1、初级程序员下午试题-109 及答案解析(总分：90.00，做题时间：90 分钟)一、试题一(总题数：1，分数：15.00)1.说明如图 8-7 所示的流程图用于从数组 K 中找出一切满足：K(I)+K(J)=M 的元素对(K(I)，K(J)(1IJN)。假定数组 K 中的 N 个不同的整数已按由小到大的顺序进行排列，M 是给定的常数。流程图（分数：15.00）填空项 1:_二、试题二(总题数：2，分数：15.00)2.说明 1函数 BTREE*SortTreeSearch(BTREE*tree,int key)采用非递归方法，在二叉排序树(二叉查找树)中查找键值为 key 的结点。若找到，则返
2、回键值所在结点的指针，否则返回 NULL。typedef struct nodeint data; /*结点的键值*/struct node *left;struct node *right;C 程序代码 1以上C 程序代码 1中共有 3 处错误。请在表 8-5 中指出这些错误所在代码的行号，并在不增加和删除代码行的情况下进行修改，写出修改正确后的完整代码行。（分数：7.50）填空项 1:_3.说明 2C 程序代码 2是能求得“背包问题”的一组解的递归算法程序。“背包问题”的基本描述是：有一个背包，能盛放的物品总重量为 S，设有件物品，其重量分别为 W1，W 2，W n，希望从 N 件物品中选
3、择若干件物品，所选物品的重量之和恰能放入该背包中，即所选物品的重量之和等于 S。C 程序代码 2BTREE;#includestdio.h#define N 7#define S 15int wN+1 = 0,1,4,3,4,5,2,7;int knap ( int S, int n) if (S = 0)return 1 ;if ( s0 ( s0 if ( (1) ) ) printf( “4d“,wn );return 1 ;return (2) ;main () if (knap(S,N) )printf( “OK!/n“ );elseprintf ( “N0 ! /n“ ) ;请将C
4、 程序代码 2中空缺处的内容填补完整。（分数：7.50）填空项 1:_三、试题三(总题数：1，分数：15.00)4.说明喜迎 2012 年伦敦夏季奥运会!以下C 程序代码能将一个给定汉字(例如，奥运会的“会”字)的点阵逆时针旋转 90 度，并输出旋转前后的点阵数据及字形。图 8-8 是汉字“会”字的 1616 点阵字形，用数字 0 表示空白位置，用数字 1 表示非空白位置，“会”字的第 1 行即可表示成如下的 0，1 序列。0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0若将它看做一个字的 16 个位，则“会”字的第 1 行可以用 16 进制数的 0100 来表示。同理，“会”字
5、的第 2 行可以用 16 进制数的 0240 表示，第 3 行可以用 16 进制数的 0420 表示，。以此类推，用 16 个双字节整型数即可存放一个汉字点阵字形。“会”字的点阵数据及字形如图 8-8 的左半部分所示。将一个汉字逆时针旋转 90 度，就是把该汉字点阵的最右列作为旋转后新点阵的第 1 行，次最右列作为旋转后新点阵的第 2 行，以形成一个旋转后的点阵字形。图 8-8 的右半部分就是将“会”字逆时针旋转 90 度后的点阵数据和字形(提示：读者可将书本顺时针旋转 90 度，以查看旋转 90 度后的点阵字形)。在C 程序代码中，数组 old 中存放着“会”字的 16 个双字节整型点阵数据
6、。函数 turnleft 能将该点阵数据逆时针旋转 90 度，旋转后的点阵数据存放在数组 new 中。函数 display 能将旋转前后的点阵数据加以编辑，用点字符“.”表示值为 0 的位，用字符“x”表示值为 1 的位，从而将旋转前后的点阵按行输出其 16 进制的数据及字形，如图 8-8 所示。（分数：15.00）填空项 1:_四、试题四(总题数：1，分数：15.00)5.说明函数 DelXInsY(LinkedList Lx，LinkedList Ly,int key 1，int key2,int len)的功能是，将线性表 X中关键码为 key1 的结点开始的 len 个结点，按原顺序移
7、至线性表 Y 中关键码为 key2 的结点之前，若移动成功，则返回 0；否则返回-1。线性表的存储结构为带头结点的单链表，Lx 为表 X 的头指针，Ly 为表 Y的头指针。单链表结点的类型定义如下。typedef struct nodeint key;struct node *next;*LinkedList;C 程序代码（分数：15.00）填空项 1:_五、试题五(总题数：1，分数：15.00)6.说明某绘图系统中有两个画矩形的程序 DP1 和 DP2。程序 DP1 用函数 draw a line(x1,y1,x2,y2)画一条直线，程序 DP2 则用函数 drawline(x1,x2,y1
8、,y2)画一条直线。当实例化矩形时，确定使用 DP1 还是 DP2。为了适应变化，包括“不同类型的形状”和“不同类型的画图程序”，将抽象部分与实现部分分离，使它们可以独立地变化。若将“抽象部分”对应“形状”，“实现部分”对应“画图”，与一般的接口(抽象方法)和具体实现不同，则将这种应用称为 Bridge(桥接)模式。图 8-9 显示了该系统与矩形绘制相关的各个类之间的关系。系统始终只处理 3 个对象：Shape 对象、Drawing 对象，以及 DP1 或 DP2 对象。以下是 C+语言的实现过程，能够正确编译通过。（分数：15.00）填空项 1:_六、试题六(总题数：1，分数：15.00)7
9、.说明某绘图系统中有两个画矩形的程序 DP1 和 DP2。程序 DP1 用函数 draw_a_line(x1,y1,x2,y2)画一条直线，程序 DP2 则用函数 drawline(x1,x2,y1,y2)画一条直线。当实例化矩形时，确定使用 DP1 还是 DP2。为了适应变化，包括“不同类型的形状”和“不同类型的画图程序”，将抽象部分与实现部分分离，使它们可以独立地变化。若将“抽象部分”对应“形状”，“实现部分”对应“画图”，与一般的接口(抽象方法)和具体实现不同，则将这种应用称为 Bridge(桥接)模式。图 8-10 显示了该系统与矩形绘制相关的各个类之间的关系。系统始终只处理 3 个对
10、象：Shape 对象、Drawing 对象，以及 DP1 或 DP2 对象。以下是 Java语言实现，能够正确编译通过。（分数：15.00）填空项 1:_初级程序员下午试题-109 答案解析(总分：90.00，做题时间：90 分钟)一、试题一(总题数：1，分数：15.00)1.说明如图 8-7 所示的流程图用于从数组 K 中找出一切满足：K(I)+K(J)=M 的元素对(K(I)，K(J)(1IJN)。假定数组 K 中的 N 个不同的整数已按由小到大的顺序进行排列，M 是给定的常数。流程图（分数：15.00）填空项 1:_ （正确答案：NJ (2) IJ?(3)I-1I (4) J-1J(5)
11、 |N/2|）解析：依题意，理顺图 8-7 所示的从数组 K 中查找相关元素对的算法基本思想是：设置了两个变量 I 和J，初始时分别指向数组 K 的第一个元素和最后一个元素。若这两个元素之和等于 M，则输出结果，并且使这两个指针都向中间移动一个位置；若这两个元素之和小于 M，则将指针，向中间移动(因为数组 K 已按由小到大的顺序进行排列)；若这两个元素之和大于 M，则将指针 J 向中间移动；以此类推。当 IJ 时，说明数组 K 中所有的元素都搜索完毕，则退出循环。结合以上分析，(1) 空缺处应将数组 K 中最后一个元素的下标赋予 J，即应填入 NJ。(2) 空缺处应判断循环体是否退出，其所填入
12、的条件表达式是 IJ?。当 I=J 时，说明这两个指针指向同一元素，则应当退出循环。(3) 空缺处在流程图中有两处，一处是当 K(I)+K(J)=M 时，另一处是当 K(I)+K(J)M 时，在这两种情况下，都要将指针 I 向中间移动一个位置，即该空缺处应填入 I+1I。同理，(4) 空缺处应填入将指针 J 向中间移动一个位置的表达式 J-1J。在如图 8-7 所示的流程图中，比较“K(I)+K(J)=M?”最少执行次数发生在第 1 元素与第 N 个元素之和等于M、第 2 元素与第 N-1 个元素之和等于 M、第 3 元素与第 N-2 个元素之和等于 M、。若符合此类型的情况，则每次比较时，指
13、针 I 和 J 都向中间移动，因此比较“K(I)+K(J)=M”最少执行次数约为 N/2 次(计算结果应向上取整数)。二、试题二(总题数：2，分数：15.00)2.说明 1函数 BTREE*SortTreeSearch(BTREE*tree,int key)采用非递归方法，在二叉排序树(二叉查找树)中查找键值为 key 的结点。若找到，则返回键值所在结点的指针，否则返回 NULL。typedef struct nodeint data; /*结点的键值*/struct node *left;struct node *right;C 程序代码 1以上C 程序代码 1中共有 3 处错误。请在表 8
14、-5 中指出这些错误所在代码的行号，并在不增加和删除代码行的情况下进行修改，写出修改正确后的完整代码行。（分数：7.50）填空项 1:_ （正确答案：行号 修改正确后的完整代码行3 while(ptr!=NULL”，或其他等价表达形式。第 3 个错误是第 9 行的“return *ptr;”语句。若在二叉排序树中找到键值为 key 的结点，则返回键值所在结点的指针，即该行代码应修改为“retun ptr;”。3.说明 2C 程序代码 2是能求得“背包问题”的一组解的递归算法程序。“背包问题”的基本描述是：有一个背包，能盛放的物品总重量为 S，设有件物品，其重量分别为 W1，W 2，W n，希望
15、从 N 件物品中选择若干件物品，所选物品的重量之和恰能放入该背包中，即所选物品的重量之和等于 S。C 程序代码 2BTREE;#includestdio.h#define N 7#define S 15int wN+1 = 0,1,4,3,4,5,2,7;int knap ( int S, int n) if (S = 0)return 1 ;if ( s0 ( s0 if ( (1) ) ) printf( “4d“,wn );return 1 ;return (2) ;main () if (knap(S,N) )printf( “OK!/n“ );elseprintf ( “N0 ! /
16、n“ ) ;请将C 程序代码 2中空缺处的内容填补完整。（分数：7.50）填空项 1:_ （正确答案：knap(s-wn,n-1)或其等价形式(2) knap(s,n-1)或其等价形式）解析：递归是设计和描述算法的一种有力工具。能采用递归描述的算法通常有这样的特征：为求解规模为N 的问题，设法将它分解成一些规模较小的问题，然后由这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并由这些更小问题的解构造出规模稍大问题的解。特别地，当规模 N=1 时，能直接得到解。递归算法的重点与难点分别如下。(1) 编写递归程序的关键是：找出问题的递
17、归关系和初始值，可以利用归纳法由一个问题归纳总结出递归式，再加上初始条件，即可编写递归函数。(2) 编写递归程序时，必须要给出递归结束条件。(3) 递归的次数不是无限制的，每一次的递归调用都要压栈，占用内存，而计算机的内存是有限的。(4) 采用递归方法定义的数据结构或问题最适合使用递归方法。C 程序代码 2用递归算法解决背包问题，解决该问题的思路是对于物品 i 的选择有两种可能。(1) 考虑物品 i 被选择的情况，这种可能性当且仅当包含它不会超过方案总重量的限制时才是可行的。物品 i 被选择后，继续递归去考虑下一个物品。(2) 考虑物品 i 不被选择的情况，这种可能性当且仅当不包含物品 f 时
18、，也有可能找到价值更大的方案。考虑完物品 i 后，也要继续递归考虑下一个物品。根据以上思路分析C 程序代码 2中的函数 knap(int s,int n)，该函数是用递归算法解决“背包问题”的。其中，参数 s 为考查完物品 i 后，背包还能盛放的重量；n 为考查完物品 i 后，下一个待考查的物品。(1) 空缺处是考虑物品 n 被选择的情况，此时因为物品，n 已被选择，所以剩余可盛放的重量应为 s-wn，而背包待考查物品应为 n-1，则该空缺处所应填写的内容是“knap(s-wn，n-1)”。(2) 空缺处是处理不包含物品 i 时的情况。由于物品 i 没有放入背包，则背包可装载重量不变还应是 s
19、，而这时应该考虑下一个物品，n-1。因此(2)空缺处所应填写的内容是“knap(s,n-1)”。三、试题三(总题数：1，分数：15.00)4.说明喜迎 2012 年伦敦夏季奥运会!以下C 程序代码能将一个给定汉字(例如，奥运会的“会”字)的点阵逆时针旋转 90 度，并输出旋转前后的点阵数据及字形。图 8-8 是汉字“会”字的 1616 点阵字形，用数字 0 表示空白位置，用数字 1 表示非空白位置，“会”字的第 1 行即可表示成如下的 0，1 序列。0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0若将它看做一个字的 16 个位，则“会”字的第 1 行可以用 16 进制数的 010
20、0 来表示。同理，“会”字的第 2 行可以用 16 进制数的 0240 表示，第 3 行可以用 16 进制数的 0420 表示，。以此类推，用 16 个双字节整型数即可存放一个汉字点阵字形。“会”字的点阵数据及字形如图 8-8 的左半部分所示。将一个汉字逆时针旋转 90 度，就是把该汉字点阵的最右列作为旋转后新点阵的第 1 行，次最右列作为旋转后新点阵的第 2 行，以形成一个旋转后的点阵字形。图 8-8 的右半部分就是将“会”字逆时针旋转 90 度后的点阵数据和字形(提示：读者可将书本顺时针旋转 90 度，以查看旋转 90 度后的点阵字形)。在C 程序代码中，数组 old 中存放着“会”字的
21、16 个双字节整型点阵数据。函数 turnleft 能将该点阵数据逆时针旋转 90 度，旋转后的点阵数据存放在数组 new 中。函数 display 能将旋转前后的点阵数据加以编辑，用点字符“.”表示值为 0 的位，用字符“x”表示值为 1 的位，从而将旋转前后的点阵按行输出其 16 进制的数据及字形，如图 8-8 所示。（分数：15.00）填空项 1:_ （正确答案：k=0,newrow=0(2) row(3) 15-k(4) /0(5) *old(15-col)或 oldrow(15-col)(6) new(15-col)或 newrow(15-col)）解析：这是一道要求读者掌握数组应用
22、的程序设计题。本题的解答思路如下。阅读完程序说明信息后可知，本程序可将一个给定汉字的点阵逆转 90 度后输出。用 16 个元素的元素数组表示汉字点阵，每个无符号整数有 16 位，当一位为 0 时表示空白，为 1 时表示非主空白。该 C 程序的功能是将上述表示形式的汉字点阵(“会”字)逆时针旋转 90 度后存储在数组 new 中，并输出旋转前后的 16进制点阵数据及字形。函数 turnleft 完成点阵数据逆时针旋转 90 度，并将旋转后的点阵数据存放在数组 new 中的操作。在函数turnleft 的内部 for 循环中，语句“newrow|=(oldk (2) )”用于实现“将一个汉字逆时针
23、旋转 90 度，就是把该汉字点阵的最右列作为旋转后新点阵的第 1 行，次最右列作为旋转后新点阵的第 2 行，”，即装配新点阵中的第 row 行。其中，地址运算符“”是一个返回操作数地址的单目操作符，运算符“|=”是进行位逻辑或赋值运算。由于新点阵的第 row 行的各位来自原点阵中各行的第(15-row)位，而且此处用struct node *next;*LinkedList;C 程序代码（分数：15.00）填空项 1:_ （正确答案：klen 或其等价形式(2) q=q_next 或其等价形式(3) pres=Ly 或其等价形式(4) prep_next(5) prep_next）解析：由题干
24、说明及所给出的 C 程序代码可知，已知条件为两个链表 Lx 和 Ly，最后得到的结果也是两个链表，只不过是将 Lx 中的部分结点移动到 Ly 中，因此，本问题主要解决的问题是怎么合理地移动相关结点。在题干信息中没有给出结点移动的具体算法描述，这就要求解题时要先结合实例自行设计一个算法，然后观察是否与程序中的算法一致。若不一致，则再寻找其他算法。在自己设计相关算法之前，最好要先看一看题目给出的算法提示，在给出的 C 程序代码中，总是有一些蛛丝马迹可以让我们找到突破口的，这些地方通常都会给出题目所用算法的暗示。五、试题五(总题数：1，分数：15.00)6.说明某绘图系统中有两个画矩形的程序 DP1
25、 和 DP2。程序 DP1 用函数 draw a line(x1,y1,x2,y2)画一条直线，程序 DP2 则用函数 drawline(x1,x2,y1,y2)画一条直线。当实例化矩形时，确定使用 DP1 还是 DP2。为了适应变化，包括“不同类型的形状”和“不同类型的画图程序”，将抽象部分与实现部分分离，使它们可以独立地变化。若将“抽象部分”对应“形状”，“实现部分”对应“画图”，与一般的接口(抽象方法)和具体实现不同，则将这种应用称为 Bridge(桥接)模式。图 8-9 显示了该系统与矩形绘制相关的各个类之间的关系。系统始终只处理 3 个对象：Shape 对象、Drawing 对象，以
26、及 DP1 或 DP2 对象。以下是 C+语言的实现过程，能够正确编译通过。（分数：15.00）填空项 1:_ （正确答案：DP2:drawline(x1,x2,y1,y2) (2)Drawing(3) virtual (4) _dp-drawLine(x1,y1,x2,y2)(5) Shape (6) Shape(dp)）解析：类图中通常包含依赖关系、泛化关系、关联关系、聚合关系和实现关系等，其相关的图符符号如图8-12 所示。六、试题六(总题数：1，分数：15.00)7.说明某绘图系统中有两个画矩形的程序 DP1 和 DP2。程序 DP1 用函数 draw_a_line(x1,y1,x2,
27、y2)画一条直线，程序 DP2 则用函数 drawline(x1,x2,y1,y2)画一条直线。当实例化矩形时，确定使用 DP1 还是 DP2。为了适应变化，包括“不同类型的形状”和“不同类型的画图程序”，将抽象部分与实现部分分离，使它们可以独立地变化。若将“抽象部分”对应“形状”，“实现部分”对应“画图”，与一般的接口(抽象方法)和具体实现不同，则将这种应用称为 Bridge(桥接)模式。图 8-10 显示了该系统与矩形绘制相关的各个类之间的关系。系统始终只处理 3 个对象：Shape 对象、Drawing 对象，以及 DP1 或 DP2 对象。以下是 Java语言实现，能够正确编译通过。（
28、分数：15.00）填空项 1:_ （正确答案：abstract (2) DP2.drawline(x1,x2,y1,y2)(3) Drawing (4) dp.drawLine(x1,y1,x2,y2)(5) extends Shape (6) super(dp)）解析：在如图 8-10 所示的类图中，各类之间的关系请参见本节试题 5 的相关要点解析。由于类 Drawing 的 drawLine()方法是 abstract 的，因此 Drawing 要么是接口，要么是抽象类，即(1)空缺处应填入 abstract。(2) 空缺处是调用 DP2 系统的相应方法，可参照 DP1 的对应函数的函数体
29、语句“DP1.draw a line 匣子(x1,y1,x2,y2);”，但要注意其参数不完全相同，因此该空缺处应填入“DP2.drawline(x1,x2,y1,y2)”。(3) 空缺处所在的语句中，_dp 属性是用来存储 Drawing 对象的，参照 Shape 的构造函数可确认这一点，因此该空缺处应填入 Drawing。Shape 类的 drawLine 方法是通过调用 Drawing 对应的方法来实现所需功能的，因此(4)空缺处应填入_dp.drawLine(x1,y1,x2,y2)。由图 8-10 中类 Rectangle 与类 Shape 之间的泛化关系可知，(5)空缺处应填入 extends Shape。(6) 空缺处应填入基类构造函数 super(dp)。
