一、问答题
1、阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。
[说明]
本流程图旨在统计一本电子书中各个关键词出现的次数。假设已经对该书从头到尾依次分离出各个关键词{A(i)|i=1,…,n}(n＞1)}，其中包含了很多重复项，经下面的流程处理后，从中挑选出所有不同的关键词共m个{K(j)|j=1,…,m}，而每个关键词K(j)出现的次数为NK(j),j=1,…,m。
[流程图]
参考答案：
1 K(j) NK(j)+1→NK(i) 或NK(j)++ 或等价表示 m+1→m或m++ 或等价表示 A(i)
2、阅读以下说明和C函数，填补代码中的空缺，将解答填入答题纸的对应栏内。
[说明]
函数removeDuplicates(chai *str)的功能是移除给定字符串中的重复字符，使每种字符仅保留一个，其方法是：对原字符串逐个字符进行扫描，遇到重复出现的字符时，设置标志，并将其后的非重复字符前移。例如，若str指向的字符串为"aaabbbbscbsss"，则函数运行后该字符串为"absc"。
[C代码]
void
removeDuplicates(char *str)
{
int
i,len=strlen(str); /*求字符串长度*/
if(______)return;
/*空串或长度为1的字符串无需处理*/
for(i=0;i＜len;i++){
int flag=0;
/*字符是否重复标志*/
int m;
for(m=______; m＜len;m++){
if(Str[i]==str[m]){
______;
break;
}
}
if (flag) {
int n,idx=m;
/*将字符串第idx字符之后、与str[i]不同的字符向前移*/
for(n=idx+1; n＜len; n++)
if(Str[n]!=str[i]){
str[idx]=str[n];
______;
}
str[______]='\0';
/*设置字符串结束标志*/
}
}
}参考答案：
len＜2 或len＜=1 或等价表示 i+1 或等价表示 flag=1 或给flag赋值为任何一个不是0的值 idx++ 或idx=idx+1 或等价表示 idx 或等价表示
3、阅读以下说明和C函数，填补函数代码中的空缺，将解答填入答题纸的对应栏内。
[说明]
队列是一种常用的数据结构，其特点是先入先出，即元素的插入在表头、删除在表尾进行。下面采用顺序存储方式实现队列，即利用一组地址连续的存储单元存放队列元素，同时通过模运算将存储空间看作一个环状结构(称为循环队列)。
设循环队列的存储空间容量为MAXQSIZE，并在其类型定义中设置base、rear和length三个域变量，其中，base为队列空间的首地址，rear为队尾元素的指针，length表示队列的长度。
#define MAXQSIZE 100
typedef
struct {
QElemType *base;
/*循环队列的存储空间首地址*/
int
rear; /*队尾元素索引*/
int length;
/*队列的长度*/
}SqQueue;例如，容量为8的循环队列如下图所示，初始时创建的空队列如下图(a)所示，经过一系列的入队、出队操作后，队列的状态如下图(b)所示(队列长度为3)。
下面的C函数1、C函数2和c函数3用于实现队列的创建、插入和删除操作，请完善这些代码。
[C函数1]创建一个空的循环队列。
[C函数1]创建一个空的循环队列。
int
InitQueue(SqQueue *Q)
/*创建容量为MAXQSIZE的空队列,若成功则返回1;否则返回0*/
{ Q-＞base=(QElemType *)malloc(MAXQSIZE* ______};
if (!Q-＞baSe)return 0;
Q-＞length=0;
Q-＞rear=0;
return 1;
}/*InitQueue*/
[＜strong＞[C函数2]＜/strong＞]元素插入循环队列。
int
EnQueue(SqQueue *Q,QElemType e) /*元素e入队,若成功则返回1;否则返回0*/
{
if(Q-＞length＞=MAXQSIZE.return 0;
Q-＞rear= ______;
Q-＞base[Q-＞rear]=e;
______;
return 1;
}/*EnQueue*/
[C函数3]元素出循环队列。
int
DeQueue(SqQueue *Q,QElemType *e)
/*若队列不空,则删除队头元素,由参数e带回其值并返回1;否则返回0*/
{
if(______)return 0;
*e=Q-＞base[(Q-＞rear-Q-＞length+1+MAXQSIZE.%MAXQSIZE.;
______;
return 1;
}/*DeQueue*/
参考答案：
sizeof(QElemType) (e-＞rear+1)%MAXQSIZE或等价表示 Q-＞length++ 或Q-＞length=Q-＞length+1或等价表示 Q-＞length＜=0 或Q-＞length==0或等价表示 e-＞length-- 或Q-＞length=Q-＞length-1或等价表示
4、阅读以下说明和C函数，填补代码中的空缺，将解答填入答题纸的对应栏内。
[说明]
二叉树的宽度定义为含有结点数最多的那一层上的结点数。函数GetWidth()用于求二叉树的宽度。其思路是根据树的高度设置一个数组counter[]，counterl[i]存放第i层上的结点数，并按照层次顺序来遍历二叉树中的结点，在此过程中可获得每个结点的层次值，最后从counter[]中取出最大的元素就是树的宽度。
按照层次顺序遍历二叉树的实现方法是借助一个队列，按访问结点的先后顺序来记录结点，离根结点越近的结点越先进入队列，具体处理过程为：先令根结点及其层次号(为1)进入初始为空的队列，然后在队列非空的情况下，取出队头所指示的结点及其层次号，然后将该结点的左子树根结点及层次号入队列(若左子树存在)，其次将该结点的右子树根结点及层次号入队列(若右子树存在)，然后再取队头，重复该过程直至完成遍历。
设二叉树采用二叉链表存储，结点类型定义如下：
typedef struct BTNode {
TElemType data;
struct BTNode
*left,*right;队列元素的类型定义如下：
typedef struct {
BTNode *ptr;
int LevelNumber;
)QElemType;GetWidth()函数中用到的函数原型如下所述，队列的类型名为QUEUE：
[C函数]
int
GetWidth(BiTree root)
{
QUEUE Q;
QElemType a,
b;
int
width,height=GetHeight(root);
int
i,*counter=(int*)calloc(height+1,sizeof(int));
if (______)
return-1; /*申请空间失败*/
if(!root)
return 0; /*空树的宽度为0*/
if(______)
return-1; /*初始化队列失败时返回*/
a.ptr=root;
a.LeveiNumber=1;
if(!EnQueue(&Q,a))return-1; /*元素入队列操作失败时返回*/
while(!isEmpty(Q)){
if(______)return-1; /*出队列操作失败时返回*/
counter[b.LevelNumber]++; /*对层号为b.LevelNumber的结点计数*/
if(b.ptr-＞left) { /*若左孔树存在,则左孔树根结点及其层次号入队*/
a.ptr=b.ptr-＞left;
a.LevelNumber=
______;
if (
!EnQueue(&Q,a))return-1;
}
if (bptr-＞right) {/*若右孔树存在,则右孔树根结点及其层次号入队*/
a.ptr=b.ptr-＞right;
a.LevelNumber=______;
if(!EnQueue(&Q,a))return-1;
}
}
width=counter[1];
for(i=1;i＜height+1;i++) /*求counter[]中的最大值*/
if(______)
width=counter[i];
free(counter);
return width;
}
参考答案：
!counter 或0==counter 或NULL==counte r或等价表示 !InitQueue(&Q) 或0==InitQueue(&Q) 或等价表示 !DeQueue(&Q,&b)或0==DeQueue(&Q,&b) 或等价表示 b.LevelNumber+1 或等价表示 b.LevelNumber+1 或等价表示 counter[i]＞width 或等价表示
5、阅读下列说明、C++代码和运行结果，填补代码中的空缺，将解答填入答题纸的对应栏内。
[说明]
很多依托扑克牌进行的游戏都要先洗牌。下面的C++程序运行时先生成一副扑克牌，洗牌后再按顺序打印每张牌的点数和花色。
[C++代码]
#include＜iostream＞
#include＜stdlib.h＞
#include＜ctime＞
#include＜algorithm＞
#include＜string＞
USing namespace
std;
const string
Rank[13]={"A","2","3","4","5","6","7","8","9","10","J",
"Q","K"}; //扑克牌点数
const strinq
Suits[4]={"SPADES","HEARTS","DIAMONDS","CLUBS");
//扑克牌花色
Class Card{
private:
int rank;
int suit;
public:
Card(){}
～Card(){}
Card(int rank,int
suit) {______ rank=rank;______ suit=suit;}
int getRank(){
return rank;
}
int getSuit(){
return suit;
}
void printCard(){
cout＜＜ '('＜＜Rank[rank]＜＜",
"＜＜Suits[suit]＜＜")":
}
};
Class
DeckofCards{
private:
Card deck[52];
public:
DeckOfCards(){
//初始化牌桌并进行洗牌
for(int i=0; i＜52;i++) { //用Card对象填充牌桌
______
=card(i%13,i%4);
}
Srand((unsigned)time(0)); //设置随机数种孔
std::random
shuffle(&deck[0],&deck[51]); //洗牌
}
～DeckOfCards() {
}
void printCards()
{
for(int i=0; i＜52; i++){
______
printCard();
if((i+1)%
4==0)cout＜＜endl;
else cout＜＜"\t";
}
}
};
int main (){
DeckOfCards
*d= ______; //生成一个牌桌
______;
//打印一副扑克牌中每张牌的点数和花色
delete d:
return 0;
}参考答案：
this-＞ this-＞ deck[i] 或*(deck+i) 或等价表示 deck[i]. 或*(deck+i).或等价表示 new DeckOfCards() d-＞printCards() 或等价表示
6、阅读以下说明和Java程序，填补代码中的空缺，将解答填入答题纸的对应栏内。
[说明]
很多依托扑克牌进行的游戏都要先洗牌。下面的Java代码运行时先生成一副扑克牌，洗牌后再按顺序打印每张牌的点数和花色。
[Java代码]
import
java.util.List;
import
java.util.Arrays;
import
java.util.Collections;
class Card { //扑克牌类
public static enum
Face { Ace, Deuce, Three, Four, Five, Six,
Seven,
Eight, Nine, Ten, Jack, Queen, King };
//枚举牌点
public static enum
Suit { Clubs, Diamonds, Hearts, Spades }; //枚举花色
private final Face
face;
private final Suit
suit;
public Card( Face
face, Suit suit ) {
______ face =
face;
______ suit =
suit;
}
public Face
getFace() { return face; }
public Suit
getSuit() { return suit; }
public String
getCard() { //返回String来表示一张牌
return
String.format( "%s, %s", face, suit);
}
}
//牌桌类
class DeckOfCards
{
private List＜ Card ＞ list; //声明List以存储牌
public DeckOfCards
() { //初始化牌桌并进行洗牌
Card[] deck
= new Card[ 52 ];
int count = 0;
//牌数
//用Card对象填充牌桌
for ( Card.
Suit suit : Card. Suit.values() ) {
for ( Card.
Face face : Card. Face. values() ) {
______ = new Card(
face, suit );
}
}
list =
Arrays.asList( deck );
Collections.
shuffle( list ); //洗牌
}
public void
printCards()
{
//按4列显示52张牌
for ( int i = 0; i
＜ list.size(); i++ )
System.out.printf(
"%-19s%s", list. ______,
( ( i+1 ) % 4 == 0
) ? "\n );
}
}
public class
Dealer {
public static void
main( String[] args ) {
DeckOfCards player
= ______;
______ printCards
();
}
}参考答案：
this. this. deck[count++] 或等价表示 get(i).getCard() new DeckOfCards() player.
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
