《数据结构》第03章在线测试

 《数据结构》第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

正确错误