数据结构查找和内排序习题

09信管《数据结构》单元测验四

一、填空题

1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。

2. 线性有序表（a1，a2，a3，…，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索 8 次。设有100个结点，用二分法查找时，最大比较次数是 7 。

3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。

4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中

元素 28，6，12，20 比较大小。

5. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 散列查找 。 6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。

7. 有一个表长为m的散列表，初始状态为空，现将n（n

入到有序表时，为寻找插入位置至少需比较 6 次。 10. 在插入和选择排序中，若初始数据基本正序，则选用 插入 ；若初始数据基本反序，则选用

选择 。 11. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用 堆排序 ；若初始记录基本无序，则最好选用 快速排序 。

12. 对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是 O(n2) 。若对其进行快速

排序，在最坏的情况下所需要的时间是 O(n2) 。

13. 对于n个记录的集合进行归并排序，所需要的平均时间是 O(nlog2n) ，所需要的附加空间

是 O(n) 。

14． 对于n个记录的表进行2路归并排序，整个归并排序需进行 ┌log2n┐ 趟（遍）。15. 设要将序

列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则： 冒泡排序一趟扫描的结果是 H C Q P A M S R D F X Y ；

初始步长为4的希尔（shell）排序一趟的结果是 P A C S Q D F X R H M Y ； 二路归并排序一趟扫描的结果是 H Q C Y A P M S D R F X； 快速排序一趟扫描的结果是 F H C D P A M Q R S Y X ；（ 以Q为基准） 堆排序初始建堆的结果是 A D C R F Q M S Y P H X 。（小根堆）

16. 在堆排序、快速排序和归并排序中，

若只从存储空间考虑，则应首先选取堆 方法，其次选取 快速排序方法，最后选取归并排序方法； 若只从排序结果的稳定性考虑，则应 选取 归并排序 方法； 若只从平均情况下最快考虑，则应选取 快速排序方法；

若只从最坏情况下最快并且要节省内存考虑，则应选取 堆排序 方法。

1

二、单项选择题

（ B ）1．在表长为ｎ的链表中进行线性查找，它的平均查找长度为

Ａ. ＡＳＬ＝ｎ; Ｂ. ＡＳＬ＝（ｎ＋１）／２; Ｃ. ＡＳＬ＝n＋１; Ｄ. ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１

（ A ）2．折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它

将依次与表中 比较大小，查找结果是失败。

A．20，70，30，50 B．30，88，70，50 C．20，50 D．30，88，50

（ C ）3．对22个记录的有序表作折半查找，当查找失败时，至少需要比较 次关键字。

A．3 B．4 C．5 D． 6

（ A ）4. 链表适用于 查找

A．顺序 B．二分法 C．顺序，也能二分法 D．随机

（ C ）5. 折半搜索与二叉搜索树的时间性能

A. 相同 B. 完全不同 C. 有时不相同 D. 数量级都是O（log2n）

6．从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。

要进行线性查找，则线性表 A ；要进行二分查找，则线性表 B ；要进行散列查找，则线性表 C 。 某顺序存储的表格，其中有90000个元素，已按关键项的值的上升顺序排列。现假定对各个元素进行查找的概率是相同的，并且各个元素的关键项的值皆不相同。当用顺序查找法查找时，平均比较次数约为 D ，最大比较次数为 E 。 供选择的答案：

A~C：① 必须以顺序方式存储 ② 必须以链表方式存储 ③ 必须以散列方式存储 ④ 既可以以顺序方式，也可以以链表方式存储

⑤ 必须以顺序方式存储且数据元素已按值递增或递减的次序排好 ⑥ 必须以链表方式存储且数据元素已按值递增或递减的次序排好

D，E： ① 25000 ② 30000 ③ 45000 ④ 90000

答案： A= ④ B= ⑤ C= ③ D＝ ③ E＝ ④

7.从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。

数据结构反映了数据元素之间的结构关系。链表是一种 A ，它对于数据元素的插入和删除 B 。通常查找线性表数据元素的方法有 C 和 D 两种方法，其中 C 是一种只适合于顺序存储结构但 E 的方法；而 D 是一种对顺序和链式存储结构均适用的方法。 供选择的答案：

A：①顺序存储线性表 ②非顺序存储非线性表

③顺序存储非线性表 ④非顺序存储线性表

B： ① 不需要移动结点，不需改变结点指针 ②不需要移动结点，只需改变结点指针

③只需移动结点，不需改变结点指针 ④既需移动结点，又需改变结点指针 C：① 顺序查找 ②循环查找 D：① 顺序查找 ②随机查找 E：① 效率较低的线性查找

③ 效率较高的非线性查找

③条件查找 ④二分法查找 ③二分法查找 ④分块查找 ②效率较低的非线性查找 ④效率较高的线性查找

2

答案：A＝ ④ B＝ ② C＝ ④ D＝ ① E＝ ③

8. 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。 在二叉排序树中，每个结点的关键码值 A ， B 一棵二叉排序，即可得到排序序列。同一个结点集合，可用不同的二叉排序树表示。 供选择的答案

A： ①比左子树所有结点的关键码值大，比右子树所有结点的关键码值小

②比左子树所有结点的关键码值小，比右子树所有结点的关键码值大

③比左右子树的所有结点的关键码值都大

④与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的大小关系 B: ①前序遍历 ② 中序（对称）遍历 ③ 后序遍历 ④ 层次遍历 答案：A＝ ① B＝ ②

9. 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。

散列法存储的基本思想是根据 A 来决定 B ，碰撞（冲突）指的是 C ，处理碰撞的两类主要方法是 D 。 供选择的答案

A，B： ①存储地址 ② 元素的符号 ③ 元素个数 ④ 关键码值

⑤ 非码属性 ⑥ 平均检索长度 ⑦ 负载因子 ⑧ 散列表空间 C: ①两个元素具有相同序号 ② 两个元素的关键码值不同，而非码属性相同

③ 不同关键码值对应到相同的存储地址 ④ 负载因子过大 ⑤ 数据元素过多 D： ① 线性探查法和双散列函数法 ② 建溢出区法和不建溢出区法 ③ 除余法和折叠法 ④ 拉链法和开地址法

答案：A＝ ④ B＝ ① C＝ ③ D＝ ④

10.考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值。并小于等于其右子树上的一切结点的值。

现把9个数1，2，3，…，8，9填入右图所示的二叉树的9个结点中，并使之具有上述性质。此时，n1的值是 A ，n2的值是 B ，n9的值是 C 。现欲把10放入此树并使该树保持前述性质，增加的一个结点可以放在 D 或 E 。 供选择的答案

A～C： ①1 ② 2 ③ 3 ④ 4 ⑤ 5 ⑥ 6 ⑦ 7 ⑧ 8 ⑨ 9

D～E： ① n7下面 ② n8下面 ③ n9下面 ④ n6下面 ⑤ n1与n2之间 ⑥ n2与n4之间 ⑦ n6与n9之间 ⑧ n3与n6之间 答案：A＝ ⑦ B＝ ④ C＝ ⑥ D＝ ② E＝ ⑥

3

（ C ）11．将5个不同的数据进行排序，至多需要比较 次。

Ａ. 8 Ｂ. 9 Ｃ. 10 Ｄ. 25

（ C ）12． 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比

较，将其放入已排序序列的正确位置上的方法，称为 Ａ. 希尔排序 Ｂ. 冒泡排序 Ｃ. 插入排序 Ｄ. 选择排序

（ D ）13．从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称

为

Ａ. 希尔排序 Ｂ. 归并排序 Ｃ. 插入排序 Ｄ. 选择排序

（ B ）14．对ｎ个不同的排序码进行冒泡排序（递增），在下列哪种情况下比较的次数最多。

Ａ. 从小到大排列好的 Ｂ. 从大到小排列好的 Ｃ. 元素无序 Ｄ. 元素基本有序

（ D ）15．对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为

Ａ. n+1 Ｂ. n Ｃ. n-1 Ｄ. n(n-1)/2

（ C ）16．快速排序在下列哪种情况下最易发挥其长处。

Ａ. 被排序的数据中含有多个相同排序码 Ｂ. 被排序的数据已基本有序

Ｃ. 被排序的数据完全无序 Ｄ. 被排序的数据中的最大值和最小值相差悬殊 （ B ）17． 对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是

A．O(n) B．O(n2) C．O(nlog2n) D．O(n3)

（ C ）18．若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用快速排序的方法，以第一个记录为

基准得到的一次划分结果为

Ａ. 38, 40, 46, 56, 79, 84 Ｂ. 40, 38, 46 , 79, 56, 84 Ｃ. 40, 38，46, 56, 79, 84 Ｄ. 40, 38, 46, 84, 56, 79

（ D ）19．下列关键字序列中， 是堆。

Ａ. 16, 72, 31, 23, 94, 53 Ｂ. 94, 23, 31, 72, 16, 53

Ｃ. 16, 53, 23, 94，31, 72 Ｄ. 16, 23, 53, 31, 94, 72

（ B ）20．堆是一种 排序。

Ａ. 插入 Ｂ.选择 Ｃ. 交换 Ｄ. 归并

（ C ）21．堆的形状是一棵

Ａ. 二叉排序树 Ｂ.满二叉树 Ｃ. 完全二叉树 Ｄ. 平衡二叉树

（ B ）22．若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始（大根）堆为

Ａ. 79, 46, 56, 38, 40, 84 Ｂ. 84, 79, 56, 38, 40, 46

4

Ｃ. 84, 79, 56, 46, 40, 38 Ｄ. 84, 56, 79, 40, 46, 38

（ C ）23． 下述几种排序方法中，要求内存最大的是

Ａ. 插入排序 Ｂ.快速排序 Ｃ. 归并排序 Ｄ. 选择排序

三、简答题

1.假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：

（1） 画出描述折半查找过程的判定树；

（2） 若查找元素54，需依次与哪些元素比较？

（3） 若查找元素90，需依次与哪些元素比较？

（4） 假定每个元素的查找概率相等，求查找成功时的平均查找长度。

解：

（1） 先画出判定树如下（注：mid=?(1+12)/2?=6）：

30 5 63 3 7 42 87 4 24 54 72 95 (2) 查找元素54，需依次与30, 63, 42, 54比较； (3) 查找元素90，需依次与30, 63,87, 95比较；

（4） 求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17次；

但最后一层未满，不能用8×4，只能用5×4=20次， 所以ASL＝1/12（17＋20）＝37/12≈3.08

2.设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝K MOD 16。

K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：

（10，24，32，17，31，30，46，47，40，63，49） 造出Hash表，试回答下列问题： （1） 画出哈希表的示意图；

（2） 若查找关键字63，需要依次与哪些关键字进行比较？

（3） 若查找关键字60，需要依次与哪些关键字比较？

（4） 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

解： （1）画表如下： 0 1 2 3 4 5 32 17 63 49 6 7 8 24 9 40 10 10 11 12 13 14 30 15 31 16 46 17 47 （2） 查找63,首先要与H(63)=63=15号单元内容比较，即63 vs 31 ,no; 然后顺移，与46,47,32,17,63相比，一共比较了6次！

（3）查找60,首先要与H(60)=60=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。

（4）ASL=1/11（6+6＋2＋3×3）＝23/11

5

本文来源：https://www.bwwdw.com/article/seod.html