【程序说明】
本程序先从文件读人各考生的准考证号(设为整型数)及成绩，并将其存放在一棵检索二叉树上，二叉树结点的健值是成绩，每个结点带一链表，链表结点存放取得该成绩的考生的准考证号。然后，程序按中序遍历检索二叉树，从高分到低分输出结果，使每行输出成绩及其取得成绩的考生的准考证号。
【程序】
#include ＜ stdio. h ＞
typedef struet idnode
int id;
struct idnode * next;
ldNode;
typedef struct marknode I
int mark;
ldNode * head;
struct marknode * left, * right;
MarkNode;
char fname [ ] = "sp07.dat";
main( )
int id, mark;
MarkNode * root = null;
FILE * fp = fopen(fname," r" );
if(!fp)
printf("file%s open error, \n" , fname);
exit(0);

while (!feop(fp))
fscanf(fp," %d%d", &id, &mark);
btree(&root, id, mark);

fclose(fp);
print(root);
btree(MarkNod * * mpptr, int id, int mark)
ldNode * ip;
MarkNode *mp = * mpptr;
if (1)
if (mark==p-＞mark) addldNODE ( (2) , id);
else if ( mark ＞mp -＞ mark) btree (&top -＞ left, id, mark);
else btree(&mp-＞ right, id, mark);
else
Imp = ( marknode * ) malloc(sizeo (marknode) );
mp -＞ mark = mark;
mp -＞ left =mp -＞ right = NULL;
(3)
addldNode(&mp -＞ head, id);
(4) ;

addldNode(ldNode * * ipp, int id)
ldNode * ip = * ipp;
if ( (5) )addldNode ( (6) ), id;
else
ip = (ldNode * )malloc(sizeof(ldNode) );
sp - ＞ id = id;
ip -＞ next = NULL;
(7)

print(MarkNode * rap)
ldNode *ip, *ip0;
if (mp)
print ( mp -＞ left);
printf(" %6d: \t" ,mp -＞ mark);
ip = mp -＞ head;
while(ip)
printf(" %6d" ,ip -＞ id);
ip0 =ip;
ip = ip -＞ next;
free (ip0);

printf(" \n" ); printf( mp -＞ right); free(mp);

问答题【问题1】 请将【算法2-1】和【算法2-2】中(1)～(7)处补充完整。

问答题【说明】 本题将有向网(带权有向图)定义为类Adjacency WDigraph。类中的数据成员n表示有向网中的顶点数；a为带权邻接矩阵，用于存储有向网中每一对顶点间弧上的权值；c为二维数组，存储有向网中每一对顶点间的最短路径长度；kay为二维数组，存储最短路径，kay[i][j]=k表示顶点i到达顶点j的最短路径必须经过顶点k。类中的主要成员函数有： Input()：输入有向网的顶点数、各条弧及权值，建立带权领接矩阵a。若顶点i到顶点j有弧，则a[i][j]取弧上的权值，否则a[i][j]的值取NoEdge。 AllPairs()；用弗洛伊德(Floyd)算法求有向网中每一对顶点间的最短路径长度。 OutShortestPath (int i, int j：计算顶点i到顶点j的最短路径。 outputPath(int i, int j)：输出顶点i到顶点j的最短路径上的顶点。 Floyd算法的基本思想是递推地产生一个矩阵序列C0，C1，C2，…，Cn，其中C0是已知的带权邻接矩阵，a，Ck(i, j(0≤i，j＜)表示从顶点i到顶点j的中间顶点序号不大于k的最短路径长度。如果i到j的路径没有中间顶点，则对于0≤k＜n，有Ck(i,j)=C0(i,j)= a[i][j]。递推地产生C1，C2，…，Cn的过程就是逐步将可能是最短路径上的顶点作为路径上的中间顶点进行试探，直到为全部路径都找遍了所有可能成为最短路径上的中间顶点，所有的最短路径也就全部求出，算法就此结束。 【C++代码】#include ＜ iostream. h ＞#define NoEdge 10000 当两个顶点之间没有边相连时，在邻接矩阵中用NoEdge表示void Make2DArray(int * * &x, int rows, int cols);class AdjacencyWDigraph private int n; 有向网中的顶点数目 int* *a; 存储顶点间弧上的权值 int* *c; 存储计算出的最短路径长度 int* * kay; 存储求出的最短路径pubic: int Vertices( )const j return n; void AllPairs( ); void Input( ); 输入有向网的顶点数、各条弧及权值，建立邻接矩阵a void OutShortestPath(int i, int j); 计算顶点i到j的最短路径(试卷中未列出) ~ AdjacencyWDigraph ( ); 析构函数(试卷中未列出)private: void outputPath(int i, int j);;void AdjacencyWDigraph: :AllPairs( ) int i,j,k,t1,t2,t3; for(i=1;i＜=n; k++) for(j=1;j＜=n; ++j) c[i][j]= (1) ; kay[i][j]=0; for(k=1;k＜=n; k++) for(i=1;i＜=n; i++) if(i= =k) continue; t1=c[i][k]; for(j=1;j＜=n; j++) if(j==k||j==i) continue; t2 =c[k] [j]; t3 =c[i] [j]; if( t1 ! = NoEdge && t2! = NoEdge &&(t3==NoEdge || t1+t2＜t3) ) c[i][j]= (2) ;kay[i][j]= (3) ; for forvoid AdjacencyWDigraph:: outputPath(int i, int j) 输出顶点i到j的最短路径上的顶点 if(i==j) return; if(kay[i] [j]==0)cout＜＜j ＜＜ ; else outputPath(i, (4) ); outputPath( (5) );void Adjacency WDigraph: :lnput( )int i,j,u,v,w,E; cout ＜＜ 输入网中顶点个数: ;cin＞ ＞n; cout ＜＜ 输入网中弧的个数: ; cin＞ ＞E; Make2DArray (a, n+1, n+1); for(i=1;i＜=n; i++) for(j=1; j＜=n; j++) a[i][j]=NoEdge; for(i=1;i＜ =n; i++) a[i][i]=0; Make2DArray(c, n+1, n+1); Make2DArray(kay, n+1, n+1) for(i=1;i＜=E; i++)cout＜＜ 输入弧的信息(起点终点权值); ; cin＞ ＞u＞ ＞v＞ ＞w; a[u][v] =w;void Make2DArray(int * * &x, int rows, int cols) int i,j; x=new int* [rows+1]; for(i=0;i＜rows+1;i ++ ) x[i]=new int [cols+1]; for(i=1;i＜= rows; i ++) for(j=1;j＜=cols; j++) x[i][j]=0;

问答题【问题1】 在UML中，用例代表一个完整的功能，如与角色通信、进行计算或在系统内工作等。请简要说明用例具有哪些的特征，并指出用例图中(1)～(3)处表示的内容。