数据结构试题及答案Word格式文档下载.docx
《数据结构试题及答案Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《数据结构试题及答案Word格式文档下载.docx（12页珍藏版）》请在冰点文库上搜索。
9.对广义表L=（（a,b）,（c,d）,（e,f））执行操作tail（tail（L））的结果是（）
A.（e,f）B.（（e,f））
C.（f）D.（）
10.下列图示的顺序存储结构表示的二叉树是（）
11.n个顶点的强连通图中至少含有（）
A.n-1条有向边B.n条有向边
C.n（n-1）/2条有向边D.n（n-1）条有向边
12.对关键字序列（56，23，78，92，88，67，19，34）进行增量为3的一趟希尔排序的结果为（）
A.（19，23，56，34，78，67，88，92）B.（23，56，78，66，88，92，19，34）
C.（19，23，34，56，67，78，88，92）D.（19，23，67，56，34，78，92，88）
13.若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为
A.4B.5
C.8D.9
14.由同一关键字集合构造的各棵二叉排序树（）
A.其形态不一定相同，但平均查找长度相同
B.其形态不一定相同，平均查找长度也不一定相同
C.其形态均相同，但平均查找长度不一定相同
D.其形态均相同，平均查找长度也都相同
15.ISAM文件和VSAM文件的区别之一是（）
A.前者是索引顺序文件，后者是索引非顺序文件
B.前者只能进行顺序存取，后者只能进行随机存取
C.前者建立静态索引结构，后者建立动态索引结构
D.前者的存储介质是磁盘，后者的存储介质不是磁盘
二、填空题（本大题共10小题，每空2分，共20分）
16.数据的逻辑结构在计算机存储器内的表示，称为数据的____________。
17.删除双向循环链表中*p的前驱结点（存在）应执行的语句是____________。
18.栈下溢是指在____________时进行出栈操作。
19.已知substr（s,i,len）函数的功能是返回串s中第i个字符开始长度为len的子串，strlen（s）函数的功能是返回串s的长度。
若s=″ABCDEFGHIJK″,t=″ABCD″,执行运算substr（s,strlen（t）,strlen（t））后的返回值为____________。
20.去除广义表LS=（a1,a2,a3,……，an）中第1个元素，由其余元素构成的广义表称为LS的____________。
21.已知完全二叉树T的第5层只有7个结点，则该树共有____________个叶子结点。
22.在有向图中，以顶点v为终点的边的数目称为v的____________。
23.当关键字的取值范围是实数集合时，无法进行箱排序和____________排序。
24.产生冲突现象的两个关键字称为该散列函数的____________。
25.假设散列文件中一个桶能存放m个记录，则桶“溢出”的含义是，当需要插入新的记录时，该桶中____________。
三、解答题（本大题共4小题，每小题5分，共20分）
26.假设以数组seqn［m］存放循环队列的元素，设变量rear和quelen分别指示循环队列中队尾元素的位置和元素的个数。
（1）写出队满的条件表达式；
（2）写出队空的条件表达式；
（3）设m=40,rear=13,quelen=19,求队头元素的位置；
（4）写出一般情况下队头元素位置的表达式。
27.已知一棵二叉树的中序序列为ABCDEFG，层序序列为BAFEGCD，请画出该二叉树。
28.画出下图所示有向图的所有强连通分量。
29.对7个关键字进行快速排序，在最好的情况下仅需进行10次关键字的比较。
（1）假设关键字集合为{1,2,3,4,5,6,7}，试举出能达到上述结果的初始关键字序列；
（2）对所举序列进行快速排序，写出排序过程。
四、算法阅读题（本大题共4小题，每小题5分，共20分）
30.阅读下列算法，并回答问题：
（1）设顺序表L=（3,7,11,14,20,51），写出执行f30（&
L,15）之后的L；
（2）设顺序表L=（4,7,10,14,20,51），写出执行f30（&
L,10）之后的L；
（3）简述算法的功能。
voidf30（SeqList*L,DataTypex）
{
inti=0,j;
while（i<
L->
length&
&
x>
data［i］）i++;
if（i<
x==L->
data［i］）{
for（j=i+1;
j<
length;
j++）
L->
data［j-1］=L->
data［j］;
length--;
}else{
for（j=L->
j>
i;
j--）
data［j］=L->
data［j-1］;
data［i］=x;
length++;
}
}
31.已知图的邻接表表示的形式说明如下：
#defineMaxNum50//图的最大顶点数
typedefstructnode{
intadjvex;
//邻接点域
structnode*next;
//链指针域
}EdgeNode;
//边表结点结构描述
typedefstruct{
charvertex;
//顶点域
EdgeNode*firstedge;
//边表头指针
}VertexNode;
//顶点表结点结构描述
VertexNodeadjlist［MaxNum］;
//邻接表
intn,e;
//图中当前的顶点数和边数
}ALGraph;
//邻接表结构描述
下列算法输出图G的深度优先生成树（或森林）的边。
阅读算法，并在空缺处填入合适的内容，使其成为一个完整的算法。
typedefenum{FALSE,TRUE}Boolean;
Booleanvisited［MaxNum］;
voidDFSForest（ALGraph*G）{
inti;
for（i=0;
i<
G->
n;
i++）visited［i］=
（1）;
i++）if（!
visited［i］）DFSTree（G,i）;
voidDFSTree（ALGraph*G,inti）{
EdgeNode*p;
visited［i］=TRUE;
p=G->
adjlist［i］.firstedge;
while（p!
=NULL）{
if（!
visited［p->
adjvex］）{
printf（″<
%c,%c>
″,G->
adjlist［i］.vertex,
G->
adjlist［p->
adjvex］.vertex）;
（2）;
（3）;
32.阅读下列算法，并回答问题：
（1）假设数组L［8］={3,0,5,1,6,4,2,7}，写出执行函数调用f32（L，8）后的L；
（2）写出上述函数调用过程中进行元素交换操作的总次数。
voidf32（intR［］,intn）{
inti,t;
for（i=0;
n-1;
i++）
while（R［i］!
=i）{
t=R［R［i］］;
R［R［i］］=R［i］;
R［i］=t;
key
next
33.已知带头结点的单链表中的关键字为整数，为提高查找效率，需将它改建为采用拉链法处理冲突的散列表。
设散列表的长度为m，散列函数为Hash（key）=key%m。
链表的结点结构为：
。
请在空缺处填入适当内容，使其成为一个完整算法。
voidf33（LinkListL,LinkListH［］,intm）
{//由带头结点的单链表L生成散列表H，散列表生成之后原链表不再存在
inti,j;
LinkListp,q;
m;
H［i］=
（1）;
p=L->
next;
while（p）
{
q=p->
j=p->
key%m;
H［j］=p;
free（L）;
五、算法设计题（本大题10分）
34.假设以带双亲指针的二叉链表作为二叉树的存储结构，其结点结构的类型说明如下所示：
typedefcharDataType;
DataTypedata;
structnode*lchild,*rchild;
//左右孩子指针
structnode*parent;
//指向双亲的指针
}BinTNode;
typedefBinTNode*BinTree;
若px为指向非空二叉树中某个结点的指针，可借助该结构求得px所指结点在二叉树的中序序列中的后继。
（1）就后继的不同情况，简要叙述实现求后继操作的方法；
（2）编写算法求px所指结点的中序序列后继，并在算法语句中加注注释。
数据结构标准答案
一、单项选择题
1.（
B
）
2.（
D
）
3.（
A
4.（
5.（
6.（
C
7.（
8.（
9.（
10.（
11.（
12.（
13.（
14.（
15.（
16.存储结构
17.q=p->
pre;
q->
pre->
next=p;
p->
pre=q->
free（q）;
18.栈空
19."
DEFG"
//注意双引号不能少
20.表尾
21.２^（I-2）+M/2叶子结点．
22.入度
23.基数
24.同义词
25.已有m个同义词记录
26.
（1）quelen==m
（2）quelen==0
（3）（13-19+40）%40=34
（4）（rear-quelen+m）%m
27.
B
/
\
F
/\
E
G
/
C
D
28.3个:
a、bce、dfg
29.
我们知道，对n个关键自序列进行一趟快速排序，要进行n-1次比较，
也就是基准和其他n-1个关键字比较。
这里要求10次，而7-1+2*（3-1）=10，这就要求2趟快速排序后，算法结束。
所以，列举出来的序列，要求在做partition的时候，正好将序列平分
（1）4132657
或4137652
或4537612
或4135627.......
（2）自己列吧:
）
30.
（1）L=（3,7,11,14,15,20,51）
（2）L=（4,7,14,20,51）
（3）在顺序表L中查找数x,
找到，则删除x，
没找到，则在适当的位置插入x，插入后，L依然有序.
31.
（1）FALSE//初始化为未访问
（2）DSFTree（G,p->
adjvex）;
//从相邻结点往下继续深度搜索
（3）p=p->
//下一个未访问的相邻结点
32.
（1）L={0,1,2,3,4,5,6,7};
（2）5次
33.
（1）NULL
//初始化
（2）p->
next=H[j]//和下面一句完成头插法
（3）p=q;
//继续遍历L
34.
1）
a）*px有右孩子，则其右孩子为其中序序列中的后继
b）*px无右孩子，从*px开始回溯其祖先结点，找到第1个身份为左孩子的结点，
找到，则该结点的父结点为*px的中序序列中的后继。
找不到，则无后继。
2）
BinTNode*fintNext（BinTNode*px）
if（px->
rchild）returnpx->
rchild;
//*px有右孩子
BinTNode*q,*qp;
q=px;
while（qp=q->
parent）{//未回溯到根结点
if（qp->
lchild==q）returnqp;
//找到1）b）所述结点
q=qp;
//往上回溯
returnNULL;
//未找到
升级会员 