数据结构第3章测试 栈和队列

第一题、单项选择题（每题1分，5道题共5分）
1、一个栈的输入序列是{1，2，3，4}，则＿＿＿＿A＿＿＿＿是它的不可能的输出序列。
A、{1，2，3，4} B、{4，3，2，1}
C、{1，3，4，2} D、{4，2，1，3}
2、一个栈的入栈序列是1，2，3，…，n，其输出序列为p1,p2,p3,…pn,若p1＝n, 则pi为＿＿＿＿C＿＿＿＿。
A、i B、n-i
C、n-i+1 D、不确定
3、在进行递归函数调用时，处理参数和返回地址需要使用一种称为＿＿＿B＿＿＿＿＿的数据结构。
A、线性表 B、栈
C、队列 D、树
4、已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1,p2,p3,…pn,若p1＝n,则pi为＿＿C＿＿＿＿＿＿。
A、i B、n-i
C、n-i+1 D、不确定
5、栈是限定在＿＿＿＿＿D＿＿＿进行插入或删除的线性表。
A、栈底 B、栈顶
C、任意位置 D、
第二题、多项选择题（每题2分，5道题共10分）
1、一个栈的入栈序列是{1,2,3,4,5},在各种出栈序列中，以3，4开头的输出序列可能是＿＿＿CDF＿＿＿＿。
A、{3,4,5,1,2}
B、{3,4,1,2,5}
C、{3,4,5,2,1}
D、{3,4,2,1,5}
E、{3,4,1,5,2}
F、{3,4,2,5,1}
2、循环队列中，设队列元素依次存放在Q[0..m]中，f、r分别指示队头元素位置和队尾元素的下一个位置，此时队空、队满的判断条件都是f＝＝r,为解决此矛盾，通常可采用＿＿＿ACD＿＿＿＿。
A、附设标志位，f＝＝r时借助标志判断
B、牺牲一个元素空间，(r+1）％ m＝＝f时队满，f＝＝r时队空
C、牺牲一个元素空间，(r+1）％ (m+1)＝＝f时队满，f＝＝r时队空
D、另设表示队列长度的length域来区别队列空、满
3、队列操作的原则是＿＿＿＿ACD＿＿＿。
A、先进先出
B、后进先出
C、可以进行插入
D、可以进行删除
4、一个队列的入队序列是{1,2,3,4},则队列不可能的输出序列是＿＿＿＿ACD＿＿＿。
A、4321
B、1234
C、1432
D、3241
5、在链队列中，若插入一个元素，则＿＿＿AD＿＿＿＿。
A、必须修改尾指针
B、必须修改头指针
C、不必修改尾指针
D、不必修改头指针
第三题、判断题（每题1分，5道题共5分）
1、队列是先进先出的线性表。T
正确 错误
2、一个队列的入队序列是{1,2,3,4},则队列的输出序列只能是{1,2,3,4}。T
正确 错误
3、栈和队列都是插入和删除位置受限制的线性表。T
正确 错误
4、队列只能有一种输出序列，即队列中的元素只能按照进入队列的顺序依次出队。T
正确 错误
5、栈只能有一种输出序列，栈中的元素只能按照入栈的顺序反向依次出栈。T
正确 错误