一、问答题
1、第一题 阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。
【说明】
对于大于1的正整数n，(x+1)n可展开为
问题：1.1 【流程图】
注：循环开始框内应给出循环控制变量的初值和终值，默认递增值为1。
格式为：循环控制变量=初值，终值，递增值。
参考答案：
（1）2，n，1
（2）A[k]
（3）k-1，1，-1
（4）A[i]+A[i-1]
（5）A[i]
解析：
（1）根据流程图，此处应为循环控制变量的初值、终值和递增值的填写。由于题目要求计算的是杨辉三角，所以循环控制变量应从第二行开始，即初值为2，一直到第n行。递增值默认为正序递增，此处无需特别指明。因此填写为循环控制变量=2，n，1。
（2）根据流程图中的赋值操作，此处应为数组元素A[k]的赋值操作。因此填写为A[k]。
（3）根据流程图中的循环结构，此处应为循环控制变量的逆序递减操作。由于题目没有给出具体的递减值，默认为递减值为负一。因此填写为循环控制变量=k-1，终值未给出（根据题目要求应为正无穷或其他合适的值），递减值=-1。此处需要注意与初值时的正序递增区别开来。
（4）根据流程图中的求和操作，此处应为数组元素之和的计算。因此填写为A[i]+A[i-1]。其中，“求和”表示两个相邻的数组元素相加的操作。因此正确填写即可。
（5）根据流程图中的赋值操作，此处应为计算结果的赋值操作。因此填写为A[i]。表示将计算结果赋值给数组元素A[i]。
2、第二题
阅读以下说明和代码，填补代码中的空缺，将解答填入答题纸的对应栏内。
【说明】
对n个元素进行简单选择排序的基本方法是：第一趟从第1个元素开始，在n个元素中选出最小者，将其交换至第一个位置，第二趟从第2个元素开始，在剩下的n-1个元素中选出最小者，将其交换至第二个位置，依此类推，第i趟从n-i+1个元素中选出最小元素，将其交换至第i个位置，通过n-1趟选择最终得到非递减排序的有序序列。
问题：2.1 【代码】
#include <stdio.h>
void selectSort(int data[ ],int n)
//对 data[0]~data[n-1]中的n个整数按非递减有序的方式进行排列
{
int i,j,k;
int temp;
for(i=0;i<n-1;i++){
for(k=i,j=i+1;（1）;（2）) //k表示data[i]~data[n-1]中最小元素的下标
if(data[j]<data[k]) （3）
if(k!=i) {
//将本趟找出的最小元素与data[i]交换
temp=data[i]; （4） ;data[k]=temp;
}
}
}
int main()
{
int arr[ ]={79,85,93,65,44,70,100,57};
int i,m;
m=sizeof(arr)/sizeof(int); //计算数组元素的个数，用m表示
（5）; //调用selectSort对数组arr进行非递减排序
for(（6）;i <m;i++) //按非递减顺序输出所有的数组元素
printf(“%d\t”,arr[i]);
printf(“\n”);
return 0;
}
参考答案：
j<n或者j<=n-1
（2）j++
（3）k=j
（4）data[i]=data[k]
（5）selectSort(arr,m)此处m也可以填8或者sizeof(arr)/sizeof(int), arr可以改成&arr[0]
（6）i=0
解析：
根据题目描述和参考解析，我们可以得知以下填空答案：第一空应填j<n或者j<=n-1；第二空填j++；第三空为自动保存最大元素的下标，填k=j；第四空为交换两个元素，使用data[i]=data[k]；第五空为调用selectSort函数进行排序，参数为数组名和数组元素个数，即selectSort(arr, m)；第六空为遍历输出数组元素，从下标为0开始，填i=0。第七空和第八空是关于数组和指针的使用问题，需要注意传递数组的地址和数组元素的个数作为参数。同时需要注意格式化字符串的使用和程序逻辑的正确性。
3、第三题
阅读以下代码和问题，回答问题1至问题3，将解答填入答题纸的对应栏内。
【代码 1】
typedef enum {A，B，C，D} EnumType;
EnumType f(int yr)
{
if(0 == yr%400) {
return A;
}
else if (!(yr%4)) {
if(0!=yr%100)
return B;
else
return C;
}
return D;
}
【代码2 】
#include<stdio.h>
int main()
{ int score;
scanf("%d"，&score);
switch (score)
{
case 5: printf("Excellent!\n");
case 4: printf("Good!\n"); break;
case 3: printf("Average!\n");
case 2:
case 1:
case 0: printf("Poor!\n");
default: printf("Oops,Error\n");
}
return 0;
}
【代码3】
#include<stdio.h>
int main()
{ int i,j,k;
for(i=0; i<2; i++)
for(j=0; j<3;j++)
for( k=0; k<2;k++) {
if(i!=j&&j!=k)
printf("%d %d %d\n", i,j,k);
}
ruturn 0;
}
问题：3.1 (4分)
对于代码1，写出下面的函数调用后x1 、x2、x3和x4的值。
x1 = f(1997);
x2 = f(2000);
x3 = f(2100);
x4 = f(2020);
问题：3.2 （5分）
（1）写出代码2进行时输入为3的输出结果；
（2）写出代码2进行时输入为5的输出结果。
问题：3.3 （6分）
写出代码3运行后的输出结果。
参考答案：
x1=3;x2=0;x3=2;x4=1
第一个条件 0==yr%400， 2000满足，返回为A；其余都不满足，继续进行判断；
第二个条件 ！yr%4， 1997不满足，返回为D；其余满足，继续进行判断；
第三个条件 0！=yr%100，2020满足，返回为B；2100不满足，返回为C。
枚举类型中列出的每一个枚举符都对应着一个整数值，枚举类型实际上是一个整型符号常量的集合。当定义枚举类型时，枚举符都已经被系统隐含地赋予了一个整型值，默认情况下，第一个元素为0，第二个元素为1，依此类推。所以相应的A=0，B=1，C=2，D=3，故返回为：x1=3;x2=0;x3=2;x4=1。
Average！
poor！
Oops，Error
（2）Excellent！
Good！
控制传递给与开关的值匹配的 case 语句。switch 语句可以包括任意数目的 case 实例，但是任何两个 case 语句都不能具有相同的值。语句体从选定的语句开始执行，直到 break 将控制传递到 case 体以外。case后面的常量表达式实际上只起语句标号作用,而不起条件判断作用,即"只是开始执行处的入口标号". 因此,一旦与switch后面圆括号中表达式的值匹配,就从此标号处开始执行,而且执行完一个case后面的语句后,若没遇到break语句,就自动进入 下一个case继续执行,而不在判断是否与之匹配,直到遇到break语句才停止执行,退出break语句.因此,若想执行一个case分之后立即跳出 switch语句,就必须在此分支的最后添加一个break语句。
0 1 0
0 2 0
0 2 1
1 0 1
1 2 0
1 2 1
解析：
问题 3.1 的解析中，我们根据代码中的逻辑判断，对每一个年份进行条件判断，得到对应的枚举值。问题 3.2 的解析中，我们根据输入的分数，使用switch语句进行匹配，执行相应的case语句，得到输出结果。问题 3.3 的解析中，我们根据代码中的三重for循环和判定条件，输出符合条件的i、j、k的值。
4、第四题
阅读以下说明、C函数和问题，回答问题1和问题2将解答填入答题纸的对应栏内。
【说明】
当数组中的元素已经排列有序时，可以采用折半查找（二分查找）法查找一个元素。下面的函数biSearch(int r[]，int low，int high，int key)用非递归方式在数组r中进行二分查找，函数biSearch_rec(int r[]，int low，int high，int key)采用递归方式在数组r中进行二分查找，函数的返回值都为所找到元素的下标；若找不到，则返回-1。
【C函数1】
int biSearch(int r[]，int low，int high，int key)
//r[low..high] 中的元素按非递减顺序排列
//用二分查找法在数组r中查找与key相同的元素
//若找到则返回该元素在数组r的下标，否则返回-1
{
int mid;
while(（1）) {
mid = (low+high)/2 ;
if (key ==r[mid])
return mid;
else if (key<r[mid])
（2）;
else
（3）;
}/*while*/
return -1;
}/*biSearch*/
【C 函数 2】
int biSearch_rec(int r[]，int low，int high，int key)
//r[low..high]中的元素按非递减顺序排列
//用二分查找法在数组r中查找与key相同的元素
//若找到则返回该元素在数组r的下标，否则返回-1
{
int mid;
if(（4）) {
mid = (low+high)/2 ;
if (key ==r[mid])
return mid;
else if (key<r[mid])
return biSearch_rec(（5）,key);
else
return biSearch_rec(（6）,key);
}/*if*/
return -1;
}/*biSearch_rec*/
问题：4.1 (12分）
请填充C函数1和C函数2中的空缺，将解答填入答题纸的对应栏内。
问题：4.2 (3分）
若有序数组中有n个元素，采用二分查找法查找一个元素时，最多与（ ）个数组元素进行比较，即可确定查找结果。
（7）备选答案：
A.[log2(n+1)] B.[n/2] C.n-1 D.n
参考答案：
low<=high
（2）high=mid-1
（3）low=mid+1
（4）low<=high
（5）low,mid-1
（6）mid+1,high
（7）A
解析：
问题一：对于二分查找算法，首先需要确定查找的范围，即数组中的元素范围。在C函数1的while循环中，(1)处应判断low是否小于等于high，以确定循环是否继续。在二分查找过程中，如果待查找的元素小于中间元素，那么搜索范围缩小到左半部分，即(high = mid - 1)；反之，如果待查找的元素大于中间元素，那么搜索范围缩小到右半部分，即(low = mid + 1)。对于递归版本的二分查找，其逻辑相同，只是在调用自身函数时传递新的范围。因此，(2)和(3)处应填写high = mid - 1和low = mid + 1。在递归版本的二分查找中，(4)处同样需要判断low是否小于等于high以确定递归是否继续。在递归调用时，(5)和(6)处应分别传递左半部分和右半部分的范围。综上，答案如上所述。
问题二：二分查找法是一种高效的查找算法，它的比较次数取决于树的高度。在一个包含n个节点的完全二叉树中，树的高度为log2(n+1)。因此，最多与log2(n+1)个数组元素进行比较即可确定查找结果。所以答案为A。
5、第五题
阅读以下说明和Java代码，填补代码中的空缺，将解答填入答题纸的对应栏内。
【说明】
以下Java代码实现一个超市简单销售系统中的部分功能，顾客选择图书等物件 (Item)加入购物车(ShoppingCart)，到收银台(Cashier)对每个购物车中的物品统计其价格进行结账。设计如图5-1所示类图。
图5-1类图
问题：5.1 【Java代码】
interface Item{
public void accept(Visitor visitor);
public double getPrice();
}
class Book （1）{
private double price;
public Book(double price){（2）;}
public void accept(Visitor visitor){ //访问本元素
（3）;
}
public double getPrice() {
return price;
}
}
//其它物品类略
interface Visitor {
public void visit(Book book);
//其它物品的visit方法
}
class Cashier（4）{
private double totalForCart;
//访问Book类型对象的价格并累加
（5）{
//假设Book类型的物品价格超过10元打8折
if(book.getPrice()<10.0）{
totalForCart+=book.getPrice();
} else
totalForCart+=book.getPrice()*0.8;
}
//其它visit方法和折扣策略类似，此处略
public double getTotal() {
return totalForCart;
}
}
class ShoppingCart {
//normal shopping cart stuff
private java.util.ArrayList<Item>items=new java.util.ArrayList<>();
public double calculatePrice() {
Cashier visitor=new Cashier();
for(Item item:items) {
（6）;
}
double total=visitor.getTotal();
return total;
}
public void add(Item e) {
this.items.add(e);
}
}
参考答案：
implements Item
（2）this.price=price
（3）visitor.visit(this)
（4）implements Visitor
（5）public void visit(Book book)
（6）item.accept(visitor)
解析：
本题考察的是访问者模式在Java中的应用。访问者模式是一种行为设计模式，它封装了一些作用于某种数据结构（如类或对象集合）中元素的操作。该模式可以在不改变数据结构的前提下定义新的操作。
1.（1）处，由于Book类要实现Item接口，所以应使用“implements Item”。
2.（2）处，构造函数需要初始化对象的属性，所以应该是“this.price = price;”来表示初始化Book对象的price属性。
3.（3）处，在accept方法中，需要调用访问者的visit方法，所以应该是“visitor.visit(this);”。
4.（4）处，Cashier类需要实现Visitor接口，所以应使用“implements Visitor”。
5.（5）处，需要实现Visitor接口中的visit方法，针对Book类型物品进行价格访问和累加操作，所以应该是“public void visit(Book book) { … }”。
6.（6）处，在ShoppingCart类的calculatePrice方法中，需要遍历购物车中的所有物品，并调用每个物品的accept方法，让Cashier访问这些物品，所以应该是“item.accept(visitor);”。
6、第六题
阅读下列说明和C++代码，填补代码中的空缺，将解答填入答题纸的对应栏内。
【说明 】
以下C++代码实现一个超市简单销售系统中的部分功能，顾客选择图书等物品（Item）加入购物车（ShoppingCart），到收银台（Cashier）对每个购物车中的物品统计其价格进行结账，设计如图6-1所示类图。
图6-1 类图
问题：6.1 【C++代码】
using namespace std;
class Book;
class Visitor {
public:
virtual void visit(Book* book)=0;
//其它物品的visit方法
};
class Item {
public:virtual void accept(Visitor* visitor)=0;
virtual double getPrice()=0;
};
class Book （1）{
private: double price;
public:
Book (double price){ //访问本元素
（2）;
}
void accept(Visitor* visitor) {
（3）;
}
double getPrice() { return price; }
};
class Cashier（4）{
private;
double totalForCart;
public:
//访问Book类型对象的价格并累加
（5）{
//假设Book类型的物品价格超过10元打8折
if(book->getPrice()<10.0) {
totalForCart+=book->getPrice();
} else
totalForCart+=book->getPrice()*0.8;
}
//其它visit方法和折扣策略类似，此处略
double getTotal() {
return totalForCart;
}
};
class ShoppingCart {
private:
vector<item*>items;
public:
double calculatePrice() {
Cashier* visitor=new Cashier();
for(int i=0;i <items.size();i++)
（6）;
}
double total=visitor->getTotal();
return total;
}
void add(Item*e) {
items.push_back（e）;
}
};
参考答案：
（1）：public Item
（2）this->price=price
（3）visitor->visit(this)
（4）public visitor
（5）void visit(Book*book)
（6）item->accept(visitor)
解析：
本题考察的是访问者模式的应用。访问者模式是一种行为设计模式，它允许你在不改变对象结构的情况下增加新的操作。在这个超市销售系统中，我们需要对不同的商品（Item）进行结账操作，这就是一个典型的访问者模式的应用场景。
（1）在Book类中，由于Book是Item类的派生类，所以应该声明为public并继承自Item类。
（2）在Book类的构造函数中，使用"this->price = price;"来初始化成员变量price。
（3）在Book类的accept方法中，接受一个Visitor类型的指针visitor，并调用其visit方法，即"visitor->visit(this);"。
（4）Cashier类应该有一个visit方法来访问Book类型的对象，所以应该声明为public Visitor。并且，Cashier类需要访问其他类型的物品，因此也应该包含相应的visit方法。
（5）在Cashier类的visit方法中，接受一个Book类型的指针book，并对book进行价格访问和累加操作。如果价格低于10元则直接累加，否则打8折后累加。
（6）在ShoppingCart类的calculatePrice方法中，创建一个Cashier对象visitor，遍历购物车中的每个物品（Item），调用每个物品的accept方法接受visitor的访问，即"items[i]->accept(visitor);"。最后通过visitor的getTotal方法获取总价并返回。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
