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

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

● 閱讀以下說明和流程圖，填補流程圖和問題中的空缺(1)～(5)，將解答填入答題紙的對應欄內。
【說明】
設整型數組A[1：N]每個元素的值都是1到N之間的正整數。一般來說，其中會有一些元素的值是重復的，也有些數未出現在數組中。下面流程圖的功能是查缺查重，即找出A[1：N]中所有缺的或重復的整數，并計算其出現的次數（出現次數為0時表示缺）。流程圖中采用的算法思想是將數組A的下標與值看作是整數集[1：N]加上的一個映射，并用數組C[1：N]記錄各整數出現的次數，需輸出所有缺少的或重復的數及其出現的次數。
【流程圖】

【問題】

如果數組A[1：5]的元素分別為{3，2，5，5，1}，則算法流程結束后輸出結果為： (5) 。

輸出格式為：缺少或重復的元素，次數（0表示缺少）

● 閱讀以下說明和C代碼，填補代碼中的空缺，將解答填入答題紙的對應欄內。
【說明1】
遞歸函數is_elem(char ch, char *set)的功能是判斷ch中的字符是否在set表示的字符集合中，若是，則返回1，否則返回0。
【C代碼1】
int is_elem (char ch ,char*set)
{
If(*set==‘\0’)
return 0;
else
If( (1) )
return 1;
else
return is_elem( (2) )
}【說明2】
函數char*combine(char* setA,char *setB)的功能是將字符集合A（元素互異，由setA表示）和字符集合B（元素互異，由setB表示）合并，并返回合并后的字符集合。
【C代碼2】
char*combine(char *setA, char*setB)
{
int i，lenA, lenB, lenC；
lenA=strlen(setA)；
lenB=strlen(setB)；
char*setC=(char*)malloc(lenA+lenB+1);
if(!setC)
return NULL;
strncpy(setC,setA,lenA)； //將setA的前lenA個字符復制后存入setC
lenC= (3) ;
for(i=0;i＜lenB；i++)
if( (4) ) //調用is_elem判斷字符是否在setA中
setC[lenC++]=setB[i];
(5) =‘/0’; //設置合并后字符集的結尾標識
return setC;
}

●閱讀以下說明和C代碼，填補代碼中的空缺，將解答填入答題紙的對應欄內。
【說明】
某文本文件中保存了若干個日期數據，格式如下（年／月／日）：
2005/12/1
2013/2/29
1997/10/11
1980/5/15
....
但是其中有些日期是非法的，例如2013/2/29是非法日期，閏年（即能被400整除或者能被4整除而不能被100整除的年份）的2月份有29天，2013年不是閏年。現要求將其中自1985/1/1開始、至2010/12/31結束的合法日期挑選出來并輸出。
下面的C代碼用于完成上述要求。【C代碼】
#include <stdio.h>
typedef struct{
int year, month, day；/* 年，月，日*/
}DATE；int isLeap Year(int y) /*判斷y表示的年份是否為閏年，是則返回1，否則返回0*/
{
return((y%4==0 && y%100!=0)Il(y%400==0))；
}int isLegal(DATE date) /*判斷date表示的日期是否合法，是則返回1，否則返回0*/
{
int y=date.year,m= date.month,d=date.day;if (y<1985 II y>2010 II m<1 II m>12 II d<l II d>31) return 0;
if((m==4 ll m==6 ll m==9 II m==11)&& (1) ) return 0;
If(m==2){
if(isLeap Year(y)&& (2) ) return 1； 。
else
if (d>28) return 0；
}
return 1;
}Int Lteq(DATE d1，DATE d2)
/*比較日期d1和d2，若d1在d2之前或相同則返回1，否則返回0*/
{
Long t1,t2;
t1=d1.year*10000+d1.month*100+d1.day;
t2=d2.year*10000+d2.month*100+d2.day;
if( (3) ) return 1;
else return 0;
}int main__(3)__
{
DATE date,start={1985,1,1},end={2010,12,30};
FILE*fp; fp=fopen(“d.txt”,”r”);
If( (4) )
return-1; while(!feof(fp)){
if(fscanf(fp,”%d%d%d”,&date.year,&date.month,&date.day)!=3)
break;
if( (5) ) /*判斷是否為非法日期 */
continue；
if( (6) ) /*調用Lteq判斷是否在起至日期之間*/
printf(“%d%d%d\n”,date.year,date.month,date.day);
}
fclose(fp); Return 0;
}

● 閱讀以下說明和C代碼，填補代碼中的空缺，將解答填入答題紙的對應欄內。
【說明】
二叉查找樹又稱為二叉排序樹，它或者是一棵空樹，或者是具有如下性質的二叉樹。
（1）若它的左子樹非空，則左子樹上所有結點的值均小于根結點的值。
（2）若它的右子樹非空，則右子樹上所有結點的值均大于根結點的值。
（3）左、右子樹本身就是兩棵二叉查找樹。
二叉查找樹是通過依次輸入數據元素并把它們插入到二叉樹的適當位置上構造起來的，具體的過程是：每讀入一個元素，建立一個新結點，若二叉查找樹非空，則將新結點的值與根結點的值相比較，如果小于根結點的值，則插入到左子樹中，否則插入到右子樹中；若二叉查找樹為空，則新結點作為二叉查找樹的根結點。
根據關鍵碼序列{46，25，54，13，29，91}構造一個二叉查找樹的過程如圖4-1所示。

設二叉查找樹采用二叉鏈表存儲，結點類型定義如下：
typedef int KeyType；
typedef struct BSTNode{
KeyType key；
struct BSTNode *left,*right；
}BSTNode,*BSTree；圖4-1(g)所示二叉查找樹的二叉鏈表表示如圖4-2所示。

函數int InsertBST(BSTree *rootptr,KeyType kword)功能是將關鍵碼kword插入到由rootptr指示出根結點的二叉查找樹中，若插入成功，函數返回1，否則返回0。【C代碼】
int lnsertBST(BSTree*rootptr，KeyType kword)
/*在二叉查找樹中插入一個鍵值為kword的結點，若插入成功返回1，否則返回0；
*rootptr為二叉查找樹根結點的指針
*/
{
BSTree p,father; (1) ; /*將father初始化為空指針*/
p=*rootptr; /*p指示二叉查找樹的根節點*/
while(p&& （2） ){ /*在二叉查找樹中查找鍵值kword的結點*/
father=p;
if(kword＜p-＞key)
p=p-＞left；
else
p=p-＞right；
}
if( (3) )return 0; /*二叉查找樹中已包含鍵值kword，插入失敗*/p=(BSTree)malloc( (4) ); /*創建新結點用來保存鍵值kword*/
If(!p)return 0; /*創建新結點失敗*/
p-＞key=kword；
p-＞left=NULL；
p-＞right=NULL；If(!father)
(5) =p； /*二叉查找樹為空樹時新結點作為樹根插入*/
else
if(kword＜father-＞key)
(6) ； /*作為左孩子結點插入*/
else
(7) ； /*作右孩子結點插入*/ return 1；}/*InsertBST*/

●閱讀以下說明和Java代碼，填補代碼中的空缺，將解答填入答題紙的對應欄內。
【說明】
以下Java代碼實現兩類交通工具（Flight和Train）的簡單訂票處理， 類Vehicle、Flight、Train之間的關系如圖5-1所示。

圖5-1【Java代碼】

import jav

（5）A．util.ArrayList;

import jav

（6）A．util.List;

abstract class Vehicle {

void book(int n) { //訂 n張票

if (getTicket0()>=n) {

decrease Ticket(n);

} else {

System.out.println(“余票不足！！“)；

}

}

abstract int getTicket();

abstract void decreaseTicket(int n);

};

class Flight （1） {

Private （2） tickets=216； //Flight的票數

Int getTicket(){

Return tickets；

}

void decreaseTicket(int n){

tickets=tickets -n；

}

}

class Train （3） {

Private （4） tickets=2016; //Train的票數

int getTicket() {

return tickets;

}

void decreaseticket(int n) {

tickets = tickets - n;

}

}

public class Test

{

public static void main(String[] args) {

System.out.println（“歡迎訂票 ! ")；

ArrayList<Vehicle> v = new ArrayList<Vehicle>();

v.add(new Flight());

v.add(new Train());

v.add(new Flight());

v.add(new Train());

v.add(new Train());

for (int i=0;i<v.size(); i++){

（5） （i+1）; //訂i+1張票

System.out.println（“剩余票數：” +v.get(i).getTicket())；

}

}

}

運行該程序時輸出如下：

歡迎訂票！

剩余票數：215

剩余票數：2014

剩余票數： （6）

剩余票數： （7）

剩余票數： （8）

●閱讀下列說明和C++代碼，填補代碼中的空缺，將解答填入答題紙的對應欄內。
【說明】
以下C++代碼實現兩類交通工具（Flight和Train）的簡單訂票處理，類Vehicle、Flight、Train之間的關系如圖6-1所示。

圖6-1【C++代碼】

#include <iostream>

#include <vector>

using namespace std;

class Vehicle{

public:

virtual ~Vehicle(){}

void book(int n){ //訂n張票

if (getTicket()>=n){

decreaseTicket(n);

} else{

cout<<n<<“余票不足！！ ”；

}

}

virtual int getTicket()=0;

virtual void decreaseTicket(int)=0；

}；

Class Flight: （1） {

private:

（2） tickets; //Flight的票數

public:

int getTicket();

void decreaseTicket(int);

};

class Train: （3） {

private:

（4） tickets; //Train的票數

public:

int getTicket();

void decreaseTicket(int);

};

int Train::tickets =2016; //初始化Train的票數為2016

int Flight::tickets =216; //初始化Flight的票數為216

int Train：：getTicket() { return tickets； }

void Train：：decreaseTicket(int n){ tickets=tickets -n;}

int Flight::getTicket () { return tickets; }

void Flight::decreaseTicket(int n) { tickets= tickets - n;}

int main() {

vector<Vehicle*> v;

v.push_back(new Flight());

v.push_back(new Train());

v;push _back(new Flight());

v.push_back(new Tram());

v.push_back(new Train());

cout《"歡迎訂票！”《endl：

for (int i= 0; i < v.size(); i++) {

（5） (i+1)； //訂i+l張票

cout《“剩余票數：”<<（*V[i]）. getTicket()<<endl;

}

for (vector<Vehicle*>：：iterator it = v.begin(); it != v.end(); it ++) {

if (NULL !=*it) {

delete*it ;

*it = NULL;

}

}

v.clear();

Return0;

}

運行該程序時輸出如下：

歡迎訂票！

剩余票數：215

剩余票數：2014

剩余票數： （6）

剩余票數： （7）

剩余票數： （8）