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

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

●閱讀以下說明和流程圖，填補流程圖中的空缺(1)～(5)，將解答填入答題紙的對應欄內。

【說明】

本流程圖旨在統計一本電子書中各個關鍵詞出現的次數。假設已經對該書從頭到尾依次分離出各個關鍵詞{A(i)|i=1,…,n)(n>1)}，其中包含了很多重復項，經下面的流程處理后，從中挑選出所有不同的關鍵詞共m個{K(j)|j=1,…,m}，而每個關鍵詞K(j)出現的次數為NK(j),j=1,…,m。

【流程圖】

●閱讀以下說明和C函數，填補代碼中的空缺(1)～(5)，將解答填入答題紙的對應欄內。

【說明】

函數removeDuplicates(char *str)的功能是移除給定字符串中的重復字符，使每種字符僅保留一個，其方法是：對原字符串逐個字符進行掃描，遇到重復出現的字符時，設置標志，并將其后的非重復字符前移。例如，若str指向的字符串為“aaabbbbscbsss”，則函數運行后該字符串為“absc”。

【C代碼】

void removeDuplicates(char *str)

{

int i, len=strlen(str); /* 求字符串長度 */

if( (1) ) return; /* 空串或長度為1的字符串無需處理 */

for( i=0; i

int flag=0; /* 字符是否重復標志 */

int m;

for( m= (2) ; m

if( str[i]==str[m] ) {

(3) ; break;

}

}

if(flag) {

int n, idx=m;

/* 將字符串第idx字符之后、與str[i]不同的字符向前移 */

for( n=idx+1; n

if( str[n]!=str[i] ) {

str[idx]=str[n]; (4) ;

}

str[ (5) ]='\0'; /* 設置字符串結束標志 */

}

}

}

●閱讀以下說明和C函數，填補函數代碼中的空缺(1)～(5)，將解答填入答題紙的對應欄內。

【說明】

隊列是一種常用的數據結構，其特點是先入先出，即元素的插入在表頭、刪除在表尾進行。下面采用順序存儲方式實現隊列，即利用一組地址連續的存儲單元存放隊列元素，同時通過模運算將存儲空間看作一個環狀結構(稱為循環隊列)。

設循環隊列的存儲空間容量為MAXQSIZE，并在其類型定義中設置base、rear和length三個域變量，其中，base為隊列空間的首地址，rear為隊尾元素的指針，length表示隊列的長度。

#define MAXQSIZE 100

typedef struct {

QElemType *base; /* 循環隊列的存儲空間首地址 */

int rear; /* 隊尾元素索引 */

int length; /* 隊列的長度 */

} SqQueue;

例如，容量為8的循環隊列如圖3-1所示，初始時創建的空隊列如圖3-1(a)所示，經過一系列的入隊、出隊操作后，隊列的狀態如圖3-1(b)所示(隊列長度為3)。

下面的C函數1、C函數2和C函數3用于實現隊列的創建、插入和刪除操作，請完善這些代碼。

【C函數1】創建一個空的循環隊列。

int InitQueue(SqQueue *Q)

/* 創建容量為MAXQSIZE的空隊列，若成功則返回1;否則返回0 */

{ Q->base=(QElemType *) malloc ( MAXQSIZE* (1) );

if (!Q->base) return 0;

Q->length=0;

Q->rear=0;

return 1;

} /* InitQueue */

【C函數2】元素插入循環隊列。

int EnQueue(SqQueue}Q, QElemType e) /* 元素e入隊，若成功則返回1;否則返回0 */

{ if(Q->length>=MAXQSIZE) return 0;

Q->rear= (2) ;

Q->base[Q->rear]=e;

(3) ;

return 1;

} /* EnQueue */

【C函數3】元素出循環隊列。

int DeQueue (SqQueuea *Q, QElemType *e)

/* 若隊列不空，則刪除隊頭元素，由參數e帶回其值并返回1;否則返回0 */

{ if ( (4) ) return 0;

*e=Q->base[(Q->rear - Q->length+1+MAXQSIZE) %MAXQSIZE];

(5) ;

return 1;

} /* DeQueue */

●閱讀以下說明和C函數，填補代碼中的空缺(1)～(6)，將解答填入答題紙的對應欄內。

【說明】

二叉樹的寬度定義為含有結點數最多的那一層上的結點數。函數GetWidth__(4)__用于求二叉樹的寬度。其思路是根據樹的高度設置一個數組counter[]，counter[i]存放第i層上的結點數，并按照層次順序來遍歷二叉樹中的結點，在此過程中可獲得每個結點的層次值，最后從counter[]中取出最大的元素就是樹的寬度。

按照層次順序遍歷二叉樹的實現方法是借助一個隊列，按訪問結點的先后順序來記錄結點，離根結點越近的結點越先進入隊列，具體處理過程為：先令根結點及其層次號(為1)進入初始為空的隊列，然后在隊列非空的情況下，取出隊頭所指示的結點及其層次號，然后將該結點的左予樹根結點及層次號入隊列(若左子樹存在)，其次將該結點的右子樹根結點及層次號入隊列(若右子樹存在)，然后再取隊頭，重復該過程直至完成遍歷。

設二叉樹采用二叉鏈表存儲，結點類型定義如下：

typedef struct BTNode {

TElemType data;

struct BTNode *left, *right;

} BTNode, *BiTree;

隊列元素的類型定義如下：

typedef struct {

BTNode *ptr;

int LevelNumber;

} QElemType;

GetWidth__(5)__函數中用到的函數原型如下所述，隊列的類型名為QUEUE：

【C函數】

int GetWidth(BiTree root)

{

QUEUE Q;

QElemType a, b;

int width, height=GetHeight(root);

int i, *counter=(int *) calloc (height+1, sizeof(int));

if ( (1) ) return -1; /* 申請空間失敗 */

if ( !root ) return 0; /* 空樹的寬度為0 */

if ( (2) ) return -1; /* 初始化隊列失敗時返回 */

(4)A.ptr=root;

(5)A.LevelNumber=1;

if (!EnQueue ( &Q, a)) return -1; /* 元素入隊列操作失敗時返回 */

while (!isEmpty (Q)) {

if( (3) )return-1; /* 出隊列操作失敗時返回*/

counter[b.LevelNumber]++; /* 對層號為b.LevelNumber的結點計數 */

if(b.ptr->left){ */ 若左子樹存在，則左子樹根結點及其層次號入隊 */

(6)A.ptr=bptr->left;

(7)A.LevelNumber= (4) ;

if ( !EnQueue (&Q, a)) return -1;

}

if(b.ptr->right){ /* 若右子樹存在，則右子樹根結點及其層次號入隊 */

(8)A.ptr = b.ptr->right;

(9)A.LeveINumber= (5) ;

if ( !EnQueue (&Q, a)) return -1;

}

}

width=counter [1] ;

for (i=1; i< height +1; i++) /* 求counter[]中的最大值 */

if ( (6) ) width=counter[i];

free(counter);

return width;

}

●閱讀下列說明、C++代碼和運行結果，填補代碼中的空缺(1)～(6)，將解答填入答題紙的對應欄內。

【說明】

很多依托撲克牌進行的游戲都要先洗牌。下面的C++程序運行時先生成一副撲克牌，洗牌后再按順序打印每張牌的點數和花色。

【C++代碼】

#include

#include

#include

#include

#include

using namespace std;

const string Rank[13]={"A","2","3","4","5","6","7","8","9","10","J","Q","K"};//撲克牌點數

const string Suits[4]={"SPADES","HEARTS","DIAMONDS","CLUBS"};//撲克牌花色

class Card {

private:

int rank;

int suit;

public:

Card(){}

~Card(){}

Card(int rank, int suit) { (1) rank=rank; (2) suit=suit;}

int getRank() {

return rank;

}

int getSuit() {

return suit;

}

void printCard() {

cout << '(' << Rank[rank] << "," << Suits[suit] << ")";

}

};

class DeckOfCardsts {

private:

Card deck[52];

public:

DeckOfCards() { //初始化牌桌并進行洗牌

for (int i=0; i<52; i++) { //用Card對象填充牌桌

(3) =Card(i%13, i%4);

}

srand((unsigned) time(0)); //設置隨機數種子

std::random_shuffle(&deck[0], &deck[51]);//洗牌

}

~DeckOfCards() {

}

void printCards() {

for ( int i=0; i<52; i++ ){

(4) printCard() ;

if ((i+1)%4==0) cout<

else cout << "\t";

}

}

};

int main(){

DeckOfCards * d = (5) ; //生成一個牌桌

(6) ; //打印一副撲克牌中每張牌的點數和花色

delete d;

return 0;

}

●閱讀以下說明和Java程序，填補代碼中的空缺(1)～(6)，將解答填入答題紙的對應欄內。

【說明】

很多依托撲克牌進行的游戲都要先洗牌。下面的Java代碼運行時先生成一副撲克牌，洗牌后再按順序打印每張牌的點數和花色。

【Java代碼】

import iav

(6)A.util.List;

import jav

(7)A.util.Arrays;

import jav

(8)A.util.Collections;

class Card { //撲克牌類

public static enum Face { Ace, Deuce, Three, Four, Five, Six, Seven, Eight, Nine, Ten, Jacky, Queen, King ); //枚舉牌點

public static enum Suit(Clubs, Diamonds, Hearts, Spades}; //枚舉花色

private final Face face;

private final Suit suit;

public Card( Face face, Suit suit ) {

(1) face=face;

(2) suit=suit;

}

public Face getFace() { return face; }

public Suit getSuit() { return suit; }

public String getCard() { //返回String來表示一張牌

return String.format( "%s, %s", face, suit );

}

}

//牌桌類

class DeckOfCards {

private List< Card > list; //聲明List以存儲牌

public DeckOfCards() { //初始化牌桌并進行洗牌

Card[] deck=new Card[52];

int count=0; //牌數

//用Card對象填充牌桌

for ( Card.Suit suit:Card.Suit.values() ) {

for ( Card Face face:Card.Face.values() ) {

(3) =new Card( face, suit);

}

}

list= Arrays.asList( deck );

Collections.shuffle( list ); //洗牌

}

public void printCards ()

{

//按4列顯示52張牌

for ( int i=0; i

System.out.printf( "%-19s%s", list. (4) ,((i+1)%4==0)?"\n":"" );

}

}

public class Dealer {

public static void main( String[] args ) {

DeckOfCards player= (5) ;

(6) printCards();

}

}