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

1、操作系統(tǒng)1. 有3個(gè)進(jìn)程PA、PB和PC協(xié)作解決文件打印問(wèn)題：PA將文件記錄從磁盤讀入主存的緩沖區(qū)1，每執(zhí)行一次讀一個(gè)記錄；PB將緩沖區(qū)1的內(nèi)存復(fù)制到緩沖區(qū)2，每執(zhí)行一次復(fù)制一個(gè)記錄；PC將緩沖區(qū)2的內(nèi)容打印出來(lái)，每執(zhí)行一次打印一個(gè)記錄，緩沖區(qū)的大小和一個(gè)記錄大小一樣，請(qǐng)用進(jìn)程通訊或P.V操作方式來(lái)保證文件的正確打印。解：答案一答案二定義信號(hào)量：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語(yǔ)言編寫(xiě)一個(gè)java應(yīng)用程序根據(jù)給定圖實(shí)現(xiàn)最小生成樹(shù)(Minimal Spinning Tree),可以采用Prim算法和Kruskal算法，并用動(dòng)畫(huà)的方式表示最小生成樹(shù)的生成過(guò)程。解：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時(shí)表示終點(diǎn)i加入生成樹(shù) */ int lowcost=new intn+1; /* msti記錄對(duì)應(yīng)lowcosti的起點(diǎn)，當(dāng)msti=0時(shí)表示起點(diǎn)i加入生成樹(shù) */ int mst=new intn+1; int min, minid, sum = 0; /* 默認(rèn)選擇1號(hào)節(jié)點(diǎn)加入生成樹(shù)，從2號(hào)節(jié)點(diǎn)開(kāi)始初始化 */ for (

4、int i = 2; i <= n; i+)/* 最短距離初始化為其他節(jié)點(diǎn)到1號(hào)節(jié)點(diǎn)的距離 */lowcosti = graph1i; /* 標(biāo)記所有節(jié)點(diǎn)的起點(diǎn)皆為默認(rèn)的1號(hào)節(jié)點(diǎn) */msti = 1; /* 標(biāo)記1號(hào)節(jié)點(diǎn)加入生成樹(shù) */ mst1 = 0; /* n個(gè)節(jié)點(diǎn)至少需要n-1條邊構(gòu)成最小生成樹(shù) */ 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)值較小且不在生成樹(shù)中 */ if (lowco

5、stj < min && lowcostj != 0) min = lowcostj; minid = j; /* 輸出生成樹(shù)邊的信息:起點(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加入生成樹(shù) */ 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)間距離為無(wú)窮大 */ 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; /* 求解最小生成樹(shù) */ cost = Prim(graph, n); /* 輸出最小權(quán)值和 */ System.out.println("Total:"+cost); 2、編寫(xiě)一個(gè)java程序?qū)崿F(xiàn)Min堆(Heap)或者M(jìn)ax堆的主要功能，并用動(dòng)畫(huà)的方式表示Min堆或者M(jìn)ax堆的變化過(guò)程。解：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、編寫(xiě)一個(gè)求解圖的最小周游路徑的算法，并用動(dòng)畫(huà)的方式表示最小周游路徑的生成過(guò)程。路徑的生成過(guò)程。解：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); 動(dòng)畫(huà)就沒(méi)有加在里面，你自己做，參數(shù)已經(jīng)給你，

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