全部科目 > 软件设计师 >
2017年上半年 上午试卷 综合知识
第 62 题
知识点 算法设计   迁移   实例  
关键词 时间复杂度   实例   算法  
章/节 计算机软件知识  
 
 
某汽车加工工厂有两条装配线L1和L2，每条装配线的工位数均为n（Sij，i=1或2，j= 1，2，...，n），两条装配线对应的工位完成同样的加工工作，但是所需要的时间可能不同（aij，i=1或2，j=1，2，...，n）。汽车底盘开始到进入两条装配线的时间 (e1，e2) 以及装配后到结束的时间(x1x2)也可能不相同。从一个工位加工后流到下一个工位需要迁移时间(tij，i=1或2，j=2，...n）。现在要以最快的时间完成一辆汽车的装配，求最优的装配路线。
分析该问题，发现问题具有最优子结构。以L1为例，除了第一个工位之外，经过第j个工位的最短时间包含了经过L1的第j-1个工位的最短时间或者经过L2的第j-1个工位的最短时间，如式(1)。装配后到结束的最短时间包含离开L1的最短时间或者离开L2的最短时间如式（2）。

由于在求解经过L1和L2的第j个工位的最短时间均包含了经过L1的第j-1个工位的最短时间或者经过L2的第j-1个工位的最短时间，该问题具有重复子问题的性质，故采用迭代方法求解。
该问题采用的算法设计策略是（62），算法的时间复杂度为（63）
以下是一个装配调度实例，其最短的装配时间为（64），装配路线为（65）
 
  A.  分治
 
  B.  动态规划
 
  C.  贪心
 
  D.  回溯




 
 
相关试题     计算机软件知识 

  第39题    2021年上半年  
对数组A=(2,8,7,1,3,5,6,4）构建大顶堆为( )(用数组表示)

  第11题    2024年上半年  
对下列有向图的邻接矩阵，进行深度遍历的次序是(  )。

  第64题    2012年上半年  
某货车运输公司有一个中央仓库和n个运输目的地，每天要从中央仓库将货物运输到所有的运输目的地，到达每个运输目的地一次且仅一次，最后回到中央仓库。在两个地点..

 
知识点讲解
· 算法设计
· 迁移
· 实例
 
        算法设计
        通常求解一个问题可能会有多种算法可供选择，选择的主要标准首先是算法的正确性和可靠性、简单性和易理解性；其次是算法所需要的存储空间更少和执行速度更快等。
        算法设计是一件非常困难的工作，通常设计一个"好"的算法应考虑达到正确性、可读性、健壮性、效率与低存储量需求等目标。
        经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪心法、回溯法、分治法和动态规划法等。
 
        迁移
        选择一个适当的迁移时间，最好定在单位事务不繁忙的时候（如周末）。事先做好系统软件和数据的备份，然后逐步将原有系统安装部署到新网络中，并做好相关设备的配置。要一边安装一边测试，注意不但要用管理员身份测试，还要用普通用户身份测试，以确保迁移后的系统与原有系统一致。
 
        实例
        某考务处理系统有如下功能：
        （1）对考生送来的报名单进行检查。
        （2）对合格的报名单进行检查。
        （3）对阅卷站送来的成绩清单进行检查，并根据考试中心指定的合格标准审定合格者。
        （4）制作考生通知单（内含成绩合格／不合格标志）送给考生。
        （5）按地区、年龄、文化程度、职业和考试级别等进行成绩分类统计和试题难度分析，产生统计分析表。
        该考务处理系统的分层数据流图如下图所示。
        
        考务处理系统分层数据流图



更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5
京公网安备 11010502032051号 | 营业执照
 Copyright ©2000-2025 All Rights Reserved
软考在线版权所有