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分）

一对一辅导咨询：