数据结构第8章查找练习题

数据结构查找部分练习题

一、单选题

1．下列查找方法中，不属于动态的查找方法是( )。

A．二叉排序树法 B．平衡树法 C．散列法 D．二分查找法

2．适用于静态的查找方法为( )。

A．二分查找、二叉排序树查找 B．二分查找、索引顺序表查找

C．二叉排序树查找、索引顺序表查找 D．二叉排序树查找、散列法查找

3．静态查找表与动态查找表二者的根本差别在于( )。

A．它们的逻辑结构不一样 B．施加在其上的操作不同

C．所包含的数据元素的类型不一样 D．存储实现不一样

4．对长度为10的顺序表进行查找，若查找前面5个元素的概率相同，均为1/8，查找后面5个元素的概率相同，均为3/40，则查找任一元素的平均查找长度为( )。

A．5.5 B．5 C．39/8 D．19/4

5．( )存储方式适用于折半查找。

A．键值有序的单链表 B．键值有序的顺序表

C．键值有序的双链表 D．键值无序的顺序表

6．对线性表进行二分查找时，要求线性表必须( )。

A．以顺序方式存储 B．以链接方式存储

C．顺序存储，且结点按关键字有序排序 D．链式存储，且结点按关键字有序排序

7．在索引顺序表中查找一个元素，可用的且最快的方法是( )。

A．用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找

B．用顺序查找法确定元素所在块，再用二分查找法在相应块中查找

C．用二分查找法确定元素所在块，再用顺序查找法在相应块中查找

D．用二分查找法确定元素所在块，再用二分查找法在相应块中查找

8．在索引查找中，若主表长度为144，它被均分为12子表，每个子表的长度均为12，则索引查找的平均查找长度为( )。

A．13 B．24 C．12 D．79

9．由同一关键字集合构造的各棵二叉排序树( )。

A．形态和平均查找长度都不一定相同

B．形态不一定相同，但平均查找长度相同

C．形态和平均查找长度都相同

D．形态相同，但平均查找长度不一定相同

10．对二叉排序树进行( )，可以得到各结点键值的递增序列。

A．先根遍历 B．中根遍历 C．层次遍历 D．后根遍历

11．下述序列中，哪个可能是在二叉排序树上查找35时所比较过的关键字序列？

A．2，25，40，39，53，34，35 B．25，39，2，40，53，34，35

C．53，40，2，25，34，39，35 D．39，25，40，53，34，2，35

12．在AVL树中，每个结点的平衡因子的取值范围是( )。

A．-1 1 B．-2 2 C．1 2 D．0 1

13．在AVL树中，任一结点的( )。

A．左、右子树的高度均相同 B．左、右子树高度差的绝对值不超过1

C．左、右子树的结点数均相同 D．左、右子树结点数差的绝对值不超过1

+14．下面关于B树和B树的叙述中，不正确的是

A．都是平衡的多叉树 B．都是可用于文件的索引结构

28C．都能有效地支持顺序检索 D15．右图是一棵( )。

05101519222628