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