用户中心
昆明理工大学2019年博士研究生入学考试算法分析与设计真题
各位考生，2021年全国各大院校博士招生将陆续开始。华慧考博将为大学提供2021年各大院校博士招生简章、考博招生专业目录等招生信息。如对考博备考有任何疑问，华慧考博还为广大考生提供了英语试考博真题、部分考博院校gt;专业课真题以及其他考博备考资料。如有需要，请大家关注华慧考博频道或者咨询华慧考博官方电话（ＱＱ同步）4006224468以下是昆明理工大学2019年博士研究生入学考试算法分析与设计真题内容如下：
昆明理工大学2019年博士研究生招生考试试题
考试科目代码：2035 考试科目名称 ：算法分析与设计 考生答题须知
1．所有题目（包括填空、选择、图表等类型题目）答题答案必须做在考点发给的答题纸上，做在本试题册上无效。请考生务必在答题纸上写清题号。
2．评卷时不评阅本试题册，答题如有做在本试题册上而影响成绩的，后果由考生自己负责。
3．答题时一律使用蓝、黑色墨水笔或圆珠笔作答（画图可用铅笔），用其它笔答题不给分。
答题时不准使用涂改液等具有明显标记的涂改用品。
一、选择题（每题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的时间复杂性满足递归方程
算法B的时间复杂性满足递归方程，若要使得算法A时间复杂性的阶高于算法B时间复杂性的阶，a的最大整数值可取多少？
4、比较分支限界法与回溯法的异同。
5、旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。证明TSP问题满足最优性原理。
三、应用题（共55分）
1、在Internet上的搜索引擎经常需要对信息进行比较，比如可以通过某个人对一些事物的排名来估计他（或她）对各种不同信息的兴趣，从而实现个性化的服务。对于不同的排名结果可以用逆序来评价它们之间的差异。考虑1,2,…,n的排列i1i2…in，如果其中存在ij,ik，使得j
(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分）
华慧考博英语预测作文（2021年版）适用于非医学命题作文已到货
详情请点击:[现货] 华慧考博英语预测作文（2021年版）适用于非医学命题作文
![华慧考博英语预测作文（2021年版）适用于非医学命题作文已到货 详情请点击:[现货] 华慧考博英语预测作文（2021年版）适用于非医学命题作文](http://www.hhkaobo.com/static/upload/2020-12-09/1607501869185.jpg)
