武汉纺织大学848数据结构2017考研真题
时间：2017-11-28 15:40 来源：研导师
武汉纺织大学
7 2017 年招收硕士学位研究生试卷
科目代码 848 科目名称 数据结构
考试时间 2016 年 年 12 月 月 25 日下午 报考专业
1、试题内容不得超过画线范围，试题必须打印，图表清晰，标注准确。
2、试题之间不留空格。
3、答案请写在答题纸上，在此试卷上答题无效。
题号 一 二 三 四 五 六 七 八 九 十 十一 得分
得分
本试卷总分 150 分，考试时间 3 小时。
一、填空题（每空 3 3 分，共 0 30 分）
1、_____是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中
并被计算机程序处理的符号总称。
2、根据数据元素之间关系的不同特性，通常有下列四类基本结构：集合、线性
结构、_____、图状结构或网状结构。
3、算法具有下列五个重要特性：_____、确定性、可行性、输入、输出。
4、以下程序段的时间复杂度为_____。
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
{
c[i][j] = 0;
for (k = 1; k <= n; k++)
c[i][j] += a[i][k] * b[k][j];
}
5、在长度为 n 的顺序表的第 i 个元素 a i 之前插入一个元素，需移动_____个元素。
(a 1 , a 2 , ... , a i , ... , a n )
共 页 第 页
共 4 页；第 1 页
6、栈的入栈序列为 abcdefg，出栈序列的第一个元素是 g，则出栈序列的第五个
元素是_____。
7、深度为 10 的满二叉树共有_____个结点。
8、二叉树中有 100 个度为 2 的结点，该二叉树中有_____个度为 0 的结点。
9、无向图中共有 20 个顶点，当具有_____条边时，该无向图被称为完全图。
10、按排序方法的稳定性而言，希尔排序是_____的排序方法。
二、 解答题（共 100 分）
1、已知循环队列的最大长度为 6，队列中已有 3 个元素，队列头元素是 a，队列
尾元素是 c，如下图所示。依次进行三步操作：d 入队列；e 入队列；一个元素出
队列。
a b c
1 2 3 4 5
front rear
0
①画出“d 入队列”后的循环队列（5 分）
②画出“e 入队列”后的循环队列（5 分）
③画出“一个元素出队列”后的循环队列（5 分）
2、已知某二叉树的后序遍历序列为 DCBFJIHGEA，中序遍历序列为 BCDAFEHJIG
①画出该二叉树（10 分）
②写出该二叉树的先序遍历序列（5 分）
3、已知关键字序列为{12, 25, 36, 80, 66, 72}
①根据关键字序列构造并画出二叉排序树（10 分）
②假设每个记录的查找概率相等，求查找成功时的平均查找长度（5 分）
4、已知电文中字母出现频率的相应权值为{12, 8, 6, 20, 36, 25, 5}
①构造并画出赫夫曼(Huffman)树（10 分）
②计算带权路径长度（5 分）
5、已知无向图的邻接表如下图所示
共 4 页；第 2 页
E
A
D
C
B
5
0 4 ^
0 ^
1 2 0
1
2
3
4
3
0 ^
1 0 ^
F 5 3 0 ^
4 5 ^
①根据邻接表计算顶点 A 的度（5 分）
②根据邻接表，从顶点 B 出发进行遍历，写出深度优先搜索的遍历结果序列（5 分）
③根据邻接表，从顶点 E 出发进行遍历，写出广度优先搜索的遍历结果序列（5 分）
6、已知静态链表如下图所示，依次进行两步操作：在数据元素“ZHOU”之前插入
数据元素“SHI”；删除数据元素“ZHENG”。
LI 5 4
ZHOU 6 5
QIAN 3 2
SUN 4 3
WANG 0 8
9
WU 7 6
ZHENG 8 7
1 0
ZHAO 2 1
10
共 4 页；第 3 页
①画出插入数据元素“SHI”后的静态链表（5 分）
②画出删除数据元素“ZHENG”后的静态链表（5 分）
7、已知待排序的关键字序列为{50，60，30，90，80，20}
①采用“直接插入排序”方法，写出按从小到大的顺序进行排序的过程（5 分）
②采用“起泡排序”方法，写出按从小到大的顺序进行排序的过程（5 分）
③采用“简单选择排序”方法，写出按从小到大的顺序进行排序的过程（5 分）
三、算法设计题（共 共 20 分 ）
已知函数头为“int prime(int n)”，函数 prime 的功能：如果 n 是质数，返回 1；
否则，返回 0。编写并调用函数 prime 输出 1000 以内所有的质数，每行输出 10 个
质数。要求写出完整的程序。（注：质数是指在大于 1 的整数中，除了 1 和该整数
自身外，不能被其他正整数整除的整数）
共 4 页；第 4 页
共 页；第 页
共 页；第 页
附件：
 |
848数据结构 |
以上是本机构为大家提供的武汉纺织大学848数据结构2017考研真题，希望对大家有所帮助。