初级程序员下午试题-4

1、初级程序员下午试题-4(总分：120.00 ,做题时间：90分钟)一、B试题一 /B(总题数：1，分数：15.00)1.【算法说明】 为便于描述屏幕上每个像素的位置，在屏幕上建立平面直角坐标系。屏幕左上角 的像素设为原点，水平向右方向设为X轴，垂直向下方向设为Y轴。设某种显示器的像素为128 X 128，即在每条水平线和每条垂直线上都有128个像素。这样，屏幕上的每个像素可用坐标(x, y)来描述其位置，其中x和y都是整数，0< x< 127 , 0< y< 127。现用一维数组 MAP来存储整个一屏显示的位图信息。 数组的每个元素有 16位二进位， 其中每 位对应一个

2、像 素，“ 1 表示该像素“亮，“ 0表示该像素“暗。数组 MAP的各个元 素与屏幕上的像素相对应后，其位置可排列如下：MAP(0) , MAP(1) , ? , MAP(7)MAP(8) , MAP(9) , ? ,MAP(15)MAP(1016) , MAP(1017) , ? , MAP(1023)下述算法可根据用户要求，将指定坐标(x , y)上的像素置为“亮或“暗。在该算法中，变量X，丫 , , S ,K都是16位无符号的二进制整数。 数组BIT中的每个元素BIT(K)(K=0 , ? , 15)的值是左起第K位为1，其余位均为0的16位无符号二进制整数，即 BIT(K)的值为215

3、-k。【算法】(x , y),算出该像素的位置所属的数组元素MAP(V)。第1步 根据用户指定像素的位置坐标 这一步的具体实现过程如下：1 .将x送变量X,将y送变量Y;2 .将Y左移U (1) /U位，仍存入变量Y;3 .将 X右移U/U位，并存入变量S ；4.计算Y+S,存入变量 第2步算出指定像素在 将变量V，得到像素的位置所属的数组元素MAP(V)中所对应的位置K(K=0 , ?MAP(V) o15)。这一步的具体实现过程如下：X与二进制数U/U进行逻辑乘运算，并存入变量K第3步 根据用户要求将数组元素MAP(V)左起第K位设置为“ 1或“ 0。这一步的具体实现过程如下：1 .为把指定

4、像素置“亮，应将MAP(V)与BIT(K)进行逻辑U/U运算，并存入MAP(V)2 .为把指定像素置“暗，应先将 BIT(K)各位取反，再将MAP(V)与BIT(K)进行逻辑U/U运 算，并存入 MAP(V)。(分数：15.00 )正确答案：()解析：(1)3 (2)4 (3)1111 (4)或(加)与(乘)解析(1)由于每一行像素占用8个数组元素，所以第y行的像素占用数组的第8约到8 X y+7号元素。于是y需要乘以8存入变量Y ,即左移3位。(2)x表示y行上的第x列像素，因为每个数组兀素表示16个像素，所以需要将 x除以16，得到所在数组元素位置，即右移4位。(3)X的后四位即表示像素在

5、 MAP(V)中所对应的位置，因此取 x的后4位送入K即 可。因为0和1与1逻辑或的结果都是 1，而与0逻辑或的结果不变。所以将 MAP(V)与BIT(K) 进行逻辑或(加),即可将MAP(V)指定位置“ 1 。(5)0和1与0逻辑与的结果都是 0,而与1逻辑 与的结果不变，所以将MAP(V)与取反后的BIT(K)进行逻辑与(乘)，即可将MAP(V)指定位置“ 0。B试题二/B(总题数：1，分数：15.00)2.【函数2.1说明】 函数pal in drome(char s)的功能是，判断字符串s是否为回文字符串，假设是,那么 返回0,否那么返回-1。假设一个字符串顺读和倒读都一样时，称该字符

6、串是回文字符串，例如：“ LEVEL是回文字符串，而“ LEVAL 不是。 【函数 2.1 】int pal in drome( char s ) char * pi, * pj; pi=s; pj二s+strle n(s)-1;while( pi< Pj&&U (1) /U) pi + ;pj - if(U/U)return-1; else return 0; 【函数2.2说明】 函数f(char * str , char del)的功能是：将非空字符串str分割成假设干个子字符串并输出，del表示分割时的标志字符。例如假设str的值为“ 33123333435 ，de

7、l的 值为“ 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(U/U)i+; /* 忽略 连续的标志字符*/ /*寻找从stri开始直到标志字符出现的一个子字符串*/ j=i+1;给找到的字符序列置字符while(strj != del && strj ! = 7O')j + U(4) /U: '/0' /*串结束标志*/ pri

8、ntf("%s/t", &stri); U(5) /U; (分数：15.00 )正确答案：()解析：(1)*pi=*pj (2)pi <pj 或者等价表达式(3)stri=del (4)strj (5)i=j+1 解析(1)指针 pi从左往右移动，指针pj从右往左移动，每移动一次，判断二者指向的兀素是否相等，所以此处应填入判断语句*pi= =*pj o (2)pi如果能移动到pj右面，说明字符串是回文字符串，否那么返回-1，所以此处应填入pi < pj或者其他等价表达式。此处表达式判断当前字符是否等于标志字符del ,即填入stri=del。(4)此处表

9、达式为符合要求的字符串置结束标志，此时 j已指向最后，所以应填 入strj即可。此处语句是修改i指针进行下一次循环，所以应填入i=j+1。三、B试题三/B(总题数：1，分数：15.00)放数据的成员data和访问频度freq。所有结点的freq初始时都为0。每当 在链表上进行一次3.链表L,每个结点有4个数据成员：【说明】设有一个带表头结点的双向循环指向前驱结点的指针 prior、指向后继结点的指针next、存L.Locate(x)操作时，令元素值 x的结点的访问频度freq加1,并将该结点前移，链接 到现它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问

10、的结点总是靠近表头。【函数】void Locate( int &x) <结点类型说明> * p =first -> next;while(p!=frist&&U (1) /U)P=P-> next; if(p! =first) /*链表中存在 x*/ U (2) /U;<结点类型说明 > * current = P; /*从链表中摘下这个结点*/ Current - > prior - > next = current-> next; Current - > next - > prior = curren

11、t -> prior; P = current -> prior; /*寻找重新插入的位置 */ While(p! =first &&U/U)p=p-> prior; Current- > next = U(4) /U;/* 插入在 P 之后 *? Current - > prior = P; P - > next - > prior = current; P- >next=U/U; else printf("Sorry.Not find!/n"); /*没找至 U*/ (分数： 15.00 )正确答案： ()

12、解析：(1)p- > data!=x (2)p- >freq+ (3)current- >freq > P-> freq (4)p- >next (5)current 解析 (1)空所在的循 环是定位x，将指针指向x结点(如存在的话)，因此(1)空应填写“ p- >data!=x 。显然，(2)空是 使该结点的访问频度加1,因此空应填写“ p- >freq+ 。空所在的循环是根据访问频度定位x结点的新位置，用P指向x结点的前驱，因此 (3)空处应填“cu rrent- >freq > P->freq 。、空 之间的语句是将结点x

13、插入在P之后。空所在语句是将指针P指向x结点的前驱，因此空应填写“ p- >next 。(5)空所在语句是将P后继指向结点current ,因此空(5)处应填写a力curre nt 。四、B试题四/B(总题数：1，分数：15.00)4. 【说明】 函数Quicksort是在一维数组An上进行快速排序的递归算法。【函数】voidQuickSort( int A ,i nt s,i nt t) int i=s,j=t+1,temp; int x=As; do do i + ;while U(1) /U; do j-;while(Aj >x); if(i <j)temp=Ai; U

14、 (2) /U; U(3) /U; while(i<j); Aa=Aj;Aj =x; if(s<i-1)U/U; if(j+1<t)U/U; (分数： 15.00 )正确答案：()解析： (1)Ai <x Ai=Aj< 3)Aj=temp (4)QuickSort(A, s, j-1) (5)QuickSort(A , j+1 , t);解析快速排序的思想是：任取待排序序列中的某个元素作为基准(一般取第一个元素),通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子 序列的排序码那么大于基准元素的排序码，然后分别对两个

15、子序列继续进行排序，直至整个序列有序。快速排序是对冒泡排序的一种改进方法，算法中元素的比较和交换是从两端向中间进行的，排序码较大的元素一次就能够交换到后面单元，排序码较小的记录一次就能够交换到前面单元，记录每次移动的距离较远，因而总的比较和移动次数较少。五、B试题五/B(总题数：1，分数：15.00)5. 【程序说明】函数 int commstr(char * strl ， char * str2 ，int * sublen) 从两字符串strl和str2中，找出它们的所有最长的公共子串。如果最长公共子串不止1个，函数将把它们全部找出并输出。约定空串不作为公共子串。函数将最长公共子串的长度送入

16、由参数sublen所指的变量中，并返回字符串str1和str2的最长公共子串的个数。如果字符串 str1和str2没有公共子串，约定最长公共子串的个数 和最长公共子串的长度均为0。 【程序】 int strlen(char * s) char *t=s; while( * +); return t-s-1; intcommstr(char) *str1,char *str2,i nt *suble n char*s1, *s2; int count=0,len1en 2,k,j,i,p;len 1:=strlen(str1) Ien2 = strlen(str2); if(len1> I

17、en2) s1=str1 ;s2=str2; else Ien2 = len 1;s1 = str2;s2 = str1; for(j=len2;j>0；j-) /* 从可能最长子串开始寻找*/ for(k=0;U (1) /U<:len2;k+)/*k为子串 s2 的开始位置 */ for(i=0;s1U/U!='/0'i+;) /*i为子串 s1的开始位置 */ /*s1 的子串与 s2 的子串比较 */ for (p=0;p < j)&&U/U;p+); if (U/U) /*女口果两子串相同 */ for(p=0);p < j;p

18、+ /* 输出子串 */ printf ("%c",s2k+p); printf ("/n"); count+;/*计数增 1*/ if (cou nt>0) break; *suble n=(cou nt> 0)?U/U:0;return cou nt;(分数： 15.00 ) 正确答案：()解析：(1)k+j i+j-1 (3)s1i+P=s2k+P (4)P=j或 p>=j (5)j 解析略。六、B试题六/B(总题数：1，分数：15.00)6. 【说明】下面是一个Applet程序，其功能是输出已定义好的两个变量x和chr。请改正程

19、序中的错误(有下划线的语句)，使程序能输出正确的结果。注意：不改动程序的结构，不得增行或删行。import java. awt.*; U (1)/U U/U int x=10; U/U Label output1; Label output2; U/U output1 = new Label("定义int类型变量 "+"x,的初值为 "+x); output2 = new Label(" 定义 char类型变量 "+"chr,的初值为 "+chr);add(output1); add(output2); <

20、HTML > < HEAD > <TITLE > ex34_3 </TITLE > < /HEAD > < BODY > U/U width=400 height=400> < /applet> < /BODY > < /HTML >(分数：15.00 )正确答案：()解析： (1)import java.applet .* (2)public class MyApplet exte nds Applet (3) char chr='R' (4)public void i

21、n it() (5)< appletcode二"MyApplet. class 解析创立 applet 程序应导入包applet。applet程序类继承自类Applet。声明字符型变量应当使用单引号。初始化函数必须是公有的。调用applet类应 当使用关键字 code。七、B试题七/B(总题数：1，分数：15.00)7. 【说明】窗体上有两个名为cmdGene和cmdSort的命令按钮。单击 cmdCene按钮时，随机产生10个1,100范围内的整数并将它们放在数组intA中；单击cmdSort按钮时，用选择法排序这10个数并输出。【程序代码】 Dim in tA(1 To 1

22、0)As in teger Private Sub cmdGe ne_Click( ) Dim intl As In tegerRandomize 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 =

23、intA(intJ) intA(intJ)=U (3) /U intMin = intTemp End If Next intJU (4) /U U (5) /U For intl = 1 To 10 PrintStr(intA(intl)+"" Next intl Next lntl Print End Sub(分数：15.00 )正确答案：()解析： (1)1+int(rnd*100) (2)intl+1 (3)intMin (4)intA(intl)=intMin (5)Next intI 解析根据题意， 第一个空应该是产生10个1 , 100范围内的随机整数，因此填

24、“1+int(rnd*100) 。选择排序思想是：第i趟排序开始时，当前有序区和无序区分别为 R1.i-1 和Ri.n(1 < i <r-1),该趟排序那么是从当前 无序区中选出关键字最小的记录Rk，将它与无序区的第1个记录Ri交换，使R1.i和Ri+1.r)分 别变为新的有序区和新的无序区。因为每趟排序均使有序区中增加了一个记录，且有序区中的 记录关键字均不大于无序区中记录的关键字，即第i趟排序之后R1.i . keys < Ri +1.r . keys ,所以进行r-1趟排序之后有R1.r-1 . keys < Rr . key。也就是说，经过r-1趟排序之后，整个

25、文件R1.r递增有序。因此(2)空填“ irtl+1 ； If irtA(irtJ) V irtMir Ther后的3条语句是实现 数 irtA(irtJ)与 irtMir的交换，因此(3)空填“ irtMir ；空是实现最小数与无序区的第1个数交换，因此填“ irtA(irtl)=irtMir；(5)空是循环结束语句，填“Next irtl 。八、B试题八/B(总题数：1，分数：15.00)8.【说明】源程序文件vectorClass.cpp，其中定义了用于表示向量的类vector，但类vector的定义并不完整。请按要求完成以下操作，将类vector的定义补充完整，并给出输出结果。 1 .补充类vector的 构造函数，该函数有参数x和y ,它们都是irt型的数据，默认值都为0。请使用参数列表的形式分别将类的数据成员a和b分别初始化为参数x和y的值。2.完成类vector的成员函数irput(irt x , irt y)的定义， 将irt型的参数x和y分别赋值给数