青少年編程能力等級測評試卷Python編程四級第2套及解析答案

青少年編程能力等級測評試卷Python編程(四級)(考試時間90分鐘，滿分100分)一、單項選擇題(共15題，每題3分，共45分)在一個棧中，從棧低到棧頂依次存放元素A.B.C.D.E棧里原本的元素可以出棧。出棧后的元素不可以再次入棧，那么下面元素出棧的順序正確的是()。E,A,B,C,DB.A,B.C,D,EC.E,D,C,B,AD.D,C,B,A,E分形凡何就是研究無限復(fù)雜，但具有一定意義下的自相似圖形和結(jié)構(gòu)的幾何學(xué)。下而是使用turtle完成的一個謝爾賓斯基(Sierpinski)三角形的代碼，畫出的圖形是( )0importturtleast#計算中間點坐標(biāo)defget_midpoint(azb):ax,ay=abx,by=breturn(ax+bx)/2,(ay+by)/2#繪制一個三角形defdraw__triangle(a,bzc):ax,ay=abx,by=bex,cy=ct.pensize(5)t.penup()t.goto(ax,ay)t.pendown()t.goto(bx,by)t.goto(ex,cy)t.goto(ax,ay)t.penup()#繪制Sieipinski三角形defdraw_sierpinski(triangle,depth):a,b,c=triangledraw_triangle(a,b,c)ifdepth==0:return

else:b)c)a)f],depth-1)b)c)a)f],depth-1)b,e],depth-1)c],depth-1)[0,200],[200,-100]]3)在下列幾種排序方法中，空間復(fù)雜度最高的是()。插入排序選擇排序冒泡排序桶排序下列屬于分類算法的是()OA.K-Means算法B.DBSCANA.K-Means算法B.DBSCAN算法C.Cantor三分集算法D.決策樹分類算法對于順序存儲的棧和隊列，進行選擇排序運算的時間復(fù)雜度為( )。O(n) B.O(n2) C.O(log〃) D.0(1)在超市購物的時候，往往會現(xiàn)了排隊結(jié)賬的情況。我們可以把收銀臺結(jié)賬的過程，看作以下哪種調(diào)度算法( )oA.先來先服務(wù) B.高響應(yīng)比優(yōu)先C.時間片輪轉(zhuǎn) D.非搶占式短任務(wù)優(yōu)先將列表[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]請問使用的是以下選項中的哪種排序算法( )°A.快速排序 B.口泡排序C,選擇排序D.插入排序運行下方代碼，輸出結(jié)果為[0,1,2,3,4,5,6,7,8.9],空白處應(yīng)補充的代碼是( )0defselection_sort(arr):foriinrange(len(arr)):min_idx=iforjinrange(i+1,len(A)):A[i],A[min_idx]=A[min_idx],A[i]returnarrifA[min_idx]>A[j]:minidx=iifA[min_idx]<A[j]:min_idx=iifA[min_idx]>A[j]:min_idx=jifA[min_idx]<A[j]:min_idx=j運行下方代碼段，輸出的結(jié)果是()。deffirstUniqChar(str):counts={}order=[]forsinstr:ifsincounts:counts[s]+=1else:counts[s]=1order.append(s)foriinorder:

ifcounts[i]==1:returnis='abcdcba'i=firstUniqChar(s)print(i)B.aD.NoneB.aD.NoneC.d已知在下圖中，給出了一個數(shù)字網(wǎng)格。使用迪杰斯特拉（Dijkstra）算法，找出從左上角到右下角的路徑，并且路徑上的所有數(shù)值之和加起來最小的一條路徑是（ ）。A.a[0,0]->a[0zl]->a[l,l]->a[l,2]->a[2,2]A.a[0,0]->a[0zl]->a[l,l]->a[l,2]->a[2,2]C.a[0,0]->a[l,0]->a(l,l]->a[l,2]->a[2,2]a[0,0]->a[0zl]->a[0,2]->a[l/2]->a[2,2]D.a(0,0]->a[l,0]->a[2,0]->a[2,l]->a[2zl]對一組數(shù)據(jù)[91,12,26,92,22,88,6]進行從小到大進行冒泡排序，在排序的過程中，可能出現(xiàn)的排序情況有( )。A.[12,22,26.6,88,91,92] B,[12,26,88,22,6,91,92][6,12,26,22,88,91,92] D.[12,6,88,26,22,91.92]下列算法中，不屬于路徑規(guī)劃算法的是（A.C.貝葉斯算法算法迪杰斯特拉（Dijkstra）算法 A.C.貝葉斯算法算法A*算法運行下方代碼段，輸出的結(jié)果是( )。defsearch(nums):nums_sort=sorted(nums)iflen(nums)==1:return0ifnums_sort[-1]>=nums_sort[-2]*2:returnnums.index(nums_sort[-1])else:return-1nums=[2,0,3,9,1,4]i=search(nums)print(i)A.9 B.3 C.0 D.-114.使用冒泡排序?qū)⑿蛄?,4,5,1,2,9降序排列，需要交換（ ）。

14.A.3次B.4A.3次B.4次C.6次D.7次運行下方代碼段，輸出的結(jié)果最接近（importrandomnum_all=10000000num_cir=0foriinrange（num_all）:x=random.random（）y=random.random（）ifx*x+y*y<1:num_cir=num_cir+1print（num_cir/num_all）n/4 B.n/2C.n D.2n二、多項選擇題（共5題，每題2分，共10分）下列對Python第三方庫sklearn的敘述中，正確的有（ ）°sklearn庫中封裝了大量的機器學(xué)習(xí)算法sklearn庫中l(wèi)inear_model是廣義的矩陣模型sklearn庫中決策樹模型是GaussianNBfromsklearn.clusterimportKMeans可以導(dǎo)出K-Means函數(shù)下列排序的平均時間復(fù)雜度為0（?。┑乃惴ㄊ牵?）。D.希爾排序插入排序 B.冒泡排序 C.桶排序D.希爾排序下面關(guān)于K-Means聚類算法的描述正確的是（ ）°K-means停止的條件是所有的聚類中心不再改變K-means是隨機的把數(shù)據(jù)進行聚類K-means是常見的聚類方法，速度快，效率高K-Means思想就是把屬性相似的樣本歸到一類下面的算法中，屬于預(yù)測算法的有哪些（ ）。A.簡易平均法 B.指數(shù)平滑法C.廣度優(yōu)先法 D.線性回歸法下列有關(guān)常見數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的有（ ）。棧和堆都是由系統(tǒng)自動分配存儲空間棧的開辟釋放效率快，申請的內(nèi)存是連續(xù)的棧是先進后出的，而堆是先進先出的

棧和隊列都是限制了插入和刪除點的線性表三、編程題（共3題，共45分）如果一個字符串1的所有字符，按其在字符串中的順序，出現(xiàn)在另外一個字符串2中，則字符串1稱之為字符串2的子串。例如：*abc*就是123abc456的子串請編寫一個程序，接收用戶輸入的兩個字符串，求這兩個字符串的最長公共子串。要求：（1） 接收用戶輸入的兩個字符串，找到兩個字符申之間的最長公共子串，并旦打印出公共子串和子申的長度。（2） 如果沒有找到符合條件的公共子串，則打印無和0提示:（I）輸入兩個字符串’1234'和’12452345',字符串’234,是它們的最長公共子串，則輸出：'234，3（2）（2）使用一個變量記錄出現(xiàn)連續(xù)字符的次數(shù),并且可以用列表把重復(fù)出現(xiàn)的字符記家下來。例：輸入：BDCABA輸入：ABCCABBDAB輸入：ABCDE例：輸入：BDCABA輸入：ABCCABBDAB輸入：ABCDE輸入:SDFGHJ輸入：BCD輸入:0PIU0輸入：Abl23io輸入：12輸入:gguicci輸入：234uiccigg輸入:abccba輸入：abmccbam輸入:234輸入：Imn輸入：Zznmtl2輸入：Znmt45輸入：user輸入：USER出輸CAB3D1無0122uicci5ccba4無0nmt3無0出輸出輸出輸答案：defgetNumofCommonSubstr(strl,str2):Istrl=len(strl)lstr2=Ien(str2)record=[[0foriinrange(lstr2+1)]fbrjinrange(lstrl+l))#多一位maxNum=0 #最長匹配長度P=0 #匹配的起始位foriinrange(lstrl):fbrjinrange(lstr2):ifstrlli]==str2|j):#相同則累加record[i+l][j+l]=record[i][i]+1ifrecord[i+l][j+l]>maxNum:#獲取最大匹配長度maxNum=record(i+l]|j+l]#記錄最大匹配長度的終止位置p=i+1ifmaxNum==0:print('無',maxNum)else:print(strl[p-maxNum:p],maxNum)getNumofCommonSubstr('user','USER')在一個不確定的列表中，所有數(shù)字都是唯一的，并且每個數(shù)字都是規(guī)律遞増的。在這個不確定長度的列表中，只有一?個數(shù)字不在里面，請找出這個數(shù)字，如果沒有找到，則返回-1。例：輸入：[1,2,4]輸出：3輸入：[0,2,4,6,10,12,14]輸出：8輸入：[3,6,9,12]輸出：輸入：[5,10,20,25,301給出：15輸入：[4,6,8,10]輸出：T輸入：[1,3,5,7,11]輸出：9輸入：[4,4,4,4]給出：-1輸入：[2,3,3]輸出：-1輸入：[10,20,30,50,60,70]輸出：40答案：numjist=eval(inputO)defcheckjist⑴：add=l[l]-l[0]check_count=0num=-1foriinrange(len(l)-l):ifl[i]+add!=l[i+l]:check_count+=1num=l[i]+addifcheck_count==1andl[O]+add*len(l)==l[-1]:print(num)else:print(-l)check_list(num_list)現(xiàn)有一個神秘字符串s=，aceehrf,請你編寫一個排序程序，可以讓用戶找到字符串的真正含義。程序要求如下：依次輸入7個數(shù)字大小不同的數(shù)字，存在一個列表num中，列表的索引和字符串的索引一一對應(yīng),然后根據(jù)num列表里面的數(shù)字升序排序的結(jié)果，重新對字符串s進行組合。打印出新組合后的字符串S。例：輸入：[3,4,2,6,5,7,1]輸出:teacher輸入：[40,10,60,30,20,70,50]輸出:cheater稔入:[41,28,23,60,4,55,30】輸出:hectare輸入：[33,10,21,9,18,0,50]輸出:recheat輸入:[46,67,8,30,88,5,15]輸出:reteach輸入:[61,68,3,52,