黑龙江大学 计算机软件学院算法习题.docVIP

黑龙江大学 计算机软件学院算法习题.doc

  1. 1、本文档共4页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
黑龙江大学 计算机软件学院算法习题

Coursework 1 Exercise 1.3 (P5) Exercise 1.6 (P5) Please verify . (2) . (3) . (4) 4. (1)Write out the recurrence for quick sort. (2) Use a recursion tree to give an asymptotically tight solution to the recurrence you have given. (3) Verify your bound by the substitution method. Use the master method to give tight asymptotic bounds for the following recurrences. T(n)=4T(n/2)+n. T(n)=4T(n/2)+n2. T(n)=4T(n/2)+n3. Coursework 2 1.求一个非空集合中的最大的数。要求用分治策略设计算法并进行时间复杂度分析。 2.用分治策略设计一个算法,求二叉树中叶结点的个数。 3. 设计算法并证明: 给定一个由n个实数构成的集合S和另一个实数x,请设计一个在最坏情况下执行时间为O(n log n)的算法,使之能判断出S中是否存在两个和等于x的元素。 根据slides演示的过程设计一个PARTITION算法。(不用做) 根据slides演示的过程设计一个计数排序(Counting Sort)算法。(不用做) Coursework 3 设要计算矩阵连乘积A1 A2 A3 A4 矩阵 A1 A2 A3 A4 矩阵的阶 3(2 2(4 4(3 3(2 采用动态规划策略, 确定计算矩阵连乘积A1A2A3A4的一个计算次序,使得依此次序计算矩阵连乘积所需要的乘法次数最少。 计算矩阵连乘积A1A2A3A4所需要的最少乘法次数是多少?(10分)Coursework 4 1.用贪心策略设计一个算法,求解背包问题。 [背包问题:给定n种物品和一个背包,物品i的重量是w[i], 其价值是p[i], 背包的容量为c。设物品已按单位重量价值递减的次序排序。每种物品不可以装入背包多次,但可以装入部分的物品i。问应如何选择装入背包中的物品,使得背包的总价值最大?] 2.设有无数多个硬币,面值分别为1角、五分、二分和一分。请设计一个贪心算法,使得对于任意给定的面值为n分钱的纸币(n18分钱),能够将该纸币换为等值的最少个数的硬币,并输出每种面值硬币个数。要求: 说明所用的数据结构及其含义; 用C/C++程序设计语言或伪代码写出算法; 简要分析算法的时间复杂性。 设计算法实现优先队列(堆)的删除操作。 设计算法实现优先队列(堆)的插入操作。 5. 设有一个活动的集合S={1,2,…,11}如下表所示。其中[sj,fjj的起止时间,且f1≤f2≤…≤f11。li是Si ={j∈S | sj≥fli-1 }中具有最小结束时间fli的活动(设l0=0,f0=0)。设A是S的包含活动1的优化解。请写出每个li,并据此构造出S的包含活动1的优化解A。最后针对此例子说明贪心选择性。 活动集合S中活动的起止时间表 S 1 2 3 4 5 6 7 8 9 10 11 si 1 3 5 0 3 5 6 2 8 8 12 fi 4 5 6 7 8 9 10 11 12 13 14 6. 有一批集装箱要装上一艘载重量为c的轮船,其中集装箱i的重量为Wi。现要将尽可能多的集装箱装到轮船上。设集装箱已依其重量从小到大排序,(x1,x2,…,xn)x1=1。请证明(x2, x3,…, xn) Coursework 5 1.给出下图所示的四个顶点图所有3-着色法,要求画出可行解空间树。 2.考虑n=3时0-1背包问题的实例:W={30,20,20},P={100,60,60},C=40。当x[1]=1且x[2]=0时,计算Bound(3)。 3. 考虑n=3的批处理作业调度实例: tji 机器1 机器2 作业1 3 5 作业2 4 6 作业3 2 3 要求(1)画出该问题的解空间树; (2)写出该问题的剪枝策略(限界条件); (3)按回溯法有哪些信誉好的足球投注网站解空间树,并利用剪枝策略对应该剪掉的子树打(,最终给出该问题的解。 4. 所谓子集和问题是:给定由n个不同正数组成的集合W={wi| wi0,i=1,2,…,n}和正数M,要求找出N={1,2,…,n}的子集S。 (例如:给定n=4, W={11,13,24,7}和M=31,则相应的子集和问题的解是{3,4},{1,2,4}。) 1.考虑n=3的批处理作业调度实例: tji 机器1 机器2 作业1 3 5 作业2 4

文档评论(0)

asd522513656 + 关注
实名认证
文档贡献者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档