一、问答题
1、
试题（15 分）
阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏 内。
【说明】
设有整数数组 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、j=i+1
2、S+A[j]
3、S
4、j-i+1
5、S
解析：
根据说明和流程图的要求，我们需要寻找数组 A[1：N] 中连续排列的若干个元素，使其和达到最大值。
- 从流程图中的顺序可以看出，我们首先初始化 j=i+1，这样我们可以从当前位置开始计算连续子数组的和。
- 在每次循环中，我们需要计算从 i 到 j 的子数组的和，即 S+A[j]。这里 A[j] 是当前位置的元素值。
- 为了找到最大的和值 M，我们需要动态地记录其最大值 M。因此，此处应该是判断当前的和 S 是否大于之前的最大和值 M，而不是简单的比较 S 的正负。如果 S 大于 M，则更新 M 的值。
- 当我们找到一段连续的子数组的和达到最大值时，我们需要输出其起始下标 K 和元素个数 L。在流程图中，通过计算 j-i+1 可以得到当前连续子数组的个数 L。
- 最后，当我们完成所有的比较和计算后，输出最大的和值 M。由于整个流程中都在动态地记录最大的和值 M，因此这一步是合理的。
2、
试题二（共 15 分）
阅读以下代码，回答问题：1 至问题 3 ，将解答填入答题纸的对应栏内。
【代码 1】
#include<stdio.h >
void swap(int x, int y)
{
int tmp =x; x= y; y= tmp;
}
int maim()
{
int a= 3, b= 7;
printf("al= %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;
Mun++;
}
Printf(“%d/n”,num) retun 0;
}
【代码 3】
#include<stdio.h>
#define SPACE “//空格字符
int countStrs(char *); int main()
{
char str[128] = " Nothing is impossible! "; Printf(‘%d/n,（1）(str))
retum 0;
}
int countStrs(char *p)
{
int num=0, wordMark= 0; for(;（2）；p++) {
If(（3）=SPACE)
wordMark= 0;
else
if( !wordMark ) { wordMark = 1;
++mun
}
}
retum （4） ;
}
【问题 1】（4 分）
写出代码 1 运行后的输出结果。
【问题 2】（3 分）
写出代码 2 运行后的输出结果。
【问题 3】（8 分）
代码 3 的功能与代码 2 完全相同，请补充 3 中的空缺，将解答写入答题纸的对应栏内。
参考答案：
问题1
a1=3
b1=7
a2=7
b2=3
问题2
3
问题3
（1)CountStr
（2)p[i]
（3)p[i]
（4)num
解析：
代码 1 中的 swap 函数并没有正确实现两个数的交换。在 C 语言中，函数参数传递的是值，而不是引用。因此，在 swap 函数中对 x 和 y 的修改并不会影响到函数外部的变量。所以，变量 a 和 b 的值并没有交换。在 maim 函数中，先输出了原始的 a 和 b 的值，然后调用了 Swap 函数（注意这里函数名应该是 swap），但由于没有交换成功，再次输出的 a 和 b 的值仍然是原来的值。
3、
试题三（共 15 分）
阅读以下说明和代码，填补代码中的空缺，将解答填入答题纸的对应栏内。
【说明】
下面的程序利用快速排序中划分的思想在整数序列中找出第 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+l]、…、a[high]进行划分，最后将该基准值放入 a[i] (low≤i≤high)，并 使得 a[low]、a[low+l]、，．．、A[i-1]都小于或等于 a[i]，而 a[i+l]、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 (startldx<0 ||endIdx<0 || startIdx>endIdx || k<1 ||k-l>endIdx
||k-1<startIdx)
Return-1; //参数错误 if(startIdx<endldx){
int loc=partition(a, startIdx, endldx)； ∥进行划分，确定基准元素
的位置
if (loc==k-1) ∥找到第 k 小的元素
return （3） ；
if(k-l <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；
}
参考答案：
1) CountStr
2) p[i]
3) p[i]
4) num
3、
1、!i=j
2、a[i]=pivot
3、a[loc]
4、stratIdx,Loc-1
5、Loc+1,endIdx
解析：
题目要求填补代码中的空缺，以完成快速排序算法中的划分函数和查找第 k 小元素的函数。以下是详细的解析：
4、
试题四（共 15 分）
阅读以下说明和代码，填补代码中的空缺，将解答填入答题纸的对应栏内。
【说明】 图是很多领域中的数据模型，遍历是图的一种基本运算。从图中某顶点 v
出发进行广度优先遍历的过程是：
①访问顶点 v；
②访问 V 的所有未被访问的邻接顶点 W1 ,W2 ,..,Wk；
③依次从这些邻接顶点 W1 ,W2 ,..,Wk 出发，访问其所有未被访问的邻接顶 点；依此类推，直到图中所有访问过的顶点的邻接顶点都得到访问。
显然，上述过程可以访问到从顶点 V 出发且有路径可达的所有顶点。对于 从 v 出发不可达的顶点 u，可从顶点 u 出发再次重复以上过程,直到图中所有顶 点都被访问到。
例如，对于图 4-1 所示的有向图 G，从 a 出发进行广度优先遍历，访问顶点 的一种顺序为 a、b、c、e、f、d。
图 4-1
图 4-2
设图 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=l};
代码中用到的队列运算的函数原型如表 4-1 所述，队列类型名为 QUEUE。
表 4-1 实现队列运算的函数原型及说明
【代码】
int BFSTraverse(Graph G)
{//图 G 进行广度优先遍历，图采用邻接矩阵存储
unsigned char*visited； //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]=l；
（3） ； while(！isEmpty(Q)){
（4） ； //出队列并用 u 表示出队的元素 for(v=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
从下列的 2 道试题（试题五至试题六）中任选 1 道解答。请在答题纸上的 指定位置处将所选择试题的题号框涂黑。若多涂或者未涂题号框，则对题号最小 的一道试题进行评分。
参考答案：
1、visited==NULL
2、InitQueue(&Q)
3、EnQueue(&Q,v)
4、DeQueue(&Q,&u)
5、visited==0
解析：
-
第一处判断visited是否为空，如果为空则返回ERROR，表示内存分配失败。这是因为visited数组是用来标记图中各个顶点是否被访问过的，如果无法分配内存给visited数组，则无法进行广度优先遍历。所以选择"visited==NULL"。
-
第二处是初始化队列Q为空队列，使用InitQueue函数进行初始化。这是因为广度优先遍历需要使用队列来保存待访问的顶点，所以在开始遍历之前需要初始化队列。所以选择"InitQueue(&Q)"。
-
第三处是将起始顶点v加入队列Q中，使用EnQueue函数进行入队操作。这是为了从起始顶点开始进行广度优先遍历。所以选择"EnQueue(&Q, v)"。
-
第四处是出队操作，使用DeQueue函数将队列中的元素出队，并用变量u来接收出队的元素。这是为了依次访问队列中的顶点。所以选择"DeQueue(&Q, &u)"。
-
第五处是判断w是否是u的邻接顶点且未被访问过，如果是则进行访问并将w加入队列。这里使用visited数组来标记顶点是否被访问过，如果visited[w]==0，表示顶点w未被访问过。所以选择"visited[w]==0"。
5、
试题五（共 15 分）
阅读以下说明和 Java 程序，填补代码中的空缺，将解答填入答题纸的对应 栏内。
【说明】
以下 Java 代码实现一个简单的聊天室系统（ChatRoomSystem），多个用 户(User)可以向聊天室( ChatRoom)发送消息，聊天室将消息展示给所有用户。 类图如图 5-1 所示。
【Java 代码】 class ChatRoom {
public static void showMessage(User user, Strmg message) {
System.out.println("[" + user.getName() + "] : " + message);
}
}
classUser{
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 Chat:RoomSystem { public void startup() {
User zhang= new User("John");
User li =new User("Leo"); zhang.sendMessage("Hi! Leo! "); 1i.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! Leol [Leo]：Hi! John!
[Wayne】：Hello Everyone!Iam Wayne
*/
参考答案：
1、this.name
2、ChatRoom.showMessage
3、user.sendMessage
4、new ChatRoomSystem()
5、new User
解析：
对于第一个空，在User类的构造函数中，我们需要将传入的参数name赋值给类的成员变量name，因此应该填写this.name = name;。
第二个空在User类的sendMessage方法中，目的是调用ChatRoom类的静态方法showMessage来展示消息。因此，应该填写ChatRoom.showMessage(this, message);。
第三个空在ChatRoomSystem类的join方法中，目的是调用User对象的sendMessage方法来发送欢迎消息。因此，应填写user.sendMessage("Hello Everyone! I am" + user.getName());。
第四个空在ChatRoomSystem类的main方法中，我们需要创建一个新的ChatRoomSystem对象。因此，应填写new ChatRoomSystem()。
最后一个空同样在main方法中，我们需要创建一个新的User对象并命名为"Wayne"。因此，应填写new User("Wayne")。
6、
试题六（共 15 分）
阅读下列说明和 C++代码，填补代码中的空缺，将解答填入答题纸的对应
栏内。
【说明】
以下 C++代码实现一个简单的聊天室系统（ChatRoomSystem），多个用户 (User)可以向聊天室（ChatRoom）发送消息，聊天室将消息展示给所有用户。 类图如图 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 startup0(){
User* zhang = new User(“John"); User* li = new User("Leo");
zhang->sendMessage("Hi! Leo!");
li_>sendMessage("Hi! John!");
}
void join(User* user) {
（3） ("HeIIoEveryone!l am"+user->getName()); . ;
} .
};
int main(){
ChatRoomSystem*crs= （4） ; crs->startup();
crs->join( （5） ("Wayne")); delete crs;
}
/* 程序运行结果： [John]：Hi! Leol [Leo]：Hi! John!
[Wayne】：Hello Everyone!Iam Wayne
/*
参考答案：
1、this->name
2、ChatRoom::showMessage
3、user->sendMessage
4、new ChatRoomSystem()
5、new User
解析：
题目是关于一个简单的聊天室系统的C++代码实现。根据题目描述和给出的代码片段，我们可以进行以下分析：
-
在User类的构造函数中，我们需要初始化name成员变量，所以空缺（1）应填入
this->name = name;。这里的this->name表示当前对象的name成员变量，将其赋值为传入的参数name。 -
在User类的sendMessage方法中，我们需要调用ChatRoom类的showMessage方法来展示消息。因此，空缺（2）应填入
ChatRoom::showMessage。这里的::表示静态成员函数的调用。 -
在ChatRoomSystem类的join方法中，我们需要调用用户的sendMessage方法来发送消息。因此，空缺（3）应填入
user->sendMessage。这里假设该方法内部会有适当的逻辑处理用户的加入和发送消息。 -
在main函数中，我们需要创建ChatRoomSystem的实例来启动聊天室系统。因此，空缺（4）应填入
new ChatRoomSystem()来创建一个新的ChatRoomSystem对象。 -
在main函数中创建新用户时，我们需要使用new关键字来动态分配内存并返回指向新对象的指针。因此，空缺（5）应填入
new User("Wayne")来创建一个名为"Wayne"的新用户对象。注意这里的"Wayne"是作为构造函数的参数来传递的。
综上所述，填空答案为：
（1）this->name = name; （2）ChatRoom::showMessage （3）user->sendMessage （4）new ChatRoomSystem() （5）new User(“Wayne”)
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
