数据结构 第八章 查找表 下载本文

第八章 查找表

一、选择题

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

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

2. 对N个元素的表做顺序查找时,若查找每个元素的概率相同,则平均查找长度为( )

A.(N+1)/2 B. N/2 C. N D. [(1+N)*N ]/2

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

A.N+1 B.2log2N C.logN D.N/2 E.Nlog2N F.N 4. 下面关于二分查找的叙述正确的是 ( )

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

B. 表必须有序且表中数据必须是整型,实型或字符型 D. 表必须有序,且表只能以顺序方式存储 5. 对线性表进行二分查找时,要求线性表必须( )

A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储 D.以链接方式存储,且数据元素有序 6.适用于折半查找的表的存储方式及元素排列要求为( ) A.链接方式存储,元素无序 B.链接方式存储,元素有序

C.顺序方式存储,元素无序 D.顺序方式存储,元素有序 7. 用二分(对半)查找表的元素的速度比用顺序法( )

A. 必然快 B. 必然慢 C. 相等 D. 不能确定

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

A.必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减 9. 具有12个关键字的有序表,折半查找的平均查找长度( ) A. 3.1 B. 4 C. 2.5 D. 5 10. 折半查找的时间复杂性为( )

A. O(n) B. O(n) C. O(nlog) D. O(log) 11.当采用分快查找时,数据的组织方式为 ( )

A.数据分成若干块,每块内数据有序

2

n

n

2

B.数据分成若干块,每块内数据不必有序,但块间必须有序,每块内最大(或最小)的数据组成索引块

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

12. 二叉查找树的查找效率与二叉树的( (1))有关, 在 ((2))时其查找效率最低 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 13. 要进行顺序查找,则线性表(1);要进行折半查询,则线性表(2);若表中元素个数为n,则顺序查找的平均比较次数为(3);折半查找的平均比较次数为(4)。 (1)(2):A. 必须以顺序方式存储; B. 必须以链式方式存储;

C. 既可以以顺序方式存储,也可以链式方式存储;

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

(3)(4):A.n B.n/2 C.n*n D.n*n/2 E.log2

F.nlog2 G.(n+1)/2 H.log2(n+1)

14.在等概率情况下,线性表的顺序查找的平均查找长度ASL为( (1) ),有序表的折半查找的ASL为( (2) ),对静态树表,在最坏情况下,ASL为( (3) ),而当它是一棵平衡树时,ASL为 ( (4) ),在平衡树上删除一个结点后可以通过旋转使其平衡,在最坏情况下需( (5) )次旋转。供选择的答案:

(1)(2)(3)(4)(5): A. O(1) B. O( log2 )

C. O((log2)) D.O(nlog2) E. O(n)

15. 对大小均为n的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找失败,它们的平均查找长度是((1)) ,对于查找成功,他们的平均查找长度是((2))供选择的答案:

A. 相同的 B.不同的

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

A. 分快查找 B. 顺序查找 C. 折半查找 D. 基于属性 17. 既希望较快的查找又便于线性表动态变化的查找方法是 ( )

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

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

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

n2

nn

n

n

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

19. 在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。

A. LL B. LR C. RL D. RR 20.下列关于m阶B-树的说法错误的是( )

A.根结点至多有m棵子树 B.所有叶子都在同一层次上 C. 非叶结点至少有m/2 (m为偶数)或m/2+1(m为奇数)棵子树 D. 根结点中的数据是有序的

21. 下面关于m阶B树说法正确的是( )

①每个结点至少有两棵非空子树; ②树中每个结点至多有m一1个关键字; ③所有叶子在同一层上; ④当插入一个数据项引起B树结点分裂后,树长高一层。

A. ①②③ B. ②③ C. ②③④ D. ③

22. 下面关于B和B+树的叙述中,不正确的是( )

A. B树和B+树都是平衡的多叉树。 B. B树和B+树都可用于文件的索引结构。 C. B树和B+树都能有效地支持顺序检索。 D. B树和B+树都能有效地支持随机检索。 23. m阶B-树是一棵( )

A. m叉排序树 B. m叉平衡排序树 C. m-1叉平衡排序树 D. m+1叉平衡排序树

24. 设有一组记录的关键字为{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

25. 下面关于哈希(Hash,杂凑)查找的说法正确的是( )

A.哈希函数构造的越复杂越好,因为这样随机性好,冲突小 B.除留余数法是所有哈希函数中最好的 C.不存在特别好与坏的哈希函数,要视情况而定

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

26. 若采用链地址法构造散列表,散列函数为H(key)=key MOD 17,则需 ((1)) 个链表。这些链的链首指针构成一个指针数组,数组的下标范围为 ((2))

(1) A.17 B. 13 C. 16 D. 任意 (2) A.0至17 B. 1至17 C. 0至16 D. 1至16 27. 关于杂凑查找说法不正确的有几个( )

(1)采用链地址法解决冲突时,查找一个元素的时间是相同的

(2)采用链地址法解决冲突时,若插入规定总是在链首,则插入任一个元素的时间是

相同的

(3)用链地址法解决冲突易引起聚集现象 (4)再哈希法不易产生聚集

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

28. 设哈希表长为14,哈希函数是H(key)=key,表中已有数据的关键字为15,38,61,84共四个,现要将关键字为49的结点加到表中,用二次探测再散列法解决冲突,则放入的位置是( )

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

29. 假定有k个关键字互为同义词,若用线性探测法把这k个关键字存入散列表中,至少要进行多少次探测?( )

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

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

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

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

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

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

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

(2)存放元素59需要搜索的次数是( )。

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

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

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

二、判断题

1.采用线性探测法处理散列时的冲突,当从哈希表删除一个记录时,不应将这个记录的所在位置置空,因为这会影响以后的查找。

2.在散列检索中,“比较”操作一般也是不可避免的。 3.散列函数越复杂越好,因为这样随机性好,冲突概率小. 4.哈希函数的选取平方取中法最好。

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