练习题

一、选择题

1.静态查找表与动态查找表的根本区别在于（ ）。

A.它们的逻辑结构不一样　B.其上的操作不一样

C.所包含的数据元素类型不一样　D.存储实现不一样

2.在表长为n的顺序表上实施顺序查找，在查找不成功时与关键字比较的次数为（ ）。

A.n　B.1　C.n＋1　D.n－1

3.顺序查找适用于存储结构为（ ）的线性表。

A.散列存储B.压缩存储

C.顺序存储或链接存储D.索引存储

4.用顺序查找法对具有n个结点的线性表查找一个结点的时间复杂度为（ ）。

A.O（log2n2）　B.O（nlog2n）　C.O（n）　D.O（log2n）

5.适用于折半查找的表的存储方式及元素排列要求为（ ）。

A.链接方式存储，元素无序　B.链接方式存储，元素有序

C.顺序方式存储，元素无序　D.顺序方式存储，元素有序

6.一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况下查找成功所需要的平均比较次数为（ ）。

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

7.在有序表｛1，3，9，12，32，41，62，75，77，82，95，100｝上进行折半查找关键字为82的数据元素需要比较（ ）次。

A.1　B.2　C.4　D.5

8.设散列表长为14，散列函数为H（key）＝key%11。当前表中已有4个结点：addr（15）＝4，addr（38）＝5，addr（61）＝6，addr（84）＝7。如用二次探测再散列处理冲突，则关键字为49的结点的地址是（ ）。

A.8　B.3　C.5　D.9

9.假设有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行（ ）探测。

A.k－1次　B.k次　C.k＋1次　D.k（k＋1）／2次

10.在散列函数H（k）＝k%m中，一般来讲，m应取（ ）。

A.奇数　B.偶数　C.素数　D.充分大的数

11.下列关于m阶B树的说法错误的是（ ）。

A.根结点至多有m棵子树

B.所有叶子都在同一层次上

C.非叶结点至少有m／2（m为偶数）或m／2＋1（m为奇数）棵子树

D.根结点中的数据是有序的

12.m阶B树是一颗（ ）。

A.m叉排序树　B.m叉平衡排序树

C.m－1叉平衡排序树　D.m＋1叉平衡排序树

二、简答题

1.建立一棵具有13个结点的判定树，并求其成功和不成功的平均查找长度值各为多少。

2.已知长度为12的表｛Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec｝

（1）试按表中元素的次序依次插入一棵初始为空的二叉排序树，并求在等概率情况下查找成功的平均查找长度。

（2）用表中元素构造一棵最佳二叉排序树，求在等概率的情况下查找成功的平均查找长度。

（3）按表中元素顺序构造一棵AVL树，并求其在等概率情况下查找成功的平均查找长度。

3.用关键字1，2，3，4的四个结点能构造出几种不同的二叉排序树？其中最优查找树有几种？AVL树有几种？完全二叉树有几种？试画出这些二叉排序树。

4.设哈希函数H（k）＝3k%11，散列地址空间为0～10，对关键字序列（32，13，49，24，38，21，4，12）按下述两种解决冲突的方法构造哈希表：

（1）线性探测再散列。

（2）链地址法，并分别求出等概率下查找成功时和查找失败时的平均查找长度。