第 3 章 特殊线性表——栈、队列和串 (2005-07-14) - 第 3 章 特殊线性表——栈、队列和串 课后习题讲解 1. 填空 ⑴ 设有一个空栈，栈顶指针为1000H，现有输入序列为1、2、3、4、5， 经过 push，push，pop，push，pop，push，push后，输出序列是（ ），栈顶指针为（ ）。 【解答】23，1003H ⑵ 栈通常采用的两种存储结构是（ ）；其判定栈空的条件分别是（ ），判定栈满的条件分别是（ ）。 【解答】顺序存储结构和链接存储结构（或顺序栈和链栈），栈顶指针top= -1和top=NULL，栈顶指针top等于数 组的长度和内存无可用空间 ⑶（ ）可作为实现递归函数调用的一种数据结构。 【解答】栈 【分析】递归函数的调用和返回正好符合后进先出性。 ⑷ 表达式a*(b+c)-d的后缀表达式是（ ）。 【解答】abc+*d- 【分析】将中缀表达式变为后缀表达式有一个技巧：将操作数依次写下来，再将算符插在它的两个操作数的后面 。 ⑸ 栈和队列是两种特殊的线性表，栈的操作特性是（ ），队列的操作特性是（ ），栈和队列的主要区别在于（ ）。 【解答】后进先出，先进先出，对插入和删除操作限定的位置不同 ⑹ 循环队列的引入是为了克服（ ）。 【解答】假溢出 ⑺ 数组Q[n]用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素的位置，计算队列中元素 个数的公式为（ ）。 page: 2 The Home of jetmambo - 第 3 章 特殊线性表——栈、队列和串 【解答】（rear-front+n）% n 【分析】也可以是（rear-front）% n，但rear-front的结果可能是负整数，而对一个负整数求模，其结果在不同 的编 译 器 环境 下可能会 有所 不同。 ⑻ 用循环链表表示的队列长度为n，若 只 设头指针，则 出队和入队的时 间复 杂 度分别是（ ）和（ ）。 【解答】Ｏ (1)，Ｏ (n) 【分析】在带 头指针的循环链表中，出队即 是删除开 始 结点 ，这 只 需 修 改 相 应 指针；入队即 是在终 端 结点 的后面 插入一个结点 ，这 需 要从 头指针开 始 查 找 终 端 结点 的地 址 。 ⑼ 串是一种特殊的线性表，其特殊性体 现在（ ）。 【解答】数据元素的类型是一个字符 ⑽ 两个串相等的充分必要条件是（ ）。 【解答】长度相同且对应位置的字符相等 【分析】例如"abc"≠"abc "，"abc"≠"bca"。 2. 选择题 ⑴ 若一个栈的输入序列是1，2，3，…，n，输...
