青岛大学2017年硕士研究生入学考试试题
科目代码：921科目名称：数据结构与算法基础（共5页）请考生写明题号，将答案全部答在答题纸上，答在试卷上无效
一、单项选择题（共15小题，每小题2分，共30分）
1.以下时间复杂度T(n)最高的是：
A.T(n)=666n+999
B.T(n)=100n2
C.T(n)=2n
D.T(n)=22223n log2n
2.二叉树T中度为2的结点有2016个，则T中叶子结点有：
A.2015个
B.2016个
C.2017个
D.以上都不对
3.逆波兰式(后缀式)10255/-2*83-/的值是：
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(log N)。
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.下列排序算法中，其中（）是稳定的
1