《数据结构与算法》第九章-查找.docx

《《数据结构与算法》第九章-查找.docx》由会员分享，可在线阅读，更多相关《《数据结构与算法》第九章-查找.docx（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构与算法第九章 查找答案第二部分考研真题精选一、选择题.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一 个记录，其平均查找长度ASL为（）oA. （n-l）/2 B. n/2 C. （n+l）/2 D. n.对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（）A. （N+l） /2B.N/2 C.N D. （1+N） *N /2.顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（1）,二分法查 找只适用于查找顺序存储的有序表，平均比较次数为（2）。在此假定N为线性表中结点数，且每次查找都是成功的。D.N/2 E.Nlog

2、2N F.N2A.N+1 B.21og2N C.logN.下面关于二分查找的叙述正确的是（C.表必须有序，而且只A.表必须有序，表可以顺序方式存储，也可以链表方式存储能从小到大排列实型或字符型D.表必须有序，且表只B.表必须有序且表中数据必须是整型,能以顺序方式存储1 .对线性表进行二分查找时，要求线性表必须（）A.以顺序方式存储B.以顺序方式存储，且数据元素有序C.以链接方式存储D.以链接方 式存储，且数据元素有序.适用于折半查找的表的存储方式及元素排列要求为（）A.链接方式存储，元素无序 B.链接方式存储，元素有序C.顺序方式存储，元素无序D.顺序方式存储，元素有序.用二分（对半）查找表的

3、元素的速度比用顺序法（）A. 必然快 B.必然慢 C.相等 D.不能确定.当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度（）A.必定快B.不一定C.在大部分情况下要快D.取决于表递增还是递减.具有12个关键字的有序表，折半查找的平均查找长度（）A. 3.1B.4C. 2.5D.5.折半查找的时间复杂性为（）A.O （n2） B.O （n） C. O （nlogn） D. O （logn）.当采用分快查找时，数据的组织方式为（）A.数据分成若干块，每块内数据有序B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小） 的数据组

4、成索引块C.数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D.数据分成若干块，每块（除最后一块外）中数据个数需相同.二叉查找树的查找效率与二叉树的（1）有关，在（2）时其查找效率最低（1）：A.高度B.结点的多少C.树型D.结点的位置（2）:A.结点太多B.完全二叉树C.呈单枝树D.结点太复杂。2 .要进行顺序查找，则线性表（1）；要进行折半查询，则线性表（2）；若表中元素个数为.已知二叉树排序树中某结点指针p,其双亲结点指针为fp,p为fp的左孩子，试编写算法, 删除p所指结点。4 .二叉排序树采用二叉链表存储。写一个算法，删除结点值是X的结点。要求删除该结点 后，此树

5、仍然是一棵二叉排序树，并且高度没有增长(注：可不考虑被删除的结点是根的情 况)。5 .设记录R1,R2,Rn按关键字值从小到大顺序存储在数组rL.n中，在rn+l处设立一个 监督哨，其关键字值为+8；试写一查找给定关键字k的算法;并画出此查找过程的判定树, 求出在等概率情况下查找成功时的平均查找长度。6 .元素集合已存入整型数组ALn中，试写出依次取A中各值Ai(I=irear34. (l)p!=null (2)pf=p (3)p!=*t (4)*t二null四.应用题1 .概念是基本知识的主要部分，要牢固掌握。这里只列出一部分，目的是引起重视，解答 略。2 . (1)散列表存储的基本思想是用

6、关键字的值决定数据元素的存储地址(2)散列表存储中解决碰撞的基本方法： 开放定址法形成地址序列的公式是：Hi= (H (key) +&) %m,其中m是表长，&是增量。根据&取法不同，又分为三种：a. di = l, 2,，m-1称为线性探测再散列，其特点是逐个探测表空间，只要散列表中 有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一散 列地址。b. di=l2, -I2, 22,-22,，k2 (km/2)称为二次探测再散列，它减少了聚集，但 不容易探测到全部表空间，只有当表长为形如4j+3 (j为整数)的素数时才有可能。c. 4 =伪随机数序列，称为随机探测再

7、散列。再散列法 Hi=RHi (key) i=l, 2,，k,是不同的散列函数，即在同义词产生 碰撞时，用另一散列函数计算散列地址，直到解决碰撞。该方法不易产生“聚集”，但增加 了计算时间。 链地址法 将关键字为同义词的记录存储在同一链表中，散列表地址区间用 表示，分量初始值为空指针。凡散列地址为i (OWiWm-1)的记录均插在以Hi为 头指针的链表中。这种解决方法中数据元素个数不受表长限制，插入和删除操作方便，但增 加了指针的空间开销。这种散列表常称为开散列表，而中的散列表称闭散列表，含义是元 素个数受表长限制。 建立公共溢出区 设为基本表，凡关键字为同义词的记录，都填入溢出 区O0.m-

8、lo(3)用分离的同义词表和结合的同义词表解决碰撞均属于链地址法。链地址向量空间中的 每个元素不是简单的地址，而是关键字和指针两个域，散列地址为i (OWiWm-1)的第一个 关键字存储在地址空间向量第i个分量的“关键字”域。前者的指针域是动态指针，指向同 义词的链表，具有上面的优缺点；后者实际是静态链表，同义词存在同一地址向量空间(从 最后向前找空闲单元)，以指针相连。节省了空间，但易产生“堆积”，查找效率低。(4)要在被删除结点的散列地址处作标记，不能物理的删除。否则，中断了查找通路。(5)记录负载因子.评价哈希函数优劣的因素有：能否将关键字均匀影射到哈希空间上，有无好的解决冲突 的方法，

9、计算哈希函数是否简单高效。由于哈希函数是压缩映像，冲突难以避免。解决冲突 的方法见上面2题。3 .哈希方法的平均查找路长主要取决于负载因子(表中实有元素数与表长之比)，它反映了 哈希表的装满程度，该值一般取0.650.9。解决冲突方法见上面2题。4 .不一定相邻。哈希地址为i (OWiWm-1)的关键字，和为解决冲突形成的探测序列i的同 义词，都争夺哈希地址i。散列地址0123456789关键字140192384275520比较次数11123412平均查找长度：ASLsucc= (1 + 1+1+2+3+4+1+2) /8=15/8以关键字27为例：H (27) =27%7=6 (冲突) H尸

10、(6+1) % 10=7 (冲突)H2= (6+22) %io=o (冲突)H3= (6+33) % 10=5所以比较了 4 次。7.由于装填因子为0.8,关键字有8个，所以表长为8/0.8=10。(1)用除留余数法，哈希函数为H (key) =key%7(2)散列地址0123456789关键字2115303625402637比较次数11131126(3)计算查找失败时的平均查找长度，必须计算不在表中的关键字，当其哈希地址为i(0WiWm-1)时的查找次数。本例中m=10。故查找失败时的平均查找长度为：ASLUnsucc= (9+8+7+6+5+4+3+2+1 + 1) /10=4.6ASLS

11、Ucc =16/8=2(4) int Delete (int hn, int k)从哈希表hn中删除元素k,若删除成功返回1,否则返回。i=k%7； / 哈希函数用上面(1),即 H (key) =key % 7if (hi= maxint) /maxint 解释成空地址printf (无关键字dn，k)； return (0)； )if (hi=k) hi=-maxint ； return (1)； 被删元素换成最大机器数的负数else /采用线性探测再散列解决冲突廿i；for (d=l； dWn-1； d+)11为表长，此处为1011为表长，此处为10i= (j+d) %n；if (hi=

12、 maxint) return (0); /maxint 解释成空地址if (hi=k) hi=-maxint ； return (1 )； /forprintf (无关键字dn, k)； return (0)哈希表 a: ASLsucc=24/8=3；散列地址0123456789关键字1524101917381840比较次数11214555散列地址0123456789关键字1517241019403818比较次数13121244哈希表 b: ASLsucc=18/8(4) ASLunsucc =29/139.常用构造哈希函数的方法有：(1)数字分析法 该法事先需知道关键字集合，且关键字位数比

13、散列表地址位数多，应选 数字分布均匀的位。(2)平方取中法 将关键字值的平方取中间几位作哈希地址。(3)除留余数法 H (key) =key%p,通常p取小于等于表长的最大素数。(4)折叠法 将关键字分成长度相等(最后一段可不等)的几部分，进行移位叠加或间界 叠加，其值作哈希地址。(5)基数转换法 两基数要互素，且后一基数要大于前一基数。在哈希表中删除一个记录，在拉链法情况下可以物理地删除。在开放定址法下，不能物理 地删除，只能作删除标记。该地址可能是该记录的同义词查找路径上的地址，物理的删除 就中断了查找路径。因为查找时碰到空地址就认为是查找失败。散列地址012345678910111213

14、1415关键字140168275519208479231110比较次数12143113911310.散列地址01234567891011关键字231897925471638825139151比较次数11112123243ASLsucc =21/1111.散列地址012345678910关键字223346130167415330比较次数12124511312.设用线性探测再散列解决冲突，根据公式Snl (1 + 1/ (1-a ) /2 。可求出负载因子 为a=0.67。再根据数据个数和装载因子，可求出表长m= 15/0.67,取m=23。设哈希函数H (key)=(关键字首尾字母在字母表中序号

15、之和)MOD 23。从上表求出查找成功时的平均查找长度为ASLsucc=19/152*m/21口即lW10gm/2（）+1。附：推导B-树中叶子结点数s与关键字数n的关系式：s=n+l设B-树某结点的子树数为Ci，则该结点的关键字数NfG-1。对于有k个结点的B-树, 有ENFS（Ci-l）=ECi-k （IWiWk） （1）因为B树上的关键字数，即XN尸n（liWk） （2）而B-树上的子树数可这样计算：每个结点（除根结点）都是一棵子树，设叶子（子树）数为S；则ECi=(k-l)+s (iWiWk) (3) 综合(1) (2) (3)式，有s=n+l。证毕。20 .满二叉检索树可以看作是三阶

16、B-树(23树)。B-树的插入和删除算法不适合满二叉检 索树。满二叉检索树插入和删除结点后均破坏了 “多路平衡查找树”“叶子在同一层上”(查 找失败结点)的定义。21 . B+树的查找可从根结点开始随机查找，也可以从最小关键字起顺序查找。22 .含9个叶子结点的3阶B-树至少有4个非叶子结点，当每个非叶子结点均含3棵子树， 第三层是叶子结点时就是这种情况。当4层3阶B-树有10个叶子结点时，非叶子结点达到 最大值8个，其中第一层一个，第二层两个，第三层五个非叶子结点。23 .ASLSucc=32/10. (2) 10,12/5,20,24,28,30,35,46,50,55,68(3) ASL

17、sUcc=41/12.序列(2)不可能是二叉排序树中查到363的序列。查到501后，因363llink,flag)； / 中序遍历左子树if (pre=null) pre=t； /中序遍历的第一个结点不必判断else if (pre-datadata) pre=t； 前驱指针指向当前结点 elseflag=flase； 不是完全二叉树Judgebst (t-rlink,flag)； / 中序遍历右子树/JudgeBST算法结束本题的另一算法是照定义，二叉排序树的左右子树都是二叉排序树，根结点的值大于左 子树中所有值而小于右子树中所有值，即根结点大于左子树的最大值而小于右子树的最小 值。算法如下

18、：int JudgeBST (BTree t)判断二叉树t是否是二叉排序树，若是，返回true,否则，返回falseif (t=null) return true；if (Judgebst (t-llink) & Judgebst (t-rlink) 若左右子树均为二叉排序树m=max (t-llink)； n=min (t-rlink)； 左子树中最大值和右子树中最小值 return (t-datam & t-datarlink! =null) p=p-rlink；return p-data； int min (BTree p) 求二叉树右子树的最小值if (p=null) return m

19、axint； 返回机器最大整数 else(while (p-llink! =null) p=p-llink；return p-data； )1 .题目分析借助于分块查找思想，在建立数据顺序表的同时丁建立一索引表。数据表中按 k个集合分块(元素个数不一定相等)，索引表中有两个域，一是各集合最后一个元素在数 据表中的位置(一维数组中的下标)，二是集合的个数(k)o实现数据运算时，根据给定的 二元组(i, X),首先在索引表中找到集合i的位置，然后在数据表中查找X。如查到X ,则 查找成功，返回X在数据表中的位置，否则查找失败。若要插入，则将数据表中的数据后移， 插入X,同时修改索引表。typede

20、f struct datatype data； rectype；typedef structint a； /a数组容量够大，存储各集合最后一个数据在数据表中的下标 int k；集合个数 index；int SetSearch_Insert (rectype R, index id, datatype x, int i)数据表R,查找第i个集合的元素x,若查找成功，返回其位置，否则将其插入第i个 集合if (iid.k) printf (无第(1 个集合n”, i)； exit (0)； if (i=l) first=0； else first=id.ai-l+l； /first 指向第 i 个

21、集合在数据表的首址 last= id.ai； /last是第i个集合在数据表中的末址for (j=first； jWlast； j+) if (Rj=x) return (j)； 查找成功for (j=id.aid.k； jid.ai； j-)/查找失败,将 x 插入数据表Rj+l=Rj； 元素后移Rj+l=x； 将x插入到原第i个集合最后一个元素之后。for (j=i； jlchild=null) f-rchild=p-rchild； free (p)； p 无左子女else 用p左子树中的最大值代替p结点的值q=p-lchild； s=q；while (q-rchild) s=q； q=q

22、-rchild ； 查p左子树中序序列最右结点if (S=p-lchild) p左子树的根结点无右子女p-data=s-data； p-lchild=s-lchild； free (s)； elsep-data=q-data； s-rchild=q-lchild； free (q)； )/Delete4 .题目分析上题用被删结点左子树中最大值结点代替被删结点，本题用被删结点右子树中 最小值(中序遍历第一个)结点代替被删结点。void Delete(BSTree bst,p,fp)/在二叉排序树bst上，删除fp所指结点的左子女(由p所指向)的算法。if (!p-lchild) fp-lchil

23、d=p-rchild； free (p)； p 无左子女else if (!p-rchild) fp-lchild=p-lchild； free (p)； p 无右子女else p有左子女和右子女q=p-rchild； s=q； 用p右子树中的最小值代替p结点的值while (q-lchild) s=q； q=q-lchild ； 查p右子树中序序列最左结点if (s=p-rchild) p右子树的根结点无左子女p-data=s-data； p-rchild=s-rchild； free (s)； elsep-data=q-data； s-lchild=q-rchild； free (q)；

24、/Delete.题目分析在二叉排序树上删除结点，首先要查找该结点。查找成功后，若该结点无左 子树，则可直接将其右子树的根结点接到其双亲结点上；若该结点有左子树，则将其左子树 中按中序遍历的最后一个结点代替该结点，从而不增加树的高度。void Delete(BSTree bst, keytype X)在二叉排序树bst上，删除其关键字为X的结点。BSTree f,p=bst;while (p & p-key!=X) 查找值为X的结点if (p-keyX) f=p; p=p-lchild;else f=p; p=p-rchild;if(p=null) printf(无关键字为 X 的结点n);ex

25、it(0);if p-lchild=null 被删结点无左子树if(f-lchild=p)f-lchild=p-rchild;将被删结点的右子树接到其双亲上else f-rchild=p-rchild;else q=p； s=p-lchild; 被删结点有左子树while (s-rchild !=null)/查左子树中最右下的结点(中序最后结点)q=s; s=s-rchild;p-key=s-key;结点值用其左子树最右下的结点的值代替if (q=p) p-lchild=s-lchild;被删结点左子树的根结点无右子女 else q-rchild=s-lchild; /s是被删结点左子树中序序

26、列最后一个结点 free(s);算法结束. int Search (rectype r , int n, keytype k)在n个关键字从小到大排列的顺序表中，查找关键字为k的结点。rn+l.key=MAXINT； 在高端设置监视哨i=l;while (ri.kcyk) return (BinSrch (r,k, mid+1, high);else return (BinSrch (r,k, low, mid-1);)else return (0)； 查找失败。算法结束算法时间复杂度为O (logn)。n,则顺序查找的平均比较次数为(3)；折半查找的平均比较次数为(4)o(1) (2)： A

27、.必须以顺序方式存储；B.必须以链式方式存储；C.既可以以顺序方式存 储，也可以链式方式存储；D.必须以顺序方式存储，且数据已按递增或递减顺序排好；E.必须以链式方式存储，且数据已按递增或递减的次序排好。(3) (4)： A.n B,n/2 Cn*n D.n*n/2E.log2nEnlog2n G.(n+l)/2H.log2(n+1)14 .在等概率情况下,线性表的顺序查找的平均查找长度人51为(1)，有序表的折半查找 的人5匕为(2)，对静态树表，在最坏情况下,人51为(3)，而当它是一棵平衡树时,ASL 为(4)，在平衡树上删除一个结点后可以通过旋转使其平衡，在最坏情况下需(5) 次旋转。供选择的答案：(1) (2) (3) (4) (5): A. 0( 1)B. 0( log2n)C. O(log2n)2) D.O(nlog2n) E.0(n).对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找失 败，它们的平均查找长度是()，对于查找成功，他们