实践考试试题及答案

操作系统1. 有3个进程PA、PB和PC协作解决文件打印问题：PA将文件记录从磁盘读入主存的缓冲区1，每执行一次读一个记录；PB将缓冲区1的内存复制到缓冲区2，每执行一次复制一个记录；PC将缓冲区2的内容打印出来，每执行一次打印一个记录，缓冲区的大小和一个记录大小一样，请用进程通讯或P.V操作方式来保证文件的正确打印。解：答案一答案二定义信号量：avail1 ,avail2 初始值1full1, full2 初始值0PA:beginL1:read from disk; P(avail1); put to buffer1; V(full1); goto L1;End;PB:beginL2:P(full1); get from buffer1; V(avail1); P(avail2); put to buffer2; V(full2);goto L2;End;PC:beginL3: P(full2); get from buffer2; V(avail2); print RECORD; goto L3 end ;Cobegin PA;PB;PC;Coend.Java1、用java语言编写一个java应用程序根据给定图实现最小生成树(Minimal Spinning Tree),可以采用Prim算法和Kruskal算法，并用动画的方式表示最小生成树的生成过程。解：import java.util.*;public class Main static int MAXCOST=Integer.MAX_VALUE; static int Prim(int graph, int n) /* lowcosti记录以i为终点的边的最小权值，当lowcosti=0时表示终点i加入生成树 */ int lowcost=new intn+1; /* msti记录对应lowcosti的起点，当msti=0时表示起点i加入生成树 */ int mst=new intn+1; int min, minid, sum = 0; /* 默认选择1号节点加入生成树，从2号节点开始初始化 */ for (int i = 2; i = n; i+)/* 最短距离初始化为其他节点到1号节点的距离 */lowcosti = graph1i; /* 标记所有节点的起点皆为默认的1号节点 */msti = 1; /* 标记1号节点加入生成树 */ mst1 = 0; /* n个节点至少需要n-1条边构成最小生成树 */ for (int i = 2; i = n; i+)min = MAXCOST;minid = 0; /* 找满足条件的最小权值边的节点minid */ for (int j = 2; j = n; j+) /* 边权值较小且不在生成树中 */ if (lowcostj min & lowcostj != 0) min = lowcostj; minid = j; /* 输出生成树边的信息:起点，终点，权值 */System.out.printf(%c - %c : %dn, mstminid + A - 1, minid + A - 1, min); /* 累加权值 */ sum += min; /* 标记节点minid加入生成树 */ lowcostminid = 0; /* 更新当前节点minid到其他节点的权值 */ for (int j = 2; j = n; j+) /* 发现更小的权值 */ if (graphminidj lowcostj) /* 更新权值信息 */ lowcostj = graphminidj; /* 更新最小权值边的起点 */ mstj = minid; /* 返回最小权值和 */return sum; public static void main(String args) Scanner sc=new Scanner(System.in); int cost; char chx, chy; /* 读取节点和边的数目 */ int n=sc.nextInt();/节点 int m=sc.nextInt();/边数 int graph=new intn+1n+1; /* 初始化图，所有节点间距离为无穷大 */ for (int i = 1; i = n; i+)for (int j = 1; j = n; j+)graphij = MAXCOST; /* 读取边信息 */ for (int k = 0; k size/2) & (pos = size); private void swap(int pos1, int pos2) int tmp; tmp = Heappos1; Heappos1 = Heappos2; Heappos2 = tmp; public void insert(int elem) size+; Heapsize = elem; int current = size; while (Heapcurrent Heapparent(current) swap(current, parent(current); current = parent(current); public void print() int i; for (i=1; i=size;i+) System.out.print(Heapi + ); System.out.println(); public int removemin() swap(1,size); size-; if (size != 0) pushdown(1); return Heapsize+1; private void pushdown(int position) int smallestchild; while (!isleaf(position) smallestchild = leftchild(position); if (smallestchild Heapsmallestchild+1) smallestchild = smallestchild + 1; if (Heapposition = Heapsmallestchild) return; swap(position,smallestchild); position = smallestchild; 3、编写一个求解图的最小周游路径的算法，并用动画的方式表示最小周游路径的生成过程。路径的生成过程。解：package wjcsq;class Edge char vexa; char vexb; int weight; Edge(char vexa, char vexb, int weight) this.vexa = vexa; this.vexb = vexb; this.weight = weight; public class prim static Edge e = new Edge(a, b, 2), new Edge(b, c, 1),new Edge(c, d, 2), new Edge(d, e, 9),new Edge(e, f, 4), new Edge(f, g, 1),new Edge(g, h, 9), new Edge(h, a, 1),new Edge(a, i, 8), new Edge(b, i, 6),new Edge(c, j, 3), new Edge(d, k, 7),new Edge(e, k, 2), new Edge(f, k, 1),new Edge(g, j, 4), new Edge(h, i, 7),new Edge(i, j, 1), new Edge(j, k, 6) ; static int w(int x, int y) char from = (char) (x + 97); char to = (char) (y + 97); for (int i = 0; i 18; i+) if (ei.vexa = from & ei.vexb = to) return ei.weight; if (ei.vexa = to & ei.vexb = from) return ei.weight; return 1000; public static void main(String args) int vex_mst = new int11; for (int i = 0; i 11; i+) vex_msti = 0; vex_mst0 = 1; for (int i = 0; i 10; i+) int add_vex = 0; int min_weight = 1000; Edge adde = new Edge( , , 0); for (int j = 0; j 11; j+) if (vex_mstj = 1) for (int k = 0; k 11; k+) if (vex_mstk = 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_mstadd_vex = 1; char avex = (char) (add_vex + 97); system.out.println(addedge: + adde.vexa + - + adde.vexb + w:+ adde.weight); 动画就没有加在里面，你自己做，参数已经给你，你把参数带入就可以，很简单的GUI编程，重要自己学点知识的。数据结构1. 试用尾插法建立如下单链表： 写出用C语言表示的算法，转化成完整的C程序，并上机调试通过。解：答案一#includestruct Nodechar c;Node* next;/创建一系列的节点连接void CreateNodes(Node* head)/临时指针Node* temp=head-next;for(int i=100;i=98;-i)Node* newnode = new Node();newnode-c=i;head-next=newnode;newnode-next=temp;temp=newnode;int main()Node* head = new Node();head-c=a;head-next=NULL;CreateNodes(head);/输出for(Node* p=head;p!=NULL;p=p-next)printf(