暨南大学-830数据结构【2016】考研真题
2023-06-21
999+
134.17KB
5 页
侵权投诉
2016 年全国硕士研究生统一入学考试自命题试题（A卷）
********************************************************************************************
学科、专业名称：计算机科学与技术、软件工程
研究方向：计算机系统结构 081201，计算机软件与理论 081202，计算机应用技术 081203，
软件工程 083500，计算机技术(专业学位) 085211，软件工程(专业学位) 085212
考试科目名称及代码：数据结构 830
考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。
一、 单项选择题(每题 2分，共 30 分)
1. 在线索化二叉树中，T所指结点没有左子树的充要条件是（ ）。
A. T-> lchild=NULL B. T->ltag=1
C. t->ltag=1 且t-> lchild =Null D. 以上都不对
2. 一个带有头结点的单链表为空的判定条件是 ( )。
A. head == NULL B. head->next == NULL
C. head->next == head D. head != NULL
3. 线性链表不具有的特点是（ ）。
A. 随机访问 B. 不必预估所需存储空间大小
C. 插入与删除时不必移动元素 D. 所需空间与线性表长度成正比
4. 在下面的排序方法中，稳定的是（ ）。
A. 希尔排序 B. 堆排序 C. 插入排序 D. 快速排序
5.设有 n个待排序的记录关键字，则在堆排序中需要（ ）辅助记录空间。
A．O(1) B. O(n) C. O(nlog2n) D. O(n2)
6. 数组 A［５］［６］的每个元素占 5 个字节，将其按行优先次序存储。假设 A[1][1]元素的
存储地址为 1000，则元素 A［５，５］的存储地址为( )。
A. 1140 B. 1145 C. 1120 D. 1125
7.高度为 n的完全二叉树的结点数至少为（ ）。
A. 2n-1 B. 2n-1+1 C. 2nD. 2n+1
8. 设有一个无向图 G=（V，E）和 G’=（V’，E’），如果 G’为 G的生成树，则下面不正确
的说法是（ ）。
A．G’为 G的子图 B．G’为 G的连通分量
C．G’为 G的极小连通子图且 V’=V D．G’为 G的一个无环子图
9. 在有向图的邻接表存储结构中，顶点 V在表结点中出现的次数是（ ）。
A. 顶点 V的度 B. 顶点 V的出度
C. 顶点 V的入度 D. 依附于顶点 V的边数
10. 关键路径是事件结点网络中( )。
A．最短的回路 B．从源点到汇点的最短路径
C．最长的回路 D．从源点到汇点的最长路径
考试科目： 数据结构 共 5页，第 1页
11. 一个有 n个结点的无向图最多有（ ）条边。
A. n B. n-1 C. n(n-1) D. n(n-1)/2
12. 对某个无向图的邻接矩阵来说，( )。
A．第 i行上的非零元素个数和第 i列的非零元素个数一定相等
B．矩阵中的非零元素个数等于图中的边数
C．第 i行上，第 i列上非零元素总数等于顶点 vi的度数
D．矩阵中非全零行的行数等于图中的顶点数
13. 平衡二叉树的平均查找长度是 ( )。
A. O(n2）B. O(nlog2n）C. O(n）D. O(log2n）
14. 下列哪种排序需要的附加存储开销最大( )。
A. 快速排序 B. 堆排序 C. 归并排序 D. 插入 排序
15. 设一数列的顺序为 1,2,3,4,5,6, 通过栈操作可以得到（ ）的输出序列。
A. 3,2,5,6,4,1 B. 1,5,4,6,2,3
C. 6,4,3,2,5,1 D. 3,5,6,2,4,1
二．填空题(每空 2分，共 20 分)
1. 在一个长度为 n的顺序表中删除第 i个元素时，需向前移动 个元素。
2. 设数组 Data[0..m]作为循环队列 SQ 的存储空间，front 为队头指针，rear 为队尾指针
则执行出队操作时 front 指针的值应更新为 front= 。
3. 在单链表中，若要删除指针 p所指结点的后一结点，则需要执行下列语句：（设 q为指针
变量）q=p->next; ； 。
4. 在有 n个结点的二叉链表中，值为 NULL 的链域的个数为 。
5. 二叉树中度为 0的结点数为 30，度为 1的结点数为 30，总结点数为 。
6. 在堆排序的过程中，对任一分支结点进行筛选运算的时间复杂度为 ，整个
堆排序过程的时间复杂度为 。
7. 对于 n个记录（假设每个记录含 d个关键字）进行链式基数排序，总共需要进行 趟
分配和收集。
8. 设有向图 G 中有向边的集合 E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则该图的
一种拓扑序列为 。
三．判断题（每题 1分，共 10 分，正确的选 t，错误的选 f）
1. 在n个顶点的无向图中，若边数>n-1，则该图必是连通图。 （ ）
2. 具有 n个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的（ ）
3. 使用散列法存储时，哈希表的大小可随意选取，通常取 10 的倍数。（ ）
4. 向一个二叉排序树插入新的结点时，新插入的结点总是叶子结点（ ）
5. 数据元素是数据的最小单位。（ ）
6. 普里姆(Prim)算法相对于克鲁斯卡尔(Kruskal)算法更适合求一个稀疏图 G的最小生成树。
（ ）
7. 向二叉排序树中插入一个新结点，需要比较的次数可能大于此二叉树的高度 h。（ ）
8. 向一棵 B_树插入元素的过程中，若最终引起树根结点的分裂，则新树高度为原树的高度
加1。（ ）
9. 无向图的邻接矩阵一定是对称阵。 ( )
10. 对小根堆进行层次遍历可以得到一个有序序列。（ ）
考试科目： 数据结构 共 5页，第 2页
摘要：
展开>>
收起<<
2016年全国硕士研究生统一入学考试自命题试题（A卷）********************************************************************************************学科、专业名称：计算机科学与技术、软件工程研究方向：计算机系统结构081201，计算机软件与理论081202，计算机应用技术081203，软件工程083500，计算机技术(专业学位)085211，软件工程(专业学位)085212考试科目名称及代码：数据结构830考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。一、单项选择题(每题2分，共30分...
声明：研友网所有资料均为用户上传分享，仅供参考学习使用，版权归原作者所有。若侵犯到您的权益，请告知我们处理！任何个人或组织，在未征得本平台同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。
