第10章查找习题参考答案
一、单选题
ABC
ABC
D
n
n/2
C.(n+1)/2
D.(n-1)/2
ABC
ABC
D
1
n
n/2
D.(n+1)/2
3.
对长度为3的顺序表进行顺序查找，若查找第1个元素的概率是1/2，查找第2个元素的概率是1/3，查找第3个元素的概率是1/6，则成功查找表中任一元素的平均查找长度是 。
A
ABC
D
A.5/3
B.2
C.7/3
D.3
ABC
ABC
D
以顺序方式存储
以链接方式存储
以顺序方式存储，且结点按关键字有序排序
以链表方式存储，且结点按关键字有序排序
ABC
ABC
D
一次成功查找过程终止的结点
一次失败查找过程终止的结点
一次成功查找过程中经过的中间结点
一次失败查找过程中经过的中间结点
ABCD已知一个长度为16的有序顺序表R[1..16]
ABC
D
5
4
7
6
AB设有100个元素的有序顺序表，采用折半查找方法，不成功时最大的比较次数是 。
A
B
25
50
CD
C
D
7
有一个长度为12的有序表R[0..11]，按折半查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为 。
ABCDA.
ABC
D
B.37/12
C.39/12
D.43/12
有一个长度为12的有序表R[0..11]，按折半查找法对该表进行查找，在表内各元素等概率情况下查找不成功所需的平均比较次数为 。
ABCDA.
ABC
D
B.37/12
C.49/12
D.49/13imgstyle=max-width:50%;src=/d95099e5345aeb40dba9fdc51883db92.png/
有一个有序表为（1，3，9，12，32，41，45，62，75，77，82，95，99），当采用折半查找法查找关键字为82的元素时， 次比较后查找成功。
A
ABC
D
1
2
4
8
ABCD有一个长度为n的有序顺序表，采用折半查找，经过
ABC
D
2i
2i+1
2i-1
2i-1
ABC
ABC
D
数据分成若干块，每块内数据有序
数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的关键字组成索引块
数据分成若干块，每块内数据有序，每块内最大（或最小）的关键字组成索引块
数据分成若干块，每块中的数据个数必须相同
ABC
ABC
D
A.1800
B.60
C.1200
D.log23600
设待查关键字为47，且已存入变量k中，如果在查找过程中，和k进行比较的元素依次是47、32、46、25、47，则所采用的查找方法
。
A
ABC
D
是一种错误的方法
可能是分块查找
可能是顺序查找
可能是折半查找
设待查关键字为47，且已存入变量k中，如果在查找过程中，和k进行比较的元素依次是27、72、16、84、47，则所采用的查找方法是
。
A
ABC
D
二叉排序树查找
分块查找
顺序查找
折半查找
ABC
ABC
D
折半查找
分块查找
顺序查找
二叉排序树查找
ABCD以下
ABC
D
二叉排序树是动态树表，在插入新结点时会引起树的重新分裂和合并
对二叉排序树进行层次遍历可以得到一个有序序列
在构造二叉排序树时，若关键字序列有序，则二叉排序树的高度最大
在二叉排序树中进行查找，关键字的比较次数最多不超过结点数的一半
ABCD由一个关键字序列建立一棵二叉排序树，
ABC
D
该序列的存储结构
序列中的关键字的取值范围
关键字的输入次序
使用的计算机的软、硬件条件
在任意一棵非空二叉排序树T1中，删除某结点v之后形成二叉排序树T2，再将v插入T2形成二叉排序树T3。下列关于T1与T3的叙述中，正确的是 。I.若v是T1的叶子结点，则T1与T3不同II.若v是T1的叶子结点，则T1与T3相同III.若v不是T1的叶子结点，则T1与T3不同IV.若v不是T1的叶子结点，则T1与T3相同
A
ABC
D
仅I、III
仅I、IV
仅II、III
仅II、IV
ABCD对于下列关键字序列，不可能构成
ABC
D
A.95，22，91，24，94，71
B.92，20，91，34，88，35
C.21，89，77，29，36，38
D.12，25，71，68，33，34
ABCD
ABC
D
树形未定，无法确定
B.18，43，27，77，44，36，39
C.18，27，36，39，43，44，77
D.18，44，43，39，36，27，77
以下查找方法中速度最快的是
A
ABC
D