第1页 / 共6页
第2页 / 共6页
第3页 / 共6页
第4页 / 共6页
第5页 / 共6页
第6页 / 共6页
2020年广东暨南大学数据结构考研真题.doc
2020 年广东暨南大学数据结构考研真题
学科、专业名称：网络空间安全
研究方向：网络空间安全 083900
考试科目名称及代码：数据结构 830
考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。
一、 单项选择题(每题 2 分，共 30 分)
1. 下述关于顺序存储结构优点的说法，哪个是正确的（ ）
A. 插入运算方便
B. 可方便地用于各种逻辑结构的存储表示
C. 存储密度大
D. 删除运算方便
2. 假设根结点为第 1 层，深度为 h 层的二叉树至少有(
) 个结点(h>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)
4. 以下关于递归算法的论述，不正确的是(
)
A. 递归算法的代码可读性好
B. 递归算法可以提高程序运行效率
C. 递归调用层次太深有可能造成堆栈溢出
D. 递归调用层次太深会占用大量内存
5. 设有字符集合{4,6,3,W,S}，将字符序列 6W43S 中的字符按顺序进入堆栈，出栈可发生
在任何时刻。则以下的出栈序列错误的是（
）。
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. 若线性表最常用的操作是增加或者删除某个元素, 则采用(
)存储方式节省时间.
A. 单链表
B. 双链表
C. 单循环链表
D. 顺序表
9. 由权为 6,3,2,8 的四个叶子结点构造一个哈夫曼树，该树的带权路径长度为（
）。
A. 36
B. 35
C. 34
D. 33
10. 为了提高哈希表的查找效率，以下方法说法不正确的是(
)。
A. 设计好的哈希函数
B. 增加哈希函数的个数
C. 增大存储空间
D. 采用更好的地址冲突解决方法
11. 以下数据结构中哪一个是非线性结构？(
)
A. 队列
B. 栈
C. 线性表
D. 二叉树
12. 对于一个整数集合{11，37，29，55，80，46，73，17}进行散列存储时，若选用函数
H（K）= K %9 作为散列(哈希)函数，则散列地址为 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;
B.
p=p->next; p->prev=p->prev->prev; p->prev->next=p;
C.
p->prev->next=p->next; p->next->prev=p->prev;
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 分)
1. 对 n 个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为
。
2. 在 单 链 表 中 ， 要 将 m 所 指 结 点 插 入 到 n 所 指 结 点 之 后 ， 其 语 句 表 示
为
。
3. 设有数组 A[i][j]，数组的每个元素长度为 3 字节，i 的值为 1 到 8，j 的值为 1 到 10，
数组从内存首地址 BA 开始顺序存放，当用以列为主存放时，元素 A[5][8]的存储首地址
为
。
4. 设哈夫曼树中有 199 个结点，则该哈夫曼树中有
个叶子结点。
5. 对 22 个记录的有序表作折半查找，当查找失败时候，至多需要比较
次关键字，
至少需要比较
次关键字。
6. 由 3 个结点可以构造出
种不同的二叉树。
7. 最 大 容 量 为 s 的 循 环 队 列 ， 队 尾 指 针 是 rear ， 队 头 是 front ， 则 队 满 的 条 件
是
。
8. G 是一个非连通无向图，共有 28 条边，则该图至少有
个顶点。
9. 数据表中有 10000 个元素，如果仅要求求出其中最大的 10 个元素，则采用
排
序算法最节省时间。
三．判断题（每题 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，则该图必是连通图。(
)
四、简答题（40 分）
1. 简述逻辑结构的四种基本关系并画出它们的关系图。（10 分）
2. 设二维数组 num[1….m, 1…n]含有 m*n 个整数，请分析判断数组中元素是否互不相同的
算法的时间复杂度。（8 分）
3. 设待排序的关键字序列为{12，2，16，30，28，10，16*，20，6，18} ，请写出二路归
并排序的方法下，每趟排序结束后关键字序列的状态。（6 分）
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;
}
2. 假设一维数组 A 保存有 N 个整数，以下快速排序算法代码能够对数组 A 进行排序。请在
__________处填上适当内容，使其成为一个完整的算法。
int partition(int* A, int N, int p, int r)
{
int x = A[r];
int i =
(5)
;
for (int j = p; j<=r-1; j++){
if (
(6)
){
i = i + 1;
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
int temp = A[i+1];
A[i+1] = A[r];
A[r] = temp;
return
(7)
;
}
void QuickSort(int* A, int N, int p, int r)
{
}
int q;
if (
(8)
){
q = partition(A, N, p, r);
QuickSort(
(9)
QuickSort(
(10)
);
);
}
return;
void main()
QuickSort(A, N, 0,N-1);
return 0;
{
}
六．编写算法（30 分）
1. 写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中
的合法字符为 A-Z 这 26 个字母与 0-9 这 10 个数字）。（10 分）
2. 已知 f 为单链表的表头指针，链表中存储的都是整型数据，请写出实现下列运算的递归
算法，求（1）链表中最大整数；（2）所有整数的平均值。（10 分）
3. 采用邻接表存储结构，编写一个算法，判别无向图中任意给定的两个顶点之间是否存在
一条长度为 k 的简单路径。（10 分）
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
