1、软件设计师-程序流程图及答案解析(总分：46.00，做题时间：90 分钟)一、B试题一/B(总题数：1，分数：15.00)1.【说明】一个印刷电路板的布线区域可分成 nm 个方格，如图 4-1(a)所示，现在需要确定电路板中给定的两个方格的中心点之间的最短布线方案。电路只能沿水平或垂直方向布线，如图 4-1 (b)中虚线所示。为了避免线路相交，应将已布过线的方格做成封锁标记，其他线路不允许穿过被封锁的方格。设给定印刷电路板的起始方格 x 与目的方格 y 尚未布线，求这两个方格间最短布线方案的基本思路是：从起始方格 x 开始，考查与起始方格距离为 k 的某一个可达方格是目标方格 y 时为止，或者
2、由于不存在从 x到 y 的布线方案而终止。布线区域中的每一个方格与其相邻的上、下、左、右 4 个方格之间的距离为 1，依次沿下、右、上、左这 4 个方向考查，并用一个队列记录可达方格的位置。表 4-1 给出了沿这 4 个方向前进 1 步时相对于当前方格的相对偏移量。B表 4-1 相对偏移量/B 搜索顺序 i 方 向 行偏移量 列偏移量0 上 -1 01 右 0 12 上 -1 03 左 0 -1例如，设印刷电路板的布线区域可划分为一个 68 的方格阵列，如图 4-2(a)所示，其中阴影表示已封锁方格。从起始方格 x(位置3，2，标记为 0)出发，按照下、右、上、左的方向依次考查，所标记的可达方
3、格如图 4-2(a)所示，目标方格为 y)位置4，7，标记为 10)，相应的最短布线路径如图 4-2(b)虚线所示。如图 4-3 和图 4-4 所示的流程图即利用上述思路，在电路板方格阵列中进行标记，图中使用的主要符号如表 4-2 所示。在图 4-4 中，设置电路板初始格局，即将可布线方格置为数值-1、已布线方格(即封锁方格)置为-9。设置方格阵列“围墙”的目的是省略方格位置的边界条件判定，方法是在四周附加格，并将其标记为-9(与封锁标记相同)。B表 4-2 主要符号/B符 号 含 义Grid 全局二维数组 GridN+2，M+2，表示电路板方格阵列，初始时数组元素Gridi，j的值为-1 表
4、示当前方格可布线，为-9 表示前方格不可布线offset 一维数组 offset4:offseti(0I3)的分量为 r(行偏移景)和 c(列偏移量)，按照表 4-1 的内容设置其值Startpos、Endpos、Cuapos、T分别表示起始方格、目标方格、当前方格和临时方格，其位置用分量度row 和 col 确定Q.insen(s) 将方格 s 的位置信息加入队列Q.delete() 删除非空队列的队头元素，并返回该元素Q.emply() 若队列 Q 为空，则返回 true；否则返回 false供选择的答案：aFoundtrue bFound=truecT=EndPos dQ.insert(
5、T)eTQ.delete() fCurPos=EndPosgi （分数：15.00）_二、B试题二/B(总题数：3，分数：15.00)2.【问题 1】假设当前该旅馆各个房间的情况如表 4-3 所示。B表 4-3 旅馆各房间情况/B 序号 1 ROOM RANK NBED STATUS1 101 3 4 02 102 3 4 13 201 2 3 04 202 2 4 15 301 1 6 0当输入 M=4，R=0 时，该算法的输出是什么?（分数：5.00）_3.【问题 2】 如果等级为 R 的房间每人每天的住宿费为 RATE(R)，RATE 为数组。为使该算法在输出每个候选的房间号 RM(J)
6、后，再输出这批散客每天所需的总住宿费 DAYRENT(J)，图 4-5 的 所指框中的最后处应增加什么处理?（分数：5.00）_4.【问题 3】 如果限制该算法最多输出 K 个可供选择的房间号，则在图 4-5 的 所指的判断框应改成什么处理? （分数：5.00）_三、B试题三/B(总题数：4，分数：16.00)5.【问题 1】 填充流程图中的判断条件。（分数：4.00）_6.【问题 2】 写出子程序 A 的功能，并顺序写出实现该功能的操作。（分数：4.00）_7.【问题 3】 写出子程序 B 的功能，并顺序写出实现该功能的操作。（分数：4.00）_8.【问题 4】 中缀表达式(A+B-C*D)
7、*(E-F)/G 经该流程图处理后的输出是什么? （分数：4.00）_软件设计师-程序流程图答案解析(总分：46.00，做题时间：90 分钟)一、B试题一/B(总题数：1，分数：15.00)1.【说明】一个印刷电路板的布线区域可分成 nm 个方格，如图 4-1(a)所示，现在需要确定电路板中给定的两个方格的中心点之间的最短布线方案。电路只能沿水平或垂直方向布线，如图 4-1 (b)中虚线所示。为了避免线路相交，应将已布过线的方格做成封锁标记，其他线路不允许穿过被封锁的方格。设给定印刷电路板的起始方格 x 与目的方格 y 尚未布线，求这两个方格间最短布线方案的基本思路是：从起始方格 x 开始，考
8、查与起始方格距离为 k 的某一个可达方格是目标方格 y 时为止，或者由于不存在从 x到 y 的布线方案而终止。布线区域中的每一个方格与其相邻的上、下、左、右 4 个方格之间的距离为 1，依次沿下、右、上、左这 4 个方向考查，并用一个队列记录可达方格的位置。表 4-1 给出了沿这 4 个方向前进 1 步时相对于当前方格的相对偏移量。B表 4-1 相对偏移量/B 搜索顺序 i 方 向 行偏移量 列偏移量0 上 -1 01 右 0 12 上 -1 03 左 0 -1例如，设印刷电路板的布线区域可划分为一个 68 的方格阵列，如图 4-2(a)所示，其中阴影表示已封锁方格。从起始方格 x(位置3，2
9、，标记为 0)出发，按照下、右、上、左的方向依次考查，所标记的可达方格如图 4-2(a)所示，目标方格为 y)位置4，7，标记为 10)，相应的最短布线路径如图 4-2(b)虚线所示。如图 4-3 和图 4-4 所示的流程图即利用上述思路，在电路板方格阵列中进行标记，图中使用的主要符号如表 4-2 所示。在图 4-4 中，设置电路板初始格局，即将可布线方格置为数值-1、已布线方格(即封锁方格)置为-9。设置方格阵列“围墙”的目的是省略方格位置的边界条件判定，方法是在四周附加格，并将其标记为-9(与封锁标记相同)。B表 4-2 主要符号/B符 号 含 义Grid 全局二维数组 GridN+2，M
10、+2，表示电路板方格阵列，初始时数组元素Gridi，j的值为-1 表示当前方格可布线，为-9 表示前方格不可布线offset 一维数组 offset4:offseti(0I3)的分量为 r(行偏移景)和 c(列偏移量)，按照表 4-1 的内容设置其值Startpos、Endpos、Cuapos、T分别表示起始方格、目标方格、当前方格和临时方格，其位置用分量度row 和 col 确定Q.insen(s) 将方格 s 的位置信息加入队列Q.delete() 删除非空队列的队头元素，并返回该元素Q.emply() 若队列 Q 为空，则返回 true；否则返回 false供选择的答案：aFoundtr
11、ue bFound=truecT=EndPos dQ.insert(T)eTQ.delete() fCurPos=EndPosgi （分数：15.00）_正确答案：()解析：(1)i或 i (2)c或 c (3)d或 d (4)a或 a (5)h或 h 分析 该流程实现的功能是为印刷电路板选择布线路径，路经中的每一小步都只能走垂直线或水平线，而且要求得到的路径是最短路径。 图4-3 是该算法的整体流程，包含了变量的初始化及输入输出，以及调用了子过程 findPath。findPath 子过程才是关键的处理(如图 4-4 所示)。 findPath 中，先设置 offset 数组的元素值，并创建
12、空队列。然后将当前位置 CurPos 置为起始位置 StartPos，并将标记 Found 置为 false，表示当前还没找到路径，接着将当前方格置为 0 (Grid 数组中的对应元素)，表示起始点。进入循环，将 i 赋初值为 0，从接着的判定的条件 i 4 及 offseti.r 可以断定，变量 i 就是表 4-1 中的“搜索顺序 i”，所以紧接着的语句“T.rowCurPos.row+offseti.r”和“T.colCurPos.col+offseti.c”就是求下一个要走的单元格(临时方格 T)的行坐标和列坐标。然后是判定(1)，若不成立，则直接将 i 加 1，向另一个方向继续搜索，意
13、味着临时方格 T 不能布线(值为-9)或已经判断过(值大于等于 0)；若成立，则将临时方格置为当前方格值加 1，表示到起始方格的距离增加 1，亦即可以布线且尚未判断过。根据题述，方格的初始值为-1 表示可以布线，故判定(1)应为“GridT.row,T.col =-1”，即选项 i。 接着是判定(2)，若成立则执行语句“Foundtrue”，意味着找到了解，即临时方格已经是目标方格。故判定(2)应为“T=EndPos”，即选项c。判定(2)不成立时，执行加工(3)，这里应该是入队操作，将临时方格入队，故加工(3)应为“Q.insert(T)”，即选项 d。接着将 i 值加 1，继续搜索。 当判
14、定“i4 且 Found=false”不成立时，有两种情况：一种是 i=4，另一种是 Found=true。判定(4)若不成立返回 true，意味着找到了解，故判定(4)应为“Foundtrue”，即选项 a。这样，若判定(4)成立，意味着 i=4，即 4 个方向均已搜索，接着判断队列是否为空，若非空，则出队继续查找，进程(5)自然是出队操作了，但是出队给哪个变量呢?是临时方格 T 还是当前方格 CurPos?其实很容易判断，从最近的语句“T.rowCurPos.row+offseti.r”和“T.colCurPos.col+offseti.c”可得应为当前方格 CurPos，故应为“CurP
15、osQ.delete()”，即选项 h。二、B试题二/B(总题数：3，分数：15.00)2.【问题 1】假设当前该旅馆各个房间的情况如表 4-3 所示。B表 4-3 旅馆各房间情况/B 序号 1 ROOM RANK NBED STATUS1 101 3 4 02 102 3 4 13 201 2 3 04 202 2 4 15 301 1 6 0当输入 M=4，R=0 时，该算法的输出是什么?（分数：5.00）_正确答案：()解析：101，301。3.【问题 2】 如果等级为 R 的房间每人每天的住宿费为 RATE(R)，RATE 为数组。为使该算法在输出每个候选的房间号 RM(J)后，再输出
16、这批散客每天所需的总住宿费 DAYRENT(J)，图 4-5 的 所指框中的最后处应增加什么处理?（分数：5.00）_正确答案：()解析：RATE(RANK(I)* MDAYRENT(J)或 M* RATE(RANK(I)DAYRENT(J)4.【问题 3】 如果限制该算法最多输出 K 个可供选择的房间号，则在图 4-5 的 所指的判断框应改成什么处理? （分数：5.00）_正确答案：()解析：IN OR J=K，其中，IN 也可以写成 I=N+1；J=K 也可以写成 JK。 分析 问题 1 比较简单，“输入 M=4，R=0”表示散客人数为 4，房间等级任意。对照旅馆各房间的情况表，易得满足条
17、件的房间号有：101 和 301，算法的输出正是可供选择的房间号，故算法的输出应该为：“101，301”。 根据题设，每天的住宿费 DAYRENT(J)应为散客数 M 与对应房间(等级为 r)的每人每天住宿费 RATE(r)的乘积。问题就是 r 是多少呢?是用户输入的“R”吗?显然可以排除这种情况，因为 R 可以为 0。仔细地分析可得，r 应为“RANK(I)”。故应增加“RATE(RANK(I)*M DAYRENT(J)”。需要注意的一点是，将变量 A 赋值 V 的写法如下：VA，而不是 C 语言的习惯：A=V。在流程图中，等号“=”就表示“等于”。 仔细分析可得，变量 I 是用来计数旅馆房
18、间的，变量 J 是用来计数满足条件的房间数的。 所指的判断框成立时输出结果，因此应改成：IN OR J=K。三、B试题三/B(总题数：4，分数：16.00)5.【问题 1】 填充流程图中的判断条件。（分数：4.00）_正确答案：()解析：PRIOR(INi):PRIOR(Sp)6.【问题 2】 写出子程序 A 的功能，并顺序写出实现该功能的操作。（分数：4.00）_正确答案：()解析：功能：将当前符号 INi入栈。 操作：P+1P INiSp7.【问题 3】 写出子程序 B 的功能，并顺序写出实现该功能的操作。（分数：4.00）_正确答案：()解析：功能：出栈(将栈顶元素送往数组 POLISH
19、) 操作：k+1k SpPOLISHk p-1p8.【问题 4】 中缀表达式(A+B-C*D)*(E-F)/G 经该流程图处理后的输出是什么? （分数：4.00）_正确答案：()解析：AB+CD*-EP-*G/ 分析 流程图中借助栈 S(其实是数组，栈顶 p 指向最后一个元素)，相应的栈操作如下。进栈：p+1p、入栈元素Sp：出栈：Sp栈元素变量、p-1p：栈空条件：p=0。 流程图中采用了 3 个下标变量 k、p、i，容易判断 i 是输入数组 IN的下标，k 是输出数组 POLISH的下标，p 是栈 S的栈顶下标。 整个循环结束的条件是遇到空格字符，即表示中缀表达式结束。然后根据 Si的不同
20、进行不同的操作。 是变量，则将变量保存到输出数组中。 是左括号，则调用 A(A 未知，这正是难点所在)。 是右括号，则循环调用 B，直到栈顶元素是左括号，意味着需要修改栈顶指针；将 p-1P，即进行一次出栈操作，但不关心栈顶元素，其实此时栈顶元素就是左括号。 是运算符，首先判断栈是否为空，若空则直接调用 A；若非空，则进行某种大小比较(判定(1)，这里容易想到是进行优先级比较)，当小于等于时调用 B，继续判断下一个栈顶元素，否则调用 A。 从对右括号的处理可得，左括号一定要入栈，也就是说 A 一定包含左括号入栈操作；B 含义出栈操作，栈顶元素做何种处理待定。再结合输出结果前的一个循环：循环调用 B 直到栈空。如果输入中缀式正确的话，此时栈中不可能含有括号，只可能含有运算符，因此应该是将剩余运算符送入输出数组 POLISH中。这就是对栈顶元素的处理。 判定(1)猜想是进行优先级比较：将当前运算符与栈顶元素进行比较，若当前元素优先级高()，则不出栈，将当前运算符入栈；否则()，出栈并处理栈顶元素，再将当前运算符入栈。 至于问题 4，则比较容易，只要知道后缀式的含义就能解答。
