扫码获取更多资源

●查找习题

填空题

1.对于长度为n的线性表，如果进行顺序查找，则时间复杂度为（ ）；如果进行折 半查找，则时间复杂度为（ ）;如果进行分块查找（假定总块数和每块长度均接近而的 值），则时间复杂度为（ ）0

2.在哈希表中，装填因子a值越大，存取元素发生冲突的可能性就（ ），当装填因子 a值越小，存取元素发生冲突的可能性就（ ）。

3.已知一组记录的关键字序列为｛18, 34, 58, 26, 75, 67, 48, 93, 81 ）,哈希函数为 H（k） = k MOD 110如果采用线性探测再散列法解决冲突，则平均查找长度为（ ）；如 果采用链地址法解决冲突，则平均查找长度为（ ）。

4.已知一组记录的关键字序列为｛35, 75, 40, 15, 20, 55, 95, 65｝,按依次插入结点 的方法生成一棵二叉排序树，最后两层上的结点总数为（ ）0

5.在一棵10阶B_树上，每个树根结点中所含关键字最多允许为（ ）个，最少允许 为（ ）o

问答题

将一组记录关键字序列｛for, case, while, class, protected, virtual, public, private, do, template, const, if, int｝依次插入到初态为空的二叉排序树中：

（1）试画出所得到的二叉排序树T；

(2)试画出删除关键字“for”之后的二叉排序树T'；

(3)试回答将关键字“for”插入T'中得到的二叉排序树T〃是否与T相同？

(4)试给出T”的先序、中序和后序序列。

(2. 已知一组记录的关键字序列为{50, 20, 10, 100, 120, 30, 110, 60, 70, 90, 80, 40},依次把记录插入到初始状态为空的平衡二叉排序树中，使得在每次插入后保持该树仍 然是平衡二叉树。试画出每次插入后所形成的平衡二叉排序树。

(3. 从空树开始，依次输入数据20、30、50、52、60、68、70,试画出建立3阶B_树(即2-3 树)的过程。并画出删除50和68后的B_树状态。

(4. 设哈希函数为H(k) = k MOD 101,解决冲 0 12 3 wo

(突的方法采用线性探测再散列法，表中用“一1”表示 丁恆帀帀帀研 - 一

(空单元，哈希表T如图8-42所示。 图"a哈希表T

((1) 如果删除T中的304(即令T[l] = — 1)之 后，在T中查找707将会发生什么？

((2) 如果将删除的表项标记为“一2”,查找时探测到一2继续向前搜索，探测到一1时终 止搜索，则用这种方法删除304后能否正确地查找到707?

(5. 对于一组给定且固定不变的关键字序列，有可能设计出无冲突的哈希函数H,此时 称H为完备哈希函数(Perfect Hashing Function) 0如果H能无冲突地将关键字完全填满 哈希表，则称H是最小完备(Minimal Perfect)哈希函数。通常，寻找完备的哈希函数非常 困难，寻找最小完备的哈希函数就更困难。

((1) 如果H是已知关键字集合K的完备哈希函数，则要增加一个新的记录关键字到集 合K,一般情况下H还是完备的吗？

((2) 已知一组记录关键字序列为{81, 129, 301, 38, 434, 216, 412, 487, 234},哈希函 数为H(k) = (k+18)/63,请问H是完备的吗？它是最小完备的吗？

((3) 考虑由字符串构成的关键字序列{Bret, Jane? Shirley, Bryce» Michelle, Heather},试 为哈希表[0..6]设计一个完备哈希函数。(提示：考虑每个字符串的第3个字符，即s[2]。)

算法设计题

1. 试设计一个算法：递归折半查找给定关键字。

2. 试设计一个算法：求给定结点在二叉排序树中所在的层数。

3. 试设计一个算法：判别给定的二叉树是否为二叉排序树。设此二叉树以二叉链表 为存储结构，且树中记录结点的关键字均不相同。

4. 试设计一个算法：在二叉排序树上找出任意两个不同结点的最近公共祖先。

联系我们：