实践考试试题及答案.doc

《实践考试试题及答案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、操作系统1.有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);

2、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

3、{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++){/*最短距离初始

4、化为其他节点到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]

5、点，终点，权值*/System.out.printf("%c-%c:%d",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]

6、turnsum;}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

7、++){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堆的主要功能，