武汉纺织大学2017年招收硕士学位研究生试卷科目代码848科目名称数据结构考试时间2016年12月25日下午报考专业1、试题内容不得超过画线范围，试题必须打印，图表清晰，标注准确。2、试题之间不留空格。3、答案请写在答题纸上，在此试卷上答题无效。题号一二三四五六七八九十十一得分得分本试卷总分150分，考试时间3小时。一、填空题（每空3分，共30分）1、_____是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号总称。2、根据数据元素之间关系的不同特性，通常有下列四类基本结构：集合、线性结构、_____、图状结构或网状结构。3、算法具有下列五个重要特性：_____、确定性、可行性、输入、输出。4、以下程序段的时间复杂度为_____。for(i=1;i<=n;i++)for(j=1;j<=n;j++){c[i][j]=0;for(k=1;k<=n;k++)c[i][j]+=a[i][k]*b[k][j];}5、在长度为n的顺序表的第i个元素ai之前插入一个元素，需移动_____个元素。(a1,a2,...,ai,...,an)共页第页共4页；第1页6、栈的入栈序列为abcdefg，出栈序列的第一个元素是g，则出栈序列的第五个元素是_____。7、深度为10的满二叉树共有_____个结点。8、二叉树中有100个度为2的结点，该二叉树中有_____个度为0的结点。9、无向图中共有20个顶点，当具有_____条边时，该无向图被称为完全图。10、按排序方法的稳定性而言，希尔排序是_____的排序方法。二、解答题（共100分）1、已知循环队列的最大长度为6，队列中已有3个元素，队列头元素是a，队列尾元素是c，如下图所示。依次进行三步操作：d入队列；e入队列；一个元素出队列。abc12345frontrear0①画出“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、已知无向图的邻接表如下图所示共4页；第2页EADCB504^0^120123430^10^F530^45^①根据邻接表计算顶点A的度（5分）②根据邻接表，从顶点B出发进行遍历，写出深度优先搜索的遍历结果序列（5分）③根据...
