B.Kruskal算法：(贪心)按权值递增顺序删去图中的边，若不形成回路则将此边加入最小生成树。function find(v:integer):integer; {返回顶点v所在的集合}var i:integer;

A、Private Sub sele(ByVal A( ) As integer)

B、Private Function sale(A() As Integer) As String

C、Private Sub sale(A() As Integer) As Integer

D、Private Sub sale(A(i) As Integer)

有如下程序： Private Sub Command1_Click() Dim k As Integer，m As Integer Dim p As Integer k=4：m=1 p=PC(k，m)：Print p； p=PC(k，m)：Print p End Sub Private Function PC(a As Integer，b As Integer) Static m As Integer，i As Integer m=0：i=2 i=i + m + 1 m=i + a + b PC=m End Function 程序运行后，输出的结果为

A．4 6

B．6 6

C．8 8

D．10 12

单击命令按钮时，下列程序代码的执行结果为 ( ) Function FirProc(x As Integer, y As Integer, z As Integer) FirProc=2*x+y+3*z End Function Function SecProc(x As Integer, y As Integer, z As Integer) SecProc＝FirProc(z, x, y)+x End Function Private Sub Commandl Click() Dim a As Integer, b As Integer, c As Integer a＝2 :b=3 :c=4 Print SecProc(c, b,A)End Sub

A．21

B．19

C．17

D．34

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

【说明】 应用Prim算法求解连通网络的最小生成树问题。请阅读程序后填空。

const int MaxInt＝INT MAX； //INT MAX的值在＜limits．h＞中

const int n＝6； //图的顶点数，应由用户定义

typedef int AdjMatrix[n][n]； //用二维数组作为邻接矩阵表示

typedef struct{ //生成树的边结点

int fromVex，to Vex； //边的起点与终点

int weight； //边上的权值

}TreeEdSenode；

typedef TreeEdgeNode MST[n-1]； //最小生成树定义

void PrimMST (AdjMatrix G，MST T，int rt){

//从顶点rt出发构造图G的最小生成树T，rt成为树的根结点

TreeEdgeNode e； int i，k＝0，min，minpos，v；

for(i＝0；i＜n；i++) //初始化最小生成树T

if(i!＝rt){

T[k]．fromVex＝rt；

(1)；

T[k++].weight＝G[rt][i]；

}

for(k＝0；k＜n-1；k++){ //依次求MST的候选边

(2)；

for(i＝k；i＜n-1；i++) 八遍历当前候选边集合

if(T[i].weight＜min) //选具有最小权值的候选边

{min＝T[i]．weight；(3)；}

if(min＝＝MaxInt) //图不连通，出错处理

{cerr＜＜“Graph is disconnected!”＜＜endl； exit(1)；}

e=T[minpos]；T[minpos]＝T[k]；(4)；

v=T[k].to Vex；

for(i＝k+1；i＜n-1；i++) //修改候选边集合

if(G[v][T[i].to Vex]＜T[i].weight){

T[i]．weight＝G[v][T[i].toVex]；

(5)；

}

}

}

求两数的最小公倍数

function lcm(a,b:integer):integer;

最小生成树

A.Prim算法：

procedure prim(v0:integer);

var

lowcost,closest:array[1..maxn] of integer;

i,j,k,min:integer;

四、排序算法

A.快速排序：

procedure qsort(l,r:integer);

var i,j,mid:integer;

链表的定位函数

loc(I:integer):pointer; {寻找链表中的第I个结点的指针}

procedure loc(L:linklist; I:integer):pointer;

var p:pointer;

j:integer;

有以下函数过程： Function Gys(ByVal x As Integer，ByVal y As Integer)As Integer Do While y＜ >0 Remender=x Mod v x=y Y=Reminder Loop Gys=x End Function 以下是调用该函数的事件过程，该程序的运行结果是 Private Sub Command1_Click( ) Dim a As Integer Dim b As Integer a=50 b=10 x=Cys(a，B)Print x End sub

A．0

B．10

C．50

D．100

Prim算法和Kruscal算法都是无向连通网的最小生成树的算法，Prim算法从一 个顶点开始，每次从剩余的顶点加入一个顶点，该顶点与当前生成树中的顶占的连边权重 最小，直到得到最小生成树开始，Kruscal算法从权重最小的边开始，每次从不在当前的生成树顶点之间的边中选择权重最小的边加入，直到得到一颗最小生成树，这两个算法都采用了（ ）设计策略，且（ ）。

A.分治 B.贪心 C.动态规划 D.回溯 A.若网较稠密，则Prim算法更好 B.两个算法得到的最小生成树是一样的 C.Prim算法比Kruscal算法效率更高 D.Kruscal算法比Prim算法效率更高

A.type Integer intfunc (a Integer) Add(b Integer) Integer { return a + b}

B.type Integer intfunc (a Integer) Add(b *Integer) Integer { return a + *b}

C.type Integer intfunc (a *Integer) Add(b Integer) Integer { return *a + b}

D.type Integer intfunc (a *Integer) Add(b *Integer) Integer { return *a + *b}

阅读下列函数说明和C代码，将应填入(n)处的字句写上。

[说明]

若要在N个城市之间建立通信网络，只需要N-1条线路即可。如何以最低的经济代价建设这个网络，是一个网的最小生成树的问题。现要在8个城市间建立通信网络，其问拓扑结构如图5-1所示，边表示城市间通信线路，边上标示的是建立该线路的代价。

[图5-1]

无向图用邻接矩阵存储，元素的值为对应的权值。考虑到邻接矩阵是对称的且对角线上元素均为0，故压缩存储，只存储上三角元素(不包括对角线)。

现用Prim算法生成网络的最小生成树。由网络G=(V，E)构造最小生成树T=(U，TE)的Prim算法的基本思想是：首先从集合V中任取一顶点放入集合U中，然后把所有一个顶点在集合U里、另一个顶点在集合V-U里的边中，找出权值最小的边(u，v)，将边加入TE，并将顶点v加入集合U，重复上述操作直到U=V为止。

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

define MAX 32768 /*无穷大权，表示顶点间不连通*/

define MAXVEX 30 /*图中顶点数目的最大值*/

typedef struct{

int startVex，stopVex; /*边的起点和终点*/

float weight; /*边的权*/

}Edge;

typedef struct{

char vexs[MAXVEX]; /*顶点信息*/

float arcs[MAXVEX*(MAXVEX-1)/2]; /*邻接矩阵信息，压缩存储*/

int n; /*图的顶点个数*/

}Graph;

[函数]

void PrimMST(Graph*pGraph, Edge mst[])

{

int i,j,k,min,vx,vy;

float weight，minWeight;

Edge edge;

for(i=0; i＜pGraph-＞n-1；i++){

mst[i].StartVex=0;

mst[i].StopVex=i+1;

mst[i].weight=pGraph-＞arcs[i];

}

for(i=0；i＜(1)；i++){/*共n-1条边*/

minWeight=(float)MAX;

min=i;

/*从所有边(vx，vy)中选出最短的边*/

for(j=i; j＜pGraph-＞n-1; j++){

if(mst[j].weight＜minWeight){

minWeight=(2);

min=j；

}

}

/*mst[minl是最短的边(vx，vy)，将mst[min]加入最小生成树*/

edge=mst[min]；

mst[min]=mst[i];

mst[i]=edge;

vx=(3);/*vx为刚加入最小生成树的顶点下标*/

/*调整mst[i+1]到mst[n-1]*/

for(j=i+1；j＜pGraph-＞n-1；j++){

vy=mst[j].StopVex;

if( (4) ){/*计算(vx，vy)对应的边在压缩矩阵中的下标*/

k=pGraph-＞n*vy-vy*(vy+1)/2+vx-vy-1；

}else{

k=pGraph-＞n*vx-vx*(vx+1)/2+vy-vx-1;

}

weight(5)；

if(weight＜mst[j].weight){

mst[j].weight=weight;

mst[j].StartVex=vx;

}

}

}

}

(1)

有如下程序： Private Sub Command1_Click() Dim k As Integer，m As Integer Dim op As Integer k=4:m=1 p=PPC(k,m):Print op； p=PPC(k.m):Print op End Sub Private Function PPC(a As Integer，b As Integer) Static m As Integer，i As Integer m=0:i=2 i=i+m+1 m=i+a+b PPC=m End Function 程序运行后，输出的结果为

A．4 6

B．6 6

C．8 8

D．10 12

以下用户自定义函数 Function Func(a As Integer, b As Integer) As Integer Static m As Integer, i As Integer m=0:i=2 i=i+m+i m=i+a+b Func=m End Function 在窗体上画一个命令按钮，然后编写如下事件过程： Private Sub Command1_Click() Dim k As Integer，m As Integer，p As Integer k=4：m=1 P=Func(k，m) Print p End Sub 程序运行后，单击命令按钮，输出结果为

A．8

B．9

C．10

D．11

素数的求法

A.小范围内判断一个数是否为质数：

function prime (n: integer): Boolean;

var I: integer;

C. Dijkstra 算法：

var

a:array[1..maxn,1..maxn] of integer;

b,pre:array[1..maxn] of integer; {pre[i]指最短路径上I的前驱结点}

mark:array[1..maxn] of boolean;

procedure dijkstra(v0:integer);

折半查找

function binsearch(k:keytype):integer;

var low,hig,mid:integer;

有如下函数： Function fun(a As Integer，n As Integer)As Integer Dim m AS Integer While a>=n a=a-n：m=m+1 Wend Fun=m End Function 该函数的返回值是。 A．a乘以n的乘积 B．a加n的和 C．a减n的差 D．a除以n的商(不含小数部分)

在窗体上画一个按钮，然后编写如下的事件代码。在按钮上单击，输出为( )。 Private Function fun(x As Integer，y As Integer) Static m As Integer Static i As Integer i=i+2 i=i+m+1 m=i+x+y fun=m End Function Private Sub Command1_Click() Dim j As Integer，m As Integer,k As Integer j=4：m=1 k=fun(j,m) Print k； k=fun (j，m) Print k End Sub

A．8 18

B．7 17

C．7 19

D．8 19

●试题四

阅读下列算法说明和算法，将应填入(n)的字句写在答题纸的对应栏内。

【说明】

下列最短路径算法的具体流程如下：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通网的最小生成树。该算法的基本思想是：为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出n-1条互不构成回路的权值最小边为止。

图5算法流程图

【算法】

/*对图定义一种新的表示方法，以一维数组存放图中所有边，并在构建图的存储结构时将它构造为一个"有序表"。以顺序表MSTree返回生成树上各条边。*/

typedef struct{

VertexType vex1；

VertexType vex2；

VRType weight；

}EdgeType；

typedef ElemType EdgeType；

typedef struct{//有向网的定义

VertexType vexs[MAX_VERTEX_NUM]；//顶点信息

EdgeType edge[MAX_EDGE_NUM]；//边的信息

int vexnum，arcnum；//图中顶点的数目和边的数目

}ELGraph；

void MiniSpanTree_Kruskal(ELGraph G，SqList& MSTree){

//G.edge 中依权值从小到大存放有向网中各边

//生成树的边存放在顺序表MSTree中

MFSetF；

InitSet(F，G.vexnum)；//将森林F初始化为n棵树的集合

InitList(MSTree，G.vexnum)；//初始化生成树为空树

i=0；k=1；

while(k< (1) ){

e=G.edge[i]；//取第i条权值最小的边

/*函数fix_mfset返回边的顶点所在树的树根代号，如果边的两个顶点所在树的树根相同，则说明它们已落在同一棵树上。*/

rl=fix_mfset(F，LocateVex(e.vex1))；

r2= (2) //返回两个顶点所在树的树根

if(r1 (3) r2){//选定生成树上第k条边

if(ListInsert(MSTree，k，e){ (4) ；//插入生成树

mix_mfset(E，rl，r2)；//将两棵树归并为一棵树

}

(5) ；//继续考察下一条权值最小边

}

DestroySet(F)；

}