暨南大学830数据结构2010,2012--2018年考研初试专业课真题试卷

目录Ⅰ历年真题试卷 (2)暨南大学2010年招收攻读硕士学位研究生入学考试试题 (2)暨南大学2011年招收攻读硕士学位研究生入学考试试题 (8)暨南大学2012年招收攻读硕士学位研究生入学考试试题 (12)暨南大学2013年招收攻读硕士学位研究生入学考试试题 (17)暨南大学2014年招收攻读硕士学位研究生入学考试试题 (22)暨南大学2015年招收攻读硕士学位研究生入学考试试题 (26)暨南大学2016年招收攻读硕士学位研究生入学考试试题 (31)暨南大学2017年招收攻读硕士学位研究生入学考试试题 (35)暨南大学2018年招收攻读硕士学位研究生入学考试试题 (40)Ⅱ历年真题试卷答案解析 (45)暨南大学2010年招收攻读硕士学位研究生入学考试试题答案解析 (45)暨南大学2011年招收攻读硕士学位研究生入学考试试题答案解析 (57)暨南大学2012年招收攻读硕士学位研究生入学考试试题答案解析 (66)暨南大学2013年招收攻读硕士学位研究生入学考试试题答案解析 (79)暨南大学2014年招收攻读硕士学位研究生入学考试试题答案解析 (93)暨南大学2015年招收攻读硕士学位研究生入学考试试题答案解析 (104)Ⅰ历年真题试卷暨南大学2010年招收攻读硕士学位研究生入学考试试题学科、专业名称：信息科学技术学院电路与系统、微电子学与固体电子学、电磁场与微波技术、通信与信息系统、信号与信息处理、电子与通信工程（专业学位）专业；理工学院物理电子学考试科目名称：823电子技术基础考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。

一、判断下列说法是否正确，凡对者打“√”，错者打“×”，（答案必须写在答题纸上）。

（共10小题，每小题2分，共20分）1、一个理想对称的差分放大电路，既能放大差模输入信号，也有可能放大共模输入信号。

2、场效应管依靠电场控制漏极电流，故不能称为电压控制器件。

暨南大学硕士研究生统一入学考试自命题试题（网络空间安全）******************************************************************************************** 学科、专业名称：网络空间安全研究方向：网络空间安全083900四、简答题（40分）1. 简述逻辑结构的四种基本关系并画出它们的关系图。

（10分）2. 设待排序的关键字序列为{12，2，16，30，28，10，16*，20，6，18} ，请写出二路归并排序的方法下，每趟排序结束后关键字序列的状态。

（6分）3. 设二维数组num[1….m, 1…n]含有m*n个整数，请分析判断数组中元素是否互不相同的算法的时间复杂度。

（8分）4. 已知图1所示的有向图，请给出（1）每个顶点的入度与出度；（2）邻接矩阵。

（10分）图1. 有向图5. 在一棵空的二叉排列树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉排列树。

（6分）五、算法填空（共2小题，每空2分，共20分）1. 在汉诺塔(hanoi tower)游戏中，总共有3根柱子和n个大小不一样的盘子。

初始状态时n 个盘子从小到大堆叠在1号柱子，下面的递归算法伪代码能够将这n个盘子从1号柱子移动到3号柱子。

其中，该递归算法满足以下条件：(1)每次只移动1个盘子，(2)任何一个盘子只有当它上面没有堆放盘子时才能移动，(3)任何时刻在任何一个柱子上永远不能出现大盘子堆在小盘子之上的情况。

请在_________处填上适当内容，使其成为一个完整的算法。

hanoi(from, tmp, to, n){ if(n==1){move( (1) , (2) );return;}hanoi( (3) );printf ( "(%d,%d)", from, to );hanoi( (4) );return;}。

一、选择题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较好。

2012年全国硕士研究生统一入学考试自命题试题******************************************************************************************** 学科与专业名称：计算机技术，软件工程考试科目代码与名称：830 数据结构考试科目：数据结构共5页，第1 页考试科目：数据结构共5 页，第2 页图1考试科目：数据结构共5 页，第3页图2所示带权有向图及其邻接矩阵，利用Floyd径及其路径长度（要求写出求解过程）。

（12分）图3．给出一组关键字的序列为{ 12，15，34，37，39，22，38，66，74，80Hash(key)=key mod 11，画出按照链地址法处理冲突构造所得的哈希表，并在记录考试科目：数据结构共5 页，第4页考试科目：数据结构共5页，第5页赠送以下资料考研英语作文模板（英语一）大作文考研英语大作文一般是看图写作，从一幅图分析含义及意义，所以只需要几个好的模板，根据题目套上去就行了。

题目反映的意义无非三种：积极，消极和中性。

所以我准备了三个不同类型的模板，到时候大家根据题目自己分析一个写作方向，再结合模板，把内容填进模板就好了。

模板只是保证文章结构不过于混乱，具体的写作还希望大家多背历年写作真题和资料书上的作文，总结出自己喜欢的句子背下来，背熟之后根据原文的中文意义用自己的语言再把文章写出来，这样才能得到更好的效果。

切记：模板只能起到应急和保证结构的作用，真正写好作文拿高分还需要自己不断地背诵和练习，祝大家考试顺利！模板一：积极（图画反映了什么积极现象，我们应提倡…）………（开头：为了避免跟大部分模板有重复之嫌，我们可以在第一句写一句跟作文话题有关的句子，俗语和谚语皆可，也可以是一句关于话题的感悟。

如果实在写不出可以不写）……….，The picture above symbolically/subtly illustrate/demonstrate that ……(描述图画)……。

2020年全国硕士研究生统一入学考试自命题试题B卷********************************************************************************************学科、专业名称：网络空间安全研究方向：网络空间安全083900考试科目名称及代码：数据结构830考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。

一、单项选择题(每题2分，共30分)1. 下述关于顺序存储结构优点的说法，哪个是正确的（）A. 插入运算方便B. 可方便地用于各种逻辑结构的存储表示C. 存储密度大D. 删除运算方便2. 假设根结点为第1层，深度为h层的二叉树至少有( ) 个结点(h>1)；A. 2hB. 2h-1C. 2h+1D. 2h-13. 用单向链表来实现容量为n的堆栈时，链表头指针指向堆栈顶部元素，链表尾指针指向堆栈底部元素，则以下说法错误的是( )A. 入栈操作的复杂度为O(1)B. 出栈操作的复杂度为O(1)C. 删除底部元素的复杂度为O(1)D. 插入一个新的堆栈底部元素复杂度为O(1)4. 以下关于递归算法的论述，不正确的是( )A. 递归算法的代码可读性好B. 递归算法可以提高程序运行效率C. 递归调用层次太深有可能造成堆栈溢出D. 递归调用层次太深会占用大量内存5. 设有字符集合{4,6,3,W,S}，将字符序列6W43S中的字符按顺序进入堆栈，出栈可发生在任何时刻。

则以下的出栈序列错误的是（）。

A. 64WS3B. 4W36SC. 6W34SD. WS4366. 在管理城市道路交通网络据时，最适合采用（）数据结构来对其进行存储。

A．有向图B．无向图C．树D．矩阵7. 具有k个顶点的完全有向图的边数为( )。

A. k(k-1)B. k(k-1)/2C. k2-1D. k2+18. 若线性表最常用的操作是增加或者删除某个元素, 则采用( )存储方式节省时间.A. 单链表B. 双链表C. 单循环链表D. 顺序表9. 由权为6,3,2,8的四个叶子结点构造一个哈夫曼树，该树的带权路径长度为（）。

《数据结构》考研真题及解答目录2009 年试题 (1)填空题 (1)解答题 (2)2010 年试题 (2)填空题 (2)解答题 (4)2011 年试题 (4)填空题 (4)解答题 (5)2012 年试题 (6)填空题 (6)解答题 (7)2013 年试题 (8)填空题 (8)解答题 (9)2014 年试题 (10)填空题 (10)解答题 (11)2015 年试题 (12)填空题 (12)解答题 (14)2009 年试题填空题1.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。

该缓冲区的逻辑结构应该是A.栈B.队列C.树D.图2.设栈 S 和队列 Q 的初始状态均为空，元素 abcdefg 依次进入栈 S。

若每个元素出栈后立即进入队列 Q，且7 个元素出队的顺序是 bdcfeag，则栈 S 的容量至少是A．1 B.2 C.3 D.43.给定二叉树图所示。

设 N 代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。

若遍历后的结点序列为 3，1，7，5，6，2，4，则其遍历方式是A．LRN B.NRL C.RLN D.RNL4.下列二叉排序树中，满足平衡二叉树定义的是5.已知一棵完全二叉树的第 6 层（设根为第 1 层）有8 个叶结点，则完全二叉树的结点个数最多是A．39 B.52 C.111 D.1196.将森林转换为对应的二叉树，若在二叉树中，结点u 是结点v 的父结点的父结点，则在原来的森林中，u 和v 可能具有的关系是I．父子关系II.兄弟关系III.u 的父结点与v 的父结点是兄弟关系A.只有IIB.I 和IIC.I 和IIID.I、II 和III7.下列关于无向连通图特性的叙述中，正确的是I．所有顶点的度之和为偶数II.边数大于顶点个数减1 III.至少有一个顶点的度为1A.只有IB.只有IIC.I 和IID.I 和III8.下列叙述中，不符合 m 阶B 树定义要求的是A．根节点最多有m 棵子树 B.所有叶结点都在同一层上C．各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接9.已知关键序列 5，8，12，19，28，20，15，22 是小根堆（最小堆），插入关键字 3，调整后得到的小根堆是A．3，5，12，8，28，20，15，22，19B.3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D.3，12，5，8，28，20，15，22，1910.若数据元素序列 11，12，13，7，8，9，23，4，5 是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是A．起泡排序 B.插入排序 C.选择排序 D.二路归并排序解答题41.（10 分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。

2 010参考答案一、 选择题1 1 1 .B 2.A 3.C 4.A 5.D 6.A 7.B 8.A 9.C 10.C1.B 12.C 13.A 14.C 15.B 16.D 17.D 18.D 19.A 20.A5 解释：线索二叉树中某结点是否有左孩子，不能通过左指针域是否为空来判 断，而要判断左标志是否为 1。

二、 填空题1 2 3 .归并排序。

. 能否将关键字均匀影射到哈希空间上.一端 先进后出有无好的解决冲突的方法4 5 6 7 8 9 . 顺序存储或链式存储 （1+n ）/2.从任意节点出发都能访问到整个链表.时间 空间.n-1 n(n-1)/2.2n-1.n n三、 判断题 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 .F.F 非空才成立.F 有向的非强连通图，不成立.T.F 表头没有前驱，表尾没有后序.T.F 先序跟后序不行，中序才行.T.F 不可能0.T1.F2.T3.F4.F5.F四、 应用题1 ．逻辑结构是从操作对象抽象出来的数学模型，结构定义中的“关系”描述的 是数据元素之间的逻辑关系；物理结构是数据结构在计算机中的表示（又称 映像），又称存储结构。

物理结构是指数据具体存放在哪个位置,逻辑结构是 指数据跟数据间是怎样联系的2 3．由 AOV 网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存 在入度为 0的顶点为止。

(1) 选择一个入度为 0的顶点并输出之；(2) 从网 中删除此顶点及所有出边。

拓扑序列 1：abcdef 拓扑序列 2：adbcef.二叉树图如下：4 5 .略。

已经不纳入考纲.哈夫曼编码问题编码： 3: 000020: 10 10: 0001 22: 11 18: 001 37: 016.二叉排序树问题比根节点小的往左子树插，大的往右子树插。

图如下：删除50有两种做法：《数据结构》中的解析这里我用第二种做法:五.算法设计题1 & .算法填空（L.elem[i-1]） L.length-1 ++p *p L.length-1;2. 设计算法: 输入 n 个元素的值 创建带头结点的单链线性表 L 。