习题第九章查找(1)

第九章 查找

一、 选择题

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. 下面关于二分查找的叙述正确的是 ( ) 【南京理工大学 1996 一、3 （2分）】

A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列 B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储 4. 对线性表进行二分查找时，要求线性表必须（ ）【燕山大学 2001 一、5 （2分）】

A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储 D.以链接方式存储,且数据元素有序 5．适用于折半查找的表的存储方式及元素排列要求为( ) 【南京理工大学 1997 一、6 （2分）】 A．链接方式存储，元素无序 B．链接方式存储，元素有序

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

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

A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减 【南京理工大学 1997 一、7 （2分）】

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

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

B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块 C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D. 数据分成若干块，每块（除最后一块外）中数据个数需相同

8. 二叉查找树的查找效率与二叉树的( （1） )有关, 在 (（2） )时其查找效率最低【武汉交通科技大学1996 一、2(4分)】 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 9. 要进行顺序查找，则线性表（1 ）；要进行折半查询，则线性表（2 ）；若表中元素个数为n,则顺序查找的平均比较次数为（3 ）；折半查找的平均比较次数为（4H）。【北方交通大学 1999 一、2 （4分）】 （1）（2）：A. 必须以顺序方式存储； B. 必须以链式方式存储；C. 既可以以顺序方式存储，也可以链式方式存储；

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

nn

（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) 10．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( )查找法。

A. 分快查找 B. 顺序查找 C. 折半查找 D. 基于属性 【西安电子科技大学 2001应用 一、8 （2分）】

11. 既希望较快的查找又便于线性表动态变化的查找方法是 ( ) 【北方交通大学 2000 二、4 （2分）】 A．顺序查找 B. 折半查找 C. 索引顺序查找 D. 哈希法查找

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

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)

13. 散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，

18，59依次存储到散列表中。

（1）元素59存放在散列表中的【北方交通大学 2001 一、（19，20） （4分）】地址是（ ）。

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

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

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

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

A. 一定会 B. 一定不会 C. 仍可能会 15. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（ ）个记录。【南京理工大学 1997 一、4 （2分）】

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

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

A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B．除留余数法是所有哈希函数中最好的

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

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

17. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需 (（1） ) 个链表。这些链的链首指针构成一个指

针数组，数组的下标范围为 (（2） ) 【南京理工大学 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,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结

点加到表中，用二次探测再散列法解决冲突，则放入的位置是( ) 【南京理工大学 2001 一、15 （1.5分）】

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

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

A．k-1次 B. k次 C. k+1次 D. k（k+1）/2次 【中国科技大学 1998 二、3 （2分）】【中科院计算所1998 二、3 （2分）】

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

次探测。【西安电子科技大学 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，需做的关键码比较次数为_ __.

【北方交通大学 2001 二、2】

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

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

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

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

【西安电子科技大学2001软件 一、7 （2分）】

5. 平衡因子的定义是_ __【北京轻工业学院 2000 一、2 （2分）】

6. 假设有n个关键字，它们具有相同的Hash函数值，用线性探测方法解决冲突，把这n个关键字散列到大小为n的地址空间中，共计需要做_ __次插入和探测操作。【武汉大学 2000 一、8】 7. 可以唯一的标识一个记录的关键字称为____ __。【燕山大学 1998 一、7 （1分）】

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

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

三、应用题

1. 设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长为10，用开放地址法的二次探测

222

再散列方法Hi=(H(key)+di) mod 10(di=1,2,3,…,)解决冲突。要求：对该关键字序列构造哈希表。【东北大学 2002 二 、2 （5分）】

2. 对下面的关键字集{30,15,21,40,25,26,36,37}若查找表的装填因子为0.8，采用线性探测再散列方法解决冲突，做： （1）设计哈希函数； （2）画出哈希表； 【东北大学 2001 六 (18分)】

由于装填因子为0.8，关键字有8个，所以表长为8/0.8=10。

3. 设哈希函数H（k）=3 K mod 11，散列地址空间为0～10，对关键字序列（32,13,49,24,38,21,4,12）按下述两种解决冲突的方法构造哈希表（1）线性探测再散列（2）链地址法，

4. 使用散列函数hashf(x)=x mod 11,把一个整数值转换成散列表下标，现要把数据：1,13,12,34,38,33,27,22插入到散列表中。 （1）使用线性探查再散列法来构造散列表。（5分） （2）使用链地址法构造散列表。（5分）

5. 设输入的关键字序列为：22,41,53,33,46,30,13,01,67, Hash函数为：H（key）=key MOD 11。HASH表长度为11。试用线性探测法解决冲突，将各关键字按输入顺序填入Hash表中。【南京航空航天大学 1998 二 （10分）】

6. 已知关键字序列R={11,4,3,2,17,30,19}，请按算法步骤：【北方交通大学 1996 四】 （1）构造一棵哈夫曼树，并计算出它的带权路径长度WPL（7分） 7. 按下述次序输入关键字：e,i,p,k,,m,l,b,试画出AVL树的构造与调整过程。（要求画出每插入一个关键字检索树的形状及调整后的结果）。【山东大学 1992 一 、5 (3分)】

8. 试画出从空树开始，由字符序列(t,d,e,s,u,g,b,j,a,k,r,i)构成的二叉平衡树，并为每一次的平衡处理指明旋转类型。

【清华大学 1994 三 （10分）】

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库习题第九章查找(1)在线全文阅读。