免费智能真题库 > 历年试卷 > 软件设计师 > 2012年上半年 软件设计师 上午试卷 综合知识
  第63题      
  知识点:   算法设计   运输
  关键词:   时间复杂度   算法        章/节:   计算机软件知识       

 
某货车运输公司有一个中央仓库和n个运输目的地,每天要从中央仓库将货物运输到所有的运输目的地,到达每个运输目的地一次且仅一次,最后回到中央仓库。在两个地点i和j之间运输货物存在费用cij。为求解旅行费用总和最小的运输路径,设计如下算法:首先选择离中央仓库最近的运输目的地1,然后选择离运输目的地1最近的运输目的地2,……,每次在未访问过的运输目的地中选择离当前运输目的地最近的运输目的地,最后回到中央仓库。则该算法采用了(63)算法设计策略,其时间复杂度为(64)。
 
 
  A.  分治
 
  B.  动态规划
 
  C.  贪心
 
  D.  回溯
 
 
 

 
  第62题    2022年下半年  
   28%
折半查找在有序数组A中查找特定的记录K:通过比较K和数组中的中间元素A[mid]进行,如果相等,则算法结束∶如果K小于[Amid],则对..
  第60题    2018年上半年  
   54%
现需要申请一些场地举办一批活动,每个活动有开始时间和结束时间。在同一个场地,如果一个活动结束之前,另一个活动开始,即两个..
  第62题    2015年下半年  
   63%
已知算法A的运行时间函数为T(n)=8T(n/2)+n2,其中n表示问题的规模,则该算法的时间复杂度为(62)。另已知算法B的运行..
   知识点讲解    
   · 算法设计    · 运输
 
       算法设计
        通常求解一个问题可能会有多种算法可供选择,选择的主要标准首先是算法的正确性和可靠性、简单性和易理解性;其次是算法所需要的存储空间更少和执行速度更快等。
        算法设计是一件非常困难的工作,通常设计一个"好"的算法应考虑达到正确性、可读性、健壮性、效率与低存储量需求等目标。
        经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪心法、回溯法、分治法和动态规划法等。
 
       运输
        运输是物体借助运力在空间上产生的位置移动。我国国家标准《物流术语》对运输的定义是:“用设备和工具,将物品从一地点向另一地点运送的物流活动”。物流的运输创造着物流的空间效用,在存在空间背离的商品产地与销地之间搭建起连接的“桥梁”,使消费者或用户能够在当地买到所需商品。由于运输活动相对来讲时间长、距离远、能源动力消耗多,其成本在物流总成本中的比例高达50%以上。因而,运输成本降低的潜力大,无论在物流领域还是国民经济领域都占有举足轻重的位置,同时,运输在现代物流中又是一个最重要的子系统。
               运输的作用及意义
               运输的任务是对物资进行较长距离的空间移动。物流部门通过运输解决物资在生产地点和需要地点之间的空间距离问题,从而创造商品的空间效益,实现其使用价值,以满足社会需要。运输是物流的中心环节之一,可以说是物流最重要的一个功能。运输在经济上的作用是扩大了经济作用范围和在一定的经济范围内促进物价的平均化。现代化大生产的发展,社会分工越来越细,产品种类越来越多,无论是原材料的需求,还是产品的输出量,都大幅度上升,区域之间的物资交换更加频繁,这就促进运输业的发展和运输能力的提高,所以产业的发展促进了运输技术的革新和运输水平的提高。反之,运输手段的发达也是产业发展的重要支柱。例如现代钢铁企业每日需万吨以上铁矿石原料,往往是从几千公里甚至几万公里之外用大型货车运来,许多发达国家需要数万吨以至数亿万吨级油轮从国外输送石油,没有这样强有力的输送手段,许多大工业企业就难以存在,甚至国民经济也难以正常运转。
               运输方式及特点
               陆地、海洋和天空都可以作为运输活动的空间,根据运载工具的不同,运输的主要方式可以分为以下几种:
                      基于铁路的运输方式
                      它是陆地长距离运输的主要方式。由于其货车在固定轨道线路上行驶,可以自成系统,不受其他运输条件的影响,具有按时刻表运行,轨道行驶阻力小、不需频繁地启动制动、可重载高速运行及运输单位大等优点,从而使运费和劳务费降低。但由于在专用线路上行驶,而且车站之间距离比较远,缺乏机动性,此外,运输的起点和终点常常需要汽车进行转运,增加搬运次数。
                      铁路及其附属设施的建设需要国家投资,除了少数大型工厂和矿山有自己的支线外,一般企业只能利用公有铁路,铁道运输车辆主要有机车和货车车厢两种,货车车箱随用途而异,也有不同种类,化学品车、油罐车、集装箱车等。
                      基于公路的运输方式
                      它是最普及的一种运输方式,其最大优点是空间和时间方面具有充分的自由性,少受路线和停车站的约束,只要没有特别的障碍(如壕沟、过窄的通道等),汽车都可以到达。因此,可以实行从发货人到收货人之间门对门直达输送。由于减少了转运环节,货物包装可以简化,货物损伤、丢失和误送的可能性很小。购置汽车成本较低,一般企业都可以实现。自行运输和委托运输可以同时进行,由于自备车有充分的机动性,使用非常方便。
                      汽车运输的运输单位小,运输量和汽车台数与操作人员数成正比,产生不了大批量输送的效果。动力费和劳务费较高,特别是长距离输送中缺点较为显著。此外,由于在运行中司机自由意志起主要作用,容易发生交通事故,对人身、货物、汽车本身造成损失。由于汽车数量的增多,产生交通阻塞,使汽车运行困难,同时产生的废气、噪音也造成了环境污染。运货汽车种类很多,有卡车、厢式货车、拖车、冷藏车等专用货车,虽然大型化是发展趋势,但是小型货车的适用范围很广,今后仍然会保持大型货车和小型货车相结合的汽车运输体系。
                      基于水路的运输方式
                      有海运和内河航运两种。利用水路运送货物,在大批量和远距离的运输中价格便宜,可以运送超大型和超重物。运输线路主要利用自然的海洋与河流,不受道路的限制,在隔海的区域之间是代替陆地运输的必要方式。水上航行的速度比较慢、航行周期长,海上运输有时以几个月为周期,易受天气影响,航期不能保证,建设港湾也要花费高额费用。船舶按用途分类有专用船(如油轮、矿石船、冷冻船等),还有混装船、集装箱船;按装卸货物的方式有载货车辆可以直接开到船上的滚装船,还有无自行能力的船舶等。
                      基于航空的运输方式
                      它们主要优点是速度快。因为时间短,货物损坏少,特别适合一些保鲜物品的输送。但是航空运输的费用高,离机场距离比较远的地方利用价值不大。客运飞机可以利用下部货仓运送少部分货物。随着空运货物的增加,出现了专用货运机,采用单元装载系统,缩短装卸时间,保证“快”的特色。
                      基于管道的运输方式
                      自来水和城市的煤气的输配送是和人们生活最为密切相关的管道运输,它的主要优点是:基本没有运动部件,维修费便宜。管道一旦建成,可以连续不断地输送大量物资,不费人力,运输成本低。管道铺设可以不占用土地或占地较少。此外,具有安全、事故少、公害少等优点。管道运输的缺点是在输送地点和输送对象方面具有局限性。一般适用于气体、液体、天然气、石油等,但是也发展到粉粒体的近距离输送,如粮食、矿粉等,并且还研究了将轻便物体放在特定的密封存器内,在管道内利用空气压力进行输送.如书籍文件、实验样品的输送。随着技术的进步,输送对象的范围在不断扩大。管道的铺设有地面、地下和架空安装等方式。必要时中途要采用保温、加热、加压的措施,以保证管道的畅通。
                      多种方式联合运输
                      联合运输是综合利用某一区间中各种不同运输方式的优势进行不同运输方式的协作,使货主能够按一个统一的运输规章或制度,使用同一个运输凭证,享受不同运输方式综合优势的一种运输形式。联运的最低限度要求是两种不同运输方式进行两程的衔接运输。联合运输按地域划分有国际联运和国内联运两种,国内联运较为简单,国际联运是联合运输最高水平的体现。联合运输具有三个特点:一是具有组织运输的全程性,二是运程凭证的通用性,三是托运手续的简易性。
   题号导航      2012年上半年 软件设计师 上午试卷 综合知识   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
7 /
8 /
9 /
10 /
11 /
12 /
13 /
14 /
15 /
 
16 /
17 /
18 /
19 /
20 /
21 /
22 /
23 /
24 /
25 /
26 /
27 /
28 /
29 /
30 /
 
31 /
32 /
33 /
34 /
35 /
36 /
37 /
38 /
39 /
40 /
41 /
42 /
43 /
44 /
45 /
 
46 /
47 /
48 /
49 /
50 /
51 /
52 /
53 /
54 /
55 /
56 /
57 /
58 /
59 /
60 /
 
61 /
62 /
63 /
64 /
65 /
66 /
67 /
68 /
69 /
70 /
71 /
72 /
73 /
74 /
75 /
 
第63题    在手机中做本题