2017青岛大学考研真题921数据结构与算法基础.pdf
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.如何计算一个无向图的连通分量的数量?给出算法描述。