对接CSP-J/S认证C++算法蓝桥等考导学/一级:入门算法/之一:(1)模拟算法

一、观看PPT教程 

01】算法【02】模拟算法

二、练习题(不清楚回头查看有关PPT)

01】有关算法(algorithm)的描述,错误的是:①算法来自数学领域,在数学领域是指解决某一类问题的公式和思想。
②计算机领域的算法本质是一系列程序指令,用于解决特定的运算和逻辑问题。
③大体上看,数学领域的算法和计算机领域的算有很多相通的地方。
④算法是计算机或数学的专用术语,只能在计算机或数学中应用。
02】有关算法的历史的描述,错误的是:
①算法的概念历史悠久,公元前2500年,古埃及数学家就用到了除法这样的算术算法。
②公元9世纪阿拉伯数学家肯迪则利用基于频率分析的密码学算法破译密码。
③在中国,“算法”即演算法,源自《周髀算经》;“Algorithm”源自9世纪波斯数学家阿尔·花拉子密。
④“算法”原为“algorism”,意思是阿拉伯数字的运算法则,在18世纪演变为“algorithm”。⑤欧几里得算法(辗转相除法)被人们认为是史上第一个算法。
03】一个合格的算法应该具备五个重要的特性,在下面的特性中选出来:
①输入项:一个算法有零个或多个输入,以刻画运算对象的初始情况,所谓零个输入是指算法本身指定了初始条件。
②易懂性:算法务必是大多数人都能看懂。
③有穷性:算法的有穷性是指算法必须能在执行有限个步骤之后终止。
④依据性:算法务必使用已有的数学公式或定理。
⑤可行性:算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤,即每个计算步骤都可以在有限时间内完成(也称之为有效性)。
⑥确切性:算法的每一步骤必须有确切的定义。
⑦输出性:一个算法有一个或多个输出,以反映对输入数据的加工后的结果。没有输出的算法是毫无意义的。
04】一个算法的评价主要从下面五点来考虑,请选出它们:
①正确性,算法的正确性是评价一个算法优劣的重要标准。
②可读性,是指一个算法可供人们阅读的容易程度。
③可调节,根据计算资源调节算法达到最快的计算效率。
④容错性,是指一个算法对不合理输入数据的反应能力和处理能力。
⑤模块化,是指算法能够分解问题,然后用独立的代码完成不同的问题。
⑥空间复杂度,是指算法需要消耗的内存空间。
⑦时间复杂度,是指算法需要的计算工作量。
05】有关时间复杂度的描述,错误的是:
①一般情况下,算法程序中基本操作的执行次数,用时间度量是问题规模n的一个函数f(n)——同样的程序和相同的运行环境,规模n越大,时间一定越长
②时间复杂度是程序暂停的次数。
③随着问题规模n的增大,程序执行的实际的增长情况,简称时间复杂度。
④通常使用大写O表示法来表示算法的时间复杂度,记作 T = O(f(n))。
⑤代码中的基本操作是指最内层循环中的语句。
06】用 T = O(f(n))的形式写出下面代码的时间复杂度。

· 

· 

· 

for(int i = 0; i < n; i++){    cout << i;}

· 

· 

· 

· 

· 

for(int i = 0; i < n; i++){    for(int j =0; j < n; j++{        cout << i * j << endl;    }}

· 

· 

· 

· 

· 

for(int i = 1; i <= n; i++){    for(int j = 1; j <=i ; j++{        cout << i + j << endl;    }}\

07】时间复杂度越低,程序执行效率越快,请从小到大排列下面的时间复杂度:
①  O(n)          :线性
②  O(logn)     :n的自然对数
③  O(n²)         :n的平方
④  O(1)           :与n无关
⑤  O(nlogn)    :n自然对数的n倍
⑥  O(n!)          :n阶乘 
⑦  O(2^n)       :2的n次方
08】用S = O(f(n)表示下面程序的空间复杂度:

· 

· 

· 

· 

int j = 0;for (int i = 0; i < n; i++){    j++;}

· 

· 

· 

· 

int *a = new int(n);for (int i = 0; i < n; i++){    a[i] = i;}

09】有关模拟算法的描述,错误的是:
①模拟是对真实事物或者过程的虚拟,有些问题的描述和解决方法已经很清楚,只需要按照题目描述使用计算机语言一步一步实现即可,这种方法就是计算机解决问题的一种最普遍最直接的方法——模拟法。
②模拟算法是一种特定的算法,是我们依赖计算机的运行速度解决特定问题的方法。
③模拟法适用于问题求解清晰、运算规模较小的问题。如果问题求解的时间复杂度或空间复杂度很大,就要考虑使用有其它更好的解决方案。
10】用模拟法编程解决下“A+B问题”:
输入两个整数 a 和 b,输出 a + b 的和(|a|, |b|≤10000)。
11】编程题:跑道上的锥筒
12】编程题:构建矩阵