《数据结构》课程教学资源（作业习题）练习题及答案3

1.向量、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素：对于栈只能在 找顶插入和删除元素；对于队列只能在队尾插入和队首时除元素。 6.向栈中压入元素的操作是先移动战顶指针，后在入元素 7.从循环队列中别除一个元素时，其操作是先移动队首指针，后取出元素· (C)1.若己知一个栈的入栈序列是1,2,3，n,其输出序列为pl,p2,p3,.,pn,若pl=n, 则pi为 A i B. D,不确定 解释：当plm,即n是最先出栈的，根据栈的原理，n必定是最后入栈的（事实上题目已经表明了），那 么输入顺序必定是1,2,3，.，n,则出栈的序列是n,.,3,2,1。 (若不要求顺序出栈，则输出序列不确定) (B)2.判定一个栈ST(最多元素为0)为空的条件是 A.ST->top0 B.ST->top-0 C.ST->topm0 D.ST->top-m0 (A)3.判定一个队列QU(最多元素为m0)为满队列的条件是 A.OU->rear -OU->front==mo B.QU->rear-QU->front -1==m0 C.OU->front==QU->rear D.OU->front==OU->rear+l 解：队满条件是元素个数为m0。由于约定满队时队首指针与队尾指针相差1，所以不必再减1了，应当选 A。当然，更正确的答案应该取模，即：QU>-front==(QU>rcar+1)%m 21设有编号为1,2,3,4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的 所有可能的顺序。 刘答：至少有14种. ①全进之后再出情况，只有1种：4,3,2,1 进3个之后再出的情视，有3种3232132， ③进2个之后再出的情况，有5种，2,4,3,12,34,12,1.3.42,1,4,32,1,3.4 ①进1个之后再出的情况.有5种，1.43.213.2.413.421.2.3.41.2.4.3 2.设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有 rear-19 ②ion=19,rea=Il:问在这两种情况下，循环队列中各有元素多少个？ 容：用队列长度计算公式：(N十r一%N (1DL=(40+19-11)%40=8 ②L=(40+11-19)%40=32 3.写出下列程序段的输出结果（栈的元素类型SElem Type为char)。 void main() Stack S; Char x.y. InitStack(S): X='cv=k' Push(S.x).Push(S.a);Push(S.y): Pop(S.x);Push(S,'t);Push(Sx); Pop(S.x):Push(S.'s'): while(IStackEmpty(S))Pop(S,y)printfy):: Printf(x):

1 1. 向量、栈和队列都是 线性 结构，可以在向量的 任何 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素。 6. 向栈中压入元素的操作是先 移动栈顶指针 ，后 存入元素 。 7. 从循环队列中删除一个元素时，其操作是 先 移动队首指针 ，后 取出元素 。 （ C ）1.若已知一个栈的入栈序列是 1，2，3，.，n，其输出序列为 p1，p2，p3，.，pn，若 p1=n， 则 pi 为 Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定 解释：当 p1=n，即 n 是最先出栈的，根据栈的原理，n 必定是最后入栈的（事实上题目已经表明了），那 么输入顺序必定是 1，2，3，.，n，则出栈的序列是 n，.，3，2，1。 （若不要求顺序出栈，则输出序列不确定） （ B ）2.判定一个栈 ST（最多元素为 m0）为空的条件是 Ａ．ST->top<>0 Ｂ．ST->top=0 Ｃ．ST->top<>m0 Ｄ．ST->top=m0 （ A ）3.判定一个队列 QU（最多元素为 m0）为满队列的条件是 Ａ．QU->rear － QU->front = = m0 Ｂ．QU->rear － QU->front －1= = m0 Ｃ．QU->front = = QU->rear Ｄ．QU->front = = QU->rear+1 解：队满条件是元素个数为 m0。由于约定满队时队首指针与队尾指针相差 1，所以不必再减 1 了，应当选 A。当然，更正确的答案应该取模，即：QU->front = = (QU->rear+1)% m0 21.设有编号为 1，2，3，4 的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的 所有可能的顺序。 刘答：至少有 14 种。 ① 全进之后再出情况，只有 1 种：4，3，2，1 ② 进 3 个之后再出的情况，有 3 种，3,4,2,1 3,2,4,1 3,2,1,4 ③ 进 2 个之后再出的情况，有 5 种，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4 ④ 进 1 个之后再出的情况，有 5 种，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,3 2.设循环队列的容量为 40（序号从 0 到 39），现经过一系列的入队和出队运算后，有 ① front=11，rear=19; ② front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？ 答：用队列长度计算公式： (N＋r－f)% N ① L=（40＋19－11）% 40=8 ② L=（40＋11－19）% 40=32 3.写出下列程序段的输出结果（栈的元素类型 SElem Type 为 char）。 void main( ){ Stack S; Char x,y; InitStack(S); X=’c’;y=’k’; Push(S,x); Push(S,’a’); Push(S,y); Pop(S,x); Push(S,’t’); Push(S,x); Pop(S,x); Push(S,’s’); while(!StackEmpty(S)){ Pop(S,y);printf(y); }; Printf(x); }

答：输出为“sack”。 2.写出下列程序段的输出结果（队列中的元素类型QElem Typ为char)。 void main() Queue O:Init Queue(O) Char x='e'v='c' EnQueue(Q,'h');EnQueue(Q.'r')EnQueue(Q,y). DeQueue(Q.x).EnQueue(Q.x) DeQueue(Q.x):EnQueue(Q.'a'), while(!QueueEmpty(Q)){DeQueue(Q.y);printf(y);); Printf(x): 答：输出为“char”。 3.简述以下算法的功能（栈和队列的元素类型均为t)。 void algo3(Queue&Q) Stack S:int d: InitStack(S) while(1QueueEmpty(Q)f DeQueue (Q.d):Push(S,d): while(!StackEmpty(S)) Pop(S.d):EnQueue(Q.d): 答：该算法的功能是：利用堆栈做辅助，将队列中的数据元素进行逆置

2 答：输出为“stack”。 2. 写出下列程序段的输出结果（队列中的元素类型 QElem Type 为 char）。 void main( ){ Queue Q; Init Queue (Q); Char x=’e’; y=’c’; EnQueue (Q,’h’); EnQueue (Q,’r’); EnQueue (Q, y); DeQueue (Q,x); EnQueue (Q,x); DeQueue (Q,x); EnQueue (Q,’a’); while(!QueueEmpty(Q)){ DeQueue (Q,y);printf(y); }; Printf(x); } 答：输出为“char”。 3. 简述以下算法的功能（栈和队列的元素类型均为 int）。 void algo3(Queue &Q){ Stack S; int d; InitStack(S); while(!QueueEmpty(Q)){ DeQueue (Q,d); Push(S,d); }; while(!StackEmpty(S)){ Pop(S,d); EnQueue (Q,d); } } 答：该算法的功能是：利用堆栈做辅助，将队列中的数据元素进行逆置