问答题
请设计一个队列，要求满足：①初始时队列为空；②入队时，允许增加队列占用空间；③出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减；④入队操作和出队操作的时间复杂度始终保持为O(l)。请回答下列问题：
问答题
该队列应该选择链式存储结构，还是顺序存储结构?
【正确答案】采用链式存储结构(两段式单向循环链表)，队头指针为front队尾指针为rear。
【答案解析】
问答题
画出队列的初始状态，并给出判断队空和队满的条件
【正确答案】初始时，创建只有一个空闲结点的两段式单向循环链表，头指针front与尾指针rear均指向空闲结点。如下图所示。 队空的判定条件：front==rear。 队满的判定条件：front==rear-＞next。
【答案解析】
【正确答案】插入第一个元素后的队列状志：
【答案解析】
【正确答案】操作的基本过程 入队操作： 若(front==rear-＞near) //队满 则在rear后面插入一个新的空闲结点； 入队元素保存到rear所指结点中；rear=rear=-＞next; 返回 出队操作： 若(front==rear) //队空 则出队失败，返回 取front所指结点中的元素e;front=front=-＞next;返回e。
【答案解析】
问答题
有n(n≥3)位哲学家围坐在一张圆桌边，每位哲学家交替地就餐和思考。在圆桌中心有m(m≥1)个碗，每两位哲学家之间有1根筷子。每位哲学家必须取到一个碗和两侧的筷子之后，才能就餐，进餐完毕，将碗和筷子放同原位，并继续思考。为使尽可能多的哲学家同时就餐，且防止出现死锁现象，请使用信号量的p、v操作(wait()、signal()操作)描述上述过程中的互斥与同步，并说明所用信号量及初值的含义。
【正确答案】//信号量 semaphore bowl; //用于协调哲学家对碗的使用 semaphore chopsticks[n]; //用于协调哲学家对筷子的使用 for(int i=0;i＜n;i++) chopsticks[i]value=1; //设置两个哲学家之间筷子的数最 bowl.value=min(n-1,m); //bowl.value≤n-1,确保不死锁 CoBegin while(True){ //哲学家i的程序 思考; P(bowl); //取碗 P(chopsticks[i]); //取左边筷子 P(chopsticks[(i+I)MOD n]);//取右边筷子 就餐; V(chopsticks[i]); V(chopslicks[(i+1)MOD n]); V(bowl); } CoEnd
【答案解析】