阅读下列C程序和程序说明,将应填入(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;

题目

阅读下列C程序和程序说明,将应填入(n)处的字句写在答题纸的对应栏内。

【说明】用克鲁斯卡尔算法求解给定图的最小生成树。

include <stdio. h>

include <stdlib. h>

define MAXN 30

typedef 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];

&nb


相似考题
更多“阅读下列C程序和程序说明,将应填入(n)处的字句写在答题纸的对应栏内。【说明】用克鲁斯卡尔算法求解 ”相关问题
  • 第1题:

    图2-1是基于软交换的网络分层模型。请将选项应填入(n)处的字句写在答题纸对应的解答栏内。


    正确答案:
    (1)业务/应用层
    (2)控制层
    (3)接入层
    (4)媒体网关

  • 第2题:

    ()阅读下列说明和C语言程序,将应填入 (n)处的语句写在答题纸的对应栏内。[说明]下面程序是一个带参数的主函数,其功能是显示在命令行中输入的文本文件内容。[C语言函数]#include"stdio.h"main(argc,argv) int argc; char *argv[]; { (1) ; if((fp=fopen(argv[1],”r’’))== (2) ) { printf(”file not open!\n”);exit(0);} while( (3) ) putchar( (4) ); (5); }


    正确答案:()
    (1)FILE *fp; (2)NULL  (3)!feof(fp)  (4)fgetc(fp)   (5)fclose(fp)
    从程序功能来看,程序中需要用到文件型指针变量中,而主函数体没有定义,所以(1)应该填写的是“FILE *fp;”。接下来的语句是标准的打开只读文本文件的语句,显示的是文件没打开,说明文件名不存在,也就是为“NULL”。接着的while循环语句中有两处空白。前一个空白是控制循环的条件,从程序功能来看,要将文本文件中的所有字符显示出来,这儿当然只能填写“不是文件尾则继续循环”,具体说,需要填写的是“!feof(fp)”。(4)出现在循环体中的语句中,该循环体的功能是从fp指向的文本文件中读取单个字符并显示在屏幕上,此处使用的是putchar函数,该函数的功能是将形参对应的字符显示在屏幕上,所以该处的空白就是要显示的字符,这个字符必须是从文本文件中读取的单个字符,完成这项工作的可以利用fgetc()函数,所以(4)填写的是“fgetc(fp)”。最后一句应当是关闭文件,所以(5)应填fclose(fp)。

  • 第3题:

    阅读下列说明,补充(1)-(9),将解答填入答题纸的对应栏内。


    答案:
    解析:

  • 第4题:

    (a)智能网概念模型中分布功能平面模型如下图所示,请根据此图将应填入(n)处的 字句写在答题纸的对应栏内。


    正确答案:
    (1)SMF(或业务管理功能)
    (2)SCEF(或业务生成功能)
    (3)SDF(或业务数据功能)
    (4)SCF(或业务控制功能)
    (5)SSF(或业务交换功能)
    (6)CCF(或呼叫控制功能)

  • 第5题:

    阅读下列说明和C++-代码,将应填入(n)处的字句写在答题纸的对应栏内。 【说明】 某发票(lnvoice)由抬头(Head)部分、正文部分和脚注(Foot)部分构成。现采用装饰(Decorator)模式实现打印发票的功能,得到如图5-1所示的类图。

    【C++代码】 #include using namespace std; class invoice{ public: (1){ cout<<"This is the content of the invoice!"<

    答案:
    解析:
    (1) virtual void printInvoice() (2) ticket->printInvoice() (3) Decorator::printInvoice() (4) Decorator::printInvoice() (5) &a
    【解析】

    试题分析
    1.Invoice类下,义虛函数,按类图,函数名是printInvoice
    2.前面定义对象名是ticket,那么在ticket不为空的时候调用函数printInvoice
    3.这部分填写发票的抬头,看类图应该实现函数printInvoice ,Decorator装饰模式使用该方法
    4.这部分是发票的脚注,看类图应该实现函数printlnvoice,Decorator装饰模式使用该方法
    5.FootDecorator a(NULL) ;脚步的装饰参数是a,调用a参数,

  • 第6题:

    阅读下列说明和?C++代码,将应填入(n)处的字句写在答题纸的对应栏内。
    【说明】
    阅读下列说明和?Java代码,将应填入?(n)?处的字句写在答题纸的对应栏内。
    【说明】
    某快餐厅主要制作并出售儿童套餐,一般包括主餐(各类比萨)、饮料和玩具,其餐品种
    类可能不同,但其制作过程相同。前台服务员?(Waiter)?调度厨师制作套餐。现采用生成器?(Builder)?模式实现制作过程,得到如图?6-1?所示的类图。






    答案:
    解析: