华侨大学计算机科学与技术学院《850数据结构》与C＋＋[专业硕士]历年考研真题汇编.pdf

目录2015年华侨大学计算机科学与技术学院850数据结构与C+专业硕士考研真题2014年华侨大学计算机科学与技术学院850数据结构与C+专业硕士考研真题2013年华侨大学计算机科学与技术学院850数据结构与C+专业硕士考研真题2012年华侨大学计算机科学与技术学院850数据结构与C+专业硕士考研真题2011年华侨大学计算机科学与技术学院848数据结构与C+专业硕士考研真题已知intarray43=9A.&21 B.*(array2+1)C.array2+1 D.*(array-2)+1在创建派生类对象时，构造函数的执行顺序是()。A.对象成员构造函数、基类构造函数、派生类本身的构造函数B.派生类本身的构造函数、基类构造函数、对象成员构造函数C.基类构造函数、派生类本身的构造函数、对象成员构造函数D.基类构造函数、对象成员构造函数、派生类本身的构造函数有函数原型voidfunx(int&);下面选项中，正确的调用是()。A.intx=5.17;funx(&x);B.inta=20;funx(a*3.14);C.funx(210);D.intb=30;funx(b);若有以下声明和定义，则下列引用非法的是()。structdataintn;floatscore;data*q;dataa3=101data*p=a;A.p-n+B.(*p).n+C.+p-n D.*p-n2010年华侨大学计算机科学与技术学院848数据结构与C+专业硕士考研真题2009年华侨大学计算机科学与技术学院845数据结构与C+专业硕士考研真题2008年华侨大学计算机科学与技术学院845数据结构与C+专业硕士考研真题2015年华侨大学计算机科学与技术学院850数据结构与C+专业硕士考研真题2014年华侨大学计算机科学与技术学院850数据结构与C+专业硕士考研真题2013年华侨大学计算机科学与技术学院850数据结构与C+专业硕士考研真题2012年华侨大学计算机科学与技术学院850数据结构与C+专业硕士考研真题（答案必须写在答题纸上）招生专业计算机技术科目名称数据结构与C+科目代码850 第一部分C+程序设计（共75分）一、是非题（共10分，每题1分）1一个数据对象的内存地址称为该数据对象的指针。2指针函数就是函数的类型为指针数据类型。3程序设计语言的语义表示语言结构的书写规则。4数组的存储类别不可以是register。5.switch语句的caseconstant-exp只作为语句的入口标号，本身并不能改变控制流程，也即无法控制跳过switch语句的其它分支。6因为函数内部声明的数据存放在函数栈区，所以其作用域是局部的。7数组的体积是静态确定的，而向量的体积（容器的大小）是可以动态改变的。8类的析构函数不但可以重载，而且还可以设置默认参数。9成员函数是类的操作的实现，一个类可以包含多个成员函数。这些函数可以由类的所有对象所共享。10为了保证类的封装性，C+规定类的所有成员都只能在类的内部定义。二、填空题（共10分，每空1分）1设一个C+程序由f1、f2、f3、f4和main五个函数构成，f1中分别调用了f2和f3，f2中调用了f1,则对于f1的递归调用形式，我们可以说(1)。2.I/O流是标准字符设备上的一系列字符组成的(2)，标准字符设备分为(3)和(4)分别用(5)和(6)表示。3外部函数应声明成类的（7），才能访问类的类的私有成员。4使用友元函数可以提高程序执行效率的理由是（8）。5表达式的语义涉及两方面：其一，（9）。第二，执行过程中所要遵循的（10）、求值次序及优先级规则。三、阅读以下程序并给出执行结果（10分）1（3分）#include#includeusingnamespacestd;voidmain()chara100,t;inti,j,k;cina;k=strlen(a);for(i=0;i=k-2;i+=2)for(j=I+2;jaj)t=ai;ai=aj;aj=t;coutaendl;输入：kajbacl输出：？2（3分）#includeusingnamespacestd;classTcintv1,v2;public:Tc(intx=0,inty=0):v1(x),v2(y)coutThisisaconstructor!v1+v2=v1+v2endl;Tc()coutThisisadestructor!endl;voidmain()Tcx,y(10,20),z(y);输出：?3（4分）#includeusingnamespacestd;classBclass public:Bclass(inti,intj)x=i;y=j;virtualintfun()return0;protected:intx,y;classIclass:publicBclass public:Iclass(inti,intj,intk):Bclass(i,j)z=k;intfun()return(x+y+z)/3;private:intz;voidmain()Iclassobj(2,4,10);Bclassp1=obj;coutp1.fun()endl;Bclass&p2=obj;coutp2.fun()endl;coutp2.Bclass:fun()endl;Bclass*p3=&obj;coutfun()endl;输出：？四、阅读以下程序或函数，简要叙述其功能（10分）1（3分）intf1(inta,intn,intkey)intlow,high,mid;low=0;hight=n-1;while(low=high)mid=(low+high)/2;if(keyamid)low=mid+1;elsereturnmid;return1;功能：？2（3分）#include#include#includeusingnamespacestd;voidmain()inti,m,m1,sqrtm,n1,n2;intl=0;cinn1n2;for(m=n1;m=n2;m+=2)if(m!=2)m1=m-1;elsem1=m;sqrtm=sqrt(m1);for(i=2;isqrtm)if(l+%10=0)coutendl;coutsetw(5)m1;功能：？3（4分）简述Matrix类的功能。#includeusingnamespacestd;classMatrixpublic:Matrix();friendMatrixoperator+(Matrix&,Matrix&);friendostream&operator(istream&,Matrix&);private:intmat23;Matrix:Matrix()for(inti=0;i2;i+)for(intj=0;j3;j+)matij=0;Matrixoperator+(Matrix&a,Matrix&b)Matrixc;for(inti=0;i2;i+)for(intj=0;j(istream&in,Matrix&m)coutinputvalueofmatrix:endl;for(inti=0;i2;i+)for(intj=0;jm.matij;returnin;ostream&operator(ostream&out,Matrix&m)for(inti=0;i2;i+)for(intj=0;j3;j+)outm.matij;outendl;returnout;五、编程题（35分）1编写计算1！+3！+5！+n!的程序，要求用递归函数实现阶乘运算。（10分）2设计一个满足如下要求的日期类。（25分）（1）设置日期；（2）按day/moth/year的格式输出日期；（3）输出对当前日期加上一天后的日期。第二部分数据结构（共75分）六、单项选择题（每小题2分，共20分）1下面算法的时间复杂度为（）。ints=0;for(inti=0;im;i+)for(intj=0;j=1&order=Get_length(list)/函数Get_length(list)返回链表的长度coutErrororderfoundn;returnNULL;LinkListt=(1);intnum=1;while(2)num+;(3);returnt;2（6分）阅读下面算法，指出该算法的功能。Statusfun2(char*str)StackT;QueueQ;charch1,ch2;inti;InitStack（T）;InitQueue(Q);for(i=0;stri!=0;i+)Push(T,stri);EnQueue(Q,stri);for(i=1;ilchild=NULL&T-rchild=NULL)return1;elsereturnfun3(T-lchild)+fun3(T-rchild)+1;八、简答题（13分）1如何理解链表中的头指针和头结点？(4分)2（6分）若有如下无向图G：（1）试画出G的邻接表表示，要求邻接表中的表结点按顶点序号从小到大排列；（2分）（2）根据你所给出的邻接表，分别给出从顶点A出发的深度优先搜索序列和深度优先搜索生成树。（4分）3（3分）设有一组关键字25,57,48,37,12,92,6,86,15,33,18,20，请给出快速排序的第一趟结果。九、算法设计题（24分）1分别编写非递归与递归算法，输出不带头结点的单向链表L的各个元素值(11分)2设二叉排序树bt以二叉链表为存储结构，试设计算法删除二叉排序树bt中值最大的结点。（13分）2011年华侨大学计算机科学与技术学院848数据结构与C+专业硕士考研真题（答案必须写在答题纸上）招生专业计算机技术科目名称数据结构与C+科目代码848 第一部分数据结构（共75分）一、单项选择题（每小题2分，共20分）1下面算法的时间复杂度为（）。for(pass=1;pass=n-1;i+)flag=1;for(j=0;jaj+1)flag=0,t=aj,aj=aj+1,aj+1=t;if(flag)break;A)O(1)B)O(log2n)C)O(n)D)O(n2)2.L是一个带头结点的空单向循环链表，若要向L中插入一个由指针p指向的结点，则执行（）。A)L=p;p-next=L;B)L-next=p;p-next=L;C)p-next=L;p=L;D)p-next=L-next;L=p;3设栈S和队列Q的初始状态皆为空，元素a1,a2,a3,a4,a5和a6依次通过一个栈，一个元素出栈后即进入队列，若6个元素出队列的顺序是a3,a5,a4,a6,a2,a1，则栈S至少应该容纳（）个元素。A)3B)4C)5D)64一棵完全二叉树的结点总数为28，则该完全二叉树的深度为（）。A)4B)5C)6D)75由权值分别为4,8,6,3,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。A)24B)36C)49D)596假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除以顶点vi为弧尾（出发点）的所有弧的时间复杂度是（）。A)O(n)B)O(e)C)O(n+e)D)O(n*e)7图的广度优先遍历类似于二叉树的（）。A)先序遍历B)中序遍历C)后序遍历D)层次遍历8对一棵二叉排序树进行（）遍历，可以得到该二叉树的所有结点按值从小到大排列的序列。A)前序B)后序C)中序D)按层次9设散列表长m=14,散列函数H(K)=K%11，已知表中已有4个结点,r(15)=4,r(38)=5;r(61)=6;r(84)=7,其他地址为空，如用二次探测再散列处理冲突，关键字为49的结点地址是（）。A)8B)3C)5D)910用某种排序方法对关键字序列（23，22，21，47，15，27，59，35，20）进行排序时，前两趟的结果情况如下：22，23，21，47，15，27，59，35，2021，22，23，47，15，27，59，35，20则所采用的排序方法是（）。A)堆排序B)起泡排序C)插入排序D)快速排序二、算法分析和阅读题（20分）1（每空2分，共6分）list是一个带头结点的单链表。下面算法的功能是删除单链表list中所有data值大于min且小于max的结点，请补充算法中的空缺，使之完成该功能。typedefstructNodeElemTypedata;structNode*next;LNode,*Linklist;voidFun1(_(1)_list,ElemTypemax,ElemTypemin)if(minnext;while(p)while(p-datanext;if(p-datanext;else_(3)_;/while(p)/if(mindata=T-data;t-lchild=Fun2(T-lchild);t-rchild=Fun2(T-rchild);/elsereturnt;/Fun23（8分）设有序表的n个数据元素(关键字即为数据元素的值)存储在一维数组R0.n-1中，阅读下面的算法，回答相关问题。intFun3(TElemTypeR,intn,TElemTypekey)intlow=0,high=n-1,mid;while(low=high)mid=(low+high)/2;if(key=Rmid)returnmid;if(key2)+1在创建派生类对象时，构造函数的执行顺序是()。A.对象成员构造函数、基类构造函数、派生类本身的构造函数B.派生类本身的构造函数、基类构造函数、对象成员构造函数C.基类构造函数、派生类本身的构造函数、对象成员构造函数D.基类构造函数、对象成员构造函数、派生类本身的构造函数有函数原型voidfunx(int&);下面选项中，正确的调用是()。A.intx=5.17;funx(&x);B.inta=20;funx(a*3.14);C.funx(210);D.intb=30;funx(b);若有以下声明和定义，则下列引用非法的是()。structdataintn;floatscore;data*q;dataa3=101,50,&a1,102,70,&a2,103,95,&a0;data*p=a;A.p-n+B.(*p).n+C.+p-n D.*p-n有以下程序段voidmain()inti=1,sum=0,n;cinn;doi+=2;sum+=i;while(i!=n);cout=4:s1+;break;caset=3:s2+;break;caset=2:s3+;default:s4+;couts1,s2,s3,s4endl;A.语法错，编译通不过B.1，1，1，2C.1，2，3，2D.1，1，2，2假设Xclass为抽象类，下列声明正确的是()。A.Xclassfun(int);B.Xclass*p;C.intfun(Xclass);D.XclassObj;若有以下定义，则说法错误的是()。inta=200,*p=&a;A声明变量p，其中*表示p是一个指针变量B变量p经初始化，获得变量a的地址C变量p只可以指向一个整型变量D变量p的值为200假定已定义浮点型变量data，以二进制方式把data的值写入输出文件流对象outfile中去，正确的语句是()。A.outfile.write(float*)&data,sizeof(float);B.outfile.write(float*)&data,data);C.outfile.write(char*)&data,sizeof(float);D.outfile.write(char*)&data,data);六、程序阅读与填空题（共33分）12345678956232122312181212121001)阅读下列程序，写出执行结果(5分)#include#include#includeusingnamespacestd;voidmain()input.txtfor(strings;getline(in,s);)inta,sum=0;for(istringstreamsin(s);sina;sum+=a);coutsumendl;2)阅读下列程序，写出执行结果(5分)#includeusingnamespacestd;voidmain()inta=78,14,22,90,34;intn=sizeof(a)/sizeof(a0);for(inti=0;in/2*2;i+=2)inttemp=ai;ai=ai+1;ai+1=temp;for(i=0;in;i+)coutai;3)阅读下列程序，写出执行结果(5分)#includeusingnamespacestd;voidfunc()staticinta=2;intb=5;a+=2;b+=5;couta=a,b=bendl;voidmain()func();func();4)请补充程序中的空缺，使之输出如下运行结果（每空2分，共6分）。#includeusingnamespacestd;voidmain()for(inti=1;i=10;+i)for(intj=1;(1);+j)cout;for(2);(3);+ch)coutch;coutn;5)请补充程序中的空缺，使之完成若干字符串按字母顺序（从小到大）输出（每空2分，共12分）。#includeusingnamespacestd;voidmain()voidsort(char*name,intn);voidprint(char*name,intn);char*name=BASIC,FORTRAN,C+,Pascal,COBOLintn=5;(1);(2);voidsort(char*name,intn)char*temp;inti,j,k;for(i=0;in-1;i+)k=i;for(j=i+1;（3）;j+)if(4)k=j;if(（5）)temp=namei;（6）;namek=temp;voidprint(char*name,intn)inti;for(i=0;in;i+)coutnameiendl;七、编程题（共22分）对于数组array10=4,20,20,5,7,9,4,30,20,5，先按照从小到大的顺序排序为array10=4,4,5,5,7,9,20,20,20,30,输出排序后数组序列中相等的数字对。(10分)定义一个Book（图书）类，在该类定义中包括数据成员：bookname（书名）、price（价格）和number（存书数量）；成员函数：display()显示图书的情况；borrow()将存书数量减1，并显示当前存书数量；restore()将存书数量加1，并显示当前存书数量；在main函数中，要求创建某一种图书对象(书名:C+程序设计;价格：36；数量：100)，并对该图书进行简单的显示、借阅和归还管理。(12分)2010年华侨大学计算机科学与技术学院848数据结构与C+专业硕士考研真题2009年华侨大学计算机科学与技术学院845数据结构与C+专业硕士考研真题2008年华侨大学计算机科学与技术学院845数据结构与C+专业硕士考研真题