试题一（共 20 分）阅读下列说明和图，回答问题 1 至问题 3，将解答填入答题纸对应栏内。【说明】设有二维整数数组（矩阵）A[1:m,1:n],其每行元素从左至右是递增，每列元素从上到下是递增。以下流程图旨在该矩阵中需找与给定整数 X 相等数。如果找不到则输出“false”;只要找到一个（可能有多个）就输出“True”以及该元素下标 i 和 j（注意数组元素下标从 1 开始）。例如，在如下矩阵中查找整数 8，则输出伟：True,4,12 4 6 94 5 9 106 7 10 128 9 11 13流程图中采用算法如下：从矩阵右上角元素开始，按照一定路线逐个取元素与给定整数 X 进行比较（必要时向左走一步或向下走一步取下一个元素），直到找到相等数或超出矩阵范围（找不到）。【流程图】
【问题】该算法时间复杂数是（）
供选择答案：A.O（1） B.O（m+n） C.（m*n） D,O（m2+n2）
（1）n（2）j-1→j（3）i+1→I（4）j（5）C
【解析】
读题，可以看出元素查找过程为从右上角开始，往右或者往下进行查找。因此，初始值i=1，j=n。如果查找值小于右上角值，则往右移动一位再进行比较。所以，第二空填j-1→j 。接下来是判断什么时候跳出循环。此时，终止循环条件是：j=0，也就是其从最右端移到了最左端。再看X＜A[i,j]不成立时，执行流程右枝。此时，也就是说第一行最大值都小于查找值，因此需往下移动一行。所以第三空填i+1→I 。
试题一（共 20 分）阅读下列说明和图，回答问题 1 至问题 3，将解答填入答题纸对应栏内。【说明】设有二维整数数组（矩阵）A[1:m,1:n],其每行元素从左至右是递增，每列元素从上到下是递增。以下流程图旨在该矩阵中需找与给定整数 X 相等数。如果找不到则输出“false”;只要找到一个（可能有多个）就输出“True”以及该元素下标 i 和 j（注意数组元素下标从 1 开始）。例如，在如下矩阵中查找整数 8，则输出伟：True,4,12 4 6 94 5 9 106 7 10 128 9 11 13流程图中采用算法如下：从矩阵右上角元素开始，按照一定路线逐个取元素与给定整数 X 进行比较（必要时向左走一步或向下走一步取下一个元素），直到找到相等数或超出矩阵范围（找不到）。【流程图】
【问题】该算法时间复杂数是（）
供选择答案：A.O（1） B.O（m+n） C.（m*n） D,O（m2+n2）
阅读以下说明和流程图，填补流程图中空缺，将解答填入答题纸对应栏内。
[说明]
指定网页中，某个关键词出现次数除以该网页长度称为该关键词在此网页中词频。对新闻类网页，存在一组公共关键词。因此，每个新闻网页都存在一组词频，称为该新闻网页特征向量。
设两个新闻网页特征向量分别为：甲(a1,a2,...,ak)、乙(b1,b2,...,bk)，则计算这两个网页相似度时需要先计算它们内积S=a1b1+a2b2+...+akbk。一般情况下，新闻网页特征向量维数是巨大，但每个特征向量中非零元素却并不多。为了节省存储空间和计算时间，我们依次用特征向量中非零元素序号及相应词频值来简化特征向量。为此，我们用(NA(i),A(i)|i=1,2,...,m)和(NB(j),B(j)|j=1,2,...,n)来简化两个网页特征向量。其中：NA(i)从前到后描述了特征向量甲中非零元素A(i)序号(NA(1)＜NA(2)＜...)，NB(j)从前到后描述了特征向量乙中非零元素B(j)序号(NB(1)＜NB(2)＜...)。
下面流程图描述了计算这两个特征向量内积S过程。
试题（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，格式为：循环控制变量=初值，终值
阅读以下说明和流程图，填补流程图中空缺，将解答填入答题纸对应栏内。
[说明]
本流程图旨在统计一本电子书中各个关键词出现次数。假设已经对该书从头到尾依次分离出各个关键词{A(i)|i=1,…,n}(n＞1)}，其中包含了很多重复项，经下面流程处理后，从中挑选出所有不同关键词共m个{K(j)|j=1,…,m}，而每个关键词K(j)出现次数为NK(j),j=1,…,m。
[流程图]
阅读下列说明、C++代码和运行结果，填补代码中空缺，将解答填入答题纸对应栏内。
[说明]
对部分乐器进行建模，其类图如下图所示，包括：乐器(Instrument)、管乐器(Wind)、打击乐器(Percussion)、弦乐器(Stringed)、木管乐器(Woodwind)、铜管乐器(Brass)。
类图
下面是实现上述设计C++代码，其中音乐类(Music)使用各类乐器(Instrument)进行演奏和调音等操作。
using namespace std; enum Note(/*枚举各种音调*/ MIDDLE_C,C_SHARP,B_FLAT }; classInstrument{/*抽象基类,乐器*/ public: ______; //play函数接口 virtual voidadjust()=0; //adjust函数接口 }; class Wind ______{ public: void play(Note n) { cout＜＜"Wind.play() "＜＜n＜＜endl; } void adjust(){cout＜＜"Wind.adjust()"＜＜endl; } ); /*类Percussion和Stringed实现代码略*/ class Brass ______{ public: void play(Note n) {cout＜＜"Brass.play() "＜＜n＜＜endl; } void adjUSt(){cout＜＜"Brass.adjust()"＜＜endl;) }; classWoodwind:public Wind{ public: void play(Note n) { cout＜＜"Woodwind.play()"＜＜n＜＜endl; } }; class MusiC { public: voidtune(Instrument*i) { i-＞play(MIDDLE_C.; } voidadjust(Instrument*i){ i-＞adjust(); } void tuneAll(______ e[],int numIns){ /*为每个乐器定调*/ for(int i=0; i＜numIns; i++){ this-＞tune(e[i]); this-＞adjust(e[i]); } } }; /*使用模板定义一个函数size,该函数将返回数组array元素个数,实现代码略*/ int main(){ Music*music=______ Music(); Instrument*orchestra[]={new Wind(),new Woodwind() }; music-＞tuneAll(orchestra,size(orchestra));/*size返回数组orchestra元素个数*/ for(int i=0;i＜size(orchestra);i++) deleteorchestra[i]; delete music; }
本程序运行后输出结果为：
Wind.play()0 Wind.adjust() Woodwind.play()0 Wind.adjust()
第五题 阅读以下说明和Java代码，填补代码中空缺，将解答填入答题纸对应栏内。
【说明】
以下Java代码实现一个超市简单销售系统中部分功能，顾客选择图书等物件 (Item)加入购物车(ShoppingCart)，到收银台(Cashier)对每个购物车中物品统计其价格进行结账。设计如图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);
}
}
【试题三】阅读下列说明和 C 函数，填补 C 函数中空缺，将解答填入答案纸对应栏目内。【说明】字符串是程序中常见一种处理对象，在字符串中进行子串定位、插入和删除是常见运算。设存储字符串时不设置结束标志，而是另行说明串长度，因此串类型定义如下：Typedef struct ﹛char*str ／／字符串存储空间起始地址int length ／／字符串长int capacity ／／存储空间容量﹜SString;【函数 1 说明】函数 indexStr（S,T,pos）功能是：在 S 所表示字符串中，从下标 pos 开始查找 T 所表示字符串首次出现位置。方法是：第一趟从 S 中下标为 pos、T 中下标伟 0 字符开始，从左往右逐个对于来比较 S 和 T 字符，直到遇到不同字符或者到达 T 末尾。若到达 T 末尾，则本趟匹配起始下标 pos 为 T 出现位置，结束查找；若遇到了不同字符，则本趟匹配失效。下一趟从 S 中下标 pos+1 处字符开始，重复以上过程。若在 S 中找到 T，则返回其首次出现位置，否则返回-1。例如，若 S 中字符串伟″students ents″,T 中字符串伟″ent″，pos=0，则 T 在 S 中首次出现位置为 4。【C 函数 1】int indexStr（SString S ,SString T,int pos）﹛int i,j:if（S.length＜1||S.length＜pos+T.length-1）return-1;for（i=pos,j=0;i＜S.length &&j＜T.length;）﹛if （S.str[i]==T.str[j]）﹛i++;j++;﹜else﹛i=（）;j=0﹜﹜if （）return i -T.length;return-1;﹜【函数 2 说明】函数 eraseS 位（S，T}功能是删除字符串 S 中所有与 T 相同子串，其处理过程为: 首先从字符串 S 第一个字符（下标为 0）开始查找子串 T，若找到〈得到子串 在 S 中起始位置），则将串 S中子串 T 之后所有字符向前移动，将子串 T 覆盖，从而将 其删除，然后重新开始查找下一个子串 T，若找到就用后面宇符序列进行覆盖，重复上述过程，直到将 S 中所有子串 T 删除。例如，若字符串 S 为 “12ab345abab678”、T 为“ab”。第一次找到 "ab" 时（位置为（2），将 "345abab678 "前移，S 中串改为"12345abab678" ，第二次找到"ab"时（位置为 5）;将 ab678 前移，S 中串改为 "12345ab678"，第三次找到"ab"时（位置 为 5）;将“678‘前移 ，S 中串改为 "12345678 "。【C 函数 2】void eraseStr（SString*S,SStringT）﹛int i;int pos;if （S->leght＜1||T.length＜1||S->length＜T.length）return;pos=0for（;;）﹛／／调用 indexStr 在 S 所表示串 pos 开始查找 T 位置pos=indexStr（）;if（pos＝=-1） ／／S 所表示串中不存在子串 Treturn;for（i=pos+T.length;i＜S->length;i++） ／／通过覆盖来删除自串 TS->str[（）]=S->str[i];S->length=（）; ／／更新 S所表示串长度﹜﹜
阅读以下说明和C程序，填充程序中空缺，将解答填入答题纸对应栏内。
[说明]
正整数n若是其平方数尾部，则称n为同构数。例如，6是其平方数36尾部，76是其平方数5776尾部，6与76都是同构数。下面程序求解不超过10000所有同构数。
已知一位同构数有三个：1，5，6，因此二位同构数个位数字只可能是1，5，6这三个数字。依此类推，更高位数同构数个位数字也只可能是1，5，6这三个数字。
下面程序处理思路是：对不超过10000每一个整数a，判断其个位数字，若为1、5或6，则将a转换为字符串as，然后对a进行平方运算，并截取其尾部与as长度相等若干字符形成字符串后与as比较，根据它们相等与否来断定a是否为同构数。
[C程序] #include＜stdio.h＞ #include＜stdlib.h＞ #include＜string.h＞ int myitoa(int,char*); /*将整数转换为字符串*/ /*right取得指定字符串尾部长度为length子串,返回所得孔串首字符指针*/ char*right(char*,int length); int main() { int a,t; int fen; char as[10],rs[20]; printf("[1,10000]内同构数:\n"); for(a=1; a＜=10000;a++) { t=______; /*取整数a个位数字*/ if(t!=1&&t!=5&&t!=6)continue; len=myitoa(a,as); /*数a转换为字符串,存入as*/ myitoa(a*a,rs); /*数a平方转换为字符串,存入rs*/ /*比较字符串as与rs末尾长度为len子串是否相等*/ if(strcmp(as,______)==0) /*若相同则是同构数并输出*/ printf("%s平方为%s\n",as,rs); } return 0; } int myitoa(int num,char*s) /*将整数num转换为字符串存入s*/ { int i,n=0; char ch; /*从个位数开始,取num每一位数字转换为字符后放入s[]*/ while(num){ s[n++]=______+'0'; num=num/10; } s[n]='\0'; for(i=0; i＜n/2;i++){ /*将S中字符串逆置*/ ______;s[i]=s[n-i-1]; s[n-i-1]=ch; } return n; /*返回输入参数num位数*/ } char*right(char*ms,int length) /*取字符串ms尾部长度为length孔串,返回所得孔串首字符指针*/ { int i; for(;*ms;ms++); /*使ms到达原字符串尾部*/ for(i=0;i＜length;______); /*使ms指向所得孔串首部字符*/ return ms; }
试题六（共 15 分）阅读下列说明和 C++代码，填补代码中空缺，将解答填入答题纸对应栏内。【说明】以下 C++代码实现一个简单客户关系管理系统（CrM）中通过工厂（Customerfactory）对象来创建客户（Customer）对象功能。客户分为创建成功客户（realCustomer）和空客户（NullCustomer）。空客户对象是当不满足特定条件时创建或获取对象。类间关系如图6-1 所示。
【C++代码】#include＜iostream>#include＜string>using namespace std； class Customer｛protected:string name；public:（1） boll isNil（）=0；（2） string getName（）=0；﹜； class realCustomer （3）｛public:realCustomer（string name）｛this->name=name；﹜bool isNil（）｛ return false；﹜string getName（）｛ return name；﹜﹜； class NullCustomer （4） ｛public:bool isNil（）｛ return true；﹜string getName（）｛ return 〝Not Available in Customer Database〞； ﹜﹜；class Customerfactory｛public:string names［3］=｛〝rob〞, 〝Joe〞,〝Julie〞﹜；public:Customer*getCustomer（string name）｛for （int i=0；i＜3；i++）｛if （names［i］.（5） ）｛return new realCustomer（name）；﹜﹜return （6）；﹜﹜； class CrM｛public:void getCustomer（）｛Customerfactory*（7）；Customer*customer1=cf->getCustomer（〝rob〞）；Customer*customer2=cf->getCustomer（〝Bob〞）；Customer*customer3=cf->getCustomer（〝Julie〞）；Customer*customer4=cf->getCustomer（〝Laura〞）； cout＜＜〝Customers〞＜＜endl；cout＜＜Customer1->getName（） ＜＜endl； delete customer1；cout＜＜Customer2->getName（） ＜＜endl； delete customer2；cout＜＜Customer3->getName（） ＜＜endl； delete customer3；cout＜＜Customer4->getName（） ＜＜endl； delete customer4；delete cf；﹜﹜； int main（）｛CrM*crs=new CrM（）；crs->getCustomer（）；delete crs；return 0；﹜ /*程序输出为：CustomersrobNot Available in Customer DatabaseJulieNot Available in Customer Database*/
第三题 阅读以下代码和问题，回答问题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运行后输出结果。
