数据结构C语言版查找练习题.pdfVIP

数据结构C语言版查找练习题

第8章查找

一选择题

1．若查找每个记录的概率均等，则在具有n个记录的连续顺序文

件中采用顺序查找法查找一个记录，其平均查找长度ASL为（）

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

2．在一个有N个元素的有序单链表中查找具有给定关键字的结点，

平均情况下的时间复杂性为（）A．O(1)B．O(N)C．O(N2)

D．O(NlogN)

3．顺序查找法适用于查找顺序存储或链式存储的线性表，平均比

较次数为（），二分法查找只适用于查找顺序存储的有序表，平均比

较次数为（）。在此假定N为线性表中结点数，且每次查找都是成功

的。

A．N+1B．2log2NC．logND．N/2E．Nlog2NF．N2

4．下面关于二分查找的叙述正确的是（）

A．表必须有序，表可以顺序方式存储，也可以链表方式存储

B．表必须有序且表中数据必须是整型，实型或字符型

C．表必须有序，而且只能从小到大排列

D．表必须有序，且表只能以顺序方式存储

5．将两个各有n个元素的有序表归并成一个有序表，其最多的比

较次数是（）

A．2nB．nC．2n-1

8．当在一个有序的顺序存储表上查找一个数据时，即可用折半查

找，也可用顺序查找，但前者比后者的查找速度（）

A．必定快B．不一定C．在大部分情况下要快D．取决于表递增

还是递减

9．具有12个关键字的有序表，折半查找的平均查找长度（）

A．3.1B．4C．2.5D．5

10．折半查找的时间复杂性为（）

A．O（n2）B．O（n）C．O（nlogn）D．O（logn）

13．对表长为n的有序表进行折半查找，其判定树高度为（）

A．?log2(n+1)?B．?log2(n+1)?C．?log2n?D．?log2n?

15．对大小均为n的有序表和无序表分别进行顺序查找，在等概

率查找的情况下，对于查找失败，它们的平均查找长度是（），对于

查找成功，他们的平均查找长度是（）

A．相同的B．不同的

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)D．(100，80，60，

90，120，130，110)

19．在平衡二叉树中插入一个结点后造成了不平衡，设最低的不

平衡结点为A，并已知A的左孩子的平衡因子为0右孩子的平衡因子

为1，则应作（）型调整以使其平衡。

A．LLB．LRC．RLD．RR

27．设有一组记录的关键字为{19，14，23，1，68，20，84，

27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）

=keyMOD13，散列地址为1的链中有（）个记录。

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

28．下面关于哈希(Hash，杂凑)查找的说法正确的是（）

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

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

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

D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只

要简单的将该元素删去即可

29．若采用链地址法构造散列表，散列函数为H（key）=key

MOD17