2017年湖北武汉纺织大学数据结构考研真题.doc

发布时间：2022-10-14 发布人：admin 分类：说明书资料大小：0.08M 资料格式：doc 举报版权申诉

第1页 / 共3页

第2页 / 共3页

第3页 / 共3页

文本预览

2017 年湖北武汉纺织大学数据结构考研真题一、填空题（每空 3 分，共 30 分） 1、_____是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号总称。 2、根据数据元素之间关系的不同特性，通常有下列四类基本结构：集合、线性结构、_____、图状结构或网状结构。 3、算法具有下列五个重要特性：_____、确定性、可行性、输入、输出。 4、以下程序段的时间复杂度为_____。 5、在长度为 n 的顺序表的第 i 个元素 ai 之前插入一个元素，需移动_____个元素。 (a1,a2,...,ai,...,an) 6、栈的入栈序列为 abcdefg，出栈序列的第一个元素是 g，则出栈序列的第五个元素是_____。 7、深度为 10 的满二叉树共有_____个结点。 8、二叉树中有 100 个度为 2 的结点，该二叉树中有_____个度为 0 的结点。 9、无向图中共有 20 个顶点，当具有_____条边时，该无向图被称为完全图。 10、按排序方法的稳定性而言，希尔排序是_____的排序方法。二、解答题（共 100 分） 1、已知循环队列的最大长度为 6，队列中已有 3 个元素，队列头元素是 a，队列尾元素是 c，如下图所示。依次进行三步操作：d 入队列；e 入队列；一个元素出队列。 ①画出“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、已知无向图的邻接表如下图所示 ①根据邻接表计算顶点 A 的度（5 分） ②根据邻接表，从顶点 B 出发进行遍历，写出深度优先搜索的遍历结果序列（5 分） ③根据邻接表，从顶点 E 出发进行遍历，写出广度优先搜索的遍历结果序列（5 分） 6、已知静态链表如下图所示，依次进行两步操作：在数据元素“ZHOU”之前插入数据元素 “SHI”；删除数据元素“ZHENG” ①画出插入数据元素“SHI”后的静态链表（5 分） ②画出删除数据元素“ZHENG”后的静态链表（5 分） 7、已知待排序的关键字序列为{50，60，30，90，80，20} ①采用“直接插入排序”方法，写出按从小到大的顺序进行排序的过程（5 分）

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

分享到：

赞收藏

资料库

2017年湖北武汉纺织大学数据结构考研真题.doc

相关推荐

考研

热门标签

最新资料