1、计算机专业基础综合数据结构（集合）历年真题试卷汇编 6及答案解析(总分：58.00，做题时间：90 分钟)一、填空题(总题数：7，分数：14.00)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(i_3.下列算法是利用折半查找算法在一个有序表中插入一个元素 X，并保持表
2、的有序性。请将程序中空白处填上适当的语句完成功能。 int bininsert(sqlist r，int x，int n)将 x插入到 r1-n中并保持其有序性 int low：1，high=13，mid，flag=l，pos，i； 插入的位置为 pos while( (1) size：int； lchild， rchild， parent8： tree；END；一个结点 x的 size域的值是以该结点为根的子树中结点的总数(包括 x本身)。例如，下图中 x所指结点的 size值为 4。设树高为 h，试写一时间为 O(h)的算法Rank(T：tree；x：node)返回 x所指结点在二叉排序树
3、 T的中序序列里的排序序号，即求 x结点是根为T的二叉排序树中第几个最小元素。例如，下图 x所指结点是树 T中第 11个最小元素。(提示：你可利用size值和双亲指针 parents)【中科院软件所 1997四(12 分)】【中国科学技术大学 1997 (10分)】（分数：2.00）_24.已知一棵排序二叉树是以二叉链表的形式存储的，且结点的数据场的类型为 int。现已知该二叉树的根结点的地址为 root，以及一个整数值 key。请写一个非递归的函数，给出数据场之值为 key的结点的双亲结点的地址。【上海交通大学 2005二(25 分)】（分数：2.00）_25.设二叉树结点结构为：(1eR，
4、data，bf，right)。定义二叉树结点的平衡因子 bf(T)=h L 一 h R ，写一递归算法确定二又树 tree中各结点的平衡因子 bf,同时返回二叉树 tree中非叶子结点的个数。【东南大学 2005三(10 分)】（分数：2.00）_26.假设一棵平衡二叉树的每个结点都标明了平衡因子 b，试设计一个算法，求平衡二叉树的高度。【燕山大学 2001四、3(8 分)】（分数：2.00）_计算机专业基础综合数据结构（集合）历年真题试卷汇编 6答案解析(总分：58.00，做题时间：90 分钟)一、填空题(总题数：7，分数：14.00)1.已知 N元整型数组 a存放 N个学生的成绩，已按由大
5、到小排序，以下算法是用对分(折半)查找方法统计成绩大于或等于 x分的学生人数，请填空使之完善。#define N*学生人数*intuprx(int aN，int x) *函数返回大于等于 x分的学生人数* int head=1，mid，rear=N; domid=(head+rear)2； if(x=aj)i+； if(i_正确答案：(正确答案：(1)il=k (2)i+1 (3)i 一 1 (4)il=k)解析：3.下列算法是利用折半查找算法在一个有序表中插入一个元素 X，并保持表的有序性。请将程序中空白处填上适当的语句完成功能。 int bininsert(sqlist r，int x，i
6、nt n)将 x插入到 r1-n中并保持其有序性 int low：1，high=13，mid，flag=l，pos，i； 插入的位置为 pos while( (1) elseq=p； s=p 一lchild； 被删结点有左子树 while(s 一rcchild!=null) 查左子树中最右下的结点(中序最后结点) (q=s； s=s 一rchild；) P 一key=s 一key； 结点值用其左子树最右下的结点的值代替 if(q=p)P 一ichild=s 一ichild； 被删结点左子树的根结点无右子女 else q 一rchild：s 一ichild； s 是被删结点左子树中序序列最后一个
7、结点 delete(s)； else 结束，被删结点有左子树)解析：17.写出在二叉排序树中删除一个结点的算法，使删除后仍为二叉排序树。设删除结点由指针 p所指，其双亲结点由指针 f所指，并假设被删除结点是其双亲结点的右孩子。用类 Pascal(或 C)语言将上述算法写为过程形式。【南开大学 1998七(16 分)】（分数：2.00）_正确答案：(正确答案：是二叉排序树结点的删除， while(p elseq=p； s=p 一lchild； 被删结点有左子树 while(s 一rcchild!=null) 查左子树中最右下的结点(中序最后结点) (q=s； s=s 一rchild；) P 一k
8、ey=s 一key； 结点值用其左子树最右下的结点的值代替 if(q=p)P一ichild=s 一ichild； 被删结点左子树的根结点无右子女 else q 一rchild：s 一ichild； s 是被删结点左子树中序序列最后一个结点 delete(s)； else 结束，被删结点有左子树)解析：18.设排序二叉树中结点的结构为下述三个域构成：data：给出结点数据的值；left：给出本结点的左儿子结点的地址；right：给出本结点的右儿子结点的地址。设 data域为正整数，该二叉树根结点地址为T。现给出一个正整数 x。请编写非递归程序，实现将 data域之值小于等于 x的结点全部删除掉。
9、【上海交通大学 2000十一(12 分)】（分数：2.00）_正确答案：(正确答案：利用二叉排序树的性质，从根结点开始查找，若根结点的值小于等于 x，则根结点及其左子树均应删除，然后以右子树的根结点为树根，重新开始查找。若根结点的值大于 x，则顺左子树向下查找，直到某结点的值小于等于 x，则该结点及其左子树均应删除，同时将指向被删结点的指针(即双亲指向被删结点的指针)置空。删除以某结点为根的子树，采用后序遍历：删除其左子树，删除其右子树，删除根结点。)解析：19.设二叉排序树的各元素值均不相同，采用二叉链表作为存储结构，试分别设计递归和非递归算法按递减序打印所有左子树为空，右子树非空的结点的数
10、据域的值。【北方交通大学 1998七(20 分)】（分数：2.00）_正确答案：(正确答案：中序遍历二叉排序树可以得到结点的升序序列，若按“右子树一根结点一左子树”进行遍历，则可以得到递减的结点序列。递归算法非常简单，如下所示： void DecPrint(BSTree t) 递减序输出二叉排序树 t中所有左子树为空、右子树非空的结点数据域的值 if(t) DecPrint(t 一rchild)； if(!t 一ichiid 右子树 if(t 一data)ichild，x)； 左子树 )解析：21.设二叉排序树中的结点值为整型，最大值为 MAX，给出任意整型值为(xMAX)，编写程序，求二叉排
11、序树中大于 x的最小一个数。【南京航空航天大学 2003六(10 分)】（分数：2.00）_正确答案：(正确答案：二又排序树中大于 x的最小一个数，是在中序遍历序列中排在 x后面的第一个数。)解析：22.在二叉排序树的结构中，有些数据元素值可能是相同的，设计一个算法实现按递增有序打印结点的数据域，要求相同的数据元素仅输出一个，算法还应能报出最后被滤掉而未输出的数据元素个数，对如图所示的二叉排序树，输出为：10，12，13，15，18，21，27，35，42。滤掉 3个元素。【北京工业大学1995六(18 分)】 （分数：2.00）_正确答案：(正确答案：采用中序遍历，将遍历结点与前驱比较，若相
12、同，则不输出并记数。核心语句段如下： if(t) BSTPrint(t 一ichild)； 中序遍历左子树 if(pre=null)pre=t； pre 是当前访问结点的前驱，调用本算法时初值为 null else if(pre一key=t 一key)count+；count 记重复元素，初值为 0 elsecoutrchiid)； 中序遍历右子树 if)解析：23.设二又排序树的存储结构为：TYpE tree=node：node=RECORD key： keytype; size：int； lchild， rchild， parent8： tree；END；一个结点 x的 size域的值是以
13、该结点为根的子树中结点的总数(包括 x本身)。例如，下图中 x所指结点的 size值为 4。设树高为 h，试写一时间为 O(h)的算法Rank(T：tree；x：node)返回 x所指结点在二叉排序树 T的中序序列里的排序序号，即求 x结点是根为T的二叉排序树中第几个最小元素。例如，下图 x所指结点是树 T中第 11个最小元素。(提示：你可利用size值和双亲指针 parents)【中科院软件所 1997四(12 分)】【中国科学技术大学 1997 (10分)】（分数：2.00）_正确答案：(正确答案：设 r是以*x 为根的中序序号。初始时，若 X的左子树为空，r=1；否则，r=lchild一
14、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的双亲 while 另一算法是
15、从根往下查找结点*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； 根结点的中序序号 r while(T) if(T一keyx 一key) 到左子树去查找 T=T一ichild； if(T)if(Trchild)r=rT 一rchild 一size-1；else r=r 一 1) else if(T
16、一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 结点的中序序号)解析：24.已知一棵排序二叉树是以二叉链表的形式存储的，且结点的数据场的类型为 int。现已知该二叉树的根结点的地址为 root，以及一个整数值 key。请写一个非递归的函数，给出数据场之值为 key的结点的双亲结点的地址。【上海交通大学 2005二(25 分)】（分数：2.00）_正确答案：(正确答案：利用二叉排序树性质，从根结点开始查找，设 P表示根结点的指针，核心语句段如下： if(p&P 一key=key)coutkey=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) 左子树高度+1 else return(1+height(bst一rchild)右子树高度+1)解析：
