《数据结构》第03章在线测试
《数据结构》第03章在线测试剩余时间：59:57
答题须知：1、本卷满分20分。
2、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。
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、iB、n-i
C、n-i+1D、不确定
3、在顺序栈中，base、top分别为栈底、栈顶指针，则＿＿＿C＿＿＿＿时表明栈空。
A、base＝＝NULLB、top＝＝ NULL
C、base＝＝topD、
4、栈是限定在＿＿＿＿B＿＿＿＿进行插入或删除的线性表。
A、栈底B、栈顶
C、任意位置D、
5、在循环队列中，设队列元素依次存放在Q[0..m]中，f、r分别指示队头元素位置和队尾元素的下一个位置，Q中存放m个元素时认为队列满，则队列满的判定方法是 ＿＿＿C＿＿＿＿。
A、f==rB、(f+1) ％ (m+1)＝＝r
C、(r+1) ％ (m+1)＝＝fD、(r+1) ％ m＝＝f
第二题、多项选择题（每题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、下列数据结构中，＿＿＿ABC＿＿＿＿是线性结构。
A、线性表
B、栈
C、队列
D、树
E、图
4、队列操作的原则是＿＿＿ACD＿＿＿＿。
A、先进先出
B、后进先出
C、可以进行插入
D、可以进行删除
5、非空链栈（ls为栈顶指针）的出栈操作可表示为: p＝ls; ＿＿＿AC＿＿＿＿; free(p);
A、ls＝ls-＞next
B、ls=p
C、ls＝p-＞next
D、p＝ ls-＞next
第三题、判断题（每题1分，5道题共5分）
1、若用户无法估计所用队列的最大长度，则最好采用循环队列F
正确错误
2、一个队列的入队序列是{1,2,3,4},则队列的输出序列只能是{1,2,3,4}。T
正确错误
3、栈的一个重要应用是在程序设计语言中实现递归。T
正确错误
4、队列只能有一种输出序列，即队列中的元素只能按照进入队列的顺序依次出队。T
正确错误
5、栈只能有一种输出序列，栈中的元素只能按照入栈的顺序反向依次出栈。F
正确错误
