内容发布更新时间 : 2024/12/23 7:30:16星期一 下面是文章的全部内容请认真阅读。

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和链地址法处理冲突来构造哈希表。