1、 2017 年全国硕士研究生统一入学考试自命题试题（ B 卷） * 学科、专业名称：计算机科学与技术、软件工程 研究方向： 计算机系统结构 081201， 计算机软件与理论 081202， 计算机应用技术 081203，软件工程 083500， 计算机技术 (专业学位 ) 085211， 软件工程 (专业学位 ) 085212 考试科目名称及代码：数据结构 830 考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。 一 、 单项 选择题 (每题 2 分，共 30 分 ) 1. 一个队列的入列序列是 1,2,3,4, 则队列的输出序列是（ ）。 A. 4,3,2,1 B. 1,2
2、,3,4 C. 1,4,3,2 D. 3,2,4,1 2. 循环队列用数组 A0.m-1存放其元素值，已知其头尾指针分别是 front 和 rear, 则当前队列中的元素个数是 ( )。 A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front 3. 平衡二叉树的平均查找长度是 ( )。 A. O(n2） B. O(nlog2n） C. O(n） D. O(log2n） 4. 设 F 是由 T1、 T2 和 T3 三棵树组成的森林，与 F 对应的二叉树为 B， T1、 T2 和 T3 的结点数分别为 N1、 N2 和 N
3、3，则二叉树 B 的根结点的左子树的结点数为（ ）。 A. N1-1 B. N2-1 C. N2+N3 D. N1+N3 5. 计算机内部数据处理的基本单元 是 （ ）。 A. 数据 B. 数据元素 C. 数据项 D. 数据库 6. 设按照从上到下、从左到右的顺序从 1 开始对完全二叉树 的结点 进行顺序编号，则编 号为 i结点的左孩子结点的编号为（ ）。 A. 2i+1 B. 2i C. i/2 D. 2i-1 7. 设用邻接矩阵 A 表示有向图 G 的存储结构，则有向图 G 中顶点 i 的入度为（ ）。 A. 第 i 行非 0 元素的个数之和 B. 第 i 列非 0 元素的个数之和 C.
4、第 i 行 0 元素的个数之和 D. 第 i 列 0 元素的个数之和 8. 设一组初始记录关键字序列为 (16, 25,12, 30,47,11, 23,36, 9,18,31)，则以增量 d=5 的一趟希 尔排序结束后的结果为（ ）。 A. 11, 23,12, 9, 18,16, 25,36,30, 47, 31 B. 11, 23,12, 9, 16, 18, 25,36, 47, 30, 31 C. 16, 23,12, 9, 11,18, 25,36,30, 47, 31 C. 9, 11,12, 16, 18, 23, 25,30, 36, 47, 31 9. 设某有向图的邻接表中
5、有 n 个表头结点和 m 个表结点，则该图中有（ ）条有向边。 A. n B. n-1 C. m D. m-1 10. 设哈夫曼树中的叶子结点总数为 m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ ）个空指针域。 A. 2m-1 B. 2m C. 2m+1 D. 4m 11. 对于线性表（ 7， 34， 55， 25， 64， 46， 20， 10）进行散列存储时，若选用 H(K)=K %9 作为散列函数，则散列地址为 1 的元素有（ ）个 。 A 1 B 2 C 3 D 4 考试科目： 数据结构 共 5 页，第 1 页 12. 下面程序的时间复杂为（ ） 。 for（ i=1， s=0
6、； inext=s； s-prior=p； p-next-prior=s； s-prior=p-nest； B. s-prior=p; s-next = p-next; p-next=s; s-next-prior=s; C. p-prior=s； p-nest-prior=s； s-prior=p； s-next=p-prior； D. s-prior=p； s-next=p-next； p-next=s； p-next-prior=s； 二 填空题 (每 空 2 分，共 20 分 ) 1. 采 用堆排序、快速排序、冒泡排序，对初态为有序的表，最省时间的是 。 2. 设一组初始记录关键字序列
7、为 (49， 38， 65， 97， 76， 13， 27， 50)，则第 4 趟直接选择排序结束后的结果为 。 3. 当待排记录序列按关键字顺序有序时，直接插入排序和 冒 泡排序能达到 的时间复杂度，快速排序的时间性能 退 化为 (以第一个关键字为枢轴 )。 4. 判定顺序栈是否为空的条件是 ，判定顺序栈是否为满的条件是 。 5. 当向 B-树中插入关键字时 ,可能引起结点的 ,最终可能导致整个 B-树的高度增加 。 6. 设散列表的长度为 8，散列函数 H(k)=k%7，用线性探测法解决冲突，则根据一组初始关键字序列 (8， 15， 16， 22， 30， 32)构造出的散列表的平均查找长
8、度是 。 7. 设在一棵度数为 3 的树中，度数为 3 的结点数有 2 个，度数为 2 的结点数有 1 个，度数为1 的结点数有 2 个，那么度数为 0 的结点数有 个。 三判断题（每题 1 分，共 10 分 ， 正确的选 t，错误的选 f） 1. 顺序表查找指的是在顺序存储结构上进行查找。 （ ） 2. 循环队列中不存在队列满的问题。（ ） 3. n 阶对称矩阵可压缩存储到 n/2 个 单 元的空间中。 ( ) 4. 一个图的邻接 表 表示法是唯一的。 ( ) 5. 希尔排序是稳定的。 ( ) 6. 由树转化成二叉树，该二叉树的右子树不一定为空。（ ） 7. 根据拓扑排序结果可以判断一个有向
9、图中是否存在环路。（ ） 8. 稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非 0 元素。（ ） 9. 入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。 ( ) 10.数据元素是数据的最小单位。（ ） 考试科目： 数据结构 共 5 页，第 2 页 四 . 简答题 （ 45 分） 1. 设有 1000 个元素组成的无序序列，希望用最快的速度挑选 出其中前 10 个（仅挑前 10个）最大元素，以下几种排序方法中哪一种最合适？ 分析各排序算法 , 给出原因？ （ 7 分） （ 1）简单选择排序； （ 2）冒泡排序； （ 3）堆排序； （ 4）归并排序 2. 设二叉排序树中
10、关键字由 1 至 1000 的整数组成，现要查找关键字为 363 的结点，下面的关键字序列哪个不可能是在二叉树中查到的序列？说明原因。（ 5 分） （ 1） 51, 250, 501, 390, 320, 340, 382, 363 （ 2） 24， 877， 125, 342, 501， 623， 421, 363 3. 针对二叉树，回答以下问题： （ 1）具有 n 个结点的二叉树的最小深度是多少？最大深度是多少？（ 4 分） （ 2）具有 n 个结点的完全二叉树中有多少个叶子结点？有多少个度为 2 的结点？（ 4 分） （ 3）具有 n0 个叶子结点的完全二叉树中共有多少个结点？（ 4 分
11、） 4. 阅读如下程序，写出此程序的输出结果（其中栈的元素类型为 char）。 (5分 ) void main ( ) Stack S; char x, y; InitStack(S); x=y; y=s ; Push(S,x); Push(S,y); Pop(S,x); Push(S,k); Push(S,x); while(!StackEmpty(S) Pop(S,y); printf(y); 5. 给定图 1所示带权有向图，利用 Floyd算法，求每一对顶点之间的最短路径及其路径长度（要求写出求解过程）。 （ 10分） 图 1 6. 一个带权无向图的最小生成树是否一定唯一？在什么情况下构
12、造出的最小生成树可能不唯一？（ 6 分） 考试科目： 数据结构 共 5 页，第 3 页 五算法填空 （ 共 2 小题，每空 2 分，共 20 分 ） 1. 下面的算法是在带头结点的单链表 L 中第 i 个位置之前插入元素 e。请在 _处填上适当内容，使其成为一个完整算法。 typedef struct LNode ElemType data; struct LNode *next; LNode, * LinkList; Status ListInsert_L (LinkList j= (1) ; while (p (2) if (!p ) return ERROR; s=(LinkList)m
13、alloc(sizeof (LNode); s-date = e; (3) ; (4) return Ok ; 2. 下面是一个有向图 G 采用邻接表存储结构的拓扑排序算法。请在 _处填上适当内容，使其成为一个完整算法。 typedef struct VNode VertexType data; ArcNode *firstarc; VNode, AdjListMAX_VERTEX_NUM; typedef struct ArcNode int adjvex; struct ArcNode *nextarc; InfoType *info; ArcNode; typedef struct Ad
14、jList vertices; int vexnum, arcnum; int kind; ALGraph; 考试科目： 数据结构 共 5 页，第 4 页 Status TopologicalSort(ALGraph G) / 有向图 G 采用邻接表存储结构。若 G 无回路 ,则输出 G 的顶点的一个拓扑序列并返回 OK，否则返回 ERROR。 int indegreevexnum; FindInDegree(G, indegree); /对各顶点求入度 indegree 0.vexnum-1 InitStack(S); for(i=0; inextarc) k=p-adjvex; if(!(- -indegreek) （ 9） if( (10) ) return ERROR; else return OK; /TopologicalSort 六编写算法（ 25分） 1. 编写一个算法求二叉树中叶子结点的个数（ 10 分） 。 2. 已知 n 个顶点的带权图用邻接矩阵表示，试编写算 法实现用 kruskal 算法构造最小生成树。（ 15 分） 考试科目： 数据结构 共 5 页，第 5 页
