计算机专业基础综合数据结构历年真题试卷汇编1

《计算机专业基础综合数据结构历年真题试卷汇编1》由会员分享，可在线阅读，更多相关《计算机专业基础综合数据结构历年真题试卷汇编1（6页珍藏版）》请在装配图网上搜索。

1、计算机专业基础综合数据结构(集合)历年真题试卷汇编 1(总分：82.00，做题时间：90 分钟)一、 综合题(总题数：25，分数：72.00)I. 试用关键字序列(33, 10, 45, 20, 53, 43, 31, 15, 65, 40),构造哈希(Hash)表，设哈希函数为：H(key)=key%II, 其中key为关键字，为求余运算符；用开放定址法处理冲突，用线性探测再散列法查找空位，用长 度为14的数据元素组A14表示哈希表。(1)画出该哈希表的存储结构图；(2)假定每个元素的查找概率相 等，计算查找成功时的ASL； (3)计算查找不成功时的ASL【华中科技大学2007四、25(10

2、分)】(2)ASL 成功 =(6*1+2*3+5+7)10=2410(3)ASL 失败正确答案：(正确答案：(1)成功成功 =(4+3+2+1+2+1+1+2+1+9+8)11=341 1。计算方法参见上面58题(3)。 )2采用哈希函数H(k)=3 *kmod13并用线性探测开放地址法处理冲突，在散列地址空间012中对关键字序列 22, 41, 53, 46, 30, 13, 1, 67, 51。 (1)构造哈希表(画示意图)； (2)装填因子；等概率下(3)成 功的和(4)不成功的平均查找长度。【北京工业大学2000三(8分)】【烟台大学2007四、 4(10分)】正确答案： (正确答案：

3、 (1)2)装填因子=913=07 (3)ASL=119 (4)ASL=2913)SUCCUNSUCC3设散列表长度为14,散列函数其中 i 为键值中第一个字母在字母表中的序号,若键值的输入顺序为 Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec，用拉链法处理冲突，要求：(1) 构造散列表； (2)求出在等概率情况下,查找成功的平均查找长度。 【厦门大学 2001 二、 2(24%3分)】正确答案： (正确答案： (1)ASL SUCC =1912 (2)4. 常用的构造哈希函数的方法有哪些?若在哈希表中删除一个记录,应如何操

4、作?为什么?已知一组关键字为(19, 14, 23, 01, 68, 20, 84, 27, 55, 11, 10, 79)，按哈希函数 H(Key)=KeyMOD 13 和线性探测再散列 处理冲突的方法在地址空间A0. 15中构造哈希表。【燕山大学1999 八(14分)】正确答案： (正确答案：常用构造哈希函数的方法有： (1)数字分析法。该方法需要事先知道关键字集合, 且关键字位数比散列表地址位数多,应选数字分布均匀的位。 (2)平方取中法。将关键字值的平方取中间 几位作哈希地址。(3)除留余数法。H(key)=key%p，通常P取小于等于表长的最大素数。(4)折叠法。将 关键字分成长度相

5、等(最后一段可不等)的几部分,进行移位叠加或间界叠加,其值作为哈希地址。 (5)基数转换法。两基数要互素,且后一基数要大于前一基数。在哈希表中删除一个记录,在链地址法情况下可以物理地删除。在开放定址法下,不能物理地删除,只能作删除标记。该地址可能是该记录的同义词查找路径上的地址,物理地删除就中断了查找路径。因为查找时碰到空地址就认为是查找失败。5.解答题。【中国海洋大学2006六(15分)】 (1)画出对长度为10的有序表进行折半查找的查找树,并求其等概率时查找成功的平均查找长度。 (2)设有一组关键字9, 01, 23, 14, 55, 20, 84, 27,采用哈希 函数：H(key)=k

6、ey MOD 7,表长为10,用开放地址法的二次探测再散列方法=H(key)+di)MOD 10(di=1 2 , 2 2 , 3 2，)解决冲突。要求：对该关键字序列构造哈希表，指出有哪些同义词并计算查找成功的平均查找长度。正确答案： (正确答案： (1)ASL= (1*1+2*2+4*3+3*4)10=2910(4*3含义是4个长度为3的结点)判成功定树请参见上面第9题。 (2)55、 20和27是同义词，9和23是同义词，14和84是同义词。SL 成=(4*1+2*2+2*3)8=14)6.设哈希表的长度为15,哈希函数H(k)=k mod 13,散列地址空间为014，对关键字序列(19

7、, 5, 21, 24， 45， 20， 68， 27， 70， 11， 10)，按线性探测再散列解决冲突的方法构造哈希表，写出构造后的哈希表 并求出等概率下查找成功和查找不成功时的平均查找长度。【北京交通大学2006四、5(5分)】设哈希函数为：H(key)=key mod 13，其中key为关键字；mod为取模运算，试用关键字序列(39, 25, 15, 54, 26, 24, 14, 21, 37, 38)构造哈希表：(分数： 4.00)(1) .用链地址法处理冲突,画出该哈希表的存储结构图；假定每个记录的查找概率相等,计算查找成功时 的平均查找长度；(2) .设表地址范围为013,用线

8、性探测再散列法处理冲突,画出该哈希表的存储结构图；假定每个记录的查找概率相等,计算查找成功时的平均查找长度。【华中科技大学2006四、4(12分)】正确答案： (正确答案： ASL=118 ASL=1911 值得指出的是,对用链地址法求查找失败时的平AUCC UNSUCC均查找长度有两种观点。其一,认为比较到空指针算失败。以本题为例,哈希地址0、2、5、7、9和10均 为比较1次失败,而哈希地址1和3比较2次失败,其余哈希地址均为比较3次失败,因此,查找失败时 的平均查找长度为1911,我们持这种观点。还有另一种理解,他们认为只有和关键字比较才计算比较次 数,而和空指针比较不计算。照这种观点,

9、本题的 ASL=(1+1+2+2+2)11=811。)UNSUCC7.设开放定址哈希表的表长为10,表中元素的编号从0到9,设初始时表为空。作图表示出采用二次探测 处理冲突时,将关键词89, 1 8, 49, 58, 69依次插入到该表中的过程。同时要求对每一步给出简要的说 明。【中南大学2005四、5(10分)】正确答案：(正确答案：设哈希函数为H(key)=key%7。数据太少，哈希函数得当，未发生冲突。8若散列函数为H(key)=f MOD 7,其中，i为关键字key的第一个字母在英文字母表中的序号，并且采用 线性探测再散列方法处理冲突。请画出在一个初始状态为空,地址值域为06的散列表中

10、依次插入下列关键字MON, TUE, WED, THU, FRI, SAT,SUN以后的散列表。【北京航空航天大学2005 一 (10分)】正确答案： (正确答案：9使用散列函数hash(x)xmod 11,把一个整数值转换成散列表下标，现要把数据：1, 13, 12, 34, 38, 33, 27, 22插入到散列表中。 (1)使用线性探查再散列法来构造散列表。 (5分)(2)使用链地址法构造散列 表。 (5分)(3)针对这两种情况,确定其装填因子,查找成功所需的平均探查次数,以及查找不成功所需的 平均探查次数。 (5分)【清华大学1998五(1 5分)】 正确答案：(正确答案：由hashf

11、(x)=mod 11可知，散列地址空间是0到10，由于有8个数据，装载因子rSEil取 0. 7。(1)AsL =21 / 8 ASL =47 / 11 (2)ASL =13/8;ASL =19 / 11SUCCUNSUCCSUCCUNSUCC10. 设散列函数H(k)=k mod 7,散列表的地址空间为06,对关键字序列32, 13, 49, 18, 22, 38, 21按链地址法处理冲突的办法构造哈希表,并指出查找各关键字要进行几次比较。【西安电子科技大学1999 计算机应用一、5 (5分) 】 正确答案： (正确答案：查找时,对关键49, 22, 38, 32, 13各比较一次,对21,

12、 18各比较两次。 )11. 选取哈希函数H(key)=key mod 7,用链地址法解决冲突。试在06的散列地址空间内对关键字序列31,23， 17， 27， 19， 11， 13， 91， 61， 41构造哈希表，并计算在等概率下成功查找的平均查找长度。【大连 海事大学200 1 八(10分)】正确答案：(正确答案：ASL =15/10SUCC设哈希(Hash)表的地址范围为017，哈希函数为：H(K)=K MOD 16, K为关键字，用线性探测再散列法处理冲突,输入关键字序列： (10, 24, 32, 17, 31, 30, 46, 47, 40, 63, 49),造出哈希表,试回答下

13、列 问题：(分数： 8.00)(1). 画出哈希表示意图。正确答案： (正确答案：查找关键字63, H(k)=63 MOD 16=15,依次与31, 46, 47, 32, 17, 63比较。)(3) .若查找关键字60,需要依次与哪些关键字比较?正确答案： (正确答案：查找关键字60, H(k)=60 MOD 16=12,散列地址12内为空,查找失败。)(4) .假定每个关键字的查找概率相等,求查找成功时的平均查找长度。【华中理工大学 1999三(10分)】 【江苏大学2006三、3(11分)】 正确答案： (正确答案： ASL =23/ 11)SUCC12. 试为下列关键字设计哈希表,要求

14、所设计的表在查找成功时的平均查找长度不超过20。并请验证你 造的哈希表的实际平均查找长度是否满足要求。(CHA, CAI, LAN, WEN, LONGZHAO, WU, LIU, CHEN, LI, WANG CAO, YUN, CHANG YANG) 【清华大学 1996 五】正确答案：(正确答案：设用线性探测再散列解决冲突，根据公式S (1+1/ (1 一 a )/2。可求出负载 nl=19SUCC因子为a =0. 67。再根据数据个数和装填因子，可求出表长m=15/0. 67,取m=23。设哈希函数H(key) = (关 键字首尾字母在字母表中序号之和)MOD23。/1 5=2 Fib

15、onacciTree（d 一 2, T. 1eftptr）； FibonacciTree（d 一 1, T. rightptr） ； （1）画出深度为 4 的 Fibonacci 树（即用 d=4 调用上述算法的结果）。（7分）（2）从你画的树中分析深度为d的Fibonacci树中结点总数和Hbonacci数的关系。Fibonacci 数定义如下： F =1， F =1 F =F +F n1 （3）你所画出的 Fibonacci 树是否为平衡二n1n n-1n-2叉树?若是，它是否为同样深度的平衡二叉树中结点数目最少的一种?（4分）【中国科学技术大学1998三（15树，而且是同样深度的平衡二叉

16、树中结点数目最少的一种。 ）二、 设计题（总题数：4，分数：10.00）已知某哈希表HT的装填因子小于1,哈希函数H（key）为关键字的第一个字母在字母表中的序号。【西北大 学 2001 五】（分数： 4.00）（1）.处理冲突的方法为线性探测开放地址法。编写一个按第一个字母的顺序输出哈希表中所有关键字的程 序。正确答案：(正确答案：由于装填因子小于1,且哈希函数H(k)为关键字第一个字母在字母表中的序号，字 母A的序号为1，表长可设为n(n27),而在链地址法中，表长为26。查找不成功是指碰到空指针为 止(另一种观点是空指针不计算比较次数，请参见本章应用题第65题 (2)。核心语句段如下：

17、for (i=1 ； iW26； i+) /哈希地址 1 到 26 (j=1； count(2).处理冲突的方法为链地址法。编写一个计算在等概率情况下查找不成功的平均查找长度的算法。注意， 此算法中规定不能用公式直接求解计算。正确答案：(正确答案：for(i=1； iW26； i+) (p=hi； j=1；/按我们的约定，查找不成功指到空指 针为止 while(p!=null) j+； p=p 一next； count+=j； return (count / 26. 0)；)18. 有一个100 * 100的稀疏矩阵，其中1的元素为非零元素，现要求用哈希表作存储结构。 (1)请你设 计一个哈希

18、表。 (2)请写一个对你所设计的哈希表中给定行值和列值存取矩阵元素的算法；并对你的算法 所需时间和用一维数组(每个分量存放一个非零元素的行值、列值和元素值)作存储结构时存取元素的算法 (注：此算法不需要写出，仅需说明存取的方法和所用时间)进行比较。【北方交通大学1994六(16分)】 正确答案：(正确答案：非零元素个数是100，负载因子取0. 8,表长125左右，取p为127,散列地址为 0到126。哈希函数用H(k) = (3*i+2*f) %127，i、j为行值和列值。)19. 将一组数据元素按哈希函数H(key)散列到哈希表HT(0： m)中，用线性探测法处理冲突H(key)+1， H(

19、key)+2，H(key) 一 1)，假设空单元用EMPTY表示，删除操作是将哈希表中结点标志位从INUSE标记 为DELETED，试写出该散列表的查找、插入和删除三个基本操作算法。【北京邮电大学2001五、2(10分)】正确答案：(正确答案：本题哈希函数H(key)，用线性探测解决冲突，空单元用EMPTY，删除标记用DELETED， 占用单元用INUSE，其他均符合哈希表标准操作。插入、删除都以查找为基础，这里只给出查找的核心语 句如下： i=H(key)； /计算哈希地址 if(HTi=EMPTY)return(false)； /查找失败 else if(HTi=key)return (t

20、rue)； elsej=(i+1)%m；/形成探测序列 while(j!=i) /至多循环哈希表长 if(HTj. =key)return (true)； /查找成功 else if(HTj=EMPTY)return(false)；/查找失败j=(j+1)%m； return (false) ；/查遍哈希表，未查到给定关键字key / else)20. 设给定关键字输入序列为(100，90，120，60，78，35，42，31，15)用散列法散列010的地址区间。 要求设计一合理的散列函数；冲突时用链表法解决,写出散列算法，并构造出散列表，在等概率查找情况下 查找成功的平均查找长度是多少?【东北大学1996四(12分)】 正确答案：(正确答案：用链地址法解决冲突，构造散列表，散列函数用H(key)=key%11。核心语句如下： for(i=0； ikey=x； if(rail=null)HTj=p； 第一个数据结点 else while(rail一next!=null)rail=rail 一next；/查找同义词链表尾rail 一next=p；/将插入结点链入同义词表 查找成功时的平均查找长度 ASL=129。 )