中南大学期末考试真题+解析

题目	题型
本期学了很多类算法，请针对以下几类设计策略，举出相应的例子，详细描述算法细节，以说明它们为什么是属于相应的设计策略？	问答
中南大学12-13算法分析与设计	单选
归并排序在最好情况下的时间复杂度为 O(nlogn).	单选
具有 n 个结点的二叉排序树的树高均为 O(logn) 。	单选
如果一个问题是 NP 完全问题，它肯定也是 NP 问题。	单选
给定 n 个数，可以在 O （ n ）的时间内找到 10 个最大数与 10 个最小数之间的中间数。	单选
给定 n 个数，可以在 O （ n ）的时间内找到 10 个最大数与 10 个最小数之间的中间数。	单选
Kruskal 算法利用了动态规划思想寻找给定图中的最小生成树。	单选
n!=O(2n) 。	单选
回溯法借鉴了广度优先的策略得到问题的最优解。</span>	单选
对于一个有 n 个顶点 m 条边的无向图 G ，有两个不同的顶点 s ¹ t ，则在 O(m+n) 的时间内可以找到 s 与 t 之间的最短路径。	单选
在最坏情况下，快速排序耗费 O(N2) 。	单选
如果图中包含负权值的边，则 Dijkstra 算法不可适用。	单选
分治法是属于自底向上的算法策略；动态规划是属于自顶向下的算法策略。	单选
有一个算法，将 n 个整数 a1,...,an 作为输入，算法的时间复杂度是 O(a1+a2+......+an) 。它是一个多项式时间算法。	单选
有一个图 G=(V,E) ，每条边 e∈E 的权 We >0, 如果一棵生成树 T 最小化 Σ e∈T We ，那么 T 也最小化 Σ e∈T We 2 ，反之也成立（即图中边的权值都平方后，生成树 T 仍是这个图的最小生成树）。	单选
给定两个判定性问题 Q1 、 Q2 ，如果 Q1 可以在多项式时间内规约到 Q2 ，则 Q1 和 Q2 具有同等难度。	单选
如果一个问题是 NP 完全问题，它肯定也是 NP-hard 问题，反过来却不一定成立。	单选
设计一个算法判断一个多边形是否是凸多边形，并分析你的算法的时间性能 ( 注：输入是沿着多边形逆时针的顶点系列 ) 。	问答
给定图 G=(V, E) ，利用深度优先算法统计图 G 中连通块的个数。给出统计算法 .	问答

题目

题型

本期学了很多类算法，请针对以下几类设计策略，举出相应的例子，详细描述算法细节，以说明它们为什么是属于相应的设计策略？

问答

中南大学12-13算法分析与设计

单选

归并排序在最好情况下的时间复杂度为 O(nlogn).

单选

具有 n 个结点的二叉排序树的树高均为 O(logn) 。

单选

如果一个问题是 NP 完全问题，它肯定也是 NP 问题。

单选