2017年山东青岛大学数据结构与算法基础考研真题.doc

发布时间：2023-11-14 发布人：admin 分类：说明书资料大小：0.09M 资料格式：doc 举报版权申诉

第1页 / 共4页

2017年山东青岛大学数据结构与算法基础考研真题.doc.pdf-第2页.jpg

第2页 / 共4页

2017年山东青岛大学数据结构与算法基础考研真题.doc.pdf-第3页.jpg

第3页 / 共4页

2017年山东青岛大学数据结构与算法基础考研真题.doc.pdf-第4页.jpg

第4页 / 共4页

文本预览

2017 年山东青岛大学数据结构与算法基础考研真题一、单项选择题（共 15 小题，每小题 2 分，共 30 分） 1.以下时间复杂度 T(n)最高的是： A.T(n)=666n+999 B.T(n)=100n2 C.T(n)=2n D.T(n)=22223nlog2n 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 个结点的二叉搜索树(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)层的结点数最多为： A.2k-1 B.2k+1 C.2k-1 D.2k-1 8.下列排序算法中，其中（）是稳定的 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(x3，则对于图的说法，以下正确的是： A.对于有 N 个顶点的无向图 G，从一个顶点出发进行一次深度优先搜索，若遍历结果的结点数小于 N，则图 G 必有环。 B.对于有向连通图 G，若不存在拓扑排序序列，则图 G 必有环。 C.对于具有 N 个顶点的无向图 G，若边数大于 N，则图 G 必连通。 D.一个具有 N 个顶点和 N 条边的有向图 G，不可能是强连通的。 15.对于规模为 N 的排序算法时间复杂度，以下正确的是： A.目前最快的排序算法的平均时间复杂度是 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)如果给定一棵二叉树的前序和中序遍历序列，是否能写出该树的后序遍历序列？请做出分析。 2.根据下面所示无向图作答： (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 为取余运算)，采用开放定址法的线性探测法解决冲突，请作答： (1)将上述关键字依次加入哈希表，画出最终的存储结构图 (2)计算此哈希表的装填因子 (3)在表中查找关键字 29，需依次与哪些关键字比较才能确认查找失败？ (4)假设题干所示的关键字查找概率相同，计算查找成功的平均查找长度。五、算法分析与设计题（共 4 小题，每题 10 分，共 40 分） 1.使用一个数组实现两个栈，要求最大限度地利用数组空间，使得只要数组还有空间，入栈操作就可以成功。请分析应当如何实现？并写出两个栈相应的出栈、入栈操作算法。 2.请给出单链表的结构定义，并写出在单链表中查找第 k 个(k>=1)元素的算法。 3.二叉树采用链式结构表示，结构定义如下：给出计算二叉树叶子结点数量的算法。 4.如何计算一个无向图的连通分量的数量？给出算法描述。

分享到：

赞收藏

资料库

2017年山东青岛大学数据结构与算法基础考研真题.doc

相关推荐

考研

热门标签

最新资料