《2022年数据结构考研试题精选及答案查找答案参照 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构考研试题精选及答案查找答案参照 .pdf（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第 9 章集合一选择题1.C 2.A 3.1D 3.2C 4.D 5.B 6.D 7.D 8.C 9.A 10.D 11.B 12.1C 12.2C 13.1C 13.2D 13.3G 13.4H 14.1E 14.2B 14.3E 14.4B 14.5B 15.1B 15.2A 16.A 17.C 18.C 19.C 20.D 21.B 22.C 23.B 24.C 25.1B 25.2F 25.3I 26.A 27.D 28.C 29.1A 29.2C 30.B 31.D 32.D 33.C 34.D 35.1D 35.2C 36.C 二判断题1.2.3.4.5.6.7.8.9.10.11
2、.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。但是，平衡二叉树本质上是二叉排序树，完全二叉树不一
3、定是排序树。故不能说完全二叉树是平衡二叉树。23某结点的左子树根结点不一定是它的中序前驱，其右子树根结点也不一定是它的中序后继。24在等概率下，查找成功时的平均查找长度相同，查找失败时的平均查找长度不相同。26只有被删除结点是叶子结点时命题才正确。三填空题1n n+1 24 36,9,11,12 45 526（第 4 层是叶子结点，每个结点两个关键字）61,3,6,8,11,13,16,19 75,96 8m-1,m/2-1 92,4,3 10(1)哈希函数(2)解决冲突的方法(3)选择好的哈希函数(4)处理冲突的方法(5)均匀(6)简单11 AVL树（高度平衡树，高度平衡的二叉排序树），或为
4、空二叉树，或二叉树中任意结点左子树高度与右子树高度差的绝对值小于等于1。12小于等于表长的最大素数或不包含小于20 的质因子的合数 1316 142n+1 15(1)45(2)45(3)46（块内顺序查找）16k(k+1)/2 1730，31.5（块内顺序查找）18(1)顺序存储或链式存储 (2)顺序存储且有序(3)块内顺序存储，块间有序(4)散列存储名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 8 页 -19(n+1)/2 20(n+1)/n*log2(n+1)-1 21结点的左子树的高度减去结点的右子树的高度22(1)顺序表(2)树表(3)哈希表(4)开放定址方法(5)链地
5、址方法(6)再哈希(7)建立公共溢出区23直接定址法 24 logm/2(21n)+1 25O(N)26n(n+1)/2 27 54 2831 2937/12 30主关键字 31左子树右子树32插入删除 33 14 34(1)126 (2)64 (3)33 (4)65 35（1）low=high (2)(low+hig)DIV 2 (3)binsrch:=mid (4)binsrch:=0 36(1)k (2)Irear 38(1)p!=null (2)pf=p (3)p!=*t (4)*t=null 四应用题1概念是基本知识的主要部分，要牢固掌握。这里只列出一部分，目的是引起重视，解答略。2
6、（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=伪随机数序列，称为随机探
7、测再散列。再散列法 Hi=RHi（key）i=1，2，,，k，是不同的散列函数，即在同义词产生碰撞时，用另一散列函数计算散列地址，直到解决碰撞。该方法不易产生“聚集”，但增加了计算时间。链地址法将关键字为同义词的记录存储在同一链表中，散列表地址区间用H0.m-1表示，分量初始值为空指针。凡散列地址为i（0 i m-1）的记录均插在以Hi为头指针的链表中。这种解决方法中数据元素个数不受表长限制，插入和删除操作方便，但增加了指针的空间开销。这种散列表常称为开散列表，而中的散列表称闭散列表，含义是元素个数受表长限制。建立公共溢出区设 H0.m-1为基本表，凡关键字为同义词的记录，都填入溢出区O0.m
8、-1。（3）用分离的同义词表和结合的同义词表解决碰撞均属于链地址法。链地址向量空间中的每个元素不是简单的地址，而是关键字和指针两个域，散列地址为i（0i m-1）的第一个关键字存储在地址空间向量第i 个分量的“关键字”域。前者的指针域是动态指针，指向同义词的链表，具有上面的优缺点；后者实际是静态链表，同义词存在同一地址向量空间（从最后向前找空闲单元），以指针相连。节省了空间，但易产生“堆积”，查找效率低。（4）要在被删除结点的散列地址处作标记，不能物理的删除。否则，中断了查找通路。名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 8 页 -（5）记录负载因子3评价哈希函数优劣的因素
9、有：能否将关键字均匀影射到哈希空间上，有无好的解决冲突的方法，计算哈希函数是否简单高效。由于哈希函数是压缩映像，冲突难以避免。解决冲突的方法见上面2 题。4哈希方法的平均查找路长主要取决于负载因子（表中实有元素数与表长之比），它反映了哈希表的装满程度，该值一般取0.650.9。解决冲突方法见上面2 题。5不一定相邻。哈希地址为i（0i m-1）的关键字，和为解决冲突形成的探测序列i 的同义词，都争夺哈希地址i。6散列地址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+
10、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）散列地址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）计算查找失败时的平均查找长度，必须计算不在表中的关键字，当其哈希地址为i（0i m-1）时的查找次数。本例中m=10。
11、故查找失败时的平均查找长度为：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，否则返回0 i=k%7；/哈希函数用上面（1），即 H（key）=key%7 if（hi=maxint）/maxint解释成空地址printf（“无关键字%dn”，k）；return （0）；if（hi=k）hi=-maxint ；return（1）；/被删元素换成最大机器数的负数else /采用线性探测再散列解决冲突 j=i;for（d=1；d n-1；d+
12、）i=（j+d）%n；/n为表长，此处为10 if（hi=maxint）return(0);/maxint解释成空地址if（hi=k）hi=-maxint；return （1）；/for printf（“无关键字%dn”，k）；return(0)8散列地址0 1 2 3 4 5 6 7 8 9 关键字15 24 10 19 17 38 18 40 名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 8 页 -比较次数1 1 2 1 4 5 5 5 哈希表 a:ASLsucc=24/8=3；散列地址0 1 2 3 4 5 6 7 8 9 关键字15 17 24 10 19 40 38
13、18 比较次数1 3 1 2 1 2 4 4 哈希表 b:ASLsucc=18/8 9（1）散列地址0 1 2 3 4 5 6 7 8 9 10 11 12 关键字13 22 53 1 41 67 46 51 30 比较次数1 1 1 2 1 2 1 1 1（2）装填因子=9/13=0.7 （3）ASLsucc=11/9 （4）ASLunsucc=29/13 10 11ASLsucc=19/12 12常用构造哈希函数的方法有：（1）数字分析法该法事先需知道关键字集合，且关键字位数比散列表地址位数多，应选数字分布均匀的位。（2）平方取中法将关键字值的平方取中间几位作哈希地址。（3）除留余数法 H
14、（key）=key%p，通常 p 取小于等于表长的最大素数。（4）折叠法将关键字分成长度相等（最后一段可不等）的几部分，进行移位叠加或间界叠加，其值作哈希地址。（5）基数转换法两基数要互素，且后一基数要大于前一基数。在哈希表中删除一个记录，在拉链法情况下可以物理地删除。在开放定址法下，不能物理地删除，只能作删除标记。该地址可能是该记录的同义词查找路径上的地址，物理的删除就中断了查找路径。因为查找时碰到空地址就认为是查找失败。散列地址0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 关键字14 01 68 27 55 19 20 84 79 23 11 10 比较次数1
15、 2 1 4 3 1 1 3 9 1 1 3 13（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 ASLsucc=（1+1+1+2+1+2+1+2）/8=11/8 ASLunsucc=（1+2+1+8+7+6+5+4+3+2+1）/11=40/11 名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 8 页 -（2）13 题图 ASLsucc=11/8 ASLunsucc=19/11 14题（2）ASLsucc=13/8 ASLunsucc=19/11 值得指出，对用拉链法求查找失
16、败时的平均查找长度有两种观点。其一，认为比较到空指针算失败。以本题为例，哈希地址0、2、5、7、9 和 10 均为比较 1 次失败，而哈希地址1 和 3 比较 2 次失败，其余哈希地址均为比较3 次失败，因此，查找失败时的平均查找长度为 19/11，我们持这种观点。还有另一种理解，他们认为只有和关键字比较才计算比较次数，而和空指针比较不计算。照这种观点，本题的ASLunsucc=（1+1+2+2+2）/11=8/11 14由 hashf(x)=x mod 11 可知，散列地址空间是0 到 10，由于有 8 个数据，装载因子取0.7。（1）散列地址0 1 2 3 4 5 6 7 8 9 10 关
17、键字33 1 13 12 34 38 27 22 比较次数1 1 1 3 4 1 2 8 ASLsucc=21/8 ASLunsucc=47/11 15（1）ASL=42/12 （2）a：ASLsucc=31/12（2）b：ASLsucc=18/12(注：本题 x 取小于等于x 的最大整数)16名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 8 页 -17查找时，对关键字49,22,38,32,13各比较一次，对21,18 各比较两次18 ASLsucc=15/1019 ASLsuss=16/11 20散列地址0 1 2 3 4 5 6 7 8 9 10 11 关键字231 89
18、 79 25 47 16 38 82 51 39 151 比较次数1 1 1 1 2 1 2 3 2 4 3 名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 8 页 -ASLsucc=21/11 21散列地址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 22（1）散 列地址0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 关 键字32 17 63 49 24 40 10 30 31 46 47 比 较次数1 1 6 3 1 2 1 1 1
19、3 3（2）查找关键字63，H（k）=63 MOD 16=15，依次与31，46，47，32，17，63 比较。（3）查找关键字60，H（k）=60 MOD 16=12，散列地址12 内为空，查找失败。（4）ASLsucc=23/11 23设用线性探测再散列解决冲突，根据公式Snl（1+1/（1-）/2 。可求出负载因子为=0.67。再根据数据个数和装载因子，可求出表长m=15/0.67，取 m=23。设哈希函数 H（key）=（关键字首尾字母在字母表中序号之和）MOD 23。从上表求出查找成功时的平均查找长度为ASLsucc=19/152.0，满足要求。24（1）哈希函数H（key）=（关键
20、字各字符编码之和）MOD 7（2）散列地址0 1 2 3 4 5 6 7 8 9 关键字be cd aa ab ac ad bd bc ae ce 比较次数1 2 1 1 1 1 1 3 3 9 25=0.7，所以表长取m=7/0.7=10 散列地址0 1 2 3 4 5 6 7 8 9 关键字SAT WED SUN MON TUE THU FRI 比较次数6 1 1 1 2 3 4 ASLsucc=18/7 ASLunsucc=32/10 26（1）散列地址0 1 2 3 4 5 6 7 8 9 10 11 12 关键字27 53 2 31 19 20 8 18 比较次数3 1 1 1 1
21、1 1 2（2）ASLsuss=11/8 27（1）散列地址0 1 2 3 4 5 6 7 8 9 10 11 12 关键字0 3 29 200 32 45 58 100 10 126 400 比较次数1 1 2 1 1 2 3 1 1 3 3 名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 8 页 -关键字 29 和 45 各发生 一次碰撞，关键字58,126 和 400 各发生 两次碰撞，其余关键字无碰撞。（2）散列地址0 1 2 3 4 5 6 7 8 9 10 11 12 关键字58 10 100 3 名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 8 页 -