做网站高校视频,辽宁城乡住房建设厅网站首页,做外贸网站机构,网页微信版官网登录下载文章目录 主要内容一.队列基础练习题1.用链式存储方式的队列进行删除操作时需要 ( D ).代码如下#xff08;示例#xff09;: 2.若以1,2,3,4作为双端队列的输入序列#xff0c;则既不能由输入受限的双端队列得到#xff0c;又不能由输出受限的双端队列得到的输出序列是( C … 文章目录 主要内容一.队列基础练习题1.用链式存储方式的队列进行删除操作时需要 ( D ).代码如下示例: 2.若以1,2,3,4作为双端队列的输入序列则既不能由输入受限的双端队列得到又不能由输出受限的双端队列得到的输出序列是( C )代码如下示例: 3.现有队列Q与栈 S,初始时Q中的元素依次是 1,2.3,,5,6(1在队头).S 为空。若仅允许下列3 种操作: (1) 出队并输出出队元素;(2)出队并将出队元素入栈:(3)出栈并输出出栈元素则不能得到的输出序列是 ( C )。代码如下示例: 4.Q是一个队列S 是一个空栈实现将队列中的元素逆置的算法代码如下示例: 5.利用两个栈 S1S2来模拟一个队列已知栈的4个运算定义如下:代码如下示例: 总结 主要内容
队列基础练习题
一.队列基础练习题 1.用链式存储方式的队列进行删除操作时需要 ( D ).
A.仅修改头指针 B.仅修改尾指针 C.头尾指针都要修改 D.头尾指针可能都要修改
代码如下示例:
队列用链式存储时删除元素从表头删除通常仅需修改头指针
但若队列中仅有一个元素则尾指针也需要被修改
当仅有一个元素时删除后队列为空需修改尾指针为 rearfront。2.若以1,2,3,4作为双端队列的输入序列则既不能由输入受限的双端队列得到又不能由输出受限的双端队列得到的输出序列是( C )
A.1,2,3,4 B.4,1,3,2 C.4,2,3,1 D.4,2,1,3
代码如下示例:
使用排除法。先看可由输入受限的双端队列产生的序列:
设右端输入受限1,2,3,4 依次左入则依次左出可得 4,3,2,1排除 A;
右出、左出、右出、右出可得到4,1,3,2排除 B;
再看可由输出受限的双端队列产生的序列:
设右端输出受限1,2,3,4 依次左入、左入、右入、左入依次左出可得到 4,2,1,3排除 D3.现有队列Q与栈 S,初始时Q中的元素依次是 1,2.3,5,6(1在队头).S 为空。若仅允许下列3 种操作: (1) 出队并输出出队元素;(2)出队并将出队元素入栈:(3)出栈并输出出栈元素则不能得到的输出序列是 ( C )。
A.1,2,5,6,4,3 B.2,3,4,5,6,1 C.3,4,5,6,1,2 D.6,5,4,3,2,1
代码如下示例:
A 的操作顺序为11221133。
B 的操作顺序为2111113。
D 的操作顺序为22222133333。
对于 C: 首先输出3说明 1和2 必须先依次入栈而此后2肯定比1先输出
因此无法得到 1,2的输出顺序4.Q是一个队列S 是一个空栈实现将队列中的元素逆置的算法
代码如下示例:
本题主要考查对队列和栈的特性与操作的理解。
由于对队列的一系列操作不可能将其中的元素逆置而栈可以将入栈的元素逆序提取出来
因此我们可以让队列中的元素逐个地出队列入栈;全部入栈后再逐个出栈入队列。void Inverser(Stack S,Queue Q){
//本算法实现将队列中的元素逆置while(!QueueEmpty(Q)){xDeQueue(O); //队列中全部元素依次出队Push(Sx); //元素依次入栈}while(!StackEmpty(S)){PoP(S,x); //栈中全部元素依次出栈EnQueue(Qx); //再入队}
}
5.利用两个栈 S1S2来模拟一个队列已知栈的4个运算定义如下:
Push(S,x); //元素x入栈s
Pop(S,x); //s出栈并将出栈的值赋给 x
StackEmpty(s); //判断栈是否为空
StackOverflow(S); //判断栈是否满如何利用栈的运算来实现该队列的 3 个运算(形参由读者根据要求自己设计)?
Enqueue; //将元素x入队
Dequeue; //出队并将出队元素存储在x中
QueueEmpty; //判断队列是否代码如下示例:
利用两个栈S1和 s2来模拟一个队列当需要向队列中插入一个元素时
用S1 来存放已输入的元素即 S1 执行入栈操作。
当需要出队时则对 S2 执行出操作。
由于从栈中取出元素的顺序是原顺序的逆序所以必须先将 S1 中的所有元素全部出栈并入栈到 S2 中
再在 S2 中执行出栈操作即可实现出队操作
而在执行此操作前必须判断 S2 是否为空否则会导致顺序混乱。当栈S1和s2都为空时队列为空。总结如下:
1)对S2的出找操作用做出队若s2为空则先将是s1中的所有元素送入s2
2)对 s1的入操作用作入队若 S1 满必须先保证s2为空才能将s1中的元素全部插入S2中。入队算法
入队算法int EnQueue(Stack Sl,Stack S2,ElemType e){if(!stackOverflow(s1)){Push(S1,e);return 1;}if(StackOverflow(S1)!StackEmpty(s2)){printf(队列满);return 0;}if(StackOveflow(S1)sStackEmpty(S2)){while(!stackEmpty(S1)){Pop(S1.x);Push(S2,x);}}Push(s1,e);return 1;
}出队算法
void DeQueue(Stack S1,Stack S2,ElemType x){if(!StackEmpty(s2)){Pop(S2x);}else if(StackEmpty(S1)){printf(队列为空);}else{while(!stackEmpty(S1)){Pop(S1,x);Push(S2x);}Pop(S2,x);}
}判断队列为空的算法
int QueueEmpty(Stack Sl,Stack s2){if(StackEmpty(s1)StackEmpty(S2))return 1;elsereturn 0;
}总结
以上是今天要讲的内容练习了线性表–队列的相关习题。
