2017武汉纺织大学848数据结构考研真题.pdf
武汉纺织大学 2017 年招收硕士学位研究生试卷 科目代码 848 科目名称 数据结构 考试时间 2016 年 12 月 25 日下午 报考专业 1、试题内容不得超过画线范围,试 题 必须打印,图表清晰,标注准确。 2、试题之间不留空格。 3、答案请写在答题纸上,在此试卷上答题无效。 题号 一 二 三 四 五 六 七 八 九 十 十一 得分 得分 本试卷总分 150 分,考试时间 3 小时。 一、填空题(每空 3分,共 30分) 1、 _是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号总称。 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,则出栈序列的第五个元素是 _。 7、深度为 10的满二叉树共有 _个结点。 8、二叉树中有 100个度为 2的结点,该二叉树 中有 _个度为 0的结点。 9、 无向图中共有 20 个顶点,当具有 _条边时,该无向图被称为完全图。 10、按排序方法的稳定性而言,希尔 排序是 _的排序方法。 二、 解答题(共 100 分) 1、 已知 循环队列的最大长度为 6, 队列中已有 3个元素, 队列头元素是 a,队列尾元素是 c, 如下图所示 。依次进行三步操作: d入队列; e入队列;一个元素出队列。 a b c1 2 3 4 5fr o n t r e a r0画出“ 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 页 EADCB50 4 0 1 201234301 0 F5 3 0 45 根据 邻接表 计算顶点 A 的度 ( 5分) 根据邻接表,从顶点 B出发进行遍历, 写 出深度优先搜索的遍历结果序列 ( 5分) 根据邻接表,从顶点 E出发进行遍历,写 出 广 度优先搜索的遍历结果序列 ( 5分) 6、已知静态链表如下图所示, 依次进行两步操作: 在数据元素“ ZHOU”之前插入数据元素“ SHI” ; 删除数据元素“ ZHENG” 。 L I 54Z H O U 65Q IA N 32S U N 43W A N G 089W U 76Z H E N G 8710Z H A O 211 0共 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 页 共 页;第 页 共 页;第 页