死机英文习题第九章查找答案

2021年1月22日发(作者：ba是什么)
第九章

查找

一、

选择题

1.
若查找每个记录的概率均等，则在具有
n
个记录的连续顺序文件中采用顺序查找 法查找一个记录，其平均查找长度
ASL
为
( C )
。
【北京航空航天大学
2000
一、
8
（
2
分）
】

A
．
(n-1)/2 B. n/2 C. (n+1)/2 D. n
2.
对
N
个元素的表做顺序查 找时，若查找每个元素的概率相同，则平均查找长度为
(
A
)
【南京理 工大学
1998
一、
7
（
2
分）
】

A
．
（
N+1
）
/2 B. N/2 C. N D. [
（
1+N
）
*N ]/2
3.
下面关于二分查找的叙述正确的是
( D )
【南京理工大学
1996
一、
3
（
2
分）
】

A.
表必须有序，表可以顺序方式存储，也可以链表方式存储
C.
表必须有序，而且只能从小到大排列

B.
表必须有序且表中数据必须是整型，实型或字符型
D.
表必须有序，且表只能以顺序方式存储

4.
对线性表进行二分查找时，要求线性表必须（
B
）
【燕山大学
2001
一、
5
（
2
分）
】

A.
以顺序方式存储
B.
以顺序方式存储
,
且数据元素有序
C.
以链接方式存储
D.
以链接方式存储
,
且数据元素有序

5
．适用于折半查找的表的存储方式及元素排列要求为
( D )
【南京理工大学
1997
一、
6
（
2
分）
】

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

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

6
．当在一个有序的顺序存储表上查找一个数 据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度
( C )
A
．必定快
B.
不一定
C.
在大部分情况下要快
D.
取决于表递增还是递减

【南京理工大学
1997
一、
7
（
2
分）
】

7
．当采用分快查找时，数据的组织方式为
( B )
【南京理工大学
1996
一、
7
（
2
分）
】

A
．数据分成若干块，每块内数据有序

B
．数据分成若干块，每块 内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块

C.
数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块

D.
数据分成若干块，每块（除最后一块外）中数据个数需相同

8.
二叉查找树的查找效率与二叉树的
(
（
1
）
C)
有关
,
在
(
（< br>2
）
C)
时其查找效率最低【武汉交通科技大学
1996
一、
2(4
分
)
】

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

(2): A.
结点太多
B.
完全二叉树
C.
呈单枝树
D.
结点太复杂。

9.
要进行顺序查 找，则线性表（
1C
）
；要进行折半查询，则线性表（
2D
）
；若表中元素个数为
n,
则顺序查找的平均比较次数为
（
3G
）< br>；折半查找的平均比较次数为（
4H
）
。
【北方交通大学
1999
一、
2
（
4
分）
】


（
1
）
（
2
）
：
A.
必须以顺序方式存储；
B.
必须以链式方式存储；
C.
既可以以顺序方式存储，也可以链式方式存储；

D.
必须以顺序方式存储，且数据已按递增或递减顺序排好；

E.
必须以链式方式存储，且数据已按递增或递减的次序排好。

n
n
（
3
）
（
4
）
：
A.n B.n/2 C.n*n D.n*n/2
2

2
G.(n+1)/2
2
(n+1)
10
．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用
( A)
查找法。

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

【西安电子科技大学
2001
应用

一、
8
（
2
分）
】

11.
既希望较快的查找又便于线性表动态变化的查找方法是
( C )
【北方交通大学
2000
二、
4
（
2
分）
】

A
．顺序查找
B.
折半查找
C.
索引顺序查找
D.
哈希法查找

12
．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是
( C )
【合肥工业大学
2000
一、
4
（
2
分 ）
】

A
．
（
100
，
80
，
90
，
60
，
120
，
110
，
130
）
B.
（
1 00
，
120
，
110
，
130
，
80< br>，
60
，
90
）

C.
（
100
，
60
，
80
，
90
，
120
，
110
，
130
）
D. (100
，
80
，
60
，
90
，
120
，
130
，
110)
13.
散列表的地址区间为
0-17,
散列函数为
H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列
26
，
25
，
72
，
38
，
8
，
18
，
59
依次存 储到散列表中。


（
1
）元素
59
存放在散列表中的【北方交通大学
2001
一、
（
19
，
20
）

（
4
分）
】地址是（
D
）
。

A
．
8 B. 9 C. 10 D. 11

（
2
）存放元素
59
需要搜索的次数是（
C
）
。

A
．
2 B. 3 C. 4 D. 5
14.
将
10
个元素散列到
100000
个单元的哈希表中，则（
C
）产生冲突。
【北京邮电大学
2001
一、
4
（
2
分）
】

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

15.
设有一组记录的关键字为
{19
，
14
，
23
，
1
，
68
，
20
，
84
，
27
，< br>55
，
11
，
10
，
79}
，
用链 地址法构造散列表，
散列函数为
H
（
key
）
=key MOD 13,
散列地址为
1
的链中有（

D
）个记录。
【南京理工大学

1997
一、
4
（
2
分）
】

A
．
1 B. 2 C. 3 D. 4
16.
下面关于哈希
(Hash
，杂凑
)
查找的说法正确的是
( C )
【南京理工大学
1998
一、
10
（
2
分）
】

A
．哈希函数构造的越复杂越好，因为这样随机性好，冲突小

B
．除留余数法是所有哈希函数中最好的

C
．不存在特别好与坏的哈希函数，要视情况而定

D
．若需在哈希 表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可

17.
若采用链地址法构造散列表，散列函数为
H
（
key
）
=key MOD 17
，则需
(
（
1
）
A)
个链表。这些链的链首指针构成一个指
针数组，数组的下标范围为
(
（
2
）
C)
【南京理工大学
1999
一、
12(13)
（
4
分）
】

（
1
）
A
．
17 B. 13 C. 16 D.
任意

（
2
）
A
．
0
至
17 B. 1
至
17 C. 0
至
16 D. 1
至
16
18. 设哈希表长为
14
，
哈希函数是
H(key)=key%11,
表中已有数据的关键字为
15
，
38
，
61
，
84
共四个，
现要将关键字为
49
的结
点加到表中，用二次探测再散列法 解决冲突，则放入的位置是
( D )
【南京理工大学
2001
一、
15
（
1.5
分）
】

A
．
8 B
．
3 C
．
5 D
．
9
19.
假定有
k
个关键字互为同义词，若用线性探测法把这
k
个关键字存入散列表中，至少要进行多 少次探测？
( D )
A
．
k-1
次
B. k
次
C. k+1
次
D. k
（
k+1
）
/2
次

【中国科技大学
1998
二、
3
（
2
分）
】
【中科院计算所
1998
二、
3
（
2
分）
】

20.
哈希查找中
k
个关键字具有同一哈希值，若用线性探测法将这
k
个关键字对应 的记录存入哈希表中，至少要进行
(
C
)
次探
测。
【西安电子科技大学
1998
一、
8
（
2
分）
】

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

三、填空题

1.
在顺序表（8,11,15,19,25,26,30,33,42,48,50
）中，用二分（折半）法查找 关键码值
20
，需做的关键码比较次数为
_4__.
【北方交通大学
2001
二、
2
】

2. < br>给定一组数据
{6
，
2
，
7
，
10
，
3
，
12}
以它构造一棵哈夫曼树，则树高为
__5_____< br>，带权路径长度
WPL
的值为
___96_____
。

【南京理工大学
1997
三、
4
（
2
分）
】

3.
己知有序表为
(12 ,18,24,35,47,50,62,83,90,115
，
134)
当用二分法 查找
90
时，需
____2____
次查找成功，
47
时< br>____4____
成功，查
100
时，需
___3_____
次才能确定不成功。
【南京理工大学
2000
二、
7
（
4.5
分）
】

4.
平衡二叉树又称
__ AVL
树
（高度平衡树，高度平衡的二叉排序树），
____
，其定义是
_
或为空二叉树，或二叉树中任意结点
左 子树高度与右子树高度差的绝对值小于等于
1__
。
【青岛大学
2001
六、
3
（
3
分）
】

5.
在哈希函数
H
（
key
）
=key%p中，
p
值最好取
_
小于等于表长的最大素数或不包含小于
20< br>的质因子的合数
__
。
【青岛大学
2002
三、
9
（
2
分）
】

6
．假定 有
k
个关键字互为同义词，若用线性探测再散列法把这
k
个关键字存入散列表 中，至少要进行
__ k(k+1)/2__
次探测。

【西安电子科技大学
2001
软件

一、
7
（
2
分）
】

7.
执行顺序查找时，储存方式可以是
__(1)
顺序存储或链式存储
__，二分法查找时，要求线性表
__(2)_
顺序存储且有序
_
，分
块查找时要求线性表
__(3)
块内顺序存储，
块间有序
__
，
而散列表的查找，
要求线性表的存储方式是
__(4)_
散列
存储
_
。
【山
东大学
1998
一

、
1 (3
分
)
】

8.
平衡因子的定义是
_
结点的左子树的高度减去结点的右子树的高度
__
【北京轻工业学院
2000
一、
2
（
2
分）
】

9.
假设有
n
个 关键字，
它们具有相同的
Hash
函数值，
用线性探测方法解决冲突，
把这
n
个关键字散列到大小为
n
的地址空间
中，共计需要做
_
n(n+1)/2
__
次插入和探测操作。
【武汉大学
2000
一、
8
】

10.
可以唯一的标识一个记录的 关键字称为
____
主关键字
__
。
【燕山大学
1998
一、
7
（
1
分）
】

11.
已知二叉排序树的左右子树均不为空，
则
__
左子树
__
上所有结点 的值均小于它的根结点值，
_
右子树
__
上所有结点的值均大
于它的 根结点的值。
【燕山大学
1998
一、
8
（
2
分）
】

12.
动态查找表和静态查找表的 重要区别在于前者包含有
__
插入
___
和
___
删除___
运算，而后者不包含这两种运算。

【厦门大学
2001
一、
3
（
14%/5
分）】

13.
已知
N
元整型数组
a
存放
N
个学生的成绩，已按由大到小排 序，以下算法是用对分（折半）查找方法统计成绩大于或等于
X
分的学生人数，请填空使之完善 。
(C
语言）

#define N /*
学生人数
*/
int uprx(int a[N],int x ) /*
函数返回大于等于
X
分的学生人数
*/
{ int head=1,mid,rear=N;
do {mid=(head+rear)/2;
if(x<=a[mid]) __(1) rear=mid-1__ else __(2) head=mid+1__;
}while(__(3)_ head>rear _);
if (a[head]return head; }
【西南交通大学
2000
一、
12
】