1、计算机专业基础综合数据结构（集合）历年真题试卷汇编 8及答案解析(总分：70.00，做题时间：90 分钟)一、综合题(总题数：26，分数：54.00)1.已知长度为 11的表(xal，wan，wil，zol，yo，xul，yum，wen，wim，zi，yon)，按表中元素顺序依次插入一棵初始为空的平衡二叉排序树，画出插入完成后的平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。【山东大学 2001七(7 分)】（分数：2.00）_2.用关键字 1，2，3，4 的四个结点(1)能构造出几种不同的二叉排序树?其中(2)最优查找树有几种?(3)AVL树有几种?(4)完全二叉树有几种?试画
2、出这些二叉排序树。【北京工业大学 1997二、3(5 分)】（分数：2.00）_3.可以生成下图所示的二叉排序树的关键字初始序列有几种?试写出其中的任意 4种。【电子科技大学2005三、2(6 分)】 （分数：2.00）_4.设二叉排序树中关键字由 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）_5.一棵具有 m层的 AVL树至少有多
3、少个结点，最多有多少个结点? 【浙江大学 1995六(8 分)】（分数：2.00）_6.设 T是一棵高度平衡树(又称平衡树)，给定关键词 K，如果在 T中查找 K失败，且查找路径上的任一结点的平衡系数皆为零，试回答用高度平衡树插入算法在 T中插入关键词为 K的新结点后，树 T的高度是否一定增加?并回答为什么。【吉林大学 1996四、2(7 分)】（分数：2.00）_7.试画出从空树开始，由字符序列(t，d，e，s，u，g，b,一 j，k，r，i)构成的二叉平衡树，并为每一次的平衡处理指明旋转类型。【清华大学 1994三(10 分)】（分数：2.00）_8.在 B一树和 B+树中查找关键字时，有
4、什么不同?【东北大学 2002一、5(2 分)】（分数：2.00）_9.简要叙述 B树(有些教材中称为 B一树)与 B+树的区别。【南京航空航天大学 1999六(5 分)】（分数：2.00）_10.当 B一树作为文件的索引时，一个结点除了包含关键字和指向孩子结点的指针外，还包含指向文件记录的指针。假设一个结点占用的最大空间被限定为 4096字节，每个关键字和每个指针都占 2字节。如果采用 n阶 B树作为文件的索引，则它的最大的阶数应该是多少?【北京理工大学 2006十一、5(5 分)】（分数：2.00）_11.证明：高为 h(不含叶子层)的 m阶 B一树上最多有 m h 一 1个关键字。【北京
5、交通大学 2006四、2(5分)】（分数：2.00）_12.满二叉检索树符合 B树定义吗?B 树的插入和删除算法适用于满二叉检索树吗?为何?【东南大学 1995五(6 分)】（分数：2.00）_13.含 9个叶子结点的 3阶 B一树中至少有多少个非叶子结点?含 10个叶子结点的 3阶 B一树中至多有多少个非叶子结点?【东南大学 2005一、1(5 分)】【北京轻工业学院 2000八(10 分)】（分数：2.00）_14.设依以下次序给出关键字：34，16，19，21，5，49，24，62，3，17，45，8，构造 3阶 B一树。要求从空树开始，每插入一个关键字，画出一个树形。【南开大学 199
6、7六(10 分)】（分数：2.00）_15.对下面的 3阶 B一树，依次执行下列操作，画出各步操作的结果。【合肥工业大学 1999四、3(5 分)】(1)插入 90 (2)插入 25 (3)插入 45 (4)删除 60 (5)删除 80 （分数：2.00）_已知 2棵 23 B一树如下(省略外结点)。 （分数：4.00）(1).对树(a)，请分别画出 先后插入 26，85 两个新结点后的树形；（分数：2.00）_(2).对树(b)，请分别画出 先后删除 53，37 两个结点后的树形。（分数：2.00）_16.阶 B树中(如图所示)，插入关键字 87，试画出插入调整后树的形状。【东南大学 199
7、9五(1 5 分)】（分数：2.00）_17.下图是 5阶 B树，画出删去 P后的 B树，再画出删去 D后的 B树。【厦门大学 2000七、3(203 分)】（分数：2.00）_18.设有关键码序列 10，20，35，40，44，51，65，70，85，91，93，95。试按照最大关键码复写原则绘出相应的 2阶 B+树。【山东工业大学 1 996二、1(6 分)】（分数：2.00）_19.回答问题并填空。(1)(2 分)散列表存储的基本思想是什么?(2)(4 分)散列表存储中解决碰撞的基本方法有哪些?其基本思想是什么?(3)(4 分)用分离的同义词子表解决碰撞和用结合的同义词表解决碰撞属于哪种
8、基本方法?他们各有何特点?(4)(3 分)用线性探查法解决碰撞时，如何处理被删除的结点?为什么?(5)(2分)散列法的平均检索长度不随( )的增加而增加，而是随( )的增大而增加。【山东工业大学 1999四(15分)】（分数：2.00）_20.如何衡量 Hash函数的优劣?简要叙述 Hash表技术中的冲突概念，并指出三种解决冲突的方法。【南京航空航天大学 1996九、2(6 分)】（分数：2.00）_21.Hash方法的平均查找路长决定于什么?是否与结点个数 N有关?处理冲突的方法主要有哪些? 【中国人民大学 2000一、4(4 分)】（分数：2.00）_22.在采用线性探测法处理冲突的散列表
9、中，所有同义词在表中是否一定相邻? 【西安电子科技大学 2000计算机应用一、8(5 分)】（分数：2.00）_23.假定有 k个关键字互为同义词，若用线性探测法将这 k个关键字存入散列表中，至少需要进行多少次探测?【厦门大学 2006四、2(253 分)】（分数：2.00）_24.设有一组关键字9，01，23，14，55，20，84，27)，采用哈希函数：H(key)=key mod 7，表长为10，用开放地址法的二次探测再散列方法 Hi=(H(key)+di)mod10(di=1 2 ，2 2 ，3 2 ，)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。【东北大学
10、 2002二、2(5 分)】（分数：2.00）_25.对下面的关键字集30，15，21，40，25，26，36，37，若查找表的装填因子为 08，采用线性探测再散列方法解决冲突。(1)设计哈希函数；(2)画出哈希表；(3)计算查找成功和查找失败的平均查找长度；(4)写出将哈希表中某个数据元素删除的算法。【东北大学 2001六(1 8 分)】（分数：2.00）_二、设计题(总题数：8，分数：16.00)26.假设一棵平衡二叉树的每个结点都标明平衡因子，试设计一个非递归算法，利用平衡因子，求平衡二叉树的高度。【南京航空航天大学 2003八(10 分)】（分数：2.00）_27.在平衡二叉排序树的每
11、个结点中增设一个 lsize域，其值为它的左子树的结点数加 1。试写一时间复杂度为 D(10gn)的算法，确定树中第尼个结点的位置。【大连理工大学 2005三、2 (453 分)】（分数：2.00）_28.在二又链表的每个结点中添加一个域 int depth，表示以该结点为根的子树的深度(结构编者略)。(1)试编写一递归函数。BiTreeDepth(BiTree T)，计算二叉树 T中每个结点的 depth值，函数的返回值为树T的深度。(2)在(1)的基础上(即已求出二叉树中每个结点的 depth值)，编写一递归函数BiTreeBalance(BiTree T)，判断二叉排序树 T是否为平衡二
12、叉树，如果是平衡二叉树，则函数的返回值为真。【北京理工大学 2006十一、2(252 分)】（分数：2.00）_29.(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)的分析，写一个算法判定给定的关
13、键字序列(假定关键字互不相同)是否可能是二叉排序树的搜索序列。若可能是返回真，否则返回假。可假定被判定的序列已存入数组中。【中国科学技术大学 1998】（分数：2.00）_30.设二叉树以二又链表形式存放，一棵二又树的繁茂程度定义为各层结点数的最大值与树的高度的乘积。试设计一个高效算法，求二叉树的繁茂程度。【大连理工大学 2008三、3(10 分)】（分数：2.00）_31.请用类 C或用类 Pascal语言编写算法：键树，又称数字查找树。它是一棵度为2 的树，树中的每个结点中不是包含一个或几个关键字，而是只含有组成关键字的符号。编写一个在键(trie)树 T上查找关键字等于给定值 KEY的记
14、录的算法。若查找成功，返回指向该记录的指针；否则返回空指针。【上海大学2002七、2(10 分)】（分数：2.00）_32.写出从哈希表中删除关键字为 K的一个记录的算法，设哈希函数为 H，解决冲突的方法为链地址法。【上海交通大学 1999五(12 分)】（分数：2.00）_33.在用除余法作为散列函数、线性探测解决冲突的散列表中，写一删除关键字的算法，要求将所有可以前移的元素前移去填充被删除的空位，以保证探测序列不至于断裂。【中科院计算所 2000八(15 分)】（分数：2.00）_计算机专业基础综合数据结构（集合）历年真题试卷汇编 8答案解析(总分：70.00，做题时间：90 分钟)一、综
15、合题(总题数：26，分数：54.00)1.已知长度为 11的表(xal，wan，wil，zol，yo，xul，yum，wen，wim，zi，yon)，按表中元素顺序依次插入一棵初始为空的平衡二叉排序树，画出插入完成后的平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。【山东大学 2001七(7 分)】（分数：2.00）_正确答案：(正确答案： )解析：2.用关键字 1，2，3，4 的四个结点(1)能构造出几种不同的二叉排序树?其中(2)最优查找树有几种?(3)AVL树有几种?(4)完全二叉树有几种?试画出这些二叉排序树。【北京工业大学 1997二、3(5 分)】（分数：2.00）_
16、正确答案：(正确答案：(1)本题的实质是给定中序序列 1、2、3、4，有几种不同的二叉排序树，即该中序序列相当于多少不同的前序序列，这是树的计数问题。设中序序列中元素数为 n，则二又数的数目为1(n+1)C 2n n ，这里 n=4，故有 14种。图示如下： )解析：3.可以生成下图所示的二叉排序树的关键字初始序列有几种?试写出其中的任意 4种。【电子科技大学2005三、2(6 分)】 （分数：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)
17、8，4，9，2，6 (8) 8，4，9，6，2)解析：4.设二叉排序树中关键字由 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后，因 363bfrchild；llbf=-1 沿右分支向下 else p=p一Ichild； bf=0 沿左分支向下 w
18、hile)解析：27.在平衡二叉排序树的每个结点中增设一个 lsize域，其值为它的左子树的结点数加 1。试写一时间复杂度为 D(10gn)的算法，确定树中第尼个结点的位置。【大连理工大学 2005三、2 (453 分)】（分数：2.00）_正确答案：(正确答案：设平衡二叉排序树根结点的指针是 pbst， (1)若 pbst一lsize=k，则根结点即为所求； (2)按根结点的位序与 k的关系，k 小到左(大到右)子树去查找：根结点的左右子女分别是第pbst一lchild 一lsize 和 pbst-lsize+pbst一rchild-lsize 个结点。)解析：28.在二又链表的每个结点中添
19、加一个域 int depth，表示以该结点为根的子树的深度(结构编者略)。(1)试编写一递归函数。BiTreeDepth(BiTree T)，计算二叉树 T中每个结点的 depth值，函数的返回值为树T的深度。(2)在(1)的基础上(即已求出二叉树中每个结点的 depth值)，编写一递归函数BiTreeBalance(BiTree T)，判断二叉排序树 T是否为平衡二叉树，如果是平衡二叉树，则函数的返回值为真。【北京理工大学 2006十一、2(252 分)】（分数：2.00）_正确答案：(正确答案：(1)设根的层数为 1，进行遍历，在遍历中填写结点的层数，结点的最大层次就是所求。 (2)若任一
20、结点其左右子女的层次差的绝对值大于 1，则不是平衡二叉排序树。 void BiTreeDep七 h(BiTree T，int depth) if(!T)return 0； elseT 一depth+； if(T 一depthmaxdepth)maxdepth=T一depth； maxdepth 是全局变量，初值 0 if(T一Ichild)BiTreeDepth(T 一Ichild，depth+1)； 左子树上各结点的层次 if(T 一rchild)BiTreeDepth(T 一rchild，depth+1)；右子树上各结点的层次 使用 BiTreeDepth(T，0)调用)解析：29.(1)
21、设二叉排序树中关键字由 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)的分析，写一个算法判定给定的关键字序列(假定关键字互不相同)是否可能是二叉排序树的搜索序列。若可能是返回真，否则返回假。可假定被判定的序列已存入数组中。【
22、中国科学技术大学 1998】（分数：2.00）_正确答案：(正确答案：(1)A、B、D 有可能是二叉排序树的查找序列。C 不可能是。 (2)二叉排序树的查找走了一条从根结点到子孙结点的路径。查找开始时首先和根结点的值比较，若根结点的值大于待查结点的值，则到左子树中查找，否则到右子树中查找。子树根结点的值和待查结点值的比较，也遵循如上规律。在查找过程中逐渐缩小查找范围。我们用 high表示查找的上界，用 low表示查找的下界，若 lowhigh，则不是二叉排序树的查找序列。算法的核心语句段如下： low=preLow=一maxint，high=preHigh=maxint；max 是机器最大数
23、while(lowRmid)low=mid+1 ； else if(item解析：31.请用类 C或用类 Pascal语言编写算法：键树，又称数字查找树。它是一棵度为2 的树，树中的每个结点中不是包含一个或几个关键字，而是只含有组成关键字的符号。编写一个在键(trie)树 T上查找关键字等于给定值 KEY的记录的算法。若查找成功，返回指向该记录的指针；否则返回空指针。【上海大学2002七、2(10 分)】（分数：2.00）_正确答案：(正确答案：在 Trie树上查找给定值 KEY的过程如下：沿和给定值相应的指针向下，直至叶子结点，若叶子中的关键字和 KEY相等，则查找成功；若分支结点中和给定值
24、相应的指针为空，或叶子结点中的关键字和给定值不等，则查找不成功。)解析：32.写出从哈希表中删除关键字为 K的一个记录的算法，设哈希函数为 H，解决冲突的方法为链地址法。【上海交通大学 1999五(12 分)】（分数：2.00）_正确答案：(正确答案：用链地址法解决冲突的哈希表是一个指针数组，数组分量均是指向单链表的指针，(第 f个)单链表结点有两个域，一个是哈希地址为 f的关键字，另一个是指向同义词结点的指针。删除算法与单链表上删除算法类似。核心语句段如下： i=H(K)； 用哈希函数确定关键字 K的哈希地址 if(HTi=null)COUtnext； if(p=null)coutnext；
25、delete(p)； )解析：33.在用除余法作为散列函数、线性探测解决冲突的散列表中，写一删除关键字的算法，要求将所有可以前移的元素前移去填充被删除的空位，以保证探测序列不至于断裂。【中科院计算所 2000八(15 分)】（分数：2.00）_正确答案：(正确答案：首先计算关键字的散列地址，若该地址为空(null)，则空操作；若该地址有关键字，但与给定值不等，则用解决冲突的方法去查找给定值；若该关键字与给定值相等，则实行删除。由于用线性探测解决冲突，设被删除元素的散列地址为 i，则其余 m一 1(m为表长)个位置均可能是同义词。查找同义词的操作直到碰到空地址或循环一圈回到 i才能结束。为了提高算法效率，应将最后一个同义词前移填充被删除关键字，但要保证二次聚集时也正确。)解析：
