青少年编程能力等级测评试卷Python编程四级第2套及解析答案
青少年编程能力等级测评试卷Python编程(四级)（考试时间90分钟，满分100分）一、 单项选择题（共15题，每题3分，共45分）1. 在一个栈中，从栈低到栈顶依次存放元素A,B,C,D,E 栈里原本的元素可以出栈。出栈后的元素不可以再次入栈，那么下面元素出栈的顺序正确的是（）。AE, A, B, C, DBA,B,C,D,ECE,D,C,B,ADD,C,B,A,E2. 分形几何就是研究无限复杂，但具有一定意义下的自相似图形和结构的几何学。下面是使用turtle 完成的一个谢尔宾斯基（Sierpinski）三角形的代码，画出的图形是( ) 。import turtle as t# 计算中间点坐标def get_midpoint(a, b): ax, ay = a bx, by = breturn (ax + bx) / 2, (ay + by) / 2# 绘制一个三角形def draw_triangle(a, b, c): ax, ay = a bx, by = b cx, cy = c t.pensize(5) t.penup() t.goto(ax, ay) t.pendown() t.goto(bx, by) t.goto(cx, cy) t.goto(ax, ay) t.penup()# 绘制 Sierpinski 三角形def draw_sierpinski(triangle, depth): a, b, c = triangle draw_triangle(a, b, c) if depth = 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)# 设置初始坐标绘制triangle = -200, -100, 0, 200, 200, -100draw_sierpinski(triangle, 3)A. 正确 B.C. D.3. 在下列几种排序方法中，空间复杂度最高的是（）。A插入排序B选择排序C冒泡排序D桶排序4. 下列属于分类算法的是（）。AK-Means算法BDBSCAN算法CCantor三分集算法D决策树分类算法5. 对于顺序存储的栈和队列，进行选择排序运算的时间复杂度为（）。AO(n)BO(n2)CO(logn)DO(1)6. 在超市购物的时候，往往会现了排队结账的情况。我们可以把收银台结账的过程，看作以下哪种调度算法（ ）。A先来先服务B高响应比优先C时间片轮转D非抢占式短任务优先7. 将列表 1, 3, 0, 4, 2, 6, 5 进行排序，并将过程中的结果打印如下：1, 3, 0, 4, 2, 6, 51, 3, 0, 4, 2, 6, 50, 1, 3, 4, 2, 6, 50, 1, 3, 4, 2, 6, 50, 1, 2, 3, 4, 6, 50, 1, 2, 3, 4, 6, 5 0, 1, 2, 3, 4, 5, 6请问使用的是以下选项中的哪种排序算法（）。A快速排序B冒泡排序C选择排序D插入排序8. 运行下方代码，输出结果为 0, 1, 2, 3, 4, 5, 6, 7, 8, 9，空白处应补充的代码是（）。def selection_sort(arr): for i in range(len(arr): min_idx = i for j in range(i + 1, len(A):_Ai, Amin_idx = Amin_idx, Aireturn arrAif Amin_idx > Aj: min_idx = iBif Amin_idx < Aj: min_idx = iCif Amin_idx > Aj: min_idx = jDif Amin_idx < Aj: min_idx = j9. 运行下方代码段，输出的结果是（）。def firstUniqChar(str): counts = order = for s in str: if s in counts: countss +=1 else: countss = 1 order.append(s) for i in order: if countsi = 1: return is = 'abcdcba'i = firstUniqChar(s)print(i)AabcBaCdDNone10. 已知在下图中，给出了一个数字网格。使用迪杰斯特拉（Dijkstra）算法，找出从左上角到右下角的路径，并且路径上的所有数值之和加起来最小的一条路径是（）。Aa0,0->a0,1->a1,1-> a1,2->a2,2 Ba0,0->a0,1->a0,2->a1,2->a2,2 Ca0,0->a1,0->a1,1-> a1,2->a2,2 Da0,0->a1,0->a2,0-> a2,1->a2,111. 对一组数据 91, 12, 26, 92, 22, 88, 6 进行从小到大进行冒泡排序，在排序的过程中，可能出现的排序情况有（ ）。A12, 22, 26, 6, 88, 91, 92B12, 26, 88, 22, 6, 91, 92C6, 12, 26, 22, 88, 91, 92D12, 6, 88, 26, 22, 91, 9212. 下列算法中，不属于路径规划算法的是（）。A迪杰斯特拉（Dijkstra）算法B弗洛伊德（Floyd）算法C贝叶斯算法DA*算法13. 运行下方代码段，输出的结果是（）。def search(nums): nums_sort = sorted(nums) if len(nums) = 1: return 0 if nums_sort-1 >= nums_sort-2 * 2: return nums.index(nums_sort-1) else: return -1nums = 2,0,3,9,1,4i = search(nums)print(i)A9B3C0D-114. 使用冒泡排序将序列6, 4, 5, 1, 2, 9降序排列，需要交换（）。A3次B4次C6次D7次15. 运行下方代码段，输出的结果最接近（）。import randomnum_all = 10000000num_cir = 0for i in range(num_all): x = random.random() y = random.random() if x*x + y*y < 1 : num_cir = num_cir + 1print(num_cir/num_all)A4B2CD2二、 多项选择题（共5题，每题2分，共10分）16. 下列对Python第三方库sklearn的叙述中，正确的有（）。Asklearn库中封装了大量的机器学习算法Bsklearn库中linear_model是广义的矩阵模型Csklearn库中决策树模型是GaussianNBDfrom sklearn.cluster import KMeans 可以导出K-Means 函数17. 下列排序的平均时间复杂度为O(n2)的算法是（）。A插入排序B冒泡排序C桶排序D希尔排序18. 下面关于 K-Means 聚类算法的描述正确的是（）。AK-means停止的条件是所有的聚类中心不再改变BK-means 是随机的把数据进行聚类CK-means是常见的聚类方法，速度快，效率高DK-Means思想就是把属性相似的样本归到一类19. 下面的算法中，属于预测算法的有哪些（ ）。A简易平均法B指数平滑法C广度优先法D线性回归法20. 下列有关常见数据结构的叙述中，正确的有（）。A栈和堆都是由系统自动分配存储空间B栈的开辟释放效率快，申请的内存是连续的C栈是先进后出的，而堆是先进先出的D栈和队列都是限制了插入和删除点的线性表三、 编程题（共3题，共45分）21. 如果一个字符串1的所有字符，按其在字符串中的顺序，出现在另外一个字符串2中，则字符串1称之为字符串2的子串。例如：abc 就是 123abc456的子串请编写一个程序，接收用户输入的两个字符串，求这两个字符串的最长公共子串。要求：（1） 接收用户输入的两个字符串，找到两个字符串之间的最长公共子串，并且打印出公共子串和子串的长度。（2） 如果没有找到符合条件的公共子串，则打印 无 和 0提示：（1） 输入两个字符串 1234 和 12452345，字符串 234 是它们的最长公共子串，则输出: 234 3（2） 使用一个变量记录出现连续字符的次数，并且可以用列表把重复出现的字符记录下来。例：输入：BDCABA输入：ABCCABBD
