数据结构查找与排序练习题答案——查找排序练习题答案

1、数据结构查找与排序练习题答案一、选择题1. 对 N 个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（ ）A（ N+1） /2 B. N/2 C. N D. （1+N）*N /22. 适用于折半查找的表的存储方式及元素排列要求为 （ ） A链接方式存储，元素无序 B 链接方式存储，元素有序 C顺序方式存储，元素无序D顺序方式存储，元素有序3. 当在一个有序的顺序存储表上查找一个数据时， 即可用折半查找， 也可用顺序查找， 但前 者比后者的查找速度 （ ）A必定快 B. 不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减 4有一个长度为 12 的有序表， 按二分查找法

2、对该表进行查找， 在表内各元素等概率情况下 查找成功所需的平均比较次数为（ ）。A 35/12B.37/12 C.39/12 D.43/125. 折半查找的时间复杂性为（ ）2A. O（n2） B. O （n） C. O （nlogn ）D. O （ logn ）6. 对有 18个元素的有序表作折半查找，则查找A3 的比较序列的下标为（ ）A.1，2，3 B.9 ， 5，2，3 7. 设有序表的关键字序列为 当用二分查找法查找健值为A.2 B. 3 C. 4C.9 ， 5，3 D.9 ，4， 2，31 ，4，6，10，18， 84 的结点时，经（ D.128.用 n 个键值构造一棵二叉排序树，

3、最低高度为（35，42，53，67， 71，78，）次比较后查找成功。84，92，99 ，D.logn+1A. n/2 B. 、 n C.logn 9分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是 A（ 100， 80， 90， 60， 120，110，130）B. （100，120，110，130，80， 60， 90）C. （ 100， 60， 80， 90， 120，110，130）79 ，用链地 ）个记录。D. （100 ，80， 60， 90， 120，130，110）10. 设有一组记录的关键字为 19 ，14，23，1，68，20，84，27，55，11，10

4、， 址法构造散列表，散列函数为 H（ key ） =key% 13, 散列地址为 1 的链中有（ A1 B. 2 C. 3 D. 411. 已知一采用开放地址法解决 Hash 表冲突，要从此 Hash 表中删除出一个记录，正确的做 法是（）A.将该元素所在的存储单元清空。B. 将该元素用一个特殊的元素代替C. 将与该元素有相同 Hash 地址的后继元素顺次前移一个位置。D. 用与该元素有相同 Hash 地址的最后插入表中的元素替代。12. 假定有 k 个关键字互为同义词，若用线性探测法把这k 个关键字存入散列表中，至少要进行多少次探测？ （ ）Ak-1 次 B. k 次 C. k+1 次 D.

5、 k （k+1）/2 次13. 散列表的地址区间为 0-17, 散列函数为 H（K）=K mod 17。采用线性探测法处理冲突，并将 关键字序列 26，25，72，38，8，18，59 依次存储到散列表中。（1）元素 59 存放在散列表中的地址是（）。A 8 B. 9 C. 10 D. 11（2）存放元素 59 需要搜索的次数是（）。A 2 B. 3 C. 4 D. 514. 将 10个元素散列到 100000个单元的哈希表中，则（ ）产生冲突。A. 一定会 B. 一定不会 C. 仍可能会15.对于线性表（ 7，34，77，25，64，49，20，14）进行散列存储时，若选用 H（K）=K %

6、7 作为散列函数，则散列地址为 0 的元素有（ ）个。A.1B.2 C.3D.416.下列排序方法中，哪一个是稳定的排序方法？（）A直接选择排序B 直接插入排序C希尔排序D 快速排序17.在下列排序算法中, 哪一个算法的时间复杂度与初始排序无关（）。A. 直接插入排序B. 气泡排序 C. 快速排序D. 直接选择排序18. 比较次数与排序的初始状态无关的排序方法是（ ） 。A. 直接插入排序B. 起泡排序 C. 快速排序 D. 简单选择排序19. 对序列 15，9，7，8，20，-1，4进行排序，进行一趟后数据的排列变为4 ， 9，-1 ， 8，20，7，15 ；则采用的是（）排序。A. 选择B

7、. 快速 C. 希尔 D. 冒泡20. 一组记录的关键码为（ 46，79，56，38，40，84），则利用快速排序的方法，以第一个记 录为基准得到的一次划分结果为（ ）。A.（38,40,46,56,79,84） B.（40,38,46,79,56,84） C.（40,38,46,56,79,84） D.（40,38,46,84,56,79）二、判断题1. 查找相同结点的效率折半查找总比顺序查找高。 2. 对无序表用二分法查找比顺序查找快。 3. 对大小均为 n 的有序表和无序表分别进行顺序查找， 在等概率查找的情况下， 对于查找成 功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查

8、找长度是不同的。 4. 二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：（ 1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值； （ 2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值。 5. 在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面。 6. 对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。 7. 二叉树中除叶结点外 , 任一结点 X，其左子树根结点的值小于该结点（ X）的值；其右子 树根结点的值该结点（ X）的值 , 则此二叉树一定是二叉排序树。 8. 在任意一棵非空二叉排序树中， 删除某结点后又将其插入， 则所得二排序叉树与原二排序 叉树相同。 9. 采用线性探测法处理散列时的冲突， 当从哈希表删除一个记录时， 不应将这个记录的所在 位置置空，因为这会影响以后的查找。 10. 在散列检索中， “比较”操作一般也是不可避免的。 11. 散列