下载文档原格式
中国计量大学2019年硕士研究生招生考试试题考试科目代码：806 考试科目名称：数据结构与操作系统所有答案必须写在报考点提供的答题纸上，做在试卷或草稿纸上无效。
一、 单项选择题：1～30小题，每小题2分，共60分。
1.以下T(n)表示各算法中最耗时操作的执行次数，n表示数据量，请按照时间复杂度从小到大排列，正确的是（）。
T1(n) = 100n + 200logn2T2(n) = 3n2T3(n) = 10000000nT4(n) = 300log2A.T1<T2<T3<T4 B．T2<T1<T4<T3C．T3<T4<T1<T2 D．T3<T1<T4<T22.在一个无序数据序列上进行查找，分别采用以下算法，速度最快的是（ ）。
A．折半查找 B．顺序查找 C．二叉排序树查找 D．哈希表查找3.下列关于线性表的描述，错误的是（ ）。
A.顺序表不能进行插入操作B.顺序表可以进行插入操作C.顺序表适宜于随机存取D.链表适宜于顺序存取4.往队列中依次输入序列{1,2,3,4}，经过若干入队与出队操作，队列中剩下的数据可能是（ ）。
A．1 B．2 C．3 D．4《数据结构与操作系统》试卷第1页共9 页5.往栈中依次输入序列{1,2,3,4}，经过若干入栈队与出栈操作，关于栈中剩下的数据正确的是（ ）。
A.不可能是4 B．无法确定C．不可能是2 D．不可能是16.已知一棵完全二叉树的第3层有3个叶子节点（树根为第1层），则这棵完全二叉树的节点个数最多有几个（ ）。
A．6 B．8 C．9 D．127.下列关于堆的描述，错误的是（ ）。
A．堆是满二叉树B．大根堆的树根关键字大于其子树中的所有结点的关键字C．堆一般用数组来表示D．大根堆的右子树中所有结点的关键字小于树根关键字8.关于图1的邻接矩阵，如果结点A的出度为2，则描述错误的是（ ）。
A．结点A到结点C的最短路径长度为4B. 结点A的度为3C．结点A到C只有2条路径D．结点E的度为2A B C D E FA 1 2B 34C 5 6D 7E 8F 9图1. 题8的邻接矩阵9.下列排序算法中，时间复杂度与快速排序相同的是（ ）。
2019年中国科学院大学862计算机学科综合(非专业)考研初试大纲《计算机学科综合(非专业)》考试大纲本《计算机学科综合(非专业)》考试大纲适用于中国科学院大学非计算机科学与技术一级学科下各专业的硕士研究生入学考试。
《计算机学科综合(非专业)》主要内容包括数据结构、操作系统和计算机网络三大部分。
要求考生对计算机科学与技术及相关学科的基本概念有较深入、系统的理解;掌握各种数据结构的定义和实现算法;掌握操作系统和计算机网络所涉及的关键内容，并具有综合运用所学知识分析问题和解决问题的能力。
一、考试内容数据结构1、绪论(1)数据结构的基本概念，数据的逻辑结构、存储结构。
(2)算法的定义、算法的基本特性以及算法分析的基本概念。
2、线性表(1)线性关系、线性表的定义，线性表的基本操作。
(2)线性表的顺序存储结构与链式存储结构(包括单链表、循环链表和双向链表)的构造原理。
在以上两种存储结构上对线性表实施的最主要的操作(包括三种链表的建立、插入和删除、检索等)的算法设计。
3、堆栈与队列(1)堆栈与队列的基本概念、基本操作。
(2)堆栈与队列的顺序存储结构与链式存储结构的构造原理。
(3)在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作对应的算法设计。
4、串(1)串的基本概念、串的基本操作和存储结构。
(2)串的模式匹配算法和改进的KMP算法5、数组和广义表(1)数组的概念，以及表示和实现(2)矩阵(对称矩阵和稀疏矩阵)的压缩存储(3)广义表的基本概念6、树与二叉树(1)树的定义和性质(2)二叉树的概念、性质和实现(3)遍历二叉树和线索二叉树(4)树和森林(5)赫夫曼树及其应用(6)回溯法与树的遍历(7)树的计数7、图(1)图的定义，基本概念，图的分类，常用名词术语。
(2)图的邻接矩阵存储方法、邻接表存储方法的构造原理。
(3)图的遍历操作。
(4)图的连通性、最小生成树(5)最短路径的计算(6)AOV网与拓扑排序。
A-6-1 河北大学课程考核试卷—学年第学期级专业（类）考核科目数据结构课程类别必修课考核类型考试考核方式闭卷卷别（注：考生务必将答案写在答题纸上，写在本试卷上的无效）一、单项选择题（共20分，每题2分）1、线性表采用链式存储时，结点的存储地址（）A A、必须是不连续的、必须是不连续的、必须是不连续的B B B、连续与否均可、连续与否均可C 、必须是连续的、必须是连续的D D D、和头结点的存储地址相连续、和头结点的存储地址相连续2、下列说法不正确的是（）A 、栈是一种运算受限的线性表、栈是一种运算受限的线性表 B B B、栈是一种后进先出的线性结构、栈是一种后进先出的线性结构C 、栈可以是线性结构也可以是非线性结构、栈可以是线性结构也可以是非线性结构D D D、栈可以用数组实现或链表来实现、栈可以用数组实现或链表来实现3、设循环队列中数组的下标范围是0 0 ～～ n-1 n-1，，f 表示队首元素的前驱位置，表示队首元素的前驱位置，r r 表示队尾元素的位置，则队列中元素个数为（）。
A 、r-fB r-f B、、r-f+1C r-f+1 C、、(r-f+1)mod nD (r-f+1)mod n D、、(r-f+n)mod n4、一棵度数为4的树，它的4度结点有1个，个，33度结点有2个，个，22度结点有3个，1度结点有4个，问它的叶子结点有多少个？（）A 、5B 5 B、、 6C 6 C、、 9D 9 D、、 115、在含n 个顶点和e 条边的有向图的邻接矩阵中，零元素的个数为（）A 、e B 、2e C 、n 2-e D 、n 2-2e 6、已知一个有向图如右所示，则从定点a 出发进行深度优先遍历，不可能得到的DFS 序列为（） A A、、 adbefcB B、、 adcefbC C、、 adcbfeD D、、 adefcb7、一棵深度为k 的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树的共有（共有（ ）个结点。
数据结构考研真题及其答案数据结构是计算机科学与技术专业考研中的重要科目之一，它对于培养学生的程序设计和算法分析能力具有关键作用。
以下将为大家呈现一些典型的数据结构考研真题，并提供详细的答案解析。
一、选择题1、若一个栈的输入序列为 1, 2, 3, 4, 5，不可能得到的输出序列是（）A 2, 3, 4, 1, 5B 5, 4, 3, 2, 1C 1, 5, 4, 3, 2D 3, 4, 2, 5, 1答案：C解析：栈的特点是“后进先出”。
对于选项 C，先输出 1，意味着 2、3、4、5 都已入栈，此时栈顶元素为 5，不可能接着输出 5 之后就输出4。
2、已知一棵二叉树的先序遍历序列为 ABCDEFG，中序遍历序列为 CBDAEGF，则其后序遍历序列为（）A CDBAFGEB CDBGFEAC CDBAGFED BCDAFGE答案：B解析：先根据先序和中序遍历序列构建二叉树。
先序遍历中第一个节点 A 为根节点，在中序遍历中找到 A，其左边的 CBD 为左子树，右边的 EGF 为右子树。
同样的方法确定左子树和右子树的结构。
然后按照“左子树右子树根节点”的顺序得到后序遍历序列 CDBGFEA。
3、对于一个具有 n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的非零元素个数为（）A n(n 1) ／ 2B n(n ＋ 1) ／ 2C n(n 1)D n(n ＋ 1)答案：A解析：无向图的邻接矩阵是对称的。
对于顶点 i 和 j（i ≠ j），若它们之间有边，则矩阵中对应位置为 1，共有 n(n 1) ／ 2 对不同的顶点对，所以非零元素个数为 n(n 1) ／ 2 。
二、简答题1、简述冒泡排序的基本思想，并分析其时间复杂度和空间复杂度。
答案：冒泡排序的基本思想是通过相邻元素的两两比较和交换，将最大（或最小）的元素逐步“浮”到数组的一端。
时间复杂度：在最坏情况下，即数组完全逆序，需要进行 n 1 轮比较，每轮比较 n i 次（i 为轮数，从 1 到 n 1），所以总的比较次数为n(n 1) ／ 2，时间复杂度为 O(n^2)。
2019年考研计算机学科专业基础综合真题及答案解析(1/40)单项选择题第1题设n是描述问题规模的非负整数，下列程序段的时间复杂度是x=0；while(n＞=(x+l)*(x+l))x=x+l；A.O(log n)B.O(n1/2)C.O(n)D.O(n2)下一题(2/40)单项选择题第2题若将一棵树T转化为对应的二又树BT，则下列对BT的遍历中，其遍历序列与T的后根遍历序列相同的是A.先序遍历B.中序遍历C.后序遍历D.按层遍历上一题下一题(3/40)单项选择题第3题对n个互不相同的符号进行哈夫曼编码。
若生成的哈夫曼树共有115个结点，则n的值是A.56B.57C.58D.60上一题下一题(4/40)单项选择题第4题在任意一棵非空平衡二又树(AVL树)T1中，删除某结点v之后形成平衡二又树T2，再将w插入T2形成平衡二又树T3。
下列关于T1与T3的叙述中，正确的是I.若v是T1的叶结点，则T1与T3可能不相同Ⅱ.若v不是T1的叶结点，则T1与T3一定不相同Ⅲ.若v不是T1的叶结点，则T1与T3一定相同A.仅IB.仅IIC.仅I、ⅡD.仅I、Ⅲ上一题下一题(5/40)单项选择题第5题下图所示的AOE网表示一项包含8个活动的工程。
活动d的最早开始时间和最迟开始时间图片A.3和7B.12和12C.12和14D.15和15上一题下一题(6/40)单项选择题第6题用有向无环图描述表达式(x+y)*((x+y)/x)，需要的顶点个数至少是A.5B.6C.8D.9上一题下一题(7/40)单项选择题第7题选择一个排序算法时，除算法的时空效率外，下列因素中，还需要考虑的是I.数据的规模Ⅱ.数据的存储方式Ⅲ.算法的稳定性V.数据的初始状态A.仅ⅢB.仅I、ⅡC.仅Ⅱ、Ⅲ、IVD.I、Ⅱ、Ⅲ、Ⅳ上一题下一题(8/40)单项选择题第8题现有长度为11且初始为空的散列表HT，散列函数是H(key)=key%7，采用线性探查(线性探测再散列)法解决冲突将关键字序列87，40，30，6，11，22，98，20依次插入到HT后，HT查找失败的平均查找长度是A.4B.5.25C.6D.6.29上一题下一题(9/40)单项选择题第9题设主串T=“abaabaabcabaabc”，模式串S=“abaabc”，采用KMP算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是A.9B.10C.12上一题下一题(10/40)单项选择题第10题排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。
2019年全国硕士研究生招生考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：1~40小题，每小题2分，共80分。
下列每题给出的四个选项中，只有一个选项符合试题要求。
1.设n是描述问题规模的非负整数，下列程序段的时间复杂度是x=0；while(n>=(x+l)*(x+l))x=x+l；A. O(log n)B. O(n1/2)C. O(n)D. O(n2)2.若将一棵树T转化为对应的二又树BT，则下列对BT的遍历中，其遍历序列与T的后根遍历序列相同的是A. 先序遍历B. 中序遍历C. 后序遍历D. 按层遍历3.对n个互不相同的符号进行哈夫曼编码。
若生成的哈夫曼树共有115个结点，则n的值是A. 56B. 57C. 58D. 604.在任意一棵非空平衡二又树(AVL树)T1中，删除某结点v之后形成平衡二又树T2，再将w插入T2形成平衡二又树T3。
下列关于T1与T3的叙述中，正确的是I.若v是T1的叶结点，则T1与T3可能不相同Ⅱ.若v不是T1的叶结点，则T1与T3一定不相同Ⅲ.若v不是T1的叶结点，则T1与T3一定相同A. 仅IB. 仅IIC. 仅I、ⅡD. 仅I、Ⅲ5.下图所示的AOE网表示一项包含8个活动的工程。
活动d的最早开始时间和最迟开始时间分别是A. 3和7B. 12和12C. 12和14D. 15和156.用有向无环图描述表达式(x+y)*((x+y)/x)，需要的顶点个数至少是A. 5B. 6C. 8D. 97.选择一个排序算法时，除算法的时空效率外，下列因素中，还需要考虑的是I.数据的规模Ⅱ.数据的存储方式Ⅲ.算法的稳定性V.数据的初始状态A. 仅ⅢB. 仅I、ⅡC. 仅Ⅱ、Ⅲ、IVD. I、Ⅱ、Ⅲ、Ⅳ8.现有长度为11且初始为空的散列表HT，散列函数是H(key)=key%7，采用线性探查(线性探测再散列)法解决冲突将关键字序列87，40，30，6，11，22，98，20依次插入到HT后，HT查找失败的平均查找长度是A. 4B. 5.25C. 6D. 6.299.设主串T=“abaabaabcabaabc”，模式串S=“abaabc”，采用KMP算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是A. 9B. 10C. 12D. 1510. 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。
