i*=2；
3．在数据结构中，与所使用的计算机无关的是。
A．存储结构B．物理结构C．物理和存储结构D．逻辑结构
4．非线性结构中每个结点。
A．无直接前驱结点B．只有一个直接前驱和直接后继结点
C．无直接后继结点D．可能有多个直接前驱和多个直接后继结点
5．可以把数据的逻辑结构划分成。
A．内部结构和外部结构B．动态结构和静态结构
C．紧凑结构和非紧凑结构D．线性结构和非线性结构
第二章线性表
一、单项选择题
1．下面关于线性表叙述中，错误的是_
（1）_。
（1）：
A．顺序表必须占用一片地址连续的存储单元
B．链表不必占用一片地址连续的存储单元
C．顺序表可以随机存取任一元素
D．链表可以随机存取任一元素
2．在表长为n的单链表中，算法时间复杂度为O（n）的操作是
（2）。
（2）：
A．查找单链表中第i个结点B．在p结点之后插入一个结点
C．删除表中第一个结点D．删除p结点的直接后继结点
3．单链表的存储密度（3）。
（3）：
A．大于1B．等于1C．小于1D．不能确定
4．在表长为n的顺序表中，算法的时间复杂度为O
（1）的操作是（4）。
（4）：
A．在第n个结点之后插入一个结点B．在第i个结点前插入一个新结点
C．删除第i个结点D．求表长
5．在下列链表中不能从当前结点出发访问到其余各结点的是（5）。
（5）：
A．单链表B．单循环链表C．双向链表D．双向循环链表
6．在设头、尾指针的单链表中，与长度n有关的操作是（6）。
（6）：
A．删除第一个结点B．删除最后一个结点
C.在第一个结点之前插入一个结点D.在表尾结点后插入一个结点
7.设p结点是带表头结点的双循环链表中的结点，则
（1）在p结点后插入s结点的语句序列中正确的是（7）。
（7）：
A.s->next=p->next；p->next->prior=s；
p->next=s；s->next=p->next；
B.p—>next=s；S—>next=p—>next；
p—>next—>prior=s；s—>next=p；
C.p->next=s；p—>next—>prior=s；
s->next=p—>next；S—>next=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->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．单链表中每个结点需要两个域，一个是数据域，另一个是
（1）。
2．链表相对于顺序表的优点是
（2）和（3）操作方便。
3．表长为n的顺序表中，若在第j个数据元素（1≤i≤n+1）之前插入一个数据元素，需要向后移动（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；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）。
（4）：
A．O
（1）B．O（log2n）C．O（n）D．O（n2）
5．设栈s和队列q均为空，先将a，b，c，d依次进队列q，再将队列q中顺次出队的元素进栈s，直至队空。
再将栈s中的元素逐个出栈，并将出栈元素顺次进队列q，则队列q的状态是（5）。
（5）：
A．abcdB．dcbaC．bcadD．dbca
6．若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为（6）。
（6）：
A．5和1B．4和2C．2和4D．1和5
7．一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（7）。
（7）：
A.edcbaB.decbaC.dceabD.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.已知q是一个非空顺序队列，s是一个顺序栈，请设计一个算法，实现将队列q中所有元素逆置。
2．已知递归函数：
1当n=0时
F（n）=
n·F（n/2）当n>0时
（1）写出求F（n）递归算法；
（2）写出求F（n）的非递归算法。
3．假设以带头结点的循环链表表示队列，并且仅设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。
第四章串、数组和广义表
一、选择题
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
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．872B．860C．868D．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+jB．i（i-1）/2+j-1
C．j（j+1）／2+jD．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-jB.（2n-j+2）（j-1）/2+i-j
C．（2n-i+1）i/2+j-ID．（2n-i+2）i／2+j-i
7．设有10阶矩阵A，其对角线以上的元素aij（1≤j≤10，1（7）：
A．45B．46C．55D.56
8．设广义表L=（a，b，L）其深度是（8）。
（8）：
A．3B．¥C．2D．都不对
9．广义表B：
（d），则其表尾是（9），表头是（10）。
（9）—（10）：
A．dB．（）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．aB．（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．设有矩阵
压缩存储到一维数组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．已知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之值。
4．特殊矩阵和稀疏矩阵哪一种压缩存储会失去随机存储功能?
5．设n阶对称矩阵A压缩存储于一维数组F[m]中，矩阵元素aij（1≤i≤n，1≤j≤n），存于F[k]（0≤k用列优先顺序转换时的对应关系是什么?
第五章树和二叉树
一、单项选择题
1．关于二叉树的下列说法正确的是
（1）。
（1）：
A．二叉树的度为2B．二叉树的度可以小于2
C．每一个结点的度都为2D．至少有一个结点的度为
2．设深度为h（h>0）的二叉树中只有度为0和度为2的结点，则此二叉树中所含的结点总数至少为
（2）。
（2）A．2hB．2h-1C．2h+1D．h+1
3．在树中，若结点A有4个兄弟，而且B是A的双亲，则B的度为（3）。
（3）：
A．3B．4C．5D．6
4．若一棵完全二叉树中某结点无左孩子，则该结点一定是（4）。
（4）：
A.度为1的结点B．度为2的结点C．分支结点D．叶子结点
5．深度为k的完全二叉树至多有（5）个结点，至少有（6）个结点。
（5）-（6）：
A．2k-1-1B．2k-1C．2k-1D．2k
6．前序序列为ABC的不同二叉树有（7）种不同形态。
（7）：
A．3B．4C．5D．6
7．若二叉树的前序序列为DABCEFG，中序序列为BACDFGE，则其后序序列为（8），层次序列为（9）。
（8）-（9）：
A．BCAGFEDB．DAEBCFGC．ABCDEFGD．BCAEFGD
8．在具有200个结点的完全二叉树中，设根结点的层次编号为1，则层次编号为60的结点，其左孩子结点的层次编号为（10），右孩子结点的层次编号为（11），双亲结点的层次编号为（12）。
（10）-（12）：
A．30B．60C．120D．121
9．遍历一棵具有n个结点的二叉树，在前序序列、中序序列和后序序列中所有叶子结点的相对次序（13）。
（13）：
A.都不相同B．完全相同C．前序和中序相同D．中序与后序相同
10．在由4棵树组成的森林中，第一、第二、第三和第四棵树组成的结点个数分别为30，10，20，5，当把森林转换成二叉树后，对应的二叉树中根结点的左子树中结点个数为（14），根结点的右子树中结点个数为（15）。
（14）—（15）：
A．20B．29C．30D．35
11.具有n个结点（n>1）的二叉树的前序序列和后序序列正好相反，则该二叉树中除叶子结点外每个结点（16）。
（16）：
A.仅有左孩子B．仅有右孩子C．仅有一个孩子D．都有左、右孩子
12．判断线索二叉树中p结点有右孩子的条件是（17）。
（17）：
A.p!
=NULLB．p->rchild!
=NULLC．p->rtag=0D．p->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．中序C．后序D．层次
15．对于树中任一结点x，在前根序列中序号为pre（x），在后根序列中序号为post（x），若树中结点x是结点y的祖先，下列（22）条件是正确的。
（22）：
A.pre（x）B．pre（x）post（y）
C.pre（x）>pre（y）且post（x）D．pre（x）>pre（y）且post（x）>post（y）
16．每棵树都能惟一地转换成对应的二叉树，由树转换的二叉树中，一个结点N的左孩子是它在原树对应结点的（23），而结点N的右孩子是它在原树里对应结点的（24）。
（23）—（24）：
A．最左孩子B．最右孩子C．右邻兄弟D．左邻兄弟
17．二叉树在线索化后，仍不能有效求解的问题是（25）。
（25）：
A．前序线索树中求前序直接后继结点
B．中序线索树中求中序直接前驱结点
C．中序线索树中求中序直接后继结点
D．后序线索树中求后序直接后继结点
18．一棵具有124个叶子结点的完全二叉树，最多有（26）个结点。
（26）：
A．247B．248C．249D．250。
19．实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最有效的存储结构是采用（27）。
（27）：
A.二叉链表B．孩子链表C．三叉链表D．顺序表
二、填空题
1.树中任意结点允许有
（1）孩子结点，除根结点外，其余结点
（2）双亲结点。
2.若一棵树的广义表表示为A（B（E，F），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（k>0）的二叉树至多有（8）个结点，第i层上至多有（9）个结点。
6．已知二叉树有52个叶子结点，度为1的结点个数为30则总结点个数为（10）。
7．已知二叉树中有30个叶子结点，则二叉树的总结点个数至少是（11）。
8．高度为6的完全二叉树至少有（12）个结点。
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．已知二叉树的前序、中序和后序遍历序列如下，其中有一些
升级会员 