資源簡介

3.3簡單算法及其程序實現
一、選擇題
1．在Python語言中，以下簡單數據類型選項中描述錯誤的是( )
A．整數（int）、浮點數（float） B．字符串（str）
C．布爾（bool） D．2.5+2.5的值是整數（int)類型
2．下面不是python特性的是（ ）：
A．免費的 B．簡單易學 C．可移植性好 D．是低級語言
3．關于Python，以下幾種說法不正確的是（ ）。
A．Python是一種高級程序設計語言
B．Python屬于匯編語言，或者說屬于低級語言
C．Python是一種代表簡單主義思想的語言，它具有簡單、免費、開源和可移植等特點
D．Python是一種面向對象的、解釋性計算機語言
4．python語言的特點（ ）。
A．簡單 B．免費、開源 C．可移植性 D．以上都是
5．在算法課上，老師提出了一個問題：有一個農夫帶一條狼、一只羊和一棵白菜過河問題，農夫一次只能帶一樣東西過河，如果留下羊和白菜，羊會吃掉白菜，如果留下羊和狼，狼會吃掉羊，請設計一個方案，讓農夫、狼、羊、白菜順利過河。針對老師的問題，小林所在的學習小組設計了過河方案，步驟如下：
①.農夫先帶羊過河，農夫單獨返回
②.農夫帶狼過河，農夫和羊返回
③.農夫帶白菜過河，農夫單獨返回
④.農夫帶羊過河
由此，小林所在的學習小組得出以下關于算法的結論，正確的是（ ）
A．算法簡單來說是解決某一個問題的方法步驟
B．算法的步驟是有限的
C．算法中的每一個步驟都必須有確切的定義
D．算法必須是可行的
6．韋沐沐同學利用Python軟件編寫“求能被3整除的數”程序，在設計算法環節，使用流程圖描述算法，如右圖所示，其中空白處可以填入的是（ ）
A．A÷3==0 B．A/3==0 C．A\3==0 D．A%3==0
7．算法用Python程序實現，以下代碼中哪處語句存在語法錯誤（ ）
A． B． C． D．
8．經過中國國家登山隊的測量，2020年12月8日，中尼兩國共同宣布了珠穆朗瑪峰的最新高度為海拔8848．86米。現有一張白紙的厚度大約是0．08毫米，對折一次，厚度變0．16毫米，再對折一次，厚度變為0．32毫米，……，每對折一次，其厚度均變為對折前的兩倍，假設這張紙足夠大，可以對折任意次，那么這張紙至少對折多少次后，其厚度將超過珠穆朗瑪峰的高度？以下是求解以上問題的程序片段，請你補全代碼：
請選擇適當的代碼填入程序①處。（ ）
A．while B．for C．output D．input
9．下列與數學表達式對應的python表達式，正確的是（ ）。
A．( - b + math. sqrt (b * b – 4 * a * c)) /a * a
B．- b + math. sqrt (b * b – 4 * a * c) /2*a
C．( -b + math. sqrt (b * 2 – 4 * a * c)) /(2 * a)
D．( -b + math. sqrt ( b * b – 4 * a * c)) / (2 * a)
二、操作題
10．某加密算法的加密部分Python程序段如下：
def encrypt(msg,key):
result = ""
size = len(msg)
for i in range(0,size):
result = result + msg[(i - key) % size]
return result
msg = input("請輸入明文：")
key = int(input("請輸入密鑰："))
re = _________
print(re)
(1)請在劃線處補充代碼。
(2)如果輸入的msg為“cdef”，key為3，那么輸出的結果為______。
(3)這種加密機制稱為____(選填字母：A．置換密碼；B．換位密碼；C．簡單異或密碼)。
11．奇偶校驗碼是一種增加二進制傳輸系統可靠性的簡單且廣泛采用的方法，該方法通過增加一個校驗位使得傳輸的二進制碼中“1”的個數恒為奇數或偶數，因此該校驗碼也分為“奇校驗”和“偶校驗”。“奇校驗”的原理：在發送端發送的每個字節二進制碼后增加一個校驗位（0或1），使得“1”的個數為奇數；接收端接收并統計每個字節及其校驗位中“1”的個數，若為偶數，則意味著傳輸過程中存在差錯。例如：
接收到的每個字節及校驗碼 1的個數 傳輸正誤
100101001 4 錯誤
011010101 5 正確
101011010 5 正確
根據以上原理，小強編寫了一個Python程序，對接收到的9位二進制編碼進行“奇校驗”，判斷其傳輸的正誤，若判斷正確則將前一個字節的編碼轉成十六進制并輸出。
請回答下列問題：
（1）若接收到的二進制碼為“101011011”，傳輸過程__________（選填：是/否）存在差錯。
（2）實現上述功能的Python程序如下，請在劃線處填入合適的代碼。
s=input("請輸入9位二進制編碼:")
code={10:"A",11:"B",12:"C",13:"D",14:"E",15:"F"}
k=0;p=0;ans=“”
for i in s:#統計9位二進制編碼中“1”的個數
k=k+int(i)
if ____:
print("傳輸錯誤!")
else:
print("傳輸正確!")
for j in range(0,8,4):
p=int(s[j:j+4],2)
# int(x,[base]):將x（字符串或者數字）按照base進制轉換成整數
if 0<=p<=9:
ans=ans+str(p)
else：
ans=___
print("字節編碼用十六進制表示:"，___
12．小吳研究插入排序算法，若對無序數列5，2，9，5，3，利用傳統的簡單插入排序進行升序排序，其方法如下：
首先將5取出，得到序列5；
第二步將2取出，插入序列得到2，5；
第三步將9取出，插入后得到2，5，9；
第四步將5取出，插入后得到2，5，5，9；
第五步將3取出，插入后得到2，3，5，5，9，排序完成。
小吳對這種插入排序進行了一些改進，將無序數列存入a數組中，將排序后的數據存入b數組中，同時保證b數組不存在重復的數字。對于重復出現的數字，用cnt數組記錄重復個數。例如無序數列8、6、7、4、4、9、1、9、9、8，a(1)～a(10)存儲原數據，b(1)～b(6)存儲排序后的不重復數據，cnt(1)～cnt(6)存儲每個數字重復的個數，如圖a所示。
數組/下標 1 2 3 4 5 6
b 1 4 6 7 8 9
cnt 1 2 1 1 2 3
圖a
程序運行后，自動隨機生成原數組并顯示在列表框List1中，點擊按鈕“開始”后，生成升序排序數組并顯示在列表框List2中，程序運行界面如圖b所示。
圖b
請回答下列問題。
（1）若要在窗體載入后讓窗體標題顯示“排序改進算法”，則下列操作可行的是_______（單選，填字母。）
A．直接將窗體屬性欄中的“Text”屬性值修改為“排序改進算法”
B．在程序的Form_Load()事件中寫上代碼 Form1.Caption =“排序改進算法”
C．在程序的Command1_Click()事件中寫上代碼Form1.Caption =“排序改進算法”
（2）請完成程序中的填空。
（3）程序中加框處存在錯誤，請改正。
Const n = 10
Dim a(0 To 100) As Integer, b(0 To 100) As Integer, cnt(1 To 100) As Integer
Dim Ln As Integer, pos As Integer 'Ln表示b數組的長度
Function search(key As Integer)
Dim i As Integer
For i = 1 To Ln
If b(i) >= key Then Exit For
Next i
search = i
End Function
Private Sub Command1_Click()
Dim i As Integer, j As Integer
Ln = 0
For i = 1 To n
pos = ________
If b(pos) <> a(i) Then
Ln = Ln + 1
j = Ln
Do While j > pos
b(j) = b(j - 1)
__________
j = j - 1
Loop
b(j) = a(i)
cnt(pos) = 1
Else
cnt(pos) = 1 _________
End If
Next i
For i = 1 To Ln
For j = 1 To cnt(i)
List2.AddItem Str(b(i))
Next j
Next i
End Sub
Private Sub Form_Load()
For i = 1 To n
a(i) = Rnd() * 10 + 1
List1.AddItem Str(a(i))
Next i
End Sub
三、填空題
13．簡單地說，算法就是解決問題的___和___。
14．算法是指在有限步驟內求解某一問題所使用的一組定義明確的規則。某一個算法的描述如下：
①輸入兩個數A，B；
②如果A大于B，則將A的值賦給C，B的值賦給A，C的值賦給B；
③如果A不大于B，則A、B的值保持不變；
④輸出A，B；
⑤結束
（1）以上算法的描述屬于哪一種：__________________；
（2）以上算法第④步用Python語言實現，可以寫為：___________________；
（3）如果A的值是5，B的值是3，則執行完算法后，A的值是：________。
試卷第2頁，共3頁
參考答案
1．D
【詳解】
本題主要考查Python數據類型。整數（int）、浮點數（float）、字符串（str）、布爾（bool），2.5+2.5=5.0，值是浮點數（float）類型，故本題選D選項。
2．D
【詳解】
本題主要考查Python的特性。Python特性有：免費的、簡單易學、可移植性好、是高級語言，故本題選D選項。
3．B
【詳解】
本題主要考查Python程序設計語言。Python是一種高級程序設計語言；Python是一種代表簡單主義思想的語言，它具有簡單、免費、開源和可移植等特點；Python是一種面向對象的、解釋性計算機語言，故本題選B選項。
4．D
【詳解】
本題考查的是python語言的特點。Python語言的三個特點是語法簡單（函數式語言與面向對象語言的結合）、使用直接（大量豐富的庫）、開發周期短（代碼量小）。故選項D正確。
5．ABCD
【詳解】
本題考查算法的特征。算法的特征有步驟的有限性，確切性（算法的每一步驟必須有確切的定義），輸入性（一個算法有0個或多個輸入,以刻畫運算對象的初始情況,所謂0個輸入是指算法本身定出了初始條件），輸出項 (一個算法有一個或多個輸出,以反映對輸入數據加工后的結果。沒有輸出的算法是毫無意義的），可行性 (算法中執行的任何計算步驟都是可以被分解為基本的可執行的操作步驟)。因此選項中正確的是ABCD。
6．D
【詳解】
本題考查的是流程圖及Python表達式相關知識。能被3整除的數即除3的余數為0，在Python中%表示求余，故本題應選D。
7．D
【詳解】
本題考查的是Python程序調試。雙分支IF語句。if (條件)后面要加冒號，else后面也要加冒號。故標號4中存在語法錯誤。
8．A
【詳解】
本題考查的是Python的while循環。while語句格式：
當表達式的值為真時，執行循環體語句；當表達式值為假時，退出循環，執行循環體外的下一條語句（即while后面沒有縮進的第一條語句）。當高度h小于珠穆朗瑪峰的高度height，則繼續對折，故本題應選A。
9．D
【詳解】
本題考查的是Python表達式。sqrt（）求平方根，乘法運算符為“*”，除法為“/”，嵌套函數均使用小括號。表示為( -b + math. sqrt ( b * b – 4 * a * c)) / (2 * a)。
10．encrypt(msg,key) defc A
【詳解】
本題主要考查Python程序的綜合應用。①encrypt(msg,key)函數根據輸入的明文和密鑰，返回加密后的結果，此處將加密后的結果返回給變量re，故此處填encrypt(msg,key)。②將ms="cdef"，key=3代入程序，輸出結果是defc。③置換密碼是根據一定的規則重新排列明文，以便打破明文的結構特性。置換密碼的特點是保持明文的 所有字符不變，只是利用置換打亂了明文字符的位置和次序。也就是說，改變了明文的結構，不改變明文的內容，故選A選項。
11．是 k%2==0或(k+1)%2==1或(k-1)%2==1 ans+code[p] ans
【詳解】
本題主要考查Python程序的執行與調試。①若接收到的二進制碼為“101011011”，1的個數有6個，則傳輸過程存在差錯。②變量k統計1的個數，若k是偶數則表明傳輸錯誤，否則傳輸正確，故此處填k%2==0或(k+1)%2==1或(k-1)%2==1。③如果p是1~9之間的數字，則直接將p拼接到ans中，否則從字典code中取對應的字母，故此處填ans+code[p]。④變量ans保存轉換后的十六進制，故此處填ans。
12．B search(a(i)) cnt(j)=cnt(j-i) cnt(pos)=cnt(pos)+1
【詳解】
本題主要考查VB程序排序算法。①題干要求在窗體標題顯示“排序改進算法”，故在程序的Form_Load()事件中寫上代碼 Form1.Caption =“排序改進算法”，故本題選B選項。②search()函數是按升序尋找關鍵字key在數組b中的位置i，找到后返回位置i，此處通過for循環尋找數組a中每一個元素在數組b中的位置，找到后將其賦給變量pos，故此處填search(a(i))。③此處while循環是實現移動數組b中的元素（當關鍵字比數組b中位置j的值小時，需要后移，即j-1處的值移到j處），故b(j) = b(j - 1)，cnt(j)=cnt(j-i)，同時j遞減，在位置j處插入數據a(i)，故此處填cnt(j)=cnt(j-i)。④此處是執行if條件結構的else部分，即pos位置處出現了重復值，故cnt(pos)需要遞增，故此處應改為cnt(pos)=cnt(pos)+1。
13．方法 步驟
【詳解】
本題主要考查算法的概念。算法（Algorithm）是指解題方案的準確而完整的描述，是一系列解決問題的清晰指令，算法代表著用系統的方法描述解決問題的策略機制。簡單地說，算法就是解決問題的方法和步驟。
14．自然語言描述 print(A,B) 3
【詳解】
本題主要考查算法及其實現。①以上算法的描述屬于自然語言描述。②算法第④步用Python語言實現，可以寫為print(A,B)（用輸出函數print()）。③如果A大于B，則將A的值賦給C，B的值賦給A，C的值賦給B，即實現A與B的交換，A的值是5，B的值是3，故執行完算法后，A的值是3。
答案第1頁，共2頁
答案第1頁，共2頁

展開更多......

收起↑