下载文档原格式
一、Please answer T or F for each of the following statements to indicate whether thestatement is true or false1. An algorithm is an instance, or concrete representation, for a computer programin some programming language. ( F )2. The following problem is a Decision Problem: What is the value of a bestpossible solution? ( F )3. The dynamic programming method can not solve a problem in polynomial time.( F)4. Assume that there is a polynomial reduction from problem A to problem B. Ifwe can prove that A is NP-hard, then we know that B is NP-hard. ( F )5. If one can give a polynomial-time algorithm for a problem in NP, then all theproblems NP can be solved in polynomial time. ( F )6. In an undirected graph, the minimum cut between any two vertices a and b isunique. ( F)7. Linear programming can be solved in polynomial time, but integer linearprogramming can not be solved in polynomial time. ( T )8. We can solve the maximum independent set problem in a graph with at most100 vertices in polynomial time. ( T ) 结论9. If an algorithm solves a problem of size n by dividing it into two subproblems ofsize n/2, recursively solving each subproblems, and then combine the solutions in linear time. Then the algorithm runs in O(n log n) time. ( T )10. Neural Computation, Fuzzy Computation and Evolution Computing are thethree research fields of Computational Intelligence. ( T )二、Given the following seven functions f1(n) = n5+ 10n4, f2(n) = n2+ 3n, f3(n) =f4(n) = log n + (2log n)3, f5(n) = 2n+n!+ 5e n, f6(n) = 3log(2n) + 5log n, f7(n) = 2n log n+log n n. Please answer the questions:第 1 页共5 页(a) Give the tight asymptotic growth rate (asymptotic expression with θ) to eachof them; (7分)(b) Arrange them in ascending order of asymptotic growth rate。
算法分析课程设计题目及评分标准（）任选题目任选题目优：1至少一个三星，1个二星2 至少完成5个题目3 必须主动申请，制作PPT，面向全班讲自已的思想，演示程序。
4 文档符合规范良：1 题目包含至少1个二星以上题目2 至少完成4个题目3 文档符合规范中：1 至少完成4个题目2 文档符合规范及格：1 至少完成3个题目3 文档符合规范凡发现抄袭或不能正确理解自已编写程序，该题目分数取消。
根据文档、程序、考勤，降低等级。
题目：1 一次大型的party最后节目是选取一位幸运人士，该人将获得组织者准备的一个钻石戒指。
选择办法是让所有人一字排列，然后从左至右点数，凡是奇数号的全部删除。
对剩下的人，同样从左至右点数，逢奇数号就删除。
如此不断循环，直到只剩1人为止。
此即为幸运之人。
（☆）3 假设你在餐馆吃饭花了不到100元，结账时你给服务员一张百元钞票，而服务员希望用最少的纸币给你找钱。
请设计算法帮助服务员（☆）。
4假定你开去香格里拉。
出发前油箱是满的，可以行驶D公里。
路上一共有n个加油站，A[i]表示从第i-1加油站到第i个的距离。
最后一个加油站在香格里拉。
请设计算法帮助驾驶员选择加油站使加油的次数最少（☆）。
5计算一元钱硬币有多少种表达方式。
例如，可以使用1元钱完成，也可以使用两个5角完成。
这里可供选择的货币单位从1分到1元。
编写程序计算出每一种组合方式。
（☆）6完成一维的最接近点对问题（p121）（☆）7 分别用动态规划、贪心法、回溯法实现背包问题，并比较它们的结果，算法的效率（☆）。
8给定线性序集中n 个元素和一个整数k ，1≤k ≤n ，要求找出这n 个元素中第k 小的元素（☆）9 分别实现选择排序，插入排序，归并排序，快速排序，分析他们的时间复杂度，并用程序统计他们实际运行的时间（随机产生100000个），要求有良好界面。
（☆）2 你走大街上上需要从左边马路走到右边马路，而一路上十字路口有n 个，你可以在绿灯亮时任意的一个十字路口穿越马路，遇红灯则需要等待绿灯，或继续向前走，从以后的十字路口穿过。
杭州电子科技大学电子科学与技术专业Electronic Science and Technology培养方案Undergraduate Education Program电子信息学院制定2014年6月学院负责人：胡飞跃专业负责人：郑梁电子科学与技术专业一、培养目标本专业培养适应社会主义建设和经济发展需要，德、智、体、美全面发展的具有较强的创新精神与实践能力的人才。
通过本专业课程的学习，掌握电子科学与技术专业必需的基础知识、基本理论和基本实验技能，能够从事电子材料、电子元器件及电子电路等相关电子技术领域的科技开发、工程技术、生产管理与行政管理等工作的高级技术人才。
电子科学与技术专业期待毕业生几年之内达到以下目标：（1）具有高尚的职业道德；（2）具备在电子信息领域从事科学研究、工程设计、设备制造、技术管理等方面工作的能力（3）在团队工作中，有良好的领导、组织和协作能力；（4）能够为国内的乃至全球的电子及相关行业服务；（5）能够通过继续教育或其他终身学习渠道增加知识和提升能力；或能够继续深造、攻读国内外本学科及相关专业的硕士/博士学位。
二、毕业要求1、基本素质及知识体系要求（1）热爱社会主义祖国，树立科学世界观，正确的人生观、价值观，具有良好的思想品德和社会公德。
（2）具有较好的人文社会科学素养、社会责任感和工程职业道德；（3）掌握科学锻炼身体的基本技能，受到必要的军事训练，达到国家规定的大学生体育和军事训练合格标准，身体健康、心理素质好。
（4）掌握文献检索、资料查询及运用现代信息技术获取相关信息的基本方法；（5）了解国内外信息技术的科技前沿及发展趋势，了解电子产品与系统的设计、生产过程及与之相关的政策和法津、法规；（6）掌握电子专业所需的数学、自然科学及其它人文科学知识（7）掌握各种电子元器件、电子系统设计与制造工艺的设计和研发能力，受到相关的物理、电子技术、计算机技术、电子制造工艺等方面的实验训练。
电子科技大学研究生算法设计与分析拟考题及答案评分细则（3）一、Please answer T or F for each of the following statements to indicate whether the statement is true or false1. The knapsack problem can be solved in polynomial time by using dynamic programming.( F )2. Some problems in NP can be solved in polynomial time.( T )3. To show a problem is NP-hard, we can reduce it to a well-known NP-Complete problem.( F )4. In an undirected graph, the value of the maximum flow between two vertices is equivalent to the value of the minimum cut between them. ( T )5. . ( F )二、Arrange the following functions in ascending asymptotic order of growth rate:，，，，.参考答案：f2，f3，f1，f4，f5三、Please answer the following questions:(a) What are the main steps of designing a dynamic programming algorithm?参考答案：1.定义子问题；2根据子问题建立递归关系式；3用自底而上的方式求解（建立储存表）。
(b) What are the main steps of proving the NP-Completeness of a problem?参考答案：1.证明该问题属于NP；2.选一个已知的NPC问题B；3.将问题B归约到该问题上。
第 1 页 共 8 页电子科技大学研究生试卷（考试时间： 至 ，共 小时）课程名称 算法分析与设计 教师 学时 学分 教学方式 考核日期 年 月 日 成绩 考核方式： （学生填写）一、判断下列陈述的对错（共20分，共 10题，每题2分）1. 一个计算问题的输入是n 个数字a 1，a 2，…，a n 。
如果这个问题存在一个运行时间为O(a n n 10)的算法，则这个问题可以在多项时间内被计算机求解。
( ╳ )2. 如果存在一个从问题A 到问题B 的多项式时间归约（Polynomial reduction ），且问题A 是NP 难的，则可知问题B 也是NP 难的。
( ╳ )3. 一个2倍的近似算法一定会有在一个问题上得到正好是最优解的两倍的解。
( ╳ )4. 如果存在一个NP 问题有多项式时间算法，则P=NP 。
( ╳ )5. 一个图上的最大网络流是唯一的。
( ╳ )6. 当图中的顶点个数是常数时，最大独立集问题（Maximum Independent Set Problem ）是多项式时间可解的. ( √ )7.这里有两个解决排序问题的分而治之算法：算法A 递归将需要排列的数字均分成2份，分别排序后再合并。
算法B 递归将需要排列的数字均分成3份，分别排序后再合并。
从渐进分析的角度来看，算法B 比算法A 要快。
(╳ )8. 在并行计算中，一个计算问题能在CREW PRAM 模型下O(n)处理器O(n 3)时间被解决，则也可以在EREW PRAM 模型下O(n)处理器O(n 3)时间被解决. (√ )9. 对于任意一个动态规划算法，其使用的空间一定不比它使用的时间要大。
(√ ) 10. 求一个图中两个点间最长路径的问题是属于NP 的，但是求一个图中两个点间最短路径的问题则不是属于NP 的。
(╳ )学 号 姓 名 学 院……………………密……………封……………线……………以……………内……………答……………题……………无……………效……………………第 2 页 共 8 页二、计算题（共9分，共3题，每题3分）1. 求如下有向图中的一个最长路径，要求给出路径和路径长度的值。
参考答案： CADB ，长度：40+30+35=1052. 如下可满足问题（SAT ）是否有解，若有解该如何给变量赋值：()()()()123123123123x xx x x x x x x x x x ∨∨∧∨∨∧∨∨∧∨∨。
参考答案：x1=1,x2=1,x 3=0或者x1=0,x2=0,x3=0，答案正确即可给分。
（说明：本题存在多种解，如x3=1, x1和x2中有一个0，这种情况还是有解。
只要任给出一种解就给分）3. 有一些区间段 (0,3), (2,4), (3,6), (5,7), (1,4), (3,5), (6,8),(7,9)，找出其中个数最多的一组相容的区间段（两个区间相容当且仅当两个区间的交集为空）。
参考答案：（0,3），（3,5），（5,7），（7,9）三、将下列函数按照渐进增长率由小到大进行排列，并给出你的判断依据： f 1(n )= 2014n 6 + 5n 4, f 2(n ) = n 2014 + 3n , f 3(n ) =f 4(n ) = log n + (2014log n )3, f 5(n ) = 2n +n !+5n , f 6(n ) = 3log(2n ) + loglog n , f 7(n ) = 2n log n +log n n . (7分) 参考答案和评分标准： 最终答案：f4 f6 f3 f1 f2 f5 f7 (3分，每个错误位置扣1分，扣完为止）判断依据如下：(1) θ (n6)(2) θ (3n) （1分）(3) θ (n1.007)(4) θ ( (log n)3) （1分，标准同上）(5) θ (n!)(6) θ (n) （1分，标准同上）(7) 2n log n+log n n. =θ (n n) （1分，标准同上）四、有一堆货物需要被运走，现在有四种运货车：推车的容量最小，小货车的容量是推车容量的2倍，中货车的容量是两辆小货车的容量加上一辆推车的容量，大货车的容量是一辆中货车的容量加上一辆小货车的容量再加上两辆推车的容量。
假设以上四种车的数量都非常多。
现在要求你设计一种方案派出最少辆车将货物全搬走，其中除了推车以外其它三种车都必须装满才能发车。
为这个问题设计一个算法，并证明该算法的正确性。
（8分）参考答案：用贪心算法：将车型按容量由大至小排列，能装满容量大的车就先装满发车，不行就考虑容量小一级的车。
证明：设我们算法给出的结果为，推车、小货车、中货车、大货车各a1，a2，a3，a4辆；而最优解是推车、小货车、中货车、大货车各b1，b2，b3，b4辆。
假设两个解结果不一样，设ai和bi不一样，且i是最大的。
如果i=4，则将两个中货车（或者4个小货车）换成一个大货车和一个推车，或者一个中货车和两个小货车（或者。
）换成一个大货车。
如果i=3，则两个小货车和一个推车换成一个中货车；。
如果i=2，两个推车换成一个小货车。
五、对某个输入大小为n的问题有如下四个分而治之算法：算法1将该问题分成2个子问题，子问题大小为n/3，将子问题的解合并得到上一级问题的解需要O(n)时间；算法2将该问题分成3个子问题，子问题大小为n/2，将子问题的解合并得到第 3 页共8 页上一级问题的解需要O(n)时间；算法3将该问题分成4个子问题，子问题大小为n/2，将子问题的解合并得到上一级问题的解需要O(n2)时间；算法4将该问题分成3个子问题，子问题大小为n-1，将子问题的解合并得到上一级问题的解需要O(1)时间。
请分析以上4个算法的运行时间。
（8分）参考答案：算法1运行时间为O（n）；（2分）算法2运行时间为O（n^(log23)）；（2分）算法3运行时间为O(n2logn) ；（2分）算法4运行时间为O(3n)。
（2分）六、求如下图中S和T间的最小割。
（8分）参考答案：16.第 4 页共8 页评分标准：说明计算该图从S到T的最大流（2分）给出第一个和增广路径（2分）后面任意两个增广路径（1分一个）最后答案16和这个cut [{S,A,B,C,D,E}, T] （3分，任给一个cut即可，最后结果16错误则不给分）七、证明：如果存在一个多项式时间算法判断一个图是否存在一个长度为k的路径，则存在一个多项式时间算法要么找到图中一个长度为k的路径要么证明此图不存在长度为k的路径。
（6分）参考答案：假设判断一个图是否存在一个长度为k的路径的多项时间算法为A，则我们可以用如下算法来找到图中一个长度为k的路径（或证明此图不存在长度为k的路径）：先用算法A判断这个图是否存在长度为k的路径，如果不存在则直接返回答案。
（2分）如果存在，则在图中删除一条边e，在用A来判断，如果这时还存在长度为k 的路径，则删除条边e，如果这时不存在长度为k的路径，则保留这条边e；以此用上面的方法来测试所有的边，直到最后剩下的就是一条长度为k的路径。
（4分）第 5 页共8 页第 6 页 共 8 页八、叙述带权重的点覆盖问题（Weighted Vertex Cover Problem ）的竞价法（PricingMethod ），并证明这个算法是个2倍近似算法。
（8分） 参考答案：竞价法（参考PPT 讲义） （5分） 2倍近似率的证明（参考PPT 讲义） （3分）九、为最大独立集问题建立一个整数规划模型。
（5分）参考答案： 目标函数： maxix ∑ （2分）条件：对每一条边ij ，1i j x x +≤， （2分） 对每个顶点i ，0,1i x =。
（1分）十、一个图中的一组边集A 满足如下性质则称A 为一个独立匹配：A 中任何两条边都没有公共顶点，任意两个来自A 中两条不同边的顶点之间都不存在一条边。
证明求一个图中最大独立匹配（含有最多条边的独立匹配）是NP 难的。
（提示：可以考虑利用最大独立集问题来构造归约） （5分） 参考答案：从最大独立集问题归约到最大独立匹配问题上：将最大独立集问题中的图G 构造最大独立匹配问题中的H ：对G 中任意一个顶点v 添加一个顶点v ’，而且v ’仅与v 相邻。
十一、 在（一）或者（二）中任选一题：（一）子集和问题定义如下：输入为一个有n 个正整数的集合A 和一个正整数k ，问是否存在A 的一个子集合其中所有元素之和正好等于k 。
为子集和问题设计一第 7 页 共 8 页个动态规划算法，并用你的算法对如下实例进行求解（要求画出表格）：A={1,2,5,6,7}，k=11. （10分） 参考答案：一种做法是用背包问题（Knapsack problem ）的动态规划算法来求解。
这里给出一种新的方法：定义子问题OPT(i)：如果存在A 的一个子集合其元素和正好等于i ，则OPT(i)=1，否则OPT(i)=0. （2分） 建立递归关系式：先定义x(i)：当A 中存在一个元素等于i 时，x(i)=1，否则x(i)=0. 则递归关系如下11(1),if 1()()(()()),if 1i j x i OPT i x i OPT i j OPT j i -==⎛= ∨∨-≠⎝ （4分） 实例的解为Yes 。
（4分）（二）系统中有M 个用户(U i , i=1,…,M)，每个用户的数据维度为N 维，d ij 表示第i 个用户的第j 维数据（i=1,…,M, j=1,…,N ），请用超递增序列技巧设计一个多维数据的聚合与解码方案，要求能够实现M 个用户对应维度数据的聚合与解码。
. （10分）给出正确的超递增序列（参考PPT 讲义）（3分） 能够正确地实现数据聚合（参考PPT 讲义）（3分） 能够正确地解码（参考PPT 讲义）（4分）十二、 在（一）或者（二）中任选一题：（一）问题A ：输入n 个数，求这n 个数中由小排到大第3位的那个数。
在EREW PRAM 模型下设计一个快速的并行算法，并分析算法的时间复杂度和工作复杂度。
（6分） 参考答案：设计出了算法给4分，若算法时间不是O(log n)，最多给2分。
给出时间复杂度O(log n)和工作复杂度O(n), 给2分。
（二）简述并行算法PCAM设计方法学的四个步骤；简述什么是人工神经网络；简述计算智能的三个研究领域。
（6分）参考答案：并行算法PCAM设计方法学的四个步骤：任务分解、通信设计、任务组合、处理器映射。
（每个0.5 分，共2分）人工神经网络是由具有适应性的简单单元组成的广泛并行互连的网络（1.5分），它的组织能够模拟生物神经系统对真实世界物体所作出的交互反应。
（1分）计算智能的三个领域：神经计算；模糊计算；进化计算。
