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