1、计算机专业基础综合数据结构（集合）历年真题试卷汇编 7 及答案与解析一、填空题1 已知 N 元整型数组 a 存放 N 个学生的成绩，已按由大到小排序，以下算法是用对分(折半 )查找方法统计成绩大于或等于 x 分的学生人数，请填空使之完善。#define N* 学生人数*intuprx(int aN，int x) *函数返回大于等于 x 分的学生人数*int head=1，mid，rear=N;domid=(head+rear)2；if(x=aj)i+；if(irmidkey) (3) ；else flag=0；if(!flag)pos=mid；else pos=low；for(i=n；i=po
2、s；i 一一)(4)；rposkey=x；【北京交通大学 2005 七、1(8 分)】4 假设 root 是一棵给定的非空查找树，对于下面给出的子程序，当执行注释中给出的调用语句时，就可以实现如下的操作：在非空查找树 root 中查找值为 k 的结点；若值为 k 的结点在树中，且是一个叶子结点，则删除此叶子结点，同时置Success 为“真”；若值为 k 的结点不在树中，或者虽然在树中，但不是叶子结点，则不进行删除，仅置 success 为“ 假”。应注意到非空查找树只包含一个结点情况，此时树中的唯一结点，既是根结点，也是叶子结点。#includetypedef struct、nodeint
3、key；struct node*left， *right ；node；node*root； int kt success；void delleaf(node*t，int k，int。sn)(node*P，*pf；p= 。t； *sn=0；while( (1) !*sn)if(k=p 一key) 。sn=1 ；else (2) ；if (kkey)p=p-left ； else p=p-right；if (*sn size：int； lchild， rchild， parent8： tree ；END；一个结点 x的 size 域的值是以该结点为根的子树中结点的总数(包括 x本身)。例如，下图中
4、 x 所指结点的 size 值为 4。设树高为 h，试写一时间为 O(h)的算法 Rank(T：tree；x：node)返回 x 所指结点在二叉排序树 T 的中序序列里的排序序号，即求 x结点是根为 T 的二叉排序树中第几个最小元素。例如，下图 x 所指结点是树 T 中第 11 个最小元素。(提示：你可利用 size 值和双亲指针 parents)【中科院软件所 1997 四(12 分)】【中国科学技术大学 1997 (10 分) 】27 已知一棵排序二叉树是以二叉链表的形式存储的，且结点的数据场的类型为int。现已知该二叉树的根结点的地址为 root，以及一个整数值 key。请写一个非递归的
5、函数，给出数据场之值为 key 的结点的双亲结点的地址。【上海交通大学2005 二(25 分) 】28 设二叉树结点结构为：(1eR，data ，bf，right)。定义二叉树结点的平衡因子bf(T)=hL 一 hR，写一递归算法确定二又树 tree 中各结点的平衡因子 bf,同时返回二叉树 tree 中非叶子结点的个数。【东南大学 2005 三(10 分)】29 假设一棵平衡二叉树的每个结点都标明了平衡因子 b，试设计一个算法，求平衡二叉树的高度。【燕山大学 2001 四、3(8 分)】计算机专业基础综合数据结构（集合）历年真题试卷汇编 7 答案与解析一、填空题1 【正确答案】 (1)hea
6、d=mid+1 (2)rear=mid-1 (3)headrear编者注：参数应为 aN+12 【正确答案】 (1)il=k (2)i+1 (3)i 一 1 (4)il=k3 【正确答案】 (1)lowrch (2)pre=s (3)p 一lch=s 一lch (4)pre 一rch=s 一lch(5) s 一lch (6)pre=s (7)p 一rch=s 一rch (8)pre 一lch=s 一rch6 【正确答案】 (1)delete(T) (2)qelseq=p； s=p 一lchild； 被删结点有左子树while(s 一rcchild!=null) 查左子树中最右下的结点(中序最后
7、结点)(q=s； s=s 一rchild ；)P 一key=s 一key； 结点值用其左子树最右下的结点的值代替if(q=p)P 一ichild=s 一ichild； 被删结点左子树的根结点无右子女else q 一rchild：s 一ichild； s 是被删结点左子树中序序列最后一个结点delete(s)； else 结束，被删结点有左子树20 【正确答案】 是二叉排序树结点的删除， while(pelseq=p； s=p 一lchild； 被删结点有左子树while(s 一rcchild!=null) 查左子树中最右下的结点(中序最后结点)(q=s； s=s 一rchild ；)P 一ke
8、y=s 一key； 结点值用其左子树最右下的结点的值代替if(q=p)P 一ichild=s 一ichild； 被删结点左子树的根结点无右子女else q 一rchild：s 一ichild； s 是被删结点左子树中序序列最后一个结点delete(s)； else 结束，被删结点有左子树21 【正确答案】 利用二叉排序树的性质，从根结点开始查找，若根结点的值小于等于 x，则根结点及其左子树均应删除，然后以右子树的根结点为树根，重新开始查找。若根结点的值大于 x，则顺左子树向下查找，直到某结点的值小于等于 x，则该结点及其左子树均应删除，同时将指向被删结点的指针(即双亲指向被删结点的指针)置空。
9、删除以某结点为根的子树，采用后序遍历：删除其左子树，删除其右子树，删除根结点。22 【正确答案】 中序遍历二叉排序树可以得到结点的升序序列，若按“右子树一根结点一左子树” 进行遍历，则可以得到递减的结点序列。递归算法非常简单，如下所示：void DecPrint(BSTree t)递减序输出二叉排序树 t 中所有左子树为空、右子树非空的结点数据域的值if(t)DecPrint(t 一rchild)；if(!t 一ichiid 右子树if(t 一data)dataichild)Prit(t 一ichild ，x) ； 左子树24 【正确答案】 二又排序树中大于 x 的最小一个数，是在中序遍历序列
10、中排在 x后面的第一个数。25 【正确答案】 采用中序遍历，将遍历结点与前驱比较，若相同，则不输出并记数。核心语句段如下：if(t)BSTPrint(t 一ichild)； 中序遍历左子树if(pre=null)pre=t； pre 是当前访问结点的前驱，调用本算法时初值为 nullelse if(pre 一key=t 一key)count+；count 记重复元素，初值为 0elsecoutkeyl pre=t；) 前驱后移BSTPrint(t 一rchiid) ； 中序遍历右子树 if26 【正确答案】 设 r 是以*x 为根的中序序号。初始时，若 X 的左子树为空，r=1；否则，r=lc
11、hild 一size+1。利用结点的双亲域，上溯至根结点，可得答案 r。核心语句段如下：if(x 一ichild)r=x 一Ichild 一size+1；else r=1； x 的这个序号是暂时的p=x； p 要上溯至根结点 T，求出*x 的中序序号while(p!=T)(if(p=p 一 parents 一rchild) p 是其双亲的右子女(if(p 一parents 一ichild=null)r+； P 结点的双亲排在 P 结点的前面else r=r+p 一parent 一ichild 一size+1； ；X 亲及左子树均排在 P 前面p=p-parents ； 找 P 的双亲 whil
12、e另一算法是从根往下查找结点*x。若 T 的左子树为空，则根的中序序号为 1，否则为T-lchild 一size+1。设 T 的中序序号为 r，其左子女 P 的中序序号和右子女 q 的中序序号分别为 rp 一rchild 一size 一 1 和 r+q 一lchild 一size+1。核心语句段如下：if(T 一ichild) r=T 一ichild 一size+1；else r=1； 根结点的中序序号 rwhile(T)if(T 一keyx 一key) 到左子树去查找T=T 一ichild；if(T)if(Trchild)r=rT 一rchild 一size-1；else r=r 一 1)e
13、lse if(T 一keykey) 到右子树去查找T=T 一rchild；if(T)if(T 一Ichild)r=r+T 一ichild 一size+l ；else r=r+l；else return(r)；T 一key=x 一key ，返回*x 结点的中序序号27 【正确答案】 利用二叉排序树性质，从根结点开始查找，设 P 表示根结点的指针，核心语句段如下：if(p&P 一key=key)coutlchild 一key=key lI P 一rchild 一key=key)return P ；if(p-keykey)p=p 一Ichild；else p=p 一rchild；coutbf=1 bst 一bf=0)return(height(bst 一ichild) 左子树高度+1else return(1+height(bst 一rchild)右子树高度 +1
