CMS专题
填空题求两个n阶矩阵的乘积，算法的基本操作和时间复杂度分别为（）和（）
题目
参考答案和解析
相似问题和答案
第1题：
对n个基本有序的整数进行排序，若采用插入排序算法，则时间和空间复杂度分别为（62）；若采用快速排序算法，则时间和空间复杂度分别为（63）。
A.O（n2）和O（n）
B.O（n）和O（n）
C.O（n2）和O（1）
D.O（n）和O（1）
本题考查基本排序算法的时间复杂度与空间复杂度。
第2题：
求两个n阶矩阵的乘积，算法的基本操作和时间复杂度分别为（）和（）
乘法；O（n3）
略
第3题：
要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为________和_______。
第4题：
对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal算法求最小生成树的时间复杂度为（）。
正确答案:O（n2）；O（elog2e）
第5题：
已知有实现同一功能的两个算法，其时间复杂度分别为O（2n）和O（n10），假设现实计算机可连续运算的时间为107秒（100多天），又每秒可执行基本操作（根据这些操作来估算算法时间复杂度）105次。试问在此条件下，这两个算法可解问题的规模（即n值的范围）各为多少？哪个算法更适宜？请说明理由。
正确答案: 2n=1012，n=40
N10=1012，n=16
则对于同样的循环次数n，在这个规模下，第二种算法所花费的代价要大得多。故在这个规模下，第一种算法更适宜。
第6题：
，.
第7题：
n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为（）；若采用邻接表存储，该算法的时间复杂度为（）。
正确答案:O(n2) O(n+e)
第8题：
A、单位
B、对称
C、实
D、正交
第9题：
两个字符串S1和S2的长度分别为m和n，求这两个字符串最大共同子串的时间复杂度为T（m，n），这最优的时间复杂度为（）。
正确答案:O(m*n)
第10题：
数据结构里，在算法时间复杂度中，O（n）表示（）。
- A、常数阶
- B、线性阶
- C、平方阶
- D、立方阶
正确答案:B