1青岛大学2017年硕士研究生入学考试试题科目代码：921科目名称：数据结构与算法基础（共5页）请考生写明题号，将答案全部答在答题纸上，答在试卷上无效一、单项选择题（共15小题，每小题2分，共30分）1.以下时间复杂度T(n)最高的是：A. T(n)=666n+999 B. T(n)=100n2C. T(n)=2n D. T(n)=22223nlog2n2.二叉树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. 64.元素ABCDE依次入栈，则以下( )是不可能的出栈次序。A. ABCDE B. EDCBA C. ACBDE D. DABCE5.对于有N个结点的二叉搜索树(BinarySearchTree)，以下说法正确的是：A.在此树中查找值为x的结点的时间复杂度是O(logN)。B.将此树的每个结点的左右儿子结点互换，产生的新树依然是一棵二叉搜索树。C.此树中值最大的结点一定在右子树。D.此树中值最小的结点一定不在右子树。6.一个具有N个顶点的无向连通图G，其生成树为T，以下说法正确的是：A.该生成树一定是唯一的。B.该生成树可能不唯一，但不同生成树各边的权值之和是相等的。C.生成树T一定具有N-1条边。D.生成树T是图G的极大连通子图。7.二叉树的第k(k>=1)层的结点数最多为：A2k-1 B.2k+1 C.2k-1 D.2k-18.下列排序算法中，其中（）是稳定的2A.堆排序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. AEBCFD10.设N是描述问题规模的非负整数，下面程序片段的时间复杂度是：x=1; while(x3，则对于图的说法，以下正确的是：A.对于有N个顶点的无向图G，从一个顶点出发进行一次深度优先搜索，若遍历结果的结点数小于N，则图G必有环。B.对于有向连通图G，若不存在拓扑排序序列，则图G必有环。C.对于具有N个顶点的无向图G，若边数大于N，则图G必连通。D.一个具有N个顶点和N条边的有向图G，不可能是强连通的。15.对于规模为N的排序算法时间复杂度，以下正确的是：3A.目前最快的排序算法的平均时间复杂度是O(NlogN)。B.归并排序的最好、平均和最坏情况下的时间复杂度都是O(NlogN)。C.快速排序的最坏情况下的时间复杂度是O(NlogN)。D.冒泡排序的最好情况下的时间复杂度是O(N2)。二、判断题（共5小题，每小题2分，共10分）1.稀疏图较适合采用邻接矩阵的存储方式。2.采用哈希（散列）进行查找的时间复杂度是O(N)。3.任何一棵二叉树的叶结点在前、中、后序三种遍历中的相对次序不变。4.对二叉搜索树（BST）进行中序遍历，可得到一个递增序列。5.对图进行非递归的深度优先搜索，一般均使用队列（Queue）实现。三、填空题（共5空，每空2分，共10分）1.设一棵完全二叉树有65个结点，则该树有(1)层结点，叶子结点的数量是(2)。2.若一个无向完全图有20个顶点，则该图所有顶点的度之和为(3)。3.循环队列的数组大小为MaxSize，元素入队时，对于队尾位置rear的操作是(4)。4.假设一个文本使用的字符集是a,b,c,d,e,f，字符的哈夫曼编码依次为1100,1101,1110,10,0,1111，则编码串11110010110111001110对应的文字是(5)。四、应用题（共4小题，每题15分，共60分）1.根据右图所示二叉树，回答以下问题：(1)写出该树的前序、中序、后序遍历序列。(2)该树是一棵二叉搜索树，请简述二叉搜索树删除结点的算法，并画出删除A结点之后的新的二叉搜索树。(3)如果给定一棵二叉树的前序和中序遍历序列，是否能写出该树的后序遍历序列？请做出分析。42.根据下面所示无向图作答：(1)写出该图的邻接矩阵(2)写出从顶点A出发的3个深度优先搜索遍历序列(3)写出从顶点B出发的3个广度优先搜索遍历序列3.一个有向图的邻接表如下所示：(1)画出该图(2)写出该图的逆邻接表(3)写出该图的3个拓扑排序序列4.设有一组关键字序列为58,18,40,0,20,73,43，哈希（散列）表长度为13，哈希函数为：h(key)=keyMOD11(其中MOD为取余运算)，采用开放定址法的线性探测法解决冲突，请作答：5(1)将上述关键字依次加入哈希表，画出最终的存储结构图(2)计算此哈希表的装填因子(3)在表中查找关键字29，需依次与哪些关键字比较才能确认查找失败？(4)假设题干所示的关键字查找概率相同，计算查找成功的平均查找长度。五、算法分析与设计题（共4小题，每题10分，共40分）1.使用一个数组实现两个栈，要求最大限度地利用数组空间，使得只要数组还有空间，入栈操作就可以成功。请分析应当如何实现？并写出两个栈相应的出栈、入栈操作算法。2.请给出单链表的结构定义，并写出在单链表中查找第k个(k>=1)元素的算法。3.二叉树采用链式结构表示，结构定义如下：structTreeNodeintdata;structTreeNode*left;structTreeNode*right;给出计算二叉树叶子结点数量的算法。4.如何计算一个无向图的连通分量的数量？给出算法描述。