[考研类试卷]栈和队列模拟试卷1及答案与解析.doc

1、栈和队列模拟试卷 1 及答案与解析一、单项选择题下列各题的备选答案中，只有一个是符合题意的。1 栈是（ ）。（A）顺序存储的线性结构（B）链式存储的非线性结构（C）限制存取点的线性结构（D）限制存储点的非线性结构2 栈和队列具有相同的（ ）。（A）抽象数据类型（B）逻辑结构（C）存储结构（D）运算3 设链表不带头结点，且所有操作均在表头进行，则下列最不适合作为链栈的链表是（ ）。（A）只有表头结点指针，没有表尾指针的双向循环链表（B）只有表尾结点指针，没有表头指针的双向循环链表（C）只有表头结点指针，没有表尾指针的单向循环链表（D）只有表尾结点指针，没有表头指针的单向循环链表4 （ ）不是栈的

2、基本操作。（A）删除栈顶元素（B）删除栈底元素（C）判断栈是否为空（D）将栈置为空栈5 向一个栈顶指针为 top 的链栈中插入一个 x 结点，则执行（ ）。（A）top-next=x（B） x-next=top-next，top-next=x（C） x-next=top，top=x（D）x-next=top，top=top-next6 链栈执行 Pop 操作，并将出栈的元素存在 x 中应该执行（ ）。（A）x=top ； top=top-next（B） x=top-data；（C） top=top-next；x=top-data（D）x=top-data ；top=top-next7 和顺序栈

3、相比，链栈有一个比较明显的优势是（ ）。（A）通常不会出现栈满的情况（B）通常不会出现栈空的情况（C）插入操作更容易实现（D）删除操作更：容易实现8 设有一个空栈，栈顶指针为 1000H，每个元素需要 1 个存储单元，在执行。Push、Push 、Pop、Push、Pop 、Push、Pop、Push 操作后，栈顶指针的值为（ ）。（A）1002H（B） 1003H（C） 1004H（D）1005H9 3 个不同元素依次进栈，能得到（ ）种不同的出栈序列。（A）4（B） 5（C） 6（D）710 用 s 表示进栈操作，用 x 表示出栈操作，若元素的进栈顺序是 1234，为了得到1342 的出栈

4、顺序，相应的 S 和 X 的操作序列为（ ）。（A）SXSXSSXX（B） SSSXXSXX（C） SXSSXXSX（D）SXSSXSXX：11 设 a、b、 c、d、e、f 以所给的次序进栈，若在进栈操作时，允许出栈操作，则下面得不到的序列为（ ）。（A）fedcba（B） bcafed（C） dcefba（D）cabdef12 若元素 a、 b、c 、d、e、f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续 3 次进行退栈工作，则不可能得到的出栈序列是（ ）。（A）dcebfa（B） cbdaef（C） bcaefd（D）afedcb13 设栈 S 和队列 Q 的初始状态为空，元素

5、e1、e2、e3、e4 、e5 和 e6 依次通过栈S，一个元素出栈后即进队列 Q，若 6 个元素出栈的序列是e2、e4、e3、e6、e5 、el ，则栈 S 的容量至少应该是（ ）。（A）6（B） 4（C） 3（D）214 设栈 S 和队列 Q 的初始状态均为空，元素 abcde 依次进入栈 S。若每个元素出栈后立即进入队列 Q，且 7 个元素出队的顺序是 bdcfeag，则栈 S 的容量至少是（ ）。（A）1（B） 2（C） 3（D）415 若一个栈的输入序列是 1，2，3，n，输出序列的第一个元素是 n，则第 i个输出元素是（ ）（A）不确定（B） n-i（C） n-i-1（D）n-i+

6、116 一个栈的输入序列为 1，2，3，n，输出序列的第一个元素是 i，则第 j 个输出元素是（ ）。（A）i-j-1（B） i-j（C） j-i+1（D）不确定17 设栈的初始状态为空，当字符序列“n1” 作为栈的输入时，输出长度为 3，且可用做 C 语言标识符的序列有（ ）个。（A）4（B） 5（C） 3（D）618 某栈的输入序列为 a、 b、c 、d，下面的 4 个序列中，不可能是它的输出序列的是（ ）。（A）a、b、 c、d（B） c、b、d、a（C） d、c、a 、b（D）a、c、b、d19 若一个栈的输入序列是 P1，P 2，P 3,，P n，其输出序列是 1，2，3，n，若P3

7、=l，则 P1 的值（ ）。（A）可能是 2（B）一定是 2（C）不可能是 2（D）不可能是 320 若已知一个栈的入栈序列是 1、2、3、4。其出栈序列为 P1，P 2，P 3，P 4，则P2，P 4 不可能是（ ）。（A）2、4（B） 2、1（C） 4、3（D）3、421 采用共享栈的好处是（ ）。（A）减少存取时间，降低发生上溢的可能（B）节省存储空间，降低发生上溢的可能（C）减少存取时间，降低发生下溢的可能（D）节省存储空间，降低发生下溢的可能22 设有一个顺序共享栈 Share0：n-1，其中第一个栈项指针 topl 的初值为-1，第二个栈顶指针 top2 的初值为 n，则判断共享栈

8、满的条件是（ ）。（A）top2-topl=1（B） topl-top2=1（C） topl=top2（D）以上都不对23 元素 a、b 、c 、d、e 依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素 d 开头的序列个数是（ ）。（A）3（B） 4（C） 5（D）624 栈和队列的主要区别在于（ ）。（A）它们的逻辑结构不一样（B）它们的存储结构不一样（C）所包含的元素不一样（D）插入、删除操作的限定不一样25 最不适合用做链式队列的链表是（ ）。（A）只带队首指针的非循环双链表（B）只带队首指针的循环双链表（C）只带队尾指针的循环双链

9、表（D）只带队尾指针的循环单链表26 最适合用做链队的链表是（ ）。（A）带队首指针和队尾指针的循环单链表（B）带队首指针和队尾指针的非循环单链表（C）只带队首指针的非循环单链表（D）只带队首指针的循环单链表27 允许对队列进行的操作有（ ）。（A）对队列中的元素排序（B）取出最近进队的元素（C）在队列元素之间插入元素（D）删除队头元素28 队列的“先进先出 ”特性是指（ ）。（A）最后插入队列中的元素总是最后被删除（B）当同时进行插入、删除操作时，总是插入操作优先（C）每当有删除操作时，总要先做一次插入操作（D）每次从队列中删除的总是最早插入的元素29 用链式存储方式的队列进行删除操作时需要

10、（ ）。（A）仅修改头指针（B）仅修改尾指针（C）头尾指针都要修改（D）头尾指针可能都要修改30 一个队列的入队顺序是 1、2、3、4，则出队的输出顺序是（ ）。（A）4、3、2、1（B） 1.2、3、4（C） 1、4、3、2（D）3、2、4、131 在用单链表实现队列时，队头在链表的（ ）位置。（A）链头（B）链尾（C）链中（D）以上都可以32 在一个链队列中，假设队头指针为 front，队尾指针为 rear，x 所指向的元素需要入队，则需要执行的操作为（ ）。（A）fronr=x，front=front-next（B） x-next=front-next，front=x（C） rear-n

11、ext=x，rear=x（D）rear-next=x，X-next=null ，rear=x33 循环队列存储在数组 A0n中，则入队时的操作为（ ）。（A）rear=rear+1（B） rear=(rear+1)mod(n-1)（C） rear=(rear+1)modn（D）rear=(rear+1)mod(n+1)34 已知循环队列的存储空间为数组 A21，front 指向队头元素的前一个位置，rear指向队尾元素，假设当前 front 和 rear 的值分别为 8 和 3，则该队列的长度为（ ）。（A）5（B） 6（C） 16（D）1735 假设一个循环队列 QMaxSize的队头指针为

12、 front，队尾指针为 rear，队列的最大容量为 MaxSize，除此之外，该队列再没有其他数据成员，则判断该队的列满条件是（ ）。（A）Qfront=Q.rear（B） Qfront+Q.rear=MaxSize（C） Qfront=(Q.rear+1)MaxSize（D）Qrear=(Q.front+1)MaxSize栈和队列模拟试卷 1 答案与解析一、单项选择题下列各题的备选答案中，只有一个是符合题意的。1 【正确答案】 C【试题解析】 首先栈是一种线性表，所以 B、D 错。其按照存储结构的不同分为顺序栈和链栈，但不可以把栈局限在某种存储结构上，所以 A 错。【知识模块】 栈和队列2

13、 【正确答案】 B【试题解析】 线性表、栈和队列的逻辑结构都是相同的，都属于线性结构，只是它们的运算不同，从而表现出不同的特点。【知识模块】 栈和队列3 【正确答案】 C【试题解析】 通常栈的插入和删除在表头进行。对于选项 C，插入和删除一个结点后，仍需将其变为循环单链表，因此需要找到其尾结点，时间复杂度为 O(n)。【知识模块】 栈和队列4 【正确答案】 B【试题解析】 某种数据结构的基本操作是指其最核心、最基本的运算，其他较复杂的操作可以调用基本操作实现。删除栈底操作可以通过调用栈的基本运算求得，但删除栈底元素不属于栈的基本运算。【知识模块】 栈和队列5 【正确答案】 C【试题解析】 链栈

14、采用不带头结点的单链表表示时，进栈操作在首部插入一个结点 x(即 x-next=top)，插入完后需将 top 指向该插入的结点 x。请读者思考当链栈存在头结点时的情况。【知识模块】 栈和队列6 【正确答案】 D【试题解析】 这里假设栈顶指针指向的是栈顶元素，所以答案选 D：而 A 中首先将 top 指针赋给了 x，错误：B 中没有修改 top 指针的值；C 为 top 指针指向栈顶元素的上一个元素时的答案。【知识模块】 栈和队列7 【正确答案】 A【试题解析】 顺序栈采用数组存储，数组的大小是固定的，不能动态地分配大小。和顺序栈相比，链栈的最大优势在于它可以动态地分配存储空间，所以答案为 A

15、。【知识模块】 栈和队列8 【正确答案】 A【试题解析】 每个元素需要 1 个存储单元，所以每入栈一次地址加 1，出栈一次地址减 1。【知识模块】 栈和队列9 【正确答案】 B【知识模块】 栈和队列10 【正确答案】 D【试题解析】 采用排除法。选项 A、B、C 得到的出栈序列分别为1243、3241、1324，只有选项 D 的出栈序列为 1342。故选 D。【知识模块】 栈和队列11 【正确答案】 D【试题解析】 根据栈“先进后出”的特点，并且在进栈操作的同时允许出栈操作，显然，答案 D 中 C 最先出栈，则此时栈内必定为 a 和 b，但由于 a 先于 b 进栈，故要晚出栈。对于某个出栈的元

16、素，在它之前进栈却晚出栈的元素必定是按逆序出栈的，其余答案均是可能出现的情况。【知识模块】 栈和队列12 【正确答案】 D【试题解析】 A 可由 a 进、b 进、c 进、d 进、d 出、c 出、e 进、e 出、b 出、f进、f 出、 a 出得到；B 可由 a 进、b 进、c 进、c 出、b 出、d 进、d 出、a 出、e进、e 出、f 进、f 出得到；C 可由 a 进、b 进、b 出、c 进、c 出、a 出、d 进、e进、e 出、f 进、f 出、d 出得到；D 可由 a 进、a 出、b 进、c 进、d 进、e 进、f 进、f 出、e 出、d 出、c 出、 b 出得到，但要求不允许连续 3 次退

17、栈操作，故选 D。【知识模块】 栈和队列13 【正确答案】 C【知识模块】 栈和队列14 【正确答案】 C【知识模块】 栈和队列15 【正确答案】 D【试题解析】 此时，输出序列一定是输入序列的逆序，故答案选 D。【知识模块】 栈和队列16 【正确答案】 D【试题解析】 当第 i 个元素第一个出栈时，则 i 之前的元素可以依次排在 i 之后出栈，但剩余的元素可以在此时进栈并且也会排在 i 之前的元素出栈，所以，第 j个出栈的元素是不确定的。【知识模块】 栈和队列17 【正确答案】 C【知识模块】 栈和队列18 【正确答案】 C【试题解析】 对于 A，可能的顺序是 a 入栈，a 弹栈，b 入栈，

18、b 弹栈，c 入栈，c 弹栈，d 入栈，d 弹栈。对于 B，可能的顺序是 a 入栈，b 入栈，c 入栈，c 弹栈，b 弹栈，d 入栈，d 弹栈，a 弹栈。对于 D，可能的顺序是 a 入栈，a 弹栈，b 入栈，c 入栈，c 弹栈，b 弹栈， d 入栈，d 弹栈。C 则没有对应的序列。【知识模块】 栈和队列19 【正确答案】 C【试题解析】 由于 P3=1，入栈序列是 P1，P 2， 3,，P n。第一个出栈的元素是P3，即 P1，P 2， 3 入栈后出栈，第二个出栈的元素是 2，而此时 P1 不是栈顶元素，因此 P1 的值不可能是 2。【知识模块】 栈和队列20 【正确答案】 C【试题解析】 对

19、于 A，可能的顺序是 1 入栈，1 弹栈，2 入栈，2 弹栈，3 入栈，3 弹栈，4 入栈，4 弹栈。对于 B，可能的顺序是 1 入栈，2 入栈，3 入栈，3 弹栈，2 弹栈，4 入栈，4 弹栈，1 弹栈。对于 D，可能的顺序是 1 入栈，1 弹栈，2 入栈，3 入栈，3 弹栈，2 弹栈，4 入栈，4 弹栈。C 则没有对应的序列。【知识模块】 栈和队列21 【正确答案】 B【试题解析】 存取栈中的元素都只需要 O(1)的时间，所以，减少存取时间无从谈起。另外，栈只可能发生上溢，不可能发生下溢，所以答案为 B。【知识模块】 栈和队列22 【正确答案】 A【试题解析】 这种情况就是前面我们所描述的

20、，详细内容请参见本节。另外，读者可以思考若 top1 的初值为 0，top2 的初值为 n-1 时栈满的条件。【知识模块】 栈和队列23 【正确答案】 B【知识模块】 栈和队列24 【正确答案】 D【试题解析】 栈和队列的逻辑结构都是线性表，它们的存储结构有可能是顺序的，也有可能是链式的，但不能说是它们的主要区别，C 的道理也是一样，只有 D 才是栈和队列的本质区别。【知识模块】 栈和队列25 【正确答案】 A【试题解析】 由于非循环双链表只带队首指针，在执行入队操作时需要修改队尾结点的指针域，而查找队尾结点需要 O(n)的时间。【知识模块】 栈和队列26 【正确答案】 B【试题解析】 选项

21、C 和 D 的链表显然不太适合链队。选项 A 的链表在完成进队和出队后还要修改为循环的，对于队列来讲这是多余的。对于选项 B，由于有首指针，适合删除首结点；由于有尾指针，适合在其后插入结点，故选 B。【知识模块】 栈和队列27 【正确答案】 D【试题解析】 删除队头元素即出队，故选 D。【知识模块】 栈和队列28 【正确答案】 D【试题解析】 由于队列限定插入操作在表的一端进行而删除操作在表的另一端进行，所以，在队列中被删除的一定是当前最早插入的元素。队列没有限定插入和删除操作的次序，只要队列非空就可以执行删除操作，只要队列不满就可以执行插入操作。【知识模块】 栈和队列29 【正确答案】 D【

22、试题解析】 队列用链表形式存储时，删除元素时，从队头删除，一般情况下，仅需修改头指针即可，但如果此时队列中仅有一个元素，则尾指针也需要被修改。【知识模块】 栈和队列30 【正确答案】 B【试题解析】 队列的入队顺序和出队顺序是一致的，这是和栈不同的。【知识模块】 栈和队列31 【正确答案】 A【试题解析】 为了便于删除操作，故总是选择链头作为队头。【知识模块】 栈和队列32 【正确答案】 D【试题解析】 插入操作时，先将结点 x 插入到链表尾部，再让 rear 指向这个结点 x。【知识模块】 栈和队列33 【正确答案】 D【试题解析】 这道题需要注意的是，由于数组的下标范围为 0n，所以数组的容量为 n+1。【知识模块】 栈和队列34 【正确答案】 C【试题解析】 队列的长度为(rear-front+21)2l=16。这种情况和。front 指向当前元素，rear 指向队尾元素的下一个元素的计算是相同的。【知识模块】 栈和队列35 【正确答案】 C【试题解析】 既然不能附加任何其他数据成员，则只能采用牺牲一个存储单元的方法来区分队空还是队满，因此只能选 C。【知识模块】 栈和队列