数据结构习题11级用(13)

第九章 查找

一、选择题

1．顺序查找法适合于存储结构为（ ）的线性表。 A．散列存储 B.顺序存储或链式存储 C.压缩存储 D.索引存储

2．二分查找法要求查找表中各元素的关键字必须是（ ）排列。 A．递增或递减 B.递增 C. 递减 D.无序

3．在长度为n的线性表中使用顺序查找法的平均查找长度是( )。 A． O(1) B． O(n) C.O(log2n) D．O(n)

4．在长度为n的有序表中使用二分查找法的平均查找长度是( )。 A． O(1) B． O(n) C．O(log2n) D．O(n2)

5．对有18个元素的有序表作二分查找，则查找A[3]的比较序列的下标依次为

( )。

A． 1，2，3 B． 9，5，2，3 C． 9，5，3 D． 9，4，2，3 6．有一个有序表为{3，9，12，32，41，45，62，75，77，82，99} ，用二分查找法

查找82成功时的查找次数是( )。

A． 1 B． 2 C． 3 D． 4

7．如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用（ ）

查找方法。 A． 分块

B． 顺序 C． 二分

D． 散列

8．在下列查找方法中，平均查找速度最快的是（ ）。

A． 分块查找 C． 二分查找 量级相当。 A． 分块查找 C． 二分查找

B． 顺序查找 D． 前面都不正确 B． 顺序查找 D． 二叉排序树查找

2

9．在关键字随机分布的情况下，用二叉排序树的方法进行查找，其查找长度与（ ）

10．在二分查找中，第i次查找成功的记录个数最多为（ ）。

A． 2i B． 2i+1 C． 2i-1 D． 2i-1

11．用n个关键字构造一棵二叉排序树，最低高度为（ ）。

A． n/2 A． 奇数

B．

n C． nlog2n D． log2n +1

D． 充分大的数

12. 在散列函数H(k)=k MOD m 中，一般来讲，m应取（ ）。

B． 偶数 C． 素数

38

二、填空题

1．顺序查找法的平均查找长度为 ；二分查找法的平均查找长度为 。 2．在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 。 3．以二分查找方法从长度为50的有序表中查找一个元素时，其查找长度不超

过 。

4．在具有20个元素的有序表中进行二分查找，则比较一次查找成功的结点数

为 ，比较两次查找成功的结点数为 ，比较3次查找成功的结点数为 ，比较4次查找成功的结点数为 ，比较5次查找成功的结点数为 。总的平均查找长度为 。

5．在随机情况下，含有个结点的二叉排序树的平均查找长度为 。当二叉排序树退化为一棵单支树时，平均查找长度为 。

6．对一棵二叉排序树，若以 遍历该树，将得到一个以关键字递增顺序排列的有序序列。

7. 平衡二叉树上结点的平衡因子是指 。 8. Hash技术解决冲突的方法主要有 两种。 9. Hash技术关键是 两个方面。

10．散列函数的构造方法通常是 、 、 、 和

五种。

11．若待散列的序列为（18，25，63，50，42，32，9），散列函数为H(key)=key mod

9，与18发生冲突的元素有 个。

12．在散列存储中，装填因子α的值越大，则存储元素时发生冲突的可能性

就 。

三、基础知识题

1．简述顺序查找法和二分查找法的区别。

2．若对大小均为n的有序的顺序表和无序的顺序表分别进行顺序查找，试在下列三

种情况下分别讨论两者在等概率时的平均查找长度是否相同？ （1）查找不成功，即表中没有关键字等于给定值K的记录； (2) 查找成功，且表中只有一个关键字等于给定值K的记录；

(3) 查找成功，且表中有若干个关键字等于给定值K的记录，一次查找要求找出

所有记录。此时的平均查找长度考虑找到所有记录时所用的比较次数。 3．画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平

均查找长度。

39

4．已知一组元素为(37,70,29,46,25,78,62,12)，画出按元素排列输入生成的一棵二叉排序树，并求其在等概率情况下查找成功的平均查找长度（要求写出每插入一个元素时二叉排序树形状）。

5. 取适当Hash函数及处理冲突的方法，试在0--12散列地址空间中对关键字序列(2,41,53,46,30,13,01,67)构造Hash表，并求出等概率下查找成功的平均查找长度。

6．已知长度为12的表{Jan,Feb,Mar,Apr,May,June,July, Aug,Sep,Oct,Nov, Dec},（1）试按表中元素顺序建立一棵二叉排序树，并求其在等概率情况下查找成功的 平均查找长度；

（2）若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度；(3) 按表中元素顺序建立一棵平衡二叉排序树，并求其在等概率情况下查找成功的平均查找长度。

7．试推导含12个结点的平衡二叉树的最大深度，并画出一棵这样的树。

8． 从空树开始，画出按下列次序向2-3树即3阶B-树中插入关键字的建树过程：

20，30，50，52，60，68，70。如果此后删除50和68，画出每一步执行后2-3树的状态。

9．已知一个含有1000个记录的表，关键字为中国人姓氏的拼音，请给出此表的一个

哈希表设计方案，要求它在等概率情况下查找成功的平均查找长度不超过3。

四、算法设计题

1．假设顺序表按关键字自大至小有序，改写顺序查找算法，将监视哨设在高下标端。

然后画出描述此查找过程的判定树，分别求出等概率情况下查找成功和不成功时的平均查找长度。

2．编写递归算法，从大到小输出给定二叉排序树中所有关键字不小于x的数据元素。 3．编写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表为存

储结构且树中结点的关键字均不同。

4．假设哈希表长为m，哈希函数为H(x)，用链地址法处理冲突。试编写输入一组关

键字并建造哈希表的算法。

40

第十章 内部排序

一、选择题

1．堆排序属于（ ）。

A． 插入排序 B 交换排序 C 归并排序 D． 选择排序 2．快速排序属于（ ）。

A． 插入排序 B 交换排序 C 归并排序 D． 选择排序 3．希尔排序属于（ ）.

A． 插入排序 B 交换排序 C 归并排序 D． 选择排序

4．在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是（ ）。 A． 插入排序 B 希尔排序 C 选择排序 D． 冒泡排序

5．每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序方法是（ ）。 A． 直接插入排序 B 希尔排序 C 简单选择排序 D． 冒泡排序 6．在待排序的元素基本有序的前提下，效率最高的排序方法是（ ）。 A． 快速排序 B 选择排序 C 插入排序 D． 归并排序 7．快速排序执行一遍之后，已经到位的元素个数是（ ）。

A． 1 B 3 …… 此处隐藏：1996字，全部文档内容请下载后查看。喜欢就下载吧 ……