高中信息技术浙教版（2019）选修1 验收卷(四)　数据结构与算法（课件 练习含答案，2份打包）

(课件网) 第五章　数据结构与算法 验收卷(四)　数据结构与算法 (考试时间40分钟　满分50分) 一、选择题(本题共12小题，每小题2分，共24分) 1.下列有关数据结构的叙述中正确的是(　　) A 解析　栈是限定在一端进行插入和删除的线性表，而另一端封闭，队列是限定仅在一端进行插入，在另一端进行删除的线性表，因此B选项错误；数据结构与算法有着密不可分的关系，数据结构的不同选择会影响算法的运行效率，因此，在设计算法需要考虑选用何种数据结构，故C选项错误；链式存储结构不一定优于线性表的线性存储结构，例如查找时，链式存储结构需要从头开始找，而线性表可直接通过下标找到，因此D选项错误；算法的设计和选择总是依赖于数据结构，它们两者是相辅相成的，因此，答案为A。 A.算法的设计和选择总是依赖于数据结构 B.栈是限定仅在一端进行插入，在另一端进行删除的线性表 C.数据结构与算法是相互独立的，设计算法时不用考虑选用何种数据结构 D.链式存储结构优于线性表的线性存储结构 D 2.递归算法的执行过程，一般来说，可先后分为递推阶段和(　　) 解析　本题主要考查的是递归算法的执行过程。递归算法的执行过程分为递推和回归两个阶段，因此，答案为D。 A.合并阶段 B.返回阶段 C.回溯阶段 D.回归阶段 A 3.定义如下函数： def fn(n，num1，num2): 　if n＝＝1： 　 return num1 　return fn(n－1，num2，num1＋num2) 下列说法正确的是(　　) A.该算法的时间复杂度是O(n) B.fn(10，1，2)的效果等价于1＋2＋3…＋10 C.fn(5，1，1)的结果是22 D.fn(1，1，1)与fn(1，1，2)的返回结果不同 解析　A选项函数将调用n次，因此时间复杂度是O(n)。B选项该函数的功能是实现斐波那契数列效果；C选项，fn(5，1，1)的结果是 5；D选项fn(1，1，1)与fn(1，1，2)的返回结果相同，都是 1。 4.下列有两段程序： D 关于两个程序段的说法，正确的是(　　) A.程序段 1 和程序段 2 的输出结果不相同 B.程序段 1 和程序段 2 都采用了递归算法 C.若问题规模为 n，程序段 2 的时间复杂度为O(n2) D.程序段 1 中，①和②两方框处中的数字 1 同时修改为 0，输出结果不变 解析　本题考查递归和迭代、时间复杂度的计算阅读程序段 1，可知为递归算法实现 10＋9＋…＋1 的和；阅读程序段 2，可知为迭代算法实现 1＋2＋…＋10。因此两段程序输出结果相同，A 错误；程序段 2 为迭代算法，B 错误；程序段 2 中只有一层循环，时间复杂度为O(n)，C 错误；修改程序段 1 代码，仅仅多递归一层函数，但是返回值＋0 并不会影响输出结果，D 正确。 D 5.下列四段程序中，时间复杂度为O(n)的是(　　) 解析　选项A、B中程序段的时间复杂度均为O(n2)，因此，AB选项错误；选项C中程序段的时间复杂度均为O(log2n)，因此C选项错误；选项D中程序段，外循环的时间复杂度均为O(log2n)，内循环的执行次数为20＋21＋…＋2k(k＝log2n)，根据等比数据求和公式，其和为n－1，即时间复杂度为O(n)，因此答案为D。 6.有如下Python 程序段： def fx(x)： if x>3： ans＝x*fx(x－1) elif x>1： ans＝x＋fx(x－1) else： ans＝2 return ans n＝int(input(″please input n：″)) print(fx(n)) C 程序执行时，输入n的值为6，则输出的结果为(　　) A.127 B.720 C.840 D.1440 解析　本题主要考查的是递归算法。n＝6，ans＝6*5*4*f(3)，而f(3)＝3＋2＋f(1)，已知f(1)＝2，因此ans＝840，故答案为C。 D A.10，5，32，6，7，9，17，24，4 B.10，5，32，6，7，9，4，17，24 C.10，5，32，4，6，7，9，17，24 D.4，10，5，32，17，9，24，6，7 解析　冒泡的方向可以从前往后排序，后面的数据先有序；也可以从后往前排序，前面的数据先有序 ... ...