武汉纺织大学2015年招收硕士学位研究生试卷科目代码848科目名称数据结构考试时间2014年12月28日下午报考专业1、试题内容不得超过画线范围，试题必须打印，图表清晰，标注准确。2、试题之间不留空格。3、答案请写在答题纸上，在此试卷上答题无效。题号一二三四五六七八九十十一得分得分本试卷总分150分，考试时间3小时。一、填空题（每空3分，共30分）1、根据数据元素之间关系的不同特性，通常有下列四类基本结构：集合、_____、树形结构和图状结构。2、算法具有五个重要特性：有穷性、确定性、_____、输入和输出。3、以下程序段中语句“++x;”的频度是_____。for(i=1;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,60,80)10、设待排序序列中记录的个数为n，则堆排序在最坏情况下，其时间复杂度为_____。二、解答题（共100分）1、已知静态链表如下图所示，在数据元素“ZHOU”之前插入数据元素“SHI”，然后删除数据元素“ZHENG”，试画出插入删除后的静态链表。（10分）2、已知某二叉树的先序遍历序列为ABDFCEG，中序遍历序列为FDBACEG，要求：①画出该二叉树（10分）②写出该二叉树的后序遍历序列（5分）3、有如下所示的二叉树，要求：①画出该二叉树对应的森林（10分）共4页；第2页②写出森林的中序遍历序列（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)＝keyMOD13，哈希表长为16，采用开放定址法处理冲突，增量序列选用线性探测再散列。要求：①构造并画出哈希表（10分）②假设每个记录的查找概率相等，求查找成功时的平均查找长度（5分...
