資源簡介

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．判斷
【詳解】
本題考查的是流程圖相關知識。用流程圖描述算法中，圓角矩形表示開始/結束框，平行四邊形表示輸入輸出框，矩形表示處理框，棱形表示的功能是判斷。