电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

北航研究生算法(2018精心整理)VIP免费

北航研究生算法(2018精心整理)_第1页
1/10
北航研究生算法(2018精心整理)_第2页
2/10
北航研究生算法(2018精心整理)_第3页
3/10
一:判断题1、一个正确的算法,对于每个合法输入,都会在有限的时间内输出一个满足要求的结果。(对)2、NP完全问题比其他所有NP问题都要难。(错)3、回溯法用深度优先法或广度优先法搜索状态空间树。(错,仅深度优先)4、在动态规划中,各个阶段所确定的策略就构成一个策略序列,通常称为一个决策。(错)5、P类和NP类问题的关系用P⊂NP来表示是错误的。(错)6、若近似算法A求解某极小化问题一实例的解为Sa,且已知该问题的最优解为Sa/3,则该近似算法的性能比为3。(错)7、通常来说,算法的最坏情况的时间复杂行比平均情况的时间复杂性容易计算。(对)8、若P2多项式时间转化为(polynomialtransformsto)P1,则P2至少与P1一样难。(错)9、快速排序算法的平均时间复杂度是O(nlogn),使用随机化快速排序算法可以将平均时间复杂度降得更低。(错)10、基于比较的寻找数组A[1,…,n]中最大元素的问题下届是Ω(n/3)。(错)11、O(f(n))+O(g(n))=O(min{f(n),g(n)})(错)12、若f(n)=Ω(g(n)),g(n)=Ω(h(n)),则f(n)=Ω(h(n))(对)13、若f(n)=O(g(n)),则g(n)=Ω(f(n))(对)14、贪婪技术所做的每一步选择所产生的部分解,不一定是可行性的。(错)15、LasVegas算法只要给出解就是正确的。(对)16、一个完全多项式近似方案是一个近似方案{Aε},其中每一个算法Aε在输入实例I的规模的多项式时间内运行。(错)二:简答1、二叉查找树属于减治策略的三个变种中的哪一个的应用?什么情况下二叉查找树表现出最差的效率?此时的查找和插入算法的复杂性如何?答:减治策略有3个主要的变种,包括减常量、减常数因子和减可变规模。(1)二叉查找树属于减可变规模变种的应用。(2)当先后插入的关键字有序时,构成的二叉查找树蜕变为单支树,树的深度等于n,此时二叉查找树表现出最差的效率,(3)查找和插入算法的时间效率都属于Θ(n)。2、何谓伪多项式算法?如何将一MonteCarlo算法转化为LasVegas算法?答:若一个数值算法的时间复杂度可以表示为输入数值N的多项式,但其运行时间与输入数值N的二进制位数呈指数增长关系,则称其时间复杂度为伪多项式时间。LasVegas算法不会得到不正确的解。一旦用拉斯维加斯算法找到一个解,这个解就一定是正确解。但有时用拉斯维加斯算法找不到解。MonteCarlo算法每次都能得到问题的解,但不保证所得解的准确性转化:可以在MonteCarlo算法给出的解上加一个验证算法,如果正确就得到解,如果错误就不能生成问题的解,这样MonteCarlo算法便转化为了LasVegas算法。3、构造AVL树和2-3树的主要目的是什么?它们各自有什么样的查找和插入的效率?答:(1)当先后插入的关键字有序时,构成的二叉查找树蜕变为单支树,树的深度等于n,此时二叉查找树表现出最差的效率,为了解决这一问题,可以构造AVL树或2-3树,使树的深度减小。一棵AVL树要求它的每个节点的左右子树的高度差不能超过1。2-3树和2-3-4树允许一棵查找树的单个节点不止包含一个元素。(2)AVL树在最差情况下,查找和插入操作的效率属于Θ(lgn)。2-3树无论在最差还是平均情况下,查找和插入的效率都属于Θ(logn)。4、写出0/1背包问题的一个多项式等价(PolynomialEquivalent)的判定问题,并说明为什么它们是多项式等价的。答:0/1背包问题:从M件物品中,取出若干件放在空间为W的背包里,给出一个能获得最大价值的方案。每件物品的体积为W1,W2……Wn,与之相对应的价值为P1,P2……Pn。+判定问题I:从M件物品中,取出若干件放在空间为W的背包里,是否存在一个方案,所获价值≥P*?。每件物品的体积为W1,W2……Wn,与之相对应的价值为P1,P2……Pn。若判定问题I存在多项式时间的解法,则反复调用该算法就可以在多项式时间内解决0/1背包的优化问题。因而这个判定问题与原问题多项式等价。5、下面问题是否属于NP问题?为什么?问题表述:给定图G=(N,A)中的两个点p、q,整数c和t,图G中每条边的长度cij及便利这条边的时间tij,问图G中是否存在一条由p到q的路径,使得其长度大于c,且遍历时间小于t?答:这个问题属于NP问题。因为若给出该问题的一个解,可以在多项式时间内检验这个解的正确性。如给出一条由p到q的路...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

北航研究生算法(2018精心整理)

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部