2019考研计算机数据结构试题及答案

本文部分内容来自网络整理，本司不为其真实性负责，如有异议或侵权请及时联系，本司将立即删除！== 本文为word格式，下载后可方便编辑和修改！ ==数据结构试卷篇一：数据结构试题及答案数据结构试卷（一）.................. 1 数据结构试卷（二）.................. 5 数据结构试卷（三）.................. 7 数据结构试卷（四）.................. 9 数据结构试卷（五）................. 12 数据结构试卷（六）................. 15 数据结构试卷（七）................. 17 数据结构试卷（八）................. 19 数据结构试卷（九）................. 21 数据结构试卷（十）................. 24 数据结构试卷（一）参考答案 (27)数据结构试卷（二）参考答案 ........ 28 数据结构试卷（三）参考答案 ........ 29 数据结构试卷（四）参考答案 ........ 31 数据结构试卷（五）参考答案 ........ 33 数据结构试卷（六）参考答案 ........ 34 数据结构试卷（七）参考答案 ........ 37 数据结构试卷（八）参考答案 ........ 38 数据结构试卷（九）参考答案 ........ 39 数据结构试卷（十）参考答案 .. (40)数据结构试卷（一）一、单选题（每题 2 分，共20分）1. 栈和队列的共同特点是( a )。

A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点2. 用链接方式存储的队列，在进行插入运算时( d ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3. 以下数据结构中哪一个是非线性结构？( d )A. 队列B. 栈C. 线性表D. 二叉树4. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

2018最新十套数据结构试题及答案汇编2018数据结构试题（一） (1)2018数据结构试题（二） (5)2018数据结构试题（三） (8)2018数据结构试题（四） (11)2018数据结构试题（五） (15)2018数据结构试题（六） (19)2018数据结构试题（七） (22)2018数据结构试题（八） (25)2018数据结构试题（九） (28)2018数据结构试题（十） (32)2018数据结构试题（一）答案 (35)2018数据结构试题（二）答案 (37)2018数据结构试题（三）答案 (39)2018数据结构试题（四）答案 (42)2018数据结构试题（五）答案 (45)2018数据结构试题（六）答案 (47)2018数据结构试题（七）答案 (50)2018数据结构试题（八）答案 (52)2018数据结构试题（九）答案 (54)2018数据结构试题（十）答案 (56)数据结构试题（一）一、单选题（每题2 分，共20分）1.栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时( ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构？( )A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

A．688 B．678 C．692 D．6965.树最适合用来表示( )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. O（1）B. O（n）（1og2n） D. O（n2）9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（）个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

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=“abaab c”，采用KMP算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是A. 9B. 10C. 12D. 1510. 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。

2019年哈尔滨工业大学854数据结构真题一、选择题1。

向栈内输入a1,2,3,4,5,6,输出顺序应该类似于a3,4,2,1,5,6这样的顺序，问栈的容量2。

高度为5的4阶b树，所含的关键字的最小数目是多少3。

以一个序列建立堆排序，例如46 39 54…，问建立的堆初始排序是哪个（这个比较狡猾没说是最大堆还是最小堆）4。

在拓扑排序中，v在u前面，则选项中哪一个是不可能的，有一个是有一条u到v的路径5。

prim算法求最小生成树，VT={1,2,3}，ET={（1,2）（2,3）},接下来的最小代价边要从哪个序列里找6。

平衡二叉树问题，A是最低的不平衡点，A的左子树平衡度为1，右子树平衡度为0，A需如何调整成平衡二叉树7。

n个顶点组成无向图，各顶点的度中最大是多少8。

初始有序的哪种排序方法更好（冒泡）二、填空题1。

算法的时间复杂度不仅跟问题的规模有关，还跟实例的输入有关2。

使用2路归并n个数，需要次3。

给出后序序列，中序序列，求前序序列4。

kmp算法求串abaabc的next数组5。

给了5个数，求组成的哈夫曼树的wpl6。

哈希散列要解决和问题。

7。

散列表中散列函数hash=k mod 11，空间是14，给出了4个已知数的散列地址，问若使用拉链法处理冲突，则某一个数在表中的位置8。

快速排序不适合什么情况三、简答题1。

有n个人，m对朋友关系，朋友的朋友也是朋友，这样组成1个朋友圈，问怎么求有多少个朋友圈（实质就是无向图求连通分量）2。

一项工程，有11项项目，每个项目有完成所需时间及前置任务（或者10项，记得不是很准，那个图类似于哈工大的教材149页的图，其中试卷中a6的前置任务a6，这个应该是印错了，可能是a3）。

求：（1）使用合适模型表示（2）最少需多久完成整个项目，即求关键路径（3）给出如何求最少时间的方法四、算法题1。

构造一种特殊的队列结构，其中每个结点都有权值，每一次从队列中取出的节点都是最高优先权，设计算法输出（1）最小权值（2）插入一个数（3）删除最小权值，要求时间复杂度在log n以内2。

2019年山东烟台大学数据结构考研真题一、单项选择题(本大题共20小题，每小题2分，计40分)1.算法的时间复杂度主要取决于( )。

A.计算的环境B.待处理数据的值C.问题的规模D.数据的类型2.算法应具备( )这三个特性。

A.可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性C.确定性、有穷性、稳定性D.易读性、稳定性、安全性3.以下与数据的存储结构无关的术语是( )。

A.循环队列B.链表C.哈希表D.栈4.以下数据结构中，哪一个是非线性结构( )?A. 串B.队列C.栈D.广义表5.分析下面的程序，算法的时间复杂度为( )。

for(k=1;k<n;k++)for(j=1;j<n;j++) x=x+1;A. 0(2n)B.0(n)C. 0(n)D. 0(logsn)6.以下数据结构中，多型数据类型结构是( )。

A.栈B.广义表C.数组D.字符串7.顺存储设计时，存储单元的地址( )。

A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续8.串是一种特殊的线性表，其特殊形表现在( )。

A.可以顺序存储B.数据元素是单个字符C.可以连接存储D.数据元素类型相同9.以下可以用于定义一个完整的数据结构的是( )。

A.数据元素B.数据对象C.数据关系 ID.抽象数据类型10.有关图中路径的定义，表述正确的是( )。

A.路径是顶点和相邻顶点偶对构成的边所形成的序列B.路径是图中相邻顶点的序列C.路径是不同边所形成的序列D.路径是不同顶点和不同边所形成的集合11.已知有向图G=(V,E),其中V=(V1,V2,V3,V4,V5,V6,V7),E={<V1,V2),<V1,V3>,<V1,V4>, <V2,V5>,<V3,V5>,<Y3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},则图G的拓扑序列是()。

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=“abaab c”，采用KMP算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是A. 9B. 10C. 12D. 1510. 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。

2019年云南昆明理工大学计算机学科基础综合考研真题A卷数据结构部分：一、选择题：（40分，每题2分）1.已知10个数据元素（54，28，16，34，73，62，95，60，26，43），按照依次插入结点的方法生成一棵二叉排序树后，则查找值为62的结点所需比较的次数是[ ]。

A. 2B. 3C. 4D. 52.在一棵完全二叉树中，若编号为 j 的结点有右孩子，则该结点的编号为[ ] 。

A. 2*j-1B. 2*jC. 2*j+1D. j/23.在线性表的存储结构中，[ ]查找（按关键字查找）、插入、删除速度慢，但顺序存取和随机存取第i个元素速度快；[ ]查找和存取速度快，但插入、删除速度慢；[ ]查找、插入和删除速度快，但不能进行顺序存取；[ ]插入、删除和顺序存取速度快；但查找速度慢。

A. 顺序有序表,散列表，顺序表，链接表B. 顺序有序表，链接表，散列表，顺序表C. 顺序表，顺序有序表，散列表，链接表D. 顺序表，顺序有序表，链接表，散列表4.由分别带权为9，2，5，7的四个叶结点构造一棵哈夫曼树，则该树的带权路径长度是[ ]。

A. 23B.37C. 44D. 465.如果已知一个栈的入栈序列是：1，2，3，．．．，n，其出栈序列是：p1，p2，p3，．．．，pn，若p1=n，则pi为 [ ]A．i B．n+i C．n-i D．n-i+16.已知8个数据元素（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，则最后两层上的结点总数是[ ]。

A. 1B. 2C. 3D. 47.对线性表进行二分查找时，要求线性表必须是[ ]。

A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且数据元素有序D.以链接方式存储，且数据元素有序8.一个中缀算术表达式a+（b-x）*y，则对应的后缀算术表达式为[ ]。

A. a b x y - * +;B. a b x - + y *;C. a b x - y * +;D. a b x y * - +;9.已知一个有序表为（12，18，24，35，47，50，62，83，90，115，134），当二分查找值为90的元素时，[ ]次比较后查找成功；当二分查找值为47的元素时，[ ] 次比较后查找成功。

2019 年全国硕士研究生招生考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：1~40 小题，每小题 2 分，共80 分。

下列每题给出的四个选项中，只有一个选项符合试题要求。

1. 设n 是描述问题规模的非负整数，下列程序段的时间复杂度是x=0 ；while ( n>= ( x+l ) * ( x+l )) ；x=x+l1/22 )O( n) B. O( nD. C. A. O( log n)O( n)BT 若将一棵树T 转化为对应的二又树，则下列对BT 的遍历中，其遍历序列与T 的后根遍历序列相同的 2.是A. 先序遍历B. 中序遍历C. 后序遍历D. 按层遍历115 个结点，则n 的值是对n 个互不相同的符号进行哈夫曼编码。

若生成的哈夫曼树共有 3.A. 56B. 57C. 58D. 60中，删除某结点T 形成之后形成平衡二又树v T 树) T 插入，再将w 在任意一棵非空平衡二又树( AVL 4.221与T 的叙述中，正确的是T T 。

下列关于平衡二又树331I. 若v 是T 的叶结点，则T 与T 可能不相同311的叶结点，贝V T与T 一定不相同T不是H .若v 311T与T 一定相31的叶结点，则同T若v不是山.1D.仅I、口I、山A.仅IB.仅II C.仅网表示一项包含个活动的工程。

活动下图所示的AOE 8 d 5.的最早开始时间和最迟开始时间分别是A.3和7B.12和12C. 12和14D.15和15 用有向无环图描述表达式(x+y ) *(( x+y ) /x) ，需要的顶点个数6.至少是 A.5B.6C.8D.97.选择一个排序算法时，除算法的时空效率外，下列因素中，还需要考虑的是算法的稳定性山.数据的规模H .数据的存储方式I.数据的初始状态V. 、口、山、W IIV D.仅山仅I、□仅口、山、)，采用线性探查H( key) =key%7现有长度为11 8.且初始为空的散列表HT ,散列函数是线性探测再散列(查找失败的平均查找HT 98 , 20依次插入到HT后，87法解决冲突将关键字序列，40, 30 , 6, 11 , 22, 长度是6C. A. 4B. 5.256.29 D.算法进行模式匹配，到匹配成功时为止，，模”式串S=“ abaabc9. ”，采用KMP 设主串T= “ abaabaabcabaabc 在匹配过程中进行的单个字符间的比较次数是A. 9B. 10C. 12D. 1510. 排序过程中，对尚未确定最终位置的所有兀素进行一遍处理称为一不可能是快速排序”。