考研算法试题和答案详解

考研算法试题和答案详解

单项选择题(每题2分，共10题)

1.对D个元素进行冒泡排序，最好情况下的时司复杂度是()

A.0(1)B.0(n)C.0(n'2)D.0(logn)

2.以下哪种排序算法是不稳定的()

A.归并排序B.插入排序C.快速排序D.冒泡排序

3.一个算法的时间复杂度为0(n+m),这里n和m是两个问题规

模，当n>>m时，时间复杂度近似为()

A.O(n)B.0(m)C.O(n+m)D.O(nrn)

4.深度优先搜索遍历图使用的数据结构是()

A.队列B.栈C.堆I).哈希表

5.求单源最短路径的Dijkstra算法适用于()

A.带负权边的图B.不带负权边的图C.所有图1).无向图

6.哈希表杳找的平均时间复杂度为()

A.0(n)B.0(logn)C.0(1)D.0(n^2j

7.以下数据结构中，支持快速查找和插入操作的数据结构是()

A.链表B.数组C.平衡二叉搜索树D.栈

8.对于一个有n个顶点的无向连通图，其最小生成树的边数是()

A.n-1B.nC.n+1D.2n

9.动态规划算法的基本要素是最优子结构性质和（）

A.贪心选择性质B.重叠子问题性质C.独立子问题性质I）.

无后效性

10.对n个元素进行堆排序，其时间复杂度是（）

A.0（n）B.0（nlogn）C.0（rT2）I）.0（logn）

答案：1.B2.C3.A4.B5.B6.C7.C8.A9.B

10.B

多项选择题（每题2分，共10题）

1.以下属于贪心算法的应用有（）

A.哈夫曼编码B.活动安排问题C.0-1背包问题D.单源

最短路径的Dijkstra算法

2.以下哪些数据结构可以用于实现优先队列（）

A.堆B.平衡二叉搜索树C.队列I）.栈

3.排序算法中，平均时间复杂度为0（nlogn）的有（）

A.归并排序B.快速排序C.堆排序D.插入排序

4.图的遍历方式有（）

A.广度优先搜索B.深度优先搜索C.先序遍历D.后序遍历

5.以下哪些是动态规划算法的特点（）

A.自底向上计算B.记忆化存储C.分解为子问题D.贪心选

择

6.关于哈希表，正确的说法有()

A.哈希函数设计的好可以减少冲突B.处理冲突的方法有开放定址

法和链地址法等

C.哈希表查找效率一定比顺序查找高I).哈希表的装填因子越大越

容易产生冲突

7.以下哪些操作在平衡二叉搜索树中时间复杂度为O(logn)()

A.插入B.查找C.删除D.遍历

8.对于最小生成树，以下说法正确的是()

A.一个无向连通图的最小生成树可能不唯一

B.Prim算法和Kruskal算法都是求最小生成树的算法

C.最小生成树包含图中所有顶点

D.最小生成树的边权之和一定最小

9.算法的基本特性有()

A.有穷性B.确定性C.可行性D.输入输出

10.以下属于数据结构的有()

A.数组B.链表C.图D.树

答案：1.ABD2.AB3.ABC4.AB5.ABC6.ABD7.ABC8.

ABCD9.ABCD10.ABCD

判断题(每题2分，共10题)

1.顺序直找的时间复杂度总是O(n)。()

2.快速排序在最坏情无下时间复杂度是0（d2）。（）

3.完全二叉树一定是满二叉树。（）

4.广度优先搜索遍历图可以使用队列来实现。（）

5.贪心算法一定能得到问题的最优解。（）

6.哈希表的装填因子越小，查找效率越高。（）

7.一叉排序树的中序遍历结果是有序的。（）

8.图的邻接矩阵表示法比邻接表表示法更节省空间。（）

9.动态规划算法通常用于解决具有最优子结构和重叠子问题的问题。

（）

10.堆是一种特殊的完全二叉树。（）

答案：1.X2.V3.X4.V5.X6.V7.V8.X

9.V10.J

简答题（每题5分，共4题）

1.简述快速排序的基本思想。

答案：选择一个基准值，将数组分为两部分，小于基准值的放在左边,

大于基准值的放在右边。然后对左右两部分分别进行同样的操作，直

到整个数组有序。

2.简述Dijkstra算法的主要步骤。

答案：初始化距离数组，源点距离为0,其余为无穷大。每次从未确

定顶点中选距离最小的顶点，更新其邻接顶点的距离。重复此过程直

到所有顶点确定。

3.简述平衡二叉搜索树的定义。

答案：它是一种二叉排序树，每个节点的左右子树高度差的绝对值不

超过1,且左右子树都是平衡二叉搜索树，能保证查找、插入、删除

操作平均时间复杂度为O（logn）o

4.简述贪心算法的基本要素。

答案：贪心选择性质和最优子结构性质。贪心选择性质指每一步选择

都是当前最优选择；最优子结构性质指问题的最优解包含子问题的最优

解。

讨论题（每题5分，共4题）

1.讨论排序算法在不同应用场景下的选择。

答案：数据量小且基本有序选插入排序；一般情况.追求平均性能选快

速排序；数据量极大且对稳定性有要求选归并排序；要得到最大或最小

的几个元素选堆排序。

2.讨论哈希表冲突处理方法的优缺点。

答案：开放定址法优点是实现简单，缺点是容易造成聚集；链地址法优

点是处理冲突简单，不易聚集，缺点是需要额外空间存储链表节点。

3