2017年暨南大学考研真题830数据结构

2017年全国硕士研究生统一入学考试自命题试题（B卷）

******************************************************************************************** 学科、专业名称：计算机科学与技术、软件工程

研究方向：计算机系统结构081201，计算机软件与理论081202，计算机应用技术081203，软件工程083500，计算机技术(专业学位) 085211，软件工程(专业学位) 085212

考试科目：数据结构共5页，第1 页

考试科目：数据结构共5 页，第2 页

图1

一个带权无向图的最小生成树是否一定唯一？在什么情况下构造出的最小生成树可能不考试科目：数据结构共5页，第3 页

考试科目：数据结构共5 页，第4 页

考试科目：数据结构共5 页，第5 页

暨南大学2018考研真题之830数据结构

暨南大学2018考研真题之830数据结构考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。 一、单项选择题(每题2分，共30分) 1. 任何一棵二叉树T, 如果度为1的结点数为2，度为0结点数为11，其分支数为( ) 。 A. 23 B. 22 C. 24 D. 21 2. 深度为k的二叉树至多有( ) 个结点(k>=1)； A. 2k B. 2k-1 C. 2k+1 D.2k-1 3. 已知一棵二叉树结点的中序序列为BDCEAFHG, 后序序列为DECBHGFA, 则结点的先序序列为( ) 。 A. ABCDEFGH B. DGBFHCA C. DECBGFAH D. CAFHGDB 4. 在有向图的逆邻接表存储结构中，顶点v在表结点中出现的次数是（）。 A. 顶点V的度 B. 顶点V的出度 C. 顶点V的入度 D. 依附于顶点V的边数 5. 顺序栈s的GetTop(s, e)操作是用e返回s的栈顶元素，则下列( )是正确的操作。 A. e=*(s.top) B. e=*(s.top-1) C. e=*(--s.top) D. e=s.top-1

A. 32 B. 33 C. 34 D. 40 11. 用带头结点的单链表存储队列，其队头指针指向头结点，队尾指针指向队尾结点，则在进行出队时（）。 A. 仅修改队头指针 B. 仅修改队尾指针 C. 对头、尾指针都要修改 D. 对头、尾指针都可能要修改 12. 由权为7,2,4,5的四个叶子结点构造一个哈夫曼树，该树的带权路径长度为（）。 A. 33 B. 36 C. 35 D. 34 13. 现有一"遗传"关系：设x是y的父亲，则x可以把它的属性遗传给y。表示该遗传关系最适合的数据结构为( ) 。 A．向量 B．图 C．树 D．二叉树 14. 线性表是具有n个 ( )的有限序列。 A. 表元素 B. 字符 C. 数据元素 D. 数据项 15. 在所有排序方法中，关键字的比较次数与记录的初始排列无关的是（）。 A. 希尔排序 B. 冒泡排序 C. 直接插入排序 D. 直接选择排序 二．填空题(每空2分，共20分) 1. 单链表中设置头结点的作用是。

2011年暨南大学830数据结构考研试题

暨南大学 2011 年全国硕士研究生统一入学考试自命题试题 *******************************************************************************学科与专业名称：计算机技术, 软件工程 考试科目代码与名称：数据结构 考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。 一. 选择题(每题2 分，共30 分) 1. 算法分析的目的是（）。 A. 找出数据结构的合理性 B. 研究算法中的输入和输出关系 C. 分析算法的效率以求改进 D. 分析算法的易读性和文档性 2. 下列函数中渐近时间复杂度最小的是（）。 A. T1(n)=log2n+5000n B. T2(n)=n 2-8000n C. T3(n)=n 3+5000n D. T4(n)=2nlog2n-1000n 3. 线性表的动态链表存储结构与顺序存储结构相比，优点是（）。 A. 所有的操作算法实现简单 B. 便于随机存取 C. 便于插入与删除 D. 便于节省存储器空间 4．若进栈序列为1,2,3,4,5,6, 且进栈和出栈可以穿插进行，则可能出现的出栈序列为( )。A．3,2,6,1,4,5 B．5,6,4,2,3,1 C．5,1,2,3,4,6 D．3,4,2,1,6,5 5. 顺序存储的线性表的第一个元素的存储地址是100，每个元素的长度为4，则第4 个元素的 存储地址是（）。 A. 108 B. 112 C. 116 D. 120 6. 在任意一棵二叉树的先序序列和后序序列中，各叶子之间的相对次序关系( )。A．不一定相同B．互为逆序C．都不相同D．都相同 7. 高度为5 的二叉树至多有结点数为（）。 A. 63 B. 3 2 C. 31 D.64 8. 图的邻接矩阵表示法适用于表示（）。 A．无向图B．有向图C．稠密图D．稀疏图 9. 在一个单链表中,若p 所指的结点不是最后一个结点,在p 之后插入s 所指的结点, 则执行 ( )。 A. s->next=p; p->next=s B. p->next=s; s->next=p C. p=s; s->next=p->next D. s->next=p->next; p->next=s 10. 若在线性表中采用折半查找法查找元素，该线性表应该是（）。 A. 元素按值有序 B. 采用顺序存储结构 C. 元素按值有序且采用顺序存储结构 D. 元素按值有序且采用链式存储结构 考试科目：数据结构共 5 页，第1 页11. 已知一棵二叉树结点的先序序列为ABDGCFK, 中序序列为DGBAFCK, 则结点的后

2019年广东暨南大学数据结构考研真题

2019年广东暨南大学数据结构考研真题 一、单项选择题(每题2分，共30分) 1.在任意一棵二叉树的先序序列和后序序列中，各叶子之间的相对次序关系()。 A.不一定相同 B.互为逆序 C.都不相同 D.都相同 2.深度为4的二叉树至多有结点数为()。 A.18 B.14 C.15 D.16 3.在一个具有n个顶点的有向图中，若所有顶点的入度数之和为m，则所有顶点的度数之和为()。 A.m B.m-1 C.m+1 D.2m 4.快速排序在()情况下最不利于发挥其长处。 A.被排序的数据量太大. B.被排序数据中含有多个相同的关键字 C.被排序的数据完全无序 D.被排序的数据已基本有序 5.一组记录的关键字为(45,80,55,40,42,85),则利用堆排序的方法建立的初始堆为()。 A.(80,45,55,40,42,85) B.(85,80,55,40,42,45) C.(85,80,55,45,42,40) D.(85,55,80,42,45,40) 6.对有18个元素的有序表(下标为1~18)作折半查找,则查找A[3]的比较序列的下标为()。 A.1,2,3 B.9,5,2,3 C.9,5,3 D.9,4,2,3 7.具有n个顶点的完全有向图的边数为()。 A.n(n-1)/2 B.n(n-1) C.n2 D.n2-1 8.利用逐点插入法建立序列(50,72,43,85,75,20,35,45,65,30)对应的二叉排序树以后，查找元素35要进行()。 A.4次 B.5次 C.3次 D.2次 9.判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以用()。

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

2019年全国硕士研究生统一入学考试自命题试题（A卷） ******************************************************************************************** 招生专业与代码：计算机科学与技术、软件工程、网络空间安全、工程硕士 研究方向：计算机系统结构081201，计算机软件与理论081202，计算机应用技术 081203，软件工程083500，计算机技术(专业学位) 085211，网络空间安全083900 考试科目名称及代码：数据结构830 考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。 一、单项选择题(每题2分，共30分) 1. 在任意一棵二叉树的先序序列和后序序列中，各叶子之间的相对次序关系( )。 A．不一定相同B．互为逆序C．都不相同D．都相同 2. 深度为4的二叉树至多有结点数为（ ）。 A. 18 B. 14 C. 15 D.16 3. 在一个具有n个顶点的有向图中，若所有顶点的入度数之和为m，则所有顶点的度数之和 为（）。 A．m B．m-1 C．m+1 D．2m 4. 快速排序在( )情况下最不利于发挥其长处。 A. 被排序的数据量太大. B. 被排序数据中含有多个相同的关键字 C. 被排序的数据完全无序 D. 被排序的数据已基本有序 5. 一组记录的关键字为（45,80,55,40,42,85）, 则利用堆排序的方法建立的初始堆为（）。 A. （80,45,55,40,42,85) B. (85,80,55,40,42,45) C. (85,80,55,45,42,40) D. (85,55,80,42,45,40) 6. 对有18个元素的有序表（下标为1~18）作折半查找,则查找A[3]的比较序列的下标为( )。 A. 1,2,3 B. 9,5,2,3 C. 9,5,3 D. 9,4,2,3 7. 具有n个顶点的完全有向图的边数为( )。 A. n(n-1)/2 B. n(n-1) C. n2 D. n2-1 8. 利用逐点插入法建立序列（50,72,43,85,75,20,35,45,65,30）对应的二叉排序树以后，查找元 素35要进行（）。 A. 4次 B. 5次 C. 3次 D. 2次 9. 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以用（）。 A．求最短路径的Floyd方法B．求最短路径的Dijkstra方法 C．广度优先遍历算法D．深度优先遍历算法 10. 对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为（）。 A．0 B．1 C．n D．n+1 11. 在一个单链表中,若p所指的结点不是最后一个结点,在p之后插入s所指的结点, 则执行( )。 A. s->next=p; p->next=s B. p->next=s; s->next=p C. p=s; s->next=p->next D. s->next=p->next; p->next=s 考试科目：数据结构共5 页，第 1 页

数据结构暨南大学试题

1.对顺序存储结构的线性表,设表长为La;插入一个数据元素需平均] 移动表中元素n/2 个;在最坏情况下需移动表中元素_n_个。 2.从逻辑角度看，四种基本的数据结构可分为集合、线性结构、 树形结构和图状结构；两种存储结构为顺序和链式。 5.堆栈被称为一个后进先出的线性表;队列被称为一个先进先出的线性表 6.静态查找表的查找方法主要有：有序表查找及有序表、静态树表、索引顺序表等查找方法； 8.内部排序方法大致可分为插入、交换、选择、归并和计数等五类； 简单排序方法的时间复杂度为O(n2)。 9．前序序列和中序序列相同的二叉树为单右支二叉树或孤立结点 10.文件的组织方式有顺序、随机和链等三种；顺序文件又可分为 连续文件和串联文件两大类。 11. 在内部排序中，平均比较次数最少的是快速排序，要求附加 的内存容量最大的是归并排序。 12.由n个权值构成的哈夫曼树共有2n-1个结点。 13.在单链表中，除首元结点外，任一结点的存储位置由其直接前趋 结点的链域指示。 14.栈结构允许进行删除操作的一端称为栈的栈顶。 15. GetTail(p)为求广义表p的表尾函数。其中( )是函数符号，运算 GetTail(GetHead((a,b),(c,d)))的结果是(b)。 16．循环链表的主要优点是从任一结点出发可以遍历链表中的所有结点17．在左右子树均不空的先序线索二叉树（有n个结点）中，空链 域的数目是1。 18.如果含n个顶点的图是一个环，则它有n棵生成树。 在有序表ST中折半查找其关键字等于key的数据元素。若找到， 则函数值为该元素在表中的位置，否则为0。 Low =1; high=ST.length; While (low<=high){ mid= (low+high)/2; if EQ(key, ST.elem[mid].key) return mid; else if LT( key, ST.elem[mid].key) high=mid-1; else low= mid+1; 2. 中序遍历二叉树T的递归算法，对数据元素操作调用函数printf()。InOrderTraverse(struct TNode *T){ if (T){ InOrderTraverse(___T->lchild___); printf("%c",___ T->data _____); InOrderTraverse(___T->rchild_____); 3. void Pop(SqStack *S0, char *e){ //若栈不空，则删除栈顶元素，用e返回其值。 if(S0->top= =__S0->base _____) return; ____(S0->top)_____; *e=*(____(S0->top)_____);

数据结构暨南大学期末试卷试题

数据结构暨南大学期末试卷试题 一、判断题(共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(

5.堆栈被称为一个_____________的线性表;队列被称为一个_____________的线性表。 6.静态查找表的查找方法主要有:有序表查找及 ________________________;在n个记录中进行折半查找，当查找不成功时，与关键字比较次数最多为_____________________。 7.一颗9阶的,_ 树，其每个结点(除根外)的子树数目为________________，关健字数目为________________。 8.内部排序方法大致可分为__________、___________、____________、 __________和_________等五类;简单排序方法的时间复杂度为_________。 9.外部排序分为两个相对独立的阶段。首先产生有序子文件即___________;然后对它们进行__________，直至整个文件有序为止。 10.文件的组织方式有_________________等三种;顺序文件又可分为 _________________两大类。 三、算法(共70分) 要求:对1、2、3题，在它们的下划线处填空;对4、5、6、7题,从第7题以下的空白纸张处开始书写，标明题号且只写出最终结果即可。 1. 算法填空题 (12分) Int Search_Bin(SSTable ST, KeyType key) { 在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0。 Low =1; high=ST.length; While (__________________){ mid=_______________________; if EQ(key, ST.elem[mid].key) return mid; else if LT( key, ST.elem[mid].key) high=______________; else low=______________;