《2021年最新北航研究生算法(精心整理)》由会员分享，可在线阅读，更多相关《2021年最新北航研究生算法(精心整理)（12页珍藏版）》请在金锄头文库上搜索。
1、精品word学习资料 可编辑资料 - - - - - - - - - - - - - - - -精品文档一：判定题1、一个正确的算法，对于每个合法输入，都会在有限的时间内输出一个满意要求的结果；（对）2、NP 完全问题比其他全部NP 问题都要难；（错）3、回溯法用深度优先法或广度优先法搜寻状态空间树；（错，仅深度优先）4、在动态规划中，各个阶段所确定的策略就构成一个策略序列，通常称为一个决策；（错）5、P 类和 NP 类问题的关系用P. NP 来表示是错误的； （错）6、如近似算法A 求解某微小化问题一实例的解为Sa，且已知该问题的最优解为Sa/3，就该近似算法的性 能比为 3；（错）7、通常
2、来说，算法的最坏情形的时间复杂行比平均情形的时间复杂性简单运算；（对）8、如 P2 多项式时间转化为polynomial transforms toP1 ，就 P2 至少与 P1 一样难；（ 错）9、快速排序算法的平均时间复杂度是Onlogn ，使用随机化快速排序算法可以将平均时间复杂度降得更低；（错）10、基于比较的查找数组A1,n 中最大元素的问题下届是 n/3 ；（错）11、Ofn+Ogn=Ominfn,gn （错）12、如 fn=gn ， gn=hn ，就 fn= hn （对）13、如 fn=Ogn，就 gn= fn （对）14、贪婪技术所做的每一步挑选所产生的部分解，不肯定是可行性的
3、；（ 错）15、LasVegas算法只要给出解就是正确的；（对）16、一个完全多项式近似方案是一个近似方案A，其中每一个算法A 在输入实例I 的规模的多项式时间内运行；（错）二：简答1、二叉查找树属于减治策略的三个变种中的哪一个的应用？什么情形下二叉查找树表现出最差的效率？此时的查找和插入算法的复杂性如何？答：减治策略有3 个主要的变种， 包括减常量、 减常数因子和减可变规模；1 二叉查找树属于减可变规模变种的应用； 2 当先后插入的关键字有序时，构成的二叉查找树蜕变为单支树，树的深度等于n，此时二叉查找树表现出最差的效率，3 查找和插入算法的时间效率都属于 n；2、何谓伪多项式算法？如何将一
4、Monte Carlo 算法转化为Las Vegas算法？答：如一个数值算法的时间复杂度可以表示为输入数值N 的多项式，但其运行时间与输入数值N 的二进制位数呈指数增长关系，就称其时间复杂度为伪多项式时间；Las Vegas算法不会得到不正确的解；一旦用拉斯维加斯算法找到一个解，这个解就肯定是正确解；但有时用拉斯维加斯算法找不到解；Monte Carlo 算法每次都能得到问题的解，但不保证所得解的精确性转化： 可以在 Monte Carlo 算法给出的解上加一个验证算法，假如正确就得到解，假如错误就不能生成问题的解，这样 Monte Carlo 算法便转化为了Las Vegas算法；3、构造
5、AVL树和 2-3 树的主要目的是什么？它们各自有什么样的查找和插入的效率？答： 1当先后插入的关键字有序时，构成的二叉查找树蜕变为单支树，树的深度等于n，此时二叉查找树表现出最差的效率，为明白决这一问题，可以构造AVL 树或 2-3 树，使树的深度减小；一棵AVL 树要求它的每个节点的左右子树的高度差不能超过1；2-3 树和 2-3-4 树答应一棵查找树的单个节点不止包含一个元 素；2 AVL 树在最差情形下，查找和插入操作的效率属于 lgn；2-3 树无论在最差仍是平均情形下，查找 和插入的效率都属于 log n；4、写出 0/1 背包问题的一个多项式等价Polynomial Equiva
6、lent的等价的；判定问题， 并说明为什么它们是多项式答：0/1 背包问题： 从 M 件物品中， 取出如干件放在空间为W 的背包里， 给出一个能获得最大价值的方案；每件物品的体积为W1 ，W2Wn，与之相对应的价值为P1,P2Pn；+精品文档- - -细心整理 - - - 欢迎下载 - - -第 1 页，共 9 页精品word学习资料 可编辑资料 - - - - - - - - - - - - - - - -精品文档判定问题I：从 M 件物品中，取出如干件放在空间为W 的背包里，是否存在一个方案，所获价值P*？； 每件物品的体积为W1 ，W2Wn，与之相对应的价值为P1,P2Pn；如判定问题
7、I 存在多项式时间的解法， 就反复调用该算法就可以在多项式时间内解决0/1 背包的优化问题；因而这个判定问题与原问题多项式等价；5、下面问题是否属于NP 问题？为什么？问题表述：给定图中的两个点、，整数和 ，图中每条边的长度及便利这条边的时间， 问图中是否存在一条由到的路径，使得其长度大于，且遍历时间小于？答：这个问题属于NP 问题；由于如给出该问题的一个解，可以在多项式时间内检验这个解的正确性；如给出一条由 p 到 q 的路径，可以在多项式时间内运算出它的长度及遍历时间，然后分别与C 和 t 进行比较，从而可以判定这个解的对错；分治题1. 写出一个求解以下问题的分治算法，推导其时间复杂性并与
8、蛮力法相比较；给定互不相等的n 个数的一个序列，如其中某两个数和的关系为：且，就称和是逆序的；要求运算该序列中的逆序个数，即具有逆序关系的元素对的总数目；解： /* 求解 n 个数的一个序列，具有逆序关系的元素对的总数目*/ count = 0;/ 逆序元素对的全局计数变量 mergeInvertedPairsA,low,mid,high i = low;j = mid+1; k = low;tmpn;/ 用于归并排序的帮助数组while i = mid & j Aj tmpk = Aj+;count += mid-i+1;/ 相比归并排序，就多了这一条语句 else tmpk = Ai+;
9、k+;while i = mid tmpk+ = Ai+;while j = high tmpk+ = Aj+;for j = low; j = high; j+ Aj = tmpj;findInvertedPairsA, low, high if low aj ，那么说明需要调整次序，逆序数num=num+mid-i ；时间复杂度的迭代公式为1T nn1;因此算法的时间复杂度为Tn=Onlogn；2T n/ 2Onn1;蛮力法的时间复杂度为On2，当 n 数目较大时，分治法运算规模远小于蛮力法；2. 为一个整数序列， 中的整数 假如在 中显现次数余外 ，那么 称为多数元素；例如， 在序列中
10、3 是多数元素， 由于显现了 4 次，大于 ；求 A 的多数元素问题的蛮力算法复杂性如何？设计一个具有变治思想的算法，提高蛮力算法的效率，写出伪代码并分析其大事复杂性；2. num- src 0; count-0;fori-0 to n- 1 doif num = src i count+;elsecount-;if count 0num- src i ; count = 0;；采纳减治的思想每一个减去一个元素，时间复杂度为On，蛮力法的时间复杂度为On2动态规划题1. 某工厂调查明白市场情形，估量在今后四个月内，市场对其产品的需求量如下表所示；时期（月）需要量（产品单位）12233244已知
11、：对每个月来讲，生产一批产品的固定成本费为3（千元），如不生成，就为零；每生产单位 产品的成本费为1（千元）；同时，在任何一个月内，生产才能所答应的最大生产批量为不超过6 个单位；又知：每单位产品的库存费用为每月0.5（千元），同时要求在第一个月开头之初，及在第四个月精品文档- - -细心整理 - - - 欢迎下载 - - -第 3 页，共 9 页精品word学习资料 可编辑资料 - - - - - - - - - - - - - - - -精品文档末，均无产品库存；问：在满意上述条件下，该厂应如何支配各个时期的生产与库存，使所花的总成本费用最低？写出你所设的状态变量、决策变量、状态转移方程与
12、递推关系式，和手工求解的具体步骤及结果；解： 设阶段序数k 表示月份，状态变量x k 为第 k 个月初拥有的单位产品数量，亦为第k-1 月末时的单位产品数量，决策变量uk 为第 k 个月生产的单位产品数量，ck 为第 k 月份需要的产品数量，这里xk 和 uk 均取离散变量；状态转移方程为：, k =1,2,3,4;且 x 1=0；k 段答应决策集合为:k = 1,2,3;当 k=4 时，；设为第 k 月的成本费 , 单位为 千元 ，就,故指标函数为令表示为由动身采纳最优生产方案到第4 个月终止这段期间的产品成本；根据最优化原理，就有递推公式：其中：逆序运算的具体步骤如下：1当 k=4 时，2当 k=3 时，由于，且所以有：当此时在处取得最小值；当, 此时当, 此时当, 此时当, 此时, 在在处取得最小值；在处取得最小值；, 在处取得最小值；处取得最小值；当, 此时当, 此时, 在, 在处取得最小值；处取得最小值；3当 k=2 时，由于，且所以有：当时，, 在处取得最小值；当
