1、初级程序员下午试题-4 及答案解析(总分：120.00，做题时间：90 分钟)一、B试题一/B(总题数：1，分数：15.00)1.【算法说明】为便于描述屏幕上每个像素的位置，在屏幕上建立平面直角坐标系。屏幕左上角的像素设为原点，水平向右方向设为 X 轴，垂直向下方向设为 Y 轴。设某种显示器的像素为 128128，即在每条水平线和每条垂直线上都有 128 个像素。这样，屏幕上的每个像素可用坐标(x，y)来描述其位置，其中 x 和 y 都是整数，0x127， 0y127。现用一维数组 MAP 来存储整个一屏显示的位图信息。数组的每个元素有 16 位二进位，其中每位对应一个像素，“1”表示该像素“
2、亮”，“0”表示该像素“暗”。数组 MAP 的各个元素与屏幕上的像素相对应后，其位置可排列如下：MAP(0)，MAP(1)，MAP(7)MAP(8)，MAP(9)，MAP(15)MAP(1016)，MAP(1017)，MAP(1023)下述算法可根据用户要求，将指定坐标(x，y)上的像素置为“亮”或“暗”。在该算法中，变量 X，Y，V，S，K 都是 16 位无符号的二进制整数。数组 BIT 中的每个元素 BIT(K)(K=0，15)的值是左起第 K 位为 1，其余位均为 0 的 16 位无符号二进制整数，即 BIT(K)的值为 215-k。【算法】第 1 步 根据用户指定像素的位置坐标(x，y
3、)，算出该像素的位置所属的数组元素 MAP(V)。这一步的具体实现过程如下：1将 x 送变量 X，将 y 送变量 Y；2将 Y 左移U (1) /U位，仍存入变量 Y；3将 X 右移U (2) /U位，并存入变量 S；4计算 Y+S，存入变量 V，得到像素的位置所属的数组元素 MAP(V)。第 2 步 算出指定像素在 MAP(V)中所对应的位置 K(K=0，15)。这一步的具体实现过程如下：将变量 X与二进制数U (3) /U进行逻辑乘运算，并存入变量 K。第 3 步 根据用户要求将数组元素 MAP(V)左起第 K 位设置为“1”或“0”。这一步的具体实现过程如下：1为把指定像素置“亮”，应将
4、 MAP(V)与 BIT(K)进行逻辑U (4) /U运算，并存入 MAP(V)。2为把指定像素置“暗”，应先将 BIT(K)各位取反，再将 MAP(V)与 BIT(K)进行逻辑U (5) /U运算，并存入 MAP(V)。（分数：15.00）_二、B试题二/B(总题数：1，分数：15.00)2.【函数 2.1 说明】 函数 palindrome(char s)的功能是，判断字符串 s 是否为回文字符串，若是，则返回 0，否则返回-1。若一个字符串顺读和倒读都一样时，称该字符串是回文字符串，例如：“LEVEL”是回文字符串，而“LEVAL”不是。 【函数 2.1】 int palindrome(
5、 char s ) char * pi, * pj; pi=s; pj=s+strlen(s)-1; while( pipjpj - if(U (2) /U)return -1; else return 0; 【函数 2.2 说明】 函数 f(char * str，char del)的功能是：将非空字符串 str 分割成若干个子字符串并输出，del 表示分割时的标志字符。 例如若 str 的值为“33123333435”，del 的值为“3”，调用此函数后，将输出 3 个子字符串，分别为“12”、“4”和“5”。 【函数 2.2】 void f( char * str, char del) i
6、nt i ,j ,len; len = strlen (str) i=0; while(i len) while(U (3) /U)i+; /*忽略连续的标志字符*/ /*寻找从 stri开始直到标志字符出现的一个子字符串*/ j=i+1; while(strj != del /*给找到的字符序列置字符串结束标志*/ printf(“%s/t“, U(5) /U; （分数：15.00）_三、B试题三/B(总题数：1，分数：15.00)3.【说明】 设有一个带表头结点的双向循环链表 L，每个结点有 4 个数据成员：指向前驱结点的指针prior、指向后继结点的指针 next、存放数据的成员 dat
7、a 和访问频度 freq。所有结点的 freq 初始时都为0。每当在链表上进行一次 L.Locate(x)操作时，令元素值 x 的结点的访问频度 freq 加 1，并将该结点前移，链接到现它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。 【函数】 void Locate( int while(p!=frist if(p! =first) /*链表中存在 x*/ U (2) /U; 结点类型说明 * current = P; /*从链表中摘下这个结点*/ Current - prior - next = current - next;
8、Current - next - prior = current - prior; P = current - prior; /*寻找重新插入的位置*/ While(p! =first Current- next = U(4) /U; /*插入在 P 之后*? Current - prior = P; P - next - prior = current; P-next=U (5) /U; else printf(“Sorry. Not find! /n“); /*没找到*/ （分数：15.00）_四、B试题四/B(总题数：1，分数：15.00)4.【说明】 函数 QuickSort 是在一维
9、数组 An上进行快速排序的递归算法。 【函数】 void QuickSort( int A ,int s,int t) int i=s,j=t+1,temp; int x=As; do do i + ;while U(1) /U; do j - ;while(Ajx); if(ij)temp=Ai; U(2) /U; U(3) /U; while(ij); Aa =Aj;Aj =x; if(si-1)U (4) /U; if(j+1t)U (5) /U; （分数：15.00）_五、B试题五/B(总题数：1，分数：15.00)5.【程序说明】 函数 int commstr(char * str1
10、，char * str2，int * sublen)从两已知字符串 str1 和str2 中，找出它们的所有最长的公共子串。如果最长公共子串不止 1 个，函数将把它们全部找出并输出。约定空串不作为公共子串。 函数将最长公共子串的长度送入由参数 sublen 所指的变量中，并返回字符串str1 和 str2 的最长公共子串的个数。如果字符串 str1 和 str2 没有公共子串，约定最长公共子串的个数和最长公共子串的长度均为 0。 【程序】 int strlen(char * s) char *t=s; while( * +); return t-s-1; int commstr(char) *
11、str1,char *str2,int *sublen char*s1, *s2; int count=0,len1 ,len2,k,j,i,p; len1:=strlen(str1) len2 = strlen(str2); if(len1len2) s1=str1 ;s2=str2; else len2 = len1;s1 = str2;s2 = str1; for(j=len2;j0;j-) /*从可能最长子串开始寻找*/ for(k=0;U (1) /U:len2;k+) /*k 为子串 s2 的开始位置*/ for(i=0;s1U (2) /U!=/0;i+;) /*i 为子串 s1
12、 的开始位置*/ /*s1 的子串与 s2 的子串比较*/ for (p=0;pj)p+); if (U (4) /U) /*如果两子串相同*/ for(p=0);pj;p+ /*输出子串*/ printf (“%c“,s2k+p); printf (“/n“); count+;/*计数增 1 */ if (count0) break; *sublen=(count0)?U (5) /U:0; return count; （分数：15.00）_六、B试题六/B(总题数：1，分数：15.00)6.【说明】 下面是一个 Applet 程序，其功能是输出已定义好的两个变量 x 和 chr。请改正程序
13、中的错误(有下划线的语句)，使程序能输出正确的结果。 注意：不改动程序的结构，不得增行或删行。 import java. awt.*; U (1) /U U (2) /U int x=10; U (3) /U Label output1; Label output2; U (4) /U output1 = new Label(“定义 int 类型变量“+“x,的初值为“+x); output2 = new Label(“定义 char 类型变量“+“chr,的初值为“+chr); add(output1); add(output2); HTML HEAD TITLE ex34_3 /TITLE
14、 /HEAD BODY U (5) /U width=400 height=400 /applet /BODY /HTML（分数：15.00）_七、B试题七/B(总题数：1，分数：15.00)7.【说明】 已知窗体上有两个名为 cmdGene 和 cmdSort 的命令按钮。单击 cmdCene 按钮时，随机产生 10个1,100范围内的整数并将它们放在数组 intA 中；单击 cmdSort 按钮时，用选择法排序这 10 个数并输出。 【程序代码】 Dim intA(1 To 10)As integer Private Sub cmdGene_Click( ) Dim intl As Int
15、eger Randomize For intl = 1 To 10 intA(intl) = U(1) /U Next intl End Sub Private Sub cmdSort_Click( ) Dim intl, intJ,intMin, intTemp As Integer For intl = 1 To 9 intMin = intA(intl) For intJ=U (2) /UTo 10 If intA(intJ) intMin Then Temp = intA(intJ) intA(intJ)=U (3) /U intMin = intTemp End If Next in
16、tJ U (4) /U U (5) /U For intl = 1 To 10 Print Str(intA(intl)+“ “; Next intl Next lntl Print End Sub（分数：15.00）_八、B试题八/B(总题数：1，分数：15.00)8.【说明】 源程序文件 vectorClass.cpp，其中定义了用于表示向量的类 vector，但类 vector 的定义并不完整。请按要求完成下列操作，将类 vector 的定义补充完整，并给出输出结果。 1补充类 vector 的构造函数，该函数有参数 x 和 y，它们都是 int 型的数据，默认值都为 0。请使用参数列表
17、的形式分别将类的数据成员 a 和 b 分别初始化为参数 x 和 y 的值。 2完成类 vector 的成员函数 input(int x，int y)的定义，将 int 型的参数 x 和 y 分别赋值给数据成员 b 和 a。 3完成类 vector 的友元函数 friend double Multiply(vector int b; public: vector(U (1) /U): U(2) /U void input(int x, int y) U(3) /U void output( ) cout(a,b“)“ endl; friend double Multiply(vector ; d
18、ouble Multiply(vector U (4) /U return c; void main( ) vector x(10,20),y; double d; y. input(2,3) d=Multiply(x,y); coutdendl; 程序输出结果是:U (5) /U。（分数：15.00）_初级程序员下午试题-4 答案解析(总分：120.00，做题时间：90 分钟)一、B试题一/B(总题数：1，分数：15.00)1.【算法说明】为便于描述屏幕上每个像素的位置，在屏幕上建立平面直角坐标系。屏幕左上角的像素设为原点，水平向右方向设为 X 轴，垂直向下方向设为 Y 轴。设某种显示器的像
19、素为 128128，即在每条水平线和每条垂直线上都有 128 个像素。这样，屏幕上的每个像素可用坐标(x，y)来描述其位置，其中 x 和 y 都是整数，0x127， 0y127。现用一维数组 MAP 来存储整个一屏显示的位图信息。数组的每个元素有 16 位二进位，其中每位对应一个像素，“1”表示该像素“亮”，“0”表示该像素“暗”。数组 MAP 的各个元素与屏幕上的像素相对应后，其位置可排列如下：MAP(0)，MAP(1)，MAP(7)MAP(8)，MAP(9)，MAP(15)MAP(1016)，MAP(1017)，MAP(1023)下述算法可根据用户要求，将指定坐标(x，y)上的像素置为“亮
20、”或“暗”。在该算法中，变量 X，Y，V，S，K 都是 16 位无符号的二进制整数。数组 BIT 中的每个元素 BIT(K)(K=0，15)的值是左起第 K 位为 1，其余位均为 0 的 16 位无符号二进制整数，即 BIT(K)的值为 215-k。【算法】第 1 步 根据用户指定像素的位置坐标(x，y)，算出该像素的位置所属的数组元素 MAP(V)。这一步的具体实现过程如下：1将 x 送变量 X，将 y 送变量 Y；2将 Y 左移U (1) /U位，仍存入变量 Y；3将 X 右移U (2) /U位，并存入变量 S；4计算 Y+S，存入变量 V，得到像素的位置所属的数组元素 MAP(V)。第
21、2 步 算出指定像素在 MAP(V)中所对应的位置 K(K=0，15)。这一步的具体实现过程如下：将变量 X与二进制数U (3) /U进行逻辑乘运算，并存入变量 K。第 3 步 根据用户要求将数组元素 MAP(V)左起第 K 位设置为“1”或“0”。这一步的具体实现过程如下：1为把指定像素置“亮”，应将 MAP(V)与 BIT(K)进行逻辑U (4) /U运算，并存入 MAP(V)。2为把指定像素置“暗”，应先将 BIT(K)各位取反，再将 MAP(V)与 BIT(K)进行逻辑U (5) /U运算，并存入 MAP(V)。（分数：15.00）_正确答案：()解析：(1)3 (2)4 (3)111
22、1 (4)或(加) (5)与(乘) 解析 (1)由于每一行像素占用 8 个数组元素，所以第y 行的像素占用数组的第 8y 到 8y+7 号元素。于是 y 需要乘以 8 存入变量 Y，即左移 3 位。(2)x 表示y 行上的第 x 列像素，因为每个数组元素表示 16 个像素，所以需要将 x 除以 16，得到所在数组元素位置，即右移 4 位。 (3)X 的后四位即表示像素在 MAP(V)中所对应的位置，因此取 x 的后 4 位送入 K 即可。(4)因为 0 和 1 与 1 逻辑或的结果都是 1，而与 0 逻辑或的结果不变。所以将 MAP(V)与 BIT(K)进行逻辑或(加)，即可将 MAP(V)指
23、定位置“1”。(5)0 和 1 与 0 逻辑与的结果都是 0，而与 1 逻辑与的结果不变，所以将MAP(V)与取反后的 BIT(K)进行逻辑与 (乘)，即可将 MAP(V)指定位置“0”。二、B试题二/B(总题数：1，分数：15.00)2.【函数 2.1 说明】 函数 palindrome(char s)的功能是，判断字符串 s 是否为回文字符串，若是，则返回 0，否则返回-1。若一个字符串顺读和倒读都一样时，称该字符串是回文字符串，例如：“LEVEL”是回文字符串，而“LEVAL”不是。 【函数 2.1】 int palindrome( char s ) char * pi, * pj; p
24、i=s; pj=s+strlen(s)-1; while( pipjpj - if(U (2) /U)return -1; else return 0; 【函数 2.2 说明】 函数 f(char * str，char del)的功能是：将非空字符串 str 分割成若干个子字符串并输出，del 表示分割时的标志字符。 例如若 str 的值为“33123333435”，del 的值为“3”，调用此函数后，将输出 3 个子字符串，分别为“12”、“4”和“5”。 【函数 2.2】 void f( char * str, char del) int i ,j ,len; len = strlen (
25、str) i=0; while(i len) while(U (3) /U)i+; /*忽略连续的标志字符*/ /*寻找从 stri开始直到标志字符出现的一个子字符串*/ j=i+1; while(strj != del /*给找到的字符序列置字符串结束标志*/ printf(“%s/t“, U(5) /U; （分数：15.00）_正确答案：()解析：(1)*pi=*pj (2)pipj 或者等价表达式 (3)stri=del (4)strj (5)i=j+1 解析 (1)指针pi 从左往右移动，指针 pj 从右往左移动，每移动一次，判断二者指向的元素是否相等，所以此处应填入判断语句*pi=
26、=*pj。(2)pi 如果能移动到 pj 右面，说明字符串是回文字符串，否则返回-1，所以此处应填入 pipj 或者其他等价表达式。(3)此处表达式判断当前字符是否等于标志字符 del，即填入 stri=del。(4)此处表达式为符合要求的字符串置结束标志，此时 j 已指向最后，所以应填入 strj即可。(5)此处语句是修改 i 指针进行下一次循环，所以应填入 i=j+1。三、B试题三/B(总题数：1，分数：15.00)3.【说明】 设有一个带表头结点的双向循环链表 L，每个结点有 4 个数据成员：指向前驱结点的指针prior、指向后继结点的指针 next、存放数据的成员 data 和访问频度
27、 freq。所有结点的 freq 初始时都为0。每当在链表上进行一次 L.Locate(x)操作时，令元素值 x 的结点的访问频度 freq 加 1，并将该结点前移，链接到现它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。 【函数】 void Locate( int while(p!=frist if(p! =first) /*链表中存在 x*/ U (2) /U; 结点类型说明 * current = P; /*从链表中摘下这个结点*/ Current - prior - next = current - next; Current
28、 - next - prior = current - prior; P = current - prior; /*寻找重新插入的位置*/ While(p! =first Current- next = U(4) /U; /*插入在 P 之后*? Current - prior = P; P - next - prior = current; P-next=U (5) /U; else printf(“Sorry. Not find! /n“); /*没找到*/ （分数：15.00）_正确答案：()解析：(1)p-data!=x (2)p-freq+ (3)current-freqP-freq
29、 (4)p-next (5)current 解析 (1)空所在的循环是定位 x，将指针指向 x 结点(如存在的话)，因此(1)空应填写“p-data!=x”。显然，(2)空是使该结点的访问频度加 1，因此(2)空应填写“p-freq+”。(3)空所在的循环是根据访问频度定位 x 结点的新位置，用 P 指向 x 结点的前驱，因此(3)空处应填“current-freqP-freq”。 (4)、(5)空之间的语句是将结点 x 插入在 P 之后。(4)空所在语句是将指针 P 指向 x 结点的前驱，因此(4)空应填写“p-next”。(5)空所在语句是将 P 后继指向结点 current，因此空(5)
30、处应填写“current”。四、B试题四/B(总题数：1，分数：15.00)4.【说明】 函数 QuickSort 是在一维数组 An上进行快速排序的递归算法。 【函数】 void QuickSort( int A ,int s,int t) int i=s,j=t+1,temp; int x=As; do do i + ;while U(1) /U; do j - ;while(Ajx); if(ij)temp=Ai; U(2) /U; U(3) /U; while(ij); Aa =Aj;Aj =x; if(si-1)U (4) /U; if(j+1t)U (5) /U; （分数：15.0
31、0）_正确答案：()解析：(1)Aix (2)Ai=Aj 3)Aj=temp (4)QuickSort(A，s，j-1) (5)QuickSort(A，j+1，t)；解析 快速排序的思想是：任取待排序序列中的某个元素作为基准(一般取第一个元素)，通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。快速排序是对冒泡排序的一种改进方法，算法中元素的比较和交换是从两端向中间进行的，排序码较大的元素一次就能够交换到后面单元，排序码较小的记录一次就能够交换到前面单元，记录
32、每次移动的距离较远，因而总的比较和移动次数较少。五、B试题五/B(总题数：1，分数：15.00)5.【程序说明】 函数 int commstr(char * str1，char * str2，int * sublen)从两已知字符串 str1 和str2 中，找出它们的所有最长的公共子串。如果最长公共子串不止 1 个，函数将把它们全部找出并输出。约定空串不作为公共子串。 函数将最长公共子串的长度送入由参数 sublen 所指的变量中，并返回字符串str1 和 str2 的最长公共子串的个数。如果字符串 str1 和 str2 没有公共子串，约定最长公共子串的个数和最长公共子串的长度均为 0。
33、【程序】 int strlen(char * s) char *t=s; while( * +); return t-s-1; int commstr(char) *str1,char *str2,int *sublen char*s1, *s2; int count=0,len1 ,len2,k,j,i,p; len1:=strlen(str1) len2 = strlen(str2); if(len1len2) s1=str1 ;s2=str2; else len2 = len1;s1 = str2;s2 = str1; for(j=len2;j0;j-) /*从可能最长子串开始寻找*/
34、for(k=0;U (1) /U:len2;k+) /*k 为子串 s2 的开始位置*/ for(i=0;s1U (2) /U!=/0;i+;) /*i 为子串 s1 的开始位置*/ /*s1 的子串与 s2 的子串比较*/ for (p=0;pj)p+); if (U (4) /U) /*如果两子串相同*/ for(p=0);pj;p+ /*输出子串*/ printf (“%c“,s2k+p); printf (“/n“); count+;/*计数增 1 */ if (count0) break; *sublen=(count0)?U (5) /U:0; return count; （分数：
35、15.00）_正确答案：()解析：(1)k+j (2)i+j-1 (3)s1i+P=s2k+P (4)P=j 或 p=j (5)j 解析 略。六、B试题六/B(总题数：1，分数：15.00)6.【说明】 下面是一个 Applet 程序，其功能是输出已定义好的两个变量 x 和 chr。请改正程序中的错误(有下划线的语句)，使程序能输出正确的结果。 注意：不改动程序的结构，不得增行或删行。 import java. awt.*; U (1) /U U (2) /U int x=10; U (3) /U Label output1; Label output2; U (4) /U output1 =
36、 new Label(“定义 int 类型变量“+“x,的初值为“+x); output2 = new Label(“定义 char 类型变量“+“chr,的初值为“+chr); add(output1); add(output2); HTML HEAD TITLE ex34_3 /TITLE /HEAD BODY U (5) /U width=400 height=400 /applet /BODY /HTML（分数：15.00）_正确答案：()解析：(1)import java.applet* (2)public class MyApplet extends Applet (3)char
37、chr=R (4)public void init() (5)appletcode=“MyAppletclass” 解析 创建 applet 程序应导入包applet。applet 程序类继承自类 Applet。声明字符型变量应当使用单引号。初始化函数必须是公有的。调用 applet 类应当使用关键字 code。七、B试题七/B(总题数：1，分数：15.00)7.【说明】 已知窗体上有两个名为 cmdGene 和 cmdSort 的命令按钮。单击 cmdCene 按钮时，随机产生 10个1,100范围内的整数并将它们放在数组 intA 中；单击 cmdSort 按钮时，用选择法排序这 10 个
38、数并输出。 【程序代码】 Dim intA(1 To 10)As integer Private Sub cmdGene_Click( ) Dim intl As Integer Randomize For intl = 1 To 10 intA(intl) = U(1) /U Next intl End Sub Private Sub cmdSort_Click( ) Dim intl, intJ,intMin, intTemp As Integer For intl = 1 To 9 intMin = intA(intl) For intJ=U (2) /UTo 10 If intA(in
39、tJ) intMin Then Temp = intA(intJ) intA(intJ)=U (3) /U intMin = intTemp End If Next intJ U (4) /U U (5) /U For intl = 1 To 10 Print Str(intA(intl)+“ “; Next intl Next lntl Print End Sub（分数：15.00）_正确答案：()解析：(1)1+int(rnd*100) (2)intI+1 (3)intMin (4)intA(intI)=intMin (5)Next intI 解析 根据题意，第一个空应该是产生 10 个1
40、，100范围内的随机整数，因此填“1+int(rnd*100)”。 选择排序思想是：第 i 趟排序开始时，当前有序区和无序区分别为 R1i-1和 Rin(1in-1)，该趟排序则是从当前无序区中选出关键字最小的记录 Rk，将它与无序区的第 1 个记录 Ri交换，使 R1i和Ri+1n)分别变为新的有序区和新的无序区。因为每趟排序均使有序区中增加了一个记录，且有序区中的记录关键字均不大于无序区中记录的关键字，即第 i 趟排序之后 R1ikeysRi +1nkeys，所以进行 n-1 趟排序之后有 R1n-1keysRn key。也就是说，经过 n-1 趟排序之后，整个文件R1n递增有序。因此(2
41、)空填“intI+1”；If intA(intJ)intMin Then 后的 3 条语句是实现数intA(intJ)与 intMin 的交换，因此(3)空填“intMin”；(4)空是实现最小数与无序区的第 1 个数交换，因此填“intA(intI)=intMin”；(5)空是循环结束语句，填“Next intI”。八、B试题八/B(总题数：1，分数：15.00)8.【说明】 源程序文件 vectorClass.cpp，其中定义了用于表示向量的类 vector，但类 vector 的定义并不完整。请按要求完成下列操作，将类 vector 的定义补充完整，并给出输出结果。 1补充类 vector 的构造函数，该函数有参数 x 和 y，它们都是 int 型的数据，默认值都为 0。请使用参数列表的形式分别将类的数据成员 a 和 b 分别初始化为参数 x 和 y 的值。 2完成类 vector 的成员函数 input(int x，int y)的定义，将 int 型的参数 x 和 y 分别赋值给数据成员 b 和 a。 3完成类 vector 的友元函数 friend double Multiply(vector int b; public: vector(U
