實踐考試試題及答案

1、操作系統(tǒng)1. 有 3 個進程 PA、PB和 PC協(xié)作解決文件打印問題： PA將文件記錄從磁盤讀入主存的緩沖區(qū) 1，每執(zhí)行一次讀一個記錄； PB 將緩沖區(qū) 1 的存復(fù)制到緩沖區(qū) 2，每執(zhí)行一次復(fù)制一個記錄；PC將緩沖區(qū) 2 的容打印出來，每執(zhí)行一次打印一個記錄，緩沖區(qū)的大小和一個記錄大小一樣，請用進程通訊或P.V 操作方式來保證文件的正確打印。解：答案一答案二定義信號量：avail1 ,avail2初始值1full1, full2初始值0PA:beginL1:read from disk;P(avail1);put to buffer1;V(full1);goto L1;End;PB:begin

2、L2: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 L3end ;CobeginPA;PB;PC;Coend.Java1、用 java 語言編寫一個java 應(yīng)用程序根據(jù)給定圖實現(xiàn)最小生成樹 (Minimal Spinning Tree),可以采用Prim 算法和 Kruskal算法，并用動畫的方式表示最小生成樹的生成過程。解：public cla

3、ss Main static int MAXCOST=Integer.MAX_VALUE;static int Prim(int graph, int n)/* lowcosti 記錄以 i 為終點的邊的最小權(quán)值， 當(dāng) lowcosti=0 時表示終點 i 加入生成樹 */int lowcost=new intn+1;/*msti記錄對應(yīng) lowcosti的起點，當(dāng) msti=0時表示起點i 加入生成樹 */int mst=new intn+1;int min, minid, sum = 0;/* 默認(rèn)選擇 1 號節(jié)點加入生成樹，從 2 號節(jié)點開始初始化 */ for (int i = 2;

4、i <= n; i+)/* 最短距離初始化為其他節(jié)點到 1 號節(jié)點的距離 */ lowcosti = graph1i;/*標(biāo)記所有節(jié)點的起點皆為默認(rèn)的1 號節(jié)點 */msti = 1;/*標(biāo)記 1 號節(jié)點加入生成樹*/mst1 = 0;/* n 個節(jié)點至少需要 n-1 條邊構(gòu)成最小生成樹 */ for (int i = 2; i <= n; i+)min = MAXCOST;minid = 0;/* 找滿足條件的最小權(quán)值邊的節(jié)點 for (int j = 2; j <= n; j+)minid */*邊權(quán)值較小且不在生成樹中*/if (lowcostj < min &a

5、mp;& lowcostj != 0)min = lowcostj;minid = j;/*輸出生成樹邊的信息 : 起點，終點，權(quán)值*/1, minid + 'A' - 1, min);/*累加權(quán)值 */sum += min;/*標(biāo)記節(jié)點 minid 加入生成樹 */lowcostminid = 0;/*更新當(dāng)前節(jié)點minid 到其他節(jié)點的權(quán)值*/for (int j = 2; j <= n; j+)/*發(fā)現(xiàn)更小的權(quán)值*/if (graphminidj < lowcostj)/*更新權(quán)值信息 */lowcostj = graphminidj;/*更新最小權(quán)值

6、邊的起點*/mstj = minid;/*返回最小權(quán)值和*/return sum;public static void main(String args)Scanner sc=new Scanner(System.in);int cost;char chx, chy;/*讀取節(jié)點和邊的數(shù)目*/int n=sc.nextInt();/節(jié)點int m=sc.nextInt();/邊數(shù)int graph=new intn+1n+1;/* 初始化圖，所有節(jié)點間距離為無窮大 */ for (int i = 1; i <= n; i+)for (int j = 1; j <= n; j+)gr

7、aphij = MAXCOST;/*讀取邊信息 */for (int k = 0; k < m; k+)chx=sc.next().charAt(0);chy=sc.next().charAt(0);cost=sc.nextInt();int i = chx - 'A' + 1;int j = chy - 'A' + 1;graphij = cost;graphji = cost;/*求解最小生成樹 */cost = Prim(graph, n);/*輸出最小權(quán)值和 */2、編寫一個 java 程序?qū)崿F(xiàn) Min 堆 (Heap) 或者 Max堆的主要功能，

8、并用動畫的方式表示Min 堆或者 Max堆的變化過程。解：public class MinHeap private int Heap;private int maxsize;private int size;public MinHeap(int max) maxsize = max;Heap = new intmaxsize;size = 0 ;Heap0 = Integer.MIN_VALUE;private int leftchild(int pos) return 2*pos;private int rightchild(int pos) return 2*pos + 1;private

9、 int parent(int pos) returnpos / 2;private boolean isleaf(int pos) return (pos > 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 (Heapcur

10、rent < Heapparent(current) swap(current, parent(current);current = parent(current);public void print() int i;for (i=1; i<=size;i+)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)

11、 smallestchild = leftchild(position);if (smallestchild < size) && (Heapsmallestchild > Heapsmallestchild+1)smallestchild = smallestchild + 1;if (Heapposition <= Heapsmallestchild) return;swap(position,smallestchild);position = smallestchild;3、編寫一個求解圖的最小周游路徑的算法，并用動畫的方式表示最小周游路徑的生成過程。路

12、徑的生成過程。解：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&

13、#39;, 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',

14、 '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

15、(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 (

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

17、) 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);動畫就沒有加在里面，你自己做，參數(shù)已經(jīng)給你，你把參數(shù)帶入就可以，很簡單的 GUI 編程，重要自己學(xué)點知識的。數(shù)據(jù)結(jié)構(gòu)1. 試用尾插法建立如下單鏈表：寫出用 C語言表示的算法， 轉(zhuǎn)化成完整的C程序，并上機調(diào)試通過。解：答案一#include<stdio.h&

18、gt;struct Nodechar c;Node* next;/ 創(chuàng)建一系列的節(jié)點連接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("%c",p->c);