1、武汉纺织大学2015 年招收硕士学位研究生试卷武汉纺织大学2015 年招收硕士学位研究生试卷科目代码科目代码848科目名称数据结构考试时间科目名称数据结构考试时间2014 年年 12 月月 28 日下午报考专业日下午报考专业1、试题内容不得超过画线范围，试题必须打印，图表清晰，标注准确。2、试题之间不留空格。3、答案请写在答题纸上，在此试卷上答题无效。题号一二三四五六七八九十十一得分得分本试卷总分 150 分，考试时间 3 小时。一、填空题（每空一、填空题（每空 3 分，共分，共 30 分）分）1、根据数据元素之间关系的不同特性，通常有下列四类基本结构：集合、_、树形结构和图状结构。2、算法具
2、有五个重要特性：有穷性、确定性、_、输入和输出。3、以下程序段中语句“+x;”的频度是_。for(i=1;i=n;+i)for(j=1;j=n;+j)+x;s+=x;4、在长度为 n 的顺序表中，在第 i(1in)个元素之前插入一个元素时，需将_个元素依次向后移动一个位置。5、已知队列的入队序列是 ABCD，则出队序列是_。6、树中结点 A 有 8 个兄弟，结点 B 是结点 A 的双亲，结点 B 的度是_。7、在含有 100 个结点的二叉链表中有_个空链域。共页第页共 4 页；第 1 页8、在有 200 个顶点的无向图中，边的数目最少是 0，最多是_。9、在以下有序表中，采用“折半查找”，找到
3、 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 分）共 4 页；第 2 页写出森林
4、的中序遍历序列（5 分）4、已知 8 个权值为4，29，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 页