2017年武汉纺织大学硕士考研专业课真题848数据结构.pdf

1、 武汉纺织大学武汉纺织大学 20172017 年招收硕士学位研究生试卷年招收硕士学位研究生试卷 科目代码科目代码 848 科目名称科目名称 数据结构数据结构 考试时间考试时间 2016 年年 12 月月 25 日下午日下午 报考专业报考专业 1、试题内容不得超过画线范围，试题必须打印，图表清晰，标注准确。2、试题之间不留空格。3、答案请写在答题纸上，在此试卷上答题无效。题号 一 二 三 四 五 六 七 八 九 十 十一 得分 得分 本试卷总分 150 分，考试时间 3 小时。一、填空题（每空一、填空题（每空 3 3 分，共分，共 3030 分）分）1、_是对客观事物的符号表示，在计算机科学中是

2、指所有能输入到计算机中并被计算机程序处理的符号总称。2、根据数据元素之间关系的不同特性，通常有下列四类基本结构：集合、线性结构、_、图状结构或网状结构。3、算法具有下列五个重要特性：_、确定性、可行性、输入、输出。4、以下程序段的时间复杂度为_。for(i=1;i=n;i+)for(j=1;j=n;j+)cij=0;for(k=1;k=n;k+)cij+=aik*bkj;5、在长度为 n 的顺序表的第 i 个元素 ai之前插入一个元素，需移动_个元素。(a1,a2,.,ai,.,an)共 页 第 页 共 4 页；第 1 页 6、栈的入栈序列为 abcdefg，出栈序列的第一个元素是 g，则出栈

3、序列的第五个元素是_。7、深度为 10 的满二叉树共有_个结点。8、二叉树中有 100 个度为 2 的结点，该二叉树中有_个度为 0 的结点。9、无向图中共有 20 个顶点，当具有_条边时，该无向图被称为完全图。10、按排序方法的稳定性而言，希尔排序是_的排序方法。二、二、解答题（共解答题（共 100 分）分）1、已知循环队列的最大长度为 6，队列中已有 3 个元素，队列头元素是 a，队列尾元素是 c，如下图所示。依次进行三步操作：d 入队列；e 入队列；一个元素出队列。abc12345frontrear0 画出“d 入队列”后的循环队列（5 分）画出“e 入队列”后的循环队列（5 分）画出“

4、一个元素出队列”后的循环队列（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 页 EADCB5040120123430

5、10F53045 根据邻接表计算顶点 A 的度（5 分）根据邻接表，从顶点 B 出发进行遍历，写出深度优先搜索的遍历结果序列（5 分）根据邻接表，从顶点 E 出发进行遍历，写出广度优先搜索的遍历结果序列（5 分）6、已知静态链表如下图所示，依次进行两步操作：在数据元素“ZHOU”之前插入数据元素“SHI”；删除数据元素“ZHENG”。LI54ZHOU65QIAN32SUN43WANG089WU76ZHENG8710ZHAO2110 共 4 页；第 3 页 画出插入数据元素“SHI”后的静态链表（5 分）画出删除数据元素“ZHENG”后的静态链表（5 分）7、已知待排序的关键字序列为50，60，

6、30，90，80，20 采用“直接插入排序”方法，写出按从小到大的顺序进行排序的过程（5 分）采用“起泡排序”方法，写出按从小到大的顺序进行排序的过程（5 分）采用“简单选择排序”方法，写出按从小到大的顺序进行排序的过程（5 分）三、算法设计题（三、算法设计题（共共 20 分分）已知函数头为“int prime(int n)”，函数 prime 的功能：如果 n 是质数，返回 1；否则，返回 0。编写并调用函数 prime 输出 1000 以内所有的质数，每行输出 10 个质数。要求写出完整的程序。（注：质数是指在大于 1 的整数中，除了 1 和该整数自身外，不能被其他正整数整除的整数）共 4 页；第 4 页 共 页；第 页 共 页；第 页