暨南大学计算机830数据结构2018年真题

数据结构暨南大学期末试卷试题一、判断题(共10分)1. 当静态链表采用数组实现时，插入与删除操作仍需移动元素。

2. 栈也是一种线性表，也同样有顺序存储结构和链式存储结构。

3. 二叉树的三种遍历算法区别仅在于对树根、左右子树访问先后顺序的不同。

4. 邻接表是图的一种顺序存储结构。

5. 二叉树就是度数为2的树。

6. 在哈希表中勿需比较就可找到记录在表中的位置。

7. 线性表的链式存储结构既方便其存取操作，也方便其插入与删除操作。

8. 顺序存储结构既适合于完全二叉树，也同样适合于一般的二叉树。

9.一个算法是正确的、高效率的，还不能说它就是一个“好”的算法。

10. 快速排序与堆排序的平均时间复杂度相同。

二、概念填空(共20分，每题2分)1.对顺序存储结构的线性表，设表长为La;在各元素插入为等概率条件下，插入一个数据元素需平均移动表中元素_______ 个;在最坏情况下需移动表中元素_______ 个。

2.从逻辑角度看，四种基本的数据结构可分为__________、___________、____________和____________;两种存储结构为_____________和_________________。

3.一个深度为,的满k(k>2)叉树，其第i层(若存在)有________个结点;编号为p(p>1)的结点其父结点(父结点为非根结点)编号是___________________。

4.具有n个结点的完全二叉树的深度为____________;编号为p(<n)的结点其右孩子(若存在)结点编号是___________。

5.堆栈被称为一个_____________的线性表;队列被称为一个_____________的线性表。

6.静态查找表的查找方法主要有:有序表查找及________________________;在n个记录中进行折半查找，当查找不成功时，与关键字比较次数最多为_____________________。

由此可知，左子树为o,右子树为1,故答案为A 。

6.解析：根据二叉排序树的特性：中序遍历(LNR)得到的是一个递增序列。

图中二叉排序树的中序遍历序列为Xi ,X3, X 5, X 4, X 2, 可知X3<�5<X407.解析：拓扑排序每次选取入度为0的结点输出，经观察不难发现拓扑序列前两位一定是1,5或5, 1 (因为只有1和5的入度均为o,且其他结点都不满足仅有1或仅有5作为前驱）。

因此D 显然错误。

8.解析：m阶B树的基本性质：根结点以外的非叶结点最少含有「m/21-1个关键字，代入m =3得到每个非叶结点中最少包含1个关键字，而根结点含有1个关键字，因此所有非叶结点都有两个孩子。

此时其树形与h =5的满二叉树相同，可求得关键字最少为31个。

9.解析：根据题意，得到的HT如下：二2 34 5 643 15ASL 成功(1 + 2 + 3)/3 = 2。

10.解析：初始序列：8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 6第一趟：1, 3, 7, 5, 2, 6, 4, 9, 11, 10, 8第二趟：I I I I I I I I I I I1, 2, 6, 4, 3, 7, 5, 8, 11, 10, 9 I I I I I I I I I I I第一趟分组：8, 1, 6; 3, 4; 9, 7; 11, 5; 2,.10; 间隔为5,排序后组内递增。

第二趟分组：1,5,4,10; 3,2,9,8; 7,6,11; 间隔为3,排序后组内递增。

故答案选D 。

11.解析：要熟练掌握建堆、堆的调整方法，从序列末尾开始向前遍历，变换过程如下图所示。

6)� 6')'/.)一5�气；。

＼三12. 解析：对于I,二进制由千只有0,1两种数值，运算规则较简单，都是通过A LU部件转换成加法运算。

对于II,二进制只需要高电平和低电平两个状态就可以表示，这样的物理器件很容易制造。

暨南大学2018年真题参考答案一、名词解释1.由于手术创伤的反应，术后病人的体温可略升高0.1~1℃，一般不超过38℃，称之为外科手术热或吸收热。

（外6 P.115）2.脑组织从高压区向低压区移位，导致脑组织、血管及脑神经等重要结构受压和移位，被挤入小脑幕裂孔、枕骨大孔、大脑镰下间隙等生理性或病理性间隙或孔道中，从而出现一系列严重的临床症状。

（外6 P.222）3.分级护理是指根据病人病情的轻重缓急以及自理能力的评估结果，给予病人不同级别的护理，通常分为四个护理级别，即特级护理、一级护理、二级护理及三级护理。

（基6 P.096）4.体温骤然上升至39℃以上，持续数小时或更长，然后下降至正常或正常以下，经过一个间歇，体温又升高，并反复发作，即高热期和无热期交替出现。

（基6 P.240）5.由于支气管-肺组织、胸廓或肺血管病变引起肺血管阻力增加，产生肺动脉高压，继而右心室结构和（或）功能改变的疾病。

（内6 P.083）6.是由于窦房结病变导致功能减退，从而产生多种心律失常的综合表现。

（内6 P.172）7.又称过期流产，是指胚胎或胎儿已死亡滞留在宫腔内尚未自然排出者。

（妇6 P.140）8.由各种肾脏疾病所致的，以大量蛋白尿（尿蛋白＞3.5g/d）、低蛋白血症（血清白蛋白＜30g/L）、水肿、高脂血症为临床表现的一组综合征。

（内6 P.396）二、单项选择题1. C解析：外6 P.473 注：“外6 P.473”表示“第六版外科护理学第473页”2.C解析：外6 P.0153.D解析：外6 P.5964.A解析：外6 P.4235.E解析：外6 P.4996.D解析：外6 P.5737.B解析：外6 P.0928.A解析：外6 P.0659.B解析：外6 P.70910.B解析：外6 P.50111.A解析：外6 P.23412.A解析：外6 P.424解析：基6 P.346 14.A解析：基6 P.359 15.B解析：基6 P.150 16.E解析：基6 P.280 17.C解析：基6 P.270 18.B解析：基6 P.036 19.A解析：内6 P.498 20.A解析：内6 P.049 21.B解析：内6 P.574 22.D解析：内6 P.845 23.A解析：内6 P.083 24.D解析：内6 P.618 25.C解析：内6 P.296 26.E解析：内6 P.585 27.C解析：内6 P.329 28.B解析：内6 P.455 29.A解析：内6 P.485 30.C解析：内6 P.472 31.E解析：妇6 P.025 32.B解析：妇6 P.143 33.B解析：妇6 P.299 34.E解析：妇6 P.141解析：儿6 P.21336.B解析：儿6 P.44037.E解析：儿6 P.17638.D解析：儿6 P.38039.B解析：儿6 P.20040.B解析：儿6 P.342三、简答题1.答:凡是需要营养支持但又不能或不宜接受肠内营养的病人，包括预计1周以上不能进食、或因胃肠道功能障碍、不能耐受肠内营养者，或通过肠内营养无法达到机体需要的目标量者，均是肠外营支持的适应症。

2023 年招收攻读硕士学位研究生入学考试试题A 卷******************************************************************************************** 招生专业与代码：网络空间安全考试科目名称及代码：数据结构 830考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。

一、单项选择题(每题 2 分，共 20 分)1.以下数据结构中, ( )是非线性数据结构A.字符串B．树C．队列D．栈2.请选择下面程序段的时间复杂度( )i = 1;while (i <= n)i = i * 3;A.O（n）B. O（log3 n）C. O（n2）D. O（i * n）3.顺序表中第一个元素的存储地址为120，每个元素的长度为5，则第4 个元素的地址为 ( )A. 135B. 140C. 130D. 1454.在单链表中，要将L所指节点插入到M所指节点之后，其语句应为( )A.L->next = M+1; M->next = L;B.(*M).next = L; (*L).next = (*M).next;C.L->next = M->next; M->next = L->next;D.L->next = M->next; M->next = L;5.若让元素1，2，3，4，7 依次进栈，则出栈顺序不可能为( )A. 7, 4, 3, 2, 1B. 4, 3, 1, 2, 7C. 2, 1, 7, 4, 3D. 2, 3, 7, 4, 16.假设栈 S 与队列 Q 的初始状态为空，元素 e1、e2、e3、e4、e5 和 e6 依次进入栈 S，一个元素出栈后即进入 Q，若 6 个元素出队的序列是 e2、e4、e3、e6、e5 和e1，则栈S 的容量至少为( )A．2 B. 4 C. 3. D.67.假设以行序列为主序存储二维数组 A = array[1..100,1..100]，设每个数据元素占 2 个存储单元，基地址为 10，则 LOC[5, 5] = ( )A．808 B．1010 C．818 D．10208.由3个不同结点可计算出多少种不同的二叉树？( )A. 3B. 4C. 5D. 69.广度优先遍历类似于二叉树的( )A.先序遍历B. 中序遍历C. 层次遍历D.后序遍历10.设哈希表长为14，哈希函数是H(key)=key%11，表中已有数据的关键字为15，38，61，84 共四个，现要将关键字为49 的元素加到表中，用二次探测法解决冲突，则放入的位置是( )A．8 B．3 C．5 D．9考试科目：数据结构共 3 页，第 1 页。

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

暨南大学硕士研究生入学考试自命题科目830《数据结构》考试大纲Ⅰ考试形式一、试卷满分及考试时间本试卷满分为150分，考试时间为180分钟二、答题方式答题方式为闭卷、笔试Ⅱ考查目标1.理解数据结构的基本概念；掌握数据结构的逻辑结构、存储结构及其差异，以及各种基本操作的实现。

2.掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。

3.能够选择合适的数据结构和方法进行问题求解。

一、基本概念和术语（一）数据元素、数据结构、抽象数据类型等概念（二）算法设计的基本要求（三）语句的频度和估算时间复杂度二、线性表（一）线性表的定义和基本操作（二）线性表的实现1．顺序存储结构2．链式存储结构3．线性表的应用三、栈、队列和数组（一）栈和队列的基本概念（二）栈和队列的顺序存储结构（三）栈和队列的链式存储结构（四）栈和队列的应用（五）特殊矩阵的压缩存储四、树与二叉树栈（一）树的概念（二）二叉树1．二叉树的定义及其主要特征2．二叉树的顺序存储结构和链式存储结构3．二叉树的遍历4．线索二叉树的基本概念和构造5．二叉排序树6．平衡二叉树（三）树、森林1．树的存储结构2．森林与二叉树的转换3．树和森林的遍历（四）树的应用1．特价类问题2．哈夫曼(Huffman)树和哈夫曼编码五、图（一）图的概念（二）图的存储结构及基本操作1. 邻接矩阵2.邻接表（三）图的遍历1．深度优先搜索2．广度优先搜索（四）图的基本应用1．最小（代价）生成树2．拓扑排序3．关键路径4．最短路径六、查找（一）查找的基本概念（二）顺序查找法（三）折半查找法（四）B-树（五）散列(Hash)表及其查找（六）查找算法的分析及应用七、内部排序（一）排序的基本概念（二）插入排序1．直接插入排序2．折半插入排序（三）气泡排序（bubble sort）（四）简单选择排序（五）希尔排序（shell sort）（六）快速排序（七）堆排序（八）二路归并排序(merge sort)（九）基数排序（十）各种内部排序算法的比较（十一）内部排序算法的应用Ⅲ特别推荐1．严蔚敏、吴伟民, 数据结构（C语言版）,清华大学出版社出版2．严蔚敏, 吴伟民,《数据结构习题解析》,清华大学出版社出版。

2018年计算机学科专业基础综合试题参考答案一、单项选择题1．B2．C3．A4．A5．A6．C7．D8．B9．C10．D11．A12．D13．C14．A15．A16．B17．C18．B19．A20．D21．B22．C23．C24．D25．B26．A27．C28．D29．D30．A31．D32．C33．B 34．C 35．D 36．D 37．D 38．C 39．B 40．D二、综合应用题41．解析：1）题目要求算法时间上尽可能高效，因此采用空间换时间的办法。

分配一个用于标记的数组B[n]，用来记录A中是否出现了1~n中的正整数，B[0]对应正整数1，B[n-1]对应正整数n，初始化B中全部为0。

由于A中含有n个整数，因此可能返回的值是1~n+1，当A中n个数恰好为1~n时返回n+1。

当数组A中出现了小于等于0或者大于n的值时，会导致1~n中出现空余位置，返回结果必然在1~n中，因此对于A中出现了小于等于0或者大于n的值可以不采取任何操作。

经过以上分析可以得出算法流程：从A[0]开始遍历A，若0<A[i]<=n，则令B[A[i]-1]=1；否则不做操作。

对A遍历结束后，开始遍历数组B，若能查找到第一个满足B[i]==0的下标i，返回i+1即为结果，此时说明A中未出现的最小正整数在1~n之间。

若B[i]全部不为0，返回i+1（跳出循环时i=n，i+1等于n+1），此时说明A中未出现的最小正整数是n+1。

int findMissMin(int A[],int n){int i,*B; //标记数组B=(int *)malloc(sizeof(int)*n); //分配空间memset(B,0,sizeof(int)*n); //赋初值为0for(i=0;i<n;i++)if(A[i]>0&&A[i]<=n) //若A[i]的值介于1~n，则标记数组BB[A[i]-1]=1;for(i=0;i<n;i++) //扫描数组B，找到目标值if (B[i]==0) break;return i+1; //返回结果}3）时间复杂度：遍历A一次，遍历B一次，两次循环内操作步骤为O(1)量级，因此时间复杂度为O(n)。

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的四个叶子结点构造一个哈夫曼树，该树的带权路径长度为（）。

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。