问答题

[说明] 下面的流程图实现了正整数序列{K(1),K(2),…,K(n)}的重排，得到的新序列中，比K(1)小的数都在K(1)的左侧，比K(1)大的数都在K(1)的右侧。以n=6为例，序列{12，2，9，13，21，8}的重排过程为： {12,2,9,13,21,8} →{2,12,9,13,21,8} →{9,2,12,13,21,8} →{8,9,2,12,13,21} [流程图]

【参考答案】

(1) K(s)＜K(t) (2) K(s) (3) i←i-1 (4) t←t+1 (5) s←s+1[考点分析] 考......

(↓↓↓ 点击下方‘点击查看答案’看完整答案 ↓↓↓)

<上一题目录下一题>

热门试题

问答题

[说明]Kruskal算法是一种构造图的最小生成树的方法。设G为一无向连通图，令T是由G的顶点构成的于图，Kmskal算法的基本思想是为T添加适当的边使之成为最小生成树：初始时，T中的点互相不连通；考察G的边集E中的每条边，若它的两个顶点在T中不连通，则将此边添加到T中，同时合并其两顶点所在的连通分量，如此下去，当添加了n-1条边时，T的连通分量个数为1，T便是G的一棵最小生成树。下面的函数void Kruskal(EdgeType edges[],int n)利用Kruskal算法，构造了有n个顶点的图 edges的最小生成树。其中数组father[]用于记录T中顶点的连通性质：其初值为father[i]=-1 (i=0,1,…,n-1)，表示各个顶点在不同的连通分量上；若有father[i]=j，j＞-1，则顶点i，j连通；函数int Find(int father[],int v)用于返回顶点v所在树形连通分支的根结点。[函数]#define MAXEDGE 1000typedef struct{ int v1;int v2;}EdgeType;void Kruskal(EdgeType edges[],int n){ int father[MAXEDGE];int i,j,vf1,vt2;for(i=0;i＜n;i+ +) father[i]=-1;i=0;j=0;while(i＜MAXEDGE && j＜ (1) ){ vf1=Find(father,edges[i].v1);vf2=Find(father,edges[i].v2);if( (2) ){ (3) =vf1;(4) ;printf( %3d%3d n ,edges[i].v1,edges[i].v2);}(5) ;}}int Find(int father[],int v){ int t;t=v;while(father[t]＞=0) t=father[t];return(t);}

问答题

[说明]邻接表是图的一种顺序存储与链式存储结合的存储方法。其思想是：对于图G中的每个顶点 vi，将所有邻接于vi的顶点vj连成一个单链表，这个单链表就称为顶点vi的邻接表，其中表头称作顶点表结点VertexNode，其余结点称作边表结点EdgeNode。将所有的顶点表结点放到数组中，就构成了图的邻接表AdjList。邻接表表示的形式描述如下： #define MaxVerNum 100 *最大顶点数为100* typedef struct node{ *边表结点* int adjvex; *邻接点域* struct node *next; *指向下一个边表结点的指针域* }EdgeNode;typedef struct vnode{ *顶点表结点* int vertex; *顶点域* EdgeNode *firstedge; *边表头指针* }VertexNode;typedef VertexNode AdjList[MaxVerNum]; *AdjList是邻接表类型* typedef struct{AdjList adjlist; *邻接表* int n; *顶点数* }ALGraph; *ALGraph是以邻接表方式存储的图类型* 深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。下面的函数利用递归算法，对以邻接表形式存储的图进行深度优先搜索：设初始状态是图中所有顶点未曾被访问，算法从某顶点v出发，访问此顶点，然后依次从v的邻接点出发进行搜索，直至所有与v相连的顶点都被访问；若图中尚有顶点未被访问，则选取这样的一个点作起始点，重复上述过程，直至对图的搜索完成。程序中的整型数组visited[]的作用是标记顶点i是否已被访问。[函数]void DFSTraverseAL(ALGraph *G) *深度优先搜索以邻接表存储的图G* { int i;for(i=0;i＜ (1) ;i++) visited[i]=0;for(i=0;i＜ (1) ;i++)if( (2) ) DFSAL(G,i);}void DFSAL(ALGraph *G,int i) *从Vi出发对邻接表存储的图G进行搜索* { EdgeNode *p;(3) ;p= (4) ;while(p!=NULL) *依次搜索Vi的邻接点Vj* { if(! visited[ (5) ]) DFSAL(G, (5) );p=p-＞next; *找Vi的下一个邻接点* }}

相关试题