青少年编程能力等级测评试卷Python编程四级第1套试卷.docx
青少年编程能力等级测评试卷Python编程（四级）（考试时间90分钟，满分100分）一、单项选择题（共15题，每题3分，共45分）.若A, B, C, D, E这5个元素依次顺序进栈，则下列不会出现的出栈顺序是（ ）o A. E, A, B, C, D B. A, B, C, D, E C. B, C, D, E, A D. E, D, C, B,A2.以下步骤描述的分形方式是（）。步骤1：把闭区间平均分为三段，去掉中间的1/3部分段，留下剩余两个闭区间；步骤2：将剩下的两个闭区间各自平均分为三段，同样去掉中间的区间段，这时剩下四段闭区间;步骤3：重复删除每个小区间中间的1/3段，迭代至区间无穷小。A. Koch曲线B.谢尔宾斯基三角形C.康托尔三分集D.牛顿迭代3.下方排序算法的时间复杂度为( )o x = 0 y = 1 for i in rang(n):x += ifor j in range (n):Y夫=jA. O()B.。(层)C. O(logn)D. 0(1)4.下列属于分类算法的是（ ）oA. K-Means算法 B. DBSCAN算法 C.贝叶斯算法D. Koch曲线递归算法5 .对于顺序存储的栈和队列，进行插入运算的时间复杂度为（ ）oA. 。（）B.。（/）C. OQog"）D. 。（1）.下列满足短任务优先且不会发生饥饿现象的调度算法是（ ）oA.先来先服务B.高响应比优先C.时间片轮转D.非抢占式短任务优先7 .下方代码段采取的排序方法是()。def sort(data):dl =while len(data):min = 0r data0for i in range(len(data):if min1 > datai:min = i, dataidel datamin0dl append(min1) return dlD.插入排序:)ocurrent:A.快速排序B.冒泡排序 C.选择排序.下方代码段通过插入排序的方法完成排序，空白处应补充的代码是 def insertion_sort(arr):for i in range(1, len(arr):current = arripre_index = i - 1whil pre_index >= 0 and arrpr_indexpre_index -= 1arrpre_index + 1 = current return arrA. arrpre_index = arrpre_index+lB. arri = arri+1C. arr pre_index-f-l = arr pre_indexD. arri+1 = arri.运行下方代码段，输出的结果是( )odef isPrefixOfWord(sentence,searchword):1 = sentence.split()for i in range (len (1):if 1 i :len (searchword)=searchWord: return i + 1return -1sentence = "Python is the best computer language! searchword = "comput"i = isPrfixOfWord(sentnc，searchword) print (i)A. -1A. -1B. i + 110.C. 5D. 6使用迪杰斯特拉标顶点依次是（Dijkstra）算法，求图中从顶点1到其他各顶点的最短路径，得到各最短路径的目)oA. 5, 2, 6, 3,C. 5, 2, 4, 3,11.使用冒泡排序将序列3, 4,A. 2次C. 5次1, 11, 15,7, 4升序排列,需要交换（)o12.下列路径算法中，属于贪心算法的是（A.迪杰斯特拉（Dijkstra）算法C.弗洛伊德（Floyd）算法13.运行下方代码段，输出的结果是(def search(nums, target):def helper (tar):i, j = 0, len (nums) while i <= j:m = (i + j) / 2)oif numsm <= tar:i = m + else:j = m - return ireturn helper(target)numstarget5, 6, 6, 8,8,8, 10 =8B.D.)oB.D.深度优先搜索算法广度优先搜索算法- helper(target-1)i = search(nums, target) print (i)14.A. 7B. 6使用选择排序将序列3, 7, 14, 1,18,C. 4D. 3A. 3次B. 4次5, 8, 9升序排列,C. 6次需要交换（)oD. 10 次15 .运行下方代码段，输出的结果最接近( )o import random n = 1000000 r = 1.0 a, b = (0.0, 0.0) x_neg, x_pos = a - r, a + r y_neg, y_pos = b - r, b + r count = 0 for i in range(0, n):x = random.uniform(x_neg, x_pos) y = random.uniform(y_neg, y_pos) if x*x + y*y <= 1.0: count += 1 print (count / float (n) * 4B.兀/2D. 2兀A. 7i / 4C.兀二、多项选择题（共5题，每题2分，共10分）16 .下列对Python第三方库sklearn的叙述中，正确的有（）。A. skleam库中封装了大量的机器学习算法B. skleam库中linear model是广义的线形模型C. skleam 库中决策树模型是 skleam.naive_bayesD. from ski earn. 1 i near_model import LogisticRefression 可以导入线形回归函数.下列排序算法中，基于比较的算法有（）。A.堆排序B.冒泡排序C.桶排序D.希尔排序.下列对于聚类算法的叙述中，正确的有（）。A.聚类分析是给定划分类别的情况下，根据类别进行样本分组的方法B.与传统分群方法相比聚类方法可以发现之前未知的特征因素C. K-means是常见的聚类方法，速度快，效率高D.与传统分群方法相比聚类方法能对新的数据快速复制应用.下列有关预测算法的叙述中，属于线性回归模型的优势有（ ）oA.模型简单易解释B.系数大小易理解C.对于非线性关系易捕捉D.更好的分析数据之间的相互影响.下列有关常见数据结构的叙述中，正确的有（ ）oA.栈由系统自动分配存储空间，堆由人为申请开辟空间B.栈申请空间的效率较低，堆的申请效率较高C栈只允许在栈顶插入和删除元素，堆可以随意存取D.队列只允许在前段进行删除操作，在后端进行插入操作三、编程题（共3题，共45分）.从字符串中找出一个最长的不包含重复字符的子字符串，并计算该子字符串的长度。例：输入：abcabcbb输出：3输入：bbbbb输出：121 .通过二分查找法查找有序列表1,6,9,15,26,38,49,57,63,77,81,93中的数字位置。当输入的数字 不存在于列表中时，输出FALSE。注：列表的第一个元素是第0个。例：输入：1输出：0输入：50输出：FALSE22 .通过冒泡排序将列表按从小到大的顺序排列并打印出每一步排序结果，同时输出该列表的中位数。例：输入:3,5,2,8,1,7输出：3, 2, 3, 2, 3, 2, 2, 3, 2, 3, 2, 1, 1, 2,5, 8, 1, 75, 1, 8, 75, 1, 7, 85, 1, 7, 81, 5, 7, 83, 5, 7, 83, 5, 7, 8
