下载文档原格式
数据结构试卷（一）一、单选题（每题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）C. O（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个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
A.5B.6C.7D.8二、填空题（每空1分，共26分）1. 通常从四个方面评价算法的质量：_________、_________、_________和_________。
湖北省考研计算机复习资料数据结构常见题型分析数据结构是计算机科学与技术专业中的一门重要课程，也是湖北省考研计算机专业的一项重要内容。
在备考过程中，了解和掌握常见的数据结构题型及其解题思路，对于考生来说是相当关键的。
本文将对湖北省考研计算机复习资料中常见的数据结构题型进行分析，并给出解题思路和注意事项。
一、线性表题型分析线性表是计算机中最基本的数据结构之一，题型通常包括链表、顺序表、循环链表等。
其中常见的题型有以下几种：1. 单链表的建立和逆置要求实现一个单链表的建立和逆置功能。
解题思路是通过遍历原链表，将每个节点的指针指向前一个节点，实现链表的逆置。
需要注意处理链表为空的情况。
2. 删除链表中指定元素要求实现删除链表中指定元素的功能。
解题思路是通过遍历链表，找到目标元素的前一个节点，将其指针指向下一个节点，完成删除操作。
需要注意处理目标元素不存在的情况。
3. 判断链表是否有环要求判断一个链表是否存在环。
解题思路是使用快慢指针法，通过设置两个指针，一个每次走一步，一个每次走两步，判断它们是否会相遇。
如果相遇，则链表存在环；如果其中一个指针为空，则链表不存在环。
二、栈和队列题型分析栈和队列是常见的数据结构，在湖北省考研计算机复习资料中也有相应的题型。
1. 使用栈实现表达式求值要求使用栈的数据结构实现对表达式的求值。
解题思路是通过遍历表达式，将操作数入栈，遇到操作符时，将栈顶的两个操作数弹出进行计算，并将结果入栈，最终得到表达式的值。
2. 使用队列实现栈要求使用队列的数据结构实现栈。
解题思路是使用两个队列，一个用于入栈操作，一个用于出栈操作。
入栈时将元素入队，出栈时将元素出队，直到只剩一个元素时，即为栈的顶部元素。
三、树和图题型分析树和图是数据结构中比较复杂的部分，相关题型的出现频率也较高。
1. 二叉树的遍历要求实现二叉树的前序、中序和后序遍历。
解题思路是使用递归或迭代的方式遍历树的各个节点，并按照前序、中序和后序的顺序输出节点的值。
2017年全国硕士研究生入学统一考试计算机学科专业基础综合真题(总分150,考试时间180分钟)单项选择题1～40小题，每小题2分，共80分。
下列每题给出的四个选项中，只有一个选项符合题目要求。
1. 下列函数的时间复杂度是A. O(log n)B. O(n1/2)C. O(n)D. O(nlog n)2. 下列关于栈的叙述中，错误的是Ⅰ．采用非递归方式重写递归程序时必须使用栈Ⅱ．函数调用时，系统要用栈保存必要的信息Ⅲ．只要确定了入栈次序，即可确定出栈次序Ⅳ．栈是一种受限的线性表，允许在其两端进行操作A. 仅ⅠB. 仅Ⅰ、Ⅱ、ⅢC. 仅Ⅰ、Ⅲ、ⅣD. 仅Ⅱ、Ⅲ、Ⅳ3. 适用于压缩存储稀疏矩阵的两种存储结构是A. 三元组表和十字链表B. 三元组表和邻接矩阵C. 十字链表和二叉链表D. 邻接矩阵和十字链表4. 要使一棵非空二叉树的先序序列与中序序列相同，其所有非叶结点须满足的条件是A. 只有左子树B. 只有右子树C. 结点的度均为1D. 结点的度均为25. 已知一棵二叉树的树形如下图所示，其后序序列为e，a，c，b，d，g，f，树中与结点a 同层的结点是A. cB. dC. fD. g6. 已知字符集{a，b，c，d，e，f，g，h}，若各字符的哈夫曼编码依次是0100，10，0000，0101，001，011，11，0001，则编码序列XXXX的译码结果是A. a c g a b f hB. a d b a g b bC. a f b e a g dD. a f e e f g d7. 已知无向图G含有16条边，其中度为4的顶点个数为3，度为3的顶点个数为4，其他顶点的度均小于3。
图G所含的顶点个数至少是A. 10B. 11C. 13D. 158. 下列二叉树中，可能成为折半查找判定树(不含外部结点)的是A. AB. BC. CD. D9. 下列应用中，适合使用B+树的是A. 编译器中的词法分析B. 关系数据库系统中的索引C. 网络中的路由表快速查找D. 操作系统的磁盘空闲块管理10. 在内部排序时，若选择了归并排序而没有选择插入排序，则可能的理由是Ⅰ．归并排序的程序代码更短Ⅱ．归并排序的占用空间更少Ⅲ．归并排序的运行效率更高A. 仅ⅡB. 仅ⅢC. 仅Ⅰ、ⅡD. 仅Ⅰ、Ⅲ11. 下列排序方法中，若将顺序存储更换为链式存储，则算法的时间效率会降低的是Ⅰ. 插入排序Ⅱ．选择排序Ⅲ．起泡排序Ⅳ．希尔排序Ⅴ．堆排序A. 仅Ⅰ、ⅡB. 仅Ⅱ、ⅢC. 仅Ⅲ、ⅣD. 仅Ⅳ、Ⅴ12. 假定计算机M1和M2具有相同的指令集体系结构(ⅠSA)，主频分别为1.5 GHz和1.2 GHz。
数据结构试题库及答案第一章概论一、选择题1、研究数据结构就是研究（ D ）。
A. 数据的逻辑结构B. 数据的存储结构C. 数据的逻辑结构和存储结构D. 数据的逻辑结构、存储结构及其基本操作2、算法分析的两个主要方面是（ A ）。
A. 空间复杂度和时间复杂度B. 正确性和简单性C. 可读性和文档性D. 数据复杂性和程序复杂性3、具有线性结构的数据结构是（ D ）。
A. 图B. 树C. 广义表D. 栈4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（ B ）等5个特性。
A. 可执行性、可移植性和可扩充性B. 可执行性、有穷性和确定性C. 确定性、有穷性和稳定性D. 易读性、稳定性和确定性5、下面程序段的时间复杂度是（ C ）。
for(i=0;i<m;i++)for(j=0;j<n;j++)a[i][j]=i*j;A. O(m2)B. O(n2)C. O(m*n)D. O(m+n)6、算法是（ D ）。
A. 计算机程序B. 解决问题的计算方法C. 排序算法D. 解决问题的有限运算序列7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（ C ）。
A. O(n)B. O(nlog2n)C. O(n2)D. O(log2n)8、下面程序段的时间复杂度为（ C ）。
i=1;while(i<=n)i=i*3;A. O(n)B. O(3n)C. O(log3n)D. O(n3)9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（）和运算等的学科。
A. 结构B. 关系C. 运算D. 算法10、下面程序段的时间复杂度是（）。
i=s=0;while(s<n){i++;s+=i;}A. O(n)B. O(n2)C. O(log2n)D. O(n3)11、抽象数据类型的三个组成部分分别为（）。
A. 数据对象、数据关系和基本操作B. 数据元素、逻辑结构和存储结构C. 数据项、数据元素和数据类型D.数据元素、数据结构和数据类型12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量，以下解释错误的是（）。
武汉纺织大学2017年招收硕士学位研究生试卷科目代码848 科目名称数据结构考试时间2016 年12 月25 日下午报考专业1、试题内容不得超过画线范围，试题必须打印，图表清晰，标注准确。
2、试题之间不留空格。
3、答案请写在答题纸上，在此试卷上答题无效。
本试卷总分150分，考试时间3小时。
共 4 页；第 2 页共 4 页；第 3 页共 4 页；第 4 页武汉纺织大学2016年招收硕士学位研究生试卷科目代码848 科目名称数据结构考试时间2015年12月27日下午报考专业1、试题内容不得超过画线范围，试题必须打印，图表清晰，标注准确。
2、试题之间不留空格。
3、答案请写在答题纸上，在此试卷上答题无效。
本试卷总分150分，考试时间3小时。
共 3 页；第 2 页共 3 页；第 3 页武汉纺织大学2015年招收硕士学位研究生试卷科目代码848科目名称数据结构考试时间2014年12月28日下午报考专业1、试题内容不得超过画线范围，试题必须打印，图表清晰，标注准确。
2、试题之间不留空格。
3、答案请写在答题纸上，在此试卷上答题无效。
题号一二三四五六七八九十十一得分得分本试卷总分150分，考试时间3小时。
共4页；第2页共4页；第3页，14，，6884，MOD13，采用开放定址法处理冲突，增量序列选用线性探测再散列。
要求：10②假设每个记录的查找概率相等，求查找成功时的平均查找长度（、已知待排序的关键字序列为排序”方法，给出按从小到大的顺序排序的过程（已知静态查找表的顺序存储结构如下：关键字域其他域数据元素存储空间基址，按实际长度分配，表长度中折半查找关键字等于的数据元素的算法，函数头如下：Search_Bin(SSTable，KeyType共4页；第4页。
（完整版）2017年考研计算机统考408真题2017 年考研计算机统考408 真题⼀、单项选择题1.下列函数的时间复杂度是 1 。
int func(int n){ int i = 0; sum = 0;while( sum < n) sum += ++i;return i;}A. O(logn)B. O(n1/2)C. O(n)D. O(nlogn)2.下列关于栈的叙述中，错误的是 2 。
I.采⽤⾮递归⽅式重写递归程序时必须使⽤栈II.函数调⽤时，系统要⽤栈保存必要的信息III.只要确定了⼊栈的次序，即可确定出栈次序IV.栈是⼀种受限的线性表，允许在其两端进⾏操作A. 仅 IB. 仅 I、II、IIIC. 仅 I、III、IVD. 仅 II、III、IV3.适⽤于压缩存储稀疏矩阵的两种存储结构是 3 。
A. 三元组表和⼗字链表B. 三元组表和邻接矩阵C. ⼗字链表和⼆叉链表D. 邻接矩阵和⼗字链表4.要使⼀棵⾮空⼆叉树的先序序列与中序序列相同，其所有⾮叶结点须满⾜的条件是4 。
A. 只有左⼦树B. 只有右⼦树C. 结点的度均为 1D. 结点的度均为 25.已知⼀棵⼆叉树的树形如下图所⽰，其后序序列为e,a,c,b,d,g,f，树中与结点 a 同层的结点是 5 。
A. cB. dC. fD. g6.已知字符集{a,b,c,d,e,f,g,h} ，若各字符的哈夫曼编码依次是0100,10,0000,0101,001,011,11,0001 ，则编码序列0100011001001011110101 的译码结果是 6 。
A. a c g a b f hB. a d b a g b bC. a f b e a g dD. a f e e f g d7.已知⽆向图G 含有 16 条边，其中度为 4 的顶点个数为3，度为3 的顶点个数为4，其他顶点的度均⼩于3。
图 G 所含的顶点个数⾄少是7 。
A. 10B. 11C. 13D. 158.下列⼆叉树中，可能成为折半查找判定树（不含外部结点）的是8 。
