算法与数据结构习题三(答案)_第1页
算法与数据结构习题三(答案)_第2页
算法与数据结构习题三(答案)_第3页
算法与数据结构习题三(答案)_第4页
算法与数据结构习题三(答案)_第5页
已阅读5页,还剩1页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

习题三一、选择题l.一个栈的序列是:a,b,c,d,e,则栈的不可能输出的序列是(C)。A.a,b,c,d,eB.d,e,c,b,aC.d,c,e,a,bD.e,d,c,b,a2.若一个栈的输人序列是1,2,3,…,n,输出序列的第一个元素是n,则第k个输出元素是(C)。A.kB.n-k-1C.n-k+1D.不确定3.判定一个栈S(最多有n个元素)为空的条件是(B)。A.S->top!=0B.S->top==0C.S->top!=nD.S->top==n4.判定一个栈S(最多有n个元素)为满的条件是(D)。A.S->top!=0B.S->top==0C.S->top!=nD.S->top==n5.向一个栈顶指针为top的链栈中插人一个*S结点的时候,应当执行语句(B)。A.top->next=S;B.S->next=top;top=S;C.S->next=top->next;top->next=S;D.S->next=top;top=S->next;6.向一个带头结点、栈顶指针为top的链栈中插人一个*S结点的时候,应当执行语句(C)。A.top->next=S;B.S->next=top;top=S;C.S->next=top->next;top->next=S;D.S->next=top;top=S->next;7.判定一个队列Q(最多有n个元素)为空的条件是(C)。A.Q->rear-Q->front==nB.Q->rear-Q->front+1==nC.Q->rear==Q->frontD.Q->rear+1==Q->front8.判定一个队列Q(最多有n个元素)为满的条件是(A)。A.Q->rear-Q->front==nC.Q->rear==Q->frontB.Q->rear-Q->front+1==nD.Q->rear+1==Q->front9.判定一个循环队列Q(最多有n个元素)为空的条件是(A)。A.Q->rear==Q->frontB.Q->rear==Q->front+lC.Q->front==(Q->rear+1)%nD.Q->front==(Q->rear-1)%n10.判定一个循环队列Q(最多有n个元素)为满的条件是(C)。A.Q->rear==Q->frontB.Q->rear==Q->front+lC.Q->front==(Q->rear+1)%nD.Q->front==(Q->rear-1)%n11.在一个链队列中,假定front和rear分别为头指针和尾指针,则插入一个结点*S的操作是(C)。A.front=front->nextB.S->next=rear;rear=SC.rear->next=S;rear=SD.S->next=front;front=S12.在一个链队列中,假定front和rear分别为头指针和尾指针,删除一个结点的操作是(A)。A.front=front->nextB.rear=rear->nextC.rear->next=frontD.front->next=rear13.栈与队列都是(C)。A.链式存储的线性结构C.限制存取点的线性结构B.链式存储的非线性结构D.限制存取点的非线性结构14.若进栈序列为l,2,3,4,则(C)不可能是一个出栈序列。A.3,2,4,1B.l,2,3,4C.4,2,3,1D.4,3,2,l15.在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区,主机将要输出的数据依次写人该缓冲区,而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个(B)结构。A.堆栈B.队列C.数组D.线性表二、填空回1.栈(stack)是限定在表尾一端进行插人或删除操作的线性表。在栈中,允许插人和删除操作的一端称为栈顶,而另一端称为栈底。不含元素的栈称为空栈。2.在栈的运算中,栈的插人操作称为进栈或入栈的删除操作称为退栈或出栈。3.根据栈的定义,每一次进栈的元素都在原栈顶元素之上,并成为新的栈顶元素;每一次出栈的元素总是当前的栈顶元素,因此最后进栈的元素总是最先出栈,所以栈也称为后进先出线性表,简称为LIFO表。4.栈是一种操作受到限制的线性表,是一种特殊的线性表,因此栈也有顺序和链式_两种存储结构,分别称为、顺序栈_和_链栈。5.当栈满的时候,再进行人栈操作就会产生溢出,这种情况的溢出称为上溢__;当栈空的时候,如果再进行出栈操作,也会溢出,这种情况下的溢出称为下溢。6.栈的链式存储结构简称为链栈,是一种_特殊的单链表。7.人们日常计算用到的表达式都被称为中缀表达式,这是由于这种算术表达式的运算符被置于两个操作数中间。8.计算机中通常使用后缀表达式,这是一种将运算符置于两个操作数后面的算术表达式。这种表达式是由波兰科学家谢维奇提出的,因此又称为波兰式。9.队列(Queue)也是一种特殊的线性表_,但它与栈不同,队列中所有的插人均限定在表的一端进行,而所有的删除则限定在表的另一端进行。允许插人的一端称为队尾,允许删除的一端称为队头。10.队列的特点是先进先出,因此队列又被称为先进先出.的线性表,或称为FIFO表。11.队列的顺序存储结构又称为顺序队列,是用一组地址连续的存储单元依次存放队列中的元素。12.由于队列中的元素经常变化,对于队列的删除和插人分别在队头和队尾进行,因此需要设置两个指针分别指向队头元素和队尾元素,这两个指针又称为队头指针和队尾指针。13.循环顺序队列(CircularSequenceQueue)经常简称为循环队列,它是将存储顺序队列的存储区域看成是一个首尾相连的一个环,即将队首和队尾元素连接起来形成一个环形表。首尾相连的状态是通过数学上的、取模运算来实现的。14.在算法或程序中,当一个函数直接调用自己或通过一系列语句间接调用自己的时候,则称这个函数为递归函数,也称为自调用函数。函数直接调用自己,则称为直接递归调用;当一个函数通过另一个函数来调用自己则称为间接递归调用。15.在循环队列中规定:当Q->rear==Q->front的时候循环队列为空_,当(Q->rear+1)%MAXSIZE=front的时候循环队列为满。16.用链表方式表示的队列称为链队列。17.已知栈的输人序列为1,2,3,…,n,输出序列为a1,a2,…,an,符合a2==n的输出序列共有n-1。18.一个栈的输人序列是12345,则栈的输出序列为43512是不可能的(填是否可能)。19.一个栈的输人序列是12345,则栈的输出序列为12345是可能的(填是否可能)。20.设sq[1..maxsize]为一个顺序存储的栈,变量top指示栈顶元素的位置,则作入栈操作的条件是top!=maxsize。21.设sq[1..maxsize]为一个顺序存储的栈,变量top指示栈顶元素的位置,如果把栈顶元素弹出并送到X中,则需执行语句x=sq[top];top=top-1。22.栈的特性是先进后出。23.对栈进行退栈时的操作是先取出元素,后移动栈顶指针。24.设s[1..max]为一个顺序存储的栈,变量top指示栈顶位置,栈为满的条件是top==max。25.设链栈的栈顶指针为top,则栈非空的条件是top!=nil。26.已知循环队列用数组data[1...n]存储元素值,用f,r分别作为头尾指针,则当前元素个数为(n+r-f)modn。27.在一个循环队列中,队首指针指向队首元素的前一个位置。(前一个或后一个)28.队列中允许进行删除的一端称为队首。29.链队列实际上是一个同时带有头指针和尾指针的单链表(1..n),尾指针指向该单链表的第n个元素。30.设双向链表链列为lq,lq的头指针为lq.Front,尾指针为lq.Rear,则队列为空的条件是lq->front==lq->rear。31.从循环队列中删除一个元素,其操作是先取出一个元素,后移动栈顶指针。32.队列中允许进行插入的一端称为队尾。三、判断题1.栈和队列都是限制存取点的线性结构。对)2.不同的人栈和出栈组合可能得到相同输出序列。错误:不同的入栈和出栈组合得到不同输出序列。)3.消除递归一定要用栈。(错误:某些情况如尾递归可以转换为递推的形式。)4.循环队列是顺序存储结构。(正确)5.循环队列不会产生溢出。(错误:循环队列不会产生假溢出6.循环队列满的时候rear

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论