【考研类试卷】计算机专业基础综合数据结构(集合)历年真题试卷汇编6及答案解析.doc

上传人:wealthynice100 文档编号:1389644 上传时间:2019-12-03 格式:DOC 页数:10 大小:88KB
下载 相关 举报
【考研类试卷】计算机专业基础综合数据结构(集合)历年真题试卷汇编6及答案解析.doc_第1页
第1页 / 共10页
【考研类试卷】计算机专业基础综合数据结构(集合)历年真题试卷汇编6及答案解析.doc_第2页
第2页 / 共10页
【考研类试卷】计算机专业基础综合数据结构(集合)历年真题试卷汇编6及答案解析.doc_第3页
第3页 / 共10页
【考研类试卷】计算机专业基础综合数据结构(集合)历年真题试卷汇编6及答案解析.doc_第4页
第4页 / 共10页
【考研类试卷】计算机专业基础综合数据结构(集合)历年真题试卷汇编6及答案解析.doc_第5页
第5页 / 共10页
点击查看更多>>
资源描述

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)解析:

展开阅读全文
相关资源
猜你喜欢
  • STAS SR EN 22063-1995 Metallic and other inorganic coatings Thermal spraying Zinc aluminium and their alloys《金属及其它无机涂层.热喷涂.锌、铝及其合金》.pdf STAS SR EN 22063-1995 Metallic and other inorganic coatings Thermal spraying Zinc aluminium and their alloys《金属及其它无机涂层.热喷涂.锌、铝及其合金》.pdf
  • STAS SR EN 22233-1995 Packaging - Complete filled transport packages -Conditioning for testing《包装.整装、满装运输包装.空调测试》.pdf STAS SR EN 22233-1995 Packaging - Complete filled transport packages -Conditioning for testing《包装.整装、满装运输包装.空调测试》.pdf
  • STAS SR EN 22401-1996 Covered electrodes Determination of the efficiency metal recovery and deposition coefficient《包覆焊条.效率、金属回收和熔敷系数的测定》.pdf STAS SR EN 22401-1996 Covered electrodes Determination of the efficiency metal recovery and deposition coefficient《包覆焊条.效率、金属回收和熔敷系数的测定》.pdf
  • STAS SR EN 22553-1995 Welded brazed and soldered jolnts Symbolic reprezentation on drawlngs《焊、钎焊和焊缝.图纸中的符号表示》.pdf STAS SR EN 22553-1995 Welded brazed and soldered jolnts Symbolic reprezentation on drawlngs《焊、钎焊和焊缝.图纸中的符号表示》.pdf
  • STAS SR EN 22568-1996 Hand - and machine - operated circular screwing dies and hand -operated die stocks《手动和机械操作的圆形外螺纹板牙和手动板牙扳手 》.pdf STAS SR EN 22568-1996 Hand - and machine - operated circular screwing dies and hand -operated die stocks《手动和机械操作的圆形外螺纹板牙和手动板牙扳手 》.pdf
  • STAS SR EN 22768-1-1995 General tolerances - Part 1  Tolerances for linear and angular dimensions without individual tolerance indications《一般公差.第1部分:线性和角度尺寸公差的未注公差》.pdf STAS SR EN 22768-1-1995 General tolerances - Part 1 Tolerances for linear and angular dimensions without individual tolerance indications《一般公差.第1部分:线性和角度尺寸公差的未注公差》.pdf
  • STAS SR EN 22768-2-1995 General tolerances - Part 2  Geometrical tolerances for features without individual tolerance indications《一般公差.第2部分:无单独公差指示的零件的几何公差》.pdf STAS SR EN 22768-2-1995 General tolerances - Part 2 Geometrical tolerances for features without individual tolerance indications《一般公差.第2部分:无单独公差指示的零件的几何公差》.pdf
  • STAS SR EN 22857-1996 Ground thread taps for ISO metric threads of tolerances 4H to 8H and AG to 6G coarse and fine pitches Manufacturing tolerances on the threaded portion《公差4H至8H.pdf STAS SR EN 22857-1996 Ground thread taps for ISO metric threads of tolerances 4H to 8H and AG to 6G coarse and fine pitches Manufacturing tolerances on the threaded portion《公差4H至8H.pdf
  • STAS SR EN 23134-4-1994 Light metals and their alloys Terms and definitions Part 4  Castings《轻金属及其合金术语和定义.第4部分:铸件》.pdf STAS SR EN 23134-4-1994 Light metals and their alloys Terms and definitions Part 4 Castings《轻金属及其合金术语和定义.第4部分:铸件》.pdf
  • 相关搜索
    资源标签

    当前位置:首页 > 考试资料 > 大学考试

    copyright@ 2008-2019 麦多课文库(www.mydoc123.com)网站版权所有
    备案/许可证编号:苏ICP备17064731号-1