a[i][j]=i*j;
AO（m2）BO（n2）CO（m*n）DO（m+n）
14、下面程序段的时间复杂度为（）
intf（unsignedintn）{
if（n==0||n==1）return1;
elsereturnn*f（n-1）;
}
AO
（1）BO（n）CO（n2）DO（n!
）
15、线性表若是采用链式存储结构时，要求内存中可用存储单元的地址（）。
A必须是连续的
B部分地址必须是连续的
C一定是不连续的
D连续或不连续都可以
16、数据结构的定义为（D，S），其中D是（）的集合。
A算法B数据元素C数据操作D逻辑结构
17、算法分析的目的是（）。
A找出数据结构的合理性
B研究算法中输入和输出的关系
C分析算法的效率以求改进
D分析算法的易懂性和文档性
18、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（）。
As->link=p;p->link=s;
Bs->link=p->link;p->link=s;
Cs->link=p->link;p=s;
Dp->link=s;s->link=p;
19、设单链表中结点结构为（data,link）.已知指针q所指结点是指针p所指结点
的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作（）
As->link=p->link;p->link=s;Bq->link=s;s->link=p
Cp->link=s->link;s->link=p;Dp->link=s;s->link=q;
20、设单链表中结点结构为（data,link）.若想摘除结点*p的直接后继，则应执
行下列哪一个操作（）
Ap->link=p->link->link;
Bp=p->link;p->link=p->link->link;
Cp->link=p->link;Dp=p->link->link;
21、设单循环链表中结点的结构为（data,link）,且rear是指向非空的带表头
结点的单循环链表的尾结点的指针。
若想删除链表第一个结点，则应执行下列哪
一个操作（D）
As=rear;rear=rear->link;deletes;Brear=rear->link;deleterear;
Crear=rear->link->link;deleterear;
Ds=rear->link->link;rear->link->link=s->link;deletes;s为第一个
结点硫
22、设单循环链表中结点的结构为（data,link）,且first
为指向链表表头的指
针，current
为链表当前指针，在循环链表中检测current
是否达到链表表尾的
语句是（D
）
。
A
current->link=nullBfirst->link=current
C
first=current
D
current->link=first
？
23、一个栈的入栈序列为
a，b，c，则出栈序列不可能的是（C）。
A
c,b,a
B
b,a,c
Cc,a,b
Da,c,b
24、栈的数组表示中，top
为栈顶指针，栈空的条件是（A）。
A
top=0
Btop=maxSizeC
top=maxSize
Dtop=-1
25、栈和队列的共同特点是（C）。
A
都是先进后出
B
都是先进先出
C
只允许在端点处插入和删除
D没有共同点
26、假定一个顺序存储的循环队列的队头和队尾指针分别为
f和r,则判断队空
的条件为（D）.
Af+1==rBr+1==fCf==0Df==r
27、当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（B）
An-2Bn-1CnDn+1
28、当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则
向这个栈插入一个元素时，首先应执行（）语句修改top指针。
Atop++;Btop--;Ctop=0;Dtop;
29、设链式栈中结点的结构为（data,link）,且top是指向栈顶的指针。
若想
摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行下列（A）
操作。
Ax=top->data;top=top->link;Cx=top;top=top->link;
Btop=top->link;x=top->data;
Dx=top->data;
30、设循环队列的结构是：
constintMaxsize=100;
typedefintDataType;
typedefstruct{
DataTypedata[Maxsize];
Intfront,rear;
}Queue;
若有一个Queue类型的队列Q，试问判断队列满的条件应是下列哪一个语句
（D）
AQ.front==Q.rear;
CQ.front+Q.rear==Maxsize;
BQ.front-Q.rear==Maxsize;
DQ.front==（Q.rear+1）%Maxsize;
31、设有一个递归算法如下：
intfact（intn）
{if（n<=0）return1;elsereturnn*fact（n-1）;
}
下面正确的叙述是（B）
A计算fact（n）需要执行n次递归Bfact（7）=5040
C此递归算法最多只能计算到fact（8）D以上结论都不对
32、设有一个递归算法如下
intx（intn）{
if（n<=3）return1;
elsereturnx（n-2）+x（n-4）+1;
}
试问计算x（x（8））时需要计算（D）次x函数。
A8次B9次C16次D18次
33、设有广义表D（a,b,D）,其长度为（B），深度为（A）
A∞
B3
C2
D5
34、广义表A（a）,则表尾为（C）
AaB（（））C空表D（a）
35、下列广义表是线性表的有（C）
AE（a,（b,c））BE（a,E）CE（a,b）D
E（a,L（））
36、递归表、再入表、纯表、线性表之间的关系为（C）
A再入表>递归表>纯表>线性表B递归表>线性表>再入表>纯表
C递归表>再入表>纯表>线性表D递归表>再入表>线性表>纯表
37、某二叉树的前序和后序序列正好相反，则该二叉树一定是（B）的二叉
树。
A空或只有一个结点B高度等于其结点数
C任一结点无左孩子D任一结点无右孩子
38、对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点为n2.,则
（A）
An
0=
n
2
+1Bn
2
=n
+1Cn
0=
2n
2
+1
Dn
2
=2n+1
0
0
39、由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路
径长度为（B）
A24B73C48D53
40、已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点
的地址为da1,则第I个结点的地址为（A）。
Ada1+（I-1）*mBda1+I*mCda1-I*mDda1+（I+1）*m
41、34具有35个结点的完全二叉树的深度为（A）
A5B6C7D8
42、对线性表进行折半搜索时，要求线性表必须（C）
A以链接方式存储且结点按关键码有序排列B以数组方式存储
C以数组方式存储且结点按关键码有序排列D以链接方式存储
43、顺序搜索算法适合于存储结构为（B）的线性表。
A散列存储B顺序存储或链接存储
C压缩存储D索引存储
44、采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度为（C）
AO（n2）BO（nlog2n）CO（log2n）DO（n）
45、对于一个具有n个顶点和e条边的无向图，进行拓扑排序时，总的时间为
（A）
AnBn+1Cn-1Dn+e
46、判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用
（C）。
A求关键路径的方法B求最短路径的Dijkstra方法
C深度优先遍历算法D广度优先遍历算法
47、在10阶B-树中根结点所包含的关键码个数最多为（C），最少为（A）
A1B2C9D10
48、对包含n个元素的散列表进行搜索，平均搜索长度为（C）
AO（log2n）BO（n）C不直接依赖于nD上述都不对
二、
填空题（）
1、数据的逻辑结构被分为集合结构、线性结构、树形结构、图形结构
四种
2、数据的存储结构被分为顺序结构、链接结构、索引结构、散列结构
3、一种抽象数据类型包括（数据）和（操作）两个部分。
4、设有两个串p和q，求p在q中首次出现的位置的运算称为（模式匹配）
5、栈、队列逻辑上都是（线性存储）结构。
四种
6、线性结构反映结点间的逻辑关系是（一对一）的，图中的数据元素之间的关系是（多对多）的，树形结构中数据元素间的关系是（一对多）的。
7、栈中存取数据的原则（后进先出），队列中存取数据的原则（先进先出）
8、串是由（零个或多个）字符组成的序列。
（长度为零的串）称为空串，（由一个或多个空格组成的串）称为空格串。
9、设目标串T=”abccdcdccbaa”,模式P=”cdcc”则第（6）次匹配成功。
10、一维数组的逻辑结构是（线性结构），存储结构是（顺序存储表示）。
对于二维数组，有（行优先顺序）和（列优先顺序）两种不同的存储方式，对于一个
二维数组A[m][n],若采用按行优先存放的方式，则任一数组元素A[i][j]相对于A[0][0]的地址为（n*i+j）。
11、向一个顺序栈插入一个元素时，首先使（栈顶指针）后移一个位置，然后把待插入元素（写）到这个位置上。
从一个顺序栈删除元素时，需要前移一位（栈顶指针）。
12、在一个循环队列Q中，判断队空的条件为（
Q.front==Q.rear）,
判断队满
的条件为（（Q.rear+1）%MaxSize==q.front
）
13、对于一棵具有n个结点的树，该树中所有结点的度数之和为（n-1
）。
14、一棵高度为5
的满二叉树中的结点数为（
63）个，一棵高度为
3满四叉
树中的结点数为（
85
）个。
15、若对一棵二叉树从
0开始进行结点编号，并按此编号把它顺序存储到一维数
组中，即编号为0
的结点存储到a[0]
中，其余类推，则a[i]
元素的左子女结点
为（2*i+1），右子女结点为（2*i+2
），双亲结点（i>=1
）为（「（i-1）/2
┐）.
16、在一个最大堆中，堆顶结点的值是所有结点中的（最大值），在一个最小堆中，堆顶结点的值是所有结点中的（最小值）。
17、已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，
第一个元素的地址为
LOC（a1），那么，LOC（ai）=LOC（a1）+（i-1）*k
。
18、在霍夫曼编码中，若编码长度只允许小于等于
4,则除掉已对两个字符编码
为0和
10外，还可以最多对（
4
）个字符编码。
19、设高度为
h的空二叉树的高度为
-1，只有一个结点的二叉树的高度为
0，若
设二叉树只有度为2上度为0的结点，则该二叉树中所含结点至少有
（2h+1）个。
20、由一棵二叉树的前序序列和（中序序列）可唯一确定这棵二叉树。
21、以折半搜索方法搜索一个线性表时，此线性表必须是（顺序）存储的（有序）
表。
22、已知完全二叉树的第
8层有
8个结点，则其叶子结点数是（
68）。
若完全二
叉树的第
7有
10个叶子结点，则整个二叉树的结点数最多是（
235）
23、对于折半搜索所对应的判定树，它既是一棵（二叉搜索树）
，又是一棵（理
想平衡树）。
24、假定对长度n=50的有序表进行折半搜索，则对应的判定树高度为（５），判定树中前５层的结点数为（３１），最后一层的结点数为（１９）。
25、在一个无向图中，所有顶点的度数之和等于所有边数的（２）倍。
在一个具
有n个顶点的无向完全图中，包含有（n（n-1）/2）条边，在一个具有n个顶
点的有向完全图中，包含有（n（n-1））条边。
26、对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别
为（n）和（n-1）。
27、设线性表中元素的类型是实型，其首地址为1024，则线性表中第6个元素
的存储位置是（1044）。
28、在插入和选择排序中，若初始数据基本正序，则选择（插入排序），若初始
数据基本反序，则最好选择（选择排序）。
29、算法是对特定问题的求解步驟的一种描述，它是（指令）的有限序列，每一
条（指令）表示一个或多个操作。
30、对于一个具有n个顶点肯e条边的无向图，进行拓朴排序时，总的进间为
（n）
31、构造哈希函数有三种方法，分别为（平方取中）法、（除留余数）法、（折迭移
位）法。
32、处理冲突的三种方法，分别为（线性探测）、（随机探测）、（链地址法）。
33、对于含有n个顶点和e条边的无向连通图，利用普里姆算法产生的最小生成
树，其时间复杂度为（Ｏ（n2））、利用克鲁斯卡尔算法产生的最小生成树，其时间复杂度为（Ｏ（elog2e））
34、快速排序在平均情况下的时间复杂度为（Ｏ（nlog2n）），在最坏情况下的
时间复杂度为（Ｏ（n2））；快速排序在平均情况下的空间复杂度为（Ｏ（log2n）），
在最坏情况下的空间复杂度为（Ｏ（n））。
35、假定一组记录的排序码为（４６，７９，５６，３８，４０，８０），对其
进行归并排序的过程中，第二趟排序后的结果是（［３８４６５６７９］
［４０８０］）
36、假定一组记录的排序码为（４６，７９，５６，３８，４０，８０），对其
进行快速排序的第一次划分的结果是（［３８４０］４６［５６７９８０］）。
37、一个结点的子树的（个数）称为该结点的度。
度为（零）的结点
称为叶结点或终端结点。
度不为（零）的结点称为分支结点或非终端结点。
树中各结点度的（最大值）称为树的度。
38、设Ki=Kj（1<=i<=n,1<=j<=n,j<>i）且在排序前的序列中Ri领先于Rj（i
若排序后的序列中Ri仍领先于Rj，则这种排序方法是（稳定的），反之是（不稳
定的）。
40、在堆排序的过程中，对任一分支结点进行调整运算的时间复杂度为（Ｏ
（log2n）），整个排序过程的时间复杂度为（Ｏ（nlog2n））。
41、在索引表中，每个索引项至少包含有（关键码值）域和（子表地址）域这两
项。
42、假定一个线性表为
（”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkwte”,”ccdt”,”aayb”）,若按照字符
串的第一个字母进行划分，使得同一个字母被划分在一个子表中，则得到的a,b,c
三个子表的长度分别为（３），（３），（２）。
43、对于包含５０个关键码的３阶B-树，其最小高度为（４），最大高度为（５）。
44、从一棵B-树删除关键码的过程，若最终引起树根结点的合并，则新树比原
树的高度（减１）
45、假定要对长度n=100的线性表进行散列存储，并采用开散列法处理冲突，则对于长度m=20的散列表，每个散列地址的同义词子表的长度平均为（５）。
46、在散列存储中，装载因子α又称为装载系数，若用m表示散列表的长度，n
表示待散列存储的元素的个数，则α等于（n/m）。
47、在有向图的邻接矩阵中，第i行中“1”的个数是第i个顶点的（出度），第
i列中“1”的个数是第i个顶点的（入度）。
在无向图的邻接矩阵中，第i行（列）中“1”的个数是第i个顶点的（度），矩阵中“1”的个数的一半是图中的（边
数）。
48、在对m阶B-树中，每个非根结点的关键码数最少为（「m/2┐-1）个，最多为（m-1）个，其子树棵数最少为（「m/2┐），最多为（m）。
三、判断题
四、运算应用题
1、在一个有n个元素的顺序表的第
i个元素（1
i
n）之前插入一个新
元素时，需要向后移动
升级会员 