湖南大学2022年考研真题：866计算机科学与技术专业

湖南大学2022年考研真题：866计算机科学与技术专业

10道选择题

第某道：栈的插入和删除发生在

A栈顶 B栈底 C D

第某道：一个包含100个顶点的图，其邻接矩阵的大小为

A100 B100的平方 C99 D99的平方

第某道：以下哪种排序方法是不稳定的：

A 直接插入排序 B 冒泡排序 C选择排序 D堆排序

第十道：以下哪项因素更影响散列表的查找效率：

A 处理冲突的方法 B 表长 C 装填因子 D 散列表中元素的数量

大题：

给了一个函数的代码(是一个递归的函数)，让求其时间复杂度。(5分)(不复杂，时间复杂度就是递归的深度)

给了一张图，选择克鲁斯卡尔算法或prim算法，构造该图的最小生成树，要有过程

画出8个元素的二叉排序树。然后删掉该树的根节点，让画出新得到的二叉排序树

给定初始序列，让写出第一趟快速排序之后的结果序列

给定初始序列(共11个元素)，要求写出增量依次为5、3、2、1的每一趟希尔排序的结果

给定一个图，让写出5种可能的拓扑排序序列(图不复杂，很简单)

给出了一棵二叉树(有12个结点)的先序遍历序列和中序遍历序列，让写出该二叉树的后序遍历序列

给定一组关键字的值(大概十个左右)，散列表地址从0到17，散列函数为MOD 16，用线性探测法处理冲突。第一问：画出该散列表 第二问：在该散列表中查找关键字为46的元素，需要进行哪几次比较?

上面是还记得的大题，可能有遗漏。

算法设计题：三道。

一：设计一个算法，判断一个二叉树是否是完全二叉树(15分)(题干就这么些，没有对描述算法思想和时间复杂度的要求)

二：给定了一个正整数数组{33,18,15,12,17,20}，设计一个算法，将该数组中所有奇数调整到所有偶数之前。示例输出：{33,15,17,18,12,20}。(1)描述算法的基本设计思想(2)给出具体算法并适当注释(3)说明你所设计算法的时间复杂度(15分)

三：有向图，带权路径长度。然后给出了一个定义：将一个顶点到其它所有顶点的最大的带权路径长度称为该顶点的xx(具体名词不记得了)。将一个图中xx最小的顶点称为该图的核心。设计一个算法，求图的核心(1)描述算法的基本设计思想(2)给出具体算法并适当注释(3)说明你所设计算法的时间复杂度(20分)

热点推荐:

全国各院校2023研究生招生简章陆续公布>

百日集训营 100天封闭面授 老师带你弯道超车>