第三章 栈和队列
一、选择题
二、判断题
部分答案解释如下。
1、 尾递归的消除就不需用栈
2、 这个数是前序序列为 1,2,3,…,n,所能得到的不相似的二叉树的数目。
三、填空题
1、操作受限(或限定仅在表尾进行插入和删除操作) 后进先出
2、栈 3、3 1 2 4、23 100CH 5、0 n+1 top[1]+1=top[2]
6、两栈顶指针值相减的绝对值为 1(或两栈顶指针相邻)。
7、(1)满 (2)空 (3)n (4)栈底 (5)两栈顶指针相邻(即值之差的绝对值为 1)
8、链式存储结构 9、S×SS×S×× 10、data[++top]=x;
11、23.12.3*2-4/34.5*7/++108.9/+(注:表达式中的点(.)表示将数隔开,如 23.12.3 是三个数)
12、假溢出时大量移动数据元素。
13、(M+1) MOD N (M+1)% N; 14、队列 15、先进先出 16、先进先出
17、s=(LinkedList)malloc(sizeof(LNode)); s->data=x;s->next=r->next;r->next=s;r=s;
18、牺牲一个存储单元 设标记
19、(TAIL+1)MOD M=FRONT (数组下标 0 到 M-1,若一定使用 1 到 M,则取模为 0 者,值改取 M
20、sq.front=(sq.front+1)%(M+1);return(sq.data(sq.front));(sq.rear+1)%(M+1)==sq.front;
21、栈 22、(rear-front+m)% m; 23、(R-P+N)% N;
24、(1)a[i]或 a[1] (2)a[i] (3)pop(s)或 s[1];
25、(1)PUSH(OPTR,w)(2)POP(OPTR)(3)PUSH(OPND,operate(a,theta,b))
26、(1)T>0(2)i<n(3)T>0(4)top<n(5)top+1(6)true(7)i-1(8)top-1(9)T+w[i](10)false
四、应用题
1、栈是只准在一端进行插入和删除操作的线性表,允许插入和删除的一端叫栈顶,另一端叫栈底。最
后插入的元素最先删除,故栈也称后进先出(LIFO)表。
2、队列是允许在一端插入而在另一端删除的线性表,允许插入的一端叫队尾,允许删除的一端叫队头。
最先插入队的元素最先离开(删除),故队列也常称先进先出(FIFO)表。
3、用常规意义下顺序存储结构的一维数组表示队列,由于队列的性质(队尾插入和队头删除),容易
造成“假溢出”现象,即队尾已到达一维数组的高下标,不能再插入,然而队中元素个数小于队列的长度
(容量)。循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下,通常
采用“牺牲一个存储单元”或“作标记”的方法解决“队满”和“队空”的判定问题。
4、(1)通常有两条规则。第一是给定序列中 S 的个数和 X 的个数相等;第二是从给定序列的开始,到
给定序列中的任一位置,S 的个数要大于或等于 X 的个数。
(2)可以得到相同的输出元素序列。例如,输入元素为 A,B,C,则两个输入的合法序列 ABC 和 BAC
均可得到输出元素序列 ABC。对于合法序列 ABC,我们使用本题约定的 S×S×S×操作序列;对于合法序
列 BAC,我们使用 SS××S×操作序列。
5、三个:CDEBA,CDBEA,CDBAE
6、 输 入 序 列 为 123456 , 不 能 得 出 435612, 其 理 由 是 , 输 出 序 列 最 后 两 元 素 是 12 , 前 面 4 个 元 素
评论0
最新资源