数据结构考研试题及第9章查找.pdfVIP

9

志不强者智不达，言不信者行不果。——墨翟

第9章会合

一．选择题

二．判断题

1.√2.√3.×4.×5.×6.√7.√8.×9.×10.11.12.

××√

13.14.15.16.17.18.19.20.21.22.23.24.

√×××√×√×××××

25.26.27.28.29.30.31.32.33.34.35.36.

√××√√××√√×√√

部分答案解说以下。

4．不可以说哪一种哈希函数的选用方法最好，各样选用方法有自己的合用范围。

8．哈希表的结点中能够包含指针，指向其元素。

11．单链表不可以使用折半查找方法。

20．按插入后中序遍历是递加序列的原则，若某结点只有右子树，而插入元素的重点字小于该结

点的重点字，则会插入到该结点的左边，成为其左孩子。这类插入就不是插入到叶子下边。

21．从均衡因子定义看，完整二叉树任一结点的均衡因子的绝对值的确是小于等于1。可是，均衡二

叉树实质上是二叉排序树，完整二叉树不必定是排序树。故不可以说完整二叉树是均衡

二叉树。

23．某结点的左子树根结点不必定是它的中序前驱，其右子树根结点也不必定是它的中序后

继。

24．在等概率下，查找成功时的均匀查找长度同样，查找失败时的均匀查找长度不同样。

26．只有被删除结点是叶子结点时命题才正确。

三．填空题

1．nn+12．43．6,9,11,124．5

5．26（第4层是叶子结点，每个结点两个重点字）6．1,3,6,8,11,13,16,19

7．5,968．m-1,「m/2-19．2,4,3

10．(1)哈希函数(2)解决矛盾的方法(3)选择好的哈希函数(4)办理矛盾的方法(5)均匀(6)

简单

11．AVL树（高度均衡树，高度均衡的二叉排序树），或为空二叉树，或二叉树中随意结点

左子树高度与右子树高度差的绝对值小于等于1。

12．小于等于表长的最大素数或不包含小于20的质因子的合数13．1614．㏒

n」+1

2

15．(1)45(2)45(3)46（块内次序查找）16．k(k+1)/217．30，31.5（块内次序查

找）

18．(1)次序储存或链式储存