数据结构实验二求解约瑟夫问题.doc

《数据结构实验二求解约瑟夫问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构实验二求解约瑟夫问题问题描述：使用代表头节点的循环单链表解决此问题。设有n个人围坐在一张圆桌周围，现从某个人开始从1报数，数到m的人离开。接着从出列的下一个人开始重新从1开始报数，数到m的人又出列，如此下去直到所有的人都出列为止。求出他们的出列序列。问题分析：例如，当n=8,m=4时，若从第一个人开始报数（设从1开始编号），则得到的序列是：4，8，5，2，1，3，7，6。算法：voidJosephus(intn,intm,ints){//生成表头节点，空单循环链表LNode*HL=newLNode;HL->next=HL;inti

2、;//生成含有n个节点的、节点值依次为1，2……，n的带表头节点的循环单链表For(i=n;i>=1;i--){LNode*newptr=newLNode;Newptr->data=i;newptr->next=HL->next;HL->next=newptr;}//从表头开始顺序查找出第s个节点，对应第一个开始报数的人LNode*ap=HL,*cp=HL->next;for(i=1;inext;if(cp==HL){ap=HL;cp=HL->next;}}//依次使n-1个人出列for(i=1;

3、inext;if(cp==HL){ap=HL;cp=HL->next;}}//输出cp节点的值，即出列的人cout<data<<”“;//从单链表中删除cp节点ap->next=cp->next;deletecp;//使cp指向被删除节点的后续节点cp=ap->next;//若cp指向了表头节点，则后移ap和cp指针if(cp==HL){ap=HL;cp=HL->next;}}//使最后一人出

4、列count<next->data<next;deleteHL;}补充操作系统练习：1、有一个虚拟存储系统,每个进程在内存占有3页数据区、1页程序区.刚开始时数据区为空.有以下访页序列:1、5、4、1、2、3、2、1、5、4、2、4、6、5、1试给出下列情形下的缺页次数:(1)系统采用先进先出(FIFO)淘汰算法.(2)系统采用最近最少使用(LRU)淘汰算法.(3)若采用优化(OPT)淘汰算法呢?2、设系统中有三类资源A、B和C，又设系统中有5个进程P1，P2，P3，

5、P4和P5.在T0时刻系统状态如下：最大需求量已分配资源量剩余资源量ABCABCABCP1864121211P2433311P31013413P4333322P5546113(1)系统是否处于安全状态？如是，则给出进程安全序列.(2)如果进程P5申请1个资源类A、1个资源类B和1个资源类C，能否实施分配？为什么？3、在一个两道的批处理操作系统中，有6个作业进入系统，它们的进入时刻、估计运行时间和优先级如下表所示.作业号进入时刻估计运行时间优先级JOB18：0090分钟5JOB28：1030分钟6JOB38：3020分钟3JOB48：501

6、5分钟8JOB59：2010分钟2JOB69：405分钟4系统采用短作业优先作业调度算法，作业一旦被调度运行就不再退出.但当有新的作业投入运行时，可以按照优先级进行进程调度.（1）试给出各个作业的运行时间序列.（例如：JOB1：8：00-8：30，9：10-9：20，…）（2）试计算出作业的平均周转时间.