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；im；i+)for(j=0；jn；j+) bij=0；(b)s=0 for(i=0；in；i+)for(j=0；jn；j+) s+=bij；(c)i=1While(inext=p-next；p-next-prior=s； p-next=s；s-next=p-next； B.pnext=s；Snext=pnext； pnextprior=s；
2、snext=p； C.p-next=s；pnextprior=s； s-next=pnext；Snext=p； D.p-next-prior=s；p-next=s； s-next=p-next；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-
3、prior=s；s-next=p；p-prior-next=s；s-prior=p-prior;8下列关于链表说法错误的是 (9) 。(9)：A.静态链表中存取每一个元素的时间相同 B动态链表中存取每一个元素的时间不同 C静态链表上插入或删除一个元素不必移动其他元素 D动态链表上插入或删除一个元素不必移动其他元素9在链表中最常用的操作是在最后一个数据元素之后插入一个数据元素和删除第一个数据元素，则最节省运算时间的存储方式是 (10) 。(10)：A.仅有头指针的单链表 B仅有头指针的单循环链表 C仅有头指针的双向链表 D仅有尾指针的单循环链表二、填空题 1单链表中每个结点需要两个域，一个是数据
4、域，另一个是 (1) 。2链表相对于顺序表的优点是 (2) 和 (3) 操作方便。3表长为n的顺序表中，若在第j个数据元素(1in+1)之前插入一个数据元素，需要向后移动 (4) 个数据元素；删除第j个数据元素需要向前移动 (5) 个数据元素；在等概率的情况下，插入一个数据元素平均需要移动 (6) 个数据元素，删除一个数据元素平均需要移动 (7) 个数据元素。4单链表h为空表的条件是 (8) 。5带表头结点的单链表h为空表的条件是 (9) 。 6在非空的单循环链表h中，某个p结点为尾结点的条件是 (10)。 7在非空的双循环链表中，已知p结点是表中任一结点，则 (1)在p结点后插入s结点的语句
5、序列是： s-next=p-next；s-prior=p； (11) ； (12) (2)在p结点前插入s结点的语句序列是： s-prior=p-prior；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的单循环链表中，在尾结点
6、后插入p结点的语句序列是 (18) ； (19)；删除第一个结点的语句序列是q=r-next； (20) ；free(q)。三、应用题1简述顺序表和链表各自的优点。2简述头指针和头结点的作用。 四、算法设计题1请编写一个算法，实现将x插入到已按数据域值从小到大排列的有序表中。2设计一个算法，计算单链表中数据域值为x的结点个数。3设计一个用前插法建立带表头结点的单链表的算法。4请编写一个建立单循环链表的算法。5设计一个算法，实现将带头结点的单链表进行逆置。6编写一个算法，实现以较高的效率从有序顺序表A中删除其值在x和y之间(xAi y)的所有元素。第三章 栈和队列 一、选择题 1插入和删除只能在
7、表的一端进行的线性表，称为 (1) 。 (1)：A队列 B循环队列 C栈 D双栈 2队列操作应遵循的原则是 （2） 。 (2)：A.先进先出 B后进先出 C先进后出 D随意进出 3栈操作应遵循的原则是 （3） 。 (3)：A先进先出 B后进后出 C后进先出 D随意进出 4设队长为n的队列用单循环链表表示且仅设头指针，则进队操作的时间复杂度为 （4） 。 (4)：AO(1) BO(log2n) CO(n) DO(n2) 5设栈s和队列q均为空，先将a，b，c，d依次进队列q，再将队列q中顺次出队的元素进栈s，直至队空。再将栈s中的元素逐个出栈，并将出栈元素顺次进队列q，则队列q的状态是 (5)
8、。 (5)：Aabcd Bdcba Cbcad Ddbca 6若用一个大小为6的数组来实现循环队列，且当前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，请给出全部可能的
10、出栈序列和不可能的出栈序列。 4设栈s和队列q初始状态为空，元素a，b，c，d，e和f，依次通过栈s，一个元素出栈后即进人队列，若6个元素出队的序列是bdcfea，则栈s的容量至少应该存多少个元素? 5已知一个中缀算术表达式为 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*d BLoc(a00)+i*n+j*d CLoc(a00+j*m+i*d
12、 DLoc(a00)+(j-1)*m+i-1*d 3设二维数组Amn，每个数组元素占d个存储单元，第1个数组元素的存储地址是Loc(a00)，求按列优先顺序存放的数组元素ajj(0im-1，0jn-1)的存储地址 (3) 。 (3)：ALoc(a00+(i-1)*n+j-1*d BLoc(a00)+i*n+j*d CLoc(a00+(j-1)*m+i*d DLoc(a00)+j*m+i*d 4已知二维数组A610，每个数组元素占4个存储单元，若按行优先顺序存放数组元素a35的存储地址是1000，则a00的存储地址是 (4) 。 (4)：A872 B860 C868 D864 5若将n阶上三角矩
13、阵A，按列优先顺序压缩存放在一维数组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-1 Cj(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-j C(2n-i+1)i/2+j-I
14、 D(2n-i+2)i2+j-i 7设有10阶矩阵A，其对角线以上的元素aij(1j10，1ij)均取值为-3，其他矩阵元素为正整数，现将矩阵A压缩存放在一维数组Fm中，则m为 (7) 。(7)：A45 B46 C55 D.568设广义表L=(a，b，L)其深度是 (8) 。 (8)：A3 B C2 D都不对 9广义表B：(d)，则其表尾是 (9) ，表头是 (10) 。 (9)(10)：Ad B() C(d) D() 10下列广义表是线性表的有 （11） 。 (11)：ALs=(a，(b，c) BLs=(a，Ls) CLs=(a，b) DLs=(a，() 11.一个非空广义表的表尾 (12)
15、 。 (12)：A只能是子表 B不能是子表 C只能是原子元素 D可以是原子元素或子表 12已知广义表A=(a，(b，c)，(a，(b，c)，d)，则运算head(head(tail(A)的结果是 (13) 。 (13)：Aa B(b，c) C(a，(b，c) Dd 二、填空题 1两个串相等的充分必要条件是 (1) 。 2空串是 (2) ，其长度等于 (3) 。 3设有串S=”good”，T=”morning”，求： (1)concat(S，T)= (4) ； (2)substr(T，4，3)= (5) ； (3)index(T，”n”)= (6) ； (4)replace(S，3，2，”to”
16、)= (7) 。 4若n为主串长，m为子串长，则用简单模式匹配算法最好情况下，需要比较字符总数是 (8) ，最坏情况下，需要比较字符总数是 (9) 。 5设二维数组A810中，每个数组元素占4个存储单元，数组元素a22按行优先顺序存放的存储地址是1000，则数组元素a00的存储地址是 (10) 。 6设有矩阵压缩存储到一维数组Fm中，则m为 (11) ，-3应存放到Fk1中，k1为(12)，元素aij(1i4，1ji)按行优先顺序存放到Fk2中，k2为 (13) ，按列优先顺序存放到Fk3中，k3为 (14) 。 7广义表Ls=(a，(b)，(c，(d)的长度是 (15) ，深度是 (16)
17、，表头是 (17) ，表尾是 (18) 。 8稀疏矩阵的压缩存储方法通常有两种，分别是 (19) 和 (20) 。 9任意一个非空广义表的表头可以是原子元素，也可以是 (21) ，而表尾必定是 (22) 。 三、应用题 1已知S=”(xyz)+*”试利用联接(concat(S，T)，取子串(substr(S，i，j)和置换(replace(S，i，j，T)基本操作将S转化为T=”(x+2)*y”。 2设串S的长度为n，其中的字符各不相同，求S中互异的非平凡子串(非空且不同于S本身)的个数。 3设模式串T=”abcaaccbaca”，请给出它的next函数及next函数的修正值nextval之值
18、。 4特殊矩阵和稀疏矩阵哪一种压缩存储会失去随机存储功能? 5设n阶对称矩阵A压缩存储于一维数组Fm中，矩阵元素aij(1in，1jn)，存于Fk(0k0)的二叉树中只有度为0和度为2的结点，则此二叉树中所含的结点总数至少为 （2）。 (2)A2h B2h-1 C2h+1 Dh+1 3在树中，若结点A有4个兄弟，而且B是A的双亲，则B的度为 (3) 。 (3)：A3 B4 C5 D6 4若一棵完全二叉树中某结点无左孩子，则该结点一定是 (4) 。 (4)：A.度为1的结点 B度为2的结点 C分支结点 D叶子结点 5深度为k的完全二叉树至多有 (5) 个结点，至少有 (6) 个结点。 (5)-(
19、6)：A2k-1-1 B2k-1 C2k-1 D2k 6前序序列为ABC的不同二叉树有 (7) 种不同形态。 (7)：A3 B4 C5 D6 7若二叉树的前序序列为DABCEFG，中序序列为BACDFGE，则其后序序列为 (8) ，层次序列为 (9) 。 (8)-(9)：ABCAGFED BDAEBCFG CABCDEFG DBCAEFGD 8在具有200个结点的完全二叉树中，设根结点的层次编号为1，则层次编号为60的结点，其左孩子结点的层次编号为 (10) ，右孩子结点的层次编号为 (11) ，双亲结点的层次编号为 (12)。 (10)-(12)：A30 B60 C120 D121 9遍历一
20、棵具有n个结点的二叉树，在前序序列、中序序列和后序序列中所有叶子结点的相对次序 (13) 。 (13)：A.都不相同 B完全相同 C前序和中序相同 D中序与后序相同 10在由4棵树组成的森林中，第一、第二、第三和第四棵树组成的结点个数分别为30，10，20，5，当把森林转换成二叉树后，对应的二叉树中根结点的左子树中结点个数为 （14） ，根结点的右子树中结点个数为 (15) 。 (14)(15)：A20 B29 C30 D35 11.具有n个结点(n1)的二叉树的前序序列和后序序列正好相反，则该二叉树中除叶子结点外每个结点 (16) 。 (16)：A.仅有左孩子 B仅有右孩子 C仅有一个孩子
21、D都有左、右孩子 12判断线索二叉树中p结点有右孩子的条件是 (17) 。 (17)：A.p!=NULL Bp-rchild!=NULL Cp-rtag=0 Dp-rtag=1 13将一棵树转换成二叉树，树的前根序列与其对应的二叉树的 (18) 相等。树的后根序列与其对应的二叉树的 (19)相同。(18)(19)：A前序序列 B中序序列 C后序序列 D层次序列14设数据结构(D，R)，D=dl，d2，d3，d4，d5，d6，R=，这个结构的图形是 (20) ；用 (21) 遍历方法可以得到序列d1，d2，d3，d4，d5，d6。 (20)：A线性表 B二叉树C队列 D栈 (21)：人前序 B中
22、序 C后序 D层次 15对于树中任一结点x，在前根序列中序号为pre(x)，在后根序列中序号为post(x)，若树中结点x是结点y的祖先，下列 （22） 条件是正确的。 (22)：A.pre(x)pre(y)且post(x)post(y) Bpre(x)post(y) C. pre(x)pre(y)且post(x)pre(y)且post(x)post(y) 16每棵树都能惟一地转换成对应的二叉树，由树转换的二叉树中，一个结点N的左孩子是它在原树对应结点的 (23) ，而结点N的右孩子是它在原树里对应结点的 (24) 。 (23)(24)：A最左孩子 B最右孩子 C右邻兄弟 D左邻兄弟17二叉树
23、在线索化后，仍不能有效求解的问题是 (25) 。(25)：A前序线索树中求前序直接后继结点 B中序线索树中求中序直接前驱结点 C中序线索树中求中序直接后继结点 D后序线索树中求后序直接后继结点 18一棵具有124个叶子结点的完全二叉树，最多有 (26)个结点。 (26)：A247 B248 C249 D250 。 19实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最有效的存储结构是采用 （27） 。 (27)：A. 二叉链表 B孩子链表 C三叉链表 D顺序表 二、填空题1.树中任意结点允许有 （1）孩子结点，除根结点外，其余结点 （2） 双亲结点。2.若一棵树的广义表表示为A(B(E，F
24、)，C(C(H，I，J，K)，L)，D(M(N)。则该树的度为 (3) ，树的深度为 (4) ，树中叶子结点个数为 (5) 。3若树T中度为1、2、3、4的结点个数分别为4、3、2、2，则T中叶子结点的个数是 (6) 。 4一棵具有n个结点的二叉树，若它有m个叶子结点，则该二叉树中度为1的结点个数是 (7) 。 5深度为k(k0)的二叉树至多有 (8) 个结点，第i层上至多有 (9) 个结点。 6已知二叉树有52个叶子结点，度为1的结点个数为30则总结点个数为 (10) 。 7已知二叉树中有30个叶子结点，则二叉树的总结点个数至少是 （11） 。 8高度为6的完全二叉树至少有 (12) 个结点
25、。 9一个含有68个结点的完全二叉树，它的高度是 (13) 。 10已知一棵完全二叉树的第6层上有6个结点(根结点的层数为1)，则总的结点个数至少是 (14) ，其中叶子结点个数是 （15） 。 11已知完全二叉树第6层上有10个叶子结点，则这棵二叉树的结点总数最多是 （16） 。 12一棵树转换成二叉树后，这棵二叉树的根结点一定没有 (17) 孩子，若树中有m个分支结点，则与其对应的二叉树中无右孩子的结点个数为 （18） 。 13若用二叉链表示具有n个结点的二叉树，则有 （19） 个空链域。 14具有m个叶子结点的哈夫曼树，共有 （20）个结点。 15树的后根遍历序列与其对应的二叉树的 （21） 遍历序列相同。 16线索二叉树的左线索指向其 （22） ，右线索指向其 （23） 。 三、应用题 1具有n个结点的满二叉树的叶子结点个数是多少? 2列出前序遍历序列是ABC的所有不同的二叉树。 3已知二叉树的层次遍历序列为ABCDEFGHIJK，中序序列为DBGEHJACIKF，请构造一棵二叉树。 4已知二叉树的中序遍历序列是ACBDGHFE，后序遍历序列是ABDCFHEG，请构造一棵二叉树。 5已知二叉树的前序、中序和后序遍历序列如下，其中有一些
