201611程序员下午真题

第 1 题

阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。
【说明】
设有整数数组A[1：N]（N>1），其元素有正有负。下面的流程图在该数组中寻找连续排列的若干个元素，使其和达到最大值，并输出其起始下标K、元素个数L以及最大的和值M。
例如，若数组元素依次为3，-6，2，4，-2，3，-1，则输出K=3，L=4，M=7。该流程图中考查了A[1：N]中所有从下标i到下标j（j≥i）的各元素之和S，并动态地记录其最大值M。

【流程图】

注：循环开始框内应给出循环控制变量的初值和终值，默认递增值为1，格式为：循环控制变量=初值，终值 **答案与解析** - 试题难度：较难 - 知识点：流程图>流程图 - 试题答案：（1）i，N
（2）S+A[j]
（3）S
（4）j-i+1
（5）S - 试题解析：要想在数组中寻找连续排列的若干个元素，使其和达到最大值，并输出其起始下标K、元素个数L以及最大的和值M。
那么，会将数组从第一个元素出发，依次比较A[1]，A[1] +A[2]，A[1] +A[2]+A[3]，……，A[1] +A[2]+…+A[N]，然后再比较A[2], A[2] +A[3]，A[2] +A[3]+A[4]，……，A[2] +A[3]+…+A[N]，然后再比较A[3] +A[4]，A[3] +A[4]+A[5]，……，A[3] +A[4]+…+A[N]，直到最后一个元素A[N].
按照这种逻辑，要使用两个循环，且要保存之前求和项。一个是i循环，从1到N递增，另一个是j循环，j表示的是求和项的最大下标值，那么j从i开始，且要小于N。 S+A[j]—>S不断保留A[i]+ A[i+1]+…A[j]的值，直到j循环结束。并将S的值与之前保存的M的值进行比较，如果S>M，则将S的值赋给M，并求出L值，在这里，i是最小下标值，j是最大下标值，那么L=j-i+1。如果S<M，则跳出循环。 ### 第 2 题阅读以下代码，回答问题：1至问题3 ，将解答填入答题纸的对应栏内。
【代码1】

#include<stdio.h >
void swap(int x, int y)
{
  int tmp =x;   x= y; y= tmp;
}
int main()
{
       int a= 3, b= 7;
       printf("a1= %d b1=%d\n",a,b);
       swap( a, b);
       printf("a2 = %d b2=%d\n”,a,b)；
       return 0;
}

【代码2】
#include<stdio.h>
#define SPACE " //空格字符
int main()
{
    char str[128] =" Nothing is impossible! ";
int i,num =0,wordMark=0;

    for(i=0;str[i];i++)
If(str[i]==SPACE)
WordMark=0;
else
If(wordMark=0){
wordMark=1;
num++;
}

   printf(“%d/n”,num)
return 0;
}

【代码3】
#include<stdio.h>
#define   SPACE " //空格字符

int countStrs(char *);

int main()
{
char str[128] = " Nothing is impossible! ";
   printf("%d/n",（1）(str))
return 0;
}

int countStrs(char *p)
{
     int num=0, wordMark= 0;
     for(;（2）; p++)   {
       If(（3）==SPACE)
            wordMark= 0;
else
         if( !wordMark ) {
             wordMark = 1;
               ++num
}
    }
    return （4） ;
}

【问题1】（4分）
写出代码1运行后的输出结果。
【问题2】（3分）
写出代码2运行后的输出结果。
【问题3】（8分）
代码3的功能与代码2完全相同，请补充3中的空缺，将解答写入答题纸的对应栏内。

**答案与解析** - 试题难度：较难 - 知识点：C程序设计>C程序设计 - 试题答案：（1）a1=3 b1=7 a2=3 b2=7
（2）3
（3）① countStrs     ②*p    ③*p    ④num
- 试题解析：此题考查C语言程序设计能力，要求掌握形参与实参，值传递与引用传递的区别
1、本题考查函数中值传递与引用传递，在实参与形参传递过程中可以是值传递，值传递时，形参的改变不会影响实参，引用传递是地址的传递，实参将地址传递给形参时，形参的改变会影响实参的改变。在本题中的第一次输出a,b变量的值时，结果是直接输出，所以a1=3,b1=7,而在调用swap函数时，实参a,b传递的是值传递，在函数swap(int x,int y)中形参x,y也是值类型，在函数swap内部是交换两个变量的值，交换完毕后x=y,y=x,但这个改变不会影响实参a,b，所以第二次输出a2,b2时，a,b的值不变还是3，7,所以输出结果是：a1=3 b1=7 a2=3 b2=7
2、本题是计算出字符数组中有多少个单词，单词之间是以空格’ ‘为标识，即遇到空格时变量wordMark=0，程序中再判断wordMark是否等于0，若等于0，则变量workMark置为1，同时变量num是用于统计单词个数，此时num加1，最后输出num的值就是统计的单词个数。程序运行结果是3。
3、本题是将上面的功能通过调用函数来完成的。第1处就应该直接填写调用函数的函数名，即countStrs，调用者将数组名作为实参，数组名代表的是数组的首地址，所以这里是引用传递，函数countStrs的形参p是一个指针变量，它接收实参str数组的首地址，这样实参与形参都是指针变量。在函数countStrs内部，定义两个局部变量num用于统计个数，WordMark用于标识空格，在for循环中，第2处应该设置终止条件，即*p，表示指针指向的内容不为空，第3处是判断当前的指向元素是否等于SPACE，即当前的*p是否是空格’ ‘，如果是则将标识变量WordMark等于0，否则变量num自增，最后函数应该返回num的值，所以4处应该填num。答案是：1) countStrs 2) p[i]!='\0'或者是p[i]   3) p[i]    4) num

### 第 3 题

阅读以下说明和代码，填补代码中的空缺，将解答填入答题纸的对应栏内。
【说明】
下面的程序利用快速排序中划分的思想在整数序列中找出第k小的元素（即将元素从小到大排序后，取第k个元素）。
对一个整数序列进行快速排序的方法是：在待排序的整数序列中取第一个数作为基准值，然后根据基准值进行划分，从而将待排序的序列划分为不大于基准值者（称为左子序列）和大于基准值者（称为右子序列），然后再对左子序列和右子序列分别进行快速排序，最终得到非递减的有序序列。
例如，整数序列“19， 12， 30， 11，7，53， 78， 25"的第3小元素为12。整数序列“19，12，7，30，11，11，7，53，78，25，7"的第3小元素为7。
函数partition（int a[ ], int low,int high）以a[low]的值为基准，对a[low]、a[low+1]、…、
a[high]进行划分，最后将该基准值放入a[i] (low≤i≤high)，并使得a[low]、a[low+1]、，．．、
A[i-1]都小于或等于a[i]，而a[i+1]、a[i+2]、．．、a[high]都大于a[i]。
函数findkthElem(int a[],int startIdx,int endIdx,inr k)在a[startIdx]、a[startIdx+1]、...、a[endIdx]中找出第k小的元素。

#include <stdio.h>

#include <stdlib.h>

int partition(int a [ ],int low, int high)

{//对 a[low..high]进行划分,使得a[low..i]中的元素都不大于a[i+1..high]中的元素。

int pivot=a[low]; //pivot表示基准元素

int i=low,j=high;

while(( 1 ) ){

while(i<j&&a[j]>pivot)--j;

a[i]=a[j];

while(i<j&&a[i]<=pivot)++i;

a[j]=a[i];

}

( 2 ) ; //基准元素定位

return i;

}

int findkthElem(int a[],int startIdx,int endIdx, int k)

{//整数序列存储在a[startldx..endldx]中,查找并返回第k小的元素。

if (startIdx<0 ||endIdx<0 || startIdx > endIdx || k<1 ||k-1>endIdx ||k-1<startIdx)

return-1; //参数错误

if(startIdx<endIdx){

int loc=partition(a, startIdx, endIdx); //进行划分,确定基准元素的位置

if (loc== k-1) //找到第k小的元素

return ( 3 ) ;

if(k-1 < loc) //继续在基准元素之前查找

return findkthElem(a , ( 4 ), k ) ;

else //继续在基准元素之后查找

return findkthElem(a, ( 5 ),k);

}

return a[startIdx];

}

int main()

{

int i, k;

int n;

int a[] = {19, 12, 7, 30, 11, 11, 7, 53, 78, 25, 7};

n= sizeof(a)/sizeof(int); //计算序列中的元素个数

for (k=1;k<n+1;k++){

for(i=0;i<n;i++){

printf("%d\t",a[i]);

}

printf("\n");

printf("elem %d=%d\n",k,findkthElem(a,0,n-1,k));//输出序列中第k小的元素

}

return 0;

}

**答案与解析** - 试题难度：较难 - 知识点：C程序设计>C程序设计 - 试题答案：1、i!=j或者i<j
2、a[i]=pivot
3、a[loc]
4、startIdx,loc-1
5、loc+1,endIdx - 试题解析：

此题考查排序算法的应用，快速排序的思想是：通过一趟排序将待排序的记录划分为独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后利用递归再分别对这两部分记录继续进行排序，以达到整个序列有序。一趟排序的具体做法是：设两个变量low和high，初值分别指向序列的第一个和最后一个，通常将第一个记录的关键字设为pivotkey，首先从high所指位置向前搜索，找到第一个关键字小于pivotkey的记录并互相交换，然后从low位置向后搜索，找到第一个大于pivotkey的记录并互相交换，重复这两步直到low=high为止。

本题是要找出第K个元素，要求将元素从小到大排序，然后取第K个元素。如数组中的元素是19,12,7,30,11,11,7,53,78,25,7，则第1，2，3个元素都是7，第4，5个元素是11，第6个元素是12，第11个元素是78，本题就是要找出前K个元素中第K个元素，K是不断变化的，K的取值范围是从1到数组长度，第K个元素也是不断变化的。

Partition函数是找到基准元素的位置，根据快速排序算法，循环判断的条件是最小值和最大值不相等，即1处应该填i!=j或者i<j，当开始位置和结束位置不相等时则从数组的两端分别向中间扫描。扫描的方法是：依次比较数组的high与基准pivot的大小，如果a[j]>=pivot，则j--，直到遇到第一个pivot>a[j]，则停止移动，将a[j]赋值给a[i]，同时依次比较数据的low与基准pivot的大小，如果a[i]<=pivot，则i++，直到遇到第一个pivot<a[i]，则停止移动，将a[i]赋值给a[j]，直到i等于j，则完成一次快速排序，此时找到了基准元素的位置，将基准元素移到正确的位置，赋给a[i]，并返回i的值，作为函数partition的结果。

FindthElem函数是查找并返回第k小的元素，它实际上是将原来应该在快速排序中递归完成的功能换成了FindthElem函数去完成，形参k用来接收partition函数中的i，第3处上面的if(loc==k-1)判断成立的时候表明此时找到了第k个的元素，所以直接返回数组第loc位置的元素，所以3处填a[loc]，第4处，第5处是当没有确定基准元素位置时，重复调用自己，重复调用时要判断k与loc的大小，小于loc时，表明要向前移动，大于loc时，要向后移动，所以处4处填startIdx,loc-1，第5处填loc+1,endIdx。答案是：1）i!=j或者i<j 2）a[i]=pivot 3）a[loc] 4）startIdx,loc-1 5）loc+1,endIdx，整个程序运行结果是：

第 4 题

阅读以下说明和代码，填补代码中的空缺，将解答填入答题纸的对应栏内。
【说明】
图是很多领域中的数据模型，遍历是图的一种基本运算。从图中某顶点v出发进行广度优先遍历的过程是：
①访问顶点v；
②访问V的所有未被访问的邻接顶点W1 ，W2 ，..，Wk；
③依次从这些邻接顶点W1 ，W2 ，..，Wk出发，访问其所有未被访问的邻接顶点；依此类推，直到图中所有访问过的顶点的邻接顶点都得到访问。
显然，上述过程可以访问到从顶点V出发且有路径可达的所有顶点。对于从v出发不可达的顶点u，可从顶点u出发再次重复以上过程，直到图中所有顶点都被访问到。
例如，对于图4-1所示的有向图G，从a出发进行广度优先遍历，访问顶点的一种顺序为a、b、c、e、f、d。

设图G采用数组表示法（即用邻接矩阵arcs存储），元素arcs[i][j]定义如下：

图4-1的邻接矩阵如图4-2所示，顶点a~f对应的编号依次为0~5.因此，访问顶点a的邻接顶点的顺序为b，c，e。

函数BFSTraverse(Graph G)利用队列实现图G的广度优先遍历。
相关的符号和类型定义如下：

define MaxN 50 ／图中最多顶点数／

typedef int AdjMatrix[MaxN][MaxN]；

typedef struct{
int vexnum, edgenum; ／图中实际顶点数和边（弧）数／
AdjMatrix arcs; ／邻接矩阵／
}Graph;
typedef int QElemType；
enum {ERROR=0;OK=1};
代码中用到的队列运算的函数原型如表4-1所述，队列类型名为QUEUE。

【代码】
int BFSTraverse(Graph G)
{//对图G进行广度优先遍历，图采用邻接矩阵存储
unsigned charvisited；      //visited[]用于存储图G中各顶点的访问标志，0表示未访问
int v, w, u;
QUEUEQ Q;

∥申请存储顶点访问标志的空间，成功时将所申请空间初始化为0
visited=(char)calloc(G.vexnum, sizeof(char));
If( （1） )
retum ERROR;

（2）；           //初始化Q为空队列
for( v=0; v<G.vexnum; v++){
   if(!visited[v]){          //从顶点v出发进行广度优先遍历
printf("%d”，v)；       //访问顶点v并将其加入队列
visited[v]=1；
      （3）；
    while(！isEmpty(Q)){
      （4）；              //出队列并用u表示出队的元素
   for(w=0;v<G.vexnum; w++){
if（G.arcs[u][w]!=0&& （5）   ){    //w是u的邻接顶点且未访问过
printf("%d”, w)； //访问顶点w
visited[w]=1；
EnQueue(&Q, w);
}
    }
   }
}
    free(visited);
    return OK;
)//BFSTraverse

答案与解析

试题难度：较难
知识点：C程序设计>C程序设计
试题答案：1、visited==NULL
2、InitQueue(&Q)
3、EnQueue(&Q,v)
4、DeQueue(&Q,&u)
5、visited[w]==0
试题解析：本题考查图的遍历问题，图的存储有邻接矩阵和邻接链表两种，图的遍历有深度遍历和广度遍历两种，广度遍历是尽可能进行横向搜索，即最先访问的顶点的邻接点也先被访问，为此需要引入队列来保存已访问过的顶点序列，即每当一个顶点被访问后，就将其放入队中，当队头顶点出队时，就访问其未被访问的邻接点并令这些邻接顶点入队。在广度优先遍历中，每个顶点至多进行一次队列。题目中已经提供队列的有关操作，如初始化队列，入队，出队等。
程序中第1处应该填visited==NULL，表示分配内存函数calloc分配内存空间是否成功，如果失败，则程序返回0。第2处填InitQueue(&Q)，表示初始化队列，函数InitQueue的形参是一个指针变量，接收一个指向QUEUE的变量，所以实参应该是一个地址，即&Q，第3处是顶点v入队，入队函数EnQueue有两个形参，一个是指针变量Q，一个是元素qe，所以此处填EnQueue(&Q,v)，第4处是出队，出队函数也有两个参数，一个是指向队列的指针变量Q，另一个参数是int类型的指针变量*te，表示要通过参数te带回出队的元素，即知道是哪个元素出队了，所以实参在传递时应该使用引用传递，因此第4处填DeQueue(&Q,&u)，第5处是判断图Garcs中w顶点是否被访问过，visited[]数组是用于存储图G中各顶点的访问标志，0表示未访问，1表示已访问，此处是要判断w顶点是否被访问过，即visited[w]是否等于0，所以第5处填visited[w]==0，如果没有访问过，则将w顶点置为1，并入队。

第 5 题

阅读以下说明和Java程序，填补代码中的空缺，将解答填入答题纸的对应栏内。
【说明】：
以下Java代码实现一个简单的聊天室系统（ChatRoomSystem），多个用户(User)可以向聊天室( ChatRoom)发送消息，聊天室将消息展示给所有用户。类图如图5-1所示。

图5-1 类图

【Java代码】
class ChatRoom {
public static void showMessage(User user, String message) {
System.out.println("[" + user.getName() + "] : " + message);
}
}

class User{
   private String name;

    public String getName() {
return name;
    }

    public void setName(String name) {
        this.name = name;
    }

public User(String name) {
  （1） =name；
}

    public void sendMessage(String message) {
（2） (this, message);
}
}

public class ChatRoomSystem {
public void startup() {
User zhang= new User("John");
User li =new User("Leo");

zhang.sendMessage("Hi! Leo! ");
Li.sendMessage("Hi! John!");
}
public void join(User user) {
（3） ("Hello Everyone! I am" + user.getName());
}
public static void main(String[] args) {
ChatRoomSystem crs= （4） ;
Crs.startup();
Crs.join( （5） (“Wayne”))；
}
}

/
程序运行结果：
[John]：Hi! Leo!
[Leo]：Hi! John!
[Wayne]：Hello Everyone! I am Wayne
/

答案与解析

试题难度：较难
知识点：Java程序设计>Java程序设计案例
试题答案：1、this.name
2、ChatRoom.showMessage
3、user.sendMessage
4、new ChatRoomSystem()
5、new User
试题解析：本题考查java程序基本知识，涉及到类的定义，方法调用及封装等。
第1处填this.name，User类中定义了一个私有变量name，及两个属性getName，setName。
一个构造方法User(String name)，因为构造方法中的参数名与变量同名，所以要加this区别，因此第1处填this.name，第2处定义了一个方法sendMessage，此处要调用ChatRoom类中的showMessage方法，传递两个参数，以实现某个人说了某句话，所以第2处填ChatRoom.showMessage，另外类ChatRoomSystem定义了方法join，传入一个User类型的用户变量user，此处必须调用User类中的sendMessage方法，第3处填user.sendMessage，第4处是实例化ChatRoomSystem类，并赋给变量crs，所以第4处填new ChatRoomSystem()，第5处是调用ChatRoomSystem类的join方法，要求传入一个User类型的变量，而User类有个构造方法，要求有初始值，所以第5处填写New User。

第 6 题

阅读以下说明和Java程序，填补代码中的空缺，将解答填入答题纸的对应栏内。
【说明】：
以下Java代码实现一个简单的聊天室系统（ChatRoomSystem），多个用户（User）可以向聊天室（ ChatRoom）发送消息，聊天室将消息展示给所有用户。类图如图5-1所示。

图6-1 类图

【C++代码】

include<iostream>

include <string>

using namespace std；

class User {
private:
string name;
public:
User(string name){
           （1） =name；
     }
     ~User(){}
     void setName(string name) {
this->name=name;
}
     string getName(){
return name;
}

void sendMessage(string message);
};

class ChatRoom {      .
public:
static void showMessage(User user, string message) {
                cout<<"["<<user->getName()<<"] : "<<message<<endl;
}
};

void User::sendMessage(string message) {
  （2） (this,message);
}

class ChatRoomSystem{
public: .                                  .
    void startup() {
User zhang = new User(“John");
User li = new User("Leo");

zhang->sendMessage("Hi! Leo!");
li_>sendMessage("Hi! John!");
    }

    void join(User user) {
            （3） ("HeIIo Everyone! l am"+user->getName());
     } .
};

int main(){
ChatRoomSystemcrs= （4） ;
crs->startup();
crs->join( （5） ("Wayne"));
delete crs;
}
/
程序运行结果：
[John]：Hi! Leo!
[Leo]：Hi! John!
[Wayne]：Hello Everyone! I am Wayne
/*

答案与解析

试题难度：较难
知识点：C++程序设计>C++程序设计
试题答案：1、this->name
2、ChatRoom::showMessage
3、user->sendMessage
4、new ChatRoomSystem()
5、new User
试题解析：（1）this->name      给成员属性姓名赋值
（2）ChatRoom::showMessage 调用聊天室方法显示聊天信息，是谁说了话，说的什么话
（3）user->sendMessage    新用户加入聊天室，发送对应的消息
（4）new ChatRoomSystem()   创建聊天室系统对象
（5）new User    创建用户对象

201611程序员下午真题

201611程序员下午真题

第 1 题

第 4 题

define MaxN 50 ／图中最多顶点数／

第 5 题

第 6 题

include<iostream>

include <string>

results matching ""

No results matching ""