初級(jí)程序員下午試題-4

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

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

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

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

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

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說(shuō)明】 函數(shù)f(char * str , char del)的功能是：將非空字符串str分割成假設(shè)干個(gè)子字符串并輸出，del表示分割時(shí)的標(biāo)志字符。例如假設(shè)str的值為“ 33123333435 ，de

7、l的 值為“ 3，調(diào)用此函數(shù)后， 將輸出3個(gè)子字符串，分別為“ 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ù)的標(biāo)志字符*/ /*尋找從stri開(kāi)始直到標(biāo)志字符出現(xiàn)的一個(gè)子字符串*/ j=i+1;給找到的字符序列置字符while(strj != del && strj ! = 7O')j + U(4) /U: '/0' /*串結(jié)束標(biāo)志*/ pri

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

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

10、的結(jié)點(diǎn)總是靠近表頭?！竞瘮?shù)】void Locate( int &x) <結(jié)點(diǎn)類(lèi)型說(shuō)明> * p =first -> next;while(p!=frist&&U (1) /U)P=P-> next; if(p! =first) /*鏈表中存在 x*/ U (2) /U;<結(jié)點(diǎn)類(lèi)型說(shuō)明 > * current = P; /*從鏈表中摘下這個(gè)結(jié)點(diǎn)*/ 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"); /*沒(méi)找至 U*/ (分?jǐn)?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é)點(diǎn)(如存在的話)，因此(1)空應(yīng)填寫(xiě)“ p- >data!=x 。顯然，(2)空是 使該結(jié)點(diǎn)的訪問(wèn)頻度加1,因此空應(yīng)填寫(xiě)“ p- >freq+ ?？账诘难h(huán)是根據(jù)訪問(wèn)頻度定位x結(jié)點(diǎn)的新位置，用P指向x結(jié)點(diǎn)的前驅(qū)，因此 (3)空處應(yīng)填“cu rrent- >freq > P->freq 。、空 之間的語(yǔ)句是將結(jié)點(diǎn)x

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

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

16、由參數(shù)sublen所指的變量中，并返回字符串str1和str2的最長(zhǎng)公共子串的個(gè)數(shù)。如果字符串 str1和str2沒(méi)有公共子串，約定最長(zhǎng)公共子串的個(gè)數(shù) 和最長(zhǎng)公共子串的長(zhǎng)度均為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-) /* 從可能最長(zhǎng)子串開(kāi)始尋找*/ for(k=0;U (1) /U<:len2;k+)/*k為子串 s2 的開(kāi)始位置 */ for(i=0;s1U/U!='/0'i+;) /*i為子串 s1的開(kāi)始位置 */ /*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+;/*計(jì)數(shù)增 1*/ if (cou nt>0) break; *suble n=(cou nt> 0)?U/U:0;return cou nt;(分?jǐn)?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，分?jǐn)?shù)：15.00)6. 【說(shuō)明】下面是一個(gè)Applet程序，其功能是輸出已定義好的兩個(gè)變量x和chr。請(qǐng)改正程

19、序中的錯(cuò)誤(有下劃線的語(yǔ)句)，使程序能輸出正確的結(jié)果。注意：不改動(dòng)程序的結(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類(lèi)型變量 "+"x,的初值為 "+x); output2 = new Label(" 定義 char類(lèi)型變量 "+"chr,的初值為 "+chr);add(output1); add(output2); <

20、HTML > < HEAD > <TITLE > ex34_3 </TITLE > < /HEAD > < BODY > U/U width=400 height=400> < /applet> < /BODY > < /HTML >(分?jǐn)?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程序類(lèi)繼承自類(lèi)Applet。聲明字符型變量應(yīng)當(dāng)使用單引號(hào)。初始化函數(shù)必須是公有的。調(diào)用applet類(lèi)應(yīng) 當(dāng)使用關(guān)鍵字 code。七、B試題七/B(總題數(shù)：1，分?jǐn)?shù)：15.00)7. 【說(shuō)明】窗體上有兩個(gè)名為cmdGene和cmdSort的命令按鈕。單擊 cmdCene按鈕時(shí)，隨機(jī)產(chǎn)生10個(gè)1,100范圍內(nèi)的整數(shù)并將它們放在數(shù)組intA中；單擊cmdSort按鈕時(shí)，用選擇法排序這10個(gè)數(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(分?jǐn)?shù)：15.00 )正確答案：()解析： (1)1+int(rnd*100) (2)intl+1 (3)intMin (4)intA(intl)=intMin (5)Next intI 解析根據(jù)題意， 第一個(gè)空應(yīng)該是產(chǎn)生10個(gè)1 , 100范圍內(nèi)的隨機(jī)整數(shù)，因此填

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

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