第 1 页 共 8 页华侨大学 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，则叶子结点个数为( )。A4 B5 C6 D73. 对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是( )。A 直接插入 B. 二分法插入 C. 快速排序 D. 归并排序4. 设有一个电文，其中有 5 个不同字符，每个字符的出现次数分别为5，3，4，2，6，那么将这个电文进行哈夫曼编码后得到的电文有多少个二进制位？（ ） 。A.55 B60 C65 D705. 后缀算数表达式串“2 4 * 5 -”的计算结果为( )A. 1 B. 2 C. 3 D. 4第 2 页 共 8 页二. 问答题（共 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和线性探测再散列处理冲突的方法在地址空间A0.13中构造哈希表，画出地址空间A0.13中每个位置存放记录的关键字，如果没有存放记录则留空。并计算等概率情况下，查找成功的平均查找长度。4. （10分）设有一个关键字输入序列（4，5，6，1，2，3），试从空树开始构造平衡二叉排序树，画出每加入一个结点后二叉树的形态，若发生不平衡，请指出平衡调整的类型并画出调整结果。然后计算在等概率情况下，查找成功的平均查找长度ASL。三程序设计题（共 25 分）1. （10 分）写一个算法将结点数据降序排列的单向链表中的重复结点删除。2. （15 分）已知一无向图 G 以邻接表作为存储结构，请（1）写出邻接表存储结构的定义.（2 分）（2）编写程序输出图中的所有简单环路（简单环路是除了第一个和最后一个结点相同外，其余结点均不同的一条路径） 。 （13 分）第 3 页 共 8 页第二部分 C+ (共 75 分)一. 选择题（单选，每小题 2 分，共 20 分）1. 以下程序的运行结果为（ ） 。#includeusing namespace std;void main(void)int i=1,j=0;if(-ivoid main(void)char s10=“123abc“,“abcd“;coutusing namespace std;第 4 页 共 8 页void main(void)int a3=1,2,3,4,5,6,(*p)3=a;coutusing namespace std;void main(void)int *p=new int10,k;for(k=0;kusing namespace std;class Apublic:第 5 页 共 8 页virtual void show() coutshow();A）in class A B）in class Ain class BC) in class Bin class A D) in class B二. 阅读下面程序，给出程序的运行结果（每小题 8 分，共 24 分） 1.#includeusing namespace std;#define N 4void main(void)int aNN=1,2,0,4,5,0,7,8,0,0,1,2,3,0,5,1,i,j,t;cout#include using namespace std;class Studentint num;char name20;static int count;public:Student(char* s,int n)cout#includeusing namespace std;void main(void)char str80=“hqu“,“qinghua“,“buaa“,“xmu“,“nuaa“,s80;int k,i=0,j=sizeof(str)/sizeof(char80)-1;while(i<j)strcpy(s,stri);strcpy(stri,strj);strcpy(strj,s);i+,j-;for(k=0;k<sizeof(str)/sizeof(char80);k+)cout<<strk<<“ “;cout<<endl;第 8 页 共 8 页三. 编程题（共 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 分）