一、问答题
1、阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。
[说明]
指定网页中，某个关键词出现的次数除以该网页长度称为该关键词在此网页中的词频。对新闻类网页，存在一组公共的关键词。因此，每个新闻网页都存在一组词频，称为该新闻网页的特征向量。
设两个新闻网页的特征向量分别为：甲(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的过程。
参考答案：
0 S+A(i)B(j) 或 等价表示 i＞m或i=m+1或 等价表示 j＞n或i=n+1 或 等价表示 i＞m or j＞n或i=m+1 or i=n+1 或等价表示
解析：
本题描述了如何计算两个新闻网页特征向量的内积。特征向量中的元素是关键词的词频，而向量是非零元素的序号及相应的词频值组成的简化形式。计算内积的过程需要遍历这两个简化特征向量，并计算对应序号相同时的元素乘积之和。
流程解析如下：
- 初始化S为0，作为内积的累计值。
- 对于每一个A(i)，需要与B(j)对应元素相乘并加到S上，直到NA(i)＜NB(j)，此时需要比较下一个A(i+1)与NB(j)，或者比较NA(i)与下一个B(j+1)。
- 如果在比较A(i+1)与NB(j)后，发现i+1已经越界（即i＞m或i=m+1），则扫描结束。
- 如果在比较NA(i)与B(j+1)后，发现j+1已经越界（即j＞n或j=n+1），则扫描结束。
- 当两个简化向量之一扫描结束时，整个扫描结束，即满足条件i＞m or j＞n 或 i=m+1 or i=n+1。
因此，答案中的填空部分应如上所述。
2、阅读以下说明和C函数，填补代码中的空缺，将解答填入答题纸的对应栏内。
[说明1]
函数isPrime(int n)的功能是判断n是否为素数。若是，则返回1，否则返回0。素数是只能被1和自己整除的正整数。例如，最小的5个素数是2，3，5，7，11。
[C函数]
int isPrime(int n)
{
int k, t;
if (n==2)
return 1;
if(n＜2 || ______)return 0; /*小于2的数或大于2的偶数不是素数//
t=(int)Sqrt(n)+1;
for(k=3; k＜t; k+=2)
if(______)
return 0;
return 1;
}[说明2]函数int minOne(int art[],int k)的功能是用递归方法求指定数组中前k个元素中的最小者，并作为函数值返回。
[C函数]
int minOne(int arr[],int k)
{
int t;
assert(k＞0);
if(k==1)
return ______;
t=minOne(arr+1,______);
if(arr[0]＜t)
return amr[0];
return ______;
}参考答案：
n%2==0，或!(n%2)，或其等价形式 n%k==0，或!(n%k)，或其等价形式 arr[0]，或*arr，或其等价形式 k-1，或其等价形式 t
解析：
对于isPrime函数：
- 判断一个数是否为素数，首先需要排除小于2的数以及大于2的偶数，因为偶数除了2以外都不是素数。因此，第一个空缺处是为了排除大于2的偶数，可以使用
n % 2 == 0或!(n % 2)来判断n是否为偶数。 - 对于大于2的奇数，我们需要检查它是否可被其他数整除。因此，第二个空缺处是为了检查n是否可被k整除，可以使用
n % k == 0或!(n % k)进行判断。这里的k是循环变量，从3开始递增到sqrt(n)。如果在这段范围内找到了一个因子，那么n就不是素数。
对于minOne函数：
- 使用递归方法求指定数组中前k个元素中的最小者。当k为1时，只有一个元素，这个元素就是最小的，所以空缺3处应填入
arr[0]或*arr或其等价形式。 - 在递归调用中，我们需要找的是数组中下一个元素到第k个元素中的最小值，所以第二个参数应该是k-1，表示元素个数为k-1个。因此空缺4处应填入
k-1或其等价形式。 - 最后，将递归返回的结果t与当前数组的第一个元素arr[0]比较，得到最小的值，所以空缺5处应填入
t。
3、阅读以下说明和C程序，填补代码中的空缺，将解答填入答题纸的对应栏内。
[说明]
函数areAnagrams(char *fstword,char *sndword)的功能是判断fstword和sndword中的单词(不区分大小写)是否互为变位词，若是则返回1，否则返回0。所谓变位词是指两个单词是由相同字母的不同排列得到的。例如，"triangle"与"integral"互为变位词，而"dumbest"与"stumble"不是。
函数areAnagrams的处理思路是检测两个单词是否包含相同的字母且每个字母出现的次数也相同。过程是先计算第一个单词(即fstword中的单词)中各字母的出现次数并记录在数组counter中，然后扫描第二个单词(即sndword中的单词)的各字母，若在第二个单词中遇到与第一个单词相同的字母，就将相应的计数变量值减1，若在第二个单词中发现第一个单词中不存在的字母，则可断定这两个单词不构成变位词。最后扫描用于计数的数组counter各元素，若两个单词互为变位词，则counter的所有元素值都为0。
函数areAnagrams中用到的部分标准库函数如下表所述。
[C函数]
int
areAnagrams(char *fstword, char *sndword)
{
int index;
int counter
[26]={0); /*counter[i]为英文字母表第i个字母出现的次数,
'A'或'a'为第0个,'B'或'b'为第1个,依此类推*/
if(______)
/*两个单词相同时不互为变位词*/
return 0;
while (*fstword){
/*计算第一个单词中各字母出现的次数*/
if
(isalpha(*fstword)){
if (isupper
(*fstword))
counter [*fstword
-'A']++;
else
counter
[*fstword-'a']++;
______;
/*下一个字符*/
}
}
while (*Sndword){
if (isalpha
(*sndword)) {
index=isupper
(*sndword)?* sndword -'A':*sndword-'a';
if(counter
[index])
counter [index]--;
elSe
______;
}
______;
/*下一个字符*/
}
for (index=0;index＜26; index++)
if(______)
return 0;
return 1;
}参考答案：
strcmp(fstword,sndword)=0，或其等价形式 fstword++，或其等价形式 return 0 sndwotd++，或其等价形式 counter [index]，或counter [index]!=0，或其等价形式
解析：
本题考查的是对C语言程序的理解与填空能力。根据题目描述和给出的代码片段，我们可以对每一个空进行逐一分析并填充。
空(1)：此处的目的是判断两个字符串是否相同，如果相同则它们不可能是变位词。因此，应使用strcmp函数来比较两个字符串，如果它们相等（即返回值为0），则不是变位词。所以空(1)应填写为：strcmp(fstword,sndword)=0或其等价形式。
空(2)：在第一个while循环中，我们需要逐个处理第一个单词中的字符。因此，我们需要将指针移动到下一个字符的位置，即使用fstword++或其等价形式。
空(3)：如果在处理第二个单词时，发现某个字符在第一个单词中没有出现，那么这两个单词不是变位词。此时应该直接返回0表示不是变位词。所以空(3)应填写为：return 0。
空(4)：与空(2)类似，在处理第二个单词时，我们需要将指针移动到下一个字符的位置，即使用sndword++或其等价形式。
空(5)：在最后的for循环中，我们需要检查counter数组中的每个元素是否都为0。如果某个元素的值不为0，那么这两个单词不是变位词。所以空(5)应填写为：counter[index]或counter[index]!=0或其等价形式。
4、阅读以下说明和C函数，填补代码中的空缺，将解答填入答题纸的对应栏内。
[说明]
函数ReverseList(LinkList headptr)的功能是将含有头结点的单链表就地逆置。处理思路是将链表中的指针逆转，即将原链表看成由两部分组成：已经完成逆置的部分和未完成逆置的部分，令s指向未逆置部分的第一个结点，并将该结点插入已完成部分的表头(头结点之后)，直到全部结点的指针域都修改完成为止。
例如，某单链表如图1所示，逆置过程中指针s的变化情况如图2所示。
链表结点类型定义如下：
typedef struct Node{
int data;
Struct Node *next;
}Node,*LinkList;
[C函数]
void ReverseList
(LinkList headptr)
{ //含头结点的单链表就地逆置,headptr为头指针
LinkList p,s;
if(______)
return; //空链表(仅有头结点)时无需处理
P=______;
//令P指向第一个元素结点
if(!P-＞next) return; //链表中仅有一个元素结点时无需处理
s=p-＞next; //s指向第二个元素结点
______ =NULL;
//设置第一个元素结点的指针域为空
while(s){
p=s;
//令p指向未处理链表的第一个结点
s= ______;
p-＞next=headptr-＞next; //将p所指结点插入已完成部分的表头
headptr-＞next= ______;
}
}
参考答案：
!headptr-＞next，或!headptr||!headptr-＞next，或其等价形式 headptr-＞next headptr-＞next-＞next，或p-＞next，或其等价形式 s-＞next，或p-＞next， 或其等价形式 p
解析：
本题考察的是对链表操作的掌握和理解。根据题目描述和提供的参考解析，我们可以逐一填补代码中的空缺。
- 空链表的判断：当链表为空时，头结点的指针域应该为空。因此第一个空处应填写条件判断语句来检查头结点的指针域是否为空，即"!headptr->next"，或者等价的形式如"headptr==NULL"。
- 令P指向第一个元素结点：根据注释，我们需要让P指向链表的第一个元素结点，所以第二个空处应填写"headptr->next"。
- 设置第一个元素结点的指针域为空：在将未逆置部分的第一个结点插入已完成部分的表头之前，我们需要先将第一个元素结点的指针域设置为空，避免链表断裂。因此第三个空处应填写"headptr->next->next"，或者等价的形式如"p->next"。
- s指向未逆置部分的下一个结点：在while循环中，我们需要让s指向未逆置部分的下一个结点，以便进行后续处理。所以第四个空处应填写"s->next"，或者等价的形式如"p->next"。
- 将P所指结点插入已完成部分的表头：这是逆置链表的关键步骤之一。我们需要将P所指结点插入已完成部分的表头（即头结点之后）。因此最后一个空处应填写"p"。
5、阅读下列说明、C++代码和运行结果，填补代码中的空缺，将解答填入答题纸的对应栏内。
[说明]
对部分乐器进行建模，其类图如下图所示，包括：乐器(Instrument)、管乐器(Wind)、打击乐器(Percussion)、弦乐器(Stringed)、木管乐器(Woodwind)、铜管乐器(Brass)。
类图
下面是实现上述设计的C++代码，其中音乐类(Music)使用各类乐器(Instrument)进行演奏和调音等操作。
using namespace std;
enum Note(/*枚举各种音调*/
MIDDLE_C,C_SHARP,B_FLAT
};
class
Instrument{/*抽象基类,乐器*/
public:
______;
//play函数接口
virtual void
adjust()=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;)
};
class
Woodwind:public Wind{
public:
void play(Note n)
{ cout＜＜"Woodwind.play()"＜＜n＜＜endl; }
};
class MusiC {
public:
void
tune(Instrument*i) { i-＞play(MIDDLE_C.; }
void
adjust(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++)
delete
orchestra[i];
delete music;
}
本程序运行后的输出结果为：
Wind.play()0 Wind.adjust() Woodwind.play()0 Wind.adjust()
参考答案：
virtual void play(Noten)=0 :public Instrument :public Wind Instrument* new
解析：
根据题目描述和给出的代码片段，我们可以按照以下步骤进行解析和填补空白：
- 在
Instrument类中，我们需要定义两个纯虚函数play和adjust，表示乐器的基本行为。因此，第一个空应填写为：virtual void play(Note n)=0;。 Wind类是Instrument的子类，所以应该继承自Instrument类。因此，第二个空填写为：: public Instrument。- 同样地，由于题目中的类图显示
Woodwind是Wind的子类，所以第三个空应填写为：: public Wind。 - 在
Music类的成员函数tuneAll中，我们需要遍历一个乐器数组并为每个乐器进行定调操作。由于乐器数组的元素类型为乐器指针，所以第四个空应填写为：Instrument*。 - 在主函数
main中创建Music类的对象时，需要使用关键字new来动态分配内存。因此，第五个空应填写为：new Music()。
6、阅读以下说明和Java程序，填补代码中的空缺，将解答填入答题纸的对应栏内。
[说明]
对部分乐器进行建模，其类图如下图所示，包括：乐器(Instrument)、管乐器(Wind)、打击乐器(Percussion)、弦乐器(Stringed)、木管乐器(Woodwind)、铜管乐器(Brass)。
类图
下面是实现上述设计的Java代码，其中音乐类(Music)使用各类乐器(Instrument)进行演奏和调音等操作。
[Java代码]
enum Note{/*枚举各种音调*/
MIDDLE_C,C_SHARP,B_FLAT;
//其他略
}
interface
Instrument {/*接口,乐器*/
______;
//play方法接口
void adjust();
//adjust方法接口
}
class Wind ______
{
public void
play(Note n) { System.out.println("Wind.play()"+n); }
public void adjust()
{System.out.println("Wind.adjust()");}
}
/*类Percussion和Stringed实现代码略*/
class Brass ______
{
public void
play(Note n) {System.out.println("Brass.play()"+n); }
public void
adjust(){System.out.println("BrasS.adjust()");)
}
Class Woodwind
extends Wind{
publicvoidplay(Note n)
{System.out.println("Woodwind.play()"+n); }
}
public class
Music{
void
tune(Instrument_i){i.play(Note.MIDDLE_C.; }
void
adjust(Instrument i){i.adjust(); }
void
tuneAll(______ e){
for(Instrument
i:e){
adjust(i);
tune(i);
}
}
public Static void
main(String[] args){
Music music=
______ Music();
Instrument[]
orchestra={new Wind(), new Woodwind() };
music.tuneAll(orchestra);
}
}本程序运行后的输出结果为：
Wind.adjust() Wind.play() MIDDLE_C Wind.adjust() Woodwind.play()MIDDLE_C
参考答案：
voidplay (Note n) implements Instrument extends Wind Instrument[] new
解析：
本题考察的是Java语言的基础知识和面向对象编程的概念。
1.
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
