資源簡(jiǎn)介

2023-2024學(xué)年高二上學(xué)期浙教版(2019)選修一5.3數(shù)據(jù)排序
一、選擇題
1．下列哪種算法不屬于搜索算法（ ）
A．暴力枚舉 B．順序枚舉 C．二分查找 D．堆排序
2．某冒泡排序算法的VB程序段如下：
i=6: flag =1: cnt=0
Do While i >=2 And flag=1
flag=0: cnt= cnt +1
For j =
If a(j)>a(j-1)Then
k=a(j):a(j)=a(j-1):a(j-1)=k
flag= 1
End If
Next j
i=i-1
Loop
數(shù)組元素a(1)到a(6)的值依次為“79，13，93，55，29，17”，執(zhí)行該程序段后，cnt的值為3，數(shù)組元素實(shí)現(xiàn)有序，則方框中的代碼是（ ）
A．2 To i-1 B．2 To i
C．6 To 7-i Step-1 D．6 To 8-i Step -1
3．以下哪種排序算法不是比較排序（ ）
A．歸并排序 B．快速排序 C．計(jì)數(shù)排序 D．堆排序
4．歸并排序是一種基于分治思想的排序算法，它的基本思想是將兩個(gè)有序的子序列合并成一個(gè)有序序列。歸并排序的時(shí)間復(fù)雜度是（ ）
A．O(n) B．O(n^2) C．O(n^3) D．O(nlogn)
5．以下哪個(gè)算法不是時(shí)間復(fù)雜度為O(n^2)的排序算法（ ）
A．冒泡排序 B．插入排序 C．選擇排序 D．快速排序
6．一次運(yùn)動(dòng)會(huì)上，某組6位選手的百米成績(jī)(單位：秒)分別是“14.1、12.3、11.2、14.8、13.9、11.0”，若使用選擇排序法將該組的成績(jī)按第一名、第二名、第三名……的順序排序，則第一次交換數(shù)據(jù)后的順序是（ ）
A．14.8 14.1 12.3 11.2 13.9 11.0
B．11.0 12.3 11.2 14.8 13.9 14.1
C．14.8 12.3 11.2 14.1 13.9 11.0
D．11.0 14.1 12.3 11.2 14.8 13.9
7．某市組織了一次我心目中最喜愛(ài)的球隊(duì)的評(píng)比活動(dòng)，6個(gè)球隊(duì)網(wǎng)上投票數(shù)為201、287、501、189、397、295，若采用冒泡排序算法對(duì)其進(jìn)行從大到小排序，則第三遍加工后的結(jié)果是( )
原始數(shù)據(jù) 201 287 501 189 397 295
第一遍 501 201 287 397 189 295
第二遍 501 397 201 287 295 189
第三遍
A．501 397 295 287 201 189
B．501 397 201 287 295 189
C．501 397 295 201 189 287
D．501 397 295 201 287 189
8．在實(shí)現(xiàn)排序算法時(shí)，以下哪種算法的時(shí)間復(fù)雜度最低（ ）
A．冒泡排序 B．選擇排序 C．插入排序 D．快速排序
9．對(duì)一列數(shù)據(jù)[40、7、37、27、18、63、49、15]按升序排列，使用冒泡排序方法，第一、二輪需進(jìn)行相鄰列表元素交換的次數(shù)一共為（ ）
A．4次 B．5次 C．9次 D．7次
10．某 VB 程序段如下：
n = 6: i = 1
Do While i <= 3
k = i: j = i + 1
Do while j <= n
If a(j) < a(k) Then
k = j
j = j +1
Loop
If i <> k Then
t = a(i): a(i) = a(k): a(k) = t
End If
i=i+1
Loop
數(shù)組元素 a(1)到 a(6)的值依次為 1，6，5，3，4，2，則該程序段運(yùn)行后，數(shù)組元素 a(1)到 a(6)的值依次為（ ）
A．1，2，3，5，4，6 B．6，4，5，3，2，1
C．1，2，3，4，5，6 D．6，5，4，3，2，1
11．有如下 VB 程序段：
For i = 1 To 8
a(i) = Int(Rnd * 7) + 1
Next i
For i = 1 To 3
For j = 1 To 8 - 2 * i If a(j) Mod 7 > a(j + 2) Mod 7 Then
t = a(j): a(j) = a(j + 2): a(j + 2) = t
End If
Next j
Next i
For i = 1 To 8
ch(i) = Chr(a(i) + Asc("A") - 1)
Next i
執(zhí)行該程序段后，ch(1)～ch(8)各元素值不可能的是（ ）
A．AACBFBFE B．GGABCDDE C．ABBBCDDE D．ABBCDDEG
12．以下哪種排序算法的時(shí)間復(fù)雜度在最壞情況下是O(n^2)（ ）
A．快速排序 B．歸并排序 C．冒泡排序 D．堆排序
13．以下哪種排序算法是原地排序（ ）
A．快速排序 B．歸并排序 C．堆排序 D．所有以上
14．選擇排序的主要思想是在未排序的序列中找到最小（或最大）的元素，將其存放到已排序序列的末尾。這個(gè)過(guò)程會(huì)重復(fù)進(jìn)行，直到整個(gè)序列變得有序。選擇排序的時(shí)間復(fù)雜度是（ ）
A．O(n) B．O(n^2) C．O(n^3) D．O(nlogn)
15．字符串?dāng)?shù)組a中a(1)到a(6)的原始數(shù)據(jù)為57，3，24，34， 6，120，為了對(duì)該數(shù)組進(jìn)行排序操作，編寫(xiě)了以下VB程序。
i=2
Do While i<=6
For j=6 To i+2 Step -2
If a（j）>a（j-2）Then t=a（j）:a（j)=a（j-2）:a（j-2)=t
Next j
i=i+2
Loop
則程序運(yùn)行之后，數(shù)組元素a(1)和a(2)的值分別是（　　）
A．6 3 B．57 120
C．120 57 D．6 34
二、填空題
16．選擇排序的主要思想是在未排序的序列中找到最小（或最大）的元素，將其存放到已排序序列的末尾。選擇排序的平均時(shí)間復(fù)雜度為 。
17．在實(shí)現(xiàn)排序算法時(shí)，快速排序的平均時(shí)間復(fù)雜度為 。
18．在快速排序算法中，選擇一個(gè)好的基準(zhǔn)元素可以顯著提高算法的效率。通常使用 方法選擇基準(zhǔn)元素。
19．若要取消排序操作，可以點(diǎn)擊Excel工作表中的任意 。
三、操作題
20．某會(huì)務(wù)組根據(jù)參會(huì)者到達(dá)指定上車(chē)點(diǎn)時(shí)間和每位參會(huì)者可以等待的時(shí)間信息，安排車(chē)輛接送參會(huì)者去賓館（不考慮車(chē)子座位數(shù)量）。參會(huì)者到達(dá)上車(chē)點(diǎn)的時(shí)間和可以等待的時(shí)間用長(zhǎng)度為7的字符串表示，例如“08：15 2”表示參會(huì)者當(dāng)天8點(diǎn)15分到達(dá)上車(chē)點(diǎn)，最多等待2分鐘（每個(gè)人的等待時(shí)間都小于10），那么該參會(huì)者最晚8點(diǎn)17分出發(fā)去賓館（若8點(diǎn)17分剛到的參會(huì)者也一同出發(fā)）。編寫(xiě)Python程序，統(tǒng)計(jì)接送n個(gè)參會(huì)者所需的最少車(chē)輛數(shù)。運(yùn)行程序，顯示所有參會(huì)者提交的信息，按到達(dá)時(shí)間先后排列，再顯示所需的最少車(chē)輛數(shù)，程序運(yùn)行結(jié)果如圖所示。
（1）若將圖中第4行“08：154”數(shù)據(jù)改為“08：151”，程序輸出的結(jié)果是否會(huì)發(fā)生改變 （A．會(huì)改變B．不會(huì)改變）
（2）實(shí)現(xiàn)上述功能的部分Python程序如下，請(qǐng)?jiān)趧澗€處填入合適的代碼。
a=［'08：15 4'，'08：14 3'，'08：23 4'，'08：15 2'，'08：12 2'，'08：17 1'，'08：17 3'，'08：19 4'，'08：21 4'，'08：17 1'］
def tran（str1）：
ss=int（str1［：2］）*60+int（str1［3：6］）
return ss
for i in range（len（a）-1）：
for j in range（len（a）–1，i，-1）：
if a［j］a［j］，a［j-1］=a［j-1］，a［j］
n=len（a）
b=［］
c=［］
for i in range（n）：
b.append（tran（a［i］［：5］））
c.append（b［-1］+int（a［i］［6：］））
for j in range（i，0，-1）：
①
if c［k］>c［j］：
b［k］，b［j］=b［j］，b［k］
c［k］，c［j］=c［j］，c［k］
else：
break
sum=0
flag=［False for i in range（n）］
for i in range（n）：
if flag［i］==False：
for j in range（i，n）：
if ② ：
flag［j］=True
③
print（'接送所有參會(huì)者最少需要%d輛車(chē)'%sum）
21．有如下Python程序?qū)α斜韮?nèi)的數(shù)字進(jìn)行排序:
請(qǐng)編寫(xiě)并補(bǔ)充代碼，完善程序:
(1)第5行下劃線處應(yīng)填入 。
(2)第8行下劃線處應(yīng)填入 。
(3)該程序采用了 算法。
四、簡(jiǎn)答題
22．說(shuō)明歸并排序的步驟。
23．論述歸并排序的基本思想和實(shí)現(xiàn)步驟。
參考答案：
1．D
2．B
3．C
4．D
5．D
6．B
7．D
8．D
9．C
10．A
11．D
12．C
13．A
14．B
15．B
16．O(n^2)
17．O(nlogn)
18．隨機(jī)選擇
19．單元格
20． A k=j-1 flag［j］== False and b［j］<=c［i］或b［j］<=c［i］ sum+=1或sum=sum+1
21． i+1 k!=i 或 i!=k 選擇排序
22．歸并排序的步驟包括分解、遞歸排序和合并。首先將數(shù)組分解成兩個(gè)子數(shù)組，然后對(duì)它們分別進(jìn)行歸并排序，最后將兩個(gè)有序子數(shù)組合并成一個(gè)有序數(shù)組。
23．歸并排序的基本思想是將兩個(gè)有序的子序列合并成一個(gè)有序序列。實(shí)現(xiàn)步驟包括遞歸地將數(shù)組分成兩半，對(duì)每一半進(jìn)行歸并排序，然后將兩個(gè)有序的子序列合并成一個(gè)有序序列。歸并排序的平均時(shí)間復(fù)雜度為O(nlogn)。

展開(kāi)更多......

收起↑