暨南大学-830数据结构【2017】考研真题
2023-06-21
999+
131.79KB
5 页
侵权投诉
2017 年全国硕士研究生统一入学考试自命题试题（B卷）
********************************************************************************************
学科、专业名称：计算机科学与技术、软件工程
研究方向：计算机系统结构 081201，计算机软件与理论 081202，计算机应用技术 081203，
软件工程 083500，计算机技术(专业学位) 085211，软件工程(专业学位) 085212
考试科目名称及代码：数据结构 830
考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。
一、 单项选择题(每题 2分，共 30 分)
1. 一个队列的入列序列是 1,2,3,4, 则队列的输出序列是（ ）。
A. 4,3,2,1 B. 1,2,3,4 C. 1,4,3,2 D. 3,2,4,1
2. 循环队列用数组 A[0..m-1]存放其元素值，已知其头尾指针分别是 front 和rear, 则当前队列中
的元素个数是( )。
A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front
3. 平衡二叉树的平均查找长度是( )。
A. O(n2）B. O(nlog2n）C. O(n）D. O(log2n）
4. 设F是由 T1、T2 和T3 三棵树组成的森林，与 F对应的二叉树为 B，T1、T2 和T3 的结点
数分别为 N1、N2和N3，则二叉树 B的根结点的左子树的结点数为（ ）。
A. N1-1 B. N2-1 C. N2+N3D. N1+N3
5. 计算机内部数据处理的基本单元是（ ）。
A. 数据 B. 数据元素 C. 数据项 D. 数据库
6. 设按照从上到下、从左到右的顺序从 1开始对完全二叉树的结点进行顺序编号，则编号为 i
结点的左孩子结点的编号为（ ）。
A. 2i+1 B. 2i C. i/2 D. 2i-1
7. 设用邻接矩阵 A表示有向图 G的存储结构，则有向图 G中顶点 i的入度为（ ）。
A. 第i行非 0元素的个数之和 B. 第i列非 0元素的个数之和
C. 第i行0元素的个数之和 D. 第i列0元素的个数之和
8. 设一组初始记录关键字序列为(16, 25,12, 30,47,11, 23,36, 9,18,31)，则以增量 d=5 的一趟希尔
排序结束后的结果为（ ）。
A. 11, 23,12, 9, 18,16, 25,36,30, 47, 31 B. 11, 23,12, 9, 16, 18, 25,36, 47, 30, 31
C. 16, 23,12, 9, 11,18, 25,36,30, 47, 31 C. 9, 11,12, 16, 18, 23, 25,30, 36, 47, 31
9. 设某有向图的邻接表中有 n个表头结点和 m个表结点，则该图中有（ ）条有向边。
A. n B. n-1 C. m D. m-1
10. 设哈夫曼树中的叶子结点总数为 m，若用二叉链表作为存储结构，则该哈夫曼树中总共有
（ ）个空指针域。
A. 2m-1 B. 2m C. 2m+1 D. 4m
11. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用 H(K)=K %9 作
为散列函数，则散列地址为 1的元素有（ ）个。
A．1 B．2 C．3 D．4
考试科目： 数据结构 共 5页，第 1页
12. 下面程序的时间复杂为（ ）。
for（i=1，s=0；i<=n；i++）{ t=1；for(j=1；j<=i；j++) { t=t*j；s=s+t；} }
A．O(n) B. O(n2) C. O(n3) D. O(n4)
13. 对于一个具有 n个顶点的无向连通图，它包含的连通分量的个数为( )。
A．0 B．1 C．n D．n+1
14. 设无向图 G中边的集合 E={(a,b)，(a,e)，(a,c)，(b,e)，(e,d)，(d,f)，(f,c)}，则从顶点 a出
发进行深度优先遍历可以得到的一种顶点序列为（ ）。
A. aebcfd B. acfebd C. aedfcb D. aedfbc
15.设指针变量 p指向双向链表中结点 A，指针变量 s指向被插入的结点 X，则在结点 A的后
面插入结点 X的操作序列为（ ）。
A. p->next=s；s->prior=p；p->next->prior=s；s->prior=p->nest；
B. s->prior=p; s->next = p->next; p->next=s; s->next->prior=s;
C. p->prior=s；p->nest->prior=s；s->prior=p；s->next=p->prior；
D. s->prior=p；s->next=p->next；p->next=s；p->next->prior=s；
二．填空题(每空 2分，共 20 分)
1. 采用堆排序、快速排序、冒泡排序，对初态为有序的表，最省时间的是 。
2. 设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则第 4 趟直接选择排
序结束后的结果为 。
3. 当待排记录序列按关键字顺序有序时，直接插入排序和冒泡排序能达到 的时间复杂
度，快速排序的时间性能退化为 (以第一个关键字为枢轴)。
4. 判定顺序栈是否为空的条件是 ，判定顺序栈是否为满的条件
是 。
5. 当向 B-树中插入关键字时,可能引起结点的 ,最终可能导致整个 B-树的高
度增加 。
6. 设散列表的长度为 8，散列函数 H(k)=k%7，用线性探测法解决冲突，则根据一组初始关
键字序列(8，15，16，22，30，32)构造出的散列表的平均查找长度是 。
7. 设在一棵度数为 3 的树中，度数为 3 的结点数有 2 个，度数为 2 的结点数有 1 个，度数为
1 的结点数有 2 个，那么度数为 0 的结点数有 个。
三．判断题（每题 1分，共 10 分，正确的选 t，错误的选 f）
1. 顺序表查找指的是在顺序存储结构上进行查找。（ ）
2. 循环队列中不存在队列满的问题。（ ）
3. n 阶对称矩阵可压缩存储到 n/2 个单元的空间中。( )
4. 一个图的邻接表表示法是唯一的。( )
5. 希尔排序是稳定的。( )
6. 由树转化成二叉树，该二叉树的右子树不一定为空。（ ）
7. 根据拓扑排序结果可以判断一个有向图中是否存在环路。（ ）
8. 稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非 0 元素。（ ）
9. 入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。( )
10.数据元素是数据的最小单位。（ ）
考试科目： 数据结构 共 5页，第 2页
摘要：
展开>>
收起<<
2017年全国硕士研究生统一入学考试自命题试题（B卷）********************************************************************************************学科、专业名称：计算机科学与技术、软件工程研究方向：计算机系统结构081201，计算机软件与理论081202，计算机应用技术081203，软件工程083500，计算机技术(专业学位)085211，软件工程(专业学位)085212考试科目名称及代码：数据结构830考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。一、单项选择题(每题2分，共30分...
声明：研友网所有资料均为用户上传分享，仅供参考学习使用，版权归原作者所有。若侵犯到您的权益，请告知我们处理！任何个人或组织，在未征得本平台同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。
