当前位置：文档之家 › 暨南大学2020年《830数据结构》考研专业课真题试卷

暨南大学2020年《830数据结构》考研专业课真题试卷

  • 格式：pdf
  • 大小：296.62 KB
  • 文档页数：9

下载文档原格式

  / 9

合集下载

暨南大学830数据结构2010,2012--2020年考研真题

暨南大学830数据结构2010,2012--2020年考研真题

考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。
一、 单项选择题(每题 2 分，共 30 分)
1. 下述关于顺序存储结构优点的说法，哪个是正确的（ ）
A. 插入运算方便
B. 可方便地用于各种逻辑结构的存储表示
C. 存储密度大
D. 删除运算方便
2. 假设根结点为第 1 层，深度为 h 层的二叉树至少有( ) 个结点(h>1)；
A．3
B．4
C．5
D．6
13. 有一个 100*90 的整数稀疏矩阵，其中非 0 元素个数为 10；设每个整数占用 3 个字节，则
用三元组表示该矩阵时，总共需要的存储空间为( )字节。
A．30
B．33
C．90
D．99
14. 在一个双向链表中，当删除结点 p 时，错误的操作序列为 ( )。
A. p=p->prev; p->next->prev=p; p->next=p->next->next;
2020 年全国硕士研究生统一入学考试自命题试题 B 卷
********************************************************************************************
学科、专业名称：网络空间安全 研究方向：网络空间安全 083900 考试科目名称及代码：数据结构 830
4. 以下关于递归算法的论述，不正确的是( )
A. 递归算法的代码可读性好
B. 递归算法可以提高程序运行效率
C. 递归调用层次太深有可能造成堆栈溢出 D. 递归调用层次太深会占用大量内存
5. 设有字符集合{4,6,3,W,S}，将字符序列 6W43S 中的字符按顺序进入堆栈，出栈可发生在任

暨南大学网络空间安全专业研究生统一入学考试自命题试题A卷

暨南大学网络空间安全专业研究生统一入学考试自命题试题A卷
4.试写出一种算法在带头结点的单链表结构上实现线性表操作 Length(L)。（8 分）
5.请用顺序存储的方式，用 C 语言写出实现把串 S1 复制到串 S2 的串复制函数 strcpy（S1，S2）。
（8 分）
6.试着描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。（6 分）
五、算法填空（共 2 小题，每空 2 分，共 20 分）
址冲突的整数有（）个
A. 1 B. 2
C. 3
D. 4
二、填空题 (每空 2 分，共 20 分)
1. 有一个 10 阶对称矩阵 A，采用压缩存储方式（以行序为主，且 A[0][0]=1）,则 A[8][5]的地 址是（ ） 2. 含有 100 个结点的树有（ ）条边。 3. 已知二叉树的前序序列为 ABDEGCFHIJ，中序序列为 DBGEAHFIJC，请写出后序列（ ） 4. 数据结构的三要素是指（ ）（ ）（ ）。
1/4
5. 在顺序表中插入或删除一个元素，需要平均移动（ ），具体移动的元素个数与（ ）有关。 6. 设栈 S 与队列 Q 的初始状态皆为空，元素 a1,a2,a3,a4,a5 和 a6 依次通过一个栈，一个元素出 栈后即进入队列 Q，若 6 个元素出队列的顺序是 a3,a5,a4,a6,a2,a1,则栈 S 至少应该容纳（ ）个 元素。 7. 在一个无向图的邻接表中，若表结点数目为 m，则图中边的条数为（ ）。
A. a 在 B 的左边 B. a 在 b 的右边 C. a 是 b 的祖先 D. a 是 b 的子孙
7. 用单向链表来实现容量为 n 的堆栈时，链表头指针指向堆栈顶部元素，链表尾指针指向堆栈
底部元素，则以下说法错误的是（ ）
பைடு நூலகம்

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

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

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

暨南大学数据结构考研真题试题2017、2020年

暨南大学数据结构考研真题试题2017、2020年

A. 64WS3
B. 4W36S
C. 6W34S
D. WS436
6. 在管理城市道路交通网络据时，最适合采用（ ）数据结构来对其进行存储。
A．有向图
B．无向图
C．树
D．矩阵
7. 具有 k 个顶点的完全有向图的边数为( )。
A. k(k-1)
B. k(k-1)/2
C. k2-1
D. k2+1
8. 若线性表最常用的操作是增加或者删除某个元素, 则采用( )存储方式节省时间.
1. 对 n 个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为
。
2. 在 单 链 表 中 ， 要 将 m 所 指 结 点 插 入 到 n 所 指 结 点 之 后 ， 其 语 句 表 示
为
。
3. 设有数组 A[i][j]，数组的每个元素长度为 3 字节，i 的值为 1 到 8，j 的值为 1 到 10，数组
从 内 存 首 地 址 BA 开 始 顺 序 存 放 ， 当 用 以 列 为 主 存 放 时 ， 元 素 A[5][8]的 存 储 首 地 址
为
。
4. 设哈夫曼树中有 199 个结点，则该哈夫曼树中有
个叶子结点。
5. 对 22 个记录的有序表作折半查找，当查找失败时候，至多需要比较
次关键字，
至少需要比较
A．3
B．4
C．5
D．6
考试科目：数据结构
1/9
13. 有一个 100*90 的整数稀疏矩阵，其中非 0 元素个数为 10；设每个整数占用 3 个字节，则
用三元组表示该矩阵时，总共需要的存储空间为( )字节。
A．30
B．33
C．90
D．99

暨南大学848计算机基础综合专业课考研真题(2020年)

暨南大学848计算机基础综合专业课考研真题(2020年)

有关。
5.在哈希查找方法中，要解决两方面的问题，它们是
和
6. 循环队列中，Q.rear == Q.front表示循环队列空，表示循环队列满的条件是
。 。
三、 简答题（共 3 小题，每题 7 分，共 21 分） 1. 将下面的森林转换为二叉树（3 分），并给出该二叉树的中序线索链表（4 分）。
A
C
G
B
不付韶华 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 1 0 1 0
四、 编写算法（共 2 小题，每题 10 分，共 20 分） 1. 试编写一个算法完成下面的功能：对于输入的任意一个非负十进制整数，输出与其等值的 八进制数。（10 分）
2. 试编写一个算法，在有向图 G 中，判定从顶点 Vi 到顶点 Vj 是否有通路。（10 分）
081203、电子信息(专业学位) 085400
考试科目名称及代码：计算机基础综合 848
考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。
第一部分 数据结构（75 分）
一、 单项选择题(每题 2 分，共 20 分)
1. 含有 m 个结点的二叉树链式存储结构中空指针的个数为 ( )。
二、 填空题(每空 2 分，共 14 分)
1. 已知一棵二叉树的中序遍历序列为GDHBAECIF，后序遍历序列为GHDBEIFCA，那么先序遍历序
列为
。
2. 若某记录的关键字序列是（491，77，572，16，996，101，863，258，689，325），以第一
个关键字为枢轴，写出采用快速排序算法第一趟排序的结果
E
F
D
H
2. 设 Huffman 编码的长度不超过 4，若已对两个字符编码为 01 和 11，则最多还可以对多少个

暨南大学2019年招收攻读硕士学位研究生入学考试试题数据结构830

暨南大学2019年招收攻读硕士学位研究生入学考试试题数据结构830

2019年全国硕士研究生统一入学考试自命题试题（A卷）********************************************************************************************招生专业与代码：计算机科学与技术、软件工程、网络空间安全、工程硕士研究方向：计算机系统结构081201，计算机软件与理论081202，计算机应用技术081203，软件工程083500，计算机技术(专业学位) 085211，网络空间安全083900考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。

一、单项选择题(每题2分，共30分)1. 在任意一棵二叉树的先序序列和后序序列中，各叶子之间的相对次序关系( )。

A．不一定相同 B．互为逆序C．都不相同D．都相同2. 深度为4的二叉树至多有结点数为（）。

A. 18B. 14C. 15D.163. 在一个具有n个顶点的有向图中，若所有顶点的入度数之和为m，则所有顶点的度数之和为（）。

A．m B．m-1 C．m+1 D．2m4. 快速排序在( )情况下最不利于发挥其长处。

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,3B. 9,5,2,3C. 9,5,3D. 9,4,2,37. 具有n个顶点的完全有向图的边数为( )。

A. n(n-1)/2B. n(n-1)C. n2D. n2-18. 利用逐点插入法建立序列（50,72,43,85,75,20,35,45,65,30）对应的二叉排序树以后，查找元素35要进行（）。

2021年暨南大学830数据结构考研专业课考试大纲(含参考书目)

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

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

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

一、基本概念和术语
（一）数据元素、数据结构、抽象数据类型等概念
（二）算法设计的基本要求
（三）语句的频度和估算时间复杂度
二、线性表
（一）线性表的定义和基本操作 暨南大学硕士研究生入学考试自命题考试大纲 (含参考书目清单)
第 1／4页。

暨南大学_830数据结构2010--2017_考研真题／硕士研究生入学考试试题

A．求关键路径的方法B．求最短路径的Dijkstra方法
C．广度优先遍历算法D．深度优先遍算法
19.通过一趟排序就能从整个记录序列中选择出具有最大（或最小）关键字的记录，这种排序方法是( )。
A.堆排序B.快速排序C.直接插入排序D.归并排序
20.设单链表中指针p指着结点A,若要删除A之后的结点(若存在),则需要修改指针的操作为( )。
13.在一个有向图的邻接表或逆邻接表中，如果某个顶点的链表为空，则该顶点的度一定为零。（）
14.在n个顶点的无向图中，若边数>n-1，则该图必是连通图。（）
15.一颗满二叉树同时又是一颗平衡树。（）
四.应用题（35分）
A. p->next=p->next->next B. p=p->next
C. p=p->next->next D. p->next=p
二．填空题(每空2分，共30分)
1.在堆排序，希尔排序，快速排序，归并排序算法中，占用辅助空间最多的是。
2.在散列表(hash)查找中，评判一个散列函数优劣的两个主要条件是：
A.单链表B.双链表C.单循环链表D.顺序表
6.线性表的链接实现有利于( )运算
A.插入B.读表元素C .查找D.定位
7.设连通图G的顶点数为n,则G的生成树的边数为( )
A. n B. n-1 C.2n D. 2n-1
8.从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动（）个元素。
A.n-i B.n-i+1 C.n-i-1 D. i
9.若有一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n,则第i个输出元素是（）
A.n-i B.n-i-1 C.n-i+1 D.不确定

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

2021年暨南大学数据结构考研真题2021年全国硕士研究生统一入学考试自命题试题********************************************************************************************学科与专业名称：计算机技术，软件工程考试科目代码与名称：830数据结构学生特别注意：所有答案必须写下在答题纸（卷）上，写下在本试题上一律不给分后。

一.选择题(每题2分后，共30分后)1．队列操作方式的原则就是（）。

a.先进先出b.后进先出c.就可以展开填入d.就可以展开删掉2.一个栈的进栈序列就是a,b,c,d,e,则栈的不能可能将的输入序列就是（）。

a.edcbab.decbac.dceabd.abcde3.使用顺序搜寻法搜寻长度为n的线性表时,每个元素的平均值搜寻长度为（）。

a.nb.n/2c.(n+1)/2d.(n-1)/24.线性表的链接同时实现有助于()运算。

a.读表元素b.填入c.搜寻d.定位5.设单链表指针p对着结点a,若必须删掉a之后的结点(若存有),则须要修正指针的操作方式为()。

a.p->next=p->next->nextb.p=p->nextc.p=p->next->nextd.p->next=p6.在内部排序中,排序时不稳定的存有()。

a.插入排序b.冒泡排序c.快速排序d.福兰县排序7.在aoe网中，顺利完成工程的最为短时间就是（）。

a．从源点至汇点的最久路径的长度b．从源点至汇点的最长路径的长度c．最久的电路的长度d．最短的电路的长度8．以下（）方法所用辅助存储空间最小。

a．堆排序b．希尔排序c．快速排序d．福兰县排序9．具备8个顶点的无向图至少理应（）条边就可以保证就是一个相连图。

a．5b．6c．7d．810.对具备n个结点的有序表不计搜寻时，其时间复杂度就是（）。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

D. p=p->prev; p->next=p->next->next; p->next->prev=p;
15. 在一个具有 V 个顶点的有向连通图中，若所有顶点的入度数之和为 N，所有顶点的出度
之和为 M，则以下说法正确的是（ ）。
A．V=(M+N)/2
B．M>V
C．M=N
D．N>V
二、填空题(每空 2 分，共 20 分)
A. 64WS3
B. 4W36S
C. 6W34S
D. WS436
6. 在管理城市道路交通网络据时，最适合采用（ ）数据结构来对其进行存储。
A．有向图
B．无向图
C．树
D．矩阵
7. 具有 k 个顶点的完全有向图的边数为( )。
A. k(k-1)
B. k(k-1)/2
C. k2-1
D. k2+1
8. 若线性表最常用的操作是增加或者删除某个元素, 则采用( )存储方式节省时间.
D. 采用更好的地址冲突解决方法
11. 以下数据结构中哪一个是非线性结构？( )
A. 队列
B. 栈
C. 线性表
D. 二叉树
12. 对于一个整数集合{11，37，29，55，80，46，73，17}进行散列存储时，若选用函数
H（K）= K %9 作为散列(哈希)函数，则散列地址为 1 的元素有（ ）个。
A. 2h
B. 2h-1
C. 2h+1
D. 2h-1
3. 用单向链表来实现容量为 n 的堆栈时，链表头指针指向堆栈顶部元素，链表尾指针指向堆
栈底部元素，则以下说法错误的是( )
A. 入栈操作的复杂度为 O(1)
B. 出栈操作的复杂度为 O(1)
C. 删除底部元素的复杂度为 O(1)
D. 插入一个新的堆栈底部元素复杂度为 O(1)
A．3
B．4
C．5
D．6
考试科目：数据结构
1/
9
13. 有一个 100*90 的整数稀疏矩阵，其中非 0 元素个数为 10；设每个整数占用 3 个字节，则
用三元组表示该矩阵时，总共需要的存储空间为( )字节。
A．30B．Βιβλιοθήκη 3C．90D．99
14. 在一个双向链表中，当删除结点 p 时，错误的操作序列为 ( )。
从内 存首地 址 BA 开始顺序 存放，当用以 列为主存 放时，元 素 A[5][8]的存 储首地址
为
。
4. 设哈夫曼树中有 199 个结点，则该哈夫曼树中有
个叶子结点。
5. 对 22 个记录的有序表作折半查找，当查找失败时候，至多需要比较
次关键字，
至少需要比较
次关键字。
6. 由 3 个结点可以构造出
种不同的二叉树。
7. 最 大 容 量 为 s 的 循 环 队 列 ， 队 尾 指 针 是 rear ， 队 头 是 front ， 则 队 满 的 条 件
是
。
8. G 是一个非连通无向图，共有 28 条边，则该图至少有
个顶点。
9. 数据表中有 10000 个元素，如果仅要求求出其中最大的 10 个元素，则采用
考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。
一、 单项选择题(每题 2 分，共 30 分)
1. 下述关于顺序存储结构优点的说法，哪个是正确的（ ）
A. 插入运算方便
B. 可方便地用于各种逻辑结构的存储表示
C. 存储密度大
D. 删除运算方便
2. 假设根结点为第 1 层，深度为 h 层的二叉树至少有( ) 个结点(h>1)；
1. 对 n 个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为
。
2. 在 单 链 表 中 ， 要 将 m 所 指 结 点 插 入 到 n 所 指 结 点 之 后 ， 其 语 句 表 示
为
。
3. 设有数组 A[i][j]，数组的每个元素长度为 3 字节，i 的值为 1 到 8，j 的值为 1 到 10，数组
2020 年全国硕士研究生统一入学考试自命题试题 B 卷
********************************************************************************************
学科、专业名称：网络空间安全 研究方向：网络空间安全 083900 考试科目名称及代码：数据结构 830
4. 以下关于递归算法的论述，不正确的是( )
A. 递归算法的代码可读性好
B. 递归算法可以提高程序运行效率
C. 递归调用层次太深有可能造成堆栈溢出 D. 递归调用层次太深会占用大量内存
5. 设有字符集合{4,6,3,W,S}，将字符序列 6W43S 中的字符按顺序进入堆栈，出栈可发生在任
何时刻。则以下的出栈序列错误的是（ ）。
A. 单链表
B. 双链表
C. 单循环链表 D. 顺序表
9. 由权为 6,3,2,8 的四个叶子结点构造一个哈夫曼树，该树的带权路径长度为（ ）。
A. 36
B. 35
C. 34
D. 33
10. 为了提高哈希表的查找效率，以下方法说法不正确的是( )。
A. 设计好的哈希函数
B. 增加哈希函数的个数
C. 增大存储空间
A. p=p->prev; p->next->prev=p; p->next=p->next->next;
B. p=p->next; p->prev=p->prev->prev; p->prev->next=p;
C. p->prev->next=p->next; p->next->prev=p->prev;
排
序算法最节省时间。
三．判断题（每题 1 分，共 10 分，正确的选 T，错误的选 F）
1. 对 n 个记录进行插入排序，最多只需要 O(nlog(n))次两两比较。( ) 2. 用链表(Linked list)来实现的堆栈，单次入栈/出栈操作的时间复杂度可达到 O(1)。( ) 3. 当图 G 中存在权重为负数的边时，Dijkstra 算法不能用于计算 G 中两结点间最短路径。( ) 4. 贪婪算法有时候能够求出全局最优解，有时候无法求出全局最优解。( ) 5. 对含有 n 个记录的集合进行快速排序，在最坏情况下的时间复杂度是 O(nlog(n))。 ( ) 6. 哈希表查找效率高，当查找主键在范围[a,b]内所有的记录时，也应该优先选择哈希表。( ) 7. 无向图的邻接矩阵是对称的，因此可只存储矩阵的下三角阵以节省存储空间。 ( ) 8. 用 Prime 算法和 Kruskal 算法求得的图的最小生成树一定相同。( ) 9. 在一个有向图的邻接表或逆邻接表中，若某顶点的链表为空，则该顶点的度为零。( ) 10. 在有 n 个顶点的无向图中，若边数>n-1，则该图必是连通图。( )