：码号 证题考准写 要 不 内 线 封 密 ：业专考报 ：名姓如果您喜欢这份文档，欢迎下载！祝成绩进步，学习愉快！
2019年全国硕士研究生招生考试初试自命题试题 科目名称：数据结构（C语言版）（□√A卷□B卷）科目代码：856 考试时间：3小时 满分150分 可使用的常用工具：□√无 □计算器 □直尺 □圆规（请在使用工具前打√） 注意：所有答题内容必须写在答题纸上，写在试题或草稿纸上的一律无效；考完后试题随答题纸交回。 一、选择题(共15小题，每小题2分，共30分) 1. 计算算法的时间复杂度是属于一种（ ）的方法。 A）事前统计 B）事前分析估算 C）事后统计 D）事后分析估算 2. 数据的逻辑结构可以分为（ ）。 A）静态结构和动态结构 B）物理结构和存储结构 C）线性结构和非线性结构 D）虚拟结构和抽象结构 3. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。 A）必须是连续的 B）部分地址必须是连续的 C）一定是不连续的 D）连续不连续都可以 4. 线性表既可以用带头结点的链表表示，也可以用不带头结点的链表表示，前者最主要的好处是（ ）。 A）使空表和非空表的处理统一 B）可以加快对表的遍历 C）节省存储空间 D）可以提高存取表元素的速度 5. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后， rear 和front的值分别为（ ）。 A）1和5 B）2和4 C）4和2 D）5和1 6. 对二叉树T中的某个结点x，它在先根序列、中根序列、后根序列中的序号分别为pre（x），in（x）、post（x），a和b是T中的任意两个结点，下列选项一定错误的是（ ）。 A）a是b的后代且pre（a） 如果您喜欢这份文档，欢迎下载！祝成绩进步，学习愉快！ A）n-1 B）n C）n+1 D）n*logn 10. 下面（ ）方法可以判断出一个有向图中是否有环（回路）？ A）深度优先遍历 B）求最短路径 C）拓朴排序 D）求关键路径 11. 下列关于无向连通图特性的叙述中，正确的是（ ）。 （1）所有顶点的度数之和为偶数。 （2）边数比顶点个数减1要大。 （3）至少有1个顶点的度为1。 A）只有（1） B）只有（2） C）（1）和（2） D）（1）和（3） 12. 静态查找表与动态查找表二者的根本差别在于（ ）。 A）它们的逻辑结构不一样 B）施加在其上的操作不同 C）包含的数据元素的类型不一样 D）存储实现不一样 13. 设有100个结点,用二分法查找时,最大比较次数是（ ）。 A）25 B）50 C）10 D）7 14. 对初始数据序列｛8，3，9，11，2，1，4，7，5，10，6｝进行希尔排序。若第一趟排序结果为｛1，3，7，5，2，6，4，9，11，10，8｝，第二趟排序结果为｛1，2，6，4，3，7，5，8，11，10，9｝，则两趟排序采用的增量分别是（ ）。 A）3，1 B）3，2 C）5，2 D）5，3 15. 下列排序算法中，（ ）算法可能会出现下面情况：初始数据有序时，花费时间反而更多。 A）堆排序 B）冒泡排序 C）快速排序 D）希尔排序 二、填空题(共10小题，每小题2分，共20分) 1. 将两个各有n个元素的有序表归并成一个有序表，其最少比较次数是（ ）次。 2. 在无表头结点的单链表L的表头插入s结点的语句序列是（ ）。 3. 循环队列存储在数组A[0..m]中，尾指针为rear，则数据元素x入队时,首先将x放到队尾所在位置，然后队尾后移，其中队尾后移的操作语句为（ ）。 4. 由5个结点可以构造出（ ）种不同的树。 5. 已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点,则完全二叉树的结点个数最多是（ ）。 6. 设森林F中有3棵树，三棵树的结点个数依次是n1，n2和n3，则与森林F相对应二叉树的根结点的右子树上的结点个数是（ ）个。 7. 有n个结点，e条边的无向图采取邻接表存储，求最小生成树的Kruskal算法的时间复杂度是（ ）。 8. 已知一无向图G=（V，E），其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是（ ）遍历方法。 9. 有序表包含16个数据，顺序组织。若采用二分查找方法，则在等概率情况下，查找成第 2 页 共 5 页 如果您喜欢这份文档，欢迎下载！祝成绩进步，学习愉快！ 功时的ASL值是（ ）。 10. 一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆（大顶堆）中第2，3，4个排序码分别为（ ）。 三、判断题(对的答√错的答×，共10小题，每小题2分，共20分) 1. 数据元素是数据的最小单位。 2. 一般认为，随问题规模n的增大，算法执行时间的增长速度较快的算法最优。 3. 在一个长度为n的线性表的第i个位置（1≤i≤n+1）插入一个元素时，需要向后移动n+1-i个元素。 4. 用链接方式存储的队列，在进行出队运算时仅需修改头指针。 5. 对于任何一颗二叉树，如果其叶子结点数为n0，则度为2的结点数为n0－1。 6. 如果给定二叉树的先序遍历序列和后序遍历序列，则该二叉树是唯一的。 7. 一颗有n个顶点的生成树有且仅有n－1条边。 8. 对AOV网进行拓扑排序时，结束后如果还有顶点没有被输出，且这些顶点的入度均＞0，则该网必定有环存在。 9. 采用线性探测法处理冲突，在查找成功的情况下，可能要探测的这些位置上的关键字一定都是同义词。 10. 堆排序不是稳定的排序方法。 四、综合应用题(共5小题，每小题各8分，共40分) 1. 将如下图所示矩阵的非零元素逐行存放于数组B中（下标从0开始存放，即A11存放在B[0]中），使得B[k］=A[i，j］，求： （1）用i，j表示ｋ的变换公式。 （2）用ｋ表示i，j的变换公式。 a1,1a1,2a2,1a2,20123456a3,3a3,4a4,3a4,40 a2m-1,2m-1a2m-1,2m-1a2m,2m-1a2m,2m 3Λ 2. 已知AOV网的邻接表如下图所示，要求： V1V2V3V4V5V6Λ 265Λ 56Λ 45Λ 36Λ （1）画出该AOV网。 第 3 页 共 5 页 如果您喜欢这份文档，欢迎下载！祝成绩进步，学习愉快！ （2）给出基于该AOV网邻接表的从顶点V1出发的DFS序列。 （3）给出基于该AOV网邻接表的从顶点V1出发的BFS序列。 （4）写出对该AOV网按照上述邻接表进行拓扑排序得到的拓扑序列。 3. 根据下列二叉树，要求： （1）写出其先序遍历序列、中序遍历序列和后序遍历序列。 （2）顺序存储该二叉树，画出其存储示意图。 4. 如果一颗非空k叉树T（k≥2）中每个非叶子结点都有k个孩子。请回答下列问题并给出推导过程。 （1）若T有m个非叶子结点，则T的叶子节点有多少个？ （2）若T的高度为h，则T的结点数最多是多少个？最少是多少个？ 5. 散列表长度是13，散列函数H(K)=k % 13，解决冲突用线性探测再散列法。给定的关键字序列为{19,14,23,1,68,20,84,27,55,11,10,79}，要求： （1）画出哈希表。 （2）求出等概率下查找成功的平均查找长度。 （3）求出等概率下查找失败的平均查找长度。 五、算法设计题(共4小题，每小题10分，共40分) 1. 用带头结点的双向循环链表（结点结构为（Left，Data，Right））表示的线性表为L=（a1,a2, …an）。试设计如下算法Fun实现将L改造成：L=（a1,a3,…an,…a4,a2）。 void Fun(DbLinkList &L); 2. 若表达式以字符形式已存入数组s中，‘#’为表达式的结束符，试设计如下算法Match判断表达式中括号（‘([{}])’）是否配对，如果配对，则返回1，否则返回0。 int Match(char *s); 3. 树采用孩子兄弟链表作为存储结构（结点结构CSTree为（firstchild，data，nextsibling）），试设计如下非递归算法Leaf计算树的叶子节点数。 int Leaf(CSTree *T); //函数返回值就是树的叶子节点数 4. 已知无向图采用邻接表存储方式，试设计如下算法DeletEdge删除图中(i,j)边。 void DeletEdge(AdjList g,int i,int j); 第 4 页 共 5 页 如果您喜欢这份文档，欢迎下载！祝成绩进步，学习愉快！ 第 5 页 共 5 页
武汉科技大学856 数据结构(C语言版)-2019(A卷)
