暨南大学-830数据结构【2020】考研真题
2023-06-21
999+
102.22KB
8 页
侵权投诉
2020 年全国硕士研究生统一入学考试自命题试题 B卷
********************************************************************************************
学科、专业名称：网络空间安全
研究方向：网络空间安全 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
考试科目：数据结构 1 /
8
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 算法求得的图的最小生成树一定相同。( )
考试科目：数据结构 2 /
8
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分）
考试科目：数据结构 3 /
8
摘要：
展开>>
收起<<
2020年全国硕士研究生统一入学考试自命题试题B卷********************************************************************************************学科、专业名称：网络空间安全研究方向：网络空间安全083900考试科目名称及代码：数据结构830考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。一、单项选择题(每题2分，共30分)1.下述关于顺序存储结构优点的说法，哪个是正确的（）A.插入运算方便B.可方便地用于各种逻辑结构的存储表示C.存储密度大D.删除运算方便2.假设根结点为第1层，深度为h...
声明：研友网所有资料均为用户上传分享，仅供参考学习使用，版权归原作者所有。若侵犯到您的权益，请告知我们处理！任何个人或组织，在未征得本平台同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。
