下载此文档

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


文档分类:IT计算机 | 页数:约14页 举报非法文档有奖
1/14
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/14 下载此文档
文档列表 文档介绍
专业
《数据结构(C语言描述)》期末试卷
( 一 学年第 学期)
题号
总分
得分
一、填空(10分)
1、一个m阶B-树中,每个结点最少有(ceil(m/2))个儿子结点 四阶8+树中每个结点(除根外) 最多有(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、顺序存储的线性结构
C、链式存储的线性结构
B、限制存取点的线性结构
D、限制存取点的非线性结构
5、用顺序查找方法查找长度为
n的线性表时,在等概率情况下的平均查找长度为(
A、n B、n/2 C、(n-1)/2 D、(n+1)/2
三、简答(30分)
ABCDEFGHIJ 和 BCDAFEHJIG ,
1、已知一棵二叉树的前序扫描序列和中序扫描序列分别为 试给出该二叉树的后序序列并绘出该二叉树对应的森林。
解:
后序序列为:DCBFJIHGEA
、、
2、若对序列(7, 3, 1, 8, 6, 2, 4, 5)按从小到大排序,请写出起泡排序的第一趟结果 和堆排序的初始堆。
解:
冒泡:3 1 7 6 2 4 5 8
堆:8 7 4 5 6 2 1 3
3、某通讯系统只可能有 A、B、C、D、E、F 6种字符,其出现的概率分别是 、、、 ,试画出相应的哈夫曼树,并设计哈夫曼编码。
F:100
4、在二叉平衡检索树(AVL树)的调整中,将最靠近新插入点的不平衡结点调整平衡后, 树中是否还会有不平衡结点?为什么?
解: 不会再有不平衡点。因为插入结点发生不平衡现象后,会改变
以靠近新插入点的不平衡结点 ”为根的子树(即最小不平横树)的高度加 1,
经过调整后使最小不平衡树的整体高度又恢复到原来的值,所以不会对原平衡树 的其他部分造成危害,因此不会再有不平衡点。
5、指定Hash函数H(k)=3*k mod 11及线性探测开地址法处理冲突,试在 0~10的散列空间中
对关键字序列(22, 41, 53, 46, 30, 13, 01, 67)构造Hash表,并求在等查找概率下 查找成功的平均查找长度。
解:
插入元素后的分布情况:
0
1
2
3
4
5
6
7
8
9
10
22
41
30
01
53
46
13
67
ASL = (1+1 + 1 + 1+2+2+2+6)/8=
四、(10分)下图是带权的有向图 G的邻接矩阵表示,请给出:
1、其邻接表存储结构
2、按Floyd算法求所有顶点对之间最短距离的矩阵变化过程。
V1
V2
V3
V4
V1|
0
1
oo
4
V2|
oo
0
9
2
V3|
3
5
0
8
V4|
oo
oo
6
0
解:Floyd算法执行过程中矩阵的变化情况为(从左到右)
0
1
oo
4
0
1
10
3
0
1
10
3
0
1
9
3
oo
0
9
2
oo
0
9
2
12
0
9
2
11
0
8
2
3
4
0
7
3
4
0
6
3
4
0
6
3
4
0
6
oo
oo
6
0
oo
oo
6
0

《数据结构(C语言描述)》期末试卷 来自淘豆网www.taodocs.com转载请标明出处.

非法内容举报中心
文档信息
  • 页数14
  • 收藏数0 收藏
  • 顶次数0
  • 上传人cjc201601
  • 文件大小92 KB
  • 时间2021-07-25