《数据结构C语言描述》期末试卷.docx

《数据结构C语言描述》期末试卷.docx精品文档
精品文档
2
精品文档
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
号 ⋯
学
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
名 ⋯
姓
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
装
班 ⋯
⋯
） ⋯
系
（ ⋯
院 ⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯

精品文档
精品文档
2
精品文档
专业
《数据结构（C语言描述）》期末试卷
（ — 学年 第 学期）
题号 总分
得分
一、填空(10分)
1、一个m B-中，每个点最少有 (ceil(m/2) )个儿子点,m B+中每个点(除根外)
最多有( m )个儿子点.
2、n(n>0)个点构成的二叉，叶点最多有 ( floor((n+1)/2) )个，最少有( 1 )个。若
二叉有m个叶点，度 2的点有(m-1)个。
3、序找方法适用于存构 ( 顺序表和线性链表 )的性表，使用折半找方法
的条件是(查找表为顺序存贮的有序表 )
4、广表A=(()，(a，(b，c))，d)的表尾Gettail(A) (((a,(b,c)),d) )
5、直接插入排序，起泡排序和快速排序三种方法中， (快速排序 )所需的平均行最
小；(快速排序 )所需附加空最大。
二、(10分)
1、倒排文件的主要点是：(C)
A、便于行插入和除
B、便于行文件的合并
C、能大大提高基于非主关字数据的找速度
D、易于主关字的逆向索
2下面程序段的复性
(C)
y=0;
while(n>=(y+1)*(y+1)){
y++;
}
A、O(n)
B、O(n2)
C、O(sqrt(n))
D、O(1)
3、若从二叉的任一点出到根的路径上所的点序列按其关字有序，二叉
是(
C)
A、二叉排序
B、哈夫曼
C、堆
D、AVL
4、和列都是（B
）
A、序存的性构
B、限制存取点的性构
C、式存的性构
D、限制存取点的非性构
5、用序找方法找度
n的性表，在等概率情况下的平均找度（
D
）
A、n
B、n/2
C、(n-1)/2
D、(n+1)/2
精品文档
精品文档
3
精品文档
三、答（30分）
1、已知一棵二叉的前序描序列和中序描序列分
ABCDEFGHIJ和BCDAFEHJIG
，
出二叉的后序序列并出二叉的森林。
解：
后序序列为：DCBFJIHGEA
2、若对序列（7，3，1，8，6，2，4，5）按从小到大排序，请写出起泡排序的第一趟结果
和堆排序的初始堆。
解：
冒泡：31762458
堆：87456213
3、某通讯系统只可能有 A、B、C、D、E、F6种字符，其出现的概率分别是 、、、
、、，试画出相应的哈夫曼树，并设计哈夫曼编码。
解：
精品文档
精品文档
4
精品文档
编码：A:1011 B:0
4、在二叉平衡检索树（

C:1010 D:110 E:111 F:100
AVL树）的调整中，将最靠近新插入点的不平衡结点调整平衡后，
精品文档
精品文档
25
精品文档
树中是否还会有不平衡结点？为什么？
解：
不会再有不平衡点。因为插入结点发生不平衡现象后，会改变
以“靠近新插入点的不平衡结点”为根的子树（即最小不平横树）的高度加1，经过调整后使最小不平衡树的整体高度又恢复到原来的值，所以不会对原平衡树的其他部分造成危害，因此不会再有不平衡点。
5、指定Hash函数H(k)=3*kmod11 及线性探测开地址法处理冲突，试在 0~10的散列空间中
精品文档
精品文档
7
精品文档
对关键字序列（22，41，53，46，30，13，01，67）构造Hash表，并求在等查找概率下查找成功的平均查找长度。
解：
插入元素后的分布情况：
精品文档
精品文档
7
精品文档
0
1
2
3
4
5
6
7
8
9
10
22
41
30
01
53
46
13
6