2.1算法的概念及描述　通关练习（含答案）

2.1算法的概念及描述
一、选择题
1．算法是指在有限的步骤内解决某一问题的确切过程。以下关于算法的描述中，错的是（ ）
A．算法必须有输入，也必须有输出，而且可以有多个输入输出
B．任何复杂的算法最终都可以用顺序、分支、循环结构来实现
C．《九章算术》中用“更相减损术”求最大公约数的记载属于算法的自然语言描述
D．同一问题选用不同的算法执行效率可能会有很大差别
2．某算法的部分流程图如图所示。
执行这部分流程，若依次输入2,-3,5,1,2,-1,-8,3,4,0，则输出变量m的值为（ ）
A．5 B．6 C．7 D．8
3．观察流程图，下列关于算法特征表述错误的是（ ）
A．算法可以没有数据输入
B．算法必须至少有一个输出
C．该流程图符合算法的有穷性特征
D．该流程图中s＝s＋1体现了算法的确定性
4．下列使用伪代码描述的算法中，能够完成数a 和数b 交换的是（ ）
A．a←a+b，b←a-b，a←a-b B．a←b，b←a
C．t←a，b←t，a←b D．a←a*b，a←a/b，b←a/b
5．某算法的部分流程图如图所示。执行这部分流程后，输出ｓ的值是（ ）
A．1101 B．0010
C．1111 D．1110
6．算法的空间复杂度是指（ ）。
A．算法程序的长度 B．算法程序中的指令条数
C．算法程序所占的存储空间 D．算法执行过程中所需要的存储空间
7．“通过输出变量c的值，判断n是否为质数（除了1和它本身不能被其他数整除的数）”的主要算法流程图如图所示，关于此流程图说法错误的是（ ）
A．输入6，算法结束后，输出c的值为3
B．算法结束后，若c>1则n不是质数
C．将i<=n-1改为i<=sqr(n)后，依然能判断n是否是质数
D．该算法流程图不能判断2是否为质数
8．某算法的部分流程图如图所示。输入n的值为20，执行这部分流程后，输出k的值为（ ）
A．0 B．1 C．2 D．5
9．某算法的部分流程图如图所示，执行这部分流程后，输出 s 的值为（ ）
A．3 B．4 C．15 D．19
10．下列关于算法特征的叙述，正确的是（ ）
A．算法所包含的步骤可以是无穷的 B．算法每一步骤必须确切地定义
C．一个算法可以没有输出 D．算法只能用Visual Basic来实现
11．下列关于算法描述方式的叙述正确的选项是（ ）
①自然语言； ②流程图； ③伪代码； ④汇编语言
A．①②③ B．①②④ C．①③④ D．②③④
12．某算法的部分流程图如图所示。执行这部分流程，若输入s的值为“picture”，则输出的c、i值分别为（ ）
A．"c"，3 B．"e"，4 C．"t"，3 D．"t"，4
13．某算法用伪代码描述如下。
输入两个互不相等的自然数A，BIf A关于上述算法，下列说法正确的是（　　）
A．不符合“可行性”特征 B．无法用流程图来描述
C．运用了循环结构的控制转移 D．实现从大到小输出两个自然数
14．流程图的符号中，平行四边形框是（ ）
A．连接圈 B．起止框 C．输入/输出框 D．处理框
15．针对某一问题的一系列具有精确定义的有限的操作步骤称为（ ）
A．程序 B．指令 C．算法 D．软件
16．某算法的部分流程图如图所示。执行这部分流程，若输入 i 的值为5，则输出 r 的值为（ ）
A．11 B．9 C．7 D．5
17．有27个砝码，外观一模一样，其中有一个异常砝码重0.95g，其他砝码重1g。有一个只能分清轻重的天平，请问最少需要使用（ ）次天平能找出那个重0.95g的砝码。
A．2 B．3 C．4 D．5
18．有流程图如下图所示，其功能是将键盘输入的数进行相加，当输入的数为0时输出它们的和，则图中虚线部分的内容是( )
A． B．
C． D．
19．i=3:s=1/(i-3) 无法执行，原因是它违反了算法特征中的（ ）
A．有穷性 B．唯一性 C．可行性 D．确定性
20．算法是解决问题的方法和步骤，它的每一步都有确切的含义。这体现了算法的（ ）
A．输出 B．可行性 C．确定性 D．有穷性
二、简答题
21．思考高楼的自动电梯在运行时需要考虑哪些方面（例如方便乘客，节约能源等），请为自动电梯设计一个适宜的算法。
三、操作题
22．某种字符加密方法描述如下:
①将明文字符串s中的每个字母字符根据它所在该字符串的位置，往后移动相应的位置，并转化为对应的小写或大写字母(例如:大写字母A往后移动5位变成F，转化成小写字母得到f；小写字母y往后移动8位得到g，转化成大写字母得到G)，非字母字符不处理，得到新串ss。
②将①得到的新串ss平均切割成两部分，若ss的长度n为奇数，则第一部分长度为n//2+1，第二部分长度为n//2。再将后面一段字母依次逐个插入前一段字符后边，组成一段密文。
例如“Good.Luck!”生成密文过程如下:
①明文字符串s移位和大小写转换过程:
下标位置 1 2 3 4 5 6 7 8 9 10
原始字符 G o o d . L u c k ！
向后移动i位 H q r h . R b k t ！
大小写转换 h Q R H . r B K T ！
②将①得到的密文ss平均切割成两部分。
例如将上述①得到的字符串中6~10位置的字符依次逐个连接在1~5字符后面，生成密文如图a所示:
图a
（1）若有一个待加密字符为“Python!”，根据上述加密规则，加密后的密文是_
（2）已知采用上述加密方法得到的密文是“iTCDS!”，反推出明文是___。
四、判断题
23．在用流程图描述算法时输入输出框的内容与形状都不相同。 （_____）
24．算法就是解决问题的方法和步骤。 （_____）
25．算法必须有输出。 （_____）
26．算法中执行的任何计算步骤都可以被分解为基本的可执行的操作步骤。（________）
27．算法有至少有一个输入，不一定有输出。 （____）
五、填空题
28．用智能电饭煲烧饭时，在微处理器的控制下，当饭烧熟时，智能电饭煲会自动停止高热烧饭，转为低热保温。这是因为锅底的温度传感器每隔一定时间（比如200毫秒）会将温度数据传送给微处理器，如果温度低于103℃，则继续高热烧板，一旦发现温度达到103℃（包含103℃，此时锅中水被蒸发完），微处理器就会控制继电器释放触点，让电饭煲停止烧饭，转入低热保温模式。根据以上描述回答下列问题：
（1）右图所示的流程图描述了某个时刻智能电饭煲根据输入的温度数据进行判断、处理的算法，则在流程图中①标记处应该填写_______。
（2）在这个系统中温度传感器所起的作用是________。
29．简单地说，算法就是解决问题的___和___。
30．以下是求解2个正整数a,b的最小公倍数的算法自然语言描述，请在括号内填写正确的数字。
第1步：输入正整数a和b；
第2步：如果a第3步：n=1；
第4步：a=a*n；
第5步：如果a不能整除b，则n=n+1，跳到第（_____）步；
第6步：输出结果a。
31．（_____）是对解题过程的精确描述，且需要使用自然语言或者流程图或者伪代码将其表示出来。
32．素数的定义是：大于1的自然数中，除了能被1和它本身整除以下，没有别的因子的数。以下算法用于判断一个数是否为素数，根据算法描述，回答问题。
①输入一个数n（n>2）
②i=2
③n能被i整除吗？
若能，输出“不是素数”，程序结束；
若不能，i=i+1；
④判断i>吗？
若是，输出 a ；
若不是，转为执行步骤③。
（1）“n能被i整除”用VB表达式表示为_______；
（2）a处应填入_______。
33．流程图是用辗转相除的方法求输入的两个自然数的最大公约数算法。例如输入6、4，用6/4余2，4/2余0,则6和4的最大公约数是2。流程图中划线处部分应填__________。
34．输入123，以下流程图描述的算法，执行结果是_____________。
35．以下流程图描述的算法，执行结果是_______。
36．以下流程图描述的算法，执行结果是_______。
37．用流程图描述算法中，棱形图形符号(◇)表示的功能是 。
参考答案
1．A
【详解】
本题考查的是算法特征。算法可以没有输入，但必须有输出，而且可以有多个输入输出。故选项A的说法错误。本题应选A。
2．D
【详解】
本题考查的是流程图的识读。该流程图的功能是求连续序列和的最大值，最大值为5+1+2=8，故选项D正确。
3．C
【详解】
本题考查的是算法特征。算法的五大特征：有穷性、确定性、能行性（可行性）、有 0 个或多个输入、有一个或多个输出。该流程图中初始值i=0，循环体中没有改变i的值，i<3一直成立，一直执行s=s+1，不符合算法的有穷性的特征。故本题应选C。
4．A
【详解】
本题考查的是算法。可用代入法a=2，b=3，带入选项中验证。选项A，a=2+3=5，b=5-3=2，a=5-2=3。故选项A正确。
5．A
【详解】
本题考查的是流程图的识读。执行过程如下：
x=13,y=8,x=13>0,Y,13>=8,Y,x=13-8=5,s=1,y=8\2=4
x=5,y=4,x=5>0,Y,5>=4,Y,x=5-4=1,s=11,y=4\2=2
x=1,y=2,x=1>0,Y,1>=2,N, s=110,y=2\2=1
x=1,y=1,1>0,Y,1>=1,Y,x=1-1=0,s=1101,y=1\2=0
x=0,y=0,1>0,N,输出s为1101。选项A正确。
6．D
【详解】
本题考查的是算法相关知识。算法的空间复杂度是指算法执行过程中所需要的存储空间。故本题应选D。
7．D
【详解】
本题考查的是流程图的识读。当n为2时，判断条件不成立，走N支线，输出c=1。即能证明n不存在因子，故能判断2为质数。故选项D符合题意。
8．C
【详解】
本题考查的算法的流程图表示后，数据执行的变化过程。
9．D
【详解】
本题考查的是流程图的分析。
详细过程如下：
s=0 k=1 i=1
1<=5 Y k=1*1=1 s=0+1=1 i=1+2=3
3<=5 Y k=1*3=3 s=1+3=4 i=3+2=5
5<=5 Y k=3*5=15 s=4+15=19 i=5+2=7
7<=5 N 输出s=19
10．B
【详解】
本题考查的是算法特征。算法具有有穷性，故选项A说法错误；算法每一步骤必须确切地定义，选项B说法正确；算法至少要有一个输出，故选项C说法错误；算法可以用VB来实现，也可以用其它程序语言实现，故选项D说法错误。
11．A
【详解】
本题考查的是算法相关知识。算法描述有：自然语言、流程图、伪代码。故本题应选A。
12．A
【详解】
本题考查的是流程图识读。由c=mid(s,1,1)、j=mid(s,i+1,1)可知，对输入的字符逐一跟前一个字符比较，如果大于大于前一个字符，则输出该字符c及i。若输入s的值为“picture”，“p”>“i”>“c”<“t”，所以当取到字符c为“c”时，跳出循环，此时i=3。故选项A正确。
13．D
【详解】
本题考查的是算法相关知识。该算法的计算步骤都可以被分解为基本的可执行的操作步骤，符合可行性特征，故选项A说法错误；算法可以用伪代码也可以用流程图来描述，故选项B说法错误；该算法运用了选择结构，故选项C说法错误；由算法可知，如果A14．C
【详解】
本题考查的是流程图相关知识。在流程图的符号中，圆角矩形是起止框，矩形是处理框，平行四边形是输入/输出框，菱形是判断框。故选项C正确。
15．C
【详解】
本题考查的是算法。针对某一问题的一系列具有精确定义的有限的操作步骤称为算法。程序就是一组计算机能识别和执行的指令。计算机指令就是指挥机器工作的指示和命令，程序就是一系列按一定顺序排列的指令，执行程序的过程就是计算机的工作过程。软件是一系列按照特定顺序组织的计算机数据和指令的集合。故应选C。
16．B
【详解】
本题考查的是流程图识读。初始i=5。
i<=9成立，n=i*i=25，a=n mod 10=5，b=n\10=2，a+b=7<>5，执行i=i+2=7；
i<=9成立，n=i*i=49，a=n mod 10=9，b=n\10=4，a+b=13<>7，执行i=i+2=9；
i<=9成立，n=i*i=81，a=n mod 10=1，b=n\10=8，a+b=9，执行r=i=9，i=i=2=11；
i<=9不成立，输出r=9，故选项B正确。
17．B
【详解】
本题考查的是算法。自然语言描述如下：
将27个砝码分为三堆，每堆9个，任意取两堆，如果相等，那么轻的那个在第三堆里，如果不相等，那么重0.95g的砝码就在较轻的一堆里；接着把较轻的一堆中的9个砝码再分为三份，每份3个，如此类推，三次就可以找到重0.95g的砝码。
18．D
【详解】
本题考查的是流程图识读。当输入的数为0时输出它们的和，结合输出变量s的流程线上的N，可知虚线部分应为a<>0的判断框。菱形表示判断，故应选D。
19．C
【详解】
本题考查的是算法特征。i=3:s=1/(i-3) ，除数为0，它违反了算法特征中的可行性，故应选项C。
20．C
【详解】
本题考查的是算法特征。算法的五大特征：有穷性、确定性、能行性（可行性）、有 0 个或多个输入、有一个或多个输出。每一步都有确切的含义这体现了算法的确定性，故选项C正确。
21．自动电梯能实现自动升降，主要是它安装了微型电脑控制器。微型电脑控制器主要任务如下：
A.要让乘客方便，尽可能减少等待。
B.要节约能源，尽可能减少空开里程和往返次数。
我们可以从上述两个方向思考，设计适宜的算法。
一个参考算法如下：
① 乘客进入电梯房，按目标楼层键并关门启动运行；
② 控制器根据事先存储在电脑中的指标判断人员是否超载？若超载发出提示信息，下去若干人，返回第①步；若未超载，执行下一步；
③关闭电梯门，根据目标楼层键判断上升或下降；
④ 随时判断是否有人按下同方向的请求键。若是，则运行到该层停下，开门上下人，并按键启动；若没有新的请求，则到达既定目标层后，停止；
⑤接受新的请求，转而执行①；否则，停止。
【详解】
本题考查的知识点是Python算法的设计。
自动电梯能实现自动升降，主要是它安装了微型电脑控制器。微型电脑控制器主要任务如下：A.要让乘客方便，尽可能减少等待。B.要节约能源，尽可能减少空开里程和往返次数。我们可以从上述两个方向思考，设计适宜的算法。
一个参考算法如下：① 乘客进入电梯房，按目标楼层键并关门启动运行；② 控制器根据事先存储在电脑中的指标判断人员是否超载？若超载发出提示信息，下去若干人，返回第①步；若未超载，执行下一步；③关闭电梯门，根据目标楼层键判断上升或下降；④ 随时判断是否有人按下同方向的请求键。若是，则运行到该层停下，开门上下人，并按键启动；若没有新的请求，则到达既定目标层后，停止；⑤接受新的请求，转而执行①；否则，停止。
22．qTATW!L Happy!
【详解】
本题主要考查算法描述及其实现。①若有一个待加密字符为“Python!”，根据上述加密规则，得到下表：
下标位置 1 2 3 4 5 6 7
原始字符 P y t h o n !
向后移动i位 Q a w l t t !
大小写转换 q A W L T T !
将得到的字符切割成两部分，将后面一段字母依次逐个插入前一段字符后边，组成一段密文，如下文：
下标位置 1 2 3 4 5 6 7
最终密文 q T A T W ! L
根据上述加密规则，加密后的密文是qTATW!L
②已知采用上述加密方法得到的密文是“iTCDS!”，由下表可以反推出明文是Happy!。
23．错误
【详解】
本题考查的是流程图相关知识。在用流程图描述算法时输入输出框都是用平行四边形来表示。故题干中的说法是错误的。
24．对
【详解】
本题主要考查算法的概念。算法就是解决问题的方法和步骤，表述正确。
25．对
【详解】
本题主要考查算法的特点。算法可以没有输入，但至少要有一个输出，表述正确。
26．对
【详解】
本题考查算法计算步骤
算法中执行的任何计算步骤都可以被分解为基本的可执行的操作步骤。表述正确
27．错
【详解】
本题考查的是算法特征。算法的五大特征：有穷性、确定性、能行性（可行性）、有 0 个或多个输入、有一个或多个输出。故题干中的说法是错误的。
28．x<103℃ 输入锅底当前的温度值x
【详解】
本题考查的是流程图相关知识。（1）依据题干“一旦发现温度达到103℃（包含103℃，此时锅中水被蒸发完），微处理器就会控制继电器释放触点，让电饭煲停止烧饭，转入低热保温模式。”，故①标记处应该填写x<103℃。（2）在这个系统中温度传感器所起的作用是：输入锅底当前的温度值x。
29．方法 步骤
【详解】
本题主要考查算法的概念。算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。简单地说，算法就是解决问题的方法和步骤。
30．4
【详解】
本题主要考查算法的描述。分析算法描述的步骤可知，如果a不能整除b，则n=n+1，跳到a=a*n，即第4步，继续循环判断。
31．算法
【详解】
本题主要考查算法的描述。算法是对解题过程的精确描述，且需要使用自然语言或者流程图或者伪代码将其表示出来。
32．n mod i=0 是素数
【详解】
本题主要考查算法描述。①“n能被i整除”用VB表达式表示为n mod i=0（取余值为0，则n能被i整除）。②由题干描述，知a处应填入是素数。
33．r=0
【详解】
本题考查的是流程图相关知识。辗转相除法，它的具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。故划线处部分应填：r=0 。
34．Yes
【详解】
本题考查流程图相关知识。n=123，n=int(n/10) mod 10=2，n=n mod 10=2，int（n/2）=n/2成立，故最后为YES。
35．0
【详解】
本题考查的知识点是流程图的识读。
方法一：按照流程图的执行顺序，
初始值a（1）=1，a（2）=2，a（3）=3，a（4）=4，s=0，i=1，
执行i<4语句，满足此关系表达式，故执行i=i+1语句，即i=2，并执行s=s*a（2）语句，即s=0；
执行i<4语句，满足此关系表达式，故执行i=i+1语句，即i=3，并执行s=s*a（3）语句，即s=0；
执行i<4语句，满足此关系表达式，故执行i=i+1语句，即i=4，并执行s=s*a（4）语句，即s=0；
执行i<4语句，不满足此关系表达式，故输出s语句，即s=0；
故此流程图的执行结果是0。
方法二：根据s=0，s=s*a（2）语句，可以知道s的值一直是0，所以可以直接得出此流程图的执行结果是0。
故本题的答案是0。
36．@@@@
【详解】
本题考查的知识点是程序的识读。
初始值t=0，n=1，执行输出“@@@@”语句，再执行判断n>2表达式，不符合该条件表达式，故执行输出“####”，再执行n=n+1语句，即n=2，再执行判断t=1表达式，不符合该条件表达式，故执行判断n>2表达式，不符合该条件表达式，故执行输出“####”，再执行n=n+1语句，即n=3，再执行判断t=1表达式，不符合该条件表达式，故执行判断n>2表达式，符合该条件表达式，故执行输出“”， 再执行t=1语句，再执行n=n+1语句，即n=4;再执行判断t=1表达式，符合该条件表达式，故程序结束。
所以流程图的执行结果为：@@@@########。
故答案为@@@@########。
37．判断
【详解】
本题考查的是流程图相关知识。用流程图描述算法中，圆角矩形表示开始/结束框，平行四边形表示输入输出框，矩形表示处理框，棱形表示的功能是判断。