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

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

(总分：82.00，做题时间：90分钟)

一、综合题(总题数：25，分数：72.00)

1.试用关键字序列(33，10，45，20，53，43，31，15，65，40)，构造哈希(Hash)表，设哈希函数为：H(key)=key％11，其中key为关键字，％为求余运算符；用开放定址法处理冲突，用线性探测再散列法查找空位，用长度为14的数据元素组A[14]表示哈希表。(1)画出该哈希表的存储结构图；(2)假定每个元素的查找概率相等，计算查找成功时的ASL；(3)计算查找不成功时的ASL。【华中科技大学2007四、25(10分)】（分数：2.00）

__________________________________________________________________________________________ 2.采用哈希函数H(k)=3*k mod 13并用线性探测开放地址法处理冲突，在散列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51。(1)构造哈希表(画示意图)；(2)装填因子；等概率下(3)成功的和(4)不成功的平均查找长度。【北京工业大学2000三(8分)】【烟台大学2007四、4(10分)】（分数：2.00）

__________________________________________________________________________________________ 3.设散列表长度为14，散列函数（分数：2.00）

__________________________________________________________________________________________ 4.常用的构造哈希函数的方法有哪些?若在哈希表中删除一个记录，应如何操作?为什么?已知一组关键字为(19，14，23，01，68，20，84，27，55，11，10，79)，按哈希函数H(Key)=KeyMOD 13和线性探测再散列处理冲突的方法在地址空间A[0．．15]中构造哈希表。【燕山大学1999八(14分)】（分数：2.00） __________________________________________________________________________________________ 5.解答题。【中国海洋大学2006六(15分)】 (1)画出对长度为10的有序表进行折半查找的查找树，并求其等概率时查找成功的平均查找长度。 (2)设有一组关键字{9，01，23，14，55，20，84，27}，采用哈希函数：H(key)=key MOD 7，表长为10，用开放地址法的二次探测再散列方法胁=H(key)+di)MOD 10(di=1 ，2 ，3 ，…)解决冲突。要求：对该关键字序列构造哈希表，指出有哪些同义词并计算查找成功的平均查找长度。（分数：2.00）

__________________________________________________________________________________________ 6.设哈希表的长度为15，哈希函数H(k)=k mod 13，散列地址空间为0～14，对关键字序列(19，5，21，24，45，20，68，27，70，11，10)，按线性探测再散列解决冲突的方法构造哈希表，写出构造后的哈希表，并求出等概率下查找成功和查找不成功时的平均查找长度。【北京交通大学2006四、5(5分)】（分数：2.00）

__________________________________________________________________________________________ 设哈希函数为：H(key)=key mod 13，其中key为关键字；mod为取模运算，试用关键字序列(39，25，15，54，26，24，14，21，37，38)构造哈希表：（分数：4.00）

(1).用链地址法处理冲突，画出该哈希表的存储结构图；假定每个记录的查找概率相等，计算查找成功时的平均查找长度；（分数：2.00）

__________________________________________________________________________________________ (2).设表地址范围为0～13，用线性探测再散列法处理冲突，画出该哈希表的存储结构图；假定每个记录的查找概率相等，计算查找成功时的平均查找长度。【华中科技大学2006四、4(12分)】（分数：2.00） __________________________________________________________________________________________ 7.设开放定址哈希表的表长为10，表中元素的编号从0到9，设初始时表为空。作图表示出采用二次探测处理冲突时，将关键词89，1 8，49，58，69依次插入到该表中的过程。同时要求对每一步给出简要的说明。【中南大学2005四、5(10分)】（分数：2.00）

__________________________________________________________________________________________ 8.若散列函数为H(key)=f MOD 7，其中，i为关键字key的第一个字母在英文字母表中的序号，并且采用线性探测再散列方法处理冲突。请画出在一个初始状态为空，地址值域为[0．．6]的散列表中依次插入下

2

2

2

答案见麦多课文库

列关键字MON，TUE，WED，THU，FRI，SAT,SUN以后的散列表。【北京航空航天大学2005一(10分)】（分数：2.00）

__________________________________________________________________________________________ 9.使用散列函数hash(x)xmod 11，把一个整数值转换成散列表下标，现要把数据：1，13，12，34，38，33，27，22插入到散列表中。(1)使用线性探查再散列法来构造散列表。(5分)(2)使用链地址法构造散列表。(5分)(3)针对这两种情况，确定其装填因子，查找成功所需的平均探查次数，以及查找不成功所需的平均探查次数。(5分)【清华大学1998五(1 5分)】（分数：2.00）

__________________________________________________________________________________________ 10.设散列函数H(k)=k mod 7，散列表的地址空间为0～6，对关键字序列{32，13，49，18，22，38，21}按链地址法处理冲突的办法构造哈希表，并指出查找各关键字要进行几次比较。【西安电子科技大学1999计算机应用一、5(5分)】（分数：2.00）

__________________________________________________________________________________________ 11.选取哈希函数H(key)=key mod 7，用链地址法解决冲突。试在0～6的散列地址空间内对关键字序列{31，23，17，27，19，11，13，91，61，41}构造哈希表，并计算在等概率下成功查找的平均查找长度。【大连海事大学2001八(10分)】（分数：2.00）

__________________________________________________________________________________________ 设哈希(Hash)表的地址范围为0～17，哈希函数为：H(K)=K MOD 16，K为关键字，用线性探测再散列法处理冲突，输入关键字序列：(10，24，32，17，31，30，46，47，40，63，49)，造出哈希表，试回答下列问题：（分数：8.00）

(1).画出哈希表示意图。（分数：2.00）

__________________________________________________________________________________________ (2).若查找关键字63，需要依次与哪些关键字比较?（分数：2.00）

__________________________________________________________________________________________ (3).若查找关键字60，需要依次与哪些关键字比较?（分数：2.00）

__________________________________________________________________________________________ (4).假定每个关键字的查找概率相等，求查找成功时的平均查找长度。【华中理工大学1999三(10分)】【江苏大学2006三、3(11分)】（分数：2.00）

__________________________________________________________________________________________ 12.试为下列关键字设计哈希表，要求所设计的表在查找成功时的平均查找长度不超过2．0。并请验证你造的哈希表的实际平均查找长度是否满足要求。(CHA，CAI，LAN，WEN，LONGZHAO，WU，LIU，CHEN，LI，WANG CAO，YUN，CHANG YANG)【清华大学1996五】（分数：2.00）

__________________________________________________________________________________________ 设a，b，c，d，e五个字符的编码分别为1，2，3，4，5，并设标识符依以下次序出现：ac，bd，aa，be，ab，ad，cd，bc，ae，ce。要求用哈希(Hash)方法将它们存入具有10个位置的表中。（分数：4.00） (1).将上述关键字(标识符)构造一个哈希函数，使得发生冲突尽可能地少；（分数：2.00）

__________________________________________________________________________________________ (2).线性探测再散列法解决冲突。写出上述各关键字在表中的位置。【南开大学1998六(10分)】（分数：2.00）

__________________________________________________________________________________________ 13.对以下关键字序列建立哈希表： (SUN，MON，TUE，WED，THU，FRI，SAT)，哈希函数为H(K)=(关键字中第一个字母在字母表中的序号)MOD 7，用线性探测法处理冲突，求构造一个装填因子为0．7的哈希表；并分别计算出在等概率情况下查找成功与不成功的平均查找长度。【西北大学2000二、3(5分)】（分数：2.00）

__________________________________________________________________________________________ 设散列表为HT[0．．12]，即表的大小为m=13。现采用双散列法解决冲突。散列函数和再散列函数分别为： H 0 (key)=key％13；注：％是求余数运算(=mod) H i (H i-1 +REV(key+1)％1 1+1)％13； i=1，2，3，…，m一1 其中，函数REV∽表示颠倒10进制数x的各位，如REV(37)=73，REV(7)=7等。若插入的关键字序列为(2，8，31，20，19，18，53，27)。（分数：4.00） (1).(8分)试画出插入这8个关键字后的散列表；（分数：2.00）

答案见麦多课文库

__________________________________________________________________________________________ (2).(5分)计算搜索成功的平均搜索长度ASL。【清华大学2000八(13分)】（分数：2.00）

__________________________________________________________________________________________ 设一个散列表含hashsize=13个表项，其下标从0到12，采用线性探查法解决冲突。请按以下要求，将关键字{10，100，32，45，58，126，3，29，200，400，0}散列到表中。（分数：4.00）

(1).散列函数采用除留余数法，用％hashsize(取余运算)将各关键字映像到表中，请指出每一个产生冲突的关键字可能产生多少次冲突。(7分)（分数：2.00）

__________________________________________________________________________________________ (2).散列函数采用先将关键字各位数字折叠相加，再用％hashsize将相加的结果映像到表中的办法。请指出每一个产生冲突的关键字可能产生多少次冲突。(8分)【清华大学2001五(15分)】（分数：2.00） __________________________________________________________________________________________ 14.有关键字集合K={15，22，50，13，20，36，28，48，35，31，41，18}采用散列存取，散列函数HT[0．．14]。设散列函数H(K)=K MOD 13，解决冲突采用开放定址法中的二次探测再散列的方法。试将K值填入HT表中，并把查找每个关键字所需比较次数m填入下表中，并请计算出查找成功时的平均查找长度。【中国海洋大学2005六(12分)】（分数：2.00）

__________________________________________________________________________________________ 已知一组关键字为(26，36，41，38，44，15，68，12，06，51，25)，用链地址法解决冲突。假设装填因子a=0．75，散列函数的形式为脚H(K)=KMOD P，回答下列问题：（分数：6.00） (1).构造出散列函数；(3分)（分数：2.00）

__________________________________________________________________________________________ (2).计算出等概率情况下查找成功的平均查找长度；(3分)（分数：2.00）

__________________________________________________________________________________________ (3).计算出等概率情况下查找失败的平均查找长度。(3分)【东北大学1999一、3(9分)】（分数：2.00） __________________________________________________________________________________________ 15.设哈希表的长度为11，哈希函数H(K)=K mod 11，散列地址空间为0～10，对关键字序列(32，13，49，38，21，60，12)，按二次探测(平方探测)再散列解决冲突的方法构造哈希表，写出构造后的哈希表，并求出等概率下查找成功的平均查找长度。【北京交通大学2005五、6(5分)】（分数：2.00）

__________________________________________________________________________________________ 由14个关键字(87，25，310，08，27，132，68，96，187，133，70，63，47，135)构造链地址法处理冲突的哈希表，哈希函数为H（key)=key MOD 13，完成下列工作。（分数：4.00） (1).画出该哈希表，并求其查找成功的平均查找长度ASL；（分数：2.00）

__________________________________________________________________________________________ (2).在该哈希表中，若要删除值为70的关键字，统计需要进行的比较操作次数。【北京工业大学2005三、3(8分)】（分数：2.00）

__________________________________________________________________________________________ 给定关键字序列(26，25，20，33，21，24，45，204，42，38，29，31)，要用散列法进行存储，规定负载因子a=0．6。（分数：4.00）

(1).请给出除余法的散列函数。（分数：2.00）

__________________________________________________________________________________________ (2).用开地址线性探测法解决碰撞，请画出插入所有的关键字后得到的散列表，并指出发生碰撞的次数。【北京大学1997三(6分)】（分数：2.00）

__________________________________________________________________________________________ 16.已知记录关键字集合为(53，17，19，6l，98，75，79，63，46，49)要求散列到地址区间(100，101，102，103，104，105，106，107，108，109)内，若产生冲突用开型寻址法的线性探测法解决。要求写出选用的散列函数；形成的散列表；计算出查找成功时平均查找长度与查找不成功的平均查找长度。(设等概率情况)【东北大学1998一、2(10分)】（分数：2.00）

__________________________________________________________________________________________

答案见麦多课文库

17.Fibonacci树是一种特殊的二叉树，下面给出构造该树的一种算法： procedure FibonacciTree(d： integer； Var T： binarytree) (／／d是Fibonacci树的深度 if d=0 then T：=nil else{new(T)； if d=1 then (T^．lefptr：=nil； T^．rightptr：=nil ) else { ／／d>=2 FibonacciTree(d一2， T^．1eftptr)； FibonacciTree(d一1， T^．rightptr)； } } } (1)画出深度为4的Fibonacci树(即用d=4调用上述算法的结果)。(7分) (2)从你画的树中分析深度为d的Fibonacci树中结点总数和Hbonacci数的关系。 Fibonacci数定义如下： F n =1， F 1 =1 F n =F n-1 +F n-2 n>1 (3)你所画出的Fibonacci树是否为平衡二叉树?若是，它是否为同样深度的平衡二叉树中结点数目最少的一种?(4分)【中国科学技术大学1998三(15分)】（分数：2.00）

__________________________________________________________________________________________

二、设计题(总题数：4，分数：10.00)

已知某哈希表HT的装填因子小于1，哈希函数H(key)为关键字的第一个字母在字母表中的序号。【西北大学2001五】（分数：4.00）

(1).处理冲突的方法为线性探测开放地址法。编写一个按第一个字母的顺序输出哈希表中所有关键字的程序。（分数：2.00）

__________________________________________________________________________________________ (2).处理冲突的方法为链地址法。编写一个计算在等概率情况下查找不成功的平均查找长度的算法。注意，此算法中规定不能用公式直接求解计算。（分数：2.00）

__________________________________________________________________________________________ 18.有一个100 100的稀疏矩阵，其中1％的元素为非零元素，现要求用哈希表作存储结构。 (1)请你设计一个哈希表。 (2)请写一个对你所设计的哈希表中给定行值和列值存取矩阵元素的算法；并对你的算法所需时间和用一维数组(每个分量存放一个非零元素的行值、列值和元素值)作存储结构时存取元素的算法(注：此算法不需要写出，仅需说明存取的方法和所用时间)进行比较。【北方交通大学1994六(16分)】（分数：2.00）

__________________________________________________________________________________________ 19.将一组数据元素按哈希函数H(key)散列到哈希表HT(0：m)中，用线性探测法处理冲突H(key)+1，H(key)+2，…，H(key)一1)，假设空单元用EMPTY表示，删除操作是将哈希表中结点标志位从INUSE标记为DELETED，试写出该散列表的查找、插入和删除三个基本操作算法。【北京邮电大学2001五、2(10分)】（分数：2.00）

__________________________________________________________________________________________ 20.设给定关键字输入序列为(100，90，120，60，78，35，42，31，15)用散列法散列0～10的地址区间。要求设计一合理的散列函数；冲突时用链表法解决,写出散列算法，并构造出散列表，在等概率查找情况下查找成功的平均查找长度是多少?【东北大学1996四(12分)】（分数：2.00）

__________________________________________________________________________________________

*

答案见麦多课文库