查找习题_数据结构

习题八查找

一、单项选择题

1．顺序查找法适合于存储结构为（ ）的线性表。

A．散列存储 B. 顺序存储或链式存储 C. 压缩存储 D. 索引存储 2.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。个人收集整理 勿做商业用途 A． (n-1)/2 B. n/2 C. (n+1)/2 D. n个人收集整理 勿做商业用途 3．适用于折半查找的表的存储方式及元素排列要求为( )

A．链接方式存储，元素无序 B．链接方式存储，元素有序

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

4．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( ) 个人收集整理 勿做商业用途 A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减 5．当采用分块查找时，数据的组织方式为 ( )

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

B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块

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

6．二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法（ ）。个人收集整理 勿做商业用途 A．正确 B. 错误

7. 二叉查找树的查找效率与二叉树的(（1） )有关, 在 (（2） )时其查找效率最低。 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置个人收集整理 勿做商业用途 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。

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

A. 分快查找 B. 顺序查找 C. 折半查找 D. 基于属性

9．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )。

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)

个人收集整理 勿做商业用途 10．下图所示的4棵二叉树,( )是平衡二叉树。

（A） （B） （C） （D）个人收集整理 勿做商业用途 11．散列表的平均查找长度（ ）。

A． 与处理冲突方法有关而与表的长度无关 B． 与处理冲突方法无关而与表的长度有关 C． 与处理冲突方法有关且与表的长度有关 D． 与处理冲突方法无关且与表的长度无关

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

13. 关于杂凑查找说法不正确的有几个( ) （1）采用链地址法解决冲突时，查找一个元素的时间是相同的

（2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同

的

1 / 5

个人收集整理 仅供参考学习

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

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

14. 设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( ) 个人收集整理 勿做商业用途 A．8 B．3 C．5 D．9

15. 将10个元素散列到100000个单元的哈希表中，则（）产生冲突。

A. 一定会 B. 一定不会 C. 仍可能会 二、填空题

1. 顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为__ __次；当使用监视哨时，若查找失败，则比较关键字的次数为__ __。个人收集整理 勿做商业用途 2. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为____.个人收集整理 勿做商业用途 3．一个无序序列可以通过构造一棵_ _ _ _树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。个人收集整理 勿做商业用途 4. 哈希表是通过将查找码按选定的____和 ____，把结点按查找码转换为地址进行存储的线性表。哈希方法的关键是___和 ____。一个好的哈希函数其转换地址应尽可能____，而且函数运算应尽可能____。个人收集整理 勿做商业用途 5. 平衡二叉树又称__________，其定义是__________。

6. 在哈希函数H（key）=key%p中，p值最好取__________。

7．假定有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入散列表中，至少要进行__________次探测。个人收集整理 勿做商业用途 8. __________法构造的哈希函数肯定不会发生冲突。

9. 动态查找表和静态查找表的重要区别在于前者包含有__________和__________运算，而后者不包含这两种运算。个人收集整理 勿做商业用途 10．在散列存储中，装填因子α的值越大，则____；α的值越小，则____。

11. 已知N元整型数组a存放N个学生的成绩，已按由大到小排序，以下算法是用对分（折半）查找方法统计成绩大于或等于X分的学生人数，请填空使之完善。个人收集整理 勿做商业用途 #define N /*学生人数*/

int uprx(int a[N],int x ) /*函数返回大于等于X分的学生人数*/ { int head=1,mid,rear=N; do {mid=(head+rear)/2;

if(x<=a[mid]) __(1)__ else __(2)__; }while(__(3)__);

if (a[head]1．HASH方法的平均查找路长决定于什么？是否与结点个数N有关？ 处理冲突的方法主要有哪些？

2. 设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表

222

长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=1,2,3,…,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。个人收集整理 勿做商业用途 3. 选取哈希函数Ｈ（key）=key mod 7,用链地址法解决冲突。试在０-６的散列地址空间内对关键字序列｛31,23,17,27,19,11,13,91,61,41｝构造哈希表，并计算在等概率下成功查找的平均查找长度。个人收集整理 勿做商业用途 4. 输入一个正整数序列（53,17,12,66,58,70,87,25,56,60），试完成下列各题。个人收集整理 勿做商业用途 （1） 按次序构造一棵二叉排序树BS。

2 / 5

个人收集整理 仅供参考学习

（2） 依此二叉排序树，如何得到一个从大到小的有序序列？ （3） 画出在此二叉排序树中删除“66”后的树结构。

5. 直接在二叉排序树中查找关键字K与在中序遍历输出的有序序列中查找关键字K，其效率是否相同？输入关键字有序序列来构造一棵二叉排序树，然后对此树进行查找，其效率如何？为什么？ 个人收集整理 勿做商业用途 6. 一棵二叉排序树结构如下,各结点的值从小到大依次为1-9，请标出各结点的值。

7. 假定对有序表：(3,4,5,7,24,30,42,,63,72,87,95)进行折半查找，试回答下列问题：

个人收集整理 勿做商业用途 (1).画出描述折半查找过程的判定树；

(2).若查找元素，需依次与那些元素比较? (3).若查找元素90，需依次与那些元素比较?

(4).假定每个元素的查找概率相等，求查找成功时的平均查找长度。 四、算法设计题

1. 设记录R1,R2,…,Rn按关键字值从小到大顺序存储在数组r[1..n]中,在r[n+1]处设立一个监督哨,其关键字值为+∞; 试写一查找给定关键字k 的算法;并画出此查找过程的判定树,求出在等概率情况下查找成功时的平均查找长度。个人收集整理 勿做商业用途 2．试编写算法求出指定结点在给定的二叉排序树中所在的层数。

3. 写出在二叉排序树中删除一个结点的算法，使删除后仍为二叉排序树。设删除结点由指针p所指，其双亲结点由指针f所指，并假设被删除结点是其双亲结点的右孩子。个人收集整理 勿做商业用途 第九章查找

一、单项选择题 1．B 2．C 3．D 4．C 5．B 6．B 7. C C 8．A 9．C 10．B 11．A 12. D 13. B 14. D 15. C

二、填空题 1. n n+1 2. 4

3． 二叉排序

4. (1)哈希函数(2)解决冲突的方法 (3)选择好的哈希函数 (4)处理冲突的方法 (5)均匀(6)简单个人收集整理 勿做商业用途 5. AVL树（高度平衡树，高度平衡的二叉排序树）

或为空二叉树，或二叉树中任意结点左子树高度与右子树高度差的绝对值小于等于1。 6. 小于等于表长的最大素数或不包含小于20的质因子的合数 7．k(k+1)/2 8. 直接定址法 9. 插入删除

10． 存取元素时发生冲突的可能性就越大 存取元素时发生冲突的可能性就越小 11．(1)rear=mid-1 (2)head=mid+1 (3)head>rear

3 / 5

个人收集整理 仅供参考学习

三、应用题

1．哈希方法的平均查找路长主要取决于负载因子（表中实有元素数与表长之比），它反映了哈希表的装满程度，该值一般取0.65~0.9。个人收集整理 勿做商业用途 散列表存储中解决碰撞的基本方法：

①开放定址法形成地址序列的公式是：Hi=（H（key）+di）% m，其中m是表长，di是增量。根据di取法不同，又分为三种：个人收集整理 勿做商业用途 a．di =1，2，…，m-1 称为线性探测再散列，其特点是逐个探测表空间，只要散列表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一散列地址。个人收集整理 勿做商业用途 22222

b．di =1，-1，2，-2，…，k（k≤m/2） 称为二次探测再散列，它减少了聚集，但不容易探测到全部表空间，只有当表长为形如4j+3（j为整数）的素数时才有可能。个人收集整理 勿做商业用途 c．di =伪随机数序列，称为随机探测再散列。

②再散列法 Hi=RHi（key） i=1，2，…，k，是不同的散列函数，即在同义词产生碰撞时，用另一散列函数计算散列地址，直到解决碰撞。该方法不易产生“聚集”，但增加了计算时间。个人收集整理 勿做商业用途 ③链地址法将关键字为同义词的记录存储在同一链表中，散列表地址区间用H[0..m-1]表示，分量初始值为空指针。凡散列地址为i（0≤i≤m-1）的记录均插在以H[i]为头指针的链表中。这种解决方法中数据元素个数不受表长，插入和删除操作方便，但增加了指针的空间开销。这种散列表常称为开散列表，而①中的散列表称闭散列表，含义是元素个数受表长。个人收集整理 勿做商业用途 ④建立公共溢出区设H[0..m-1]为基本表，凡关键字为同义词的记录，都填入溢出区 O[0..m-1]。 2．

散列地址 0 关键字 14 比较次数 1 1 01 1 2 9 1 3 23 2 4 84 5 27 6 55 1 7 20 2 8 9 3 4 平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8

以关键字27为例：H（27）=27%7=6（冲突） H1=（6+1）%10=7（冲突）

23

H2=（6+2）%10=0（冲突） H3=（6+3）%10=5 所以比较了4次。 3. 表略

ASLsucc =15/10 4. 略

5. 在二叉排序树上查找关键字K，走了一条从根结点至多到叶子的路径，时间复杂度是O(logn)，而在中序遍历输出的序列中查找关键字K，时间复杂度是O（n）。按序输入建立的二叉排序树，蜕变为单枝树，其平均查找长度是（n+1）/2，时间复杂度也是O（n）。个人收集整理 勿做商业用途 6. 略 7. 略

四、算法设计题

1. int Search（rectype r[ ]，int n，keytype k）

//在n个关键字从小到大排列的顺序表中，查找关键字为k的结点。 {r[n+1].key=MAXINT；//在高端设置监视哨 i=1；

while（r[i].keyif (r[n+1].key==k) return （i%（n+1））；

4 / 5

个人收集整理 仅供参考学习

else return (0) }//算法search结束

查找过程的判定树是单枝树，限于篇幅不再画出。本题中虽然表按关键字有序，但进行顺序查找，查找成功的平均查找长度亦为（n+1）/2。个人收集整理 勿做商业用途 2．解答：．分析：采用递归方法，从根结点开始查找结点p，若查询结点是所要找的结点，返回其深度h0。否则，到左、右子树上去找，查找深度加1。个人收集整理 勿做商业用途 int find1 ( birtreptr T , p , int h0 )

/*在二叉树排序树T中查找结点p的层次，若不在时返回空值。h0为根结点T的层次*/

{ if ( p == NULL ) return ( 0 ) ; /* 没找到，返回0 */个人收集整理 勿做商业用途 if( p ==T) return( h0 ) ; /* 找到 */个人收集整理 勿做商业用途 else if (p -> data < T -> data ) return( find1( T ->lchild,p,h0) +1) ; /* 到左子树去找 */个人收集整理 勿做商业用途 else return ( find1 ( T -> rchild,p,h0) + 1); /* 到右子树去找 */个人收集整理 勿做商业用途 }

int find2( birtrptr T, p ) { return ( find1 ( T, p,1 ) ) ; }个人收集整理 勿做商业用途 3. void Delete（BSTree t，p）

// 在二叉排序树t中，删除f所指结点的右孩子（由p所指向）的算法 {if（p->lchild==null）{f->rchild=p->rchild；free（p）；} //p无左子女个人收集整理 勿做商业用途 else //用p左子树中的最大值代替p结点的值 {q=p->lchild；s=q；

while（q->rchild）{s=q；q=q->rchild ；}//查p左子树中序序列最右结点 if（s==p->lchild） //p左子树的根结点无右子女

{p->data=s->data；p->lchild=s->lchild；free（s）；} else{p->data=q->data；s->rchild=q->lchild；free（q）；} }

}//Delete

5 / 5