实践考试试题及答案.docx
- 文档编号:12919971
- 上传时间:2023-06-09
- 格式:DOCX
- 页数:14
- 大小:152.82KB
实践考试试题及答案.docx
《实践考试试题及答案.docx》由会员分享,可在线阅读,更多相关《实践考试试题及答案.docx(14页珍藏版)》请在冰点文库上搜索。
实践考试试题及答案
操作系统
1.有3个进程PA、PB和PC协作解决文件打印问题:
PA将文件记录从磁盘读入主存的缓冲区1,每执行一次读一个记录;PB将缓冲区1的内存复制到缓冲区2,每执行一次复制一个记录;PC将缓冲区2的内容打印出来,每执行一次打印一个记录,缓冲区的大小和一个记录大小一样,请用进程通讯或P.V操作方式来保证文件的正确打印。
解:
答案一
答案二
定义信号量:
avail1,avail2初始值1
full1,full2初始值0
PA:
begin
L1:
readfromdisk;
P(avail1);
puttobuffer1;
V(full1);
gotoL1;
End;
PB:
begin
L2:
P(full1);
getfrombuffer1;
V(avail1);
P(avail2);
puttobuffer2;
V(full2);
gotoL2;
End;
PC:
begin
L3:
P(full2);
getfrombuffer2;
V(avail2);
printRECORD;
gotoL3
end;
Cobegin
PA;PB;PC;
Coend.
Java
1、用java语言编写一个java应用程序根据给定图实现最小生成树(MinimalSpinningTree),可以采用Prim算法和Kruskal算法,并用动画的方式表示最小生成树的生成过程。
解:
importjava.util.*;
publicclassMain{
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++){
/*最短距离初始化为其他节点到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] =0){ min=lowcost[j]; minid=j; } } /*输出生成树边的信息: 起点,终点,权值*/ System.out.printf("%c-%c: %d\n",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] /*更新权值信息*/ lowcost[j]=graph[minid][j]; /*更新最小权值边的起点*/ mst[j]=minid; } } } /*返回最小权值和*/ returnsum; } 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 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堆的主要功能,并用动画的方式表示Min堆或者Max堆的变化过程。 解: publicclassMinHeap{ privateint[]Heap; privateintmaxsize; privateintsize; publicMinHeap(intmax){ maxsize=max; Heap=newint[maxsize]; size=0; Heap[0]=Integer.MIN_VALUE; } privateintleftchild(intpos){ return2*pos; } privateintrightchild(intpos){ return2*pos+1; } privateintparent(intpos){ returnpos/2; } privatebooleanisleaf(intpos){ return((pos>size/2)&&(pos<=size)); } privatevoidswap(intpos1,intpos2){ inttmp; tmp=Heap[pos1]; Heap[pos1]=Heap[pos2]; Heap[pos2]=tmp; } publicvoidinsert(intelem){ size++; Heap[size]=elem; intcurrent=size; while(Heap[current] swap(current,parent(current)); current=parent(current); } } publicvoidprint(){ inti; for(i=1;i<=size;i++) System.out.print(Heap[i]+""); System.out.println(); } publicintremovemin(){ swap(1,size); size--; if(size! =0) pushdown (1); returnHeap[size+1]; } privatevoidpushdown(intposition){ intsmallestchild; while(! isleaf(position)){ smallestchild=leftchild(position); if((smallestchild smallestchild=smallestchild+1; if(Heap[position]<=Heap[smallestchild])return; swap(position,smallestchild); position=smallestchild; } } } 3、编写一个求解图的最小周游路径的算法,并用动画的方式表示最小周游路径的生成过程。 路径的生成过程。 解: packagewjcsq; classEdge{ charvexa; charvexb; intweight; Edge(charvexa,charvexb,intweight){ this.vexa=vexa; this.vexb=vexb; this.weight=weight; } } publicclassprim{ staticEdge[]e={newEdge('a','b',2),newEdge('b','c',1), newEdge('c','d',2),newEdge('d','e',9), newEdge('e','f',4),newEdge('f','g',1), newEdge('g','h',9),newEdge('h','a',1), newEdge('a','i',8),newEdge('b','i',6), newEdge('c','j',3),newEdge('d','k',7), newEdge('e','k',2),newEdge('f','k',1), newEdge('g','j',4),newEdge('h','i',7), newEdge('i','j',1),newEdge('j','k',6)}; staticintw(intx,inty){ charfrom=(char)(x+97); charto=(char)(y+97); for(inti=0;i<18;i++){ if(e[i].vexa==from&&e[i].vexb==to){ returne[i].weight; } if(e[i].vexa==to&&e[i].vexb==from){ returne[i].weight; } } return1000;} publicstaticvoidmain(String[]args){ int[]vex_mst=newint[11]; for(inti=0;i<11;i++) vex_mst[i]=0; vex_mst[0]=1; for(inti=0;i<10;i++){ intadd_vex=0; intmin_weight=1000; Edgeadde=newEdge('','',0); for(intj=0;j<11;j++) if(vex_mst[j]==1){ for(intk=0;k<11;k++){ if(vex_mst[k]==0&&w(j,k) add_vex=k; min_weight=w(j,k); adde.vexa=(char)(j+97); adde.vexb=(char)(k+97); adde.weight=min_weight; } } } vex_mst[add_vex]=1; charavex=(char)(add_vex+97); system.out.println("addedge: "+adde.vexa+"-"+adde.vexb+"w: "+adde.weight); } } } 动画就没有加在里面,你自己做,参数已经给你,你把参数带入就可以,很简单的GUI编程,重要自己学点知识的。 数据结构 1.试用尾插法建立如下单链表: 写出用C语言表示的算法,转化成完整的C程序,并上机调试通过。 解: 答案一 #include structNode { charc; Node*next; }; //创建一系列的节点连接 voidCreateNodes(Node*head) { //临时指针 Node*temp=head->next; for(inti=100;i>=98;--i) { Node*newnode=newNode(); newnode->c=i; head->next=newnode; newnode->next=temp; temp=newnode; } } intmain() { Node*head=newNode(); head->c='a'; head->next=NULL; CreateNodes(head); //输出 for(Node*p=head;p! =NULL;p=p->next) { printf("%c ",p->c); } } 答案二 1 /// 2 /// 创建操作(尾插法创建链表) 3 /// 4 public void CreateListTail() 5 { 6 Node p = head; 7 int d = Int32.Parse(Console.ReadLine()); 8 while(d! =-1) 9 { 10 Node s = new Node(d); 11 if (head == null) 12 { 13 head = s; 14 } 15 else 16 { 17 p.Next = s; 18 } 19 p = s; 20 d = Int32.Parse(Console.ReadLine()); 21 } 22 }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实践 考试 试题 答案