2019年云南昆明理工大学算法分析与设计考研真题.doc

发布时间：2022-09-16 发布人：admin 分类：说明书资料大小：0.03M 资料格式：doc 举报版权申诉

第1页 / 共2页

2019年云南昆明理工大学算法分析与设计考研真题.doc.pdf-第2页.jpg

第2页 / 共2页

文本预览

2019 年云南昆明理工大学算法分析与设计考研真题一、选择题（每题 2 分，共 20 分） 1、二分搜索算法是利用（）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、在下列算法中有时找不到问题解的是（）。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 3、以下不可以使用分治法求解的是（）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D0/1 背包问题 4、下列算法中通常以深度优先方式系统搜索问题解的是（ A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 5、分支限界法解最大团问题时，活结点表的组织形式是（ A、最小堆 B、最大堆 C、栈 D、数组 6、回溯法的效率不依赖于下列哪些因素（）。 A、满足显约束的值的个数 B、计算约束函数的时间 C、计算限界函数的时间 D、确定解空间的时间 7、（）是贪心算法与动态规划算法的共同点。）。）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质）。 8、分支限界法解旅行售货员问题时，活结点表的组织形式是（ A、最小堆 B、最大堆 C、栈 D、数组 9、下面问题（）不能使用贪心法解决。 A、单源最短路径问题 B、N 皇后问题 C、最小生成树问题 D、背包问题 10、回溯法搜索状态空间树是按照（）的顺序。 A、中序遍历 B、广度优先遍历 C、深度优先遍历 D、层次优先遍历 11、下列是动态规划算法基本要素的是（）。 A、定义最优解 B、构造最优解 C、算出最优解 D、子问题重叠性质 12、合并排序算法是利用（）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 13、背包问题的贪心算法所需的计算时间为（）。 A、O（n2n）B、O（nlogn）C、O（2n）D、O（n） 14、实现最大子段和利用的算法是（）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 15、优先队列式分支限界法选取扩展结点的原则是（）。 A、先进先出 B、后进先出 C、结点的优先级 D、随机 16、广度优先是（）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 17、下列哪一种算法是随机化算法（）。 A、贪心算法 B、回溯法 C、动态规划算法 D、舍伍德算法 18、实现最长公共子序列利用的算法是（）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 19、能采用贪心算法求最优解的问题，一般具有的重要性质为：（）。 A、最优子结构性质与贪心选择性质 B、重叠子问题性质与贪心选择性质 C、最优子结构性质与重叠子问题性质 D、预排序与递归调用 20、常见的两种分支限界法为（）。 A、广度优先分支限界法与深度优先分支限界法 B、队列式（FIFO）分支限界法与堆栈式分支限界法 C、排列树法与子集树法 D、队列式（FIFO）分支限界法与优先队列式分支限界法

二、简答题（每题 5 分，共 25 分） 1、请用数学化的语言来描述“最优化原理”的概念。 2、解释什么是 NP 类问题。 3、算法 A 和算法 B 解同一问题，设算法 A 的时间复杂性满足递归方程 1n , 1)n(T    1n , n)2/n(T4)n(T      算法 B 的时间复杂性满足递归方程 1n , n)4/n(aT  复杂性的阶高于算法 B 时间复杂性的阶，a 的最大整数值可取多少？ 1n , 1)n(T    )n(T     ，若要使得算法 A 时间 4、比较分支限界法与回溯法的异同。 5、旅行家要旅行 n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。证明 TSP 问题满足最优性原理。三、应用题（共 55 分） 1、在 Internet 上的搜索引擎经常需要对信息进行比较，比如可以通过某个人对一些事物的排名来估计他（或她）对各种不同信息的兴趣，从而实现个性化的服务。对于不同的排名结果可以用逆序来评价它们之间的差异。考虑 1,2,…,n 的排列 i1i2…in，如果其中存在 ij,ik，使得 jik，那么就称(ij,ik)是这个排列的一个逆序。一个排列含有逆序的个数称为这个排列的逆序数。例如排列 263451 含有 8 个逆序： (2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)，它的逆序数就是 8。显然，由 1,2,…,n 构成的所有 n!个排列中，最小的逆序数是 0，对应的排列就是 12…n；最大的逆序数是 n(n−1)/2，对应的排列就是 n(n−1)…21。逆序数越大的排列与原始排列的差异度就越大。利用二分归并排序算法设计一个计数给定排列逆序的分治算法，并对算法进行时间复杂度的分析。（15 分） 2、有 n 个分别排好序的整数数组 A0，A1,…,An－1，其中 Ai 含有 xi 个整数，i=0,1,…,n-1。已知这些数组顺序存放在一个圆环上，现在要将这些数组合并成一个排好序的大数组，且每次只能把两个在圆环上处于相邻位置的数组合并。问如何选择这 n-1 次合并的次序以使得合并时总的比较次数达到最少。（10 分） 3、假设零钱系统的币值是{1,p,p2,…,pn}，p>1，且每个钱币的重量都等于 1。设计一个最坏情况下时间复杂度最低的算法，使得对任何钱数 y，该算法得到的零钱个数最少。说明算法的主要设计思想，证明它的正确性，并给出最坏情况下的时间复杂度分析。（10 分） 4、用动态规划策略求解最长公共子序列问题：（1）给出计算最优值的递归方程。（5 分）（2）给定两个序列 X={B,C,D,A}，Y={A,B,C,B}，请采用动态规划策略求出其最长公共子序列，要求给出过程。（5 分） 5、利用分治算法写出合并排序的算法，并分析其时间复杂度。（10 分）

分享到：

赞收藏

资料库

2019年云南昆明理工大学算法分析与设计考研真题.doc

相关推荐

考研

热门标签

最新资料