初級程序員2011下半年下午試題

1、初級程序員 2011 下半年下午試題試題一 閱讀以下說明和流程圖。 說明 以下流程圖用于檢查數(shù)組 A1:n 中的元素是否為自然數(shù) 1n 的一個排列 ( 含有 1n 各數(shù) ) 。若是，則輸出 OK，否則輸出所缺的自然數(shù)及其個數(shù) m。為檢查 A1:n 中是否含有 k，只要判斷 P(k)=(A(1)-k)*(A(2)- k)* *(A(n -k) 是否等于 0 即可。 流程圖 試題二1、閱讀以下說明和 C 程序代碼。 說明 下面是一個待修改的 C 程序，其應該完成的功能是：對于輸入的一個整數(shù) num，計算其位數(shù) k，然后將其各位數(shù)字按逆序轉(zhuǎn)換為字符串保存并輸出。若 num為負整數(shù)，則輸出字符串應有前

2、綴“ - ”。例如，將該程序修改正確后，運 行時若輸入“ 14251”，則輸出“ 15241”；若輸入“ - 6319870”，則輸出“ - 0789136”。下面給出的 C 程序代碼中有五處錯誤，請指出錯誤代碼所在的行號并給出 修改正確后的完整代碼行。 C 程序代碼 行號 代 碼01 #include 02 #include 03 int main()04 05 long num=0,t=0;char *pstr,i=0,k=0;0607 scanf(%1d, num); /* 輸入一個整數(shù)，存入 num*/08 t=num; k=num!=0?0:1 ；09 while(t =0) /*

3、計算位數(shù) */10 t=t/10;11 k+;12 1314 pstr=(char *)malloc(k+2)*sizeof(char);/ 十申請字符串的存儲空間15 */16 if(pstr=0)return-1;1718 i=0 ：19 if(num 0; k-) /*形成字符串 */24pstri+=num%10;25num=num/10;2627pstrk= 0； /*設置字符串結(jié)尾 */28printf(%sn, pstr);29free(pstr);30return 0 ：試題三 閱讀以下說明和 C 代碼。 說明 某市在進行市長選舉，該市共分為 M個選區(qū)（1 M6，從 1 開始順

4、序編 號），共有 N個競選者參選 （1 N5，從 A開始順序編號 ） 。經(jīng)投票后，所得選 票數(shù)據(jù)如表 3-1 所示。表 3-1 選票數(shù)據(jù) 選區(qū) 競選者 A競 選者 B競 選者 C競 選者 D1192482063721479031221318612121384114214083952671338229現(xiàn)已將選票數(shù)據(jù)存入文本文件 data.txt ，該文件內(nèi)容格式如下：共有 M 行，每行 N+1個整數(shù)，第一個整數(shù)為選區(qū)編號，隨后為 N 個競選者在該選區(qū)所 得票數(shù)。下面的程序先從文件中讀入選票數(shù)據(jù)存入二維數(shù)組 data ，然后完成下列 功能：a計算并顯示每個競選者獲得的選票數(shù)及占總選票數(shù)的百分比；

5、b如果任一競選者獲得的選票數(shù)超過總選票數(shù)的 50%，則顯示該競選者 獲勝；c如果沒有競選者獲得總選票數(shù)的 50%以上，則顯示兩位得票最高的競 選者需再進行決選。在下面的程序代碼中，競選者 A 的編號為 1，競選者 B的編號為 2，以此 類推。C 代碼 #include #include #define M5#define N4/* 選區(qū)數(shù) */* 競選者人數(shù) */int main (int argc,char argv) FILE *fin;int dataM+1 N+1;Mj 存放 j 號競選者得票總數(shù) */int MAXP1,cd1; 選者編號 */int MAXP2, cd2; 選者編號

6、 */int i,j,totalP;fin=fopen (data.txt,r);if (!fin) return -1; i=0 ； j=0 ； while(!feof(fin)/*data 0 存放選區(qū)編號， data /*MAXP1、cd1 存放得票最多者的票數(shù)和競 /*MAXP2、cd2 存放得票次多者的票數(shù)和競 /*totalP 存放總票數(shù) */* 從文件讀入數(shù)據(jù) */fscanf( fin,%d, &dataij);(1) ;if(j N) j=0 ； i+ ；fclose( fin);totalP=0; MAXP1=0; MAXP2=0; cd1=0; cd2=0; for(j=

7、1; j N+1; j+)dataMj= (2) ; /* 設置競選者 得票總數(shù)初始值 */for(i=0; i MAXP1) (3) ;cd2=cd1;MAXP1=dataM j; cd1=j;elseif (dataM j MAXP2) (MAXP2=dataM j; cd2=j;(4) ; /* 計 算總票數(shù) */for(j=1 ； j 0.5)/* 判斷得票數(shù)最多者的得票率 */n,cd1+A -1);elseprintf (Result: Candidate-%C PK Candidate- n,cd1+A -1, cd2+A-1);system( pause ) ；return 0

8、 ；試題三 閱讀以下說明和 C 函數(shù)。 說明 約瑟夫問題是一個經(jīng)典的問題，其描述是：有 n 個人(編號為 1 n)圍成 一圈，從第 1 個人開始，按照順時針方向從 1 開始計數(shù)到 m(即數(shù)到第 m個人) ， 讓其出圈，然后再從其順時針方向的下一個人開始，依次計數(shù)到 m 并讓其出圈， 重復這個過程，直到所有人都出圈，試給出出圈者的順序。以 n-5 ，m-3 為例，其出圈順序為 3，1，5，2，4，過程如圖 4-1 所示。下面的函數(shù) Joseph() 在單向循環(huán)鏈表表示的基礎上模擬上述出圈過程。 n 為 5 時的單向循環(huán)鏈表結(jié)構(gòu)如圖 4-2 所示。鏈表的結(jié)點類型定義如下：typedef struc

9、t Nodeint no;struct Node *next;Node, *LinkList;函數(shù) Joseph(LinkList tail，int n ， int m) 的處理思路如下：(1) 用 k 計數(shù)，每次都從 0 開始，當計數(shù)到 m-1 時結(jié)束本次計數(shù)；(2) 通過指針 p 查找出圈者所對應的結(jié)點，當 k 的值等于 m-1時， p 應指 向出圈者對應結(jié)點的前驅(qū)結(jié)點；(3) 通過刪除結(jié)點表示出圈處理；(4) 當 m 大于圈中剩余人數(shù)時，為了避免重復計數(shù)，用模運算修改m的值；(5) 計數(shù)和刪除操作完成后再恢復 m的原值。C 函數(shù) void Joseph (LinkList tail, i

10、nt n, int m) /* 單循環(huán)鏈表包含 n 個結(jié)點， tai1 為鏈表的尾指針， m 為計數(shù)值 */ LinkList p ， q；int k ，i ，old_m=m;p=tai1;for(i=n; i 1; -i)/*i 表示圈中剩余人數(shù) */m=m%i; /* 避免重復計數(shù) */ if(0=m)m= (1) ;k=0;while (knext;(5) =q- next; 的結(jié)點 */ free (q) ； m=old_m;printf( %dn,p- No);試題五 閱讀以下說明、圖和 C+代碼。 說明 已知某公司主要有兩大類耗電資產(chǎn) (Asset): 計算機 (ComputerA

11、sset) 和建 筑物(Building Asset) 。為了節(jié)約能源，通過控制各種電源，將可關(guān)閉的房燈、 計算機顯示器等在夜間關(guān)閉。為了實現(xiàn)上述需求，設計了如圖 5-1 所示的類圖，并用下面的 C+代碼加 以實現(xiàn)。C 抖代碼#include #include using namespace std;class Asset/* 通用資產(chǎn)，基類 */public: virtual Asset()；class PowerSwitchable /* 抽象基類， 可在夜間關(guān)閉電源的物體接口 */public: virtual void powerDown()=0 ； /*powerDown() 函 數(shù)

12、接口 */virtual void powerUp()=0; /*powerUp 函數(shù)接口 */;class ComputerAsset ：public Asset/* 計算機資產(chǎn) */protected: int deskNumber;public ：ComputerAsset (int deskNumber) this- deskNumber=deskNumber; ；class ComputerCPU(1) /* 計算機主機，永不關(guān)閉 */ComputerAssetpublic ：ComputerCPU (int deskNumber) :(deskNumber) ；class Comp

13、uterMonitor (2) /* 計算機顯示器 */ public ：ComputerMonitor (introomNumber): ComputerAsset(roomNumber),PowerSwitchable() ComputerMonitor() void powerDown() void powerUp() /* 關(guān)電源，代碼略 */* 開電源，代碼略 */;/*BuildingAsset 、 BuildingLight.EmergencyLight和 RoomLights 代碼略*/class BuildingManagement private ：Asset* thing

14、s 24; int numltems;public ：void goodNight()/* 值班員定時“關(guān)閉”時調(diào)用，關(guān)閉可關(guān)閉的 電源*/for (int i=0; i numltems; i+)(3) ps=dynamlc_cast (things i);if (ps !=0)ps- powerDown();/*goodMorning() 與 goodNight() 類似，依次調(diào)用 powerUp() ，實現(xiàn)略 */ void add (Asset* thing) /* 為建筑添加資產(chǎn) */ things (4) =thing;int main() BuildingManagement*

15、b1= (5) BuildingManagement();/101 房間的控/101 房間的應急/101 房間 4 號b1- add (new RoomLights (101); 制燈b1- add (new EmergencyLight (101); 燈b1- add (new ComputerCPU (10104); 桌上的計算機主機b1- add (new ComputerMonitor (10104); /101房間 4號桌上的計算機顯示器b1- goodNight();delete b1;試題六 閱讀以下說明和 Java 代碼。 說明 6-1 所示的類圖，并用下面的 Java 代碼已

16、知某公司主要有兩大類耗電資產(chǎn) (Asset) ：計算機 (ComputerAsset) 和建 筑物(Building Asset) 。為了節(jié)約能源，通過控制各種電源，將可關(guān)閉的房燈、 計算機顯示器等在夜間關(guān)閉。為了實現(xiàn)上述需求，設計了如圖 加以實現(xiàn)。口*/*/Java 代碼 abstract class Asset interface PowerSwitchablepublic void powerDown(); public void powerUp();/* 通用資產(chǎn)，基類 */ /* 可在夜間關(guān)閉電源的物體實現(xiàn)該接abstract class BuildingAsset extends

17、Asset/* 建筑物資產(chǎn)protected int room;public BuildingAsset (int room) this .room=room;abstract class BuildingLight extends BuildingAsset / 燈的通用信息： flourescent/incandescent BuildingLight (int roomNumber) (roomNumber); class EmergencyLight (1) ( /* 應急燈， EmergencyLight (introomNumber) super (roomNumber);等，略

18、super永不關(guān)閉 */class RoomLights (2) RoomLights (int roomNumber) public void powerDown() public void powerUp() super( roomNumber); /* 關(guān)電源，代碼略 */ /* 開電源，代碼略 */ /*ComputerAsset.ComputerCPU 和 ComputerMonitor 代碼略 */ public class BuildingManagement Asset things =new Asset24;int numltems=0 ；public void goodNi

19、ght() /* 值班員定時”關(guān)閉”時調(diào)用，關(guān) 閉可關(guān)閉的電源 */for (int i=0; i=0”改為“ t!=0第 14 行沒有錯誤。第 15 行的錯誤很明顯，也很常見，即將“ =”誤用為“ =”，從而改變其 所在語句的語義，其中的“ pst=O”則將 pstr 的值重置為 0，使 pstr 所記錄的 字符串存儲空間首地址信息丟失，此后針對 pstr 的運算都會出錯。第 17 行至第 21 行用于處理 num為負數(shù)時輸出字符串應包含前綴“一”的要求，這幾行沒有錯誤。第 22 行至第 25 行用于從 num 得到其逆置的數(shù)字字符串，其錯誤在第 23 行，屬于邏輯錯誤。 num%10的運算

20、結(jié)果為 num的個位數(shù)字，而 pstr 中要存儲 的是數(shù)字字符 ( 即 ASCII 值) ，因此應將 num%10的運算結(jié)果加上字符 0( 或字 符0的 ASCII 碼值 48) 。第 26 行用于設置字符串結(jié)束標志，需要注意的是串結(jié)束標志的位置。由 于 num可能為負數(shù)，因此將字符串結(jié)束標志字符設置在 k 下標處可能出錯，保 險的做法是繼續(xù)用 i 作為下標，使得 0 正好跟在最后一個數(shù)字字符的后面。第 27 行至第 30 行沒有錯誤。試題三1、j+ ，或+j ，或其等價表示2、3 、MAXP2=MAXP1 4 、totalP+=dataMj ，或 totalP+=totalP+ dataMj

21、 ，或其等價表示 5、(double)MAXP1/totalP ，或 (float)MAXP1/totalP ，或其等價表示其中，將 (double) 或(float) 寫在 totaIP 之前亦可 解析 本題考查 C程序設計基本能力。 題目中涉及的知識點主要有數(shù)組、文件、循環(huán)和類型轉(zhuǎn)換，分析程序時首 先要明確各個變量 ( 或數(shù)組元素 ) 所起的作用，并以語句組分析各段代碼的功能， 從而完成空缺處的代碼填充。根據(jù)題目描述，首先將文件中的數(shù)據(jù)讀入數(shù)組 data 。顯然， i 和 j 分別起 行號、列號的作用。行號 i 應在一行的數(shù)據(jù)都讀入后增加 1，而列號 j 則每讀 入一個數(shù)據(jù)就要增加 1，因

22、此空(1) 處應填寫“ j+ ”或其等價形式的語句。將數(shù)據(jù)讀入數(shù)組 data 后，以題中的數(shù)據(jù)為例， data 數(shù)組的內(nèi)容可表示如 下：data00=1data10=2data20=3data30=4data40=5 data50=?data01=192data11=147data21=186data31=114 data41=267 data51=?data02=48 data12=90 data22=12 data32=21 data42=13 data52=?data03=206data13=312data23=121data33=408 data43=382 data53=?由于 da

23、taMi 存放 i 號競選者的得票總數(shù)， data0data04=37data14=21data24=38data34=39data44=29 data54=? 存放的是選區(qū)編號，因此 dataM0 不用。以上表為例，需要將 data01 、data11 、. 、 dataM-11 加起 來存入 dataM1 ，因此，空 (2) 處應填入 0，以設置 dataM1 、dataM 2 、 .dataMN 的初始值?？?3) 所在的語句組用于找出得票數(shù)最多的競選者，此時，因此之前的最 多票數(shù)( MAXP1)將成為次多數(shù)(MAXP2)，即空(3) 處填入“ MAXP2=MAX”P1?？?4) 處為計

24、算總票數(shù)的語句，根據(jù)說明，應填入“ totalP+=dataMj 或其等價形式。空(5) 處為計算票數(shù)最多者得票率的表達式，根據(jù)說明是將 MAXP1除以totalP ，需要注意的是： MAXP1和 totalP 都是整數(shù)且 MAXP1小于 totalP ，因此 應至少對其中的一個數(shù)值進行整數(shù)到實數(shù)的類型轉(zhuǎn)換，否則其結(jié)果為0，因此，空 (5) 處應填入“ (double)MAXP1/totalP ”或其等價形式。試題三1、2 、m-13 、p=p- next4 、p- next- No5、p- next 解析 本題考查 C程序設計基本能力及指針的應用。題目中涉及的考點主要有鏈表運算和程序邏輯，分

25、析程序時首先要明確各 個變量所起的作用，并按照語句組分析各段代碼的功能，從而完成空缺處的代 碼填充。根據(jù)函數(shù) Joseph 的處理思路，“ m=m%”i 可避免計數(shù)過程重復 ( 通俗來說， 就是計數(shù)時繞著圈地數(shù) ) ，需要考慮的特殊情況是 m可能取值為 0，此時對應的 情況應該是正好要數(shù)到目前所在位置的前一個人，由于鏈表指針的單向特點， 還需逐個結(jié)點數(shù)過去才行，即當圈中還剩下 i 個人時，最多計數(shù)到 i ，因此空 (1) 處應填入“ i ”。下面的語句組在單循環(huán)鏈表中掃描結(jié)點并完成計數(shù)。由于計數(shù)器 k 從 0 開始計數(shù)，因此， while 語句的循環(huán)條件應為“ knext ”。根據(jù)題目中函數(shù)

26、Joseph 的處理思路說明，當 k 的值等于 m-1時， p 指向 出圈者對應結(jié)點的前驅(qū)結(jié)點，因此， p- next 所指向的結(jié)點是要被刪除的結(jié)點， 其編號為 p- next- No，因此空 (4) 處應填入“p- next- No”。刪除 p所指結(jié)點的后繼結(jié)點的處理如下圖所示，即要刪除數(shù)據(jù)域為 y 的結(jié) 點，需要將 p 所指結(jié)點的指針域指向 z 結(jié)點，對應的處理是： p- next=p- next- next ，由于已經(jīng)使得 q 指向了 y 結(jié)點，從而有等同的處理： p- next=q- next 因此空 (5) 處應填入“p- next ”。試題五1、: public ComputerA

27、sset2 、: public ComputerAsset, publicPowerSwitchable 3 、 PowerSwitchable*4 、 numltems+5、new 解析 本題考查面向?qū)ο蟪绦蛟O計及其 C+語言實現(xiàn)的能力，涉及類和抽象類、 對象、函數(shù)和虛函數(shù)的定義和相關(guān)操作以及繼承關(guān)系。要求考生根據(jù)給出的案 例、類圖和執(zhí)行過程說明，認真閱讀理清程序思路，然后完成題目。先考查針對案例的特定需求，構(gòu)建類圖整體結(jié)構(gòu)。本題中根據(jù)類圖定義了 以下類：BuildingManagement 、 Asset 、 ComputerAsset、 BuildingAsset 、 ComputerC

28、PU、ComputerMoniter 、BuildingLight 、 RoomLights、 EmergencyLight 和 PowerSwitchable 。其中， Asset 為抽象類，表示通用資產(chǎn)， 作為所有資產(chǎn)類的基類； ComputerAsset 表示計算機有關(guān)資產(chǎn)、 BuildingAsset 表示建筑物有關(guān)資產(chǎn)，兩者作為 Asset 的子類，繼承了 Asset 類； ComputerCPU、 ComputerMoniter 分別表示計算機 CPU和顯示器，繼承了 ComputerAsset 。 BuildingLight 是一種建筑物資產(chǎn)，表示建筑物內(nèi)的照明設備，繼承了 Bu

29、ildingAsset ，而照明設備有 RoomLights 和 EmergencyLight ，作為BuildingLight 的子類。由于案例中兩大類耗電資產(chǎn) (Asset): 計算機 (ComputerAsset) 和建筑物 (Building Asset) ，可在夜間關(guān)閉的房燈 (RoomLights) 、計算機顯示器 (ComputerMoruter) 屬于不同的資產(chǎn)類型，所以將 可關(guān)閉的資產(chǎn)設計為抽象基類 PowerSwitchable ，規(guī)定可在夜間關(guān)閉電源的物 體的開關(guān)電源接口，即包含兩個純虛擬 (virtual) 函數(shù)。因此， RoomLights 和 ComputerMon

30、iter 繼承了 PowerSwitchable 。C+中有不同種類的繼承方式，本題目中， ComputerCPU是 ComputerAsset 的子類，并且在子類的構(gòu)造函數(shù)中，調(diào)用父類的構(gòu)造函數(shù)，所以繼承的權(quán)限為 public 。其語法為： public 后加父類名。 ComputerMonitor 是 ComputerAsset 的子類，而且均是可關(guān)閉的，具有開關(guān)電源的相同接口，均繼承了 PowerSwitchable ，并且在子類的構(gòu)造函數(shù)中，調(diào)用父類的構(gòu)造函數(shù)，所以繼承 的權(quán)限均為 public ，多個父類的繼承語法是： public 父類名 1，public 父類名 2。系統(tǒng)中有各類

31、資產(chǎn)，在 BuildingManagement 中使用 Asset 通用資產(chǎn)類型 數(shù)組，用 add函數(shù)依次為建筑添加資產(chǎn)。由于 add 函數(shù)中對數(shù)組添加元素只有 一條語句，需要在下標中完成指明當前添加資產(chǎn)元素的下標，并將下標后移。 在 goodNight 函數(shù)中對可關(guān)閉的資產(chǎn)進行控制，需要判定其是否可關(guān)閉，也就 是資產(chǎn)是否為 PowerSwitchable 類的子類。通過動態(tài)類型轉(zhuǎn)換進行判定，如果 資產(chǎn)類型是 PowerSwitchable 的子類，則轉(zhuǎn)換后的類型調(diào)用相應接口，并綁定 到具體對象，執(zhí)行對象的關(guān)閉電源行為。類 BuildingManagement 中沒有定義構(gòu)造函數(shù)，編譯器會生成

32、一個缺省的 構(gòu)造函數(shù)，采用 new關(guān)鍵字進行對象創(chuàng)建。使用完成之后，通過 delete 進行釋 放。因此空 (1) 需要表現(xiàn)出公有繼承： public ComputerAsset ；空 (2) 處添加繼 承兩個父類，并且權(quán)限均為 public ，即： public ComputerAsset ， public PowerSwitchable ；空 (3) 處動態(tài)類型轉(zhuǎn)換為抽象類，即 PowerSwitchable* ；空 (4) 處完成指明當前添加資產(chǎn)元素的下標，并將下標后移，即numltems+；空(5) 處補充通過使用編譯器生成的缺省構(gòu)造函數(shù)創(chuàng)建對象，即應填入“new”。試題六 1、ext

33、ends BuildingLight2 、 extends BuildingLightimplementsPowerSwitchable 3 、 PowerSwitchable4 、numltems+5、new 解析 本題考查面向?qū)ο蟪绦蛟O計及其 Java 語言實現(xiàn)的能力，涉及類和接口、 抽象類、對象、方法的定義和相關(guān)操作，以及繼承和實現(xiàn)關(guān)系。要求考生根據(jù) 給出的案例、類圖和執(zhí)行過程說明，認真閱讀理清程序思路，然后完成題目。先考查針對案例的特定需求，構(gòu)建類圖整體結(jié)構(gòu)。本題中根據(jù)類圖定義了 類： BuildingManagement 、Asset 、ComputerAsset 、 Buildin

34、gAsset 、 ComputerCPU、ComputerMoniter 、 BuildingLight 、RoomLights、 EmergencyLight 和 PowerSwitchable 。其中 Asset 為抽象類，表示通用資產(chǎn)，作為所有資產(chǎn)類的基類。 ComputerAsset 表示 計算機有關(guān)資產(chǎn)、 BuildingAsset 表示建筑物有關(guān)資產(chǎn)，兩者作為 Asset 的子 類，繼承了 Asset 類， ComputerCPU、ComputerMoniter 分別表示計算機 CPU和 顯示器，繼承了 ComputerAsset。 BuildingLight 是一種建筑物資產(chǎn)，表示建筑 物內(nèi)的照明設備，繼承了 BuildingAsset ，而照明設備有 RoomLights 和EmergencyLight ，作為 BuildingLight 的子類。由于案例中兩大類耗電資產(chǎn) ( Asset): 計算機 (ComputerAsset) 和建筑物 (Building Asset) 中，可在夜間關(guān) 閉的房燈 ( RoomLights) 、計算機顯示器 (ComputerMoniter) 屬于不同的資產(chǎn)類 型，所以將可關(guān)閉的資產(chǎn)單獨進行設計為一種類型 PowerSwitchable ，規(guī)定可 在夜間關(guān)閉電源的物體