数据结构练习4.pdfVIP

栈和队列习题

4．1判断题(在你认为正确的题后的括号中打√，否则打X)。

(1)堆栈和队列都是特殊的线性表。(√)

(2)堆栈和队列都将插入和删除操作限制在表的端点处进行。(√)

(3)只允许在表的一端进行插入和删除操作的线性表称为堆栈。(√)

(4)没有元素的堆栈称为空栈，空栈用不着栈顶指针。(X)

(5)只要堆栈不空，就能任意删除堆栈的元素。(X)

(6)堆栈允许删除的一端称为栈顶，而栈底元素是不能删除的。(X)

(7)n个元素进栈的顺序一定与它们出栈的顺序相反。(X)

(8)对采用链式存储结构的堆栈进行操作不必判断溢出。(X)

(9)给出顺序堆栈的栈顶元素位置的指针是一个指针类型的变量。(X)

(10)判断顺序堆栈是否为空的标志是top是否等于0(top为栈顶指针)。(√)

(11)插入和删除操作比较简单是链接堆栈和链接队列的优点之一。(√)

(12)n个元素进队的顺序与它们出队的顺序一定是相同的。(√)

(13)没有任何元素的队列称为空队。空队用不着队头指针与队尾指针。(X)

(14)元素进出队列一定满足“先进先出”的规律。(√)

(15)链接队列不存在溢出问题。(X)

(16)在链接队列中删除一个元素是在链表的最前端进行的。(√)

(17)采用循环链表作为存储结构的队列称为循环队列。(√)

(18)堆栈和队列都可以用来解决递归问题。(X)

(19)堆栈和队列都不适合采用散列存储方法。(√)

(20)无论是顺序队列还是链接队列，插入、删除操作的时间复杂度都是O(1)。

(√)

4．2单项选择题。

A(1)堆栈和队列的共同之处在于它们具有相同的——。

A．逻辑特性B．物理特性C．运算方法D．元素类型

C(2)堆栈和队列都是特殊的线性表，其特殊性在于_______。

A．它们具有一般线性表所没有的逻辑特性

B．它们的存储结构比较特殊

C．对它们的使用方法做了限制

D．它们比一般线性表更简单

D(3)若5个元素的出栈序列为1，2，3，4，5，则进栈序列可能是——。

A．2，4，3，1，5B．2，3，1，5，4C．3，1，4，2，5D．3，1，2，5，4

A(4)某队列初始为空，若它的输入序列为a，b，c，d，它的输出序列应为——。

A．a，b，c，dB．d，c，b，aC．a，c，b，dD．d，a，c，b

找公式(5)当4个元素的进栈序列给定以后，由这4个元素组成的可能的出栈序列应该有

——。

A．24种B．17种C．16种D．14种

*(6)设n个元素的进栈序列为1，2，3，„，n，出栈序列为p1，p2，p3，„，pn，若Pi=n，

则B(1≤in)的值——。

A．为i