吉首大学数据结构栈与队列考试重点
1. 向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时,应执行s->next=h->next;h->next=s操作。2. 设计一个判别表达式中左、右括号是否配对出现的算法,采用栈数据结构最佳。3. 一个递归算法必须包括终止条件和递归部分。4. 若进栈序列为a，b，c，d，e，f，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是bdacef。5. 链式栈结点为（data，link），top指向栈顶，若想摘除栈顶结点，并将删除结点的值保存到x中，则应执行操作x->top->data;top=top->link6. 若一个栈初始为空，其输入序列是1，2，3，…，n-1，n，其输出序列的第一个元素为k(1≤k≤「n/2」)，则输出序列的最后一个元素是不确定的。7. 设有一个栈，元素依次进栈的顺序为A、B、C、D、E。下列EABCD是不可能的出栈序列。8. 算术表达式采用逆波兰式表示时不用括号，可以利用栈进行求值。9. 与逆波兰式ab-cd+*对应的中缀表达式是(a-b)*(c+d)10. 若一个栈以向量V存储，初始栈顶指针top设为n+1，则元素x进栈的正确操作是top--;V【top】=x;11.设栈最大长度为3，入栈序列为1、2、3、4、5、6，则不可能的出栈序列是43215612. 判定一个循环队列qu(最多元素为MaxSize)为空的条件是qu->rear==qu->front13. 用链接方式存储的队列，在进行删除运算时头尾指针可能都要修改14. 允许对队列进行的操作有删除队头元素15. 由于循环队列的特殊性，当队首指针=队尾指针的时候，既可能表示空也可能表示满，解决该问题的策略不包括相等后对首指针置016. 用不带头结点的单链表存储队列,其头指针指向队头结点,尾指针指向队尾结点,则在进行出队操作时头尾指针可能都要修改17. 设循环队列Q的定义中有rear和len两个域变量，其中rear表示队尾元素的指针，len表示队列的长度，如下图所示（队列长度为3,队头元素为e)。设队列的存储空间容量为M，则队头元素的指针为（Q.rear-Q.len+1+M）%M18. 对于一个长度大于1且不存在重复元素的序列，令其所有元素依次通过一个初始为空的队列后，再通过一个初始为空的找。设队列和栈的容量都足够大，一个序列通过队列（栈）的含义是序列的每个元素都入队（栈）且出队列（桟）一次且仅一次。对于该序列在上述队列和栈上的操作，正确的叙述是出入队序列一定相同，入出栈序列不一定相同19. 输出受限的双端队列是指元素可以从队列的两端输入，但只能从队列的一端输出，如下图所示，若有e1,e2,e3,e4依次进入输出受限的双端队列，则得不到输出序列e4e2e3e120. 设循环队列Q的定义中有front和size两个域变量，其中front表示队头元素的指针，size表示队列的长度，如下图所示(队列长度为3，队头元素为x、队尾元素为z)。设队列的存储空间容量为M，则队尾元素的指针为（Q.front+Q.size-1+M）%M21. 最大容量为n的循环队列，队尾指针是rear，队头指针是front，则队空的条件是rear==front22. 在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印机缓冲区，该缓冲区应该是一个队列结构。23. 某双端队列如下图所示，要求元素进出队列必须在同一端口，即从A端进入的元素必须从A端出、从B端进入的元素必须从B端出，则对于4个元素的序列e1、 e2、e3、 e4，若要求前2个元素(e1、 e2)从A端口按次序全部进入队列，后两个元素(e3、e4)从B端口按次序全部进入队列，则可能得到的出队序列是e4、e3、e2、e124. 设某循环队列Q的定义中有front和rear两个域变量，其中，front指示队头元素的位置，rear指示队尾元素之后的位置，如下图所示。若该队列的容量为M，则其长度为（Q.rear-Q,front+M）%M;25. 下面关于栈和队列的叙述，错误的是利用两个栈可以模拟一个队列的操作，反之亦可26. 队列的特点是先进先出，若用循环单链表表示队列，则入队列操作需要遍历链表而出队列操作不需要27. 对于一个长度为n(n>1)且元素互异的序列，每其所有元素依次通过一个初始为空的栈后，再通过一个初始为空的队列。假设队列和栈的容量都足够大，且只要栈非空就可以进行出栈操作，只要队列非空就可以进行出队操作，那么以下叙述中，正确的是出队序列和出栈序列一定相同
页:
[1]