《数据结构习题集(1 积分)》由会员分享，可在线阅读，更多相关《数据结构习题集(1 积分)（71页珍藏版）》请在金锄头文库上搜索。
1、1第一章 绪论1下面是几种数据的逻辑结构 S=(D，R)，分别画出对应的数据逻辑结构，并指出它们分别属于何种结构。D=a，b，c，d，e，f R=r(a) r=，(b) r=，(c) r=，2分析下列程序段的时间复杂度(a) for(i=0；inext=p-next；p-next-prior=s； p-next=s；s-next=p-next； B.pnext=s；Snext=pnext；pnextprior=s；snext=p；C.p-next=s；pnextprior=s；s-next=pnext；Snext=p；D.p-next-prior=s；p-next=s；s-next=p-nex
2、t；s-next=p；(2)在 p 结点之前插入 s 结点的语句序列中正确的是(8)。(8)：A.s-prior=p-prior；p-prior-next p-prior=s；s-next=p； B.p-prior=s；p-prior-next=s;s-prior=p-prior；s-next=p;C.p-prior-next=s；p-prior=s;s-prior=p-prior；s-next=p; D.p-prior=s；s-next=p；p-prior-next=s；s-prior=p-prior;8下列关于链表说法错误的是 (9) 。(9)：A.静态链表中存取每一个元素的时间相同B动态
3、链表中存取每一个元素的时间不同C静态链表上插入或删除一个元素不必移动其他元素D动态链表上插入或删除一个元素不必移动其他元素9在链表中最常用的操作是在最后一个数据元素之后插入一个数据元素和删除第一个数据元素，则最节省运算时间的存储方式是 (10) 。(10)：A.仅有头指针的单链表 B仅有头指针的单循环链表3C仅有头指针的双向链表 D仅有尾指针的单循环链表二、填空题1单链表中每个结点需要两个域，一个是数据域，另一个是 (1) 。2链表相对于顺序表的优点是 (2) 和 (3) 操作方便。3表长为 n 的顺序表中，若在第 j 个数据元素(1in+1)之前插入一个数据元素，需要向后移动 (4) 个数据
4、元素；删除第 j 个数据元素需要向前移动 (5) 个数据元素；在等概率的情况下，插入一个数据元素平均需要移动 (6) 个数据元素，删除一个数据元素平均需要移动 (7) 个数据元素。4单链表 h 为空表的条件是 (8) 。5带表头结点的单链表 h 为空表的条件是 (9) 。6在非空的单循环链表 h 中，某个 p 结点为尾结点的条件是 (10)。7在非空的双循环链表中，已知 p 结点是表中任一结点，则(1)在 p 结点后插入 s 结点的语句序列是：s-next=p-next；s-prior=p； (11) ； (12) (2)在 p 结点前插入 s 结点的语句序列是：s-prior=p-prior
5、；s-next=p； (13) ； (14) (3)删除 p 结点的直接后继结点的语句序列是：q=p-next；p-next=q-next； (15) ；free(q)；(4)删除 p 结点的直接前驱结点的语句序列是：q=p-prior；p-prior=q-prior； (16) ；free(q)；(5)删除 p 结点的语句序列是：p-prior-next=p-next； (17) ；free(q)；8在带有尾指针 r 的单循环链表中，在尾结点后插入 p 结点的语句序列是 (18) ； (19)；删除第一个结点的语句序列是 q=r-next； (20) ；free(q)。三、应用题1简述顺序表
6、和链表各自的优点。2简述头指针和头结点的作用。 四、算法设计题1请编写一个算法，实现将 x 插入到已按数据域值从小到大排列的有序表中。2设计一个算法，计算单链表中数据域值为 x 的结点个数。3设计一个用前插法建立带表头结点的单链表的算法。4请编写一个建立单循环链表的算法。5设计一个算法，实现将带头结点的单链表进行逆置。6编写一个算法，实现以较高的效率从有序顺序表 A 中删除其值在 x 和 y 之间(xAi y)的所有元素。4第三章 栈和队列一、选择题1插入和删除只能在表的一端进行的线性表，称为 (1) 。(1)：A队列 B循环队列 C栈 D双栈2队列操作应遵循的原则是 （2） 。(2)：A.先
7、进先出 B后进先出 C先进后出 D随意进出3栈操作应遵循的原则是 （3） 。(3)：A先进先出 B后进后出 C后进先出 D随意进出4设队长为 n 的队列用单循环链表表示且仅设头指针，则进队操作的时间复杂度为 （4） 。(4)：AO(1) BO(log 2n) CO(n) DO(n 2)5设栈 s 和队列 q 均为空，先将 a，b，c，d 依次进队列 q，再将队列 q 中顺次出队的元素进栈 s，直至队空。再将栈 s 中的元素逐个出栈，并将出栈元素顺次进队列 q，则队列q 的状态是 (5) 。(5)：Aabcd Bdcba Cbcad Ddbca6若用一个大小为 6 的数组来实现循环队列，且当前
8、front 和 rear 的值分别为 3 和0，当从队列中删除一个元素，再加入两个元素后，front 和 rear 的值分别为 (6) 。(6)：A5 和 1 B4 和 2 C2 和 4 D1 和 57一个栈的入栈序列是 a,b,c,d,e,则栈的不可能的输出序列是 （7） 。(7)：A.edcba B.decba C.dceab D.abcde二、填空题1在栈结构中，允许插入、删除的一端称为 (1) ，另一端称为 (2) 。2在队列结构中，允许插入的一端称为 (3) ，允许删除的一端称为 (4) 。3设长度为 n 的链队列用单循环链表表示，若只设头指针，则进队和出队操作的时间复杂度分别是 (
9、5) 和 (6) ；若只设尾指针，则进队和出队操作的时间复杂度分别为 (7) 和 (8) 。4设用少用一个元素空间的数组 Am存放循环队列，front 指向实际队首，rear 指向新元素应存放的位置，则判断队空的条件是 (9) ，判断队满的条件是 (10) ，当队未满时，循环队列的长度是 (11) 。5.两个栈共享一个向量空间时，可将两个栈底分别设在 (12) 。三、应用题 1简述线性表、栈和队列有什么异同?2循环队列的优点是什么?设用数组 Am来存放循环队列，如何判断队满和队空。3若进栈序列为 abcd，请给出全部可能的出栈序列和不可能的出栈序列。4设栈 s 和队列 q 初始状态为空，元素
10、a，b，c，d，e 和 f，依次通过栈 s，一个元素出栈后即进人队列，若 6 个元素出队的序列是 bdcfea，则栈 s 的容量至少应该存多少个元素?55已知一个中缀算术表达式为 3 + 4 / (25- (6+15)*8 写出对应的后缀算术表达式（逆波兰表达式） 。四、算法设计题1.已知 q 是一个非空顺序队列，s 是一个顺序栈，请设计一个算法，实现将队列 q 中所有元素逆置。2已知递归函数： 1 当 n=0 时F(n)=nF(n/2) 当 n0 时 (1)写出求 F(n)递归算法；(2)写出求 F(n)的非递归算法。3假设以带头结点的循环链表表示队列，并且仅设一个指针指向队尾元素结点（注意
11、不设头指针） ，试编写相应的队列初始化、入队列和出队列的算法。第四章 串、数组和广义表一、选择题1串的模式匹配是指 (1) 。(1)：A.判断两个串是否相等B对两个串进行大小比较C找某字符在主串中第一次出现的位置D找某子串在主串中第一次出现的第一个字符位置2设二维数组 Amn，每个数组元素占用 d 个存储单元，第一个数组元素的存储地址是如 Loc(a00)，求按行优先顺序存放的数组元素 ajj(0im-1，0jn-1)的存储地址 (2) 。(2)：ALoc(a00+(i-1)*n+j-1*dBLoc(a00)+i*n+j*dCLoc(a00+j*m+i*dDLoc(a00)+(j-1)*m+i
12、-1*d3设二维数组 Amn，每个数组元素占 d 个存储单元，第 1 个数组元素的存储地址是 Loc(a00)，求按列优先顺序存放的数组元素 ajj(0im-1，0jn-1)的存储地址 (3) 。(3)：ALoc(a00+(i-1)*n+j-1*dBLoc(a00)+i*n+j*dCLoc(a00+(j-1)*m+i*dDLoc(a00)+j*m+i*d4已知二维数组 A610，每个数组元素占 4 个存储单元，若按行优先顺序存放数组6元素 a35的存储地址是 1000，则 a00的存储地址是 (4) 。(4)：A872 B860 C868 D8645若将 n 阶上三角矩阵 A，按列优先顺序压缩
13、存放在一维数组 Fn(n+1)2中，第 1个非零元素 a11存于 F0中，则应存放到 FK中的非零元素 aij(1in，1ji 的下标i,j 与 K 的对应关系是 (5) 。(5)：Ai(i+1)/2+j Bi(i-1)/2+j-1Cj(j+1)2+j Dj(j-1)2+i16若将 n 阶下三角矩阵 A，按列优先顺序压缩存放在一维数组 Fn(n+1)2中，第一个非零元素 a11，存于 F0中，则应存放到 FK中的非零元素 aij(1jn，1ji)的下标 i，i 与 K 的对应关系是 (6) 。(6):A.(2n-j+1)j/2+I-j B.(2n-j+2)(j-1)/2+i-jC(2n-i+1
14、)i/2+j-I D(2n-i+2)i2+j-i7设有 10 阶矩阵 A，其对角线以上的元素 aij(1j10，10)的二叉树中只有度为 0 和度为 2 的结点，则此二叉树中所含的结点总数至少为 （2） 。(2)A2h B2h-1 C2h+1 Dh+13在树中，若结点 A 有 4 个兄弟，而且 B 是 A 的双亲，则 B 的度为 (3) 。(3)：A3 B4 C5 D6A=8 -3 -3 -34 2 -3 -36 5 7 -31 3 9 1184若一棵完全二叉树中某结点无左孩子，则该结点一定是 (4) 。(4)：A.度为 1 的结点 B度为 2 的结点 C分支结点 D叶子结点5深度为 k 的完全二叉树至多有 (5) 个结点，至少有 (6) 个结点。(5)-(6)：A2 k-1-1 B2 k-1 C2 k-1 D2 k6前序序列为 ABC 的不同二叉树有 (7) 种不同形态。(7)
