问题描述:在网络通信系统中,要将n个数据包依次分配给m个处理器进行数据处理,并要求处理器负载

界函数等必要的函数,并将此的数用于解圆排列问题.

圆排列问题描述如下:给定n个大小不等的圆,现要将这n个圆排进一个矩形框中,且要求各圆与矩形框的底边相切.圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列.例如,当n=3,且所给的3个圆的半径分别为1、1、2时,这3个圆的最小长度的圆排列见图5-9,其最小长度为.

算法设计:对于给定的n个圆,计算最小长度圆排列.

数据输入:由文件input.txt提供输入数据.文件的第1行是1个正整数n,表示有n个圆.第2行有n个正数,分别表示n个圆的半径.

结果输出:将计算的最小长度输出到文件output.txt.文件的第1行是最小长度,保留5位小数.

A.它是网络中一种能自动从一个节点发送到另一个节点的程序

B.它可以脱离计算机在网络上运行

C.它是一段能依附在其他程序上的代码

D.它对计算机系统没有危害，只会破坏网络通信

试题五（15分）

阅读以下说明，回答问题 1 至问题 2，将解答填入答题纸的对应栏内。

【说明】

“舰汇”公司是一家国际贸易公司，他们通过 EDI 系统实施贸易活动，其 EDI 标准采用的是美国国家标准ANSI X.12。 在ANSI X.12标准系统中， 订单交易组代码为850，订单标准号为 X.12.1。图 5-1 是该公司的一份纸质订单样式。

【问题 1】 （8 分）

要通过EDI 完成商务活动需要将纸质订单通过格式转换方式转换成 （1），再通过 （2） 将其转换成 （3）最后通过 （4） 将信息发往贸易伙伴。请从下列 A~D选项中选择正确的答案填写到答题纸对应位置。

A．翻译软件 B．平面文件 C．通信系统 D．EDI标准报文

【问题 2】 （7 分）

1．EDI 标准数据格式的三要素是数据元、数据段及标准报文格式。数据元是一个独立的最小信息单元，数据段是表达一组基本信息的单元。请以图 5-1 纸质订单中的地址信息（Large Town，N.Y.，10001）为例，说明该地址信息中数据元信息有 （5） 个，数据段信息是 （6） 。 （4 分）

2．若数据元间以“*”分隔，每个数据段始前只加表 5-1 所列段起始符，段终止符以“N/L”表示，请填写表 5-2 右列中的电子订单（EDI格式）的内容。 （3 分）

下面语句中，正确地描述了网络通信控制机制的是 （16） 。

（16）A. 在数据报系统中，发送方和接收方之间建立了虚拟通道，所有的通信都省略了通路选择的开销

B. 在滑动窗口协议中，窗口的滑动由确认的帧编号控制，所以可以连续发送多个帧

C. 在前向纠错系统中，由接收方检测错误，并请求发送方重发出错帧

D. 由于TCP 协议的窗口大小是固定的，无法防止拥塞出现，所以需要超时机制来处理网络拥塞的问题

数由连线矩阵conn给出.元件i和元件j之间的连线数为conn(i,j).如果将元件i安装在线路板上位置r处,而将元件j安装在线路板上位置s处,则元件i和元件j之间的距离为dist(r,s)确定了所给的n个元件的安装位置,就确定了一个布线方案.与此布线方案相应的布线成本为.试设计一个优先队列式分支限界法,找出所给n个元件的布线成本最小的布线方案.

算法设计:对于给定的n个元件,改计一个优先队列式分支限界法,计算最佳布线方案,使布线费用达到最小.

数据输入:由文件input.txt给出输入数据.第1行有1个正整数n(1≤n≤20).接下来的n-1行,每行n-1个数,表示元件i和元件j之间连线数(1≤i＜j≤20).

结果输出:将计算的最小布线费川以及相应的最佳布线方案输出到文件output.txt.

子是空闲的,有的格子则已经堆放了沉重的货物.由于堆放的货物很重,单凭仓库管理员的力量是无法移动的.仓库管理员有一项任务:要将一个小箱子推到指定的格子上去.管理员可以在仓库中移动,但不能跨过已经堆放了货物的格子.管理员站在与箱子相对的空闲格子上时,可以做一次推动,把箱子推到另一相邻的空闲格子.推箱时只能向管理员的对面方向推.由于要推动的箱子很重,仓库管理员想尽量减少推箱子的次数.

算法设计:对于给定的仓库布局,以及仓库管理员在仓库中的位置和箱子的开始位置和目标位置,设计一个解推箱子问题的分支限界法,计算出仓库管理员将箱子从开始位置推到目标位置所需的最少推动次数.

数据输入:由文件input.txt提供输入数据.输入文件第1行有2个正整数n和m(1≤n,m≤100).表示仓库是n×m个格子的矩形阵列.接下来有n行,每行有m个字符,表示格子的状态.

S——格子上放了不可移动的沉重货物;P——箱子的初始位置;

W——格子空闲:K——箱子的目标位置.

M——仓库管理员的初始位置:

结果输出:将计算的最少推动次数输出到文件output.txt.如果仓库管理员无法将箱子从开始位置推到目标位置则输出“NoSolution!".

试题三（15 分）

阅读下列说明，回答问题1 至问题4，将解答填入答题纸的对应栏内。

[说明]

软件系统几乎都是用事件触发来控制流程的，事件触发时的情景便形成了场景，而

同一事件不同的触发顺序和处理结果就形成事件流。场景法就是通过用例场景描述业务

操作流程，从用例开始到结束遍历应用流程上所有基本流（基本事件）和备选流（分支

事件）。下面是对某IC 卡加油机应用系统的基本流和备选流的描述。

[问题1]（5 分）

使用场景法设计测试案例，指出场景涉及到的基本流和备选流，基本流用字母A 表

示，备选流用题干中描述的相应字母表示。

[问题2]（4 分）

场景中的每一个场景都需要确定测试用例，一般采用矩阵来确定和管理测试用例。

如下表所示是一种通用格式，其中行代表各个测试用例，列代表测试用例的信息。本例

中的测试用例包含测试用例ID、场景/条件、测试用例中涉及的所有数据元素和预期结

果等项目。首先确定执行用例场景所需的数据元素（本例中包括账号、是否黑名单卡、

输入油量、账面金额、加油机油量），然后构建矩阵，最后要确定包含执行场景所需的

适当条件的测试用例。在下面的矩阵中，V 表示有效数据元素，I 表示无效数据元素，

n/a 表示不适用，例如C01 表示“成功加油”基本流。请按上述规定为其它应用场景设

计用例矩阵。

测试用例表

[问题3]（3 分）

假如每升油4 元人民币，用户的账户金额为1000 元，加油机内油量足够，那么在

A4 输入油量的过程中，请运用边界值分析方法为A4 选取合适的输入数据（即油量，单

位：升）。

[问题 4]（3 分）

假设本系统开发人员在开发过程中通过测试发现了20 个错误，独立的测试组通过

上述测试用例发现了100 个软件错误，系统在上线后，用户反馈了30 个错误，请计算

缺陷探测率（DDP）。

A.在数据报系统中，发送方和接收方之间建立了虚拟通道，所有的通信都省略了通路选择的开销

B.在滑动窗口协议中，窗口的滑动由确认的帧编号控制，所以可以连续发送多个帧

C.在前向纠错系统中，由接收方检测错误，并请求发送方重发出错帧

D.由于TCP协议的窗口大小是固定的，无法防止拥塞出现，所以需要超时机制来处理网络拥塞的问题

A.数据写入时被切割成N个数据块，大小相同

B.在ErasureCode存储模式下，系统最多支持N块硬盘失效

C.系统将N+M个数据块并行的存储于不同的硬盘中

D.每N个连续数据块通过ErasureCode算法计算出M个校验块