查找--练习题

01

1. 如图所示的二叉排序树，查找成功时的平均查找长度是（ ）。

A. 21/7

B. 28/7

C. 15/6

D. 21/6

答案：C

2. 在一棵平衡二叉树中，每个结点的平衡因子的取值范围是（ ） 。

A. -1~1

B. -2~2

C. 1~2

D. 0~1

答案：A

3. （判断题）查找效率最高的二叉排序树是平衡二叉排序树。

答案：对

4. （判断题）在二叉排序树中新插入的结点总是作为叶子结点来插入的。

答案：对

5. （判断题）在二叉排序树中新插入的结点总是处于最底层。

答案：错

6. （判断题）每个结点的关键字都比左孩子关键字大，比右孩子关键字小，

这样的二叉树都是二叉排序树。

02

1.采用顺序查找法查找长度为n的线性表时，平均查找长度为（ ）。

A. n

B. n/2

C. (n+1)/2

D. (n-1)/2

答案：C

2. (多选)通常将（ ）作为衡量一个查找算法效率优劣的标准。

A. 平均查找长度

B. 比较次数

C. WPL

D. ASL

答案：AD

3. （判断题）顺序查找方法只能在顺序存储结构上进行。

答案：错

4.顺序查找含n个元素的顺序表，若查找成功，则比较关键字的次数最多

为（ ）次。

答案：n

5. 对列表进行折半查找时，要求列表必须（ ）。

A. 顺序存储

B. 链式存储

C. 顺序存储且元素按关键字有序存储

D. 链式存储且元素按关键字有序存储

答案：C

6.有一个有序表{1, 3, 9, 12, 32, 41，45, 62, 75, 77, 82, 95, 99}当采用

折半查找法查找关键字为 82 的元素时，需经过（ ）次比较后查找成功。

A. 1

B. 2

C. 4

D. 8

答案：C

7. （判断题）折半查找可以在有序的双向链表上进行。

答案：错