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

>>>點(diǎn)擊進(jìn)入軟考初級(jí)程序員歷年真題下載

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

【問題】

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

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

● 閱讀以下說明和C代碼，填補(bǔ)代碼中的空缺，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。
【說明1】
遞歸函數(shù)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】
函數(shù)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的前l(fā)enA個(gè)字符復(fù)制后存入setC
lenC= (3) ;
for(i=0;i＜lenB；i++)
if( (4) ) //調(diào)用is_elem判斷字符是否在setA中
setC[lenC++]=setB[i];
(5) =‘/0’; //設(shè)置合并后字符集的結(jié)尾標(biāo)識(shí)
return setC;
}

●閱讀以下說明和C代碼，填補(bǔ)代碼中的空缺，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。
【說明】
某文本文件中保存了若干個(gè)日期數(shù)據(jù)，格式如下（年／月／日）：
2005/12/1
2013/2/29
1997/10/11
1980/5/15
....
但是其中有些日期是非法的，例如2013/2/29是非法日期，閏年（即能被400整除或者能被4整除而不能被100整除的年份）的2月份有29天，2013年不是閏年?，F(xiàn)要求將其中自1985/1/1開始、至2010/12/31結(jié)束的合法日期挑選出來并輸出。
下面的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) ) /*調(diào)用Lteq判斷是否在起至日期之間*/
printf(“%d%d%d\n”,date.year,date.month,date.day);
}
fclose(fp); Return 0;
}

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

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

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

●閱讀以下說明和Java代碼，填補(bǔ)代碼中的空缺，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。
【說明】
以下Java代碼實(shí)現(xiàn)兩類交通工具（Flight和Train）的簡單訂票處理， 類Vehicle、Flight、Train之間的關(guān)系如圖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的票數(shù)

Int getTicket(){

Return tickets；

}

void decreaseTicket(int n){

tickets=tickets -n；

}

}

class Train （3） {

Private （4） tickets=2016; //Train的票數(shù)

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（“剩余票數(shù)：” +v.get(i).getTicket())；

}

}

}

運(yùn)行該程序時(shí)輸出如下：

歡迎訂票！

剩余票數(shù)：215

剩余票數(shù)：2014

剩余票數(shù)： （6）

剩余票數(shù)： （7）

剩余票數(shù)： （8）

●閱讀下列說明和C++代碼，填補(bǔ)代碼中的空缺，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。
【說明】
以下C++代碼實(shí)現(xiàn)兩類交通工具（Flight和Train）的簡單訂票處理，類Vehicle、Flight、Train之間的關(guān)系如圖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的票數(shù)

public:

int getTicket();

void decreaseTicket(int);

};

class Train: （3） {

private:

（4） tickets; //Train的票數(shù)

public:

int getTicket();

void decreaseTicket(int);

};

int Train::tickets =2016; //初始化Train的票數(shù)為2016

int Flight::tickets =216; //初始化Flight的票數(shù)為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《“剩余票數(shù)：”<<（*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;

}

運(yùn)行該程序時(shí)輸出如下：

歡迎訂票！

剩余票數(shù)：215

剩余票數(shù)：2014

剩余票數(shù)： （6）

剩余票數(shù)： （7）

剩余票數(shù)： （8）