算法设计与分析习题集—第1章算法引论(补：倒推法、蛮力法).doc

《算法设计与分析习题集—第1章算法引论(补：倒推法、蛮力法).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、个人收集整理勿做商业用途一、填空题：1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括时间复杂度和空间复杂度。2、多项式的上界为O(nｍ)。3、算法的基本特征:输入、输出、确定性、有限性。4、如何从两个方面评价一个算法的优劣:时间复杂度、空间复杂度。5、计算下面算法的时间复杂度记为：　　Ｏ(ｎ３)　。ﻩfｏr(ｉ=1;i<=n;i＋+）for（j=１;ｊ<=ｎ;ｊ++)　　　　　ﻩ{c[i][j]=０；　　　　　　　　　　　　　　for（k=1;ｋ<＝n；k++）　　　　　　　　　　ﻩc[i]［j]=c［i]［j]+a［i］[k]＊b[ｋ]［ｊ]；　　ﻩ}6、描述算法常用的方法

2、：自然语言、伪代码、程序设计语言、流程图、盒图、PAＤ图。7、算法设计的基本要求:正确性和　可读性。8、计算下面算法的时间复杂度记为：　Ｏ（n2)　。for(i＝1；ｉ＜n;i++)ﻩ　{y＝y+1；　　　　　　　　　　　　ﻩ　ｆor（j＝0；j＜=2ｎ；j++）x＋＋；　　　　}9、计算机求解问题的步骤：问题分析、数学模型建立、算法设计与选择、算法表示、算法分析、算法实现、程序调试、结果整理文档编制。１0、算法是指解决问题的　　　　　　　　　　　　。11、算法由操作、控制结构、数据结构三要素组成。二、简答题:１、按照时间复杂度从低到高排列：O(4n2)、O(ｌoｇｎ)、O(3ｎ）、O(

3、20n)、O(2)、O(ｎ2/３)，O（n!)应该排在哪一位？答：O（２），O(lｏgn）,Ｏ（n２/３)，Ｏ（2０n)，O（４n2),Ｏ(３n)，O(n!）2、什么是算法?算法的特征有哪些?3、给出算法的定义?何谓算法的复杂性？计算下例在最坏情况下的时间复杂性？for（j=1;ｊ<=n;j＋+）fｏr(i=1;i<＝n;i+＋)　　　　　　　　　　ﻩ{c［i］[ｊ］=0;　　　　　　　　个人收集整理勿做商业用途ﻩｆｏｒ(k=1;ｋ<=n；k＋+)　　　　　　　　　　ﻩc[i][ｊ］=c［i］［j]+a［i][k]*b[k][j］;　}4、算法A和算法B解同一问题，设算法Ａ的时间复杂性满

4、足递归方程,算法Ｂ的时间复杂性满足递归方程，若要使得算法Ａ时间复杂性的阶高于算法B时间复杂性的阶,a的最大整数值可取多少?答:分别记算法A和算法B的时间复杂性为和，解相应的递归方程得：　　依题意，要求最大的整数ａ使得〈。显然，当ａ＜=4时,〈；当a＞4时，〈　a<=１6。所以，所求的a的最大整数值为15。5、算法分析的目的？首先,为了对算法的某些特定输入,估算该算法所需的内存空间和运行时间;其次,是为了建立衡量算法优劣的标准，用以比较同一类问题的不同算法。６、算法设计常用的技术?(写５种)　答：　ﻩ①分治法②回溯法ﻩ③贪心法ﻩ④动态规划法ﻩ⑤分治限界法⑥蛮力法⑦倒推法三、算法设计题1、蛮

5、力法：百鸡百钱问题？　　见ｐｐｔ２、倒推法：穿越沙漠问题?　　　　见ｐpt