赢在大学领英工程整理汇编—算法试卷

《赢在大学领英工程整理汇编—算法试卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、B卷（视频中只有判断题部分）一．判断题：1.算法分析，我们更关注算法的空间效率问题。2．在很多情况下，数据结构的设计直接影响基于该结构之上设计的时间性能。3.算法可以采用自然语言、流程图、伪代码等多种方式来描述。4.不是所有的问题都可以用计算机来求解。5.问题规模可以影响算法的执行时间。6..P类问题是NP问题的子集。7.分治法和动态规划都将待求解问题分解成若干个子问题。8.贪心法的典型应用是求解最优化问题。9.回溯法问题的解空间树是虚拟的，并不需要在算法运行时构造一棵真正的树结构。10.分支限界法是一种有组织的系统化搜索技术。11.减治法分解出来的子问题不需要分别求解，只需求解其中的

2、一个子问题。A卷一．判断题：1.算法研究核心问题是时间（速度）问题。2.算法是程序别名。3.算法只能采用伪代码来描述。4.现实生活中只要有足够的时间和空间，所有的问题都可以用计算机解决。5.要评估一个算法的时间效率必须要该算法的执行时间。6.NP完全问题是NP类问题的子类。7.在用分治设计算法时，最好是各子问题之间相互独立。8.作为一种算法设计技术，贪心法是一种简单有效的方法。9.回溯法每次只能构造可能解的一部分。10.回溯法就是一种有组织的系统化的搜索技术。11.一个问题用贪心法求解时只会有一种贪心法策略。二．单项选择题：1.设函数f（n）和g（n）是定义在非负整数集合上的正函数，如

3、果存在两个正常数c和n0，使得当n≧n0时，有f（n）≦cg（n），则记做（A）A．f(n)=O(g(n))B.f(n)=Ω(g(n))第一小题和08届卷子的单项选择第一小题一样。2.蛮力法所依赖的基本技术是（）A．扫描技术B.查找技术C．分治技术D.动态规划3.基于比较的排序算法的时间复杂度下界为（）A．Ω（n）B.Ω（n2）C．Ω（nlogn）D.视频太模糊，看不清楚此选项4.下列哪个问题是NP完全问题（）A．停机问题B.图着色问题C．最小生成树问题D.八皇后问题5.快速排序算法是利用（）实现的算法。A．分治策略B.动态规划C．贪心法D.回溯法6.通过贪心法必定可以求得下列哪个问题

4、的最优解（）A．图着色问题B.最小生成树问题C．多机调度问题D.TSP问题7.用动态规划法求解的问题除了能够分解为相互重叠的子问题外，还需要满足（）A．最优先问题B.最优量度问题C．目标函数D.贪心规划8.以下哪种方法要将待求解的问题分解成若干子问题（）A.分治法B.贪心法C．回溯法D.分支限界法9.以下哪个函数是间接函数（）A．递归函数B.阶乘函数C．约束函数D.__函数（视频太模糊，看不清楚此选项）10.回溯法按（）遍历问题的解空间树。A．深度优先策略B.广度优先策略C.最小耗费优先D.随机搜索11.（A）可以用多项式时间的确定性算法来进行判定和求解。A．P类问题B.NP类问题C．

5、NP完全问题D.子集和问题三．按照渐近阶从低到高的顺序排列以下表达式。4n2，logn，3n，20n，2，n，n！（此题只能看个大概的内容）四．算法填空1.n皇后问题的片段在书本P174第一处空白：while（x[k]<=n&&(1)）填写内容为：!Place(k)第二、三处空白：elseif（x[k]<=n&&k

6、(4);S[i][j]=1;}elseif(L[i][j-1]>=L[i-1][j]){(5);S[i][j]=2;}空白（4）填写:L[i][j]=L[i-1][j-1]+1空白（5）填写：L[i][j]=L[i][j-1]五．简答题（A卷B卷的综合）1.什么是算法，它有哪些重要的特性？2.分治算法的求解过程？（分治算法的基本思想和分割原则？）3.应用动态规划思想有哪些步骤及其设计思想？（动态规划的基本要素？）