数据结构复习题及答案(4)

A. 35/12 B. 37/12 C. 39/12 D. 43/12

9．对于静态表的顺序查找法，若在表头设置岗哨，则正确的查找方式为。

A.从第0个元素往后查找该数据元素 B.从第1个元素往后查找该数据元素 C.从第n个元素往开始前查找该数据元素 D.与查找顺序无关

10．解决散列法中出现的冲突问题常采用的方法是。

A.数字分析法、除余法、平方取中法 B.数字分析法、除余法、线性探测法 C.数字分析法、线性探测法、多重散列法 D.线性探测法、多重散列法、链地址法

11．采用线性探测法解决冲突问题，所产生的一系列后继散列地址。

A.必须大于等于原散列地址

数据结构复习题及答案

B.必须小于等于原散列地址

C.可以大于或小于但不能等于原散列地址 D.地址大小没有具体限制

12．对于查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于 。

A.静态查找表 B.动态查找表 C.静态查找表与动态查找表 D两种表都不适合 13.散列表的平均查找长度。

A.与处理冲突方法有关而与表的长度无关 B.与处理冲突方法无关而与表的长度有关 C.与处理冲突方法有关而与表的长度有关 D.与处理冲突方法无关而与表的长度无关 8.2 填空题（将正确的答案填在相应的空中）

1.顺序查找法的平均查找长度为____；折半查找法的平均查找长度为____；哈希表查找法采用链接法处理冲突时的平均查找长度为____。

2.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是____。 3.折半查找的存储结构仅限于____，且是____。

4. 假设在有序线性表A[1..20]上进行折半查找，则比较一次查找成功的结点数为____，则比较二次查找成功的结点数为____，则比较三次查找成功的结点数为____，则比较四次查找成功的结点数为____，则比较五次查找成功的结点数为____，平均查找长度为____。

5. 对于长度为n的线性表，若进行顺序查找，则时间复杂度为____；若采用折半法查找，则时间复杂度为____；

6．已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用折半查找90时，需进行47时，需进行100时，需进行 次查找才能确定不成功。

7．二叉排序树的查找长度不仅与有关，也与二叉排序树的

8．一个无序序列可以通过构造一棵无序序列进行排序的过程。

9．平衡二叉排序树上任一结点的平衡因子只可能是 或 10． 法构造的哈希函数肯定不会发生冲突。 11．在散列函数H(key)=key%p中，p应取____。

12．在散列存储中，装填因子 的值越大，则____； 的值越小，则____。 8.3 综合练习题:

1. 画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。

4. 选取哈稀函数H（k）=（3k）MOD 11。用开放定址法处理冲突，di=i（（7k）MOD 10+1）（I=1，2，3，…）.试在0-10的散列地址空间中对关键字序列（22,41,53,46,30,13,01,67）造哈希表，并求等概率情况下查找成功时的平均查找长度。

5. 已知一组关键字{49，38，65，97，76，13，27，44，82，35，50}，画出由此生成的二叉排序树，并写出对其进行中序遍历的结果序列。 习题答案

8.1 1．B 2．C 3．C 4．D 5．B 6．C 7．D 8．B

9．C 10．D 11．C 12．B 13．C

8.2 1. （n+1）/2 、((n+1)*log2(n+1))/n-1 、1+ （ 为装填因子）

数据结构复习题及答案

2. 哈希表查找法

3. 顺序存储结构、有序的 4. 1、2、4、8、5、3．7

（依题意，构造一棵有序二叉树，共12个结点，第一层1个结点，第二层2个结点，第三层4个结点，第四层5个结点，则：ASL=（1*1+2*2+3*4+4*5）/12=37/12） 5. O（n）、O(log2n) 6．2、4、3

7．结点个数n、生成过程 8．二叉排序树 9．0、1、-1 10．直接定址

11．素数

12．存取元素时发生冲突的可能性就越大、存取元素时发生冲突的可能性就越小

习题9 排序

9.1 单项选择题

1. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是____。

A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序

2. 设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用____排序法。

A. 起泡排序 B. 快速排序 C. 堆排序 D. 基数排序

3. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是____。

A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序 4. 一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为____。

A. 79，46，56，38，40，80 B. 38，46, 56，79， 40，84， C. 84，79，56，46，40，38 D. 84，56，79，40，46，38 5. 一组记录的关键码为（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 6. 一组记录的排序码为（25，48，16，35，79，82，23，40，36，72），其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为____。

A. 16，25，35，48，23，40，79，82，36，72 B. 16，25，35，48，79，82，23，36，40，72 C. 16，25，48，35，79，82，23，36，40，72 D. 16，25，35，48，79，23，36，40，72，82

7. 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为____。

A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序

8. 排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为____。

A. 希尔排序 B. 归并排序 C. 插入排序 D. 选择排序

9. 用某种排序方法对线性表（ 25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：

⑴ 25，84，21，47，15，27，68，35，20 ⑵ 20，15，21，25，47，27，68，35，84 ⑶ 15，20，21，25，35，27，47，68，84 ⑷ 15，20，21，25，27，35，47，68，84 则所采用的排序方法是____。

数据结构复习题及答案

A. 选择排序 B. 希尔排序 C. 归并排序 D. 快速排序 10. 下述几种排序方法中，平均查找长度最小的是____。

A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序 11. 下述几种排序方法中，要求内存量最大的是____。

A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序 12. 快速排序方法在____情况下最不利于发挥其长处。

A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值 C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数 9.2 填空题 （将正确的答案填在相应的空中）

1. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较____。

2. 在利用快速排序方法对一组记录（54，38，96，23，15，72，60，45，83）进行快速 …… 此处隐藏：2543字，全部文档内容请下载后查看。喜欢就下载吧 ……