基本概念题: 什么叫堆栈?什么叫队列? 3-2线性表、堆栈和队列这三种抽象数据类型有什么相同之处和不同之处? 3-3在顺序队列中,什么叫真溢出?什么叫假溢出?为什么顺序队列通常都采用顺序循 环队列结构? 3-4什么叫优先级队列?优先级队列和队列有什么相同之处和不同之处? 3-5举例说明堆栈、队列和优先级队列的用途。 复杂概念题: 3-6设数据元素序列{ a, b, c, d, e, f.,g}的进堆栈操作和出堆栈操作可任意进行(排除堆栈 为空时的出堆栈操作情况),下列哪些数据元素序列可由出堆栈序列得到: (1){d,e,c,f,b,g,a} D)f,e, g,d, a, c, b; (3){e,f,d,g,b,c,a} (4){c,d,b,e,f,a,g} 3-7画出借助堆栈把下列中缀表达式转换成后缀表达式的过程 A*(B-D)+E/F 3-8对于一个堆栈 (1)如果输入序列由A,B,C,D组成,试给出全部可能的输出序列和不可能的输出序列。 (2)设有n个数据元素的序列顺序进栈,试给出可能的输出序列个数。 (3)设有n个数据元素的序列顺序进栈,试给出不可能的输出序列个数。 (4)以n=4为例,用(2)和(3)中得出的公式验证(1)的结论。 算法设计题 3-9编写一个判断算术表达式中开括号和闭括号是否配对的算法 3-10给出采用设置标志位的方法解决“假溢出”问题的顺序循环队列的初始化操作、入 队列操作和出队列操作的算法思想。 3-11设计采用设置标志位方法解决“假溢出”问题的顺序循环队列的初始化操作、入队 列操作和出队列操作的函数。 3-12仿照例3-3,编程序判断一个字符序列是否是回文,要求采用链式队列和链式堆栈 3-13编程序判断一个字符序列是否是回文,要求只使用堆栈,不使用队列。 3-14编写一个顺序优先级队列的出队列操作算法,要求不考虑相同优先级时的先进先出 原则。 3-15设顺序双向循环队列的数据结构定义为: typedef struct Data Type list [MaxSize] int front /*队头指针* nt rear /*队尾指针*/ 设Q为 BSeqCQueue类型的变参,并设初始化操作时有:Q>rear=Q- front=0,现要求: (1)给出顺序双向循环队列满和空的条件 (2)给出顺序双向循环队列的入队列操作和出队列操作算法思想 *(3)设计顺序双向循环队列的入队列操作和出队列操作算法。 *3-16假设算术表达式由单字母变量和加(+)、减(-)、乘(*)、除(\)运算符组成, 编写一个函数把中缀表达式转换为后缀表达式。为使问题简化,可不考虑中缀表达式不正确
基本概念题： 3-1 什么叫堆栈？什么叫队列？ 3-2 线性表、堆栈和队列这三种抽象数据类型有什么相同之处和不同之处？ 3-3 在顺序队列中，什么叫真溢出？什么叫假溢出？为什么顺序队列通常都采用顺序循 环队列结构？ 3-4 什么叫优先级队列？优先级队列和队列有什么相同之处和不同之处？ 3-5 举例说明堆栈、队列和优先级队列的用途。 复杂概念题： 3-6 设数据元素序列{a, b, c, d, e, f, g}的进堆栈操作和出堆栈操作可任意进行（排除堆栈 为空时的出堆栈操作情况），下列哪些数据元素序列可由出堆栈序列得到： （1）{d, e, c, f, b, g, a}; （2）{f, e, g, d, a, c, b}; （3）{e, f, d, g, b, c, a}; （4）{c, d, b, e, f, a, g} 3-7 画出借助堆栈把下列中缀表达式转换成后缀表达式的过程： A * (B - D) + E / F 3-8 对于一个堆栈， （1）如果输入序列由 A,B,C,D 组成，试给出全部可能的输出序列和不可能的输出序列。 （2）设有 n 个数据元素的序列顺序进栈，试给出可能的输出序列个数。 （3）设有 n 个数据元素的序列顺序进栈，试给出不可能的输出序列个数。 （4）以 n=4 为例，用（2）和（3）中得出的公式验证（1）的结论。 算法设计题： 3-9 编写一个判断算术表达式中开括号和闭括号是否配对的算法。 3-10 给出采用设置标志位的方法解决“假溢出”问题的顺序循环队列的初始化操作、入 队列操作和出队列操作的算法思想。 3-11 设计采用设置标志位方法解决“假溢出”问题的顺序循环队列的初始化操作、入队 列操作和出队列操作的函数。 3-12 仿照例 3-3，编程序判断一个字符序列是否是回文，要求采用链式队列和链式堆栈。 3-13 编程序判断一个字符序列是否是回文，要求只使用堆栈，不使用队列。 3-14 编写一个顺序优先级队列的出队列操作算法，要求不考虑相同优先级时的先进先出 原则。 3-15 设顺序双向循环队列的数据结构定义为： typedef struct { DataType list[MaxSize]; int front; /*队头指针*/ int rear; /*队尾指针*/ } BSeqCQueue; 设 Q 为 BSeqCQueue 类型的变参，并设初始化操作时有：Q->rear = Q->front = 0，现要求： （1）给出顺序双向循环队列满和空的条件。 （2）给出顺序双向循环队列的入队列操作和出队列操作算法思想。 *（3）设计顺序双向循环队列的入队列操作和出队列操作算法。 *3-16 假设算术表达式由单字母变量和加（+）、减（-）、乘（*）、除（\）运算符组成， 编写一个函数把中缀表达式转换为后缀表达式。为使问题简化，可不考虑中缀表达式不正确
的情况。 *3-17假设算术表达式由单字母变量和加(+)、减(-)、乘(*)、除()运算符组成, 编写一个函数对以后缀表达式表示的算术表达式求值。为使问题简化,可不考虑后缀表达式 不正确的情况。 上机实习题 3-18链式堆栈设计。要求: (1)用链式堆栈设计实现堆栈,堆栈的操作集合包括:初始化 StackInitiate(S)、非空否 Stack NotEmpty(S)、入栈 Stack Push(S,x)、出栈 Stack Pop(S,d、取栈顶数据元素 StackTop(S, d)。 (2)设计一个主函数对链式堆栈进行测试。测试方法为:依次把数据元素1,2,3,4, 5入栈,然后出栈堆栈中的数据元素并在屏幕上显示。 (3)定义数据元素的数据类型为如下形式的结构体, typedef struct har task Name[ 10]: /*任务名* t taskNo /*任务号* i Data Type 首先设计一个包含5个数据元素的测试数据,然后设计一个主函数对链式堆栈进行测试。测 试方法为:依次把5个数据元素入栈,然后出栈堆栈中的数据元素并在屏幕上显示 3-19对顺序循环队列,常规的设计方法是使用队尾指针和队头指针,队尾指针用于指示 当前的队尾位置下标,队头指针用于指示当前的队头位置下标。现要求: (1)设计一个使用队头指针和计数器的顺序循环队列抽象数据类型,其中操作包括初 始化、入队列、出队列、取队头元素和判队列是否非空。 (2)编写一个主函数进行测试
的情况。 *3-17 假设算术表达式由单字母变量和加（+）、减（-）、乘（*）、除（\）运算符组成， 编写一个函数对以后缀表达式表示的算术表达式求值。为使问题简化，可不考虑后缀表达式 不正确的情况。 上机实习题： 3-18 链式堆栈设计。要求： （1）用链式堆栈设计实现堆栈，堆栈的操作集合包括：初始化 StackInitiate(S)、非空否 StackNotEmpty(S)、入栈 StackPush(S, x)、出栈 StackPop(S, d)、取栈顶数据元素 StackTop(S, d）。 （2）设计一个主函数对链式堆栈进行测试。测试方法为：依次把数据元素 1，2，3，4， 5 入栈，然后出栈堆栈中的数据元素并在屏幕上显示。 （3）定义数据元素的数据类型为如下形式的结构体， typedef struct { char taskName[10]; /*任务名*/ int taskNo; /*任务号*/ } DataType; 首先设计一个包含 5 个数据元素的测试数据，然后设计一个主函数对链式堆栈进行测试。测 试方法为：依次把 5 个数据元素入栈，然后出栈堆栈中的数据元素并在屏幕上显示。 3-19 对顺序循环队列，常规的设计方法是使用队尾指针和队头指针，队尾指针用于指示 当前的队尾位置下标，队头指针用于指示当前的队头位置下标。现要求： （1）设计一个使用队头指针和计数器的顺序循环队列抽象数据类型，其中操作包括初 始化、入队列、出队列、取队头元素和判队列是否非空。 （2）编写一个主函数进行测试