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