实践考试试题及答案.docx
- 文档编号:6736278
- 上传时间:2023-05-10
- 格式:DOCX
- 页数:13
- 大小:152.49KB
实践考试试题及答案.docx
《实践考试试题及答案.docx》由会员分享,可在线阅读,更多相关《实践考试试题及答案.docx(13页珍藏版)》请在冰点文库上搜索。
实践考试试题及答案
操作系统
1.有3个进程PA、PB和PC协作解决文件打印问题:
PA将文件记录从磁盘读入主存的缓冲区1,每执行一次读一个记录;PB将缓冲区1的内存复制到缓冲区2,每执行一次复制一个记录;PC将缓冲区2的内容打印出来,每执行一次打印一个记录,缓冲区的大小和一个记录大小一样,请用进程通讯或操作方式来保证文件的正确打印。
解:
答案一
答案二
定义信号量:
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算法,并用动画的方式表示最小生成树的生成过程。
解:
import.*;
publicclassMain{
staticintMAXCOST=;
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; } } /*输出生成树边的信息: 起点,终点,权值*/ "%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; intcost; charchx,chy; /*读取节点和边的数目*/ intn=();harAt(0); chy=().charAt(0); cost=(); inti=chx-'A'+1; intj=chy-'A'+1; graph[i][j]=cost; graph[j][i]=cost; } /*求解最小生成树*/ cost=Prim(graph,n); /*输出最小权值和*/ "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]=; } 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++) +""); } 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){ =vexa; =vexb; =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); =(char)(j+97); =(char)(k+97); =min_weight; } } } vex_mst[add_vex]=1; charavex=(char)(add_vex+97); "addedge: "++"-"++"w: "+; } } } 动画就没有加在里面,你自己做,参数已经给你,你把参数带入就可以,很简单的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/// 4publicvoidCreateListTail() 5{ 6Nodep=head; 7intd=()); 8while(d! =-1) 9{ 10Nodes=newNode(d); 11if(head==null) 12{ 13head=s; 14} 15else 16{ 17=s; 18} 19p=s; 20d=()); 21} 22}
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实践 考试 试题 答案