数据结构试题及答案8Word文档格式.docx
《数据结构试题及答案8Word文档格式.docx》由会员分享，可在线阅读，更多相关《数据结构试题及答案8Word文档格式.docx（11页珍藏版）》请在冰点文库上搜索。
7.
对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（）的值除以9。
A.20B.18C.25D.22
8.
在有向图中每个顶点的度等于该顶点的（）。
A.入度B.出度
C.入度与出度之和D.入度与出度之差
9.
在基于排序码比较的排序算法中，（）算法的最坏情况下的时间复杂度不高于O（nlog2n）。
A.起泡排序B.希尔排序C.归并排序D.快速排序
10.
当α的值较小时，散列存储通常比其他存储方式具有（）的查找速度。
A.较慢B.较快C.相同
二、
填空题（每小题1分，共10分）
二维数组是一种非线性结构，其中的每一个数组元素最多有_________个直接前驱（或直接后继）。
将一个n阶三对角矩阵A的三条对角线上的元素按行压缩存放于一个一维数组B中，A[0][0]存放于B[0]中。
对于任意给定数组元素B[K]，它应是A中第_________行的元素。
链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的________域的值。
在一个链式栈中，若栈顶指针等于NULL则为________。
主程序第一次调用递归函数被称为外部调用，递归函数自己调用自己被称为内部调用，它们都需要利用栈保存调用后的_________地址。
在一棵树中，______结点没有后继结点。
一棵树的广义表表示为a（b（c,d（e,f）,g（h））,i（j,k（x,y））），结点f的层数为______。
假定根结点的层数为0。
在一棵AVL树（高度平衡的二叉搜索树）中，每个结点的左子树高度与右子树高度之差的绝对值不超过________。
n（n﹥0）个顶点的无向图最多有________条边，最少有________条边。
在索引存储中，若一个索引项对应数据对象表中的一个表项（记录），则称此索引为________索引，若对应数据对象表中的若干个表项，则称此索引为________索引。
三、
判断题（每小题1分，共10分）
数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。
链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。
在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。
通常递归的算法简单、易懂、容易编写，而且执行的效率也高。
一个广义表的表尾总是一个广义表。
当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。
对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（h）。
存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。
直接选择排序是一种稳定的排序方法。
闭散列法通常比开散列法时间效率更高。
四、
运算题（每小题8分，共40分）
设有一个1010的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么A[8][5]存放于B中什么位置。
这是一个统计单链表中结点的值等于给定值x的结点数的算法，其中while循环有错，请重新编写出正确的while循环。
intcount（ListNode*Ha,ElemTypex）
{//Ha为不带头结点的单链表的头指针
intn=0;
while（Ha->
link!
=NULL）{
Ha=Ha->
link;
if（Ha->
data==x）n++;
}
returnn;
已知一棵二叉树的前序和中序序列，求该二叉树的后序序列。
前序序列：
A,B,C,D,E,F,G,H,I,J
中序序列：
C,B,A,E,F,D,I,H,J,G
后序序列：
已知一个有序表（15,26,34,39,45,56,58,63,74,76,83,94）顺序存储于一维数组a[12]中，根据折半搜索过程填写成功搜索下表中所给元素34,56,58,63,94时的比较次数。
3456586394
元素值
比较次数
设散列表为HT[17],待插入关键码序列为{Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec}，散列函数为H（key）=i2，其中，i是关键码第一个字母在字母表中的序号。
现采用线性探查法解决冲突。
字母
A
B
C
D
E
F
G
H
I
J
K
L
M
序号
1
2
3
4
5
6
7
8
9
10
11
12
13
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
14
15
16
17
18
19
20
21
22
23
24
25
26
（1）
试画出相应的散列表；
（2）
计算等概率下搜索成功的平均搜索长度；
五、
算法分析题（每小题8分，共24分）
1．阅读下列算法，并补充所缺语句
voidpurge_linkst（ListNode*&
la）{
//从头指针为la的带表头结点的有序链表中删除所有值相同的多余元素，
//并释放被删结点空间。
ListNodep,q,t;
ElemTypetemp;
p=la->
while（p!
=NULL）{
q=p;
temp=p->
data;
p=p->
if（p!
=NULL&
&
________）p=p->
else{
while（p!
___）{
t=p;
p=p->
deletet;
}
q->
link=p;
}
下面给出一个排序算法，它属于数据表类的成员函数，其中currentSize是数据表实例的当前长度，Vector[]是存放数据表元素的一维数组。
template<
classT>
voiddataList<
T>
:
:
unknown（）{
Ttemp;
inti,j,n=currentSize;
for（i=1;
i<
n;
i++）
if（Vector[i].key<
Vector[i-1].key）{
temp=Vector[i];
Vector[i]=Vector[i-1];
for（j=i-2;
j>
=0;
j--）
if（temp.key<
Vector[j].key）Vector[j+1]=Vector[j];
elsebreak;
Vector[j+1]=temp;
}
写出该算法的功能。
针对有n个数据对象的待排序的数据表，在最好情况下，算法的排序码比较次数和对象移动次数分别是多少？
比较次数：
移动次数：
已知二叉树中的结点类型用BinTreeNode表示，被定义为:
structBinTreeNode{ElemTypedata;
BinTreeNode*leftChild,*rightChild;
};
其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。
根据下面函数的定义指出函数的功能。
算法中参数BT指向一棵二叉树的树根结点。
BinTreeNode*BinTreeSwopX（BinTreeNode*BT）{
if（BT==NULL）returnNULL;
else{
BinTreeNode*pt=newBinTreeNode;
pt->
data=BT->
data;
rightChild=BinTreeSwopX（BT->
leftChild）;
lefthild=BinTreeSwopX（BT->
rightChild）;
returnpt;
}
六、
算法设计题（6分）
已知二叉树中的结点类型用BinTreeNode表示，被定义为:
structBTreeNode{chardata;
其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出求一棵二叉树中结点总数的算法，该总数值由函数返回。
假定参数BT初始指向这棵二叉树的根结点。
intBTreeCount（BinTreeNode*BT）;
数据结构试题参考答案及评分标准
1.A2.B3.B4.D5.C6.A7.C8.C
9.C10.B
二、填空题（每小题1分，共10分）
1.22.（K+1）/33.指针4.空栈
5.返回6.叶子7.38.1
9.n（n-1）/2,010.稠密，稀疏
第9和10小题中有一空错则1分全扣。
三、判断题（每小题1分，共10分）
1.对2.错3.对4.错5.对6.对7.错8.错
9.错10.错
四、运算题（每小题8分，共40分）
根据题意，矩阵A中当元素下标I与J满足I≥J时，任意元素A[I][J]在一维数组B中的存放位置为I*（I+1）/2+J，因此，A[8][5]在数组B中位置为
8*（8+1）/2+5=41。
while（Ha!
C,B,F,E,I,J,H,G,D,A
021344
判断结果
元素值
比较次数//对1个给1分，全对给8分
H（Jan）=102=5，成功.H（Feb）=62=3，成功.
H（Mar）=132=6，成功.H（Apr）=12=0，成功.
H（May）=132=6，=7，成功，H（June）=102=5，=6，=7，=8，成功.
H（July）=102=5，=6，=7，=8，=9，成功.
H（Aug）=12=0，=1，成功.H（Sep）=192=9，=10，成功.
H（Oct）=152=7，=8，=9，=10，=11，成功.
H（Nov）=142=7，=8，=9，=10，=11，=12，成功.
H（Dec）=42=2，成功.
相应的散列表（6分），错一个存储位置扣1分，最多扣6分。
0
Apr
Aug
Dec
Feb
Jan
Mar
May
June
July
Sep
Oct
Nov
（1）
（2）
（1）
（4）
（5）
（6）
（2）搜索成功的平均搜索长度为
1/12*（1+2+1+1+1+1+2+4+5+2+5+6）=31/12（2分）
五、算法分析题（每小题8分，共24分）
p->
data>
temp//4分
p->
data=temp//4分
算法功能及执行效率
（1）该算法的功能是直接插入排序。
（4分）
（2）n-10（2分2分）
算法功能：
生成一棵新二叉树并返回树根指针，该二叉树是已知二叉树BT中所有结点的左、右子树交换的结果。
六、6分，请根据编程情况酌情给分。
intBTreeCount（BinTreeNode*BT）{
if（BT==NULL）return0;
//2分
elsereturnBTreeCount（BT->
leftChild）+BTreeCount（BT->
rightChild）+1;
//4分
升级会员 