初級程序員下午試題-4

1、初級程序員下午試題-4(總分：120.00 ,做題時間：90分鐘)一、B試題一 /B(總題數(shù)：1，分數(shù)：15.00)1.【算法說明】 為便于描述屏幕上每個像素的位置，在屏幕上建立平面直角坐標系。屏幕左上角 的像素設(shè)為原點，水平向右方向設(shè)為X軸，垂直向下方向設(shè)為Y軸。設(shè)某種顯示器的像素為128 X 128，即在每條水平線和每條垂直線上都有128個像素。這樣，屏幕上的每個像素可用坐標(x, y)來描述其位置，其中x和y都是整數(shù)，0< x< 127 , 0< y< 127?，F(xiàn)用一維數(shù)組 MAP來存儲整個一屏顯示的位圖信息。 數(shù)組的每個元素有 16位二進位， 其中每 位對應(yīng)一個

2、像 素，“ 1 表示該像素“亮，“ 0表示該像素“暗。數(shù)組 MAP的各個元 素與屏幕上的像素相對應(yīng)后，其位置可排列如下：MAP(0) , MAP(1) , ? , MAP(7)MAP(8) , MAP(9) , ? ,MAP(15)MAP(1016) , MAP(1017) , ? , MAP(1023)下述算法可根據(jù)用戶要求，將指定坐標(x , y)上的像素置為“亮或“暗。在該算法中，變量X，丫 , , S ,K都是16位無符號的二進制整數(shù)。 數(shù)組BIT中的每個元素BIT(K)(K=0 , ? , 15)的值是左起第K位為1，其余位均為0的16位無符號二進制整數(shù)，即 BIT(K)的值為215

3、-k?！舅惴ā?x , y),算出該像素的位置所屬的數(shù)組元素MAP(V)。第1步 根據(jù)用戶指定像素的位置坐標 這一步的具體實現(xiàn)過程如下：1 .將x送變量X,將y送變量Y;2 .將Y左移U (1) /U位，仍存入變量Y;3 .將 X右移U/U位，并存入變量S ；4.計算Y+S,存入變量 第2步算出指定像素在 將變量V，得到像素的位置所屬的數(shù)組元素MAP(V)中所對應(yīng)的位置K(K=0 , ?MAP(V) o15)。這一步的具體實現(xiàn)過程如下：X與二進制數(shù)U/U進行邏輯乘運算，并存入變量K第3步 根據(jù)用戶要求將數(shù)組元素MAP(V)左起第K位設(shè)置為“ 1或“ 0。這一步的具體實現(xiàn)過程如下：1 .為把指定

4、像素置“亮，應(yīng)將MAP(V)與BIT(K)進行邏輯U/U運算，并存入MAP(V)2 .為把指定像素置“暗，應(yīng)先將 BIT(K)各位取反，再將MAP(V)與BIT(K)進行邏輯U/U運 算，并存入 MAP(V)。(分數(shù)：15.00 )正確答案：()解析：(1)3 (2)4 (3)1111 (4)或(加)與(乘)解析(1)由于每一行像素占用8個數(shù)組元素，所以第y行的像素占用數(shù)組的第8約到8 X y+7號元素。于是y需要乘以8存入變量Y ,即左移3位。(2)x表示y行上的第x列像素，因為每個數(shù)組兀素表示16個像素，所以需要將 x除以16，得到所在數(shù)組元素位置，即右移4位。(3)X的后四位即表示像素在

5、 MAP(V)中所對應(yīng)的位置，因此取 x的后4位送入K即 可。因為0和1與1邏輯或的結(jié)果都是 1，而與0邏輯或的結(jié)果不變。所以將 MAP(V)與BIT(K) 進行邏輯或(加),即可將MAP(V)指定位置“ 1 。(5)0和1與0邏輯與的結(jié)果都是 0,而與1邏輯 與的結(jié)果不變，所以將MAP(V)與取反后的BIT(K)進行邏輯與(乘)，即可將MAP(V)指定位置“ 0。B試題二/B(總題數(shù)：1，分數(shù)：15.00)2.【函數(shù)2.1說明】 函數(shù)pal in drome(char s)的功能是，判斷字符串s是否為回文字符串，假設(shè)是,那么 返回0,否那么返回-1。假設(shè)一個字符串順讀和倒讀都一樣時，稱該字符

6、串是回文字符串，例如：“ LEVEL是回文字符串，而“ LEVAL 不是。 【函數(shù) 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; 【函數(shù)2.2說明】 函數(shù)f(char * str , char del)的功能是：將非空字符串str分割成假設(shè)干個子字符串并輸出，del表示分割時的標志字符。例如假設(shè)str的值為“ 33123333435 ，de

7、l的 值為“ 3，調(diào)用此函數(shù)后， 將輸出3個子字符串，分別為“ 12、“4和“ 5。【函數(shù) 2.2 】void f( char * str, char del) int i ,j ,len; len 二 strlen (str) i=0; while(i < len) while(U/U)i+; /* 忽略 連續(xù)的標志字符*/ /*尋找從stri開始直到標志字符出現(xiàn)的一個子字符串*/ j=i+1;給找到的字符序列置字符while(strj != del && strj ! = 7O')j + U(4) /U: '/0' /*串結(jié)束標志*/ pri

8、ntf("%s/t", &stri); U(5) /U; (分數(shù)：15.00 )正確答案：()解析：(1)*pi=*pj (2)pi <pj 或者等價表達式(3)stri=del (4)strj (5)i=j+1 解析(1)指針 pi從左往右移動，指針pj從右往左移動，每移動一次，判斷二者指向的兀素是否相等，所以此處應(yīng)填入判斷語句*pi= =*pj o (2)pi如果能移動到pj右面，說明字符串是回文字符串，否那么返回-1，所以此處應(yīng)填入pi < pj或者其他等價表達式。此處表達式判斷當前字符是否等于標志字符del ,即填入stri=del。(4)此處表

9、達式為符合要求的字符串置結(jié)束標志，此時 j已指向最后，所以應(yīng)填 入strj即可。此處語句是修改i指針進行下一次循環(huán)，所以應(yīng)填入i=j+1。三、B試題三/B(總題數(shù)：1，分數(shù)：15.00)放數(shù)據(jù)的成員data和訪問頻度freq。所有結(jié)點的freq初始時都為0。每當 在鏈表上進行一次3.鏈表L,每個結(jié)點有4個數(shù)據(jù)成員：【說明】設(shè)有一個帶表頭結(jié)點的雙向循環(huán)指向前驅(qū)結(jié)點的指針 prior、指向后繼結(jié)點的指針next、存L.Locate(x)操作時，令元素值 x的結(jié)點的訪問頻度freq加1,并將該結(jié)點前移，鏈接 到現(xiàn)它的訪問頻度相等的結(jié)點后面，使得鏈表中所有結(jié)點保持按訪問頻度遞減的順序排列，以使頻繁訪問

10、的結(jié)點總是靠近表頭。【函數(shù)】void Locate( int &x) <結(jié)點類型說明> * p =first -> next;while(p!=frist&&U (1) /U)P=P-> next; if(p! =first) /*鏈表中存在 x*/ U (2) /U;<結(jié)點類型說明 > * current = P; /*從鏈表中摘下這個結(jié)點*/ 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*/ (分數(shù)： 15.00 )正確答案： ()

12、解析：(1)p- > data!=x (2)p- >freq+ (3)current- >freq > P-> freq (4)p- >next (5)current 解析 (1)空所在的循 環(huán)是定位x，將指針指向x結(jié)點(如存在的話)，因此(1)空應(yīng)填寫“ p- >data!=x 。顯然，(2)空是 使該結(jié)點的訪問頻度加1,因此空應(yīng)填寫“ p- >freq+ 。空所在的循環(huán)是根據(jù)訪問頻度定位x結(jié)點的新位置，用P指向x結(jié)點的前驅(qū)，因此 (3)空處應(yīng)填“cu rrent- >freq > P->freq 。、空 之間的語句是將結(jié)點x

13、插入在P之后?？账谡Z句是將指針P指向x結(jié)點的前驅(qū)，因此空應(yīng)填寫“ p- >next 。(5)空所在語句是將P后繼指向結(jié)點current ,因此空(5)處應(yīng)填寫a力curre nt 。四、B試題四/B(總題數(shù)：1，分數(shù)：15.00)4. 【說明】 函數(shù)Quicksort是在一維數(shù)組An上進行快速排序的遞歸算法?！竞瘮?shù)】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; (分數(shù)： 15.00 )正確答案：()解析： (1)Ai <x Ai=Aj< 3)Aj=temp (4)QuickSort(A, s, j-1) (5)QuickSort(A , j+1 , t);解析快速排序的思想是：任取待排序序列中的某個元素作為基準(一般取第一個元素),通過一趟排序，將待排元素分為左右兩個子序列，左子序列元素的排序碼均小于或等于基準元素的排序碼，右子 序列的排序碼那么大于基準元素的排序碼，然后分別對兩個

15、子序列繼續(xù)進行排序，直至整個序列有序?？焖倥判蚴菍γ芭菖判虻囊环N改進方法，算法中元素的比較和交換是從兩端向中間進行的，排序碼較大的元素一次就能夠交換到后面單元，排序碼較小的記錄一次就能夠交換到前面單元，記錄每次移動的距離較遠，因而總的比較和移動次數(shù)較少。五、B試題五/B(總題數(shù)：1，分數(shù)：15.00)5. 【程序說明】函數(shù) int commstr(char * strl ， char * str2 ，int * sublen) 從兩字符串strl和str2中，找出它們的所有最長的公共子串。如果最長公共子串不止1個，函數(shù)將把它們?nèi)空页霾⑤敵?。約定空串不作為公共子串。函數(shù)將最長公共子串的長度送入

16、由參數(shù)sublen所指的變量中，并返回字符串str1和str2的最長公共子串的個數(shù)。如果字符串 str1和str2沒有公共子串，約定最長公共子串的個數(shù) 和最長公共子串的長度均為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+;/*計數(shù)增 1*/ if (cou nt>0) break; *suble n=(cou nt> 0)?U/U:0;return cou nt;(分數(shù)： 15.00 ) 正確答案：()解析：(1)k+j i+j-1 (3)s1i+P=s2k+P (4)P=j或 p>=j (5)j 解析略。六、B試題六/B(總題數(shù)：1，分數(shù)：15.00)6. 【說明】下面是一個Applet程序，其功能是輸出已定義好的兩個變量x和chr。請改正程

19、序中的錯誤(有下劃線的語句)，使程序能輸出正確的結(jié)果。注意：不改動程序的結(jié)構(gòu)，不得增行或刪行。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 >(分數(shù)：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 解析創(chuàng)立 applet 程序應(yīng)導(dǎo)入包applet。applet程序類繼承自類Applet。聲明字符型變量應(yīng)當使用單引號。初始化函數(shù)必須是公有的。調(diào)用applet類應(yīng) 當使用關(guān)鍵字 code。七、B試題七/B(總題數(shù)：1，分數(shù)：15.00)7. 【說明】窗體上有兩個名為cmdGene和cmdSort的命令按鈕。單擊 cmdCene按鈕時，隨機產(chǎn)生10個1,100范圍內(nèi)的整數(shù)并將它們放在數(shù)組intA中；單擊cmdSort按鈕時，用選擇法排序這10個數(shù)并輸出?！境绦虼a】 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(分數(shù)：15.00 )正確答案：()解析： (1)1+int(rnd*100) (2)intl+1 (3)intMin (4)intA(intl)=intMin (5)Next intI 解析根據(jù)題意， 第一個空應(yīng)該是產(chǎn)生10個1 , 100范圍內(nèi)的隨機整數(shù)，因此填

24、“1+int(rnd*100) 。選擇排序思想是：第i趟排序開始時，當前有序區(qū)和無序區(qū)分別為 R1.i-1 和Ri.n(1 < i <r-1),該趟排序那么是從當前 無序區(qū)中選出關(guān)鍵字最小的記錄Rk，將它與無序區(qū)的第1個記錄Ri交換，使R1.i和Ri+1.r)分 別變?yōu)樾碌挠行騾^(qū)和新的無序區(qū)。因為每趟排序均使有序區(qū)中增加了一個記錄，且有序區(qū)中的 記錄關(guān)鍵字均不大于無序區(qū)中記錄的關(guān)鍵字，即第i趟排序之后R1.i . keys < Ri +1.r . keys ,所以進行r-1趟排序之后有R1.r-1 . keys < Rr . key。也就是說，經(jīng)過r-1趟排序之后，整個

25、文件R1.r遞增有序。因此(2)空填“ irtl+1 ； If irtA(irtJ) V irtMir Ther后的3條語句是實現(xiàn) 數(shù) irtA(irtJ)與 irtMir的交換，因此(3)空填“ irtMir ；空是實現(xiàn)最小數(shù)與無序區(qū)的第1個數(shù)交換，因此填“ irtA(irtl)=irtMir；(5)空是循環(huán)結(jié)束語句，填“Next irtl 。八、B試題八/B(總題數(shù)：1，分數(shù)：15.00)8.【說明】源程序文件vectorClass.cpp，其中定義了用于表示向量的類vector，但類vector的定義并不完整。請按要求完成以下操作，將類vector的定義補充完整，并給出輸出結(jié)果。 1 .補充類vector的 構(gòu)造函數(shù)，該函數(shù)有參數(shù)x和y ,它們都是irt型的數(shù)據(jù)，默認值都為0。請使用參數(shù)列表的形式分別將類的數(shù)據(jù)成員a和b分別初始化為參數(shù)x和y的值。2.完成類vector的成員函數(shù)irput(irt x , irt y)的定義， 將irt型的參數(shù)x和y分別賦值給數(shù)