电子科技大学研究生算法设计与分析拟考题及答案评分细则(1)
更新时间:2024-04-14 23:47:01 阅读量: 综合文库 文档下载
- 电子科技大学研究生宿舍推荐度:
- 相关推荐
一、计算题或者简答题
1. 有一些区间段 (0,3), (1,4), (3,5), (6,8),(7,9),给出个数最多的一组相容的区间段(两个区间相容当且仅当两个区间的交集为空)。
2. 如下可满足问题(SAT)是否有解,若有解该如何给变量赋值: 3. 求如下有向图中的一个最长路径,要求给出路径和路径长度的值。
21 m 30 45 a 30 22 b 35 n
4.智能计算,并行计算概念
二、将下列函数按照渐进增长率由大到小进行排列,并给出你的判断依据:
三、有一堆货物需要被运走,现在有三种运货车:推车的容量最小,小货车的容
量是推车容量的2倍,大货车的容量是两辆小货车的容量加上一辆推车的容量。假设以上三种车的数量都非常多。现在要求你设计一种方案派出最少辆车将货物全搬走,其中除了推车以外其它三种车都必须装满才能发车。为这个问题设计一个算法,并证明该算法的正确性。 提示:贪心算法
四、求如下图中s和t间的最小割。
五、对某个输入为n的问题有如下四个分而治之算法:
算法1将该问题分成2个子问题,子问题大小为n/3,将子问题的解合并得到上一级问题的解需要O(n)时间;
算法2将该问题分成3个子问题,子问题大小为n/2,将子问题的解合并得到上一级问题的解需要O(n)时间; 算法3
第 1 页 共 2 页
六、为最大独立集问题建立一个整数规划模型。
七、一个图中的一组边集A满足如下性质则称A为一个独立匹配:A中任何两
条边都没有公共顶点,任意两个来自A中两条不同边的顶点之间都不存在一条边。证明求一个图中最大独立匹配(含有最多条边的独立匹配)是NP难的。(提示:可以考虑利用最大独立集问题来构造归约)
八、子集和问题定义如下:输入为一个有n个正整数的集合A和一个正整数k,
问是否存在A的一个子集合其中所有元素之和正好等于k。为子集和问题设计一个动态规划算法,并用你的算法对如下实例进行求解(要求画出表格):A={2,3,7,8,9},k=18.
九、叙述带权重的点覆盖问题(Weighted Vertex Cover Problem)的竞价法(Pricing
Method),并证明这个算法是个2倍近似算法。
竞价法(参考PPT讲义) 2倍近似率的证明(参考PPT讲义) 十、利用超递增序列设计多维数据的聚合与提取;
第 2 页 共 2 页
正在阅读:
电子科技大学研究生算法设计与分析拟考题及答案评分细则(1)04-14
劳模先进事迹材料(多篇)08-28
革命烈士纪念馆参观心得体会范文五篇08-16
matlab函数手册09-14
【最新修订版】VI对企业品牌形象价值提升的作用本科毕业论文设计40论文4104-27
40张动感的体育运动摄影作品02-09
小学生快乐的中秋节作文06-14
执行力培训课程大纲08-26
大数据在物流管理中的应用11-28
- 冀教版版五年级科学下册复习资料
- 微生物学复习提纲
- 2013—2014学年小学第二学期教研组工作总结
- 国有土地转让委托服务合同协议范本模板
- 我的固废说明书
- 企业管理诊断报告格式
- 东鼎雅苑施工组织设计
- 谈谈如何做好基层党支部书记工作
- 浮梁县环保局市级文明单位创建工作汇报
- 管理学基础知识
- 大学物理实验报告23 - PN结温度传感器特性1
- 计算机网络实践
- 酒桌上这四种情况下要坐牢,千万别不当回事……
- 国家康居示范工程建设技术要点
- 中国贴布行业市场调查研究报告(目录) - 图文
- 新课标下如何在高中物理教学中培养学生的创新能力初探
- 营养师冬季养生食谱每日一练(7月4日)
- 关注江西2017年第3期药品质量公告
- 建设海绵城市专题习题汇总
- 10万吨年环保净水剂建设项目报告书(2).pdf - 图文
- 考题
- 细则
- 算法
- 评分
- 研究生
- 答案
- 分析
- 设计
- 大学
- 电子
- 科技