2018 年全国硕士研究生统一入学考试自命题试题（ A 卷）*学科、专业名称：计算机科学与技术、软件工程研究方向：计算机系统结构 081201，计算机软件与理论 081202，计算机应用技术081203，软件工程 083500，计算机技术(专业学位) 085211考试科目名称及代码：数据结构 830考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。 一、 单项选择题(每题 2 分，共 30 分) 1. 任何一棵二叉树 T, 如果度为 1 的结点数为 2，度为 0 结点数为 11，其分支数为 ( ) 。 A. 23 B. 22 C. 24 D. 212. 深度为 k 的二叉树至多有( ) 个结点(k>=1)；A. 2k B. 2k-1 C. 2k+1 D.2k-13. 已知一棵二叉树结点的中序序列为 BDCEAFHG, 后序序列为 DECBHGFA, 则结点的先序序列为( ) 。A. ABCDEFGH B. DGBFHCA C. DECBGFAH D. CAFHGDB4. 在有向图的逆邻接表存储结构中，顶点 v 在表结点中出现的次数是（ ）。A. 顶点 V 的度 B. 顶点 V 的出度 C. 顶点 V 的入度 D. 依附于顶点 V 的边数5. 顺序栈 s 的 GetTop(s, e)操作是用 e 返回 s 的栈顶元素，则下列( )是正确的操作。A. e=*(s.top) B. e=*(s.top-1) C. e=*(-s.top) D. e=s.top-16. 若线性表最常用的操作是存取第 i 个元素及其前趋的值, 则采用( )存储方式节省时间.A. 单链表 B. 双链表 C. 单循环链表 D. 顺序表7. 在一棵非空 m 阶的 B-树上，除根之外的所有非终端结点 （ ）。A. 至少有 棵子树 B. 至多有 棵子树 2/ 2/mC. 至少有 棵子树 D. 至多有 棵子树/ /8. 若用单链表来表示队列，最适合队列操作的是（ ）。A. 带尾指针的非循环队列 B. 带尾指针的循环链表C. 带头指针的非循环链表 D. 带头指针的循环链表9. 下面的序列中, ( )是堆。A. 12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49B. 12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49C. 12, 36, 27, 20, 40, 34, 98, 81, 73, 55, 49D. 12, 36, 35, 65, 40, 34, 98, 81, 73, 55, 4910. 设有一个 10 阶的对称矩阵 A, 采用压缩存储方式, 以行序为主序存储其下三角,a 11 为第一个元素, 其首存储地址为 1, 每个元素占 1 个地址空间 , 则 a85 的地址为( ) 。A. 32 B. 33 C. 34 D. 40考试科目： 数据结构 共 5 页，第 1 页11. 用带头结点的单链表存储队列，其队头指针指向头结点，队尾指针指向队尾结点，则在进行出队时（ ）。A. 仅修改队头指针 B. 仅修改队尾指针C. 对头、尾指针都要修改 D. 对头、尾指针都可能要修改12. 由权为 7,2,4,5 的四个叶子结点构造一个哈夫曼树，该树的带权路径长度为（ ）。A. 33 B. 36 C. 35 D. 3413. 现有一“遗传“关系：设 x 是 y 的父亲，则 x 可以把它的属性遗传给 y。表示该遗传关系最适合的数据结构为 ( ) 。A向量 B图 C树 D二叉树14. 线性表是具有 n 个 ( )的有限序列。A. 表元素 B. 字符 C. 数据元素 D. 数据项15. 在所有排序方法中，关键字的比较次数与记录的初始排列无关的是（ ）。A. 希尔排序 B. 冒泡排序 C. 直接插入排序 D. 直接选择排序二填空题(每空 2 分，共 20 分)1. 单链表中设置头结点的作用是 。2. 操作系统中先来先服务是 数据结构应用的典型例子。3. 对线性表进行折半查找时，要求线性表必须 。4. 在中序线索二叉树上，若当前访问节点的右标志为 0，根据中序遍历的定义，它的后继结点是 。5. 哈夫曼树是带权路径长度 的二叉树 , 通常权值较大的结点离根 。6. 在 m 阶 B-树中某结点插入一个关键字后，若该结点的关键字数目已达 时，就要对该结点进行分裂。7. 顺序查找一个共有 n 个元素的线性表，其时间复杂度为 。 8. 对于含有 n 个顶点 e 条边的无向连通图, 利用广度优先搜索遍历图的时间复杂度为 。9. Dijkstra 算法是按 次序产生一点到其余各定点最短路径的算法。三判断题（每题 1 分，共 10 分，正确的选 t，错误的选 f）1. 将一棵树转换成二叉树后，根结点无右子树。 （ ）2. 归并排序是不稳定的排序方法。 （ ）3. 在一个有向图的邻接表中，如果某个顶点的链表为空，则该顶点的出度一定为零。（ ）4. 在二叉树的第 6 层上至多有 31 个结点。（ ）5. B-树和 B+树都能有效地支持随机检索。( )6. 图 G 的最小生成树的代价一定不大于其他生成树的代价。 ( )7. 一个无序的元素序列可以通过构造一棵二叉排序树而变成一个有序的元素序列。（ ）8. 图的多重邻接表表示法中，表中结点的数目是图中边的条数。（ ）9. 对特殊矩阵压缩可以降低运算的时间复杂度。 ( ) 10. 无向图的邻接矩阵是对称的，因此可只存储矩阵的下三角阵。 （ ）四. 简答题（45 分）1. 利用拓扑排序的方法求出图 1 所示有向图的所有拓扑序列。对于有向无环图，还可使用什么方法获得拓扑序列？（10 分）考试科目： 数据结构 共 5 页，第 2 页图 12. 一棵二叉树，若根结点的左右子树均有三个结点，其左子树的先序序列与中序序列相同，右子树的中序序列与后子序序列相同，试构造该二叉树。（7 分）3. 已知序列(12,18,4,3,6,13,2,9,19,8) 。请给出采用希尔排序对该序列作升序排序的每一趟结果（步长分别为 5,3,2,1）。（8 分）4. 设有一组关键字(33,41,20,24,30,13,01,67), 采用散列函数 H(key)=(3*key) %11, 采用线性探测再散列解决冲突, H i=(H(key)+di)%11,其中 di=1,2,10. 试在 010 的散列地址空间中对该关键字序列（按从左到右的次序）构造散列表，并计算在查找概率相等的前提下，查找成功时的平均查找长度。（10 分）5. 已知图 2 所示的有向图。设其顶点 a,b,c,d,e 表示一个乡的 5 个村庄，弧上的权值表示为两村之间的距离。乡内要建立一所学校，问学校设在哪个村庄才能使从各村出发到学校的距离总和最小。（要求回答解决上述问题应采用什么算法，并写出应用该算法解答上述问题的每一步计算结果）。（10 分）图 2考试科目： 数据结构 共 5 页，第 3 页五、算法填空（共 2 小题，每空 2 分，共 20 分）1. 已知一个顺序存储线性表的元素递增有序排列。下面的算法实现删除该表中值相同的元素。请在_处填上适当内容，使其成为一个完整算法。typedef struct ElemType *elem; int length ; int listsize ; SqList; void dele(SqList while ( (1) ) if ( L.elemj!=L.elemi) L.elem+i= (2) ；(3) ; L.length= (4) ;2. 下面算法是用 Dijkstra 算法求有向网 G 的 v0 顶点到其余顶点 v 的最短路径 Pv及其带权长度 Dv。若 Pvw为 TRUE，则 w 是从 v0 到 v 当前求得最短路径上的顶点。 finalv为 TRUE 当且仅当 vS（S 为已求得最短路径的终点的集合）, 即已经求得从v0 到 v 的最短路径。请在_处填上适当内容，使其成为一个完整算法。typedef struct ArcCellVRType adj;InfoType *info; /该弧相关信息的指针ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM；tpyedef structVertexType vexsMAX_VERTEX_NUM; /顶点向量AdjMatrix arcs; /邻接矩阵int vexnum,arcnum; /图的当前顶点数和弧数GraphKind kind; /图的种类标志MGraph;void ShortestPath_DIJ( MGraph G, int v0, PathMatrix v<G.vexnum; +v) finalv = FALSE; Dv = (5) ;for (w=0; (6 ) ; +w) Pvw = FALSE; if (Dv < INFINITY) Pvv0 = TRUE; Pvv = TRUE; Dv0 = 0; (7) ; for (i=1; i<G.vexnum; +i) min = INFINITY; for (w=0; w<G.vexnum; +w) 考试科目： 数据结构 共 5 页，第 4 页if (!finalw) if ( (8 ) ) v = w; min = Dw; finalv = TRUE; for (w=0; w<G.vexnum; +w) if ( (9) ) Dw = (10 ) ;for(j=0;j<G.vexnum;j+) Pwj = Pvj; /第 v 行赋值于第 w 行Pww =TRUE; /if 六编写算法（25 分）1. 假设二叉树采用二叉链存储结构存储，试编写一个非递归算法，输出先序遍历序列中第k 个结点的数据值。（10 分）2. 设计算法，对 n 个关键字取实数值的记录序列进行整理，以使所有关键字为负值的记录排序在非负值的记录之前（要求尽量减少记录的交换次数）。(8 分）3. 试编写出一个判别表达式中左、右小括号是否配对出现的算法。（7 分）考试科目： 数据结构 共 5 页，第 5 页