2018计算机考研：计算机数据结构测试题(四)

2018年全国硕士研究生入学统一考试计算机学科专业基础综合试卷一、单项选择题：140小题，每小题2分，共80分。

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

请在答题卡上将所选项的字母涂黑。

b5E2RGbCAP 1．已知程序如下：ints(int n>{ return (n<=0> ? 0 : s(n-1> +n。

}void main(>{ cout<< s(1>。

}程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息一次对应的是A．main(>->S(1>->S(0> B．S(0>->S(1>->main(>p1EanqFDPwC．main(>->S(0>->S(1> D．S(1>->S(0>->main(>DXDiTa9E3d【参考答案】 D【考查知识点】栈的基本概念和函数调用的原理。

2．先序序列为a,b,c,d的不同二叉树的个数是A．13B．14C．15D．16【参考答案】 C【考查知识点】二叉树的基本概念。

3．下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫曼树的是A．24，10，5和 24，10，7B．24，10，5和24，12，7C．24，10，10和 24，14，11 D．24，10，5和 24，14，6【参考答案】 C【考查知识点】哈夫曼树的原理。

4．现在有一颗无重复关键字的平衡二叉树<AVL树）,对其进行中序遍历可得到一个降序序列。

下列关于该平衡二叉树的叙述中，正确的是RTCrpUDGiTA．根节点的度一定为2B．树中最小元素一定是叶节点C．最后插入的元素一定是叶节点D．树中最大元素一定是无左子树【参考答案】 B【考查知识点】树的中序遍历和AVL树的基本概念。

5．设有向图G=(V,E>，顶点集V={V0,V1,V2,V3}，边集E={<v0,v1>,<v0,v2>,<v0,v3>，<v1,v3>},若从顶点V0 开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是5PCzVD7HxAA．2 B．3 C．4 D．5【参考答案】 D【考查知识点】图的深度优先遍历。

计算机考研数据结构试卷四（练习题含答案）（PS：其他正在整理，敬请期待）数据结构试卷4一、选择题1．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。

(A)O(n)(B)O(nlog2n)(C)O(1)(D)O(n2)2．设一棵二叉树的深度为k，则该二叉树中最多有（）个结点。

kk-1k(A)2k-1(B)2(C)2(D)2-13．设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（）。

(A)n(B)e(C)2n(D)2e4．在二叉排序树中插入一个结点的时间复杂度为（）。

2(A)O(1)(B)O(n)(C)O(log2n)(D)O(n)5．设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。

(A)n(B)n-1(C)m(D)m-16．设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（）趟的分配和回收才能使得初始关键字序列变成有序序列。

(A)3(B)4(C)5(D)87．设用链表作为栈的存储结构则退栈操作（）。

(A)必须判别栈是否为满(B)必须判别栈是否为空(C)判别栈元素的类型(D)对栈不作任何判别8．下列四种排序中（）的空间复杂度最大。

(A)快速排序(B)冒泡排序(C)希尔排序(D)堆9．设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（）。

(A)N0=N1+1(B)N0=Nl+N2(C)N0=N2+1(D)N0=2N1+l10.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素某的最多比较次数不超过（）。

(A)log2n+1(B)log2n-1(C)log2n(D)log2(n+1)二、填空题1．设有n个无序的记录关键字，则直接插入排序的时间复杂度为________，快速排序的平均时间复杂度为_________。

2．设指针变量p指向双向循环链表中的结点某，则删除结点某需要执行的语句序列为_________________________________________________________（设结点中的两个指针域分别为llink和rlink）。

一，简答题（60分6题）：
1：数据结构包含哪种逻辑结构？各自含义是？
2：给出入栈序列A，B，C，给出两个出栈序列。

3：请写出分块，顺序，折半查找对时间复杂度和空间复杂度的要求。

4：一个满K叉树，叶子结点n0.，其余节点按度分为n1,n2,n3….，结点数m 证明n0=1+n2+2n3+…+(m-1)Nm
还有2个题目，实在想不起来，反正没有难题，大家不用在意
二，综合题（6题60分）
1，堆排序大顶堆
2，有个程序填空题，和插入有关，很简单，不记得了，不写
3，写出下图中5种可能的拓扑排序序列。

4，最小生成树
其余的不记得了
三，编程题（2题30分）
1：十进制转换2进制
2：写一个代码求树的宽度
欢迎加入南昌大学计算机2020考研群：338295866
我们不割韭菜，我们就是想让大家免费拿到专业课资料。

考研计算机专业基础题库数据结构练习题一、选择题1. 以下哪种数据结构适合用于表示并操作大量具有层次关系的数据？A. 队列B. 栈C. 树D. 图正确答案：C解析：树结构适合表示并操作具有层次关系的数据，例如文件系统、组织结构等。

2. 在二叉树中，每个节点最多有几个子节点？A. 0B. 1C. 2D. 多于2正确答案：C解析：二叉树中每个节点最多有两个子节点。

3. 在链表中，节点之间的连接关系通过什么方式表示？A. 数组索引B. 指针C. 标签D. 无连接正确答案：B解析：链表中的节点通过指针实现之间的连接关系。

4. 哪种数据结构可以实现先进先出（FIFO）的操作方式？A. 队列B. 栈C. 树D. 图正确答案：A解析：队列是一种先进先出的数据结构。

5. 下列哪个算法用于对一组数据进行排序？A. 二分查找B. 广度优先搜索C. 深度优先搜索D. 快速排序正确答案：D解析：快速排序是一种用于对一组数据进行排序的算法。

二、填空题1. 在二叉搜索树中，左子树节点值均小于根节点值，右子树节点值均大于根节点值，这一特性被称为_二叉搜索树的性质_。

2. 通过什么方式可以遍历一个二叉树的所有节点？_前序遍历_、_中序遍历_、_后序遍历_3. 堆是一种完全二叉树，并且堆中的任意父节点的值都_大于等于_或_小于等于_其子节点的值。

4. 图中描述节点之间的连接关系的数据结构称为_邻接表_。

5. 广度优先搜索算法可以用于解决_最短路径问题_。

三、简答题1. 请简要介绍树的基本概念和常见应用。

树是一种非线性的数据结构，由节点和连接节点的边构成。

树中的节点分为根节点、叶节点和中间节点。

树的层次由根节点开始计算，根节点位于第0层，其子节点位于第1层，以此类推。

常见的树结构包括二叉树、二叉搜索树、AVL树和B树等。

树的应用非常广泛，例如文件系统的目录结构可以用树来表示，组织结构、家谱等层次关系也可以用树来描述。

此外，树还可以用于算法中，例如树的遍历和查找操作。

第四章串一、选择题1．下面关于串的的叙述中，哪一个是不正确的？（）【北方交通大学 2001 一、5（2分）】A．串是字符的有限序列 B．空串是由空格构成的串C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储2 若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘’,执行concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,i ndex(S2,‘8’),length(S2))) 其结果为（）【北方交通大学 1999 一、5 （25/7分）】A．ABC###G0123 B．ABCD###2345 C．ABC###G2345 D．ABC###2345E．ABC###G1234 F．ABCD###1234 G．ABC###012343．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A．求子串 B．联接 C．匹配 D．求串长【北京邮电大学 2000 二、4（20/8分）】【西安电子科技大学 1996 一、1 （2分）】4．已知串S=‘aaab’,其Next数组值为（）。

【西安电子科技大学 1996 一、7 （2分）】A．0123 B．1123 C．1231 D．12115．串‘ababaaababaa’的next数组为（）。

【中山大学 1999 一、7】A．9 B．2 C．6 D．456．字符串‘ababaabab’的nextval 为（）A．(0,1,0,1,04,1,0,1) B．(0,1,0,1,0,2,1,0,1)C．(0,1,0,1,0,0,0,1,1) D．(0,1,0,1,0,1,0,1,1 )【北京邮电大学 1999 一、1（2分）】7．模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（），nextval数组的值为（）。

2018年4月高等教育自学考试《数据结构》试题课程代码：02331一、单项选择题1．数据结构不包含的内容是A．数据的元素来源B．数据的逻辑结构C．数据的存储结构D．对数据施加的操作2．下列选项中，属于逻辑结构的是A．循环队列B．二叉树C．散列表D．邻接表3．下列选项中，属于顺序存储结构优点的是A．插入运算方便B．删除运算方便C．存储密度大D．方便存储各种逻辑结构4．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则下列存储结构中，最节省运算时间的是A．单链表B．仅有头指针的单循环链表C．双向链表D．仅有尾指针的单循环链表5．用不带头结点的单链表存储队列，在进行删除运算时A．仅修改头指针B．仅修改尾指针C．头、尾指针一定都要修改D．头、尾指针可能都要修改6．二维数组M，行下标取值范围为0—8，列下标取值范围为1～10，若按行优先存储时，元素M[8Ⅱ51的存储地址为ar，则按列优先存储时，地址ar存储的数组元素应是A．M[8][5] B．M[5][8] C．M[3][10] D．M[0][9]7．根据二叉树的定义，3个结点构成的二叉树的树型有A．2种B．3种C．4种D．5种8．一棵有序树可转换为一棵二叉树，树的后序遍历对应二叉树的A．前序遍历B．中序遍历C．后序遍历D．以上都不对9．若图G的邻接表中有奇数个表结点，则G是A．含奇数个顶点的图B．无向图C．含偶数个顶点的图D．有向图10．若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑排序序列的结论是A．存在，且唯一B．存在，且不唯一C．存在，可能不唯一D．无法确定是否存在11．如果无向图G的最小生成树T中含有边(a，b)和(a，c)，则下列选项中，一定不在T 中的边是A．(b，c) B．(b，d) C．(c，d) D．(c，e)12．下列排序算法中，在每一趟都能选出一个元素放到其最终位置上的是A．插入排序B．希尔排序C．归并排序D．堆排序13．若数据元素序列11，13，15，7，8，9，23，2，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法是A．冒泡排序B．插入排序C．选择排序D．归并排序14．线性表采用顺序存储或链式存储，对其进行查找的方法应是A．顺序查找B．二分查找C．散列查找D．索引查找15．设有序表为{1，3，9，12，32，41，45，62，75，77，82}，采用二分查找法查找关键字75，查找过程中关键字之间的比较次数是A．1 B．2 C．3 D．4二、填空题16．在数据结构中，从逻辑上可以把数据结构分为线性结构和。

2018年4月高等教育自学考试计算机系统结构真题(总分：100.00，做题时间：150分钟)一、单项选择题本大题共10小题，每小题1分，共10分，在每小题列出的备选项中只有一项是最符合题目要求的，请将其选出。

(总题数：10，分数：10.00)1.在计算机系统多级层次结构中,机器级从低级到高级，相对顺序正确的是（）。

（分数：1.00）A.汇编语言——操作系统——高级语言B.微程序一传统机器语言一汇编语言√C.传统机器语言——高级语言——汇编语言D.汇编语言——应用语言——高级语言解析：2.下列对系统程序员不透明的是（）。

（分数：1.00）A.Cache存储器B.数据通路宽度C.指令缓冲寄存器D.虚拟存储器√解析：3.下列予寻址方式的三种面向的是（）。

（分数：1.00）A.面向主存B.面向辅存√C.面向寄存器D.面向堆栈解析：4.浮点数尾数的基值rm=-8，尾数的计算机位数m=8位，可表示的尾数的个数为（）。

（分数：1.00）A.23×7B.24×7C.25×7√D.26×7解析：5.IBM370系统中，通道动作故障引起的中断属于（）。

（分数：1.00）A.机器校验中断√B.访管中断C.程序性中断D.I/O中断解析：6.程序员编写程序时使用的地址是（）。

（分数：1.00）A.主存地址B.逻辑地址√C.物理地址D.有效地址解析：7.对指令间“一次重叠”描述不正确的是（）。

（分数：1.00）A.仅“执行k”与“分析k+1”B.“分析k+1”完成后立即开始“执行k+1”√C.应尽量使“分析k+1”与“执行k”时间相等D.只需要一套指令分析部件和执行部件解析：8.有N个处理单元的集中式共享存储器的阵列处理机构形，为了对长度为N的向量中各元素能同时并行处理，存储器分体个数K与处理单元数N的关系是（）。

（分数：1.00）A.K与N无关B.K小于NC.K小于或等于ND.K等于或大于N √解析：9.能实现作业、任务级并行的异构型多处理机属于（）。

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

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

1．若栈S1中保存整数，栈S2中保存运算符，函数F()依次执行下述各步操作：（1）从S1中依次弹出两个操作数a和b；（2）从S2中弹出一个运算符op；（3）执行相应的运算b op a；（4）将运算结果压人S1中。

假定S1中的操作数依次是5, 8, 3, 2（2在栈顶），S2中的运算符依次是*, - , +（+在栈顶）。

调用3次F()后，S1栈顶保存的值是。

A. -15B. 15C. -20D. 202. 现有队列Q与栈S，初始时Q中的元素依次是1, 2, 3, 4, 5, 6（1在队头），S为空。

若仅允许下列3种操作：①出队并输出出队元素；②出队并将出队元素人栈；③出栈并输出出栈元素，则不能得到的输出序列是。

A. 1, 2, 5, 6, 4, 3B. 2, 3, 4, 5, 6, 1C. 3, 4, 5, 6, 1, 2D. 6, 5, 4, 3, 2, 13. 设有一个12×12的对称矩阵M，将其上三角部分的元素m i, j（1≤i≤j≤12）按行优先存人C 语言的一维数组N中，元素m6, 6在N中的下标是。

A. 50B. 51C. 55D. 664. 设一棵非空完全二叉树T的所有叶结点均位于同一层，且每个非叶结点都有2个子结点。

若T有k个叶结点，则T的结点总数是。

A. 2k-1B. 2kC. k2D. 2k-15. 已知字符集{a, b, c, d, e, f}，若各字符出现的次数分别为6, 3, 8, 2, 10, 4，则对应字符集中各字符的哈夫曼编码可能是。

A. 00, 1011, 01, 1010, 11, 100B. 00, 100, 110, 000, 0010, 01C. 10, 1011, 11, 0011, 00, 010D. 0011, 10, 11, 0010, 01, 0006. 已知二叉排序树如下图所示，元素之间应满足的大小关系是。

一、选择题1. B【解答】由n0=n2+1可得，n2=10,所以分支数为：2*10+1*2=222. D【解答】满二叉树的结点最多3. A【解答】可以直接画出二叉树如下所示，从而直接得到结果4. B【解答】看清楚题目所要求的，为逆邻接表，根据定义，所以为出度5. A6. B7. C8. B9. A【解答】根据数组给出的顺序，可以将之画成完全二叉树，看哪一个选项满足情况。

10. B【解答】在本题中，因为是对称矩阵，那么直接存储下三角元素即可。

存储方法为a11a12 a22a13 a23 a33a14 a24 a34 a44a15 a25 a35 a45 a55...a18 a28 a38 a48 a58一共1+2+3+4+5+6+7+5=3311. D【解答】可能该队列只存在一个节点12. C【解答】画出Huffman树的得，可以得到带权路径长度为：7*1+5*2+（2+4）*3=3513. C14. C15. D二、填空题1. 为了保证处理第一个节点和后面的节点的时候设计的算法相同，实现程序的高效性。

2. 队列3. 是有序的顺序表4. 遍历其右子树时第一个访问的结点，即右子树的最左下结点。

5. 最小近6. m-17. O(n)8. 题目说的不是很清楚，若是采用邻接矩阵存储，那么时间复杂度为O(n^2)，若是采用邻接表存储，那么时间复杂度为O(n+e)9. 距离源点路径长度小的三、判断题1. X2. X3. √4. X5. √6. √（最小生成树的形态可能不唯一）7. √8. √9. √10. √四、解答题1. 拓扑排序的序列可能为：a) 1、2,、3、4、5、6b) 1、2、4、3、5、6c) 2、1、3、4、5、6d) 2、1、4、3、5、6对于有向无环图，还可以采用深度优先遍历算法。

2. 该二叉树为：3. 第一趟：12 2 4 3 6 13 18 9 19 8第二趟：3 2 4 8 6 13 12 9 19 18第三趟：3 2 4 8 6 9 12 13 19 18第四趟：2 3 4 6 8 9 12 13 18 194. 构造的散列表如下：0 1 2 3 4 5 6 7 8 9 1033 41 30 1 20 24 13 67查找成功的平均查找长度为：（1+1+2+2+1+1+1+6）/8=15/85. 该问题的实质：单源最短路径，需要一个个的进行分析再得到结果a) 假设学校建在ab->a 的路径长度为6c ->a 的路径长度为2+1+6=9d->a 的路径长度为1+6=7e->a 的路径长度为5+1+6=12那么总共需要的距离之和为：6+9+7+12=34b) 假设学校建在ba->b 的路径长度为1c->b 的路径长度为2+1=3d ->b 的路径长度为1e ->b 的路径长度为5+1=6那么总共需要的距离之和为：1+3+1+6=11c) 假设建在ca->c 1+2=3;b->c 2;d->c 3 e->c 5+3=8那么总共需要的距离之和为:3+2+3+8=16d) 假设建在da->d 1+2+2=5; b->d 2+2=4; c->d 2; e->d 5那么总共需要的距离之和为:5+4+2+5=16e) 假设建在ea->e 1+2+4=7; b->e 2+4=6; c->e 4; d->e 3+4=7那么总共需要的距离之和为:7+6+4+7=24综上比较可知，建在b较好。

计算机四级数据库工程精选试题(4)2018年计算机四级数据库工程精选试题(4)1、数据模型中的__________是对数据系统的静态特征描述，包括数据结构和数据间联系的描述，__________是对数据库系统的动态特征描述，是一组定义在数据上的操作，包括操作的涵义、操作符、运算规则及其语言等。

(填空题)答案数据结构数据操作2、试述关系数据库的特点。

(问答题)答案关系数据模型具有下列优点：?关系模型与非关系模型不同，它是建立在严格的数学概念的基础上的。

?关系模型的概念单一。

无论实体还是实体之间的联系都用关系表示。

操作的对象和操作的结果都是关系。

所以其数据结构简单、清晰，用户易懂易用。

?关系模型的存取路径对用户透明，从而具有更高的数据独立性、更好的安全保密性，也简化了程序员的工作和数据库开发建立的工作。

当然，关系数据模型也有缺点，其中最主要的缺点是，由于存取路径对用户透明，查询效率往往不如非关系数据模型。

因此为了提高性能，必须对用户的查询请求进行优化，增加了开发数据库管理系统软件的难度。

3、用树型结构表示实体类型及实体间联系的数据模型称为__________模型，上一层的父结点和下一层的子结点之间的联系是的联系。

层次一对多4、试述数据库系统三级模式结构，这种结构的优点是什么?答案数据库系统的三级模式结构由外模式、模式和内模式组成。

(参见书上图1.29)外模式，亦称子模式或用户模式，是数据库用户(包括应用程序员和最终用户)能够看见和使用的局部数据的逻辑结构和特征的描述，是数据库用户的数据视图，是与某一应用有关的数据的逻辑表示。

模式，亦称逻辑模式，是数据库中全体数据的逻辑结构和特性的描述，是所有用户的公共数据视图。

模式描述的是数据的全局逻辑结构。

外模式涉及的是数据的局部的逻辑结构，通常是模式的子集。

内模式，亦称存储模式，是数据在数据库系统内部的表示，即对数据的物理结构和存储方式的描述。

数据库系统的三级模式是对数据的三个抽象级别，它把数据的具体组织留给DBMS管理，使用户能逻辑抽象地处理数据，而不必关心数据在计算机中的表示和存储。

《数据结构》第四章习题一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”）1、KMP算法的特点是在模式匹配时指示主串的指针不会变小。

( √)2、串是一种数据对象和操作都特殊的线性表。

( √)3、只包含空白字符的串称为空串（空白串）。

( ×)4、稀疏矩阵压缩存储后，必会（不会）失去随机存取功能。

( ×)5、使用三元组表示稀疏矩阵的非零元素能节省存储空间。

( √)6、插入与删除操作是数据结构中最基本的两种操作，因此这两种操作在数组中也经常使用。

（×）7、若采用三元组表存储稀疏矩阵，只要把每个元素的行下标和列下标互换（错的），就完成了对该矩阵的转置运算。

（×）二、单项选择题1．下面关于串的的叙述中，哪一个是不正确的？（ B ）A．串是字符的有限序列B．空串是由空格构成的串（空串是长度为零的串）C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储2．有串S1=’ABCDEFG’，S2 = ’PQRST’，假设函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回中s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是（ D ）。

A．BCDEF B．BCDEFG C．BCPQRST D．CDEFGFG3、串的长度是指（ B ）A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数三、填空题1、串是一种特殊的线性表，其特殊性表现在_数据元素为字符，操作集也不同__；串的两种最基本的存储方式是_顺序存储_、__ 链式存储_；两个串相等的充分必要条件是__两串的长度相等且两串中对应位置的字符也相等__。

2、设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为_O(m+n)__。

数据结构期末考试题库及答案2018目录第1章绪论 (1)第2章线性表 (4)第3章栈和队列 (8)第4章串、数组和广义表 (12)第5章树和二叉树 (16)第6章图 (20)第7章查找 (22)第8章排序 (28)第1章绪论1．选择题（1）数据结构是指（1. A ）。

A.数据元素的组织形式B.数据类型C.数据存储结构D.数据定义（2）计算机内部数据处理的基本单位是（10. B ）。

A.数据B.数据元素C.数据项D.数据库（3）数据结构中，与所使用的计算机无关的是数据的 C 结构.A) 存储 B) 物理 C) 逻辑 D) 物理和存储【解析】[解析] 数据结构概念一般包括数据的逻辑结构、存储结构及数据上的运算集合等。

数据的逻辑结构只抽象地反映数据元素之间的逻辑关系，而不管它在计算机中的存储形式。

（4）算法分析的目的是____C________A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性（5）计算机算法必须具备输入、输出和 B 等5个特性。

A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性（6）在数据结构中，从逻辑上可以把数据结构分成（）。

A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．内部结构和外部结构答案：C（7）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。

A．存储结构 B．存储实现C．逻辑结构 D．运算实现答案：C（8）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。

A．数据具有同一特点B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等答案：B（9）以下说法正确的是（）。

A．数据元素是数据的最小单位B．数据项是数据的基本单位C．数据结构是带有结构的各数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构答案：D解释：数据元素是数据的基本单位，数据项是数据的最小单位，数据结构是带有结构的各数据元素的集合。

第1章绪论一、选择题1. 算法的计算量的大小称为计算的（）;A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（）;A．问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是（），它必须具备（）这三个特性;(1)A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2)A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性4．一个算法应该是（）;A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C 5. 下面关于算法说法错误的是（）;A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（）;(1）算法原地工作的含义是指不需要任何额外的辅助空间;（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法;（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界;（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（）两大类;A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（）;A．循环队列 B. 链表 C. 哈希表 D. 栈9．以下数据结构中，哪一个是线性结构（）;A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储结构无关？（）;A．栈 B. 哈希表 C. 线索树 D. 双向链表11．在下面的程序段中，对x的赋值语句的频度为（）;FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A． O(2n) B．O(n) C．O(n2) D．O(log2n)12．程序段 FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换；其中 n为正整数，则最后一行的语句频度在最坏情况下是（）;A. O（n）B. O(nlogn)C. O(n3)D. O(n2)13．以下哪个数据结构不是多型数据类型（）;A．栈 B．广义表 C．有向图 D．字符串14．以下数据结构中，（）是非线性数据结构;A．树 B．字符串 C．队 D．栈15. 下列数据中，（）是非线性数据结构;A．栈 B. 队列 C. 完全二叉树 D. 堆16．连续存储设计时，存储单元的地址（）;A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续17．以下属于逻辑结构的是（）;A．顺序表 B. 哈希表 C.有序表 D. 单链表二、判断题1. 数据元素是数据的最小单位。

2018年全国硕士研究生统一入学考试自命题试题（A卷)*＊＊*＊*＊**＊＊＊*＊**＊＊＊＊＊＊＊***＊**********＊*＊＊＊＊＊**＊*****＊*＊**＊****＊＊＊***＊***＊***＊*＊＊＊＊***＊＊＊＊＊*＊学科、专业名称：计算机科学与技术、软件工程研究方向：计算机系统结构081201，计算机软件与理论081202，计算机应用技术081203，软件工程083500，计算机技术(专业学位) 085211考试科目名称及代码:数据结构830考生注意：所有答案必须写在答题纸（卷)上，写在本试题上一律不给分。

考试科目：数据结构共5页，第1 页考试科目：数据结构共5 页，第2 页图12。

一棵二叉树，若根结点的左右子树均有三个结点，其左子树的先序序列与中序序列相同,右子树的中序序列与后子序序列相同，试构造该二叉树。

(7分）3。

已知序列（12,18,4,3，6,13,2,9，19，8).请给出采用希尔排序对该序列作升序排序的每一趟结果（步长分别为5，3，2，1）.（8分）4. 设有一组关键字（33,41,20,24,30，13，01,67)，采用散列函数H（key)=(3＊key) 11，采用线性探测再散列解决冲突，H i=（H（key)+d i）%11,其中d i=1，2,…，10. 试在0～10散列地址空间中对该关键字序列（按从左到右的次序）构造散列表，并计算在查找概率相等的前提下查找成功时的平均查找长度。

（10分)5.已知图2所示的有向图。

设其顶点a，b，c,d,e表示一个乡的5个村庄，弧上的权值表示为两村之间的距离。

乡内要建立一所学校，问学校设在哪个村庄才能使从各村出发到学校的距离总和最小.（要求回答解决上述问题应采用什么算法，并写出应用该算法解答上述问题的每一步计算结果)。

（10分）图2考试科目: 数据结构共5 页，第3 页五、算法填空(共2小题，每空2分，共20分）1。

习题41. 填空题（1）一般来说，数组不执行（___________）和（___________）操作，所以通常采用（___________）方法来存储数组。

通常有两种存储方式：（___________）和（___________）。

答案：删除 插入 顺序存储 行优先存储 列优先存储（2）设8行8列的二维数组起始元素为A[0][0]，按行优先存储到起始元素下标为0的一维数组B 中，则元素B[23]在原二维数组中为（___________）。

若该二维数组为上三角矩阵，按行优先压缩存储上三角元素到起始元素下标为0的一维数组C 中，则元素C[23]即为原矩阵中的（___________）元素。

答案：A[2][7] A[3][5]（3）设二维数组A 为6行8列，按行优先存储，每个元素占6字节，存储器按字节编址。

已知A 的起始存储地址为1000H ，数组A 占用的存储空间大小为（___________）字节，数组A 的最后一个元素的下标为（___________），该元素的第一个字节地址为（___________）H ，元素A[1][4]的第一个字节的地址为（___________）H 。

（提示：下标从0开始计） 答案：288 A[5][7] 111AH 1048H（4）设C++中存储三维数组A mnp ，则第一个元素为a 000，若按行优先存储，则a ijk 前面共有（___________）个元素；若按列优先存储，则a ijk 前面共有（___________）个元素。

答案：inp+jp+k i+mj+mnk（5）常见的稀疏矩阵压缩方法有：（___________）和（___________）。

答案：三元组表 十字链表 （6）广义表（（a ），（（b ，c ），d ），（e ））的长度为（___________），表头为（___________），表尾为（___________）。

答案：3 （a ） （（（b ，c ），d ），（e ）） （7）设广义表LS ＝（（a ），（（b ，c ），d ），（e ）），若用取表头操作GetHead （）和取表尾操作GetTail （）进行组合操作，则取出元素b 的运算为（___________）。

2018年北京邮电大学数据结构考研题一、选择1、四个元素1、2、3、4依次进栈，出栈次序不可能出现_____情况A 1 2 3 4B 4 1 3 2C 1 4 3 2D 4 3 2 12、中缀表达式(A+B)*(C-D)/(E-F*G)的后缀表达式是_______A A+B*C-D/E-F*GB AB+CD-*EFG*-/C AB+C*D-E/F-G*D ABCDEFG+*-/-*3、4个圆盘的Hanoi塔，总的移动次数为________次A 7B 8C 15D 164、广义表(a, (b, (c, d, ( e, f ) ) ,g ) ) 的深度是_____A 3B 4C 5D 65、含有4个结点的二叉树有______种树型A 4B 5C 10D 146、一棵Huffman树共有215个结点，对其进行Huffman编码，功能得到______个不同的码字A 107B 108C 214D 2157、在一个无向图中，所有顶点的度数之和等于所有边数的______倍A 1/2B 1C 2D 48、对一个长度为50的有序表进行折半查找，最多比较_______次就能查找出结果A 6B 7C 8D 99、理论上，散列表的平均比较次数为______次A 1B 2C 4D n10、当待排序列基本有序时，下列排序方法中_______最好A 直接插入排序B 快速排序C 堆排序D 归并排序二、判断1、数据项是数据的最小单位；2、链表的每个结点都恰好有一个指针；3、同一组不重复输入序列执行不同的入栈出栈组合操作，所得结果也可能相同；4、改进的KMP算法中，字符串”abaaaba”的nextval数组值是0101110；5、用六叉链表表示30个结点的六叉树，则树中共有151个空指针；6、数组是一种线性结构，因此只能用来存储线性表；7、若有向图不存在回路，即使不用访问标志位同一结点也不会被访问两次；8、若装填因子a为1，则向散列表中散列元素时一定会产生冲突；9、若把堆看成是一个完全二叉树，则该树一定是一棵排序二叉树；10、外排中使用置换选择排序的目的，是为了增加初始归并段的长度；三、已知一棵二叉排序树的前序遍历为EBADCKGFHJI，画出该二叉树，并给出后序遍历的结果。

考研计算机数据结构测试题及答案四一、选择题(30分)1.设某无向图有n个顶点，则该无向图的邻接表中有( )个表头结点。

(A) 2n (B) n (C) n/2 (D) n(n-1)2.设无向图G中有n个顶点，则该无向图的最小生成树上有( )条边。

(A) n (B) n-1 (C) 2n (D) 2n-13.设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字45为基准而得到的一趟快速排序结果是( )。

(A) 40，42，60，55，80，85 (B) 42，45，55，60，85，80(C) 42，40，55，60，80，85 (D) 42，40，60，85，55，804.( )二叉排序树可以得到一个从小到大的有序序列。

(A) 先序遍历(B) 中序遍历(C) 后序遍历(D) 层次遍历5.设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为( )。

(A) 2i+1 (B) 2i (C) i/2 (D) 2i-16.程序段s=i=0;do {i=i+1; s=s+i;}while(i(A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(n3/2)7.设带有头结点的单向循环链表的头指针变量为head，则其判空条件是( )。

(A) head==0 (B) head->next==0(C) head->next==head (D) head!=08.设某棵二叉树的高度为10，则该二叉树上叶子结点最多有( )。

(A) 20 (B) 256 (C) 512 (D) 10249.设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为( )。

(A) 1 (B) 2 (C) 3 (D) 410.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为( )。