1、武汉纺织大学2015 年招收硕士学位研究生试卷科目代码 848 科目名称 数据结构考试时间 2014 年 12 月 28 日下午 报考专业1、试题内容不得超过画线范围，试题必须打印，图表清晰，标注准确。2、试题之间不留空格。3、答案请写在答题纸上，在此试卷上答题无效。题号一二三四五六七八九十十一得分得分本试卷总分 150 分，考试时间 3 小时。一、填空题（每空 3 分，共 30 分）1、根据数据元素之间关系的不同特性，通常有下列四类基本结构：集合、 _、树形结构和图状结构。2、算法具有五个重要特性：有穷性、确定性、 _、输入和输出。3、以下程序段中语句“ +x;”的频度是 _。for(i=1
2、;i=n;+i)for(j=1;j=n;+j)+x;s+=x;4、在长度为 n 的顺序表中，在第 i(1 i n)个元素之前插入一个元素时，需将_个元素依次向后移动一个位置。5、已知队列的入队序列是 ABCD，则出队序列是 _。6、树中结点 A 有 8 个兄弟，结点 B 是结点 A 的双亲，结点 B 的度是 _。7、在含有 100 个结点的二叉链表中有 _个空链域。共页第页共 4 页；第 1 页8、在有 200 个顶点的无向图中，边的数目最少是 0，最多是 _。9、在以下有序表中，采用“折半查找” ，找到 32 需比较 _次。(5, 8, 11, 12, 15, 20, 32, 41, 57,
3、 60, 80)10、设待排序序列中记录的个数为 n，则堆排序在最坏情况下，其时间复杂度为_。二、解答题（共 100 分）1、已知静态链表如下图所示，在数据元素“ ZHOU”之前插入数据元素“ SHI” ，然后删除数据元素“ ZHENG” ，试画出插入删除后的静态链表。 （ 10 分）2、已知某二叉树的先序遍历序列为 ABDFCEG， 中序遍历序列为 FDBACEG，要求：画出该二叉树（ 10 分）写出该二叉树的后序遍历序列（ 5 分）3、有如下所示的二叉树，要求：画出该二叉树对应的森林（ 10 分）共 4 页；第 2 页写出森林的中序遍历序列（ 5 分）4、已知 8 个权值为 4， 29，
4、9， 8， 14， 23， 6， 11，要求：根据 8 个权值构造并画出赫夫曼（ Huffman）树（ 10 分）求该赫夫曼（ Huffman）树的带权路径长度（ 5 分）5、已知无向图的邻接表如下，试画出该无向图。 （ 10 分）共 4 页；第 3 页6、已知连通网如下，采用克鲁斯卡尔（ Kruskal）算法，给出构造最小生成树的过程（ 10 分）7、已知一组关键字为 19， 14， 23， 1， 68， 20， 84， 27， 55， 11， 10， 79，哈希函数为 H(key) key MOD 13，哈希表长为 16，采用开放定址法处理冲突，增量序列选用线性探测再散列。要求：构造并画出
5、哈希表（ 10 分）假设每个记录的查找概率相等，求查找成功时的平均查找长度（ 5 分）8、已知待排序的关键字序列为 50， 60， 75， 95， 90， 20， 45，采用“简单选择排序”方法，给出按从小到大的顺序排序的过程（ 10 分）三、算法设计题（共 20 分）已知静态查找表的顺序存储结构如下：typedef int KeyType;typedef struct KeyType key; / 关键字域/其他域ElemType;typedef struct ElemType *elem; / 数据元素存储空间基址，按实际长度分配， 0 号单元留空int length; / 表长度 SSTable;试设计在有序表 ST 中折半查找关键字等于 key 的数据元素的算法，函数头如下：int Search_Bin(SSTable ST， KeyType key)共 4 页；第 4 页
