|
华侨大学2018年硕士研究生入学考试专业课试卷 （答案必须写在答题纸上） 招 招生专业 计算机技术 科 考试科目名称 数据结构与C++ 科目代码 827 第一部分 数据结构 (共75分) 一. 单项选择题（每题2分，共10分） 1. 在一个单链表中，将指针q所指结点作为指针p所指结点的后继进行插入的操作是( )。 A. q->next=p; p->next=q; B. q->next=p->next ; p->next=q; C. q->next=p; p=p->next; D. p->next=q; q->next=p; 2. 在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为2，则叶子结点个数为( )。 3. 对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是( )。 A． 直接插入 B. 二分法插入 C. 快速排序 D. 归并排序 4. 设有一个电文，其中有5个不同字符，每个字符的出现次数分别为5，3，4，2，6，那么将这个电文进行哈夫曼编码后得到的电文有多少个二进制位？（ ）。 A.55 B．60 C．65 D．70 5. 后缀算数表达式串“2 4 * 5 -”的计算结果为( ) A. 1 B. 2 C. 3 D. 4 二. 问答题（共40分） 1. （8分）已知二叉树T的后序遍历序列是DCBFHGEA，中序遍历序列是BDCAFEHG。 （1） 画出二叉树T的树形；（4分） （2） 用虚线在T上添加先序线索。（4分） 2. （10分）设无向图G包含A、B、C、D、E、F、G 7个顶点，我们用(A, B, 5)表示顶点A和B之间有一条权值为5的无向边。则图G由如下无向边构成：(A,B,2)、(A,D,3)、(A,C,1)、(B,D,2)、(D,C,5)、(E,B,6)、(E,D,1)、(E,C,3)。 （1） 画出图G的带权邻接表，要求带权邻接表的每个顶点的邻接链表中表结点的顶点序号按升序排列；（5分） （2） 请基于该邻接表画出普里姆（Prim）算法从顶点A出发得到的最小生成树，请给出生成过程；（5分） 3. （12分）已知一组记录的关键字为（15，25，18，5，27，1，39，33，6，17，13，28，23）。按哈希函数H(Key) = Key MOD 13和线性探测再散列处理冲突的方法在地址空间A[0..13]中构造哈希表，画出地址空间A[0..13]中每个位置存放记录的关键字，如果没有存放记录则留空。并计算等概率情况下，查找成功的平均查找长度。 4. （10分）设有一个关键字输入序列（4，5，6，1，2，3），试从空树开始构造平衡二叉排序树，画出每加入一个结点后二叉树的形态，若发生不平衡，请指出平衡调整的类型并画出调整结果。然后计算在等概率情况下，查找成功的平均查找长度ASL。 三．程序设计题（共25分） 1. （10分）写一个算法将结点数据降序排列的单向链表中的重复结点删除。 2. （15分）已知一无向图G以邻接表作为存储结构，请 第二部分 C++ (共75分) 一. 选择题（单选，每小题2分，共20分） #include<iostream> using namespace std; void main(void){ int i=1,j=0; if(--i&&j++) cout<<i<<','<<j<<endl; else cout<<i<<','<<j<<endl; } A) A) 0 ,0 B)1,0 C)0,1 D) 1,1 2. 若有定义：int i=2,j=5;，表达式(i++,j--)的值为（ ）。 A) 2 B) 5 C)3 D) 4 3. 下面程序段的执行结果为（ ）。 int a[2][5]={1,2,-3,4,-5,6,7,8,-9,-10},*p=a[1]; cout<<*(p+1)<<endl; A) -5 B) 6 C)7 D) 8 4. 以下程序的运行结果为（ ）。 #include<iostream> using namespace std; void main(void){ char s[][10]={"123abc","abcd"}; cout<<s[1]+1<<endl; } A)abc B)abcd C) 23abc D) bcd 5. 下面程序的运行结果为（ ）。 #include<iostream> using namespace std; void main(void){ int a[][3]={1,2,3,4,5,6},(*p)[3]=a; cout<<*(*p+1)<<endl; } A） 1 B） 3 C） 2 D） 5 6. 下面程序的运行结果为（ ）。 #include<iostream> using namespace std; void main(void){ int *p=new int[10],k; for(k=0;k<10;k++) p[k]=2*k-1; cout<<*p++<<endl; } A) 1 B) -1 C) 3 D) 0 7. 下列关于构造函数的描述中,错误的是（ ）。 A) 类中必须含有程序员自定义的构造函数 B) 构造函数可以重载 C) 构造函数的参数可以带有默认缺省值 D) 构造函数可以不带参数 8. 下列叙述正确的是（ ）。 A) 派生类的对象可以直接访问基类的公有成员 B) 运算符可以重载为类的友元函数 C) 派生类的基类只能有一个 D) 类的成员函数不可以直接访问类的私有成员 9. 假定Desk为一个类，则该类的拷贝构造函数的声明语句为（ ）。 A) copy Desk&(Desk d); B) Desk*(Desk d); C) Desk(const Desk& d); D) void Desk(copy Desk *d); 10. 下面程序的运行结果是（ ）。 #include<iostream> using namespace std; class A{ public: virtual void show(){ cout<<"in class A"<<endl; } }; class B:public A{ public: void show(){ cout<<"in class B"<<endl; } }; void main(){ A *pa; B b; pa=&b; pa->show(); } A）in class A B）in class A in class B C) in class B in class A D) in class B 二. 阅读下面程序，给出程序的运行结果（每小题8分，共24分） 1. #include<iostream> using namespace std; #define N 4 void main(void){ int a[N][N]={1,2,0,4,5,0,7,8,0,0,1,2,3,0,5,1},i,j,t; cout<<"original a:"<<endl; for(i=0;i<N;i++){ for(j=0;j<N;j++) cout<<a[i][j]<<" "; cout<<endl; } for(i=0;i<4;i++) for(j=0;j<i;j++){ t=a[i][j]; a[i][j]=a[j][i]; a[j][i]=t; } cout<<"updated a:"<<endl; for(i=0;i<N;i++){ for(j=0;j<N;j++) cout<<a[i][j]<<" "; cout<<endl; } } #include<iostream> #include<cstring> using namespace std; class Student{ int num; char name[20]; static int count; public: Student(char* s,int n){ cout<<"constrcting "<<s<<endl; num=n; strcpy(name,s); count++; } Student(const Student& s){ char temp[80]="copyof"; cout<<"copy constructing..."<<s.name<<endl; num=s.num; strcat(temp,s.name); strcpy(name,temp); count++; } void print(){ cout<<"num:"<<num<<","<<"name:"<<name<<endl; } static int getcount(){ return count; } ~Student(){ cout<<name<<" being destructing..."<<endl; } }; int Student::count=0; void main(void){ Student s1("Yumei",100102),s2("Liuhua",100203),s3(s1); cout<<"count="<<Student::getcount()<<endl; } 3. #include<iostream> #include<cstring> using namespace std; void main(void){ char str[][80]={"hqu","qinghua","buaa","xmu","nuaa"},s[80]; int k,i=0,j=sizeof(str)/sizeof(char[80])-1; while(i<j){ strcpy(s,str[i]); strcpy(str[i],str[j]); strcpy(str[j],s); i++,j--; } for(k=0;k<sizeof(str)/sizeof(char[80]);k++) cout<<str[k]<<" "; cout<<endl; } 三. 编程题（共31分） 1. 1. 编写程序，随机输入正整数n,输出它的“逆向数据”。比如，输入的n为1234,则输出4321。（8分） 2. 2. 定义非递归函数int BiSearch(int a[], int n, int x, int& count)，函数的功能：数组a存储有n个已经升序排列的元素，使用二分法查找x在数组a中的位置，若查找成功，返回其所在的下标值，若查找失败，返回-1。参数count存储查找过程中所需要的比较次数。编写完整C++程序，调用该函数。（11分） 3.编写程序实现以下功能： （1）定义一个描述学生基本情况的类，数据成员包括学号、姓名、C++成绩、英语成绩、高数成绩等。包括的主要成员函数有：①构造函数 ②输出学生基本信息 ③求总成绩 ④求平均成绩。 （2）重载输出操作符<<实现学生类对象的输出。 （3）编写main函数，测试以上所要求的各种功能。(12分） |
