插入一个数据元素平均需要移动 (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；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．简述顺序表和链表各自的优点。 2．简述头指针和头结点的作用。 ．

四、算法设计题

1．请编写一个算法，实现将x插入到已按数据域值从小到大排列的有序表中。 2．设计一个算法，计算单链表中数据域值为x的结点个数。 3．设计一个用前插法建立带表头结点的单链表的算法。 4．请编写一个建立单循环链表的算法。

5．设计一个算法，实现将带头结点的单链表进行逆置。

6．编写一个算法，实现以较高的效率从有序顺序表A中删除其值在x和y之间(x≤A[i] ≤y)的所有元素。

第三章 栈和队列

一、选择题

1．插入和删除只能在表的一端进行的线性表，称为 (1) 。 (1)：A．队列 B．循环队列 C．栈 D．双栈 2．队列操作应遵循的原则是 （2） 。

(2)：A.先进先出 B．后进先出 C．先进后出 D．随意进出 3．栈操作应遵循的原则是 （3） 。

(3)：A．先进先出 B．后进后出 C．后进先出 D．随意进出

4．设队长为n的队列用单循环链表表示且仅设头指针，则进队操作的时间复杂度为 （4） 。

2

(4)：A．O(1) B．O(log2n) C．O(n) D．O(n)

5．设栈s和队列q均为空，先将a，b，c，d依次进队列q，再将队列q中顺次出队的元素进栈

45

s，直至队空。再将栈s中的元素逐个出栈，并将出栈元素顺次进队列q，则队列q的状态是 (5) 。

(5)：A．abcd B．dcba C．bcad D．dbca

6．若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为 (6) 。

(6)：A．5和1 B．4和2 C．2和4 D．1和5 7．一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是 （7） 。 (7)：A.edcba B.decba C.dceab D.abcde

二、填空题

1．在栈结构中，允许插入、删除的一端称为 (1) ，另一端称为 (2) 。 2．在队列结构中，允许插入的一端称为 (3) ，允许删除的一端称为 (4) 。

3．设长度为n的链队列用单循环链表表示，若只设头指针，则进队和出队操作的时间复杂度分别是 (5) 和 (6) ；若只设尾指针，则进队和出队操作的时间复杂度分别为 (7) 和 (8) 。

4．设用少用一个元素空间的数组A[m]存放循环队列，front指向实际队首，rear指向新元素应存放的位置，则判断队空的条件是 (9) ，判断队满的条件是 (10) ，当队未满时，循环队列的长度是 (11) 。

5.两个栈共享一个向量空间时，可将两个栈底分别设在 (12) 。

三、应用题

1．简述线性表、栈和队列有什么异同?

2．循环队列的优点是什么?设用数组A[m]来存放循环队列，如何判断队满和队空。 3．若进栈序列为abcd，请给出全部可能的出栈序列和不可能的出栈序列。

4．设栈s和队列q初始状态为空，元素a，b，c，d，e和f，依次通过栈s，一个元素出栈后即进人队列，若6个元素出队的序列是bdcfea，则栈s的容量至少应该存多少个元素?

5．已知一个中缀算术表达式为 3 + 4 / (25- (6+15))*8 写出对应的后缀算术表达式（逆波兰表达式）。

第四章 串、数组和广义表

一、选择题

1．串的模式匹配是指 (1) 。 (1)：A.判断两个串是否相等 B．对两个串进行大小比较

C．找某字符在主串中第一次出现的位置

D．找某子串在主串中第一次出现的第一个字符位置

2．设二维数组A[m][n]，每个数组元素占用d个存储单元，第一个数组元素的存储地址是如Loc(a[0][0])，求按行优先顺序存放的数组元素a[j][j](0≤i≤m-1，0≤j≤n-1)的存储地址 (2) 。

(2)：A．Loc(a[0][0]+[(i-1)*n+j-1]*d B．Loc(a[0][0])+[i*n+j]*d C．Loc(a[0][0]+[j*m+i]*d

D．Loc(a[0][0])+[(j-1)*m+i-1]*d

46

3．设二维数组A[m][n]，每个数组元素占d个存储单元，第1个数组元素的存储地址是Loc(a[0][0])，求按列优先顺序存放的数组元素a[j][j](0≤i≤m-1，0≤j≤n-1)的存储地址 (3) 。

(3)：A．Loc(a[0][0]+[(i-1)*n+j-1]*d B．Loc(a[0][0])+[i*n+j]*d C．Loc(a[0][0]+[(j-1)*m+i]*d D．Loc(a[0][0])+[j*m+i]*d

4．已知二维数组A[6][10]，每个数组元素占4个存储单元，若按行优先顺序存放数组元素a[3][5]的存储地址是1000，则a[0][0]的存储地址是 (4) 。 (4)：A．872 B．860 C．868 D．864

5．若将n阶上三角矩阵A，按列优先顺序压缩存放在一维数组F[n(n+1)／2]中，第1个非零元素a11存于F[0]中，则应存放到F[K]中的非零元素aij(1≤i≤n，1≤j≤i的下标i,j与K的对应关系是 (5) 。

(5)：A．i(i+1)/2+j B．i(i-1)/2+j-1 C．j(j+1)／2+j D．j(j-1)／2+i—1

6．若将n阶下三角矩阵A，按列优先顺序压缩存放在一维数组F[n(n+1)／2]中，第一个非零元素a11，存于F[0]中，则应存放到F[K]中的非零元素aij(1≤j≤n，1≤j≤i)的下标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 D．(2n-i+2)i／2+j-i

7．设有10阶矩阵A，其对角线以上的元素aij(1≤j≤10，1

(7)：A．45 B．46 C．55 D.56 8．设广义表L=(a，b，L)其深度是 (8) 。 (8)：A．3 B．? C．2 D．都不对

9．广义表B：(d)，则其表尾是 (9) ，表头是 (10) 。 (9)—(10)：A．d B．() C．(d) D．(()) 10．下列广义表是线性表的有 （11） 。 (11)：A．Ls=(a，(b，c)) B．Ls=(a，Ls) C．Ls=(a，b) D．Ls=(a，(())) 11.一个非空广义表的表尾 (12) 。

(12)：A．只能是子表 B．不能是子表

C．只能是原子元素 D．可以是原子元素或子表

12．已知广义表A=((a，(b，c))，(a，(b，c)，d))，则运算head (head(tail(A)))的结果是 (13) 。

(13)：A．a B．(b，c) C．(a，(b，c)) D．d

二、填空题

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”)= (7) 。

4．若n为主串长，m为子串长，则用简单模式匹配算法最好情况下，需要比较字符总数是 (8) ，最坏情况下，需要比较字符总数是 (9) 。

5．设二维数组A[8][10]中，每个数组元素占4个存储单元，数组元素a[2][2]按行优先顺序存放的存储地址是1000，则数组元素a[0][0]的存储地址是 (10) 。 6．设有矩阵

8 -3 -3 -3

4 2 -3 -3 6 5 7 -3 1 3 9 11

47

A=

压缩存储到一维数组F[m]中，则m为 (11) ，-3应存放到F[k1]中，k1为(12)，元素aij(1≤i≤4，1≤j≤i)按行优先顺序存放到F[k2]中，k2为 (13) ，按列优先顺序存放到F[k3]中，k3为 (14) 。

7．广义表Ls=(a，(b)，((c，(d))))的长度是 (15) ，深度是 (16) ，表头是 (17) ，表尾是 (18) 。

8．稀疏矩阵的压缩存储方法通常有两种，分别是 (19) 和 (20) 。

9．任意一个非空广义表的表头可以是原子元素，也可以是 (21) ，而表尾必定是 (22) 。

第五章 树和二叉树

一、单项选择题

1．关于二叉树的下列说法正确的是 (1)。

(1)：A．二叉树的度为2 B．二叉树的度可以小于2 C．每一个结点的度都为2 D．至少有一个结点的度为

2．设深度为h(h>0)的二叉树中只有度为0和度为2的结点，则此二叉树中所含的结点总数至少为 （2）。

(2)A．2h B．2h-1 C．2h+1 D．h+1

3．在树中，若结点A有4个兄弟，而且B是A的双亲，则B的度为 (3) 。 (3)：A．3 B．4 C．5 D．6

4．若一棵完全二叉树中某结点无左孩子，则该结点一定是 (4) 。

(4)：A.度为1的结点 B．度为2的结点 C．分支结点 D．叶子结点 5．深度为k的完全二叉树至多有 (5) 个结点，至少有 (6) 个结点。

k-1k-1 kk

(5)-(6)：A．2-1 B．2 C．2-1 D．2 6．前序序列为ABC的不同二叉树有 (7) 种不同形态。 (7)：A．3 B．4 C．5 D．6

7．若二叉树的前序序列为DABCEFG，中序序列为BACDFGE，则其后序序列为 (8) ，层次序列为 (9) 。

(8)-(9)：A．BCAGFED B．DAEBCFG C．ABCDEFG D．BCAEFGD

8．在具有200个结点的完全二叉树中，设根结点的层次编号为1，则层次编号为60的结点，其左孩子结点的层次编号为 (10) ，右孩子结点的层次编号为 (11) ，双亲结点的层次编号为 (12)。

(10)-(12)：A．30 B．60 C．120 D．121

9．遍历一棵具有n个结点的二叉树，在前序序列、中序序列和后序序列中所有叶子结点的相对次序 (13) 。

(13)：A.都不相同 B．完全相同 C．前序和中序相同 D．中序与后序相同

10．在由4棵树组成的森林中，第一、第二、第三和第四棵树组成的结点个数分别为30，10，20，5，当把森林转换成二叉树后，对应的二叉树中根结点的左子树中结点个数为 （14） ，根结点的右子树中结点个数为 (15) 。

(14)—(15)：A．20 B．29 C．30 D．35

11.具有n个结点(n>1)的二叉树的前序序列和后序序列正好相反，则该二叉树中除叶子结点外每个结点 (16) 。

(16)：A.仅有左孩子 B．仅有右孩子 C．仅有一个孩子 D．都有左、右孩子 12．判断线索二叉树中p结点有右孩子的条件是 (17) 。

(17)：A.p!=NULL B．p->rchild!=NULL C．p->rtag=0 D．p->rtag=1

13．将一棵树转换成二叉树，树的前根序列与其对应的二叉树的 (18) 相等。树的后根序列与其对应的二叉树的 (19)相同。

48