第九章 查找
一、 选择题
1.若查找每个记录的概率均等,则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录,其平均查找长度ASL为( C )。【北京航空航天大学 2000 一、8 (2分)】
A. (n-1)/2 B. n/2 C. (n+1)/2 D. n
2. 对N个元素的表做顺序查找时,若查找每个元素的概率相同,则平均查找长度为( A ) 【南京理工大学1998一、7(2分)】
A.(N+1)/2 B. N/2 C. N D. [(1+N)*N ]/2
3. 下面关于二分查找的叙述正确的是 ( D ) 【南京理工大学 1996 一、3 (2分)】
A. 表必须有序,表可以顺序方式存储,也可以链表方式存储 C. 表必须有序,而且只能从小到大排列
B. 表必须有序且表中数据必须是整型,实型或字符型 D. 表必须有序,且表只能以顺序方式存储
4. 对线性表进行二分查找时,要求线性表必须( B )【燕山大学 2001 一、5 (2分)】
A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储 D.以链接方式存储,且数据元素有序
5.适用于折半查找的表的存储方式及元素排列要求为( D ) 【南京理工大学 1997 一、6 (2分)】
A.链接方式存储,元素无序 B.链接方式存储,元素有序
C.顺序方式存储,元素无序 D.顺序方式存储,元素有序
6.当在一个有序的顺序存储表上查找一个数据时,即可用折半查找,也可用顺序查找,但前者比后者的查找速度( C )
A.必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减
【南京理工大学 1997 一、7 (2分)】
7.当采用分快查找时,数据的组织方式为 ( B ) 【南京理工大学 1996 一、7 (2分)】
A.数据分成若干块,每块内数据有序
B.数据分成若干块,每块内数据不必有序,但块间必须有序,每块内最大(或最小)的数据组成索引块
C. 数据分成若干块,每块内数据有序,每块内最大(或最小)的数据组成索引块
D. 数据分成若干块,每块(除最后一块外)中数据个数需相同
8. 二叉查找树的查找效率与二叉树的( (1)C)有关, 在 ((2)C)时其查找效率最低【武汉交通科技大学1996 一、2(4分)】
(1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置
(2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。
9. 要进行顺序查找,则线性表(1C);要进行折半查询,则线性表(2D);若表中元素个数为n,则顺序查找的平均比较次数为(3G);折半查找的平均比较次数为(4H)。【北方交通大学 1999 一、2 (4分)】
(1)(2):A. 必须以顺序方式存储; B. 必须以链式方式存储;C. 既可以以顺序方式存储,也可以链式方式存储;
D. 必须以顺序方式存储,且数据已按递增或递减顺序排好;
E. 必须以链式方式存储,且数据已按递增或递减的次序排好。
(3)(4):A.n B.n/2 C.n*n D.n*n/2 E.log2n F.nlog2n G.(n+1)/2 H.log2(n+1)
10.如果要求一个线性表既能较快的查找,又能适应动态变化的要求,则可采用( A)查找法。
A. 分快查找 B. 顺序查找 C. 折半查找 D. 基于属性
【西安电子科技大学 2001应用 一、8 (2分)】
11. 既希望较快的查找又便于线性表动态变化的查找方法是 ( C ) 【北方交通大学 2000 二、4 (2分)】
A.顺序查找 B. 折半查找 C. 索引顺序查找 D. 哈希法查找
12.分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是( C ) 【合肥工业大学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分)】地址是( D)。
A. 8 B. 9 C. 10 D. 11
(2)存放元素59需要搜索的次数是( C )。
A. 2 B. 3 C. 4 D. 5
14. 将10个元素散列到100000个单元的哈希表中,则( C )产生冲突。【北京邮电大学 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的链中有( D)个记录。【南京理工大学 1997 一、4 (2分)】
A.1 B. 2 C. 3 D. 4
16. 下面关于哈希(Hash,杂凑)查找的说法正确的是( C ) 【南京理工大学 1998 一、10 (2分)】
A.哈希函数构造的越复杂越好,因为这样随机性好,冲突小
B.除留余数法是所有哈希函数中最好的
C.不存在特别好与坏的哈希函数,要视情况而定
D.若需在哈希表中删去一个元素,不管用何种方法解决冲突都只要简单的将该元素删去即可
17. 若采用链地址法构造散列表,散列函数为H(key)=key MOD 17,则需 ((1)A) 个链表。这些链的链首指针构成一个指针数组,数组的下标范围为 ((2)C) 【南京理工大学 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%11,表中已有数据的关键字为15,38,61,84共四个,现要将关键字为49的结点加到表中,用二次探测再散列法解决冲突,则放入的位置是( D ) 【南京理工大学 2001 一、15 (1.5分)】
A.8 B.3 C.5 D.9
19. 假定有k个关键字互为同义词,若用线性探测法把这k个关键字存入散列表中,至少要进行多少次探测?( D )
A.k-1次 B. k次 C. k+1次 D. k(k+1)/2次
【中国科技大学 1998 二、3 (2分)】【中科院计算所1998 二、3 (2分)】
20. 哈希查找中k个关键字具有同一哈希值,若用线性探测法将这k个关键字对应的记录存入哈希表中,至少要进行( C )次探测。【西安电子科技大学 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,需做的关键码比较次数为_4__.
【北方交通大学 2001 二、2】
2. 给定一组数据{6,2,7,10,3,12}以它构造一棵哈夫曼树,则树高为__5_____,带权路径长度WPL的值为___96_____。
【南京理工大学 1997 三、4 (2分)】
3. 己知有序表为(12,18,24,35,47,50,62,83,90,115,134)当用二分法查找90时,需____2____次查找成功,47时____4____成功,查100时,需___3_____次才能确定不成功。【南京理工大学 2000 二、7 (4.5分)】
4. 平衡二叉树又称__ AVL树(高度平衡树,高度平衡的二叉排序树),____,其定义是_或为空二叉树,或二叉树中任意结点左子树高度与右子树高度差的绝对值小于等于1__。【青岛大学 2001 六、3 (3分)】
5. 在哈希函数H(key)=key%p中,p值最好取_小于等于表长的最大素数或不包含小于20的质因子的合数__。【青岛大学 2002 三、9 (2分)】
6.假定有k个关键字互为同义词,若用线性探测再散列法把这k个关键字存入散列表中,至少要进行__ k(k+1)/2__次探测。
【西安电子科技大学2001软件 一、7 (2分)】
7. 执行顺序查找时,储存方式可以是__(1) 顺序存储或链式存储__,二分法查找时,要求线性表__(2)_顺序存储且有序_,分块查找时要求线性表 __(3) 块内顺序存储,块间有序__,而散列表的查找,要求线性表的存储方式是 __(4)_ 散列存储_。【山东大学 1998 一 、1 (3分)】
8. 平衡因子的定义是_结点的左子树的高度减去结点的右子树的高度__【北京轻工业学院 2000、2 (2分)】
9. 假设有n个关键字,它们具有相同的Hash函数值,用线性探测方法解决冲突,把这n个关键字散列到大小为n的地址空间中,共计需要做_ n(n+1)/2 __次插入和探测操作。【武汉大学 2000、8】
10. 可以唯一的标识一个记录的关键字称为____主关键字__。【燕山大学 1998 一、7 (1分)】
11. 已知二叉排序树的左右子树均不为空,则__左子树__上所有结点的值均小于它的根结点值,_右子树__上所有结点的值均大于它的根结点的值。【燕山大学 1998 一、8 (2分)】
12. 动态查找表和静态查找表的重要区别在于前者包含有__插入___和___删除___运算,而后者不包含这两种运算。
【厦门大学 2001 一、3 (14%/5分)】
13. 已知N元整型数组a存放N个学生的成绩,已按由大到小排序,以下算法是用对分(折半)查找方法统计成绩大于或等于X分的学生人数,请填空使之完善。(C语言)
#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) rear=mid-1__ else __(2) head=mid+1__;
}while(__(3)_ head>rear _);
if (a[head]
return head; } 【西南交通大学 2000 、12】
四、应用题
1. 设有一组关键字{9,01,23,14,55,20,84,27},采用哈希函数:H(key)=key mod 7 ,表长为10,用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=12,22,32,…,)解决冲突。要求:对该关键字序列构造哈希表。【东北大学 2002 二 、2 (5分)】
散列地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
关键字 | 14 | 01 | 9 | 23 | 84 | 27 | 55 | 20 | ||
比较次数 | 1 | 1 | 1 | 2 | 3 | 4 | 1 | 2 | ||
平均查找长度:ASLsucc=(1+1+1+2+3+4+1+2)/8=15/8
以关键字27为例:H(27)=27%7=6(冲突) H1=(6+1)%10=7(冲突)
H2=(6+22)%10=0(冲突) H3=(6+33)%10=5 所以比较了4次。
2. 对下面的关键字集{30,15,21,40,25,26,36,37}若查找表的装填因子为0.8,采用线性探测再散列方法解决冲突,做:
(1)设计哈希函数; (2)画出哈希表;
【东北大学 2001 六 (18分)】
由于装填因子为0.8,关键字有8个,所以表长为8/0.8=10。
(1)用除留余数法,哈希函数为H(key)=key % 7
(2)
散列地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
关键字 | 21 | 15 | 30 | 36 | 25 | 40 | 26 | 37 | ||
比较次数 | 1 | 1 | 1 | 3 | 1 | 1 | 2 | 6 | ||
3. 设哈希表a 、b分别用向量a[0..9],b[0..9]表示 ,哈希函数均为H(key)=key MOD 7,处理冲突使用开放定址法,Hi=[H(key)+Di]MOD 10,在哈希表a中Di用线性探测再散列法,在哈希表b中Di用二次探测再散列法,试将关键字{19,24, 10,17,15,38,18,40}分别填入哈希表a,b中
哈希表a:
散列地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
关键字 | 15 | 24 | 10 | 19 | 17 | 38 | 18 | 40 | ||
比较次数 | 1 | 1 | 2 | 1 | 4 | 5 | 5 | 5 | ||
哈希表b:
散列地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
关键字 | 15 | 17 | 24 | 10 | 19 | 40 | 38 | 18 | ||
比较次数 | 1 | 3 | 1 | 2 | 1 | 2 | 4 | 4 | ||
4. 设一组数据为{1,14,27,29,55,68,10,11,23},现采用的哈希函数是H(key)=key MOD 13, 即关键字对13取模,冲突用链地址法解决,设哈希表的大小为13(0..12),试画出插入上述数据后的哈希表。【南京理工大学 1996 三、3 (5分)】
5. 设哈希函数H(k)=3 K mod 11,散列地址空间为0~10,对关键字序列(32,13,49,24,38,21,4,12)按下述两种解决冲突的方法构造哈希表(1)线性探测再散列(2)链地址法,
(1)
散列地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
关键字 | 4 | 12 | 49 | 38 | 13 | 24 | 32 | 21 | |||
比较次数 | 1 | 1 | 1 | 2 | 1 | 2 | 1 | 2 | |||
6. 使用散列函数hashf(x)=x mod 11,把一个整数值转换成散列表下标,现要把数据:1,13,12,34,38,33,27,22插入到散列表中。 (1)使用线性探查再散列法来构造散列表。(5分) (2)使用链地址法构造散列表。(5分)
由hashf(x)=x mod 11 可知,散列地址空间是0到10,由于有8个数据,装载因子取0.7。
(1)
散列地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
关键字 | 33 | 1 | 13 | 12 | 34 | 38 | 27 | 22 | |||
比较次数 | 1 | 1 | 1 | 3 | 4 | 1 | 2 | 8 | |||
7. 设散列函数为H(K)=K MOD 13,给定的键值序列为13,41,15,44,06,68,12,25,38,64,19,49,画出用链地址法处理冲突构造得的哈希表。【福州大学 1998 三、3 (6分)】
8. 已知散列表的地址空间为A[0..11],散列函数H(k)=k mod 11,采用线性探测法处理冲突。请将下列数据{25,16,38,47,79,82,51,39,89,151,231}依次插入到散列表中,并计算出在等概率情况下查找成功时的平均查找长度。
【合肥工业大学 2000 四、3 (5分)】
散列地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
关键字 | 231 | 89 | 79 | 25 | 47 | 16 | 38 | 82 | 51 | 39 | 151 | |
比较次数 | 1 | 1 | 1 | 1 | 2 | 1 | 2 | 3 | 2 | 4 | 3 | |
ASLsucc =21/11
9. 设输入的关键字序列为:22,41,53,33,46,30,13,01,67, Hash函数为:H(key)=key MOD 11。HASH表长度为11。试用线性探测法解决冲突,将各关键字按输入顺序填入Hash表中。【南京航空航天大学 1998 二 (10分)】
散列地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
关键字 | 22 | 33 | 46 | 13 | 01 | 67 | 41 | 53 | 30 | ||
比较次数 | 1 | 2 | 1 | 2 | 4 | 5 | 1 | 1 | 3 | ||
10. 已知关键字序列R={11,4,3,2,17,30,19},请按算法步骤:【北方交通大学 1996 四】
(1)构造一棵哈夫曼树,并计算出它的带权路径长度WPL(7分)
11. 按下述次序输入关键字:e,i,p,k,,m,l,b,试画出AVL树的构造与调整过程。(要求画出每插入一个关键字检索树的形状及调整后的结果)。【山东大学 1992 一 、5 (3分)】
12. 试画出从空树开始,由字符序列(t,d,e,s,u,g,b,j,a,k,r,i)构成的二叉平衡树,并为每一次的平衡处理指明旋转类型。
【清华大学 1994 三 (10分)】
13. 如图2所示是一棵正在进行插入运算的AVL树,关键码70的插入使它失去平衡,按照AVL树的插入方法,需要对它的结构进行调整以恢复平衡。
(1) 请画出调整后的AVL树。
.
14. 在查找和排序算法中,监视哨的作用是什么?【长沙铁道学院 1997 三、3 (3分)】
监视哨的作用是免去查找过程中每次都要检测整个表是否查找完毕,提高了查找效率。
五.算法设计题
1.设从键盘输入一个整数的序列:n,a1,a2,…,an,其中n表示连续输入整数的个数。(10分)。
试编写一程序按整数值建立一个二叉排序树。
(1)非递归建立二叉排序树,在二叉排序树上插入的结点都是叶子结点。
void Creat_BST(BiTree bst,datatype K[],int n)
// 以存储在数组K中的n个关键字,建立一棵初始为空的二叉排序树。
{for(i=1;i≤n;i++)
{p=bst;f=null;//在调用Creat_BST时,bst=null
while(p!=null)
if(p->data
else if(p->data>K[i]){ f=p;p=p->LLINK;}
s=(BiTree)malloc(sizeof (BiNode));// 申请结点空间
s->data=K[i];s->LLINK=null;s->RLINK=null;
if(f==null)bst=s; //根结点
else if(s->data
else f->RLINK=s;//右子树根结点的值大于等于根结点的值
}//算法结束
本文来源:https://www.2haoxitong.net/k/doc/291f0e5a185f312b3169a45177232f60ddcce7c1.html
文档为doc格式