2014下半年程序员上,下午真题分析与解答

 阅读以下说明和Java程序，填补代码中的空缺(1)～(6)，将解答填入答题纸的

对应栏内。

【说明】

    很多依托扑克牌进行的游戏都要先洗牌。下面的Java代码运行时先生成一副扑克

牌，洗牌后再按顺序打印每张牌的点数和花色。

【Java代码】

 阅读下列说明、c++代码和运行结果，填补代码中的空缺(1)～(6)，将解答填入

答题纸的对应栏内。

【说明】

    很多依托扑克牌进行的游戏都要先洗牌。下面的c++程序运行时先生成一副扑克牌，

洗牌后再按顺序打印每张牌的点数和花色。

【c++代码】

#inciude ＜iostream＞

4Finclude ＜stdlib. h＞

#include ＜ctime＞

#inciude ＜aigorithm＞

#include ＜string＞

Using  namespace std 

Const  string   Rank[13]={”A”,”2”,”3”,”4“,“5”,”6，”’“7”8“,9”,”10,”J”，

”Q”，”K”}j／／扑克牌点数

阅读以下说明和C函数，填补函数代码中的空缺(1)～(5)，将解答填入答题纸

的对应栏内。

【说明】

    队列是一种常用的数据结构，其特点是先入先出，即元素的插入在表头、删除在表

尾进行。下面采用顺序存储方式实现队列，即利用一组地址连续的存储单元存放队列元

素，同时通过模运算将存储空间看作一个环状结构（称为循环队列）。

    设循环队列的存储空间容量为MAXQSIZE，并在其类型定义中设置base、rear和

lengtb三个域变量，其中’base为队列空间的首地址，rear为队尾元素的指针，length表

示队列的长度。

#define  maxqstze  100

typedef  struct  {

             QElemType *base;   /*循环队列的存储空间首地址*／

             int          rear;  ／*队尾元素索引*／

    int    length;    ／*队列的长度*／

    ) SqQueue;

    例如，容量为8的循环队列如图3-1所示，初始时创建的空队列如图3一l(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=O；

Q-’rear =O：

  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；否则返回O*／

{1f‘(4)，return  0；

    *e =O-＞base[ (Q=＞rear - Q-＞length+I+MAXQSTZE) %MAXQSIZE]

        (5)  ；

    returnl；

  } /*DeQueue*/

 阅读以下说明和C函数，填补代码中的空缺(1)～(6)，将解答填入答题纸的对

应栏内。

【说明】

  二叉树的宽度定义为含有结点数最多的那一层上的结点数。函数GetWidth()用于求

二叉树的宽度。其思路是根据树的高度设置一个数组counter[]. counter[i]存放第i层上

的结点数，并按照层次顺序来遍历二叉树中的结点，在此过程中可获得每个结点的层次

值，最后从countler[]中取出最大的元素就是树的宽度。

  按照层次顺序遍历二叉树的实现方法是借助一个队列，按访问结点的先后顺序来记

录结点，离根结点越近的结点越先进入队列，具体处理过程为；先令根结点及其层次号

（为1）进入初始为空的队列，然后在队列非空的情况下，取出队头所指示的结点及其层

次号，然后将该结点的左子树根结点及层次号八队列（若左子树存在），其次将该结点的

右子树根结点及层次号八队列（若右子树存在），然后再取队头，重复该过程直至完成

遍历。

    设二叉树采用二叉链表存储，结点类型定义如下：

typedef struct BTNode{

             TElemType data;

               struct  BTNode  *left. *right

}  BTNode , *BiTree _

队列元素的类型定义如下

typedef struct {

             BTNode *ptr;

             int LevelNumber

) QElemType;

【C函数】

int GetWidth (BiTree  root)

{

            QUEUE  Q;

QElemType  a, b;

       int width.height = GetHeight(root);

    int i,  *counter  =(lnt*) calloc (helght+l. sizeof (int));

if  ( 1)    return -1;  ／*申请空间失败*/

If(!root )   return -0;  /*空树的宽度为0*／

if  ( 1)    return -1  /*初始化队列失败时返回*／

A.ptr=root;  a.leveinumber=1;

If(!Enqueue(＆Q,a))  return-1;   ／*元素入队列操作失败时返回*／

while (！isEmpty(Q》{

    if(  (3)  )return -1;    /*出队列操作失败时返回*／

    Counter[b．LevelNumber]++；／*对层号为b．LevelNumber的结点计数*/

    if（bNaNr=＞left）{／*若左子树存在，则左于树根结点及其层次号入队*／

    aNaNr =bNaNr=＞left;

    a.LevelNurnber  =(4)  ；

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

}

if( bNaNr=＞right){／*若右子树存在，则右子树根结点及其层次号入队*／

    a．ptr= bNaNr-＞right;

    a LevelNumber  (5)  i

   If(!EnQueue (&Q,a))return  -1

   }

}

width= counter[1];

For(i=1; i

   If(6) width =counter[i];

  Free(counter);

  Return width;

}

??????

 阅读以下说明和流程图，填补流程图中的空缺(1)～(5)，将解答填入答题纸的

对应栏内。

【说明】

    本流程图旨在统计一本电子书中各个关键词出现的次数。假设已经对该书从头到尾

依次分离出各个关键词{A(i)li=l，…，n}(n＞1)}．其中包含了很多重复项，经下面的流程

处理后，从中挑选出所有不同的关键词共m个{K（j）[j=l，…，m}，而每个关键词K（j）出现的次数为NK（j）．j=l，…，m。

 阅读以下说明和C函数，填补代码中的空缺(1)～(5)，将解答填入答题纸的对

应栏内。

【说明】

    函数removeDuplicates(char *str)的功能是移除给定字符串中的重复字符，使每种字

符仅保留一个，其方法是：对原字符串逐个字符进行扫描，遇到重复出现的字符时，设

置标志，并将其后的非重复字符前移。例如，若str指向的字符串为“aaabbbbscbsss”，

则函数运行后该字符串为“abse”。

【c代码】

void removeDuplicates (char *str)

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

If(  (l)  )return;／*空串或长度为1的字符串无需处理*l

    for（i=0;i＜len;i++) {

    Int  flag =O；    ／*字符是否重复标志*／

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+l; n

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

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

}

Str[(5)]=\0;  /* 设置字符串结束标志*／

     }

   }

}

When paying cnline,you should pay attention to(75） your personal and financial Information

Many compute’languages provide a mechanism to call (73) provided by libraries such as in .dlls

(74) is a very impomnt task in the sottware development process, because an incorrect program can have significant consequences for the users

Stated more formally, an object is simply (72) of a class