Python编程四级 题库
下列有关递归与递推的描述中,正确的是?( )
递归思想体现了"大事化小事"的思想;一个问题既可以用递归也可以用递推来解决,选择哪一种算法,更多取决于效率和代码的可读性;递推通常比递归更高效,因为它避免了大量的函数调用。
递归算法的Python程序实现问题,下列说法正确的选项是?( )
递归算法必须有明确的结束递归的边界条件。
家里有16平方米的房间要打扫,小明和小红两兄妹分别想解决打扫的问题。 小明想用递归的方法解决“打扫房间”的问题:每次打扫一半区域,直到剩余区域小于1平方米。 以下哪项是递归解决此问题的核心思想?( )
递归的核心是分而治之,将原问题(打扫整个房间)分解为规模更小的同类子问题(每次打扫一半区域),直到子问题足够简单(剩余区域 <1 平方米)可直接解决。选项B准确描述了这一过程,其他选项未体现递归的“分解-解决”特性。
小红打算每次打扫一半区域,直到剩余区域≤1平方米时停止。分治算法中,递归终止条件是?( )
分治算法的终止条件是问题规模足够小可直接解决。选项B表明当剩余区域≤1平方米时,无需再分解,直接打扫。其他选项:A是继续分解的条件,非终止;C和D与问题规模无关,不符合分治逻辑。
小明的班级有8个同学,每个人身上贴了一个不同的数字,
现在要举办一场”快速排序比赛“,规则如下:
(1)设置两个变量i, j,排序开始时,i=0,j=N-1 。 (2)以第一个元素作为关键数据,将其赋值给key, 即key = A[0] 。 (3)从j开始向前搜索,即由后向前搜索(j--), 找到第一个小于key的值A[j],将A[j]与A[i]交换。 (4)从i开始向后搜索,即由前向后搜索(i++),找到第一个大于key的值A[i], 将A[i]与A[j]交换。 (5)重复第(3),(4)步骤,直到i==j; (6)分成的前后两组数据,分别再按(1)~(5)递归排序,直到全部数据有序排列。 初始队伍顺序:[5, 3, 9, 1, 7, 2, 8, 6]
请问如果第一趟快速排序后,分组结果是什么?( )
前面[1, 2, 3], 后面[7, 9, 8, 6]
开始 i=0,j=7, key=5 从后往前搜索 i=0,j=5, key=5 [2, 3, 9, 1, 7, 5, 8, 6] 从前往后搜索 i=2,j=5,key=5 [2, 3, 5, 1, 7, 9, 8, 6] 从后往前搜索 i=2,j=3,key=5 [2, 3, 1, 5, 7, 9, 8, 6] 第一趟排序结束。分成:前面[2, 3, 1]和后面[7, 9, 8, 6]
关于递归算法的特点,以下选项中描述错误的是?( )
递归算法效率不高。
递归算法的基本思想是把规模较大的问题变成规模较小的问题,下列选项中哪一项必须要有?( )
递归算法的要素。
设计一个程序来求xn(x的几次方)的值,算法思想是:把xn转换为x*xn-1,而xn-1又可以转换为x*xn-2,如此重复下去,直到x*x0,而x0=1,从而求出了xn的值。这个程序可以用递归来实现。
递归体现了“大事化小,小事化了”的思想,把大问题转换成小问题来解决,且有终止条件,即算法中的到x0=1为止。
某个问题既能用递归算法求解,又能用递推算法求解,则使用递归算法求解更容易,效率也高得多。( )
递归会引起一系列函数调用,有不少重复计算,其执行的效率也较低。
对于斐波那契数列,递推算法的时间复杂度远低于递归算法。( )
斐波那契数列的计算求解,递推算法时间复杂度为 O(n),递归算法时间复杂度为 O(2^n)。
递归算法有明确的结束递归的边界条件(又称终止条件)以及结束时的边界值,可以通过循环结构实现。( )
递归算法中结束时的边界值,可能通过条件语句实现。