实践考试试题及答案

./操作系统有3个进程PA、PB和PC协作解决文件打印问题：PA将文件记录从磁盘读入主存的缓冲区1,每执行一次读一个记录；PB将缓冲区1的存复制到缓冲区2,每执行一次复制一个记录；PC将缓冲区2的容打印出来,每执行一次打印一个记录,缓冲区的大小和一个记录大小一样,请用进程通讯或P.V操作方式来保证文件的正确打印。解：答案一答案二定义信号量：avail1,avail2初始值1full1,full2初始值0PA:beginL1:readfromdisk;P<avail1>;puttobuffer1;V<full1>;gotoL1;End;PB:beginL2:P<full1>;getfrombuffer1;V<avail1>;P<avail2>;puttobuffer2;V<full2>;gotoL2;End;PC:beginL3:P<full2>;getfrombuffer2;V<avail2>;printRECORD;gotoL3end;CobeginPA;PB;PC;Coend.Java1、用java语言编写一个java应用程序根据给定图实现最小生成树<MinimalSpinningTree>,可以采用Prim算法和Kruskal算法,并用动画的方式表示最小生成树的生成过程。解：importjava.util.*;publicclassMain{staticintMAXCOST=Integer.MAX_VALUE;staticintPrim<intgraph[][],intn>{/*lowcost[i]记录以i为终点的边的最小权值,当lowcost[i]=0时表示终点i加入生成树*/intlowcost[]=newint[n+1];/*mst[i]记录对应lowcost[i]的起点,当mst[i]=0时表示起点i加入生成树*/intmst[]=newint[n+1];intmin,minid,sum=0;/*默认选择1号节点加入生成树,从2号节点开始初始化*/for<inti=2;i<=n;i++>{ /*最短距离初始化为其他节点到1号节点的距离*/ lowcost[i]=graph[1][i]; /*标记所有节点的起点皆为默认的1号节点*/ mst[i]=1;}/*标记1号节点加入生成树*/mst[1]=0;/*n个节点至少需要n-1条边构成最小生成树*/for<inti=2;i<=n;i++>{ min=MAXCOST; minid=0;/*找满足条件的最小权值边的节点minid*/for<intj=2;j<=n;j++>{ /*边权值较小且不在生成树中*/ if<lowcost[j]<min&&lowcost[j]!=0>{ min=lowcost[j]; minid=j; }}/*输出生成树边的信息:起点,终点,权值*/ System.out.printf<"%c-%c:%d\n",mst[minid]+'A'-1,minid+'A'-1,min>;/*累加权值*/sum+=min;/*标记节点minid加入生成树*/lowcost[minid]=0;/*更新当前节点minid到其他节点的权值*/for<intj=2;j<=n;j++>{/*发现更小的权值*/ if<graph[minid][j]<lowcost[j]>{ /*更新权值信息*/ lowcost[j]=graph[minid][j]; /*更新最小权值边的起点*/ mst[j]=minid; }}}/*返回最小权值和*/ returnsum;}publicstaticvoidmain<Stringargs[]>{Scannersc=newScanner<System.in>;intcost;charchx,chy;/*读取节点和边的数目*/intn=sc.nextInt<>;//节点intm=sc.nextInt<>;//边数intgraph[][]=newint[n+1][n+1];/*初始化图,所有节点间距离为无穷大*/for<inti=1;i<=n;i++>{ for<intj=1;j<=n;j++>{ graph[i][j]=MAXCOST; }}/*读取边信息*/for<intk=0;k<m;k++>{chx=sc.next<>.charAt<0>;chy=sc.next<>.charAt<0>;cost=sc.nextInt<>; inti=chx-'A'+1; intj=chy-'A'+1; graph[i][j]=cost; graph[j][i]=cost;}/*求解最小生成树*/cost=Prim<graph,n>;/*输出最小权值和*/System.out.println<"Total:"+cost>;}}2、编写一个java程序实现Min堆<Heap>或者Max堆的主要功能,并用动画的方式表示Min堆或者Max堆的变化过程。解：publicclassMinHeap{privateint[]Heap;privateintmaxsize;privateintsize;publicMinHeap<intmax>{maxsize=max;Heap=newint[maxsize];size=0;Heap[0]=Integer.MIN_VALUE;}privateintleftchild<intpos>{return2*pos;}privateintrightchild<intpos>{return2*pos+1;}privateintparent<intpos>{returnpos/2;}privatebooleanisleaf<intpos>{return<<pos>size/2>&&<pos<=size>>;}privatevoidswap<intpos1,intpos2>{inttmp;tmp=Heap[pos1];Heap[pos1]=Heap[pos2];Heap[pos2]=tmp;}publicvoidinsert<intelem>{size++;Heap[size]=elem;intcurrent=size;while<Heap[current]<Heap[parent<current>]>{swap<current,parent<current>>;current=parent<current>;}}publicvoidprint<>{inti;for<i=1;i<=size;i++>System.out.print<Heap[i]+"">;System.out.println<>;}publicintremovemin<>{swap<1,size>;size--;if<size!=0>pushdown<1>;returnHeap[size+1];}privatevoidpushdown<intposition>{intsmallestchild;while<!isleaf<position>>{smallestchild=leftchild<position>;if<<smallestchild<size>&&<Heap[smallestchild]>Heap[smallestchild+1]>>smallestchild=smallestchild+1;if<Heap[position]<=Heap[smallestchild]>return;swap<position,smallestchild>;position=smallestchild;}}}3、编写一个求解图的最小周游路径的算法,并用动画的方式表示最小周游路径的生成过程。路径的生成过程。解：packagewjcsq;

classEdge{

charvexa;

charvexb;

intweight;

Edge<charvexa,charvexb,intweight>{

this.vexa=vexa;

this.vexb=vexb;

this.weight=weight;

}

}

publicclassprim{

staticEdge[]e={newEdge<'a','b',2>,newEdge<'b','c',1>,

newEdge<'c','d',2>,newEdge<'d','e',9>,

newEdge<'e','f',4>,newEdge<'f','g',1>,

newEdge<'g','h',9>,newEdge<'h','a',1>,

newEdge<'a','i',8>,newEdge<'b','i',6>,

newEdge<'c','j',3>,newEdge<'d','k',7>,

newEdge<'e','k',2>,newEdge<'f','k',1>,

newEdge<'g','j',4>,newEdge<'h','i',7>,

newEdge<'i','j',1>,newEdge<'j','k',6>};

staticintw<intx,inty>{

charfrom=<char><x+97>;

charto=<char><y+97>;

for<inti=0;i<18;i++>{

if<e[i].vexa==from&&e[i].vexb==to>{

returne[i].weight;

}

if<e[i].vexa==to&&e[i].vexb==from>{

returne[i].weight;

}

}

return1000;}

publicstaticvoidmain<String[]args>{

int[]vex_mst=newint[11];

for<inti=0;i<11;i++>

vex_mst[i]=0;

vex_mst[0]=1;

for<inti=0;i<10;i++>{

intadd_vex=0;

intmin_weight=1000;

Edgeadde=newEdge<'','',0>;

for<intj=0;j<11;j++>

if<vex_mst[j]==1>{

for<intk=0;k<11;k++>{

if<vex_mst[k]==0&&w<j,k><min_weight>{

add_vex=k;

min_weight=w<j,k>;

adde.vexa=<char><j+97>;

adde.vexb=<char><k+97>;

adde.weight=min_weight;

}

}

}

vex_mst[add_vex]=1;

charavex=<char><add_vex+97>;

system.out.println<"addedge:"+adde.vexa+"-"+adde.vexb+"w:"+adde.weight>;

}

}

}

动画就没有加在里面,你自己做,参数已经给你,你把参数带入就可以,很简单的GUI编程,重要自己学点知识的。数据结构试用尾插法建立如下单链表：写出用C语言表示的算法,转化成完整的C程序,并上机调试通过。解：答案一#include<stdio.h>structNode

{

charc;

Node*next;

};//创建一系列的节点连接

voidCreateNodes<Node*head>

{

//临时指针

Node*temp=head->next;

for<inti=100;i>=98;--i>

{

Node*newnode=newNode<>;

newnode->c=i;

head->next=newnode;

newnode->next=temp;

temp=newnode;

}

}

intmain<>

{

Node*head=newNode<>;

head->c='a';

head->next=NULL;

CreateNodes<he