2018年华侨大学827数据结构与C++硕士研究生入学考试试题

第 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，
则叶子结点个数为( )。
A．4 B．5 C．6 D．7
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
第 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和线性探测再散列处理冲突的
方法在地址空间A[0..13]中构造哈希表，画出地址空间A[0..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. 以下程序的运行结果为（ ）。
#include
using namespace std;
void main(void){
int i=1,j=0;
if(--i&&j++) cout