1、中级软件设计师下午试题-127 及答案解析(总分：99.98，做题时间：90 分钟)一、试题一(总题数：1，分数：25.00)说明 有一种游戏，其规则如下：有一个 33 的方格，每个方格中只可画“+”符号或“-”符号，表示该方格的值。图 1(a)定义了各方格的位置，下表为每个方格位置定义了与其相关联的位置集，各方格的初值如图 1(b)所示。游戏开始后，每次可选一个值为“+”的方格位置，然后根据表中将该位置所对应的每个相关联的位置上的符号重画成与其不同的符号，即将“+”重画成“-”，将“-”重画成“+”。重画操作可用所选的位置编号来描述。例如，在如图 1(b)所示的情况下，选择位置 4 时，重画
2、结果如图 1(c)所示。经过连续的若干次这样的操作后，当 33 方格呈现出如图 1(d)所示的图形时，表示获胜；当呈现出如图1(e)所示的图形时，表示失败。 图 2 所示的流程图旨在输出从初始状态出发直至获胜的重画操作(即所选的位置编号)序列。图中假定数组A08存放 33 方格的值，数组 c0815存放表中所示的各方格位置的相关联的位置集、数组d08存放各方格位置的相关联的位置个数，数组元素 S1Sk存放各次重画操作所对应的位置编号，变量 N 存放 33 方格中当前的“+”符号的个数。 （分数：24.99）(1).填充图 2 中的(1)(4)。（分数：8.33）_(2).应与 A、B、C 中的
3、哪一点连接?（分数：8.33）_(3).如果每次由游戏者选择方格改由程序自动枚举选择，那么为从初态出发求出所有可能的获胜重画操作序列，在哪些情况下需要进行回溯处理?（分数：8.33）_二、试题二(总题数：1，分数：25.00)1.说明 一个印制电路板的布线区域可分成 nm 个方格，如图 1(a)所示，现在需要确定电路板中给定的两个方格的中心点之间的最短布线方案。电路只能沿水平或垂直方向布线，如图 1(b)中虚线所示。为了避免线路相交，应将已布过线的方格作成封锁标记，其他线路不允许穿过被封锁的方格。 设给定印制电路板的起始方格 x 与目的方格 y 尚未布线，求这两个方格间最短布线方案的基本思路是
4、：从起始方格 x 开始，先考查距离起始方格距离为 k 的某一个可达方格就是目标方格 y 时为止，或者由于不存在从 x 到 y 的布线方案而终止。布线区域中的每一个方格与其相邻的上、下、左、右 4 个方格之间的距离为 1，依次沿下、右、上、左这 4 个方向考查，并用一个队列记录可达方格的位置。下表给出了沿这 4 个方向前进 1 步时相对于当前方格的相对偏移量。 沿 4 个方向前进 1 步时相对于当前方格的相对偏移量 搜索顺序 i 方向 行偏移量 列偏移量 0 上 -1 0 1 右 0 1 2 上 -1 0 3 左 0 -1 例如，设印制电路板的布线区域可划分为一个 68 的方格阵列，如图 2(a
5、)所示，其中阴影表示已封锁方格。从起始方格 x(位置3，2，标记为 0)出发，按照下、右、上、左的方向依次考查，所标记的可达方格如图 2(a)所示，目标方格为 y(位置4，7，标记为 10)，相应的最短布线路径如图 2(b)中虚线所示。 图 3 和图 4 所示的流程图即利用上述思路在电路板方格阵列中进行标记，图中使用的主要符号如下表所示。在图 3 中，设置电路板初始格局，即将可布线方格置为数值-1、已布线方格(即封锁方格)置为-9。设置方格阵列“围墙”的目的是省略方格位置的边界条件判定，方法是在四周附加格，并将其标记为-9(与封锁标记相同)。 （分数：25.00）_三、试题三(总题数：1，分数
6、：25.00)说明 某旅馆共有 N 间客房。每间客房的房间号、房间等级、床位数及占用状态分别存放在数组ROOM、RANK、NBED 和 STATUS 中。房间等级值为 1、2 或 3。房间的状态值为 0(空闲)或 1(占用)。客房是以房间(不是床位)为单位出租的。 本算法根据几个散客的要求预订一间空房。程序的输入为人数 M、房间等级要求 R(R=0 表示任意等级都可以)。程序的输出为所有可供选择的房间号。 （分数：24.99）(1).假设当前该旅馆各个房间的情况如下表所示。当输入 M=4，R=0 时，该算法的输出是什么? 当前该旅馆各个房间的情况 序号 i ROOM RANK NBED STA
7、TUS 1 101 3 4 0 2 102 3 4 1 3 201 2 3 0 4 202 2 4 1 5 301 1 6 0 （分数：8.33）_(2).如果等级为 R 的房间每人每天的住宿费为 RATE(R)，RATE 为数组。为使该算法在输出每个候选的房间号 RM(J)后，再输出这批散客每天所需的总住宿费 DAYRENT(J)，图中 B 所指框中的最后处应增加什么处理?（分数：8.33）_(3).如果限制该算法最多输出 K 个可供选择的房间号，则在图中 所指的判断框应改成什么处理?（分数：8.33）_四、试题四(总题数：1，分数：25.00)说明 0-1 背包问题可以描述为：有 n 个物
8、品，对 i=1，2，n，第 i 个物品价值为 v i ，重量为 w i (v i 和 w i 为非负数)，背包容量为 W(W 为非负数)，选择其中一些物品装入背包，使装入背包物品的总价值最大，即 ，且总重量不超过背包容量，即 （分数：25.00）(1).用回溯法求解此 0-1 背包问题，请填充下面伪代码中横线处的空缺。 回溯法是一种系统的搜索方法。在确定解空间后，回溯法从根节点开始，按照深度优先策略遍历解空间树，搜索满足约束条件的解。对每一个当前节点，若扩展该节点已经不满足约束条件，则不再继续扩展。为了进一步提高算法的搜索效率，往往需要设计一个限界函数，判断并剪枝那些即使扩展了也不能得到最优解
9、的节点。现在假设已经设计了 BOUND(v，W，k，W)函数，其中 v、w、k 和 W 分别表示当前已经获得的价值、当前背包的重量、已经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个节点，该函数值表示确定了部分物品是否选择之后，对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值，若该价值小于等于当前已经得到的最优解，则该节点无需再扩展。 下面给出 0-1 背包问题的回溯算法的伪代码。 函数参数说明如下。 W：背包容量；n：物品个数；w：重量数组；v：价值数组；fw：获得最大价值时背包的重量；fp：背包获得的最大价值；X：问题的最优解。 变量说明如下。 cw：当前的背包重量；
10、cp：当前获得的价值；k：当前考虑的物品编号；Y：当前已获得的部分解。 BKNAP(W, n, w, v, fw, fp, x) 1 cw cp 0 2 _ 3 fp -1 4 while true 5 while kn and cw+wkW do 6 _ 7 cp cp+vk 8 Yk 1 9 k k+1 10 if kn then 11 if fpcp then 12 fp cp 13 fw cw 14 k n 15 X Y 16 else Y(k) 0 17 while BOUND(cp, cw, k,Y)fp do 18 while k0 and Y(k)1 do 19 _ 20 if
11、 k=0 then return 21 Yk 0 22 cw cw - wk 23 cp op - vk 24 _（分数：12.50）_(2).考虑下表中所示的实例，假设有 3 个物品，背包容量为 22。下图是根据上述算法构造的搜索树，其中节点的编号表示了搜索树生成的顺序，边上的数字 1/0 分别表示选择/不选择对应物品。除了根节点之外，每个左孩子节点旁边的上、下两个数字分别表示当前背包的重量和已获得的价值，右孩子节点旁边数字表示扩展了该节点后最多可能获得的价值。为获得最优解，应该选择物品_，获得的价值为_。 （分数：12.50）_中级软件设计师下午试题-127 答案解析(总分：99.98，做
12、题时间：90 分钟)一、试题一(总题数：1，分数：25.00)说明 有一种游戏，其规则如下：有一个 33 的方格，每个方格中只可画“+”符号或“-”符号，表示该方格的值。图 1(a)定义了各方格的位置，下表为每个方格位置定义了与其相关联的位置集，各方格的初值如图 1(b)所示。游戏开始后，每次可选一个值为“+”的方格位置，然后根据表中将该位置所对应的每个相关联的位置上的符号重画成与其不同的符号，即将“+”重画成“-”，将“-”重画成“+”。重画操作可用所选的位置编号来描述。例如，在如图 1(b)所示的情况下，选择位置 4 时，重画结果如图 1(c)所示。经过连续的若干次这样的操作后，当 33
13、方格呈现出如图 1(d)所示的图形时，表示获胜；当呈现出如图1(e)所示的图形时，表示失败。 图 2 所示的流程图旨在输出从初始状态出发直至获胜的重画操作(即所选的位置编号)序列。图中假定数组A08存放 33 方格的值，数组 c0815存放表中所示的各方格位置的相关联的位置集、数组d08存放各方格位置的相关联的位置个数，数组元素 S1Sk存放各次重画操作所对应的位置编号，变量 N 存放 33 方格中当前的“+”符号的个数。 （分数：24.99）(1).填充图 2 中的(1)(4)。（分数：8.33）_正确答案：()解析：(1)Sk=i (2)N=N-1 (3)N=N+1 (4)A4=“-“(2
14、).应与 A、B、C 中的哪一点连接?（分数：8.33）_正确答案：()解析：应与 C 相连(3).如果每次由游戏者选择方格改由程序自动枚举选择，那么为从初态出发求出所有可能的获胜重画操作序列，在哪些情况下需要进行回溯处理?（分数：8.33）_正确答案：()解析：在以下情况下需要进行回溯处理。 (1)获胜。 (2)失败。 (3)出现了以前出现过的图形。 (4)一种图形的枚举选择完。二、试题二(总题数：1，分数：25.00)1.说明 一个印制电路板的布线区域可分成 nm 个方格，如图 1(a)所示，现在需要确定电路板中给定的两个方格的中心点之间的最短布线方案。电路只能沿水平或垂直方向布线，如图
15、1(b)中虚线所示。为了避免线路相交，应将已布过线的方格作成封锁标记，其他线路不允许穿过被封锁的方格。 设给定印制电路板的起始方格 x 与目的方格 y 尚未布线，求这两个方格间最短布线方案的基本思路是：从起始方格 x 开始，先考查距离起始方格距离为 k 的某一个可达方格就是目标方格 y 时为止，或者由于不存在从 x 到 y 的布线方案而终止。布线区域中的每一个方格与其相邻的上、下、左、右 4 个方格之间的距离为 1，依次沿下、右、上、左这 4 个方向考查，并用一个队列记录可达方格的位置。下表给出了沿这 4 个方向前进 1 步时相对于当前方格的相对偏移量。 沿 4 个方向前进 1 步时相对于当前
16、方格的相对偏移量 搜索顺序 i 方向 行偏移量 列偏移量 0 上 -1 0 1 右 0 1 2 上 -1 0 3 左 0 -1 例如，设印制电路板的布线区域可划分为一个 68 的方格阵列，如图 2(a)所示，其中阴影表示已封锁方格。从起始方格 x(位置3，2，标记为 0)出发，按照下、右、上、左的方向依次考查，所标记的可达方格如图 2(a)所示，目标方格为 y(位置4，7，标记为 10)，相应的最短布线路径如图 2(b)中虚线所示。 图 3 和图 4 所示的流程图即利用上述思路在电路板方格阵列中进行标记，图中使用的主要符号如下表所示。在图 3 中，设置电路板初始格局，即将可布线方格置为数值-1
17、、已布线方格(即封锁方格)置为-9。设置方格阵列“围墙”的目的是省略方格位置的边界条件判定，方法是在四周附加格，并将其标记为-9(与封锁标记相同)。 （分数：25.00）_正确答案：()解析：(1)i或 i (2)c或 c (3)d或 d (4)a或 a (5)h或 h三、试题三(总题数：1，分数：25.00)说明 某旅馆共有 N 间客房。每间客房的房间号、房间等级、床位数及占用状态分别存放在数组ROOM、RANK、NBED 和 STATUS 中。房间等级值为 1、2 或 3。房间的状态值为 0(空闲)或 1(占用)。客房是以房间(不是床位)为单位出租的。 本算法根据几个散客的要求预订一间空房
18、。程序的输入为人数 M、房间等级要求 R(R=0 表示任意等级都可以)。程序的输出为所有可供选择的房间号。 （分数：24.99）(1).假设当前该旅馆各个房间的情况如下表所示。当输入 M=4，R=0 时，该算法的输出是什么? 当前该旅馆各个房间的情况 序号 i ROOM RANK NBED STATUS 1 101 3 4 0 2 102 3 4 1 3 201 2 3 0 4 202 2 4 1 5 301 1 6 0 （分数：8.33）_正确答案：()解析：101，301(2).如果等级为 R 的房间每人每天的住宿费为 RATE(R)，RATE 为数组。为使该算法在输出每个候选的房间号 R
19、M(J)后，再输出这批散客每天所需的总住宿费 DAYRENT(J)，图中 B 所指框中的最后处应增加什么处理?（分数：8.33）_正确答案：()解析：RATE(RANK(I) * MDAYRENT(J)或 M * RATE(RANK(I)DAYRENT(J)(3).如果限制该算法最多输出 K 个可供选择的房间号，则在图中 所指的判断框应改成什么处理?（分数：8.33）_正确答案：()解析：IN OR J=K 其中，IN 也可以写成 I=N+1；J=K 也可以写成 JK。四、试题四(总题数：1，分数：25.00)说明 0-1 背包问题可以描述为：有 n 个物品，对 i=1，2，n，第 i 个物品
20、价值为 v i ，重量为 w i (v i 和 w i 为非负数)，背包容量为 W(W 为非负数)，选择其中一些物品装入背包，使装入背包物品的总价值最大，即 ，且总重量不超过背包容量，即 （分数：25.00）(1).用回溯法求解此 0-1 背包问题，请填充下面伪代码中横线处的空缺。 回溯法是一种系统的搜索方法。在确定解空间后，回溯法从根节点开始，按照深度优先策略遍历解空间树，搜索满足约束条件的解。对每一个当前节点，若扩展该节点已经不满足约束条件，则不再继续扩展。为了进一步提高算法的搜索效率，往往需要设计一个限界函数，判断并剪枝那些即使扩展了也不能得到最优解的节点。现在假设已经设计了 BOUND
21、(v，W，k，W)函数，其中 v、w、k 和 W 分别表示当前已经获得的价值、当前背包的重量、已经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个节点，该函数值表示确定了部分物品是否选择之后，对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值，若该价值小于等于当前已经得到的最优解，则该节点无需再扩展。 下面给出 0-1 背包问题的回溯算法的伪代码。 函数参数说明如下。 W：背包容量；n：物品个数；w：重量数组；v：价值数组；fw：获得最大价值时背包的重量；fp：背包获得的最大价值；X：问题的最优解。 变量说明如下。 cw：当前的背包重量；cp：当前获得的价值；k：当前考虑的物
22、品编号；Y：当前已获得的部分解。 BKNAP(W, n, w, v, fw, fp, x) 1 cw cp 0 2 _ 3 fp -1 4 while true 5 while kn and cw+wkW do 6 _ 7 cp cp+vk 8 Yk 1 9 k k+1 10 if kn then 11 if fpcp then 12 fp cp 13 fw cw 14 k n 15 X Y 16 else Y(k) 0 17 while BOUND(cp, cw, k,Y)fp do 18 while k0 and Y(k)1 do 19 _ 20 if k=0 then return 21 Yk 0 22 cw cw - wk 23 cp op - vk 24 _（分数：12.50）_正确答案：()解析：k0 cwcw+wk YkXk kk+1(2).考虑下表中所示的实例，假设有 3 个物品，背包容量为 22。下图是根据上述算法构造的搜索树，其中节点的编号表示了搜索树生成的顺序，边上的数字 1/0 分别表示选择/不选择对应物品。除了根节点之外，每个左孩子节点旁边的上、下两个数字分别表示当前背包的重量和已获得的价值，右孩子节点旁边数字表示扩展了该节点后最多可能获得的价值。为获得最优解，应该选择物品_，获得的价值为_。 （分数：12.50）_正确答案：()解析：2 18 15 4
