1、程序员-流程图类及答案解析(总分：75.00，做题时间：90 分钟)一、B试题一/B(总题数：1，分数：15.00)阅读下列算法说明和流程图，将应填入(n)处的字句写在对应栏内。【算法说明】本算法按照算符优先关系，实现对算术四则混合运算表达式(可含小括号)的求值。处理对象是以字符串形式给出的、语法正确且不含变量的整数表达式。算符优先关系见表 5.1(1，2 为按顺序出现的两个运算符)B 表 5.1/B 1，2 + - （ ） + - * / ( ) # 说明：“#”是假设的表达式开始符和结束符，不可用。为实现算法，使用了两个堆栈分别寄存运算符和运算数(中间结果值)。算法基本思路如下：首先置操作
2、数栈 S1 为空，表达式起始符“#”设为运算符栈 S2 的栈底元素；依次读入表达式的各符号，若是数字字符则连接在一起转换为 int 型操作数进 S1 栈；若是运算符2，则和 S2 栈的栈顶运算符 51 比较优先级后作相应操作，直至整个表达式求值结束。算法流程图 5.1 如下：【问题】请将流程图补充完整。（分数：15.00）(1).（分数：3.00）_(2).（分数：3.00）_(3).（分数：3.00）_(4).（分数：3.00）_(5).（分数：3.00）_二、B试题二/B(总题数：1，分数：15.00)阅读下列算法说明和算法流程，将应填入(n)处的字句写在对应栏内。【算法说明】程序实现了常
3、见的猜数字游戏。游戏开始时由程序自动产生一个 1 到 100 的随机数，接收用户输入，并给出提示信息，直至用户猜对。用户猜对后，显示猜测次数，并提供“重新开始”和“退出”功能。算法采用两层循环实现。外层循环采用 do-while 循环，由循环条件控制是否重新开始。内层采用 for 循环，用于判断用户的每次输入。m 是随机产生的整数，键盘输入是字符串类型变量，n 是整型变量。【问题 1】内循环还需要一个变量，其作用为(1)。【问题 2】请将流程图 5.2 补充完整。（分数：15.00）(1).（分数：3.00）_(2).（分数：3.00）_(3).（分数：3.00）_(4).（分数：3.00）_
4、(5).（分数：3.00）_三、B试题三/B(总题数：1，分数：15.00)阅读下列算法说明和算法，将应填入(n)处的字句写在对应栏内。（分数：15.00）(1).（分数：3.00）_(2).（分数：3.00）_(3).（分数：3.00）_(4).（分数：3.00）_(5).（分数：3.00）_四、B试题四/B(总题数：1，分数：15.00)阅读下列算法说明和算法，将应填入(n)处的字句写在答卷的对应栏内。【算法说明】某英汉词典文件包含 N 个记录(N1)，每个记录有两个字段：一个是英文单词，另一个是相应的汉语解释。各个记录按英文单词的词典顺序排列，各英文单词并不重复。本算法用于维护、更新该英
5、汉词典文件。维护、更新的方法是：首先输入一个英文单问及其汉语解释，然后在该词典中查找输入的英文单词，若找到，则用输入的汉语解释更新原有的解释；若找不到，则需要将输入的英文单词及其汉语解释插入到该词典的适当位置，使各记录仍按英文单词的词典顺序排列。【算法】第一步读入英汉词典文件，并将读入的 N 个英文单词依次存放在字符串数组 ENGLISH 中，将相应的汉语解释依次存放在字符串数组 CHN 中。数组元素 CHN(i)给出了数组元素 ENGLISH(i)的解释。第二步输入英文单词及其汉语解释，将它们分别存放在字符串变量 E 和 C 中。若 E 为空串或都是空格，则转向第四步。第三步根据变量 E 的
6、值，用二分法在数组 ENGLISH 中查找。具体步骤如下：11L，NH 2INT(L+H)/2)K3若 E=ENGLISH(K)，则 C(1)，转向第二步若 EENGLISH(K)，则 K-1H；若 EENGLISH(K)，则 K+1(2)4若 HL 则对 I=N，L，-1(始值，终值，增量)循环执行：ENGLISH(1)ENGLISH(I+1)CHN(I)CHN(I+1)然后，将 E 和 C 分别存入(3)和(4)，N+1N 最后转向第二步否则，转向(5)第四步将数组 ENGLISH 和 CHN 输出，形成新的英汉词典文件，算法结束。（分数：15.00）(1).（分数：3.00）_(2).（
7、分数：3.00）_(3).（分数：3.00）_(4).（分数：3.00）_(5).（分数：3.00）_五、B试题五/B(总题数：1，分数：15.00)阅读下列说明、流程图和算法，将应填入(n)处的字句写在对应栏内。【流程图说明】下图所示的流程图 5.3 用 N-S 盒图形式描述了数组 Array 中的元素被划分的过程。其划分方法；以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于 Arrayi，并且数组中下标小于 i 的元素的值均小于基准数，下标大于 i的元素的值均大于基准数。设数组 A 的下界为 low，上界为 hi
8、gh，数组中的元素互不相同。（分数：15.00）(1).（分数：3.00）_(2).（分数：3.00）_(3).（分数：3.00）_(4).（分数：3.00）_(5).（分数：3.00）_程序员-流程图类答案解析(总分：75.00，做题时间：90 分钟)一、B试题一/B(总题数：1，分数：15.00)阅读下列算法说明和流程图，将应填入(n)处的字句写在对应栏内。【算法说明】本算法按照算符优先关系，实现对算术四则混合运算表达式(可含小括号)的求值。处理对象是以字符串形式给出的、语法正确且不含变量的整数表达式。算符优先关系见表 5.1(1，2 为按顺序出现的两个运算符)B 表 5.1/B 1，2
9、+ - （ ） + - * / ( ) # 说明：“#”是假设的表达式开始符和结束符，不可用。为实现算法，使用了两个堆栈分别寄存运算符和运算数(中间结果值)。算法基本思路如下：首先置操作数栈 S1 为空，表达式起始符“#”设为运算符栈 S2 的栈底元素；依次读入表达式的各符号，若是数字字符则连接在一起转换为 int 型操作数进 S1 栈；若是运算符2，则和 S2 栈的栈顶运算符 51 比较优先级后作相应操作，直至整个表达式求值结束。算法流程图 5.1 如下：【问题】请将流程图补充完整。（分数：15.00）(1).（分数：3.00）_正确答案：()解析：(2).（分数：3.00）_正确答案：()
10、解析：S1 弹栈并输出 解析 此处是整个算法结束之前输出计算结果。(3).（分数：3.00）_正确答案：()解析：12 解析 当运算符 1 的优先级小于运算符 2 的优先级时，此时不能进行运算，须将当前字符入栈并定位下一字符。(4).（分数：3.00）_正确答案：()解析：1 = 2 解析 运算符优先级相等时只有两个运算符都是括号的情况，所以此时完成括号匹配。(5).（分数：3.00）_正确答案：()解析：运算结果入栈 解析 当运算符 1 的优先级大于运算符 2 的优先级时，表示前面的运算符 1 已经可以运算了，所以此处进行运算并将结果入栈。二、B试题二/B(总题数：1，分数：15.00)阅读
11、下列算法说明和算法流程，将应填入(n)处的字句写在对应栏内。【算法说明】程序实现了常见的猜数字游戏。游戏开始时由程序自动产生一个 1 到 100 的随机数，接收用户输入，并给出提示信息，直至用户猜对。用户猜对后，显示猜测次数，并提供“重新开始”和“退出”功能。算法采用两层循环实现。外层循环采用 do-while 循环，由循环条件控制是否重新开始。内层采用 for 循环，用于判断用户的每次输入。m 是随机产生的整数，键盘输入是字符串类型变量，n 是整型变量。【问题 1】内循环还需要一个变量，其作用为(1)。【问题 2】请将流程图 5.2 补充完整。（分数：15.00）(1).（分数：3.00）_
12、正确答案：()解析：(2).（分数：3.00）_正确答案：()解析：产生 1 到 100 之间的随机数 m 解析 此处是外循环的开始条件，应该是产生随机数。(3).（分数：3.00）_正确答案：()解析：输出提示 解析 当用户猜测的数字与随机数不相等时，此时需要提示用户再次输入。(4).（分数：3.00）_正确答案：()解析：将键盘输入转换位 int 型 n 解析 只有将输入字符串转换成 int 型，两个数才可以比较。(5).（分数：3.00）_正确答案：()解析：n=m 解析 此时用户猜对，输出提示信息，准备进入下一次循环。三、B试题三/B(总题数：1，分数：15.00)阅读下列算法说明和算
13、法，将应填入(n)处的字句写在对应栏内。（分数：15.00）(1).（分数：3.00）_正确答案：()解析：(2).（分数：3.00）_正确答案：()解析：4(3).（分数：3.00）_正确答案：()解析：乘(4).（分数：3.00）_正确答案：()解析：BIT(K)(5).（分数：3.00）_正确答案：()解析：取反 解析 由于每一行像素占用 8 个数组元素，所以第 y 行的像素占用数组的第 8“y 到 8“y+7号元素。于是 y 需要乘以 8 存入变量 Y，即左移 3 位，(1)处填左。 x 表示 y 行上的第 x 列像素，因为每个数组元素表示 16 个像素，所以需要将 x 除以 16，得
14、到所在数组元素位置。即右移 4 位，(2)处填 4。 第 2 步，X 的后四位即表示像素在 MAP(V)中所对应的位置，因此需要取 X 的后 4 位送入 K 即可。(3)处填乘。 第 3 步，因为 0 和 1 与 1 逻辑或的结果都是 1，而与 0 逻辑或的结果不变。所以将 MAP(V)与 BIT(K)进行逻辑或(加)，即可将 MAP(V)指定位置“1”，(4)处填 BIT(K)。0 和 1 与 0 逻辑与的结果都是 0，而与1 逻辑与的结果不变，所以将 MAP(V)与取反后的 BIT(K)进行逻辑与(乘)，即可将 MAP(V)指定位置“0”。四、B试题四/B(总题数：1，分数：15.00)阅
15、读下列算法说明和算法，将应填入(n)处的字句写在答卷的对应栏内。【算法说明】某英汉词典文件包含 N 个记录(N1)，每个记录有两个字段：一个是英文单词，另一个是相应的汉语解释。各个记录按英文单词的词典顺序排列，各英文单词并不重复。本算法用于维护、更新该英汉词典文件。维护、更新的方法是：首先输入一个英文单问及其汉语解释，然后在该词典中查找输入的英文单词，若找到，则用输入的汉语解释更新原有的解释；若找不到，则需要将输入的英文单词及其汉语解释插入到该词典的适当位置，使各记录仍按英文单词的词典顺序排列。【算法】第一步读入英汉词典文件，并将读入的 N 个英文单词依次存放在字符串数组 ENGLISH 中，
16、将相应的汉语解释依次存放在字符串数组 CHN 中。数组元素 CHN(i)给出了数组元素 ENGLISH(i)的解释。第二步输入英文单词及其汉语解释，将它们分别存放在字符串变量 E 和 C 中。若 E 为空串或都是空格，则转向第四步。第三步根据变量 E 的值，用二分法在数组 ENGLISH 中查找。具体步骤如下：11L，NH 2INT(L+H)/2)K3若 E=ENGLISH(K)，则 C(1)，转向第二步若 EENGLISH(K)，则 K-1H；若 EENGLISH(K)，则 K+1(2)4若 HL 则对 I=N，L，-1(始值，终值，增量)循环执行：ENGLISH(1)ENGLISH(I+1
17、)CHN(I)CHN(I+1)然后，将 E 和 C 分别存入(3)和(4)，N+1N 最后转向第二步否则，转向(5)第四步将数组 ENGLISH 和 CHN 输出，形成新的英汉词典文件，算法结束。（分数：15.00）(1).（分数：3.00）_正确答案：()解析：(2).（分数：3.00）_正确答案：()解析：L(3).（分数：3.00）_正确答案：()解析：ENGLISH(L)或等价表达式(4).（分数：3.00）_正确答案：()解析：CHN(L)或等价表达式(5).（分数：3.00）_正确答案：()解析：2) 解析 (1)表示找到英文单词，写入汉语意思即可；H，L 分别是二分法查找的上界和
18、下界，所以(2)应填入 L。 (3)和(4)处是将 L 之后的元素依次后移以后，将 E 和 C 分别存入 L 处，所以(3)和(4)处应分别填入 ENGLISH(L)和 CHN(L)或其他等价表达式，比如 ENGLISH(H+1)。(5)处是 HL。这说明查找表未空，需要转向 2继续查找。五、B试题五/B(总题数：1，分数：15.00)阅读下列说明、流程图和算法，将应填入(n)处的字句写在对应栏内。【流程图说明】下图所示的流程图 5.3 用 N-S 盒图形式描述了数组 Array 中的元素被划分的过程。其划分方法；以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的
19、元素向高下标端移动。当划分结束时，基准数定位于 Arrayi，并且数组中下标小于 i 的元素的值均小于基准数，下标大于 i的元素的值均大于基准数。设数组 A 的下界为 low，上界为 high，数组中的元素互不相同。（分数：15.00）(1).（分数：3.00）_正确答案：()解析：(2).（分数：3.00）_正确答案：()解析：ii+1(3).（分数：3.00）_正确答案：()解析：Arrayipivot 或 Arrayjpivot 解析 (1)处语句 j 从高到低移动一位，即 jj-1。(2)处是将一个元素移到左边后，移动 i 向高处寻找一个较大数，即 ii+10(3)处是移动结束后，将 pivot 放到正确的位置，即填入 Arrayipivot 或 Arrayjpivot。(4).（分数：3.00）_正确答案：()解析：A，L，k-1(5).（分数：3.00）_正确答案：()解析：Array，k+1，H 解析 (4)处对小于基准数的元素进行递归调用 sort 排序，应填入 Array，L，k-1。(5)处对大于基准数的元素进行递归调用 sort 排序，应填入 Array，k+1，H。
