资源预览内容
第1页 / 共110页
第2页 / 共110页
第3页 / 共110页
第4页 / 共110页
第5页 / 共110页
第6页 / 共110页
第7页 / 共110页
第8页 / 共110页
第9页 / 共110页
第10页 / 共110页
亲,该文档总共110页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
数据结构自测题答案数据结构自测题答案 (11)(11)第 9 章 集合一选择题 1.C2.A3.1D3.2C4.D5.B6.D7.D8.C9.A10.D11.B12.1C12.2C13.1C13.2D13.3G13.4H14.1E14.2B14.3E14.4B14.5B15.1B15.2A16.A17.C18.C19.C20.D21.B22.C23.B24.C25.1B25.2F25.3I26.A27.D28.C29.1A29.2C30.B31.D32.D33.C34.D35.1D35.2C36.C二判断题1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27.28.29.30.31.32.33.34.35.36.部分答案解释如下。4不能说哪种哈希函数的选取方法最好,各种选取方法有自己的适用范围。8哈希表的结点中可以包括指针,指向其元素。11单链表不能使用折半查找方法。20按插入后中序遍历是递增序列的原则,若某结点只有右子树,而插入元素的关键字小于该结点的关键字,则会插入到该结点的左侧,成为其左孩子。这种插入就不是插入到叶子下面。21从平衡因子定义看,完全二叉树任一结点的平衡因子的绝对值确实是小于等于 1。但是,平衡二叉树本质上是二叉排序树,完全二叉树不一定是排序树。故不能说完全二叉树是平衡二叉树。23某结点的左子树根结点不一定是它的中序前驱,其右子树根结点也不一定是它的中序后继。24在等概率下,查找成功时的平均查找长度相同,查找失败时的平均查找长度不相同。26只有被删除结点是叶子结点时命题才正确。三填空题1n n+1 24 36,9,11,12 45 526(第 4 层是叶子结点,每个结点两个关键字) 61,3,6,8,11,13,16,1975,96 8m-1,m/2-1 92,4,310(1)哈希函数(2)解决冲突的方法 (3)选择好的哈希函数 (4)处理冲突的方法 (5)均匀(6)简单11AVL 树(高度平衡树,高度平衡的二叉排序树) ,或为空二叉树,或二叉树中任意结点左子树高度与右子树高度差的绝对值小于等于1。12小于等于表长的最大素数或不包含小于 20 的质因子的合数 1316 142n+115(1)45 (2)45 (3)46(块内顺序查找) 16k(k+1)/2 1730,31.5(块内顺序查找)18(1)顺序存储或链式存储 (2)顺序存储且有序 (3)块内顺序存储,块间有序 (4) 散列存储19(n+1)/2 20(n+1)/n*log2(n+1)-1 21结点的左子树的高度减去结点的右子树的高度22(1)顺序表(2)树表(3)哈希表(4)开放定址方法(5)链地址方法(6)再哈希(7)建立公共溢出区23直接定址法 24logm/2()+1 25O(N) 26n(n+1)/2 2754 2831 2937/12 30主关键字 31左子树 右子树32插入 删除 3314 34(1)126 (2)64 (3)33 (4)6535 (1)lowrear38(1)p!=null (2)pf=p (3)p!=*t (4)*t=null四应用题1概念是基本知识的主要部分,要牢固掌握。这里只列出一部分,目的是引起重视,解答略。2 (1)散列表存储的基本思想是用关键字的值决定数据元素的存储地址(2)散列表存储中解决碰撞的基本方法: 开放定址法 形成地址序列的公式是:Hi=(H(key)+di)% m,其中 m 是表长,di 是增量。根据 di 取法不同,又分为三种:adi =1,2,m-1 称为线性探测再散列,其特点是逐个探测表空间,只要散列表中有空闲空间,就可解决碰撞,缺点是容易造成“聚集” ,即不是同义词的关键字争夺同一散列地址。bdi =12,-12,22,-22, ,k2(km/2) 称为二次探测再散列,它减少了聚集,但不容易探测到全部表空间,只有当表长为形如 4j+3(j 为整数)的素数时才有可能。cdi =伪随机数序列,称为随机探测再散列。 再散列法 Hi=RHi(key) i=1,2,k,是不同的散列函数,即在同义词产生碰撞时,用另一散列函数计算散列地址,直到解决碰撞。该方法不易产生“聚集” ,但增加了计算时间。 链地址法 将关键字为同义词的记录存储在同一链表中,散列表地址区间用 H0.m-1表示,分量初始值为空指针。凡散列地址为 i(0im-1)的记录均插在以 Hi为头指针的链表中。这种解决方法中数据元素个数不受表长限制,插入和删除操作方便,但增加了指针的空间开销。这种散列表常称为开散列表,而中的散列表称闭散列表,含义是元素个数受表长限制。 建立公共溢出区 设 H0.m-1为基本表,凡关键字为同义词的记录,都填入溢出区O0.m-1。(3)用分离的同义词表和结合的同义词表解决碰撞均属于链地址法。链地址向量空间中的每个元素不是简单的地址,而是关键字和指针两个域,散列地址为 i(0im-1)的第一个关键字存储在地址空间向量第 i 个分量的“关键字”域。前者的指针域是动态指针,指向同义词的链表,具有上面的优缺点;后者实际是静态链表,同义词存在同一地址向量空间(从最后向前找空闲单元) ,以指针相连。节省了空间,但易产生“堆积” ,查找效率低。(4)要在被删除结点的散列地址处作标记,不能物理的删除。否则,中断了查找通路。(5)记录 负载因子3评价哈希函数优劣的因素有:能否将关键字均匀影射到哈希空间上,有无好的解决冲突的方法,计算哈希函数是否简单高效。由于哈希函数是压缩映像,冲突难以避免。解决冲突的方法见上面 2 题。4哈希方法的平均查找路长主要取决于负载因子(表中实有元素数与表长之比) ,它反映了哈希表的装满程度,该值一般取0.650.9。解决冲突方法见上面 2 题。5不一定相邻。哈希地址为 i(0im-1)的关键字,和为解决冲突形成的探测序列 i 的同义词,都争夺哈希地址 i。6 散列地址0123456789关键字140192384275520比较次数11123 412平均查找长度: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次。7由于装填因子为 0.8,关键字有 8 个,所以表长为 8/0.8=10。(1)用除留余数法,哈希函数为 H(key)=key % 7(2)散列地址0123456789关键字2115303625402637比较次数11131126(3)计算查找失败时的平均查找长度,必须计算不在表中的关键字,当其哈希地址为 i(0im-1)时的查找次数。本例中 m=10。故查找失败时的平均查找长度为:ASLunsucc=(9+8+7+6+5+4+3+2+1+1)/10=4.6 ASLsucc =16/8=2(4)int Delete(int hn,int k)/ 从哈希表 hn中删除元素 k,若删除成功返回 1,否则返回 0i=k%7;/ 哈希函数用上面(1) ,即 H(key)=key % 7if(hi= maxint)/maxint 解释成空地址printf(“无关键字%dn” ,k) ;return (0) ;if(hi=k)hi=-maxint ;return(1) ; /被删元素换成最大机器数的负数else / 采用线性探测再散列解决冲突j=i;for(d=1;dn-1;d+)i=(j+d)%n; / n 为表长,此处为 10if(hi= maxint)return (0); /maxint 解释成空地址if(hi=k) hi=-maxint ;return (1) ;/forprintf(“无关键字%dn” ,k) ;return (0)8散列地址0123456789关键字1524101917381840比较次数11214555哈希表 a: ASLsucc=24/8=3;散列地址0123456789关键字1517241019403818比较次数13121244哈希表 b: ASLsucc=18/89 (1)散列地址0123456789101112关键字13225314167465130比较次数111212111(2)装填因子=9/13=0.7 (3)ASLsucc =11/9 (4)ASLunsucc=29/1310 11ASLsucc=19/1212常用构造哈希函数的方法有:(1)数字分析法 该法事先需知道关键字集合,且关键字位数比散列表地址位数多,应选数字分布均匀的位。(2)平方取中法 将关键字值的平方取中间几位作哈希地址。(3)除留余数法 H(key)=key%p,通常 p 取小于等于表长的最大素数。(4)折叠法 将关键字分成长度相等(最后一段可不等)的几部分,进行移位叠加或间界叠加,其值作哈希地址。(5)基数转换法 两基数要互素,且后一基数要大于前一基数。在哈希表中删除一个记录,在拉链法情况下可以物理地删除。在开放定址法下,不能物理地删除,只能作删除标记。该地址可能是该记录的同义词查找路径上的地址,物理的删除就中断了查找路径。因为查找时碰到空地址就认为是查找失败。散列地址0123456789101112131415关键字140168275519208479231110比较次数12143113911313 (1)散列地址012345678910关键字412493813243221比较次数11121212ASLsucc =(1+1+1+2+1+2+1+2)/8=11/8ASLunsucc=(1+2+1+8+7+6+5+4+3+2+1)/11=40/11(2)13 题图 ASLsucc =11/8 ASLunsucc=19/11 14 题(2) ASLsucc=13/8 ASLunsucc=19/11值得指出,对用拉链法求查找失败时的平均查找长度有两种观点。其一,认为比较到空指针算失败。以本题为例,哈希地址0、2、5、7、9 和 10 均为比较 1 次失败,而哈希地址 1 和 3 比较 2次失败,其余哈希地址均为比较 3 次失败,因此,查找失败时的平均查找长度为 19/11,我们持这种观点。还有另一种理解,他们认为只有和关键字比较才计算比较次数,而和空指针比较不计算。照这种观点,本题的 ASLunsucc=(1+1+2+2+2)/11=8/1114由 hashf(x)=x mod 11 可知,散列地址空间是 0 到 10,由于有8 个数据,装载因子取 0.7。(1)散列地址012345678910关键字331131234382722比较次数11134128ASLsucc=21/8 ASLunsucc=47/1115(1)ASL=42/12 (2)a:ASLsucc=31/12 (2)b:A
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号