PTA数据结构与算法-第三章——栈与队列

时间：2025-03-14 07:00:43

文章目录

  • 第一章——褚论
  • 第二章——线性表
  • 第三章——栈与队列
  • 第四章——字符串
  • 第五章——树与二叉树
  • 第六章——图
  • 第七章——排序
  • 第八章——检索
    • 判断题
    • 单选题
    • 程序填空题

第一章——褚论

第二章——线性表

第三章——栈与队列

第四章——字符串

第五章——树与二叉树

第六章——图

第七章——排序

第八章——检索

判断题

  • 所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。
    F错误。将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）
  • An algorithm to check for balancing symbols in an expression uses a stack to store the symbols.
    T

balancing symbols 指的是一组匹配的符号，类似于圆括号，花括号，方括号。
可见这道题的意思是求解逆波兰表达式，使用stack。对。

  • 在n个元素连续进栈以后，它们的出栈顺序和进栈顺序一定正好相反。
    T
  • n个元素通过一个栈产生n个元素的出栈序列，其中进栈和出栈操作的次数总是相等的。
    T
  • 通过对堆栈S操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为：123。
    F 231
  • 在用数组表示的循环队列中，front值一定小于等于rear值。
    F
  • "Circular Queue" is defined to be a queue implemented by a circularly linked list or a circular array.
    F 中文版即是第一个题。
  • n个元素进队的顺序和出队的顺序总是一致的。
    T 队列即为FIFO（先进先出，故一致）
  • 栈底元素是不能删除的元素。
    F 可以删除
  • 顺序栈中元素值的大小是有序的。
    这里顺序的意思是顺序存储结构，而不代表存储元素一定有序。
  • 栈顶元素和栈底元素有可能是冋一个元素。
    T
  • 栈是一种对进栈、出栈操作总次数做了限制的线性表。
    F 没有限制
  • 对顺序栈进行进栈、出栈操作不涉及元素的前、后移动问题。
    T
  • 环形队列中有多少个元素可以根据队首指针和队尾指针的值来计算。
    T 公式为(rear-front+maxsize)%maxsize
  • 若采用“队首指针和队尾指针的值相等”作为环形队列为空的标志，则在设置一个空队时只需将队首指针和队尾指针赋同一个值，不管什么值都可以。
    T
  • 栈和队列的插入和删除操作特殊，所以，栈和队列是非线性结构。
    F
  • 两个栈共享一片连续空间，可以将两个栈的栈底分别设在这片空间的两端。
    T
  • 不论是入队还是入栈操作，在顺序存储结构下都应考虑溢出现象。
    T
  • 可以通过少用一个存储空间的方法解决循环队列假溢出现象
    F

少用一个存储空间的方法是为了解决无法判别队列满还是空。
而克服"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。

单选题

  • 设一个栈的输入序列是1、2、3、4、5，则下列序列中，是栈的合法输出序列的是？
    3 2 1 5 4
    5 1 2 3 4
    4 5 1 3 2
    4 3 1 2 5
  • 下列关于栈的叙述中，错误的是：
    1采用非递归方式重写递归程序时必须使用栈
    2函数调用时，系统要用栈保存必要的信息
    3只要确定了入栈次序，即可确定出栈次序
    4栈是一种受限的线性表，允许在其两端进行操作
    仅 1
    仅 1、2、3
    仅 1、3、4
    仅 2、3、4
  • 循环顺序队列中是否可以插入下一个元素（）。
    与队头指针和队尾指针的值有关
    只与队尾指针的值有关，与队头指针的值无关
    只与数组大小有关，与队首指针和队尾指针的值无关
    与曾经进行过多少次插入操作有关
  • 设一个堆栈的入栈顺序是1、2、3、4、5。若第一个出栈的元素是4，则最后一个出栈的元素必定是：
    1
    3
    5
    1或者5
    5要是在1出栈前入栈，则最后一个出栈的元素就是1。也可以在4321的顺序出栈完毕后，5入栈，再出栈，即最后一个出栈的元素是5.
    综上，最后一个出栈的元素是1或5.
  • 设栈S和队列Q的初始状态均为空，元素{1, 2, 3, 4, 5, 6, 7}依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是{2, 5, 6, 4, 7, 3, 1}，则栈S的容量至少是：
    1
    2
    3
    =4
  • 若借助堆栈将中缀表达式a+bc+(de+f)g转换为后缀表达式，当读入f时，堆栈里的内容是什么(按堆栈自底向上顺序)
    +(*+
    +(+
    ++(+
    abcde
  • 表达式a(b+c)-d的后缀表达式是:
    a b c + * d -
    a b c d * + -
    a b c * + d -
    -+* a b c d

转换方法：
1)先按照运算符的优先级对中缀表达式加括号，变成
((a*(b+c))-d)
2)将运算符移到括号的后面，变成((a(bc)+)* d)-
3)去掉括号，得到abc+*d-

  • 若采用带头、尾指针的单向链表表示一个堆栈，那么该堆栈的栈顶指针top应该如何设置？
    将链表头设为top
    将链表尾设为top
    随便哪端作为top都可以
    链表头、尾都不适合作为top
    这里头尾指针是链表的，和栈没关系，即头指针≠栈底，尾指针≠栈顶。
    出栈入栈都是针对栈顶元素进行的操作，考虑到这个链表是单项的（从前往后不能从后往前），所以把头指针设成top，这样出栈入栈就是对表头操作，时间上快很多。
  • 利用大小为n的数组（下标从0到n-1）存储一个栈时，假定栈从数组另一头开始且top==n表示栈空，则向这个栈插入一个元素时，修改top指针应当执行:
    top=0
    top++
    top–
    top不变
  • 若已知一队列用单向链表表示，该单向链表的当前状态（含3个对象）是：1->2->3，其中x->y表示x的下一节点是y。此时，如果将对象4入队，然后队列头的对象出队，则单向链表的状态是：
    1->2->3
    2->3->4
    4->1->2
    答案不唯一
  • 若用一个大小为6的数组来实现循环队列，且当前rear和fornt的值分别为0和3。从当前队列中删除一个元素，再加入两个元素后，rear和front的值分别为（ ）。
    1和5
    2和4
    4和2
    5和1
    这里注意队列是FIFO，删除一个元素时，从队头出队，即front+=1，front=4，加入两个元素，rear+=2，rear=2；
  • 判断一个循环队列QU（最多元素为MaxSize）为空的条件是（）。
    ==
    !=
    == ( + 1) % MaxSize
    != ( + 1) % MaxSize
    判断一个循环队列QU为满队列的条件是
    == (+1)%MaxSize

Suppose that all the integer operands are stored in the stack S1, and all the operators in the other stack S2​​ . The function F() does the following operations sequentially:

(1) Pop two operands a and b from S​1​​ ;
(2) Pop one operator op from S​2​​ ;
(3) Calculate b op a; and
(4) Push the result back to S​1 .
Now given { 5, 8, 3, 2 } in S1 (where 2 is at the top), and { *, -, + } in S2 (where + is at the top). What is remained at the top of S1 after F() is executed 3 times?
-15
15
-20
20
第一次执行F（），弹出a=2，b=3，弹出op为+，计算3+2=5并把5重新压回栈S1中。
第二次执行，弹出a=5，b=8，op为-，计算8-5=3，把3压回栈中。
第三次执行，弹出a=3，b=5，op为 * ，计算5 *3=15，并把15压回栈中

  • 假定利用数组a[n]顺序存储一个栈，用top表示栈顶指针，用top==-1表示栈空，并已知栈未满，当元素x进栈时所执行的操作为（　）。
    a[–top]=x
    a[top–]=x
    a[++top]=x
    a[top++]=x
  • 经过以下栈的操作后，变量x的值为（　）。
    InitStack(st);Push(st,a);Push(st,b);Pop(st,x);Top(st,x);
    a
    b
    NULL
    FALSE
  • 若已知一个栈的入栈序列是1，2，3，4，其出栈序列为P1，P2,P3,P4,则P2，P4不可能是（ ）
    2,4
    2,1
    4,3
    3,4
    4先出栈的情况下，3必须在它后一个出栈，而中间不可能是别的元素出栈
  • 设有一个顺序共享栈Share[0:n-1]，其中第一个栈顶指针top1的初值为－1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是（　）。
    top2-top1==1
    top1-top21
    top1    top2
    以上都不对
  • 循环队列放在一维数组A[0…M-1]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。初始时为空。下列判断队空和队满的条件中，正确的是（　）。
    队空：end1== end2;队满：end1==(end2+1)mod M
    队空：end1== end2;队满：end2==(end1+1)mod (M-1)
    队空：end2==(end1+1) mod M;队满：end1==(end2+1) mod M
    队空：end1==(end2+1) mod M;队满：end2==(end1+1)mod (M-1)
  • 下列说法中，正确的是（　）。
    消除递归不一定需要使用栈
    对同一输入序列进行两组不同的合法入栈和出栈组合操作，所得的输出序列也一定相同
    通常使用队列来处理函数或过程调用
    队列和栈都是运算受限的线性表，只允许在表的两端进行运算
  • 数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（ ）。
    r-f
    (n+f-r)%n
    n+r-f
    （n+r-f)%n
  • 设有一个递归算法如下 int fact(int n) { //n大于等于0 if(n<=0) return 1; else return n * fact(n-1);
    } 则计算fact(n)需要调用该函数的次数为（ ）。
    n+1
    n-1
    n
    n+2
    直接假设代入，假设n=1，易得fact调用了两次。故选n+1。
  • 若一个栈以向量V[1…n]存储，初始栈顶指针top设为n+1，则元素x进栈的正确操作是( )。
    top++; V[top]=x;
    V[top]=x; top++;
    top–; V[top]=x;
    V[top]=x; top–;
  • 下列与队列结构有关联的是
    函数的递归调用
    数组元素的引用
    多重循环的执行
    先到先服务的作业调度

程序填空题

  • 本题要求求出不带头结点的单链表中的最大值并返回。
/* 求单链表值最大的结点 */
int getMaxNode(LinkNode* head)
{
	if (head == NULL)
		return INT_MIN;
	int first = head->data;
	int m = 
getMaxNode(head->next)
;
	if (m > first)return m;
	else return first;
}

getMaxNode(head->next)

  • 本题要求采用递归方式求不带头结点的单链表的长度。
    其中, 单链表结点类型定义如下:
typedef struct LNode {
	int data;
	struct LNode* next;
} LinkNode;
///求单链表长度
int getLength(LinkNode* L) {
	if (L == NULL)
		return 0;
	return 
1 + getLength(L->next)
;
}

1 + getLength(L->next)

已知循环队列的结构定义如下：

typedef struct
{
    int size, front, rear;
    int *element;
} AQUEUE;

说明：element 为存储队列数据元素的动态数组，size 为动态数组的尺寸，front 为队首元素的下标，rear 为队尾元素下一位置的下标。

假设有以下定义：
AQUEUE *queue;
判断 queue 所指队列为空的条件是：
queue->front == queue->rear
判断 queue 所指队列为满的条件是：
(queue->rear + 1) % queue->size == queue->front
queue 所指队列的长度是：
(queue->rear - queue->front + queue->size) % queue->size

相关文章