【说明】数据排序。将给定的n个整数分别按照升序和降序进行排列。class SortInt

问答题【说明】构造最优二叉查找树。具有n个结点的有序序列a1, a2, …, an存在于数组元素a[1]、a[2], …, a[n]之中, a[0]未被使用。结点a1, a2, …, an-1, an的查找成功的概率p1, p2, …, pn-1, pn存在于数组元素 p[1]、p[2], …, p[n—1]、p[n]之中, p[0]未用。另外, 查找失败的概率q0, q1, …, qn-1, qn存在于数组元素q[0]、p[1], …, q[n-1]、q[n]之中。算法计算的序列ai+1, ai+2,…, aj-1, aj的最优二叉查找树Tij的代价Cij存在于数组元素c[i][j]之中, Tij的根结点的序号rij存在于r[i][j]之中, 它的权值存在于w[i][j]之中。为了便于内存的动态分配, 统统使用一维数组取代二维数组。 const float MAXNUM=99999. 0; 尽可能大的浮点数 template＜ (1) ＞ void OPtimal_Binary_Search_Tree(float p[], float q[], Type a[], int n) { float *C, *W; c= (2) ; w= (3) ; int *r; r=new int[(n+1)*(n+1)]; for(i=0; i＜=n; i++) { c[i*(n+1)+i]=0. 0; 即：c[i][i]=0.0, 用一维数组表示 w[i*(n+1)+i]=q[i]; 即：w[i][i]=q[i], 用一维数组表示 } int i, j, k, m, length; m表示根结点的下标或序号, 范围为0～n float minimum; for(length=1; length＜=n; length++) 处理的序列长度由1到n for(i=0; i＜=n-length; i++){ i为二叉查找树Tij的起始序号 j=i + length; j为二叉查找树Tij的终止序号。如：处理序列a1a2a3时, 相应的二叉查找树为T03, i=0, 而j=3 w[i*(n+1)+j]= (4) ; minimum =MAXMUM; for(k=i+1; k＜=j; k++) 考察以ai+1、ai+2, …, ai为根的情况 if( (5) ＜minimum) { minimum=c[i*(n+1)+k-1]+c[k*(n+1)+j];m=k; } c[i*(n+1)+j]=w[i*(n+1)+j]+c[i*(n+1)+m-1]+c[m*(n+1)+j]; r[i*(n+1)+j]=m; r[i][j]=m } } 构造好的最优二叉查找树的根结点的序号在r[0][n]中

问答题【说明】用克鲁斯卡尔算法求解给定图的最小生成树。#include ＜stdio. h＞#include ＜stdlib. h＞#define MAXN 30typedef struct{ int v1,v2; *一条边依附的两个顶点* int weight; *边上的权值* }EDGE; typedef struct{ int Vnum; *图中的顶点数目* EDGE e[MAXN*(MAXN-1) 2]; *图中的边* }Graph; typedef struct node{ *用链表存储同一个连通分量的顶点* int v; struct node *next; }Alist; void heapadjust(EDGE data[], int s, int m){ *将元素序列data[s..m]调整为小顶堆, 堆顶元素(最小元素)为data[s]* int j; EDGE t; t=data[s]; *备份元素data[s], 为其找到适当位置后再插入* for(j=2*s+1; j＜=m; j=j*2+1){ *沿值较小的子结点向下筛选* if(j＜m && (1) ) ++j; if(!(t. weight＞data[j]. weight)) break; data[s]=data[j];s=j; *用s记录待插入元素的位置(下标)* } *for* data[s]=t; *将备份元素插入由s所指出的插入位置* } *heapadjust* int creat_graph(Graph *p) *输入图中的顶点及边, 返回图中边的数目* { int k=0; *记录图中边的数目* int n; int v1,v2; int w; printf( vertex number of the graph: ); scanf( %d , &n); *输入图中的顶点数目* if(n＜1) return 0; p-＞Vnum=n; do{ printf( edge(vertex1,vertex2,weight): ); scanf( %d %d %d , &V1, &v2, &w); if(v1＞=0 && v1＜n && v2＞=0 && v2＜n){p-＞e[k]. v1=v1; p-＞e[k]. v2=v2; p-＞e[k]. weight=w; k++; } *if* }while(!( (2) )); return k; *返回图中边的数目* } *creat_graph* int kruskal(Graph G, int enumber, int tree[][3]){ *用kruskal算法求无向连通图G的最小生成树, 图中边所得数目为enumber, * *数组tree[][3]中存放生成树中边的顶点和边上的权值, 函数返回生成树的代价* int i, k, m, c=0; int v1, v2; Alist *p, *q, *a[MAXN]; for(i=0; i＜G．Vnum; ++i){ *将每个连通分量中的顶点存放在一个单链表中* a[i]=(Alist*)malloc(sizeof(Alist)); if(!a[i]) {printf( n mernory allocation error! ); exit(0); } *if* a[i]-＞v=i; a[i]-＞next=NULL; } *for* for(i=enumber-1; i＞=0; --i) *按照边上的权值建立小顶堆* heapadjust( (3) ); k=G. Vnum; *k用于计算图中的连通分量数目* m=enumber-1; i=0; do{v1=G. e[0]. v1; v2=G. e[0]. v2; p=a[v1]; while(p && p-＞v!=v2){ *判断当前选择的边的顶点是否在一个连通分量中* q=p; p=p-＞next; }if(!p){ *当前边的顶点不在一个连通分量中* p=q; p-＞next=a[G. e[0]. v2]; p=a[G. e[0]. v1); *加入边(v1,v2), 将两个连通分量合并为一个* while(p){a[p-＞v]= (4) ; p=p-＞next; }k--; *连通分量数目减少一个* tree[i][0]=v1; *记录加入最小生成树的边* tree[i][1]=v2; tree[i][2]=G. e[0]. weight; c+=G. e[0]. weight; ++i; } *if* G. e[0]=G. e[m]; m--; heapadjust ( (5) );} while(k＞1); *当所有顶点不在同一个连通时, 继续* return c; *返回最小生成树的代价* } *kruskal* void main(void){ int i, enumber; int tree[MAXN][3]; int cost=0; Graph G; enumber=creat_graph(&G); cost=-kruskal(G,enumber,tree); printf( Minimum-Cost spanning tree(kruskal)： n ); printf( edge t weight t n ); for(i=0; i＜G. Vnum-1; ++i)printf( v %d –v %d t %d n , tree[i][0], tree[i][1], tree[i][2]); printf( Cost：%d n , cost); }

问答题【问题1】求供应红色零件北京供应商的编号、名称和状态。

问答题【问题2】比较时序图和协作图，说明区别和联系。

问答题【问题1】流程图中的文件F的记录格式设置为如下形式：赛车号姓名课程代码①② 其中的①、②应定义为何种数据