- 1、本文档共20页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
数据结构考研试题选及答案第三章 栈和队列答案
第三章 栈和队列答案
一、选择题
1.B 2.1B 2.2A 2.3B 2.4D 2.5.C 3.B 4.D 5.D 6.C 7.D 8.B 9.D 10.D 11.D 12.C 13.B 14.C 15.B 16.D 17.B 18.B 19.B 20.D 21.D 22.D 23.D 24.C 25.A 26.A 27.D 28.B 29.BD 30.C 31.B 32.C 33.1B 33.2A 33.3C 33.4C 33.5F 34.C 35.C 36.A 37.AD 二、判断题
1.√ 2.√ 3. √ 4. √ 5.× 6.√ 7.√ 8. √ 9. √ 10.× 11. √ 12.× 13. × 14.× 15. √ 16.× 17.√ 18.× 19.√ 20. √ 部分答案解释如下。
尾递归的消除就不需用栈
这个数是前序序列为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)T0(2)in(3)T0(4)topn(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个元素(4356)得到后,栈中元素剩12,且2在栈顶,不可能栈底元素1在栈顶元素2之前出栈。
得到135426的过程如下:1入栈并出栈,得到部分输出序列1;然后2和3入栈,3出栈,部分输出序列变为:13;接着4和5入栈,5
文档评论(0)