请仔细阅读以下关于某传输系统的技术说明、状态转换图及Java程序，根据要求回答问题1～问题2。 [说明

还应有哪些外部实体和数据存储?

阅读下列说明和算法，回答问题1和问题2。

【说明】

算法5-1用来检查文本文件中的圆括号是否匹配。若文件中存在圆括号没有对应的左括号或者右括号，则给出相应的提示信息，如表5-1所示。

在算法5-1中，stack为一整数栈。算法中各函数的说明如表5-2所示。

【算法5-1】

将栈stack置空，置EOF为false

ch←nextch();

while(not EOF)

k←kind(ch);

ifk== (1) )

push( (2) ;push( (3) ;

else if(k== (4) )

if(not empty())

pop();pop();

else

显示错误信息(缺少对应左括号或右括号);

显示行号row；显示列号col;

endif

endif

ch←nextch();

endwhile

if(not empty())

显示错误信息(缺少对应左括号或右括号);

while(not empty())

row←pop();col←pop();

显示行号row; 显示列号col;

endwhile

endif

为了识别更多种类的括号，对算法5-1加以改进后得到算法5-2。算法5-2能够识别圆括号、方括号和花括号(不同类型的括号不能互相匹配)。改进后，函数kind(charch)的参数及其对应的返回值如表5-3所示。

【算法5-2】

将栈stack置空, 置EOF为false

ch←nextch();

while(not EOF)

k←kind(ch);

if(k＞0)

if(判断条件 1)

push( (5) ); push( (6) ); push( (7) );

else if(判断条件2 and 判断条件3)

pop(); pop(); pop();

else

显示错误信息(缺少对应左括号或右括号);

显示行号row: 显示列号col;

endif

endif

ch←nextch();

endwhile

if(not empty())

显示错误信息(缺少对应左括号或右括号);

while(not empty())

pop(); row←pop(); col←pop();

显示行号row; 显示列号col;

endwhile

endif

请将【算法5-1】和【算法5-2】中(1)至(7)处补充完整。

阅读下列程序说明和C代码，将应填入(n)处的字句写在对应栏内。

【说明】

设某城市有n个车站，并有m条公交线路连接这些车站，设这些公交车都是单向的，这n个车站被顺序编号为0至n-1。输入该城市的公交线路数、车站个数，以及各公交线路上的各站编号，求得从站0出发乘公交车至站n-1的最少换车次数。

程序利用输入信息构建一张有向图G(用邻接矩阵g表示)，有向图的顶点是车站，若有某条公交线路经i站能到达j站，就在顶点i到顶点j之间设置一条权为1的有向边＜i,j＞。如是这样，从站点x至站点y的最少上车次数便对应图G中从点x至点y的最短路径长度。而程序要求的换车次数就是上车次数减1。

【函数5-9】

include ＜stdio.h＞

define M 20

define N 50

int a[N+1]; /*用于存放一条线路上的各站编号*/

iht g[N][N]; /*存储对应的邻接矩阵*/

int dist[N]; /*存储站0到各站的最短路径*/

int m,n;

void buildG()

{

int i,j,k,sc,dd;

printf ("输入公交线路数，公交站数\n");

scanf("%d%d", &m, &n);

for(i=0; i＜n; i++) /*邻接矩阵清0*/

for(j = 0; j ＜ n; j++)g[i][j] = 0;

for(i=0; i＜m; i++){

printf("沿第%d条公交车线路前进方向的各站编号(O＜=编号＜=%d,-1结束):\n",

i+1, n-1);

sc=0;/* 当前线路站计数器 */

while(1){

scanf("%d",&dd);

if(dd==-1)break;

if(dd＞=0 && dd＜n) (1);

}

a[sc]=-1;

for(k=1;a[k]＞=0; k++) /* 处理第i+1条公交线路 */

for(j=0; j＜k; j++)

g(2)=1;

}

}

int minLen()

{

int j, k;

for(j=0;j＜n;j++)dist[j]=g[0][j];

dist[0]=1;

do{

for(k=-1,j=0;j＜n;j++) /* 找下一个最少上车次数的站*/

if(dist[j]＞0&&(k==-1 || dist[j]＜dist[k]))k=j;

if (k＜0 || k==n-1) break;

dist[k]=-dist[k]; /* 设置k站已求得上车次数的标记 */

for(j=1;j＜n;j++) /* 调整经过k站能到达的其余各站的上车次数 */

if ((3) && (dist[j]==0 || -dist[k]+1＜dist[j]))

dist[j]=(4);

}while(1);

j=dist[n-1];

return (5);

}

void main()

{

int t；

buildG();

if((t=minLen()＜0)printf("无解!\n");

else pdnff("从0号站到%d站需换车%d次\n”，n-1，t)；

}

【问题3】（3分）

考虑实例n= 10，C= 10，各个货物的体积为{4，2，7，3，5，4，2，3，6，2}。该实例在最先适宜和最优适宜策略下所需的集装箱数分别为(9)和(10)。考虑一般的情况，这两种求解策略能否确保得到最优解？(11) （能或否）

【问题2】（4分） 使用说明中的词语，给出图1.2中的数据存储D1～D4的名称。

阅读以下函数说明和C代码，回答问题

[说明]

任何一种程序都是为了解决问题而撰写的，解决问题时需要实现一些特定的运算法则。在策略(Strategy)模式下，可以更换实现算法的部分而不留痕迹，切换整个算法，简化改为采用其他方法来解决同样问题。

以下是一个“剪刀石头布”游戏。猜拳时的“策略”有2种方法：第一种是“猜赢后继续出同样的招式”(WinningStrategy)，第二种是“从上一次出的招式种，以概率分配方式求出下一个招式的几率”(ProbStrategy)。程序中定义了Hand类表示猜拳时的“手势”，类内部以0(石头)、1(剪刀)、2(布)来表示。Hand类的实例只会产生3个。

以下是C语言实现，省略了不相关属性及方法，方法实现体亦有所省略，能够正确编译通过。

[C代码]

typedef (1) (*funl)();

enum HandValue{HANDVALUE_GUU=0, HANDVALUE_CHO=1, HANDVALUE_PAA=2};

//手势可取值，依次为“石头”、“剪刀”、“布”

//其大小顺序是循环相克的，即：石头赢剪刀，剪刀赢布，布赢石头

bool won;

struct Hand *WSprevHand;

struct Hand{//手势

enum HandValue handvalue;

}hand[3]={HANDVALUE_GUU, HANDVALUE_CHO, HANDVALUE_PAA};

int fight(struct Hand *h1, struct Hand *h2)

//比较h1和h2。h1代表的手势较大时返回1，h1较小时返回-1，相等时返回0

//

{

if(h1->handvalue == h2->handvalue){

return 0;

}else if((h1->handvalue+1)% (2) == h2>handvalue){

return 1;

}else{

return -1;

}

}

struct Hand* getHand(int handvalue){

//依据手势代表的值取得手势，若handvalue不合法，返回NULL

switch(handvalue){

case 0:

return &hand[0];

break;

case 1:

return &hand[1];

bteak;

case 2;

return &hand[2];

break;

}

return (3) ;

}

struct Strategy{//策略

funl nextHand;//下一个手势

};

struct Hand* WSnextHand()

{

if(!won){

PSprevHand = getHand(rand()%3);

}

return PSprevHand;

}

struct Player{

char name[20];

(4) strategy;//策略

int wincount;

int losecount;

int gamecount;

};

void main()

{

Strategy WS;

WS.nextHand = WSnextHand;

WSpreVHand = NULL;

struct Player WSplayer;

(5)(WSplayer.name,"ww");

WSplayer.wincount = 0;

WSplayer.losecount = 0;

WSplayer.gamecount = 0;

WSplayer.strategy = &WS;

}

阅读下列函数说明、图和C代码，回答问题

[说明]

在进行文法分析的时候，通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度，通常都要画出与单词列表所对应的单词查找树。

程序构造一棵二叉排序树，每个节点存储一个单词，按字典序列，较小的在左子树，较大的在右子树。

函数中使用的预定义符号如下：

typedef struct TreeNode{/*二叉排序树节点*/

char *word;

struct TreeNode *left, *right;

}BNODE;

[函数]

int getWord(FILE *fpt, char *word)

/*从文件fpt中读取单词到word中，到达文件结束时返回0*/

{

char c;

c = fgetc(fpt);

if(c == EOF)return 0;

/*跳过单词间的非字母字符*/

while(!(tolower(c) >= 'a' && tolower(c) <= 'z')){

c = fgetc(fpt);

if(c == EOF)return 0;

}

/*不区分大小写*/

while(tolower(c) >= 'a' && tolower(c) <= 'z'){

*word++ = c;

c = fqetc(fpt);

}

*word = '\0';

return 1;

}

void BTree(BNODE **t, char *word)

{

BNODE *ptr, *p;

int compres;

p = NITLL;

(1) ;

while(ptr){

compres = strcmp(word, (2) );

if(!compres){

return;

}else{

(3) ;

ptr = compres > 0 ? ptr->right : ptr->left;

}

}

ptr = (BNODE*)malloc(sizeof ptr);

ptr->left = ptr->right = NULL;

ptr->word = (char*)malloc(strlen(word) + 1);

strcpy(ptr->word, word);

if(p == NULL){

(4) ;

}else if(compres > 0){

p->right = ptr;

}else{

p->left = ptr;

}

}

int main()

{

FILE *fpt;

char word[40];

BNODE *root = NULL;

if((fpt = fopen("text.in", "r")) == NULL){

printf("不能打开文件text.in! \n");

return 1;

}

while(getWord(fpt, word) == 1){

BTree (5) ;

}

fclose(fpt);

return 0;

}