201411程序员下午真题

第 1 题

    阅读以下说明和流程图，填补流程图中的空缺（1）～（5），将解答填入答题纸的对应栏内。
【说明】
    本流程图旨在统计一本电子书中各个关键词出现的次数。假设已经对该书从头到尾依次分离出各个关键词{A(i)|i=1,…,n)(n>1)}，其中包含了很多重复项，经下面的流程处理后，从中挑选出所有不同的关键词共m个{K(j)|j=1,…,m}，而每个关键词K(j)出现的次数为NK(j),j=1,…,m。

【流程图】

答案与解析

  • 试题难度：较难
  • 知识点：流程图>流程图
  • 试题答案：
    （1）1    
    （2）K(j)
    （3）NK(j)+1→NK(j)    或NK(j)++    或等价表示
    （4）m+1→m或m++    或等价表示
    （5）A(i)
  • 试题解析：
        流程图中的第1框显然是初始化。A(1)→K(1)意味着将本书的第1个关键词作为选出的第1个关键词。1→NK(1)意味着此时该关键词的个数置为1。m是动态选出的关键词数目，此时应该为1，因此（1）处应填1。
        本题的算法是对每个关键词与己选出的关键词进行逐个比较。凡是遇到相同的，相应的计数就增加1；如果始终没有遇到相同关键词的，则作为新选出的关键词。
        流程图第2框开始对i=2,n循环，就是对书中其他关键词逐个进行处理。流程图第3框开始j=1,m循环，就是按已选出的关键词依次进行处理。
        接着就是将关键词A(i)与选出的关键词K(j)进行比较。因此（2）处应填K(j)。
        如果A(i)=K(j)，则需要对计数器NK(j)增1，即执行NK(j)+1→NK(j)。因此（3）处应填NK(j)+1→NK(j)。执行后，需要跳出j循环，继续进行i循环，即根据书中的下一个关键词进行处理。
        如果A(i)不等于K(j)，则需要继续与下个K(j)进行比较，即继续执行j循环。如果直到j循环结束仍没有找到匹配的关键词，则要将该A(i)作为新的已选出的关键词。因此，应执行A(i)→K(m+1)以及m+1→m。更优的做法是先将计数器m增1，再执行A(i)→K(m)。因此（4）处应填m+1→m，（5）处应填A(i)。

第 2 题

    阅读以下说明和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<len; i++ )  {
            int flag=0;    /* 字符是否重复标志 */
int m;
           for( m= （2） ; m<len; m++ )  {
                  if( str[i]==str[m] )  {
                   （3） ; break;
                  }
          }
        if(flag)    {
            int n, idx=m;
/* 将字符串第idx字符之后、与str[i]不同的字符向前移 */
            for( n=idx+1;  n<len;  n++  )
                if( str[n]!=str[i] )  {
                    str[idx]=str[n];       （4） ;
                }
            str[  （5）  ]='\0';       /* 设置字符串结束标志 */
        }
    }
}

答案与解析

  • 试题难度：较难
  • 知识点：C程序设计>C程序设计
  • 试题答案：
    （1）len<2   或len<=1    或等价表示
    （2）i+1     或等价表示
    （3）flag=1  或给flag赋值为任何一个不是0的值
    （4）idx++   或idx=idx+1    或等价表示
    （s）idx     或等价表示
  • 试题解析：
        本题考查C语言基本应用。
        题目要求在阅读理解代码说明的前提下完善代码。字符串的运算处理是C程序中常见的基本应用。
        根据注释，空（1）处应填入的内容很明确，为“len<=1”或其等价表示。
        要消除字符串中的重复字符，需要扫描字符串，这通过下面的代码来实现：
        for( i=0; i<len; i++ )  {
                      int flag=0;    /* 字符是否重复标志 */
        int m;
                      for( m= （2）   ; m<len; m++ )  {
                            if( str[i]==str[m] )  {
                            （3） ; break;
                            }
            }
         …
        上面代码中，循环变量i用于顺序地记下字符串中每个不同字符首次出现的位置，那么后面的处理就是从i的下一个位置开始，考查后面的字符中有没有与它相同的（str[i]==str[m]），因此空（2）应填入“i+1”或其等价表示。显然，当发现了重复字符时，应设置标志，空（3）处应填入“flag=1”或者给flag赋值为任何一个不是0的值。
        根据说明，发现与str[i]相同的第一个字符str[m]后，需要将其后所有与str[i]不同的字符前移，以覆盖重复字符str[m]，对应的代码如下：
        if(flag)    {
                       int n, idx=m;
        /* 将字符串第idx字符之后、与str[i]不同的字符向前移 */
                       for( n=idx+1;  n<len;  n++  )
                             if( str[n]!=str[i] )  {
                                 str[idx]=str[n];      （4） ;
                             }
                       str[  （5）  ]='\0';       /* 设置字符串结束标志 */
                    }
        初始时，idx等于m，使str[n]覆盖str[idx]后，需要将idx自增，以便将后面与str[i]不同的字符继续前移，因此空（4）处应填入“idx++”或等价表示。由于后面字符前移了，所以字符串结束标志也需重新设置，空（5）处应填入“idx”。

第 3 题

    阅读以下说明和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）。
 
图3-1
下面的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 (SqQueue *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程序设计>C程序设计
  • 试题答案：
    （1）sizeof(QElemType)
    （2）(Q->rear+1)% MAXQSIZE  或等价表示
    （3）Q->length++    或Q->length=Q->length+1  或等价表示
    （4）Q->length<=0   或Q->length==0  或等价表示
    （5）Q->length--    或Q->length=Q->length-1  或等价表示
  • 试题解析：
        本题考查数据结构实现和C语言基本应用。
        队列是一种基本的数据结构，其基本操作有初始化、判断是否为空、入队列和出队列等。
        循环队列是一种采用顺序存储结构实现的队列，其特点是将队列存储空间的首尾单元在逻辑上连接起来，从而得到一个环形结构的队列空间。
        在循环队列的类型定义SqQueue中，指针成员base存放队列空间的首地址，存储空间应在队列的初始化操作中实现，对应的语句如下：
        Q->base=(QElemType *) malloc ( MAXQSIZE* （1） );
        由于InitQueue(SqQueue *Q)的形参为指向结构体的指针，因此队列的参数可表示为“Q->base、Q->rear、Q->length”或“(*Q).base、(*Q).rear、(*Q).length”，由于队列元素类型为QElemType、队列容量为MAXQSIZE，因此空（1）处应填入“sizeof(QElemType)”。
        入队列操作由EnQueue(SqQueue *Q, QElemType e)实现。由于循环队列空间的容量为MAXQSIZE（也就是队满条件为“Q->length>=MAXQSIZE”），因此元素入队列时，需先判断是否队满，在队列中有空闲单元的情况下才能进行入队列操作。其次需确定新元素在队列空间中的位置，从图3-1（b）中可以看出，Q->rear指出了当前队尾元素，新元素应放入下一个位置，结合队列环形空间的要求，空（2）处应填入“(Q->rear+1)%MAXQSIZE”或其等价形式。通过“Q->base[Q->rear]=e”将元素加入队列后，队列长度增加了，因此空（3）处应填入“Q->length++”或其等价形式。
        出队列操作由DeQueue(SqQueue *Q, QElemType *e)实现。元素出队列时，需要判断队列是否为空，显然，队列长度为0就直接表示了队空，因此空（4）处应填入“Q->length==0”或其等价形式，空（5）处应填入“Q->length--”或其等价形式。

第 4 题

    阅读以下说明和C函数，填补代码中的空缺（1）～（6），将解答填入答题纸的对应栏内。
【说明】
    二叉树的宽度定义为含有结点数最多的那一层上的结点数。函数GetWidth()用于求二叉树的宽度。其思路是根据树的高度设置一个数组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()函数中用到的函数原型如下所述，队列的类型名为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;        /* 初始化队列失败时返回 */
        a.ptr=root;    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）{ */ 若左子树存在，则左子树根结点及其层次号入队 */
                a.ptr=b.ptr->left;
                a.LevelNumber= （4） ;
                if  (  !EnQueue (&Q,  a))  return  -1;
            }
            if（b.ptr->right）{ /* 若右子树存在，则右子树根结点及其层次号入队 */
                a.ptr = b.ptr->right;
                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程序设计>C程序设计
  • 试题答案：
    （1）!counter  或0==counter  或NULL==counter  或等价表示
    （2）!InitQueue(&Q)  或0==InitQueue(&Q)   或等价表示
    （3）!DeQueue(&Q,&b) 或0==DeQueue(＆Q,&b)  或等价表示
    （4）b.LeveINumber+1    或等价表示
    （5）b.LeveINumber+1    或等价表示
    （6）counter[i]>width   或等价表示
  • 试题解析：
        本题考查数据结构实现和C语言基本应用。
        考生需要认真阅读题目中的说明，以确定代码部分的处理逻辑，从而完成代码。
        根据注释，空（1）处应填入“!counter”或其等价形式。
        由于初始化队列的函数原型为“InitQueue(QUEUE *Q)”且返回值为0表示操作失败，因此调用该函数时实参应取地址，即空（2）处应填入“!InitQueue(&Q)”或其等价形式。
        空（3）处需进行出队列操作，同时通过参数得到队头元素，根据说明，该空应填入“!DeQueue(&Q,&b)”或其等价形式。
        出队操作后，得到的队头元素用b表示，根据队列元素的类型定义，其对应结点在二叉树中的层次号表示为b.LevelNumber，显然，其孩子结点的层次号应加1，因此空（4）和（5）处应填入“b.LevelNumber+1”。
        从代码中可知变量width的作用是表示最大的层次编号，并通过顺序地扫描数组counter中的每一个元素来确定width的值，显然，空（6）处应填入“counter[i]>width”或其等价形式。

第 5 题

    阅读下列说明、C++代码和运行结果，填补代码中的空缺（1）～（6），将解答填入答题纸的对应栏内。
【说明】
    很多依托扑克牌进行的游戏都要先洗牌。下面的C++程序运行时先生成一副扑克牌，洗牌后再按顺序打印每张牌的点数和花色。
【C++代码】
#include <iostream>
#include <stdlib.h>
#include <ctime>
#include <algorithm>
#include <string>

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 DeckOfCards {
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<<endl;
                else cout << "\t";
        }
    }
};

int main(){
    DeckOfCards  * d = （5） ;        //生成一个牌桌
     （6） ;                                      //打印一副扑克牌中每张牌的点数和花色
delete d;
return 0;
}

答案与解析

  • 试题难度：较难
  • 知识点：C++程序设计>C++程序设计
  • 试题答案：
    （1）this->
    （2）this->
    （3）deck[i]     或*(deck+i)     或等价表示
    （4）deck[i].    或*(deck+i).    或等价表示
    （5）new DeckOfCards()
    （6）d->printCards()   或等价表示
  • 试题解析：
        本题考查C++语言程序设计能力，涉及类、对象、函数的定义和相关操作。要求考生根据给出的案例和代码说明，认真阅读，理清程序思路，然后完成题目。
        本题目中涉及到扑克牌、牌桌等类以及洗牌和按点数排序等操作。根据说明进行设计。
        定义了两个数组，Rank表示扑克牌点数，Suits表示扑克牌花色，定义时进行初始化，而且值不再变化，故用const修饰。
        Card类有两个属性，rank和suit，在使用构造函数Card(int rank, int suit)新建一个Card的对象时，所传入的参数指定删咄和suit这两个属性值。因为参数名称和属性名称相同，所以用this->前缀区分出当前对象。在类Card中包含方法getRank()和getSuit()，分别返回当前对象的rank和suit属性值。printCard()函数打印扑克牌点数和花色。
        DeckOfCards类包含Card类型元素的数组deck[52]，表示牌桌上一副牌（52张）。构造函数中对牌桌进行初始化并进行冼牌。先用Card对象填充牌桌，即创建52个Card对象并加入deck数组。然后洗牌，即将数组中的Card对象根据花色和点数随机排列。printCards()函数将所有Card对象打印出来。
        主控逻辑代码在main函数中实现。在main()函数中，先初始化DeckOfCards类的对象指针d，即生成一个牌桌：
        DeckOfCards  *  d=new DeckOfCards();
        并发牌，即调用d的printCards()函数，实现打印一副扑克牌中每张牌的点数和花色。
        在printCards()函数体内部，为每个数组元素调用当前对象的printCard()一张牌。
        main()函数中使用完数组对象之后，需要用delete操作进行释放对象，对d对象进行删除，即delete d。
        因此，空（1）和（2）需要表示当前对象的this->；空（3）需要牌桌上纸牌对象，即数组元素deck[i]；空（4）也需要纸牌对象调用printCard()，即数组元素deck[i].；空（5）处为创建DeckOfCards类的对象指针d的new DeckOfCards()；空（6）需要用对象指针d调用打印所有纸牌的printCards()函数，即d->printCards()。

第 6 题

    阅读以下说明和Java程序，填补代码中的空缺（1）～（6），将解答填入答题纸的对应栏内。
【说明】
    很多依托扑克牌进行的游戏都要先洗牌。下面的Java代码运行时先生成一副扑克牌，洗牌后再按顺序打印每张牌的点数和花色。
【Java代码】
import iava.util.List;
import java.util.Arrays;
import java.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<list.size();  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();
    }
}

答案与解析

  • 试题难度：较难
  • 知识点：Java程序设计>Java程序设计案例
  • 试题答案：
    （1）this.
    （2）this.
    （3）deck[count++]     或等价表示
    （4）get(i).getCard()
    （5）new DeckOfCards()
    （6）player.
  • 试题解析：
        本题考查Java语言程序设计的能力，涉及类、对象、方法的定义和相关操作。要求考生根据给出的案例和代码说明，认真阅读，理清程序思路，然后完成题目。
        先考查题目说明。本题目中涉及到扑克牌、牌桌、玩家等类以及洗牌和按点数排序等操作。根据说明进行设计。
        Card类内定义了两个static枚举类型，Face枚举扑克牌点数，Suit枚举扑克牌花色。Card类有两个枚举类型的属性，face和suit，而且值不再变化，故用final修饰。
        在使用构造方法public Card( Face face, Suit suit)新建一个Card的对象时，所传入的参数指定face和suit这两个属性值。因为参数名称和属性名称相同，所以用this.前缀区分出当前对象。在类Card中包含方法getFace()和getSuit()，分别返回当前对象的face和suit属性值。getCard()方法返回String来表示一张牌，包括扑克牌点数和花色。
        牌桌类DeckOfCards包含持有Card类型元素的List类型对象的声明List，用以存储牌。List是Java中的一种集合接口，是Collection的子接口。构造方法中用Card对象填充牌桌并进行洗牌。先用Card对象填充牌桌，即创建52个Card对象加入deck数组，表示牌桌上一副牌（52张）。然后洗牌，即将数组中的Card财象根据花色和点数随机排列，使用集合工具类Collections中的shuffle方法，对以List类型表示的deck数组进行随机排列。Collections是Java集合框架中两个主要工具类之一，用以进行集合有关的操作。
        printCards()方法将所有Card对象打印出来，按4列显示52张牌。每张拍的打印用list.get(i)获得list表示的deck中的第i个Card对象，然后进一步调用此对象的getCard()方法，得到String表示的当前一张牌。
        玩家类中包括启动发牌洗牌等操作，主入口方法main中实现创建牌桌对象，并调用按4列显示52张牌。在main()中，先初始化DeckOfCards类的对象player，即生成一个牌桌：
        DeckOfCards  player=new DeckOfCards();
        并发牌，即调用player的printCards()方法，实现按4列显示52张牌打印一副扑克牌中每张牌的点数和花色。在printCards()方法体内部，用list调用每个数组元素，并为每个数组元素调用getCard()返回当前对象所表示一张牌的花色和点数。用格式化方法进行打印, 即:
        System.out.printf( "%-19s%s",  list.get(i).getCard(),((i+1)%4==0)?"\n":"" );
        因此，空（1）和（2）需要表示当前对象的this.；空（3）需要牌桌上纸牌对象，并将数组元素下标加1，即数组元素deck[count++]；空（4）也需要用list对象获得纸牌对象的字符串表示，即list.后的get(i).getCard()；空（5）处为创建DeckOfCards类的对象指针player的new DeckOfCards()：空（6）需要用对象player调用打印所有纸牌的printCards()函数，即player.。

results matching ""

    No results matching ""