2017年华侨大学836数据结构与C++考研专业课真题试卷

第1页共10页华侨大学2017年硕士研究生入学考试专业课试卷（答案必须写在答题纸上）招招生专业计算机技术科考试科目名称数据结构与C++科目代码836第一部分数据结构(共75分)一.单项选择题（每题1.5分，共12分）1.在一个单链表中，在指针p所指结点之后插入s所指结点的正确语句是()。A.s-next=p;p-next=s;B.s-next=p-next;p-next=s;C.s-next=p;p=p-next;D.p-next=s;s-next=p;2.有一个循环队列的存储结构是数组Q[n]，队头指针为front，队尾指针为rear，则出队时的指针操作为（）。A．front=(front-1)%nB．front=(front+1)%nC.front=(front-1)%(n+1)D．front=(front+1)%(n+1)3.下列排序方法中，排序过程中关键字比较次数与记录初始排列次序无关的是()。A．冒泡排序B.简单选择排序C.直接插入排序D.快速排序4.设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做（）次线性探测。A.n2B.n(n+1)C.n(n+1)/2D.n(n-1)/25.折半查找要求结点（）。A.有序，顺序存储B.有序，链式存储C.无序，顺序存储D.无序，链式存储第2页共10页6.有53个结点的完全二叉树的高度是（）。A.3B.4C.5D.无法确定7.有n个叶子的哈夫曼树的结点总数为（）。A.不确定B.2nC.2n+1D.2n-18.右边的图1给出由7个顶点组成的无向网。从顶点A出发，对它进行深度优先遍历得到的顶点序列不可能是()。A．ABGFDECB．AECFDGBC.ACEFGBDD．AECDFGB图1二.问答题（共40分）1.（9分）一棵二叉树的先序序列和中序序列分别如下，请回答如下问题。先序序列：ABDGEHICFJ中序序列：DGBHEIACJF(1)（3分）请画出这棵二叉树。(2)（3分）请写出这棵二叉树的后序序列。(3)（3分）画出先序线索二叉树。2.（8分）设哈希表的地址范围为0～13，哈希函数为：H(K)=KMOD13,K为关键字，用线性探测再散列法处理冲突，输入关键字序列:(7,12,20,17,25,21,33,13,22,9)，造出哈希表，试回答下列问题：(1)（4分）画出哈希表示意图。(2)（4分）假定每个关键字的查找概率相等，求查找成功时、查找失败时的平均查找长度。3.（7分）设在通信中使用了abcdef六个字符，它们出现的次数分别为：8,9,3,5,7,2。(1)（5分）请画出相应的赫夫曼树。(2)（2分）请写出字符串“abcfde”的赫夫曼编码。4.（6分）有一组键值10,20,30,14,21,14,18,15,12,采用归并排序方法由小到ABCDEFG536243511第3页共10页大进行排序，请写出每趟的结果。5.（10分）根据第一大题第8小题的无向网(图1)，回答如下问题：(1)（4分）画出该图的邻接表存储结构，并根据你给出的存储结构完成如下任务。(2)（2分）画出以结点A为根的广度优先生成树。(3)（4分）画出用普里姆（Prim）算法从顶点A构造最小生成树的过程。三．程序设计题（共23分）1.（14分）对于一棵以孩子兄弟表示法表示的树，编写如下程序：（1）（7分）求出该树中度为2的结点个数。（2）（7分）求出该树的度（即树内各结点的度的最大值）。typedefstructCSNode{//结点结构ElemTypedata;StructCSNode*firstchild,*nextsibling;}CSNode,*CSTree;2.(9分)有一个冒泡排序算法可以把大的元素向下移（下沉），也可以把小的元素向上移（上浮）。请给出上浮和下沉交替进行的冒泡排序算法。其中，数据被存放在数组inta[N]中。函数声明为：intBubbleSort(intN,inta[])第二部分C++(共75分)一.选择题（单选，每小题2分，共20分）1.若有定义：inta[10][5],k=4;表达式(sizeof(a)/sizeof(k+1))的值为（）。A)50B)40C)20D)102.下面程序段的运行结果为（）。inta[10]={0,1,-2,3,-4,5,-6,7,-8,9},*p=a+1;cout*p++endl;A)0B)1C)-1D)-23.下面程序的运行结果为（）。A)abc123xyzB)bbc123xyzC)bc123xyzD)cc123xyz第4页共10页#includeiostreamusingnamespacestd;voidmain(void){chars[]=abc123xyz;(*s)++;couts+1endl;}4.下面程序的运行结果为（）。A）1B）-2C）4D）-4#includeiostreamusingnamespacestd;voidmain(void){inta[][3]={1,-2,3,-4,5,-6},(*p)[3]=a+1;cout**pendl;}5.下面程序的运行结果为（）。A)cst1001B)cst1003C)编译出错D)cst1002#includeiostream#includecstringusingnamespacestd;typedefstructStudent{charId[20],*name;intage,score;Student*next;}STU;voidmain(void){STUs1={cst1001,NULL,18,90},s2={cst1002,NULL,19,88},*ps=&s1;s1.next=&s2;strcpy(ps-Id,cst1003);coutps-next-Idendl;}6.下列叙述正确的是（）。第5页共10页A)析构函数可以重载B)构造函数不可以设置默认参数C)构造函数没有返回值类型D)构造函数只能有一个参数7.下列叙述正确的是（）。A)类的基类只能有一个，派生类可以有多个B)公有继承的派生类对象可以直接访问基类中的公有成员C)类的成员函数不能访问类的私有成员D)类的友元类成员函数不能直接访问该类的私有成员8.假定Desk为一个类，则该类默认的构造函数形式为（）。A)Desk(){}B)Desk(Desk*d){}C)~Desk(){}D)Desk(constDesk&d){}9.下列叙述,正确的是（）。A)类的静态成员可以通过类来访问B)通过运算符重载可以定义新的运算符C)重载单目运算符时，重载函数必须带一个参数D)重载运算符的重载函数只能作为类的友元函数10.下面程序的运行结果是（）。A)constructing...HquB)constructing...BUAAC)constructing...BUAABUAAbeingdestructed!D)D)constructing...HquHqubeingdestructed!#includeiostream#includestringusingnamespacestd;classPerson{private:intage;public:stringname;Person(inta,stringn=Hqu){第6页共10页age=a;name=n;coutconstructing...nendl;}~Person(){coutnamebeingdestructed!endl;}};voidmain(void){Person*p=newPerson(19,BUAA);}二.阅读程序，回答问题（共20分）1.写出下面程序的运行结果。（6分）#includeiostreamusingnamespacestd;#defineN4voidmain(void){inta[N][N]={-1,2,3,4,5,6,7,8,-9,0,1,2,-3,4,5,-4},i,j,t;coutoriginala:endl;for(i=0;iN;i++){for(j=0;jN;j++)couta[i][j];coutendl;}for(i=1;iN;i++){for(j=0;jN-i;j++)if(a[j][j]a[j+1][j+1])t=a[j][j],a[j][j]=a[j+1][j+1],a[j+1][j+1]=t;}coutupdateda:endl;for(i=0;iN;i++){for(j=0;jN;j++)couta[i][j];coutendl;}}第7页共10页2.写出下面程序的运行结果。（7分）#includeiostreamusingnamespacestd;voidFun(intn,intB[8],intstart){inti=start;if(n==1){B[i]=1;return;}else{B[i]=n%2;i++;Fun(n/2,B,i);}}voidmain(void){staticintB[8]={0};for(intm=1;m=16;m++){Fun(m,B,0);for(intk=7;k=0;k--)coutB[k];if(m%5==0)coutendl;elsecout;}}3.写出下面程序的运行结果。（7分）#includeiostreamusingnamespacestd;classA{public:intvalue;A(intv){value=v;}};第8页共10页classB:virtualpublicA{public:intBvalue;B(intv,intb):A(v){Bvalue=b;}intBValue(){returnBvalue;}};classC:virtualpublicA{public:intCvalue;C(intv,intc):A(v){Cvalue=c;}intCValue(){returnCvalue;}};classD:publicB,publicC{public:intDvalue;intValue(){returnvalue;}D(intv1,inta,intv2,intb,intc,intd):C(v2,b),B(v1,a),A(c){Dvalue=d;}intDValue(){returnDvalue;}};voidmain(void){Dobj(1,2,3,4,5,6);coutobj.Value()=obj.Value()endl;coutobj.BValue()=obj.BValue()endl;coutobj.CValue()=obj.CValue()endl;coutobj.DValue()=obj.DValue()endl;}三.编程题（共35分）1.输入n个学生的信息（学号id和年龄age，学号为字符串），输出学号最大学生的年龄。(10分)1．2.请完成下面一个描述平面上的点的类Piont的定义，Point类中含有名字name和两个坐标值x和y，完成设计主函数测试之。(12分)第9页共10页#includeiostreamusingnamespacestd;classPoint{char*name;//点的名称floatx,y;//点的两个坐标值public://(1)构造函数？//（2）析构函数？//（3）拷贝构造函数？//（4）成员函数Output()？（输出点的信息）}voidmain(void){//（5）测试程序？}3.类Screen表示手机屏幕,屏幕信息包括宽度width和高度height。请实现类的拷贝构造函数、比较操作符“==”、“”以及插入符“”,并给出测试程序。（13分）注注：（1）两个手机屏幕当且仅当宽度和高度都相等时才相等；（2）当