全國青少年編程能力等級考試Python編程四級2021、4月

青少年編程能力等級測評Python編程四級

一.單選題

1.分形幾何就是研究無限復(fù)雜，但具有一定意義下的自相似圖形和結(jié)構(gòu)的幾何學(xué)。下面是使

用turtle完成的一個謝爾賓斯基(Sierpinski)三角形的代碼，畫出的圖形是()。

importturtleast

#計算中間點坐標

defget_midpoint(a,b):

ax,ay=a

bx,by=b

return(ax+bx)/2,(ay+by)/2

#繪制一個三角形

defdraw_triangle(a,b,c):

ax,ay=a

bx,by=b

ex,cy=c

t.pensize(5)

t.penup()

t.goto(ax,ay)

t.pendownQ

t.goto(bx,by)

t.goto(cx,cy)

t.goto(ax,ay)

t.penup()

#繪制Sierpinski三角形

defdraw_sierpinski(triangle,depth):

a,b,c=triangle

draw_triangle(a,b,c)

ifdepth==0:

return

else:

d=get_midpoint(a,b)

e=get_midpoint(b,c)

f=get_midpoint(c,a)

draw_sierpinski([a,d,f],depth-1)

draw_sierpinski([d,b,e],depth-1)

draw_sierpinski([f,e,c],depth-1)

#設(shè)置初始坐標繪制

triangle=[[-200,-100],[0,200],[200t-100]]

draw_sierpinski(triangle,3)

A.

A.插入排序

B.選擇排序

C.冒泡排序

D.桶排序

3.對一組數(shù)據(jù)[91,12,26,92,22,88,6]進行從小到大進行冒泡排序,在排序的過程中，可

能出現(xiàn)的排序情況有（）o

A.

[12,22,26,6,88,91,92]

B.

[12,26,88,22,6,91,92]

C.

[6,12,26,22,88,91,92]

D.

[12t6,88,26,22,91,92]

4.已知在下圖中，給出了一個數(shù)字網(wǎng)格。使用迪杰斯特拉(Dijkstra)算法，找出從左上角

到右下角的路徑，并且路徑上的所有數(shù)值之和加起來最小的一條路徑是()。

A.

a[0,0]->a[0,l]->a[l,l]->a[l,2]->a[2,2]

B.

a[0,0]->a[0,l]->a[0,2]->a[l,2]->a[2,2]

C.

a[0,0]->a[l,0]->a[l,l]->a[l,2]->a[2,2]

D.

a[0,0]->a[l,0]->a[2,0]->a[2,l]->a[2,l]

5.在一個棧中，從棧低到棧頂依次存放元素A,BCD,E棧里原本的元素可以出棧。出棧后的

元素不可以再次入棧，那么下面元素出棧的順序正確的是（）。

A.

E,A,B,C,D

B.

A,B,C,D,E

C.

E,D,C,B,A

D.

D,C,B,A,E

6.對于順序存儲的棧和隊列，進行選擇排序運算的時間復(fù)雜度為()。

A.O(n)

B.O(n2)

C.O(logn)

D.O(l)

7.運行下方代碼，輸出結(jié)果為[0,1,2,3,45,6,7,8,9],空白處應(yīng)補充的代碼是()。

defselection_sort(arr):

foriinrange(len(arr)):

rninjdx=i

forjinrange(i+1,len(A)):

A[i],A[min_idx]=A[min_idx],A[i]

returnarr

A.

ifA[min_idx]>A[j]：

minjdx=i

B.

ifA[min_idx]<A[j]:

minjdx=i

C.

ifA[minjdx]>A[j]：

minjdx=j

D.

ifA[minjdx]<AO]：

minjdx=j

8.使用冒泡排序?qū)⑿蛄?,4,5,1,2,9降序排列，需要進行交換的輪次是（）o

A.3次

B.4次

C.6次

D.7次

9.列屬于分類算法的是（）。

A.K-Means算法

B.DBSCAN算法

C.Cantor三分集算法

D.決策樹分類算法

10.下列算法中，不屬于路徑規(guī)劃算法的是()o

A.迪杰斯特拉(Dijkstra)算法

B?弗洛伊德(Floyd)算法

C.貝葉斯算法

D.A*算法

11.運行下方代碼段，輸出的結(jié)果最接近()o

importrandom

num_all=10000000

num_cir=0

foriinrange(num_all):

x=random.random()

y=random.random()

ifx*x+y*y<1:

num_cir=num_cir+1

print(num_cir/num_all)

A.n/4

B.n/2

C.TT

D.2n

12.運行下方代碼段，輸出的結(jié)果是()0

defsearch(nums):

nums_sort=sorted(nums)

iflen(nums)==1:

return0

ifnums_sort[-l]>=nums_sort[-2]*2:

returnnums.index(nums_sort[-l])

else:

return-1

nums=[2,0,3,9,1,4]

i=search(nums)

print(i)

A.9

B.3

C.O

D.-l

13.運行下方代碼段，輸出的結(jié)果是()。

deffirstllniqChar(str):

counts=0

order=[]

forsinstr:

ifsincounts:

counts[s]+=1

else:

counts[s]=1

order.append(s)

foriinorder:

ifcounts[i]==1:

returni

s='abcdcba'

i=firstUniqChar(s)

print(i)

A.abc

B.a

C.d

D.None

14.在超市購物的時候，往往會現(xiàn)了排隊結(jié)賬的情況。我們可以把收銀臺結(jié)賬的過程，看作

以下哪種調(diào)度算法()。

A.先來先服務(wù)

B.高響應(yīng)比優(yōu)先

C.時間片輪轉(zhuǎn)

D.非搶占式短任務(wù)優(yōu)先

15.將列表[1,3,0,4,2,6,5]進行排序，并將過程中的結(jié)果打印如下：

[1,3,0,4,2,6,5]

[1,3,0,4,2,6,5]

[0,1,3,4,2,6,5]

[0,1,3,4,2,6,5]

[0,1,2,3,4,6,5]

[0,1,2,3,4,6,5]

[0,1,2,3,4,5,6]

請問使用的是以下選項中的哪種排序算法()o

A.快速排序

B.冒泡排序

C.選擇排序

D.插入排序

二.多選題

1.下列對Python第三方庫sklearn的敘述中，正確的有（）。

A.sklearn庫中封裝了大量的機器學(xué)習(xí)算法

B.sklearn庫中l(wèi)inear_model是廣義的矩陣模型

C.sklearn庫中決策樹模型是GaussianNB

D.fromsklearn.clusterimportKMeans可以導(dǎo)出K-Means函數(shù)

2.列排序的平均時間復(fù)雜度為0（n2）的算法是（）。

A.插入排序

B.冒泡排序

C桶排序

D.希爾排序

3.下面關(guān)于K-Means聚類算法的描述正確的是（）。

A.K-means停止的條件是所有的聚類中心不再改變

B.K-means是隨機的把數(shù)據(jù)進行聚類

C.K-means是常見的聚類方法，速度快，效率高

D.K-Means思想就是把屬性相似的樣本歸到一類

下列有關(guān)常見數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的有（）

4.0

A.棧和堆都是由系統(tǒng)自動分配存儲空間

B.棧的開辟釋放效率快，申請的內(nèi)存是連續(xù)的

C.棧是先進后出的，而堆是先進先出的

D.棧和隊列都是限制了插入和刪除點的線性表

下面的算法中，屬于預(yù)測算法的有哪些（）

5.o

A.簡易平均法

B.指數(shù)平滑法

C.廣度優(yōu)先法

D.線性回歸法

三.編程題

1.如果一個字符串1的所有字符，按其在字符串中的順序，出現(xiàn)在另外一個字符串2中，

則字符串1稱之為字符串2的子串。

例如：‘a(chǎn)bc,就是123abc456的子串

請編寫一個程序，接收用戶輸入的兩個字符串，求這兩個字符串的最長公共子串。

要求：

?接收用戶輸入的兩個字符串，找到兩個字符串之間的最長公共子串，并且打印出公共子

串和子串的長度。

?如果沒有找到符合條件的公共子串，則打印無和0

提示：

?輸入兩個字符串‘1234'和'12452345’,字符串‘234,是它們的最長公共子

串，則輸出：'234,3

?使用一個變量記錄出現(xiàn)連續(xù)字符的次數(shù)，并且可以用列表把重復(fù)出現(xiàn)的字符記錄下來。

例：輸入：BDCABA輸入：ABCCABBDAB