青岛大学-921数据结构与算法基础 (1）【2017】考研真题
2023-06-21
999+
189.59KB
5 页
侵权投诉
1
青岛大学 2017 年硕士研究生入学考试试题
科目代码： 921 科目名称： 数据结构与算法基础 （共 5页）
请考生写明题号，将答案全部答在答题纸上，答在试卷上无效
一、单项选择题（共 15 小题，每小题 2分，共 30 分）
1. 以下时间复杂度 T(n)最高的是：
A. T(n) = 666n + 999 B. T(n) = 100n2
C. T(n) = 2nD. T(n) = 22223nlog2n
2. 二叉树 T中度为 2的结点有 2016 个，则 T中叶子结点有：
A. 2015 个B. 2016 个C. 2017 个D. 以上都不对
3. 逆波兰式(后缀式) 10 25 5 / - 2 * 8 3 - / 的值是：
A. 2 B. 0 C. 1 D. 6
4. 元素 ABCDE 依次入栈，则以下( )是不可能的出栈次序。
A. ABCDE B. EDCBA C. ACBDE D. DABCE
5. 对于有 N个结点的二叉搜索树(Binary Search Tree)，以下说法正确的是：
A. 在此树中查找值为 x的结点的时间复杂度是 O(logN)。
B. 将此树的每个结点的左右儿子结点互换，产生的新树依然是一棵二
叉搜索树。
C. 此树中值最大的结点一定在右子树。
D. 此树中值最小的结点一定不在右子树。
6. 一个具有 N个顶点的无向连通图 G，其生成树为 T，以下说法正确的
是：
A. 该生成树一定是唯一的。
B. 该生成树可能不唯一，但不同生成树各边的权值之和是相等的。
C. 生成树 T一定具有 N-1 条边。
D. 生成树 T是图 G的极大连通子图。
7. 二叉树的第 k(k>=1)层的结点数最多为：
A．2k-1 B.2k+1 C.2k-1 D. 2k-1
8. 下列排序算法中，其中（ ）是稳定的
2
A. 堆排序 B. 快速排序 C. 希尔排序 D. 冒泡排序
9. 设无向图 G中的边的集合 E={(A,B), (A,C), (A,E), (B,D), (B,F), (C,F),
(D,F)}，则以下是从顶点 A出发的一次深度优先搜索遍历序列为：
A. ABCDEF B. ACBEDF C. ACFDBE D. AEBCFD
10. 设N是描述问题规模的非负整数，下面程序片段的时间复杂度是：
x=1; while(x<N*100) x=2*x;
A. O(100) B. O(log2N) C. O(N) D. O(Nlog2N)
11. 若线性表最常用的操作是在表头和表尾进行的，则最节省时间和空间
的实现是：
A. 仅带有头指针的双链表 B. 仅带有头指针的单向循环链表
C. 仅带有头指针的双向循环链表 D. 仅有尾指针的单向循环链表
12. 对于哈夫曼树，正确的说法是：
A. 哈夫曼树一定是一棵完全二叉树。
B. 哈夫曼树中可能含有度为 1的结点。
C. 哈夫曼树的任意非叶结点的左右子树交换后，仍是哈夫曼树。
D. 哈夫曼树的所有叶结点所在的层次都是相同的。
13. 对于堆（优先队列），正确的说法是：
A. 堆一定是一棵完全二叉树。
B. 对于最小堆，左子树结点的值均不大于树根（堆顶）的值，右子树
结点的值均不小于树根（堆顶）的值。
C. 将具有 N个元素的数组建成一个堆的最快算法的时间复杂度是
O(NlogN)。
D. 删除具有 N个元素的堆的堆顶元素（并保证删除过之后依然为堆）
的操作可在 O(1)时间完成。
14. 假设 N>3，则对于图的说法，以下正确的是：
A. 对于有 N个顶点的无向图 G，从一个顶点出发进行一次深度优先搜
索，若遍历结果的结点数小于 N，则图 G必有环。
B. 对于有向连通图 G，若不存在拓扑排序序列，则图 G必有环。
C. 对于具有 N个顶点的无向图 G，若边数大于 N，则图 G必连通。
D. 一个具有 N个顶点和 N条边的有向图 G，不可能是强连通的。
15. 对于规模为 N的排序算法时间复杂度，以下正确的是：
标签： #青岛大学
摘要：
展开>>
收起<<
1青岛大学2017年硕士研究生入学考试试题科目代码：921科目名称：数据结构与算法基础（共5页）请考生写明题号，将答案全部答在答题纸上，答在试卷上无效一、单项选择题（共15小题，每小题2分，共30分）1.以下时间复杂度T(n)最高的是：A.T(n)=666n+999B.T(n)=100n2C.T(n)=2nD.T(n)=22223nlog2n2.二叉树T中度为2的结点有2016个，则T中叶子结点有：A.2015个B.2016个C.2017个D.以上都不对3.逆波兰式(后缀式)10255/-2*83-/的值是：A.2B.0C.1D.64.元素ABCDE依次入栈，则以下()是不可能的出栈次序。A....
声明：研友网所有资料均为用户上传分享，仅供参考学习使用，版权归原作者所有。若侵犯到您的权益，请告知我们处理！任何个人或组织，在未征得本平台同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。
