数据结构第9章例题与答案

文章作者 100test 发表时间 2007:03:10 18:19:13
来源 100Test.Com百考试题网

第九章 集合
一、 选择题
1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度asl为( )。【北京航空航天大学 2000 一、8 （2分）】
a． (n-1)/2 b. n/2 c. (n 1)/2 d. n
2. 对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) 【南京理工大学1998一、7（2分）】
a．（n 1）/2 b. n/2 c. n d. [（1 n）*n ]/2
3．顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（（1））,二分法查找只适用于查找顺序存储的有序表，平均比较次数为（（2））。 在此假定n为线性表中结点数，且每次查找都是成功的。【长沙铁道学院 1997 四、3 (4分)】
a.n 1 b.2log2n c.logn d.n/2 e.nlog2n f.n2
4. 下面关于二分查找的叙述正确的是 ( ) 【南京理工大学 1996 一、3 （2分）】
a. 表必须有序，表可以顺序方式存储，也可以链表方式存储 c. 表必须有序，而且只能从小到大排列
b. 表必须有序且表中数据必须是整型，实型或字符型 d. 表必须有序，且表只能以顺序方式存储
5. 对线性表进行二分查找时，要求线性表必须（ ）【燕山大学 2001 一、5 （2分）】
a.以顺序方式存储 b.以顺序方式存储,且数据元素有序 c.以链接方式存储 d.以链接方式存储,且数据元素有序
6．适用于折半查找的表的存储方式及元素排列要求为( ) 【南京理工大学 1997 一、6 （2分）】
a．链接方式存储，元素无序 b．链接方式存储，元素有序
c．顺序方式存储，元素无序 d．顺序方式存储，元素有序
7. 用二分（对半）查找表的元素的速度比用顺序法( ) 【南京理工大学 1998 一、11 （2分）】
a． 必然快 b. 必然慢 c. 相等 d. 不能确定
8．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( )
a．必定快 b.不一定 c. 在大部分情况下要快 d. 取决于表递增还是递减
【南京理工大学 1997 一、7 （2分）】
9. 具有12个关键字的有序表，折半查找的平均查找长度（ ）【中山大学 1998 二、10 （2分）】
a. 3.1 b. 4 c. 2.5 d. 5
10. 折半查找的时间复杂性为（ ）【中山大学 1999 一、15】
a. o（n2） b. o（n） c. o（nlogn） d. o（logn）
11．当采用分快查找时，数据的组织方式为 ( ) 【南京理工大学 1996 一、7 （2分）】
a．数据分成若干块，每块内数据有序
b．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
c. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
d. 数据分成若干块，每块（除最后一块外）中数据个数需相同
12. 二叉查找树的查找效率与二叉树的( （1）)有关, 在 (（2）)时其查找效率最低【武汉交通科技大学1996 一、2(4分)】
(1): a. 高度 b. 结点的多少 c. 树型 d. 结点的位置
(2): a. 结点太多 b. 完全二叉树 c. 呈单枝树 d. 结点太复杂。
13. 要进行顺序查找，则线性表（1）；要进行折半查询，则线性表（2）；若表中元素个数为n,则顺序查找的平均比较次数为（3）；折半查找的平均比较次数为（4）。【北方交通大学 1999 一、2 （4分）】
（1）（2）：a. 必须以顺序方式存储； b. 必须以链式方式存储；c. 既可以以顺序方式存储，也可以链式方式存储；
d. 必须以顺序方式存储，且数据已按递增或递减顺序排好；
e. 必须以链式方式存储，且数据已按递增或递减的次序排好。
（3）（4）：a.n b.n/2 c.n*n d.n*n/2 e.log2n f.nlog2n g.(n 1)/2 h.log2(n 1)