欢迎来到文档下载导航网!

第三章栈和队列习题 - 数据结构.doc

时间:2020-11-26|当前位置:首页 > 计算机 > 计算机资料/编程 > |用户下载:

第三章栈和队列习题 - 数据结构.doc


本文档部分文本预览

第三章栈和队列习题 - 数据结构 习题三 栈和队列 一 单项选择题 1. 在作进栈运算时,应先判别栈是否(① ),在作退栈运算时应先判别栈是否(② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③ )。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 2.若已知一个栈的进栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,...,pn,若p1=3,则p2为( )。 A 可能是2 B 一定是2 C 可能是1 D 一定是1 3. 有六个元素6,5,4,3,2,1 的顺序进栈,问下列哪一个不是合法的出栈序列?( ) A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 4.设有一顺序栈S,元素s1,s2,s3,s4,s5,s6依次进栈,如果6个元素出栈的顺序是s2,s3,s4, s6 , s5,s1,则栈的容量至少应该是 ( ) A.2 B. 3 C. 5 D.6 5. 若栈采用顺序存储方式存储,现两栈共享空间V,top+1=top=top作为循环队列SQ的存储空间, front为队头指针,rear为队尾指针,则执行出队操作的语句为 ( ) A.front=front+1 B. front=(front+1)% m C.rear=(rear+1)%(m+1) D. front=(front+1)%(m+1) 11.循环队列的队满条件为 ( ) A. (sq.rear+1) % maxsize ==(sq.front+1) % maxsize; B. (sq.front+1) % maxsize ==sq.rear C. (sq.rear+1) % maxsize ==sq.front D.sq.rear ==sq.front 12. 栈和队列的共同点是( )。 A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点 二、填空题 1.栈是_______的线性表,其运算遵循_______的原则。 2. 一个栈的输入序列是:1,2,3则不可能的栈输出序列是_______。 3.用S表示入栈操作,X表示出栈操作,若元素入栈的顺序为1234,为了得到1342出栈顺序,相应的S和X的操作串为_______。 4. 循环队列的引入,目的是为了克服_______。 5.队列是限制插入只能在表的一端,而删除在表的另一端进行的线性表,其特点是_______。 6. 已知链队列的头尾指针分别是f和r,则将值x入队的操作序列是_______。 7.表达式求值是_______应用的一个典型例子。 8.循环队列用数组A存放其元素值,已知其头尾指针分别是front和rear ,则当前队列的元素个数是_______。 9. 以下运算实现在链栈上的初始化,请在________________处用请适当句子予以填充。 Void InitStacl(LstackTp *ls){ ________________;} 10.` 以下运算实现在链栈上的进栈,请在处用请适当句子予以填充。 Void Push(LStackTp *ls,DataType x) { LstackTp *p;p=malloc(sizeof(LstackTp)); ________________; p->next=ls; ________________; } 11.以下运算实现在链栈上的退栈,请在________________处用请适当句子予以填充。 Int Pop(LstackTp *ls,DataType *x) {LstackTp *p; if(ls!=NULL) { p=ls; *x=________________; ls=ls->next; ________________; return(1); }else return(0); } 12. 以下运算实现在链队上的入队列,请在________________处用适当句子予以填充。 Void EnQueue(QueptrTp *lq,DataType x) { LqueueTp *p; p=(LqueueTp *)malloc(sizeof(LqueueTp)); ________________=x; p->next=NULL; (lq->rear)->next=________________; ________________; } 三、应用题 1.给出栈的两种存储结构形式名称,在这两种栈的存储结构中如何判别栈空与栈满? 2. 画出对算术表达式A-B*C/D-E↑F求值时操作数栈和运算符栈的变化过程。 3. 将两个栈存入数组V应如何安排最好?这时栈空、栈满的条件是什么? 4. 怎样判定循环队列的空和满? 四、算法设计题 1.借助栈(可用栈的基本运算)来实现单链表的逆置运算。 2. 设表达式以字符形式已存入数组E,为了尽量利用空间,减少溢出的可能,可采用栈顶相向,迎面增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。 5. 请利用两个栈S1和S2来模拟一个队列。已知栈的三个运算定义如下:PUSH(ST,x):元素x入ST栈;POP(ST,x):ST栈顶元素出栈,赋给变量x;Sempty(ST):判ST栈是否为空。那么如何利用栈的运算来实现该队列的三个运算:enqueue:插入一个元素入队列; dequeue:删除一个元素出队列;queue_empty:判队列为空。(请写明算法的思想及必要的注释) 6. 要求循环队列不损失一个空间全部都能得到利用,设置一个标志tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满,请编写与此相应的入队与出队算法。 7. 已知Q是一个非空队列,S是一个空栈。仅用队列和栈的ADT函数和少量工作变量,编写一个算法,将队列Q中的所有元素逆置。栈的ADT函数有: makeEmpty(s:stack); 置空栈 push(s:stack;value:datatype); 新元素value进栈 pop(s:stack):

继续预览文档剩余内容

温馨提示:本页预览文本内容并非错乱,是从文档中提取部分无格式预览!如您需要正常预览文档全文,请点击下方按钮↓↓↓

上一篇:电子商务练习题2.doc

栏    目:计算机资料/编程

下一篇:2B新概念第21单元的测试.doc

本文标题:第三章栈和队列习题 - 数据结构.doc

本文地址:https://www.365weibook.com/html/20201126/376866.html

    正常预览或下载提示:

    本页面文档预览是由服务器自动提取的部分内容,并不是文档错乱。如您需要预览全文或下载文档,请点击页面左侧(点击去预览文档全文或下载文档)按钮,进行全文预览或下载。

推荐下载

联系我们 | 广告投放 |网站地图

免责申明:本网站不提供任何形式的下载服务,因此与之有关的知识产权纠纷本网站不承担任何责任。

如果侵犯了您的权利,请与我们联系,我们将进行删除处理。