数据结构与算法分析 第七章 串、数组和广义表 作业讲解

单选题1

若查找每个记录的概率均等,则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录,其平均查找长度ASL为(    )。

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

正确答案：C

思路：

查找第1个元素，比较1次；

查找第2个元素，比较2次；

……

查找第n个元素，比较n次；

又因为查找每个记录的概率均等为1/n，则平均查找长度

单选题2

二分法查找只适用于查找顺序存储的有序表,平均比较次数为(     ),在此假定n为线性表中结点数,且每次查找都是成功的。

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

正确答案：C

思路：

单选题3

下面关于二分查找的叙述正确的是(    )。

A. 表必须有序,表可以顺序方式存储,也可以链表方式存储
B. 表必须有序且表中数据必须是整型,实型或字符型
C. 表必须有序,而且只能从小到大排列
D. 表必须有序,且表只能以顺序方式存储

正确答案：D

思路：

折半查找（BinarySearch）也称二分查找，它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。对于选项A，如果是链式方式存储，无法计算出low, high, mid的位置；对于选项B，数据可以是任意能比较大小的类型，不局限于整型,实型或字符型；对于选项C，也可以从大到小排列，只需要更改下对应逻辑即可实现二分查找。

单选题4

对无序表用二分法查找比顺序查找快。(    )

A. 正确
B. 错误

正确答案：B

思路：

二分法/折半查找必须采用顺序存储结构且表中元素按关键字有序排列。

单选题5

用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。(    )

A. 正确
B. 错误

正确答案：B

思路：

折半查找要求线性表必须采用顺序存储结构。

单选题6

在n个记录的有序顺序表中进行折半查找,查找成功时,最大比较次数是(    )

A. n
B. n/2
C. (n+1)/2
D. 向下取整(logn)+1

正确答案：D

思路：

方法一：特殊值法。当n=1时，查找成功的最大比较次数为1次，则排除B。当n=4时，比如序列为[1,2,3,4]，想要查找4，则对应该序列的查找成功的最大比较次数为3次，排除A，C，选D。

方法二：根据有序表对应的决策树的结构。

单选题7

具有12个关键字的有序表,折半查找的平均查找长度(    )。

A. 3.1
B. 4
C. 2.5
D. 5

正确答案：A

思路：

方法1，带入公式，这种方法不推荐，因为公式太难记了：

方法2：

画决策树。

单选题8

当在一个有序的顺序存储表上查找一个数据时,即可用折半查找,也可用顺序查找,但前者比后者的查找速度(    )。

A. 必定快
B. 不一定
C. 在大部分情况下要快
D. 取决于表递增还是递减

正确答案：C

思路：

顺序查找的时间复杂度：

 折半查找的时间复杂度：

可从以上图中对比发现在大多数情况下，折半查找的效率更优。

单选题9

当采用分块查找时,数据的组织方式为(    ) 。

A. 数据分成若干块,每块内数据有序
B. 数据分成若干块,每块内数据不必有序,但块间必须有序,每块内最大(或最小)的数据组成索引块
C. 数据分成若干块,每块内数据有序,每块内最大(或最小)的数据组成索引块
D. 数据分成若干块,每块(除最后一块外)中数据个数需相同

正确答案：B

思路：

单选题10

如果一个线性表既能较快的查找,又能适应动态变化的要求,则可采用(    )查找法。

A. 分块查找
B. 顺序查找
C. 折半查找
D. 基于属性

正确答案：A

思路：

分块查找的优点是:在表中插人和删除数据元素时，只要找到该元素对应的块，就可以在该块内进行插人和删除运算。由于块内是无序的，故插人和删除比较容易，无需进行大量移动。如果线性表既要快速查找又经常动态变化，则可采用分块查找。其缺点是:要增加一个索引表的有储空间并对初始索引表进行排序运算。

单选题11

在索引顺序表中,实现分块查找,在等概率查找情况下,其平均查找长度不仅与表中元素个数有关,而且与每块中元素个数有关。(    )

A. 正确
B. 错误

正确答案：A

思路：

多选题12

二叉查找树的查找效率与二叉树的(    )有关,在(    )时其查找效率最低。(选择两项)

 A. 高度
B. 结点的多少
C. 树型
D. 结点的位置

E. 结点太多

 F. 完全二叉树

 G. 呈单枝树

 H. 结点太复杂

正确答案：C;G

思路：

单选题13

分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是(    ) 。

A. (100,80, 90, 60, 120,110,130)
B. (100,120,110,130,80, 60, 90)
C. (100,60, 80, 90, 120,110,130)
D. (100,80, 60, 90, 120,130,110)

正确答案：C

单选题14

顺序查找法适用于存储结构为顺序或链接存储的线性表。(    )

A. 正确
B. 错误

正确答案：A

单选题15

就平均查找长度而言,分块查找最小,折半查找次之,顺序查找最大。(    )

A. 正确
B. 错误

正确答案：B

思路：

应该是折半最小，分块次之，顺序最大。

单选题16

对大小均为n的有序表和无序表分别进行顺序查找,在等概率查找的情况下,查找成功时的平均查找长度是相同的,而对于查找失败,它们的平均查找长度是不同的。(    )

A. 正确
B. 错误

正确答案：A

思路：

顺序查找有序表时可以利用有序这个信息，在查找失败时提前终止查找。而无序表每次查找失败时，都必须要从第一个元素比较至最后一个元素。

单选题17

对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。(    )

A. 正确
B. 错误

正确答案：B

思路：

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树:

1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值;
2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值;
3. 它的左、右子树也分别为二叉排序树

二叉排序树是递归定义的。由定义可以得出二叉排序树的一个重要性质:中序遍历一棵二叉树时可以得到一个结点值递增的有序序列。

单选题18

虽然信息项序列的顺序不一样,但依次生成的二叉排序树却是一样的。(    )

A. 正确
B. 错误

正确答案：B

思路：

举一个反例：

填空题19

顺序查找n个元素的顺序表,若查找成功,则比较关键字的次数最多为(______   )次;当使用监视哨时,若查找失败,则比较关键字的次数为(______   )。

正确答案：n; n+1

思路：

第一个问题：查找成功比较关键字的次数最多的情形是：要查找的关键字位于最后一个位置（位置n）。则从第一个位置开始比较至位置n一共比较了n次；

第二个问题：使用监视哨查找失败的情形是：从最后一个位置n比较到第0个位置一共比较了n+1次。

填空题20

在顺序表(8,11,15,19,25,26,30,33,42,48,50)中,用折半法查找关键码值20,需做的关键码比较次数为(______   ).

正确答案：4

思路：

方法一：

方法二：

利用决策树。

填空题21

在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为______   .

正确答案：6,9,11,12

思路：

利用决策树。

填空题22

在有序表A[1..11]中,按二分查找方法进行查找,查找长度为4的元素个数是(______   )。

正确答案：4

填空题23

己知有序表为(12,18,24,35,47,50,62,83,90,115,134)当用二分法查找90时,需(______   )次查找成功,47时(______   )次成功,查100时,需(______   )次才能确定不成功。

正确答案：2; 4; 3

思路：

画决策树

填空题24

对于长度为255的表,采用分块查找,每块的最佳长度为(______   )。

正确答案：16

思路：

填空题25

分块检索中,若索引表和各块内均用顺序查找,则有900个元素的线性表分成(______   )块最好:若分成25块,其平均查找长度为(______   )。

正确答案：30; 31.5

思路：

填空题26

已知二叉排序树的左右子树均不为空,则(______   )上所有结点的值均小于它的根结点值,(______   )上所有结点的值均大于它的根结点的值。

正确答案：左子树; 右子树

思路：

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树:

1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值;
2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值;
3. 它的左、右子树也分别为二叉排序树

二叉排序树是递归定义的。由定义可以得出二叉排序树的一个重要性质:中序遍历一棵二叉树时可以得到一个结点值递增的有序序列。

填空题27

动态查找表和静态查找表的重要区别在于前者包含有(______   )和(______   )运算,而后者不包含这两种运算。

正确答案：插入；删除

思路：

若在查找的同时对表做修改操作（如插人和删除),则相应的表称之为动态查找表，否则称之

为静态查找表。

单选题28

完全二叉树肯定是平衡二叉树。(    )

A. 正确
B. 错误

正确答案：B

思路：

平衡二叉树或者是空树，或者是具有如下特征的二叉排序树:

1. 左子树和右子树的深度之差（即平衡因子）的绝对值不超过1;
2. 左子树和右子树也是平衡二叉树。

单选题29

N个结点的二叉排序树有多种,其中树高最小的二叉排序树是较好的。(    )

A. 正确
B. 错误

正确答案：A

思路：

单选题30

在任意一棵非空二叉排序树中,删除某结点后又将其插入,则所得二排序叉树与原二排序叉树相同。(    )

A. 正确
B. 错误

正确答案：B

单选题31

二叉排序树删除一个结点后,仍是二叉排序树。(    )

A. 正确
B. 错误

正确答案：A

思路：

单选题32

设有一组记录的关键字为{19,14,23,1,68,20,84,27,55,11,10,79},用链地址法构造散列表,函数为H(key)=key MOD 13地址为1的链中有(    )个记录。

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

正确答案：D

单选题33

关于杂凑查找说法不正确的有几个(    )                                           

(1)采用链地址法解决冲突时,查找一个元素的时间是相同的   (2)采用链地址法解决冲突时,若插入规定总是在链首,则插入任一个元素的时间是相同的   (3)用链地址法解决冲突易引起聚集现象      (4)再哈希法不易产生聚集

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

正确答案：B

思路：

杂凑法又叫散列查找法或散列法。

 （1）错。（2）对。（3）错。（4）对。

再哈希法：同时构造多个不同的哈希函数，等发生哈希冲突时就使用第二个、第三个……等其他的哈希函数计算地址，直到不发生冲突为止。

单选题34

哈希查找中k个关键字具有同一哈希值,若用线性探测法将这k个关键字对应的记录存入哈希表中,至少要进行(    )次探测。

A. k
B. k+1
C. k(k+1)/2
D. 1+k(k+1)/2

正确答案：C

思路：

对于第1个关键字：探测1次能成功找到；

对于第2个关键字：探测2次能成功找到；

。。。

对于第k个关键字：探测k次能成功找到；

则对于总共k个关键字，一共探测了(1+2+ …… +k)=k(k+1)/2

单选题35

散列函数有一个共同的性质,即函数值应当以(    )取其值域的每个值。

A. 最大概率
B. 最小概率
C. 平均概率
D. 同等概率

正确答案：D

思路：

构造一个“好”的散列函数应遵循以下两条原则:

（1）函数计算要简单，每一关键字只能有一个散列地址与之对应;

（2）函数的值域需在表长的范围内，计算出的散列地址的分布应均匀，尽可能减少冲突。

多选题36

散列表的地址区间为0-17,散列函数为H(K)=K MOD 17。采用线性探测法处理冲突,并将关键字序列26,25,72,38,8,18,59依次存储到散列表中。(1)元素59存放在散列表中的地址是(    )。(2)存放元素59需要搜索的次数是(    )。

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

E. 10

 F. 4

 G. 5

H. 11

正确答案：H;F

单选题37

将10个元素散列到100000个单元的哈希表中,则(    )产生冲突。

A. 一定会
B. 一定不会
C. 仍可能会

正确答案：C

单选题38

在散列检索中,“比较”操作一般也是不可避免的。(    )

A. 正确
B. 错误

正确答案：A

单选题39

Hash函数越复杂越好,因为这样随机性好,冲突概率小。(    )

A. 正确
B. 错误

正确答案：B

思路：

hash函数太复杂会造成整个存储或查找过程效率低。

单选题40

哈希函数的选取平方取中法最好。(    )

A. 正确
B. 错误

正确答案：B

思路：

平方取中法的适用情况:不能事先了解关键字的所有情况，或难于直接从关键字中找到取值较分散的几位。

单选题41

Hash表的平均查找长度与处理冲突的方法无关。(    )

A. 正确
B. 错误

正确答案：B

思路：

处理冲突的方法与散列表本身的组织形式有关。按组织形式的不同，通常分两大类:开放地址法和链地址法。

单选题42

负载因子 (装填因子)是散列表的一个重要参数,它反映散列表的装满程度。( )

A. 正确
B. 错误

正确答案：A

思路：

单选题43

Hash表的平均查找长度不随表中结点数目的增加而增加,而与装填因子有关。(    )

A. 正确
B. 错误

正确答案：A

思路：

单选题44

哈希表的结点中只包含数据元素自身的信息,不包含任何指针。(    )

A. 正确
B. 错误

正确答案：B

思路：

如果为处理冲突，选择的组织方式是链地址法，则含有指针信息：

单选题45

若Hash表的装填因子小于1,则可避免碰撞的产生。( )

A. 正确
B. 错误

正确答案：B

思路：

举例，散列表的长度为11，散列函数H(key)=key%1,假设表中已填有关键字分别为60,17,29，现有第四个记录其关键字为38，由散列函数得到散列地址为5，此时的装填因子为4/11<1, 但仍产生冲突。