内容发布更新时间 : 2025/1/9 16:37:17星期一 下面是文章的全部内容请认真阅读。

如果对你有帮助，请下载使用！

一、填空题：

1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括时间复杂度和空间复杂度。 2、多项式A(n)?amnm??a1n?a0的上界为O(nm)。

3、算法的基本特征：输入、输出、确定性、有限性。

4、如何从两个方面评价一个算法的优劣：时间复杂度、空间复杂度。 5、计算下面算法的时间复杂度记为：O(n3) 。

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

{c[i][j]=0; for(k=1;k<=n;k++) c[i][j]= c[i][j]+a[i][k]*b[k][j]; }

6、描述算法常用的方法：自然语言、伪代码、程序设计语言、流程图、盒图、PAD图。 7、算法设计的基本要求：正确性 和 可读性。 8、计算下面算法的时间复杂度记为：O(n2) 。

for（i＝1；i

{ y=y+1; for（j＝0；j <=2n；j++ ） x＋＋； }

9、计算机求解问题的步骤：问题分析、数学模型建立、算法设计与选择、算法表示、算法分析、算法实现、程序调试、结果整理文档编制。 10、算法是指解决问题的。

11、算法由操作、控制结构、数据结构三要素组成。 二、简答题：

1、按照时间复杂度从低到高排列：O( 4n2)、O( logn)、O( 3n)、O( 20n)、O( 2)、O( n2/3), O( n!)应该排在哪一位？

答：O( 2)，O( logn)，O( n2/3)，O( 20n)，O( 4n2)，O( 3n)，O( n!) 2、什么是算法？算法的特征有哪些？ 3、给出算法的定义？何谓算法的复杂性？

计算下例在最坏情况下的时间复杂性？for(j=1;j<=n;j++)

for(i=1;i<=n;i++)

{c[i][j]=0; for(k=1;k<=n;k++) c[i][j]= c[i][j]+a[i][k]*b[k][j]; }

4、算法A和算法B解同一问题，设算法A的时间复杂性满足递归方程

1

如果对你有帮助，请下载使用！

?T(n)?1 , n?1 ，算法?T(n)?4T(n/2)?n , n?1?B的时间复杂性满足递归方程

?T(n)?1 , n?1 ，若要使得算法A时间复杂性的阶高于算法B时间复杂?T(n)?aT(n/4)?n , n?1?性的阶，a的最大整数值可取多少？

答：分别记算法A和算法B的时间复杂性为TA(n)和TB(n)，解相应的递归方程得：

依题意，要求最大的整数a使得TB(n)〈TA(n)。显然，当a<=4时，TB(n)〈TA(n)；

当a>4时，TB(n)〈TA(n)?log4a?2?a<42=16。

所以，所求的a的最大整数值为15。

5、算法分析的目的？

首先,为了对算法的某些特定输入，估算该算法所需的内存空间和运行时间； 其次,是为了建立衡量算法优劣的标准，用以比较同一类问题的不同算法。 6、算法设计常用的技术？（写５种） 答： ①分治法 ②回溯法 ③贪心法 ④动态规划法 ⑤分治限界法 ⑥蛮力法 ⑦倒推法 三、算法设计题

1、蛮力法：百鸡百钱问题？ 见ｐｐｔ

2、倒推法：穿越沙漠问题？ 见ｐｐｔ

2