7.2　习题解答

一、选择题

1. 顺序查找法适合于存储结构为( )的线性表。

A. 散列存储 B. 顺序存储或链式存储 C. 压缩存储 D. 索引存储

【解答】 B

分析：由顺序查找表的定义可知。

2. 对线性表进行二分查找时，要求线性表必须( )。

A. 以顺序方式存储B. 以链式方式存储

C. 以顺序方式存储，且结点按关键字有序排序

D. 以链式方式存储，且结点按关键字有序排序

【解答】 C

分析：查找关键字时，与查找表中间的结点关键字比较，比较后按中间的关键字再次划分查找表，所以必须是顺序存储且有序。

3. 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为( )。

A.n　　B.n/2　　C. (n+1)/2　　D. (n-1)/2

【解答】 C

分析：根据算法得知：在顺序查找时，查找最后一个元素比较n次，查找倒数第2个元素比较n-1次，依次类推，查找第1个元素比较1次，因此，总比较次数为n(n+1)/2，在等概率查找的情况下，每个元素的平均查找长度为（n(n+1)/2)·1/n=(n+1)/2。

最好情况的查找长度为1，最坏情况的查找长度为n。

4. 采用二分查找法查找的长度为n的线性表时，每个元素的平均查找长度为( )。

A.O(n₂)　B.O(nlog²n)　C.O(n)　D.O(log²n)

【解答】 D

分析：二分查找函数恰好是一条从判定树的根到被查找结点的路径，而比较的次数恰好是树深。具有n个结点的完全二叉树的深度为h=[log₂(n+1)]或h=[log₂n]+1。所以正确答案为D。

5. 有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值为82的结点时，( )次比较后查找成功。

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

【解答】 C

分析：比较过程：首先与1～100的中间位置值45比较，再与62～100的中间位置值77比较，第三次与82～100的中间位置值95比较，最后与82比较，所以为4次。

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

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

【解答】 B

分析：构造一棵有序二叉树，共有12个结点，第一层1个，第二层2个，第三层4个，第四层5个，则ASL=(1×1+2×2+3×4+4×5)/12=37/12

7. 静态查找与动态查找的根本区别在于( )。

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

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

【解答】 B

分析：静态查找不涉及插入和删除操作，而动态查找涉及插入和删除操作。

二、填空题

1. 顺序查找法的平均查找长度为( )；二分查找法的平均查找长度为( )；分块查找法(以顺序查找确定)的平均查找长度为( )；分块查找法(以二分查找确定块)的平均查找长度为( )；哈希查找法采用链界法处理冲突的平均查找长度为( )。

【解答】 (n+1)/2；(n+1)log₂(n+1)/n-1；(s²+2s+n)/2s；log₂(n/s+1)+s/2；1+α

2. 二分查找的存储结构仅限于( )，且是( )。

【解答】 顺序存储结构；有序的

3. 对于长度为n的线性表，若进行顺序查找，则时间复杂度为( )；若采用二分查找，则时间复杂度为( )；若采用分块查找(假定总块数和每块长度均接近)，则时间复杂度为( )。

【解答】O(n)；O(log₂n)；O()

三、解答题

1. 线性表的关键字集合{87，25，310，08，27，132，68，95，187，123，70，63，47},共有13个元素，已知散列函数为：

H(k)k=%13

采用拉链法处理冲突。设计出这种链表结构，并计算该表的成功查找的平均查找长度。

【解答】 依题意，得到：

H(87)=87%13=9

H(25)=25%13=12

H(310)=310%13=11

H(8)=8%13=8

H(27)=27%13=19

H(132)=132%13=2

H(68)=68%13=3

H(95)=95%13=4

H(187)=187%13=5

H(123)=123%13=6

H(70)=70%13=5

H(63)=63%13=11

H(47)=47%13=8

采用拉链法处理冲突的链接表如图7-1所示。

图7-1

成功查找的平均长度：ASL=(1×10+2×3)/13=16/13

2. 设有一组关键字{19，01，23，14，55，20，84，27，68，11，10，77}，采用哈希函数h(key)=key%13

采用开放地址的随机探测再散列方法解决冲突，试在0 ~ 18的散列地址空间中对该关键字序列构造哈希表。

【解答】 依题意，m=19，随机探测再散列的下一地址计算公式为：

d₁=h(key)d_j=(d₁+R)%m

取伪随机序列为3，54，11，36，19，…计算函数为：

H(19)=19%13=6

H(1)=1%13=1

H(23)=23%13=10

H(14)=14%13=1(冲突)

H(14)=(1+3)%19=4

H(55)=55%13=3

H(20)=20%13=7

H(84)=84%13=6(冲突)

H(84)=(6+3)%19=9

H(27)=27%13=1(冲突)

H(27)=(1+3)%19=4(仍冲突)

H(27)=(1+54)%19=17

H(68)=68%13=3(冲突)

H(68)=(3+3)%19=6(仍冲突)

H(68)=(3+54)%19=0()

H(11)=11%13=11

H(10)=10%13=10(冲突)

H(10)=(10+3)%19=13(仍冲突)

H(77)=77%13=12

各关键字的记录对应的地址分配如下：

Addr(68)=0

Addr(1)=1

Addr(55)=3

Addr(14)=4

Addr(19)=6

Addr(20)=7

Addr(84)=9

Addr(23)=10

Addr(11)=11

Addr(77)=12

Addr(10)=13

Addr(27)=17

其他地址为空。

3. 编写一个函数，利用二分查找算法在一个有序表中插入一个元素x，并保持表的有序性。

【解答】 依题意，先在有序表r中利用二分查找算法查找关键字值等于或小于x的结点，mid指向正好等于x的结点或low指向关键字正好大于x的结点，然后采用移动法插入x的结点即可。

函数如下：

Bininsert(sqlist r,int x ,int n)

4. 编写算法判断一棵树是否为二叉排序树及结点在二叉排序树中的层次数。

【解答】 (1)int SortBiTree(BiNode *root)