4.【统考书P604-13】顺序队的“假溢出”是怎样产生的?如何知道循环队列是空还是满? 答:一般的一维数组队列的尾指针已经到了数组的上界,不能再有入队操作,但其实数组中还有空位置,这就叫“假溢出”。 采用循环队列是解决假溢出的途径, 另外,解决队满队空的办法有三 ①设置一个布尔变量以区别队满还是队空 ②浪费一个元素的空间,用于区别队满还是队空 ③使用一个计数器记录队列中元素个数(即队列长度)。 我们常采用法②,即队头指针、队尾指针中有一个指向实元素,而另一个指向空闲元素。 判断循环队列队空标志是:f=rear 队满标志是:f=(r+1)%N 5.【统考书P604-14】设循环队列的容量为40(序号从0到39),现经过一系列的入队和出队运算后,有 ①font=11,rear=19;② front=19,rear=11:问在这两种情况下,循环队列中各有元素多少个? 答:用队列长度计算公式:(N+r-f%N ①L=(40+19-11)%40=8 ②L=(40+11-19)%40=3 五、阅读理解(每小题5分,共20分。至少要写出思路) 1.【严题集3.7①】按照四则运算加、减、乘、除和幂运算(↑)优先关系的惯例,并仿照教材例32的 格式,画出对下列算术表达式求值时操作数栈和运算符栈的变化过程 A-B×C/D+E↑F 序号OPTR栈OPND栈 当前字符 备注 B*C/D+E (操作) ush(OPND, ' A') push(OPTR,一) push(OPND, 'B) AB push (OPTR,*') AB push(OPND, 'C) ABC 归约,令T1=B“C push(OPTR,’/) 8 ATI push(OPND, ' D) ATID 归约,令Tz=T1/D AT2 归约,令T3=A-T2 11# h(OPTR. '+' push(OPND, 'E) 13#+ T3E push(OPTR,↑) 14#+↑ T3E ush(OPND, ' Fr 15#+↑ TEF 归约,令T=E↑F # T3T. 归约,令T5=T3+T4 17# return(Ts) 2.【严题集33②】写出下列程序段的输出结果(栈的元素类型 SElem Type为char)4 4. 【统考书 P60 4-13】顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？ 答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。 采用循环队列是解决假溢出的途径。 另外，解决队满队空的办法有三： ① 设置一个布尔变量以区别队满还是队空； ② 浪费一个元素的空间，用于区别队满还是队空。 ③ 使用一个计数器记录队列中元素个数（即队列长度）。 我们常采用法②，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。 判断循环队列队空标志是： 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 答： 2. 【严题集 3.3②】写出下列程序段的输出结果（栈的元素类型 SElem Type 为 char）