内容发布更新时间 : 2024/12/23 12:20:03星期一 下面是文章的全部内容请认真阅读。
2 1 4 6 3 5 图2
7 8
序列为：1、3、2、4、5、6、7、8
6. 已知某图采取如图2所示的邻接矩阵表示法，请回答下列问题。（共12分）
0
1 1 0 2 1 3 1 4 0 5 0 6 0 2 1 0 0 1 1 0 图2
(1) 请画出该图。（6分）
（2）对其从顶点A开始进行深度优先遍历，写出遍历序列。（6分） （1） 请画出该图。（6分）错一个结点扣1分。
3 1 0 0 0 1 1 4 0 1 0 0 0 0 5 0 1 1 0 0 0 6 0 0 1 0 0 0 1 A 2 B 3 C 4 D 5 E 6 F
A
D E F B C
（2）对其从顶点A开始进行深度优先遍历，写出遍历序列。（6分, 错一个字符扣1分）
序列为：ABDECF
7、（本题总计 7 分） 构造该图的最小生成树。
2 b e g 2 2 2
2 1 1 a d
3 1 4
c f h 1
图的最小生成树如下 ——每条边1分，共7分
b 2 2 a d 1 c 2 e 1 g 1
f 1 h
5、程序设计题
第8章 动态存储管理
1、填空题 2、选择题 3、判断题 4、应用题 5、程序设计题
第9章 查找
1、选择题
1.若在线性表中采用二分查找法查找元素，该线性表应该( )。 A．元素按值有序 B．采用顺序存储结构 C．元素按值有序，且采用顺序存储结构 D．元素按值有序，且采用链式存储结构
2.对二叉排序树进行_________遍历，可以得到该二叉树所有结点构成的有序序列。
(A) 前序 (B)中序 (C)后序 (D)按层次
3.利用逐点插入法建立序列(51，71，43，81，74，20，34，45，64，30)对应的二叉排序树以后，查找元素34要进行( )元素间的比较。
A．4次 B．5次 C. 7次 D．10
4.对二叉排序树进行____________遍历，可以得到该二叉树所有结点构成的有序序列。
(A) 前序 (B)中序 (C)后序 (D)按层次
5.散列函数有一个共同性质，即函数值应按( )取其值域的每一个值。 A.最大概率 B.最小概率 C.同等概率 D.平均概率 6.一个哈希函数被认为是“好的”，如果它满足条件_________。 (A)哈希地址分布均匀 (B)保证不产生冲突
(C)所有哈希地址在表长范围内 (D)满足(B)和(C)
7.哈希表的平均查找长度是__________的函数。 （A）哈希表的长度 （B）表中元素的多少 （C）哈希函数 （D）哈希表的装满程度 8.平均查找长度最短的查找方法是____________。
（A）折半查找 （B）顺序查找 （C）哈希查找 （4）其他
2、判断题
1.在有序表的查询过程中，设立“哨兵”的作用是为了提高效率。（ ） 2.对于折半查找，其前提条件是待查找序列只要是有序的即可。 （ ）
3、应用题
1.
输入一个正整数序列（53,17,12,66,58,70,87,25,56,60），试完成下列各题。 (1)按输入次序构造一棵二叉排序树（只要求画出最终二叉排序树）。 (2)依此二叉排序树，如何得到一个从小到大的有序序列？
2、若一棵排序二叉树的关键字输入序列为{80，6，10，7，8，25，100，90}，请画出该二叉树。
解：二叉排序树为： （16分，每个结点2分）
80 6 100 10 90 7 25 8
3.
已知一组关键字为{1,14,27,29,55,68,10,11,23}，则按哈希函数H(key)=key MOD 13和链地址法处理冲突来构造哈希表。