免费智能真题库 > 历年试卷 > 软件设计师 > 2026年下半年 软件设计师 下午试卷 案例
  第3题      
  知识点:   数组   运输

 
设有n个货物要装入若干个容量为C的集装箱以便运输,这n个货物的体积分别为 {s1,s2,…,sn},且有Si<C(l <i<n)。为节省运输成本,用尽可能少的集装箱来装运这n个货物。
下面分别采用最先适宜策略和最优适宜策略来求解该问题。
最先适宜策略(firstfit)首先将所有的集装箱初始化为空,对于所有货物,按照所给的次序,每次将一个货物装入第一个能容纳它的集装箱中。
最优适宜策略(bestfit)与最先适宜策略类似,不同的是,总是把货物装到能容纳它且目前剩余容量最小的集装箱,使得该箱子装入货物后闲置空间最小。
【C代码】
下面是这两个算法的C语言核心代码。
(1)变量说明
n:货物数
C:集装箱容量
s:数组,长度为n,其中每个元素表示货物的体积,下标从0开始
b:数组,长度为n, b[i]表示第i+1个集装箱当前已经装入货物的体积,下标从0开始
i,j:循环变量
k:所需的集装箱数
min:当前所用的各集装箱装入了第i个货物后的最小剩余容量
m:当前所需要的集装箱数
temp:临时变量
(2)函数 firstfit



 
问题:3.1   根据【说明】和【C代码】,填充C代码中的空(1)〜(4)。
 
问题:3.2   根据【说明】和【C代码】,该问题在最先适宜和最优适宜策略下分别采用了(5)和(6)算法设计策略,时间复杂度分别为 (7) 和(8)(用0符号表示)。
 
问题:3.3   考虑实例n= 10, C= 10,各个货物的体积为{4,2,7,3,5,4,2,3,6,2}。该实例在最先适 宜和最优适宜策略下所需的集装箱数分别为(9)和(10)。考虑一般的情况,这两种求解策略能否确保得到最优解? (11)(能或否)
 
 
 

   知识点讲解    
   · 数组    · 运输
 
       数组
               数组的定义及基本运算
               n维数组是一种"同构"的数据结构,其每个元素类型相同、结构一致。数组是定长线性表在维数上的扩张,即线性表中的元素又是一个线性表。
               数组结构的特点是:数据元素数目固定;数据元素具有相同的类型;数据元素的下标关系具有上下界的约束且下标有序。
               对数组进行的基本运算有以下两种。
               (1)给定一组下标,存取相应的数据元素。
               (2)给定一组下标,修改相应的数据元素中某个数据项的值。
               数组的顺序存储
               一旦定义了数组,结构中的数据元素个数和元素之间的关系就不再发生变动,因此数组适合于采用顺序存储结构。
               由于计算机的内存结构是一维线性的,因此存储多维数组时必须按照某种方式进行降维处理,即将数组元素排成一个线性序列,这就产生了次序约定问题。对二维数组有两种存储方式:一种是以列为主序的存储方式;另一种是以行为主序的存储方式。
               设每个数据元素占用L个单元,m、n为数组的行数和列数,那么以行为主序优先存储的地址计算公式为
               Loc(aij)=Loc(a11)+((i-1)n+(j-1))L
               同样的,以列为主序优先存储的地址计算公式为
               Loc(aij)=Loc(a11)+((j-1)m+(i-1))L
 
       运输
        运输是物体借助运力在空间上产生的位置移动。我国国家标准《物流术语》对运输的定义是:“用设备和工具,将物品从一地点向另一地点运送的物流活动”。物流的运输创造着物流的空间效用,在存在空间背离的商品产地与销地之间搭建起连接的“桥梁”,使消费者或用户能够在当地买到所需商品。由于运输活动相对来讲时间长、距离远、能源动力消耗多,其成本在物流总成本中的比例高达50%以上。因而,运输成本降低的潜力大,无论在物流领域还是国民经济领域都占有举足轻重的位置,同时,运输在现代物流中又是一个最重要的子系统。
               运输的作用及意义
               运输的任务是对物资进行较长距离的空间移动。物流部门通过运输解决物资在生产地点和需要地点之间的空间距离问题,从而创造商品的空间效益,实现其使用价值,以满足社会需要。运输是物流的中心环节之一,可以说是物流最重要的一个功能。运输在经济上的作用是扩大了经济作用范围和在一定的经济范围内促进物价的平均化。现代化大生产的发展,社会分工越来越细,产品种类越来越多,无论是原材料的需求,还是产品的输出量,都大幅度上升,区域之间的物资交换更加频繁,这就促进运输业的发展和运输能力的提高,所以产业的发展促进了运输技术的革新和运输水平的提高。反之,运输手段的发达也是产业发展的重要支柱。例如现代钢铁企业每日需万吨以上铁矿石原料,往往是从几千公里甚至几万公里之外用大型货车运来,许多发达国家需要数万吨以至数亿万吨级油轮从国外输送石油,没有这样强有力的输送手段,许多大工业企业就难以存在,甚至国民经济也难以正常运转。
               运输方式及特点
               陆地、海洋和天空都可以作为运输活动的空间,根据运载工具的不同,运输的主要方式可以分为以下几种:
                      基于铁路的运输方式
                      它是陆地长距离运输的主要方式。由于其货车在固定轨道线路上行驶,可以自成系统,不受其他运输条件的影响,具有按时刻表运行,轨道行驶阻力小、不需频繁地启动制动、可重载高速运行及运输单位大等优点,从而使运费和劳务费降低。但由于在专用线路上行驶,而且车站之间距离比较远,缺乏机动性,此外,运输的起点和终点常常需要汽车进行转运,增加搬运次数。
                      铁路及其附属设施的建设需要国家投资,除了少数大型工厂和矿山有自己的支线外,一般企业只能利用公有铁路,铁道运输车辆主要有机车和货车车厢两种,货车车箱随用途而异,也有不同种类,化学品车、油罐车、集装箱车等。
                      基于公路的运输方式
                      它是最普及的一种运输方式,其最大优点是空间和时间方面具有充分的自由性,少受路线和停车站的约束,只要没有特别的障碍(如壕沟、过窄的通道等),汽车都可以到达。因此,可以实行从发货人到收货人之间门对门直达输送。由于减少了转运环节,货物包装可以简化,货物损伤、丢失和误送的可能性很小。购置汽车成本较低,一般企业都可以实现。自行运输和委托运输可以同时进行,由于自备车有充分的机动性,使用非常方便。
                      汽车运输的运输单位小,运输量和汽车台数与操作人员数成正比,产生不了大批量输送的效果。动力费和劳务费较高,特别是长距离输送中缺点较为显著。此外,由于在运行中司机自由意志起主要作用,容易发生交通事故,对人身、货物、汽车本身造成损失。由于汽车数量的增多,产生交通阻塞,使汽车运行困难,同时产生的废气、噪音也造成了环境污染。运货汽车种类很多,有卡车、厢式货车、拖车、冷藏车等专用货车,虽然大型化是发展趋势,但是小型货车的适用范围很广,今后仍然会保持大型货车和小型货车相结合的汽车运输体系。
                      基于水路的运输方式
                      有海运和内河航运两种。利用水路运送货物,在大批量和远距离的运输中价格便宜,可以运送超大型和超重物。运输线路主要利用自然的海洋与河流,不受道路的限制,在隔海的区域之间是代替陆地运输的必要方式。水上航行的速度比较慢、航行周期长,海上运输有时以几个月为周期,易受天气影响,航期不能保证,建设港湾也要花费高额费用。船舶按用途分类有专用船(如油轮、矿石船、冷冻船等),还有混装船、集装箱船;按装卸货物的方式有载货车辆可以直接开到船上的滚装船,还有无自行能力的船舶等。
                      基于航空的运输方式
                      它们主要优点是速度快。因为时间短,货物损坏少,特别适合一些保鲜物品的输送。但是航空运输的费用高,离机场距离比较远的地方利用价值不大。客运飞机可以利用下部货仓运送少部分货物。随着空运货物的增加,出现了专用货运机,采用单元装载系统,缩短装卸时间,保证“快”的特色。
                      基于管道的运输方式
                      自来水和城市的煤气的输配送是和人们生活最为密切相关的管道运输,它的主要优点是:基本没有运动部件,维修费便宜。管道一旦建成,可以连续不断地输送大量物资,不费人力,运输成本低。管道铺设可以不占用土地或占地较少。此外,具有安全、事故少、公害少等优点。管道运输的缺点是在输送地点和输送对象方面具有局限性。一般适用于气体、液体、天然气、石油等,但是也发展到粉粒体的近距离输送,如粮食、矿粉等,并且还研究了将轻便物体放在特定的密封存器内,在管道内利用空气压力进行输送.如书籍文件、实验样品的输送。随着技术的进步,输送对象的范围在不断扩大。管道的铺设有地面、地下和架空安装等方式。必要时中途要采用保温、加热、加压的措施,以保证管道的畅通。
                      多种方式联合运输
                      联合运输是综合利用某一区间中各种不同运输方式的优势进行不同运输方式的协作,使货主能够按一个统一的运输规章或制度,使用同一个运输凭证,享受不同运输方式综合优势的一种运输形式。联运的最低限度要求是两种不同运输方式进行两程的衔接运输。联合运输按地域划分有国际联运和国内联运两种,国内联运较为简单,国际联运是联合运输最高水平的体现。联合运输具有三个特点:一是具有组织运输的全程性,二是运程凭证的通用性,三是托运手续的简易性。
   题号导航      2026年下半年 软件设计师 下午试卷 案例   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
 
第3题    在手机中做本题