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

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

第1页 / 共3页

第2页 / 共3页

第3页 / 共3页

文本预览

2015 年湖北武汉纺织大学数据结构考研真题一、填空题（每空 3 分，共 30 分） 1、根据数据元素之间关系的不同特性，通常有下列四类基本结构：集合、_____、树形结构和图状结构。 2、算法具有五个重要特性：有穷性、确定性、_____、输入和输出。 3、以下程序段中语句“++x;”的频度是_____。 4、在长度为 n 的顺序表中，在第 i (1≤i≤n)个元素之前插入一个元素时，需将 _____个元素依次向后移动一个位置。 5、已知队列的入队序列是 ABCD，则出队序列是_____。 6、树中结点 A 有 8 个兄弟，结点 B 是结点 A 的双亲，结点 B 的度是_____。 7、在含有 100 个结点的二叉链表中有_____个空链域。 8、在有 200 个顶点的无向图中，边的数目最少是 0，最多是_____。 9、在以下有序表中，采用“折半查找”，找到 32 需比较_____次。 (5, 8, 11, 12, 15, 20, 32, 41, 57, 60, 80) 10、设待排序序列中记录的个数为 n，则堆排序在最坏情况下，其时间复杂度为_____。二、解答题（共 100 分） 1、已知静态链表如下图所示，在数据元素“ZHOU”之前插入数据元素“SHI”，然后删除数据元素“ZHENG”，试画出插入删除后的静态链表。（10 分） 2、已知某二叉树的先序遍历序列为 ABDFCEG，中序遍历序列为 FDBACEG，

要求： ①画出该二叉树（10 分） ②写出该二叉树的后序遍历序列（5 分） 3、有如下所示的二叉树，要求： ①画出该二叉树对应的森林（10 分） ②写出森林的中序遍历序列（5 分） 4、已知 8 个权值为{4，29，9，8，14，23，6，11}，要求： ①根据 8 个权值构造并画出赫夫曼（Huffman）树（10 分） ②求该赫夫曼（Huffman）树的带权路径长度（5 分） 5、已知无向图的邻接表如下，试画出该无向图。（10 分） 6、已知连通网如下，采用克鲁斯卡尔（Kruskal）算法，给出构造最小生成树的过程（10 分）

7、已知一组关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，哈希函数为 H(key) ＝key MOD 13，哈希表长为 16，采用开放定址法处理冲突，增量序列选用线性探测再散列。要求： ①构造并画出哈希表（10 分） ②假设每个记录的查找概率相等，求查找成功时的平均查找长度（5 分） 8、已知待排序的关键字序列为{50，60，75，95，90，20，45}，采用“简单选择排序”方法，给出按从小到大的顺序排序的过程（10 分）三、算法设计题（共 20 分）已知静态查找表的顺序存储结构如下：试设计在有序表 ST 中折半查找关键字等于 key 的数据元素的算法，函数头如下： int Search_Bin(SSTable ST，KeyType key)

分享到：

赞收藏

资料库

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

相关推荐

考研

热门标签

最新资料