③ 进 2 个之后再出的情况,有 5 种,2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,3,1,4
④ 进 1 个之后再出的情况,有 5 种,1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,3
3. 【刘自编】假设正读和反读都相同的字符序列为“回文”,例如,‘abba’和‘abcba’是回文,‘abcde’ 和‘ababab’则不是回文。假
设一字符序列已存入计算机,请分析用线性表、堆栈和队列等方式正确输出其回文的可能性?
答:线性表是随机存储,可以实现,靠循环变量(j--)从表尾开始打印输出;
堆栈是后进先出,也可以实现,靠正序入栈、逆序出栈即可;
队列是先进先出,不易实现。
哪种方式最好,要具体情况具体分析。若正文在机内已是顺序存储,则直接用线性表从后往前读取即可,或将堆栈栈
顶开到数组末尾,然后直接用 POP 动作实现。(但堆栈是先减后压还是……)
若正文是单链表形式存储,则等同于队列,需开辅助空间,可以从链首开始入栈,全部压入后再依次输出。
4. 【统考书 P60 4-13】顺序队的“假溢出”是怎样产生的?如何知道循环队列是空还是满?
答:一般的一维数组队列的尾指针已经到了数组的上界,不能再有入队操作,但其实数组中还有空位置,这就叫“假溢出”。
采用循环队列是解决假溢出的途径。
另外,解决队满队空的办法有三:
1 设置一个布尔变量以区别队满还是队空;
2 浪费一个元素的空间,用于区别队满还是队空。
3 使用一个计数器记录队列中元素个数(即队列长度)。
我们常采用法②,即队头指针、队尾指针中有一个指向实元素,而另一个指向空闲元素。
判断循环队列队空标志是: f=rear 队满标志是:f=(r+1)%N
5. 【统考书 P60 4-14】设循环队列的容量为 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
五、阅读理解(每小题 5 分,共 20 分。至少要写出思路)
1. 【严题集 3.7①】按照四则运算加、减、乘、除和幂运算(↑)优先关系的惯例,并仿照教材 例 3-2 的格式,画出对下
列算术表达式求值时操作数栈和运算符栈的变化过程:
A-B×C/D+E↑F
答: