算法分析与设计综合试卷及答案.docxVIP

算法分析与设计综合试卷及答案

考试时间：______分钟总分：______分姓名：______

一、选择题

1.下列关于算法的时间复杂度T(n)和空间复杂度S(n)的说法中，正确的是：

(A)T(n)越小，算法的运行时间越长。

(B)一个算法的空间复杂度总小于或等于其时间复杂度。

(C)任何算法的时空复杂度都不能同时达到最优。

(D)如果一个算法的时间复杂度为O(nlogn)，其空间复杂度必为O(n)。

2.下列数据结构中，最适合表示稀疏矩阵（非零元素个数远小于总元素个数）的是：

(A)链栈

(B)哈希表

(C)稀疏矩阵压缩存储（如三元组表）

(D)二叉排序树

3.设有字母序列(EASYQRTUIOP)，依次进行插入操作后，得到的二分有哪些信誉好的足球投注网站树（BST）的高度为：

(A)3

(B)4

(C)5

(D)6

4.下列排序算法中，不可能产生稳定排序结果的是：

(A)冒泡排序

(B)插入排序

(C)选择排序

(D)希尔排序

5.判断一个无向图G是否存在环，可以采用以下哪种方法？

(A)拓扑排序

(B)求图的最小生成树

(C)深度优先有哪些信誉好的足球投注网站(DFS)

(D)广度优先有哪些信誉好的足球投注网站(BFS)

6.在有向图中，如果从顶点v到顶点u存在一条路径，那么顶点u的所有前驱顶点都一定是顶点v的前驱顶点。该说法：

(A)总是正确

(B)总是错误

(C)有时正确，有时错误

(D)无法判断

7.在以下算法设计范式中最适用于求解“最优化问题”（如求最短路径、最大利润）的是：

(A)分治法

(B)迭代法

(C)贪心法

(D)动态规划法

8.对于给定的递归函数F(n)=2*F(n/2)+n，其时间复杂度T(n)为：

(A)O(n)

(B)O(nlogn)

(C)O(n^2)

(D)O(logn)

9.动态规划算法通常用于解决哪一类问题？

(A)所有的最优化问题

(B)所有的排序问题

(C)具有重叠子问题和最优子结构特性的问题

(D)仅涉及递归的问题

10.下列关于哈希表的说法中，错误的是：

(A)哈希表的优点是查找速度快，尤其是在理想情况下。

(B)哈希表的缺点是存储空间利用率可能不高，且处理冲突开销可能较大。

(C)哈希表的查找效率与元素个数n成正比。

(D)常用的解决冲突的方法有链地址法和开放地址法。

二、填空题

1.在快速排序算法的平均情况下，其时间复杂度为_______。

2.对于一棵具有n个节点的二叉树，其最大可能高度为_______。

3.若一个无向图是连通的，则其生成树的最少边数为_______。

4.在图的邻接矩阵表示法中，若矩阵大小为n*n，则表示边存在的元素通常为_______（填一个符号或数字），表示无边存在的元素通常为_______（填一个符号或数字）。

5.贪心算法在每一步都选择一个_______的解，希望最终得到全局最优解。

6.解决背包问题的动态规划解法中，状态表示通常为(i,j)，其中i表示考虑前_______个物品，j表示当前背包容量为_______。

7.递归函数F(n)=F(n-1)+F(n-2)，且F(0)=0,F(1)=1，则F(n)是_______数列。

8.假设有5个元素进行堆排序，在初始建堆过程中，需要进行_______次父子节点间的比较（或调整）操作。

9.在一个长度为n的数组A中查找最大值和最小值，至少需要进行_______次比较。

10.哈希函数H(key)的设计目标之一是使得对于任意键值key1和key2，若key1≠key2，则H(key1)和H(key2)_______（填“可能相等”或“必然不相等”）。

三、判断题

1.()在任何情况下，堆排序的总时间复杂度都优于快速排序。

2.()哈希表的负载因子（填入元素数/总容量）越大，发生冲突的概率越低。

3.()任何递归算法都可以转换成等价的迭代算法。

4.()对于任何无向图，其邻接矩阵一定是对称矩阵。

5.()如果一个有向图的