数据结构题库(4)

8、假定对有序表：(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找，试回答下列问题：

(1).画出描述折半查找过程的判定树；

(2).若查找元素54，需依次与那些元素比较? (3).若查找元素90，需依次与那些元素比较?

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

第7章 排序

一、选择题

1. 某内排序方法的稳定性是指( )。

A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录

C．平均时间为0（n log n）的排序方法 D．以上都不对

2. 下面给出的四种排序法中( )排序法是不稳定性排序法。

A. 插入 B. 冒泡 C. 二路归并 D. 堆排序

3. 若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序

方法是（ ）。

A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序 4. 在希尔排序中，最后一趟排序的增量必须为（ ）。

A．1 B.3 C. 5 D. 7

5. 排序趟数与序列的原始状态有关的排序方法是( )排序法。

A．插入 B. 选择 C. 冒泡 D. 快速

6. 对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是( )。

A．直接插入 B. 二分法插入 C. 快速排序 D. 归并排序

7. 数据序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的( )的两趟排序后

的结果。

A. 快速排序 B. 冒泡排序 C. 选择排序 D. 插入排序 8. 对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1）

84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84 ，则采用的排序是 ( )。

A. 选择 B. 冒泡 C. 快速 D. 插入

9. 对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，

20，7，15}；则采用的是（ ）排序。

A. 选择 B. 快速 C. 希尔 D. 冒泡

10. 对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{9，15，7，8，

20，-1，4}，则采用的是（ ）排序。

A．选择 B. 堆 C. 直接插入 D. 冒泡

11. 下列排序算法中( )不能保证每趟排序至少能将一个元素放到其最终的位置上。

A.快速排序 B. shell排序 C. 堆排序 D.冒泡排序

12. 下列序列中，（ ）是执行第一趟快速排序后所得的序列。 A. [68，11，18，69] [23，93，73]

B. [68，11，69，23] [18，93，73]

C. [93，73] [68，11，69，23，18]

D. [68，11，69，23，18] [93，73]

13. 有一组数据（15，9，7，8，20，-1，7，4） 用快速排序的划分方法进行一趟划分后数

据的排序为 ( )（按递增序）。

A．下面的B，C，D都不对。 B．9，7，8，4，-1，7，15，20 C．20，15，8，9，7，-1，4，7 D. 9，4，7，8，7，-1，15，20

14. 在下面的排序方法中，辅助空间为O（n）的是( ) 。

A．希尔排序 B. 堆排序 C. 选择排序 D. 归并排序 15. 下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序。 A． 冒泡 B. 希尔 C. 快速 D. 堆

16. 对初始状态为递增序列的表按递增顺序排序，最省时间的是（ ）算法，最费时间的

是（ ）算法。

A. 堆排序 B. 快速排序 C. 插入排序 D. 归并排序 17. 就平均性能而言，目前最好的内排序方法是( )排序法。

A. 冒泡 B. 希尔插入 C. 交换 D. 快速

18. 如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用

（ ）方法最快。

A．起泡排序 B．快速排列 C．Shell排序 D．堆排序 E．简单选择排序 19. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在

已排序序列的合适位置，该排序方法称为( )排序法。

A. 插入 B. 选择 C. 希尔 D. 二路归并 20. 在排序算法中，每次从未排序的记录中挑出最大关键码字的记录，加入到已排序记录的

末尾，该排序方法是（ ）。

A. 选择 B. 冒泡 C. 插入 D. 堆

21. 用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是

（ ）。

A． 94,32,40,90,80,46,21,69 B． 32,40,21,46,69,94,90,80 C． 21,32,46,40,80,69,90,94 D． 90,69,80,46,21,32,94,40 22. 直接插入排序在最好情况下的时间复杂度为（ ）

2

A． O(logn) B． O(n) C． O(n*logn) D． O(n)

23. 对序列{15，9，7，8，20，-1，4，} 用希尔排序方法排序，经一趟后序列变为{15，-l，

4，8，20，9，7}则该次采用的增量是 ( )

A. l B. 4 C. 3 D. 2 24. 对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）。

A. (2,5,12,16)26(60,32,72) B. (5,16,2,12)28(60,32,72) C. (2,16,12,5)28(60,32,72) D. (5,16,2,12)28(32,60,72)

25. 在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是（ ）。 A. O(log2n) B. O(1) C. O(n) D. O(nlog2n)

二、综合应用题

1、判断下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，请将它们调整为堆）。 （1）100，85，98，77，80，60，82，40，20，10，66 （2）100，98，85，82，80，77，66，60，40，20，10 （3）100，85，40，77，80，60，66，98，82，10，20

（4）10，20，40，60，66，77，80， 82，85，98，100

2、给出一组关键字：29，18，25，47，58，22，51，10，分别写出按下列各种排序方法进行排序时的变化过程：

(1) 归并排序 每归并一次书写一个次序。 (2) 快速排序 每划分一次书写一个次序。

(3) 堆排序 先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。

第1章 绪论

一、选择题

1.B 2.C 3.1C 3.2B 4.B 5.D 6.B 7.C 8.D 9..A 10.C

第2章 线性表

一、选择题

1.A 2.B 3.C 4.A 5.D 6.D 7.D 8.B

9.B,C 10.C

11.C 12.C 13.A 14.B 15.B

第3章 栈和队列

一、选择题

1.B 2.B 3.D

4.B 5.B 6.C 7.D 8.B 9.D 10.C 11.A 12.C 13.B

14.1B 14.2A 14.3C 14.4C 14.5F 15.C

16.C

17.A

第4章 树和二叉树

一、选择题

1.D 2.D 3.A 4.B 5.D 6.B 7.C 8.D 9.C 10.B

11.C 12.C 13.B 14.D 15.A 16.C 17.C 18.D 19.C 20.B 21.D 22.B 23.A 24.B 25.C 26.B 27.D 28.A 29.D

30.C

31.D 32.B 33.C 34.A 35.C 36.C 37.B 38.B

39.D 40.1C

40.2D

40.3F

40.4H

40.5I

第5章 图

一、选择题

1.A 2.B 3.A 4.D 5.1B 5.2D 6.1B 6.2C 7.A 8.B 11.D 12.A,B 13.B 14.A

15.A

16.A

17.B

18.D

19.A

20.C

21.B

第6章 查找

一、选择题

1.C 2.D 3.C 4.D 5.B 6.1C 6.2C 7.1B 7.2A 8.C 9.D 10.1A 10.2C 11.B 12.D 13.D 14.D 15.C

二、综合应用题

1. 评价哈希函数优劣的因素有：能否将关键字均匀影射到哈希空间上，有无好的解决

9.B

10.C

冲突的方法，计算哈希函数是否简单高效。由于哈希函数是压缩映像，冲突难以避免。解决冲突的方法：

① 开放定址法 形成地址序列的公式是：Hi=（H（key）+di）% m，其中m是表长，di是增量。根据di取法不同，又分为三种：

a．di =1，2，?，m-1 称为线性探测再散列，其特点是逐个探测表空间，只要散列表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一散列地址。

b．d222，-22，? ，?k2

i =1，-1，2（k≤m/2） 称为二次探测再散列，它减少了聚集，但不容易探测到全部表空间，只有当表长为形如4j+3（j为整数）的素数时才有可能。

c．di =伪随机数序列，称为随机探测再散列。

② 再散列法 Hi=RHi（key） i=1，2，?，k，是不同的散列函数，即在同义词产生碰撞时，用另一散列函数计算散列地址，直到解决碰撞。该方法不易产生“聚集”，但增加了计算时间。

③ 链地址法 将关键字为同义词的记录存储在同一链表中，散列表地址区间用H[0..m-1]表示，分量初始值为空指针。凡散列地址为i（0≤i≤m-1）的记录均插在以H[i]为头指针的链表中。这种解决方法中数据元素个数不受表长限制，插入和删除操作方便，但增加了指针的空间开销。这种散列表常称为开散列表，而①中的散列表称闭散列表，含义是元素个数受表长限制。

2. 不一定相邻。哈希地址为i（0≤i≤m-1）的关键字，和为解决冲突形成的探测序列

i的同义词，都争夺哈希地址i。 3. 哈希表如下： 散列地址 0 1 2 3 4 5 6 7 8 9 关键字 14 01 9 23 84 27 55 20 比较次数 1 1 1 2 3 4 1 2 平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8

以关键字27为例：H（27）=27%7=6（冲突） H1=（6+1）=7（冲突）

H（6+22）=0（冲突） H3

2=3=（6+3）=5 所以比较了4次。 4. 按中序遍历序列将值1~9依次标上

6. 序列（2）不可能是二叉排序树中查到363的序列。查到501后，因363<501，后面

应出现小于501的数，但序列中出现了623，故不可能 7. 37/12

第7章 排序

一、选择题

1.D 2.D 3.C 4.A 5.C,D 6.B,D 7.A 8.A 9.C 10.C 11.B 12.C 13.A 14.D 15.C 16.1C 16.2B 17.D 18.D 19.A 21.C 22.B 23.B 24.B 25.B

二、综合应用题

1. (1)是大堆； (2)是大堆；（4）是小堆；

(3)不是堆，调成大堆 100，98，66，85，80，60，40，77，82，10，20

20.A

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构题库(4)在线全文阅读。