2013年下半年程序員考試下午真題：

>>>點擊進入軟考初級程序員歷年真題下載

● 閱讀以下說明和流程圖，填補流程醫中的空缺（1）～（5）將解答填入答題紙的對應欄內。
【說明】
兩個包含有限個元素的非空集合 A、B 的相似度定義為 |A∩B|/|A∪B|，即它們的交 集大小(元素個數）與并集大小之比。
以下的流程圖計算兩個非空整數集合(以數組表示）的交集和井集，并計算其相似度。己知整數組 A[1:m]和 B[l:n]分別存儲了集合 A 和 B 的元素(每個集合中包含的元素各不相同)，其交集存放于數組C[1:s]，并集存放于數組D[1:t] ，集合A 和 B 的相似度存放于 SIM。
例如，假設 A={ 1， 2 ，3，4} ，B={ 1， 4 ，5，的，則C={1， 4} ，D={1， 2 ，3 ，4 ，5， 6}，A 與 B 的相似度 SIM=1/3。
【流程圖】

● 閱讀以下說明和 C 函數，填充函數中的主缺，將解答填入答題紙的對應欄內。
【說明】
下面的函數 sort(int n，int a[])對保存在數在 a 中的整數序列進行非遞減排序。由于該 序列中的元素在一定范圍內重復取值，因此排序方法是先計算出每個元素出現的次數并記錄在數組 b 中，再從小到大順序地排列各元素即可得到一個非遞減有序序列。例如， 對于序列 6，5，6，9，6，4，8，6，5. 其元素在整數區間 [4，9]內取值，因此使數組元素 b[0] ～b[5]的下標。0～5分別對應數值 4～9. 順序地掃描序列的每一個元素并累計其出現的次數，即將 4的個數記入b[0]， 5 的個數記b[1]，依此類推，9的個數記入 b[5]最后依次判斷數組b的每個元素值，并將相應個數的數值順序地寫入結果序列即可。

對于上例，所得數組 b 的各個元素值如下:

那么在輸出序列中寫入 1 個 4、2個 5、4個 6、l 個 8、1 個 9，即得4，5，5，6，6，6，6，8，9，
從而完成排序處理。
【C 函數】
void sort(int n ，int a[ ])
{ int *b;
int i ,k ,number;
int minimum = a[0] , maximum = a[0];
/* minimum 和 maximum 分別表示數組a的最小、最大元素值*/
for(i=1;i<n;i++){
If( （1） ) minimum=a[j];
Else
If( （2） ) maximum=a[i];
}
number = maximum - minimum + 1;
if (number<=1) return;
b = (int *)calloc (number ，sizeof(int)) ;

if (!b) return;

for(i=0;i<n;i++){ /* 計算數組a元素值出現的次數并計入數組b */

K=a[i]-minimum; ++b[k];
}
/*按次序在數組 a 中寫入排好的序列*/
i=（3） ;
for( k=0; k<number; k++ )
for(; （4） ; --b[k] )
a [i++] = minimum +（5）;}

● 閱讀以下說明和 C 代碼，填充代碼中的空缺，將解答填入答題紙的對應欄內。
【說明 1】
下面的函數 countChar(char *text)統計字行串 text 中不同的英文字母數和每個英文字母出現的次數(英文字母不區分大小寫)。
【c代碼1】

int countChar( char *text )

{

int i，sum = 0; /* sum 保存不同的英文字母數*/

char *ptr;

int c[26] = {0}; /*數組c保存每個英文字母出現的次數*/

/*c[0]記錄字母A或a的次數，c[1] 記錄字母B或b的次數，依此類推*/

ptr = (1) ;/*ptr初始時指向字符串的首字符*/

while (*ptr) {

if ( isupper(*ptr) )

c[*ptr - 'A']++;

e1se

if ( islower(*ptr) )

c[*ptr - 'a'] ++;

(2) ; /*指向下一個字符*/

}

for(i=0;i＜26;i++)

if (3) sum++;

return sum;

}

【說明2】

將下面C代碼2中的空缺補全后運行，使其產生以下輸出。

f2:f2:f2:2

f3:f3: 1

【C代碼2】

*include <stdio.h>

int f1 (int (*f) (int)) ;

int f2 (int) ;

int f3 (int) ;

int main __(3)__

{

printf("％d\n" ，f1( (4) ));

printf("％d\n" ，f1( (5) ));

return 0;

}

int f1 ( int (*f) (int) )

{

int n = 0;

/*通過函數指針實現函數調用，以返回值作為循環條件*/

while ( (6) ) n++;

return n;

}

int f2(int n)

{

printf("f2: ");

return n*n-4;

}

int f3 (int n)

{

printf("f3: ");

return n-l;

}

● 閱讀以下說明和C程序，填充程序中的空缺，將解答填入答題紙的對應欄內。
【說明】
正整數n若是其平方數的尾部，則稱n為同構數。例如，6是其平方數36的尾部，76是其平方數5776的尾部，6與76都是同構數。下面的程序求解不超過10000的所有同構數。
己知一位的同構數有三個: 1，5，6，到此二位同構數的個位數字只可能是1，5，6這三個數字。依此類推，更高位數同構數的個位數字也只可能是1，5，6 這三個數字。
下面程序的處理思路是:對不超過10000的每一個整數a，判斷其個位數字，若為1、5或6，則將a 轉換為字符串as，然后對a進行平方運算，并截取其尾部與as長度相等的若干字符形成字符串后與出比較，根據古們相等與否來斷定a是否為同構數。

【C 程序】

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

int myitoa(int ，char *); /*將整數轉換為字符串*/

/* right取得指定字符串尾部長度為lergth的子串，返回所得子串的首字符指針*/

char *right(char*， int length);

int main __(4)__

{

int a ，t; int len;

char as[10] ，rs[20];

printf("[1 ，l0000]內的同構數: \r");

for(a=1;a<=10000;a++) {

t = (1) ; /*取整數a的個位數字*/

if (t!=1&& t!=5 && t!=6) continue;

len = myitoa(a ，as); /*數a轉換為字符串，存入as */

myitoa(a*a， rs); /*數a的平方轉換為字符串，存入rs */

/*比較字符串as與rs末尾長度為len的子串是否相等*/

if ( strcmp (as ， (2) )==0 ) /*若相同則是同構數并輸出*/

printf("%s的平方為%s\n" ，as，rs);

}

return 0;

}

int myitoa(int num ，char *s) /*將整數num轉換為字符串存入s */

{

int i ，n = 0;

char ch;

/*從個位數開始，取num的每一位數字轉換溝字符后放入s[] */

while (num) {

s[n++] = （3） + '0' ;

num = num/10;

}

s[n]='\0';

for(i=0; i<n/2; i++) { /*將s中的字符串逆置*/

(4) ; s[i] = s[n-i-1]; 5 [n-i-1] = ch;

}

return n; /*返回輸入參數num的位數*/

}

char *right(char *.ms ，int length)

/*取字符串ms尾部長度為length的子串，返回所得子串的首字符指針*/

{

int i;

for( ; *ms; ms++); /*使ms到達原字符串的尾部事*/

for( i=0; i<length; (5) );/*使ms指向所得子串的首部字符*/

return ms;

}

● 閱讀以下說明和C++代碼，填充程序中的空缺，將解答填入答題紙的對應欄內。
【說明】
某應急交通控制系統(TraficControlSystem)在紅燈時控制各類車輛 (Vehicle)的通行，其類圖如圖5-1所示，在緊急狀態下應急車輛在紅燈時可通行，其余車輛按正常規則通行。
下面的C++代碼實現以上設計，請完善其中的空缺。

【C++代碼】

#include <typeinfo>

#include <iostream>

using namespace std;

class Vehicle { /*抽象基類，車輛*/ public:virtual void run( ) = 0;}；class Emergency { /*抽象基類，可在紅燈時通行的接口，函數均為純虛函數*/public:(1) = 0; // isEmergent ( )函數接口 (2) = 0; // runRedLight( ) 函數接口}；class Car: public Vehicle {public:～Car ( ) { }void run ( ) { /*代碼略*/}}；class Truck: public Vehicle {public:～Truck( ) { }void run ( ) { /*代碼略*/ }}；class PoliceCar: (3) {private:bool isEmergency;public:PoliceCar( ) : Car( ) ，Emergency( ){ this->isEmergency = false;} PoliceCar(bool b) : Car( ) ，Emergency( ) { this->isEmergency = b;}～policeCar ( ) { }bool isEmergent ( ) { return （4） ; }void runRedLight( ) { /*代碼略*/ }}；/*類Ambulance、 FireEngine 實現代碼略*/class TraficControlSystern { /*交通控制類*/private:Vehicle* v[24}; int nurnVeh:cles; /*在構造函數中設置初始值為0*/public:void control__(5)__ { //控制在緊急情況下應急車輛紅燈通行，其他情況按常規通行for (int i = 0; i < numVehicles ; i++) {Emergency * ev = dynamic_cast<Emergency*>(v[i]);if (ev != 0)(5) ->runRedLight __(6)__ ;else(6) ->run __(7)__ ;} }void add(Vehicle * vehicle) { v[numVehicles++] = vehicle;/ *添加車輛./void shutDown__(8)__ { for (int i = 0; i < numVehicles; i++) { deletev[i]; } }} ;int main( ) {TraficControlSystern. tcs = new TraficControlSystern;tcs->add(new Car( )); tcs->add(new PoliceCar( ));tcs->add(new Ambulance( ));tcs->add(new Ambulance(true));tcs->add(new FireEngine(true)); tcs->add(new FireEngine( )); tcs->add(new Truck( ));tcs->control( ); tcs->shutDown( );delete tcs; }

● 閱讀以下說明和Java代碼，填充程序中的空缺，將解答填入答題紙的對應欄內。
【說明】
某應急交通控制系統(TraficControlSystem)在紅燈時控制各類車輛 (Vehicle)的通行，其類圖如圖6-1所示，在緊急狀態下應急車輛在紅燈時可通行，其余車輛按正常規則通行。

下面的Java代碼實現以上設計，請完善其中的空缺。
【Java 代碼 】
abstract class Vehicle {
public Vehicle( ) { )
abstract void run( );
}；
interface Emergency {
(1) ;
(2) ;
}；
class Car extends Vehicle {
public Car( ) { )
void run ( ) { /*代碼略*/
}；
class Truck extends Vehicle {
public Truck( ) { )
void run ( ) { /*代碼略*/
}；

class PoliceCar (3) {
boolean isEmergency = false;
public PoliceCar__(6)__ { )
public PoliceCar(boolean b) { this.isEmergency=b; }
public boolean isEmergent( ) { return ( 4 ) ; }
public void runRedLight( ) { /*代碼略*/ }
};
/*類h由ulance 、 FireEngine 實現代碼略叫*/
public class TraficControlSystem { /*交通控制類*/
private Vehicle[ ] v = new Vehicle[24];
int numVehicles;
public void control( ) {
for (int i = 0; i < numVehicles; i++) {
if (v[i] instanceof EmErgency && ((Emergency)v[i]).
isEmergent__(7)__) {
( 5 ) .runRedLigh ( );
} else
( 6 ) .run ( ) ;
}
}
void add(Vehicle vehicle) { v[numVehicles++] = vehiclei} /*添加車輛*/
void shutDown__(8)__ { /*代碼略* /}
public static void main (Str :.ng [ ] args) {
TraficControlSystem tcs = new TraficControlSystem__(9)__;
tcs.add(new Car__(10)__};
tcs.add(new PoliceCar__(11)__;
tcs.add(new Ambulance__(12)__;
tcs.add(new Ambulance(t:ue));
tcs.add(new FireEngine( :rue));
tcs.add(new Truck__(13)__);
tcs.add(new FireEngine( );
tcs.control__(14)__;
tcs.shutDown__(15)__;
}
}