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

计算机专业基础综合数据结构（集合）历年真题试卷汇编8（总分:70.00，做题时间：90分钟）一、综合题（总题数：26，分数：54.00）巳知长度为11的表（xal，wan，wil，zol，yo，xul，yum，wen，wim，zi，yon），按表中元素顺序依次插入一棵初始为空的平衡二叉排序树，画出插入完成后的平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。【山东大学2001七（7分）】（分数：2.00）正确答案：（正确答案:解析：SLsucc正确答案：（正确答案:解析：SLsucc=(1*1+2*2+4*3+4*4)/11=33/11)用关键字1，2,3,4的四个结点（1）能构造出几种不同的二叉排序树?其中（2）最优查找树有几种？（3）AVL树有几种？（4）完全二叉树有几种?试画出这些二叉排序树。【北京工业大学1997二、3（5分）】（分数：2.00）正确答案：（正确答案：（1）本题的实质是给定中序序列1、2、3、4,有几种不同的二叉排序树，即该中序序列相当于多少不同的前序序列，这是树的计数问题樱中序序列中元素数为n，则二又数的数目为1/（n+1）C2nn，这里n=4,故有14种。图示如下： 2）最优查找树有4种，图中（10）、（11）、（12）、（13）。（3）AVL树也有4种，图中（10）、（11）、（12）、（13）。（4）完全二叉树有1种，图中（10）。）解析：可以生成下图所示的二叉排序树的关键字初始序列有几种?试写出其中的任意4种。【电子科技大学2005A三、2（6分）】-I（分数：2.00）正确答案：（正确答案：8种（1）8,9,4,2,6（2）8,9,4,6,2（3）8,4,2,6,9（4）8,4,2,9,6（5）8，4，6,2,9（6）8,4,6,9,2（7）8,4,9,2,6（8）8,4,9,6,2）解析：设二叉排序树中关键字由1到1000的整数组成，现要查找关键字为363的结点，下述关键字序列哪一个不可能是在二叉排序树中查到的序列？说明原因。（1）51，250，501，390，320，340，382,363（2）24,877，125，342，501，623，421，363【东北大学2002一、3（4分）】（分数：2.00）正确答案：（正确答案：序列（2）不可能是二叉排序树中查到363的序列。查到501后，因363<501，后面应出现小于501的数，但序列中出现了623，故不可能。）解析：一棵具有m层的AVL树至少有多少个结点，最多有多少个结点？【浙江大学1995六（8分）】（分数：2.00）正确答案：（正确答案：设以N.正确答案：（正确答案：设以N.表示深度为m的AVL树中含有的最少结点数。显然，N°=0，N1=LN2=2,且N=N+N+1（mN2）。这个关系与斐波那契序列类似，用归纳法可以证明：当mN0时，N=Fm+2 m m数）。当，层的AVL树是满二叉树时，结点数为最大值2m一1。）解析：设T是一棵高度平衡树（又称平衡树），给定关键词K,如果在T中查找K失败，且查找路径上的任一结点的平衡系数皆为零，试回答用高度平衡树插入算法在T中插入关键词为K的新结点后，树T的高度是否一定增加?并回答为什么。【吉林大学1996四、2（7分）】（分数：2.00）正确答案：（正确答案：树的高度一定增加。因为“查找路径上的任一结点的平衡系数皆为零”，从根结点开始查找，根结点的平衡因子为零，说明根的左右子树等高（不一定是满二叉树）。沿左（或右）子树向下查找时，查找路径上所有结点的平衡因子皆为零，说明任一结点的左右子树等高，查找失败是在叶子结点，插入也是在叶子结点，树的高度自然增加。）解析：试画出从空树开始，由字符序列（t，d，e，s，u，g，b,—j，k，r，i）构成的二叉平衡树，并为每一次的平衡处理指明旋转类型。【清华大学1994三（10分）】在B一树和B+树中查找关键字时，有什么不同？【东北大学2002一、5（2分）】（分数：2.00）正确答案：（正确答案：在B一树中查找关键字从根结点开始，从根往下查找结点，然后在结点内查找关键字，得出查找成功与否的结论。B+树的非终端结点是索引部分，其查找从根开始，从根往下查到关键字后，要继续查到最下层结点，得到查找成功与否的结论。另外，B+树还可以在最下层从最小关键字开始，从左往右进行顺序查找，B一树则不能作顺序查找。）解析：简要叙述B树（有些教材中称为B一树）与B+树的区别。【南京航空航天大学1999六（5分）】（分数：2.00）正确答案：（正确答案：m阶的B+树和B一树主要区别有三：（1）有n棵子树的结点中含有n（B一树中n—1）个关键字；（2）B+树叶子结点包含了全部关键字信息，及指向含关键字记录的指针，且叶子结点本身依关键字大小自小到大顺序链接，B一树的叶子结点是失败结点，实际不存在；（3）B+树的非终端结点可以看成是索引部分，结点中只含其子树（根结点）中最大（或最小）关键字。B+树的查找既可以顺序查找，也可以随机查找，B一树只能随机查找。）解析：当B一树作为文件的索引时，一个结点除了包含关键字和指向孩子结点的指针外，还包含指向文件记录的指针。假设一个结点占用的最大空间被限定为4096字节，每个关键字和每个指针都占2字节。如果采用n阶B树作为文件的索引，则它的最大的阶数应该是多少？【北京理工大学2006十一、5（5分）】（分数：2.00）正确答案：（正确答案：因为每个非终端结点中包含下列信息数据（n，P0，K1，P1，K2，P2，…，Kn，Pn），其中n是关键字个数，P0指向关键字比K1小的结点，（Kj，Pi）（1WiWn）成对出现，按题意，，结点中还包含指向文件记录的指针，即一个关键字要占用6字节：每个结点还包括该结点的关键字个数和小于第一个关键字的指针。故最大阶数应是（4096—4）/6=682。）解析：证明：高为h（不含叶子层）的m阶B一树上最多有mh一1个关键字。【北京交通大学2006四、2（5分）】（分数：2.00）正确答案：（正确答案：m阶正确答案：（正确答案：m阶B树的每个结点最多有m1个关键字，第一层m—1个关键字，第二层m（m一1）个关键字，第三层m2（m—1）个关键字，……，第h层mi（m—1）个关键字。将各层关键字数相加，得证。）解析：满二叉检索树符合B树定义吗?B树的插入和删除算法适用于满二叉检索树吗?为何？【东南大学1995五（6分）】（分数：2.00）正确答案：（正确答案：满二叉检索树可以看作是三阶B一树（2—3树）。B一树的插入和删除算法不适合满二叉检索树。满二叉检索树插入和删除结点后均破坏了“多路平衡查找树”“叶子在同一层上”（查找失败结点）的定义。）解析：含9个叶子结点的3阶B一树中至少有多少个非叶子结点?含10个叶子结点的3阶B一树中至多有多少个非叶子结点？【东南大学2005一、1（5分）】【北京轻工业学院2000八（10分）】（分数：2.00）正确答案：（正确答案：含9个叶子结点的3阶B一树至少有4个非叶子结点，当每个非叶子结点均含3棵子树，第三层是叶子结点时就是这种情况。当4层3阶B一树有10个叶子结点时，非叶子结点达到最大值8个：其中第一层1个，第二层2个，第三层5个。）解析：设依以下次序给出关键字：34，16，19，21，5，49，24，62，3，17，45，8，构造3阶B一树。要求从空树开始，每插入一个关键字，画出一个树形。【南开大学1997六（10分）】15.对下面的3阶15.对下面的3阶B一树，依次执行下列操作，画出各步操作的结果。【合肥工业大学1999四、3（5分）】（1）插入90（2）插入25（3）插入45⑷删除60（5）删除80（分数：2.00）正确答案：（正确答案：解析：（2）.对树（b），请分别画出（分数：2.00）正确答案：（正确答案：解析：（2）.对树（b），请分别画出先后删除53,37两个结点后的树形。（分数：2.00）16.阶B树中（如图所示），插入关键字87,试画出插入调整后树的形状。【东南大学1999五（15分）】（分数：2.00）设有关键码序列10,20,35,40,44,51,65,70,85,91,93,95。试按照最大关键码复写原则绘出相应的2阶B+树。【山东工业大学1996二、1（6分）】回答问题并填空。（1）（2分）散列表存储的基本思想是什么？（2）（4分）散列表存储中解决碰撞的基本方法有哪些?其基本思想是什么？（3）（4分）用分离的同义词子表解决碰撞和用结合的同义词表解决碰撞属于哪种基本方法?他们各有何特点？（4）（3分）用线性探查法解决碰撞时，如何处理被删除的结点?为什么？（5）（2分）散列法的平均检索长度不随（）的增加而增加，而是随（）的增大而增加。【山东工业大学1999四（15分）】（分数：2.00）正确答案：（正确答案：（1）哈希表存储的基本思想是用关键字的值决定数据元素的存储地址。（2）哈希表存储中解决碰撞的基本方法：①开放定址法。形成地址序列的公式是：H「=（H（key）+dj）%m，其中m是表长，d「是增量。根据d「取法不同，又分为三种：a.d「=1,2,…，m—1称为线性探测再哈希，其特点是逐个探测表空间，只要哈希表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一哈希地址。b.d.=12,一-12,22,一-22,..•，土k2（kWm/2）称为二次探测再哈希，它减少了聚集，但不容易探测到全部表空间，只有当表长为形如4j+3（,为整数）的素数时才有可能。c.d.=伪随机数序列，称为随机探测再哈希。②再哈希法。H.=RH.（key）i=1,2,…，k,是不同的哈希函数，即在同义词产生碰撞时，用另一哈希函数计算哈希地址，直到解决碰撞。该方法不易产生“聚集”，但增加了计算时间。③链地址法。将关键字为同义词的记录存储在同一链表中，哈希表地址区间用研0—..m—1］表示，哈希表元素初始值为空指针。凡哈希地址为f（0WiWm—1）的记录均插在以研［i］为头指针的链表中。这种解决方法中数据元素个数不受表长限制，插入和删除操作方便，但增加了指针的空间开销。这种哈希表常称为开哈希表，“开”的含义是哈希表无边界，元素个数没限制，哈希表不会溢出，只受存储空间限制。而①中的哈希表称闭哈希表，“闭”含义是元素个数受表长限制。④建立公共溢出区。设H［0一m一1］为基本表，凡关键字为同义词的记录，都填入溢出区O［0..m—1］。（3）用分离的同义词表和结合的同义词表解决碰撞均属于链地址法。链地址向量空间中的每个元素不是简单的地址，而是关键字和指针两个域，哈希地址为i（0WiWm—1）的第一个关键字存储在地址空间向量下标为i的“关键字”域。前者的指针域是动态指针，指向同义词的链表，具有上面③的优缺点；后者实际是静态链表，同义词存在同一地址向量空间（从最后向前找空闲单元），以静态指针（下标）相连。这节省了空间，但易产生“堆积”，查找效率低。（4）要在被删除结点的哈希地址处作标记，不能物理地删除。否则，中断了查找通路。（5）记录、负载因子）解析：如何衡量Hash函数的优劣?简要叙述Hash表技术中的冲突概念，并指出三种解决冲突的方法。【南京航空航天大学1996九、2（6分）】（分数：2.00）

正确答案：（正确答案：评价哈希函数优劣的因素有：能否将关键字均匀影射到哈希空间上，有无好的解决冲突的方法，计算哈希函数是否简单高效。由于哈希函数是压缩映像，冲突难以避免。解决冲突的方法见上面52题（2）。）解析：Hash方法的平均查找路长决定于什么？是否与结点个数N有关?处理冲突的方法主要有哪些？【中国人民大学2000一、4（4分）】（分数：2.00）正确答案：（正确答案：哈希方法的平均查找路长主要取决于负载因子（表中实有元素数与表长之比），它反映了哈希表的装填程度，该值一般取0.65〜0.9。解决冲突方法见上面52题（2）。）解析：在采用线性探测法处理冲突的散列表中，所有同义词在表中是否一定相邻？【西安电子科技大学2000计算机应用一、8（5分）】（分数：2.00）正确答案：（正确答案：不一定相邻。哈希地址为i（0WiWm—1）的关键字，和为解决冲突形成的探测序列i的同义词，都争夺哈希地址i。）解析：假定有k个关键字互为同义词，若用线性探测法将这k个关键字存入散列表中，至少需要进行多少次探测？【厦门大学2006四、2（25/3分）】（分数：2.00）正确答案：（正确答案：k（k+1）/2。每次探测的次数依次是1，2,…，k。）解析：设有一组关键字｛9，01，23，14，55，20，84，27），采用哈希函数：H（key）=keymod7，表长为10，用开放地址法的二次探测再散列方法Hi=（H（key）+di）mod10（di=12，22，32，…）解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。【东北大学2002二、2（5分）】（分数：2.00）:ASL:ASL=(1+1+1+2+3+4+1+2)/8=15/8以关键字27为例:SUCC2=(6+22)%10=0(冲突)，H3=(6+33)%10=5,H（27）=27%7=6（冲突），H1=（6+1）%10=7（冲突），H所以比较了4次。） 1解析：对下面的关键字集｛30，15，21，40，25，26，36，37｝，若查找表的装填因子为0.8，采用线性探测再散列方法解决冲突。（1）设计哈希函数；（2）画出哈希表；（3）计算查找成功和查找失败的平均查找长度;（4）写出将哈希表中某个数据元素删除的算法。【东北大学2001六（18分）】（分数：2.00）正确答案：（正确答案：由于装填因子为0.8,关键字有8个，所以表长为8/0.8=10。（1）用除留余数法，哈希函数为H（key）=key%7。（2）——（3）计算查找失败时的平均查找长度，必须计算不在表中的关键字，当其哈希地址为i（0WiWm—1）时的查找次数。本例中虽然m=10，但真正的哈希地址是0〜6。故查找失败和查找成功时的平均查找长度分别为：ASL=（9+8+7+6+5+4+3）/7=6ASL=16/8=2（4）intUNSUCC SUCCdelete（inth[n]，intk）//从哈希表h[n]中删除元素k，若删除成功返回1，否则返回.｛i=k%7；//哈希函数用H（key）=key%7if（h[i]==maxint｝//maxint解释成空地址｛count＜）解析：二、设计题（总题数：8,分数：16.00）假设一棵平衡二叉树的每个结点都标明平衡因子，试设计一个非递归算法，利用平衡因子，求平衡二叉树的高度。【南京航空航天大学2003八（10分）】（分数：2.00）正确答案：（正确答案：算法的核心语句段如下：while（p）//求平衡二叉树高度，初值是根结点的指针（1evel++；//树的高度增1，level初值是0if（p—>bfrchild；llbf=-1沿右分支向下elsep=p一>Ichild；//bf>=0沿左分支向下}//while）解析：在平衡二叉排序树的每个结点中增设一个lsize域，其值为它的左子树的结点数加1。试写一时间复杂度为D（10gn）的算法，确定树中第尼个结点的位置。【大连理工大学2005三、2（45/3分）】（分数：2.00）正确答案：（正确答案：设平衡二叉排序树根结点的指针是pbst，（1）若pbst一>lsize=k，则根结点即为所求；（2）按根结点的位序与k的关系，k小到左（大到右）子树去查找：根结点的左右子女分别是第pbst一>lchild—>lsize和pbst->lsize+pbst—>rchild->lsize个结点。）解析：在二又链表的每个结点中添加一个域intdepth，表示以该结点为根的子树的深度（结构编者略）。（1）试编写一递归函数。BiTreeDepth（BiTreeT），计算二叉树T中每个结点的depth值，函数的返回值为树T的深度。（2）在（1）的基础上（即巳求出二叉树中每个结点的depth值），编写一递归函数BiTreeBalance（BiTreeT），判断二叉排序树T是否为平衡二叉树，如果是平衡二叉树，则函数的返回值为真。【北京理工大学2006十^一、2（25/2分）】（分数：2.00）正确答案：（正确答案：（1）设根的层数为1，进行遍历，在遍历中填写结点的层数，结点的最大层次就是所求。（2）若任一结点其左右子女的层次差的绝对值大于1，则不是平衡二叉排序树。voidBiTreeDep七h（BiTreeT，intdepth）{if（!T）return0else{T—>depth++；if（T—>depth>maxdepth）maxdepth=T—>depth；//maxdepth是全局变量，初值0if（T—>Ichild）BiTreeDepth（T—>Ichild，depth+1）；//左子树上各结点的层次if（T—>rchild）BiTreeDepth（T—>rchild，depth+1）；//右子树上各结点的层次}}//使用BiTreeDepth（T，0）调用）解析：（1）设二叉排序树中关键字由1至1000的整数组成，现要检索关键字为363的结点，下述关键字序列中哪些可能是二叉排序树上搜索到的序列，哪些不可能是二叉排序树上搜索到的序列？a.2,252,401，398,330，344,397,363b.924,220，911，244,898,258,362,363c.925,202,911，240，912,245,363d.2，399，387,219,266,382,381,278,363（2）通过对（1）的分析，写一个算法判定给定的关键字序列（假定关键字互不相同）是否可能是二叉排序树的搜索序列。若可能是返回真，否则返回假。可假定被判定的序列巳存入数组中。【中国科学技术大学1998】（分数：2.00）正确答案：（正确答案：（1）A、B、D有可能是二叉排序树的查找序列。C不可能是。（2）二叉排序树的查找走了一条从根结点到子孙结点的路径。查找开始时首先和根结点的值比较，若根结点的值大于待查结点的值，则到左子树中查找，否则到右子树中查找。子树根结点的值和待查结点值的比较，也遵循如上规律。在查找过程中逐渐缩小查找范围。我们用high表示查找的上界，用low表示查找的下界，若low>high,则不是二叉排序树的查找序列。算法的核心语句段如下：low=preLow=—maxint,high=preHigh=maxint；//max是机器最大数while（low<high&&ilow&&icn）//相当于沿右子女方向走，在某结点左转时退出{preLow=low；low=a[i++]）if（i<high&&i<high）；）解析：设二叉树以二又链表形式存放，一棵二又树的繁茂程度定义为各层结点数的最大值与树的高度的乘积。试设计一个高效算法，求二叉树的繁茂程度。【大连理工大学2008三、3（10分）】（分数：2.00）正确答案：（正确答案：本题实际是找大于等于item的最小元素，找到就成功。失败时，若在表尾，则返回0,否则此位置就为所求。算法核心语句段如下：intlow=1，high=n； //必须大于0,否则出错while（low<=high）｛mid=（10w+high）/2；if（item>R[mid]）low=mid+1；elseif（item解析：请用类C或