實(shí)踐考試試題及答案

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

2、ull1); 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應(yīng)用程序根據(jù)給定圖實(shí)現(xiàn)最小生成樹(Minimal Spinning Tree),可以采用Prim算法和Kruskal算法，并用動畫的方式表示最小生成樹的生成過程。解：import java

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

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

5、stj < min && lowcostj != 0) min = lowcostj; minid = j; /* 輸出生成樹邊的信息:起點(diǎn)，終點(diǎn)，權(quán)值 */System.out.printf("%c - %c : %dn", mstminid + 'A' - 1, minid + 'A' - 1, min); /* 累加權(quán)值 */ sum += min; /* 標(biāo)記節(jié)點(diǎn)minid加入生成樹 */ lowcostminid = 0; /* 更新當(dāng)前節(jié)點(diǎn)minid到其他節(jié)點(diǎn)的權(quán)值 */ for (int j = 2; j

6、<= n; j+) /* 發(fā)現(xiàn)更小的權(quán)值 */ if (graphminidj < lowcostj) /* 更新權(quán)值信息 */ lowcostj = graphminidj; /* 更新最小權(quán)值邊的起點(diǎn) */ mstj = minid; /* 返回最小權(quán)值和 */return sum; public static void main(String args) Scanner sc=new Scanner(System.in); int cost; char chx, chy; /* 讀取節(jié)點(diǎn)和邊的數(shù)目 */ int n=sc.nextInt();/節(jié)點(diǎn) int m=sc.next

7、Int();/邊數(shù) int graph=new intn+1n+1; /* 初始化圖，所有節(jié)點(diǎn)間距離為無窮大 */ for (int i = 1; i <= n; i+)for (int j = 1; j <= n; j+)graphij = 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&

8、#39; + 1; graphij = cost; graphji = cost; /* 求解最小生成樹 */ cost = Prim(graph, n); /* 輸出最小權(quán)值和 */ System.out.println("Total:"+cost); 2、編寫一個java程序?qū)崿F(xiàn)Min堆(Heap)或者M(jìn)ax堆的主要功能，并用動畫的方式表示Min堆或者M(jìn)ax堆的變化過程。解：public class MinHeap private int Heap; private int maxsize; private int size; public MinHeap(int ma

9、x) 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 int parent(int pos) return pos / 2; private boolean isleaf(int pos) return (pos > size/2) && (pos <= siz

10、e); 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() i

11、nt 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)

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

13、dge 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

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

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

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

17、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 =

18、 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); 動畫就沒有加在里面，你自己做，參數(shù)已經(jīng)給你，

19、你把參數(shù)帶入就可以，很簡單的GUI編程，重要自己學(xué)點(diǎn)知識的。數(shù)據(jù)結(jié)構(gòu)1. 試用尾插法建立如下單鏈表： 寫出用C語言表示的算法，轉(zhuǎn)化成完整的C程序，并上機(jī)調(diào)試通過。解：答案一#include<stdio.h>struct Node char c; Node* next;/創(chuàng)建一系列的節(jié)點(diǎn)連接void CreateNodes(Node* head) /臨時指針 Node* temp=head->next; for(int i=100;i>=98;-i)   Node* newnode = new

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

21、next)   printf("%c  ",p->c); 答案二1         / <summary> 2         / 創(chuàng)建操作(尾插法創(chuàng)建鏈表) 3         / <

22、/summary> 4         public void CreateListTail() 5          6             Node p = head; 7 &

23、#160;           int d = Int32.Parse(Console.ReadLine(); 8             while(d!=-1) 9            

24、; 10                 Node s = new Node(d);11                 if (head = null)12  

25、;               13                     head = s;14                 15