数据结构期末考试模拟题Word文档格式.docx
《数据结构期末考试模拟题Word文档格式.docx》由会员分享，可在线阅读，更多相关《数据结构期末考试模拟题Word文档格式.docx（15页珍藏版）》请在冰点文库上搜索。
hs=s;
D.s->
next=hs;
hs=hs->
11.在一个链队列中，假定front和rear分别为队首指针和队尾指针，则进行插入*s结点的操作时应执行。
A.front->
front=s;
B.rear->
rear=s;
C.front=front->
D.front=rear->
12.线性表是。
A.一个有限序列，可以为空B.一个有限序列，不能为空
C.一个无限序列，可以为空D.一个无限序列，不能为空
13.对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的，删除一个元素时大约要移动表中的个元素。
A.n+1B.n-1C.（n-1）/2D.n
14.线性表采用链式存储时，其地址。
A.必须是连续的B.部分地址必须是连续的
C.一定是不连续的D.连续与否均可以
14.根据线性表的链式存储结构，每个结点所含指针的个数，链表分为单链表和。
A.循环链表B.多重链表C.普通链表D.无头结点链表
15.下列函数中渐进时间复杂度最小的是。
A.T1（n）=nlog2n＋5000nB.T3（n）=nlog2n－6000n
C.T2（n）=n2－8000nD.T4（n）=2log2n－7000n
16.在数据结构中，与所使用的计算机无关的数据叫结构。
A.存储B.物理C.逻辑D.物理和存储
17.在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上。
A.一定相邻B.不一定相邻C.有时相邻
18.假定在一棵二叉树中，双分支结点数为15个，单分支结点数为32个，则叶子结点数为。
A.15B.16C.17D.47
19.假定一棵二叉树的结点数为18个，则它的最小高度。
A.4B.5C.6D.18
20.在一棵二叉树中第五层上的结点数最多为。
A.8B.15C.16D.32
21.在一棵具有五层的满二叉树中，结点总数为。
A.31B.32C.33D.16
22.由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为________。
A24B48C72D53
23.已知8个数据元素为（34、76、45、18、26、54、92、65），按照依次插入结点的方法生成一棵二叉排序树后，最后两层上的结点总数为。
A.1B.2C.3D.4
24.在树中除根结点外，其余结点分成m（m≥0）个的集合T1,T2,T3...Tm,每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。
A.互不相交B.可以相交
C.叶结点可以相交D.树枝结点可以相交
25.下面答案是查找二叉树（又称二叉排序树）。
A.二叉树中的每个结点的两棵子树的高度差的绝对值不大于１
B.二叉树中的每个结点的两棵子树的高度差等于１
C.二叉树中的每个结点的两棵子树是有序的
D.二叉树中的每个结点的关键字大于其左子树（如果存在）所有结点的关键字值，且小于其右子树（如果存在）所有结点的关键字值。
26.将含100个结点的完全二叉树从根这一层开始，每层从左至右依次对结点编号，根结点的编号为1。
编号为49的结点X的双亲的编号为。
A.23B.24C.25D.2无法确定
27.在完全二叉树中，当i为奇数且不等于１时，结点i的左兄弟是结点，否则没有左兄弟。
A.2i-1B.i+1C.2i+1D.i-1
28.某二叉树T有n个结点，设按某种遍历顺序对T中的每个结点进行编号，编号值为1,2,…,n且有如下性质：
T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树的结点中，其最小编号等于V左子树上结点的最大编号加1。
这时按编号。
A.中序遍历序列B.前序遍历序列C.后序遍历序列D.层次遍历序列
29.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。
A.1/2B.1C.2D.4
30.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为。
A.nB.n+1C.n-1D.n+e
31.具有n个顶点的无向完全图，边的总数为条。
A.n-1B.nC.n+1D.n*（n-1）/2
32.设图G有n个顶点和e条边，当G是非孤立顶点的连通图时有2e>
=n,故可推得深度优先搜索的时间复杂度为。
A.O（e）B.O（n）C.O（ne）D.O（n+e）
33.由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为。
A.23B.37C.44D.46
34.在无向图G的邻接矩阵A中，若A[i,j]等于1，则A[j,i]等于。
A.i+jB.i-jC.1D.0
35.图的深度优先或广度优先遍历的空间复杂性均为。
（访问标志位数组空间）
A.O（n）B.O（e）C.O（n-e）D.O（n+e）
36.二分法查找存储结构。
A.只适用于顺序B.只适用于链式C.既适用于顺序也适用于链式
D.既不适合于顺序也不适合于链式
37.已知一个有序表为（12、18、24、35、47、50、62、83、90、115、134），当二分查找值为90的元素时，次比较后查找成功；
当二分查找值为47的元素时，D次比较后查找成功。
38.散列函数有一个共同性质，即函数值应当以取其值域的每个值。
A.最大概率B.最小概率C.平均概率D.同等概率
39．用线性探测法查找闭散列上，可能要探测多个散列地址，这些位置上的键值。
A.一定都是同义词 B.一定都不是同义词 C.相同 D.不一定都是同义词
40.设散列地址空间为0～m－1,k为关键字，用p去除k，将所得的余数作为k的散列地址，即H（k）＝k%p。
为了减少发生冲突的频率，一般取p为。
A.小于m的最大奇数B.小于m的最大偶数C.mD.小于m的最大素数
41.现在A、B、C、D四个元素相继进行入栈操作，下面不可能得到的入栈序列为：
A.ABCDB.BDACC.CBDAD.DCBA
二、判断题
1．数据元素是数据的最小单位（）。
2．数据项是数据的基本单位（）。
3．顺序存储的线性表可以随机存取（）。
4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此，是属于同一数据对象（）。
5．在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点查找任何一个元素（）。
6．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构（）。
7．链表的每个结点中，都恰好包含一个指针（）。
8.中序遍历二叉排序树的结点不能得到排好序的结点序列。
（）
9.完全二叉树一定是满二叉树。
10.满二叉树一定是完全二叉树。
11．由二叉树的前序和中序遍历序列可以推导出此二叉树的后序遍历序列。
12.由树转换成二叉树，其根结点的右子树总是空的（）。
13.后序遍历树和中序遍历与该树对应的二叉树，其结果不同（）。
14.若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点（）。
15.若一个树叶是某子树的中序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点（）。
16.已知二叉树的前序遍历和后序遍历序列并不能唯一地确定这棵树，因为不知道树的根结点是哪一个（）。
17.在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理（）。
18.有回路的图不能进行拓扑排序（）。
19.连通分量是无向图中的极小连通子图（）。
//极大//
20.散列法存储的基本思想是由关键码的值决定数据的存储地址（）。
21.散列表的查找效率取决于散列表造表时选取的散列函数和处理冲突的方法（）。
22.中序遍历二叉排序树的结点就可以得到排好序的结点序列（）。
23.在二叉排序树上插入新的结点时，不必移动其它结点，仅需改动某个结点的指针，由空变为非空即可（）。
24.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。
25.算法就是程序。
第1章作业题
设n为正整数。
试确定下列各程序段中前置以记号@的语句的频度和时间复杂度：
（1）i=1;
k=0;
While（i<
=n-1）{
@k+=10*I;
i++;
}
（2）i=1;
do（i<
}while（I<
=n-1）;
（3）i=1;
@k+=10*i;
}
（4）k=0;
for（i=1;
i<
=n;
i++）{
for（j=i;
j<
j++）
@k++;
（5）for（i=1;
j++）{
for（k=1;
k<
=j;
k++）
@x+=delta;
第2章作业题
本章练习题中的顺序表和线性链表的类型定义如下：
typedefstruct//顺序表
{
ElemType*elem;
intlength;
intlistsize;
}SqList;
typedefstructLNode//单链表结点
{
ElemTypedata;
structLNode*next;
}LNode,*LinkList;
【基础知识题】
2.1简述以下算法的功能。
（1）voidA（LinkedListL）{//L是无表头结点的单链表
if（L&
&
L->
next）{
Q=L;
L=L->
P=L;
while（P->
next）P=P->
next;
P->
next=Q;
Q->
next=NULL;
}
}//A
（2）voidBB（LNode*s,LNode*q）{
p=s;
while（p->
next!
=q）p=p->
p->
next=s;
}//BB
voidAA（LNode*pa,LNode*pb）{
//pa和pb分别指向单循环链表中的两个结点
BB（pa,pb）;
BB（pb,pa）;
}//AA
2.2已知L是无表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。
a．在P结点后插入S结点的语句序列-----------------------------。
b．在P结点前插入S结点的语句序列-----------------------------。
c．在表首插入S结点的语句序列---------------------------------。
d．在表尾插入S结点的语句序列---------------------------------。
（1）P->
next=S;
（2）P->
next=P->
next->
（3）P->
next=S->
（4）S->
（5）S->
next=L；
（6）S->
next=NULL；
（7）Q=P；
（8）while（P->
=Q）P=P->
（9）while（P->
=NULL）P=P->
（10）P=Q;
（11）P=L;
（12）L=S;
（13）L=P；
2.3已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。
e．删除P结点的直接后继结点的语句序列---------------------。
f．删除P结点的直接前驱结点的语句序列---------------------。
g．删除P结点的语句序列---------------------。
h．删除首元结点的语句序列---------------------。
i．删除尾元结点结点的语句序列-----------。
（1）P=P->
next=P;
next=P->
（4）P=P->
（5）while（P!
（6）while（Q->
=NULL）{P=Q;
Q=Q->
（7）while（P->
next!
（10）Q=P;
（11）Q=P->
（12）P=L;
（13）L=L->
（14）free（Q）;
【编程练习题】
2.4设顺序表a中的数据元素递增有序。
试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。
2.5试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1,a2,…,an）逆置为（an,an-1,…,a1）。
2.6试写一算法，对单链表实现就地逆置。
2.7 编写算法删除顺序表中"
多余"
的数据元素，即使操作之后的顺序表中所有元素的值都不相
第3章
本章练习题中可以利用的栈和队列的类型定义如下：
//stack类型
voidInitStack（stack&
s）;
//初始化s为空栈
voidPush（stack&
s,charx）;
//将元素x插入s的栈顶
voidPop（stack&
//删除s中的栈顶元素
boolStackEmpty（stack&
s）;
//若栈s为空则返回TRUE,否则返回FALSE
charGetTop（stack&
//返回s中的栈顶元素
voidClearStack（stack&
//将栈s清空
intStackLength（stack&
//返回栈s中元素个数
voidDestroyStack（stack&
//销毁栈s结构
//queue类型
voidInitQueue（queue&
q）;
//初始化q为空栈
voidEnQueue（queue&
q,charx）;
//将元素x插入q的队尾
voidDequeue（queue&
q）;
//删除q中队头元素
charGetHead（queue&
//返回q中队头元素
boolQueueEmpty（queue&
//若队列q为空则返回TRUE,否则返回FALSE
voidClearQueue（queue&
//将队列q清空
intQueueLength（queue&
//返回队列q中元素个数
voidDestroyQueue（queue&
//销毁队列q结构
3.1
（1）设S[1..max]为顺序存储的栈，变量top指示栈顶的位置，栈为空的条件是__________,栈为满的条件是__________。
（2）一个栈的入栈序列是a,b,c,d,e,，则栈的不可能序列是：
（A）edcba（B）decba（C）dceab（D）abcde
（3）设循环队列中数组下标的范围是1--n，其头尾指针分别为f和r，则其元素的个数为（）
（a）r-f（b）r-f+1（c）（r-f）modn+1（d）（r-f+n）modn
（4）若一个最大长度为M的循环队列的队首和队尾指针用front和rear表示，则判别队为满的条件是:
（A）（rear-1）%M=front（B）（rear+1）%M=front
（C）rear=（front-1）%M（D）rear=（front+1）%M标识的循环队列，若队列不满
3.2写出下列程序段的输出结果（栈的元素类型SElemType为char）。
voidmain（）{
StackS;
charx,y;
InitStack（S）;
x='
c'
;
y='
k'
Push（S,x）;
Push（S,'
a'
）;
Push（S,y）;
Pop（S,x）;
t'
Push（S,x）;
s'
while（!
StackEmpty（S））{Pop（S,y）;
printf（y）;
};
printf（x）;
}
3.3简述以下算法的功能（栈的元素类型SElemType为int）。
（1）statusalgo1（StackS）{
inti,n,A[255];
n=0;
while（!
StackEmpty（S））{n++;
Pop（S,A[n]）;
for（i=1;
i<
=n;
i++）Push（S,A[i]）;
}
（2）statusalgo2（StackS,inte）{
StackT;
intd;
InitStack（T）;
StackEmpty（S））{
Pop（S,d）;
if（d!
=e）Push（T,d）;
}
StackEmpty（T））{
Pop（T,d）;
Push（S,d）;
3.4简述以下算法的功能（栈和队列的元素类型均为int）。
voidalgo3（Queue&
Q）
InitStack（S）;
QueueEmpty（Q））{ DeQueue（Q,d）;
Push（S,d）;
StackEmpty（S））{ Pop（S,d）;
EnQueue（Q,d）;
}
3.5.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。
第6章
6.1.高度为h的完全二叉树至少有多少个结点?
至多有多少个结点?
6.2如果一棵树有n1个度为1的结点,有n2个度为2的结点,…,nm个度为m的结点,试问有多少个度为0的结点?
试推导之。
6.3由如图6.2所示的二叉树，回答以下问题：
⑴其中序遍历序列为_____________；
⑵其前序遍历序列为_____________；
⑶其后序遍历序列为_____________；
6.4将如图6.3所示的一个普通树转换成一棵二叉树，
并写出它先序、中序、后序三种遍历的遍历序列。
升级会员 