数据结构与算法分析——第3章考试题

admin管理员组

文章数量:1642447

判断题

1-1

Run the following operations on a stack S: Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S). The output sequence must be {1, 2, 3}.

T        F

1-2

If keys are pushed onto a stack in the order abcde, then it's impossible to obtain the output sequence cdabe.

T        F

1-3

序列{1,2,3,4,5}依次入栈，则不可能得到{3,4,1,2,5}的出栈序列。

T        F

1-4

栈结构不会出现溢出现象。

T        F

1-5

两个栈共享一片连续空间，可以将两个栈的栈底分别设在这片空间的两端。

T        F

1-6

Non recursive programs are generally faster than equivalent recursive programs. However, recursive programs are in general much simpler and easier to understand.

T        F

1-7

Recursive programs are generally faster than equivalent non recursive programs. However, non recursive programs are in general much simpler and easier to understand.

T        F

1-8

In most restaurants, we follow one principle called "First come, first served". This principle can be implemented by a stack.

T        F

1-9

When n elements are pushed into a stack, they may be popped in a different order. But if they are inserted into a queue, they will always be deleted in the same order as the insertions.

T        F

1-10

栈的特性

栈是后进先出的线性表。

T        F

1-11

"Circular Queue" is defined to be a queue implemented by a circularly linked list or a circular array.

T        F

1-12

In a circular queue which is implemented by an array, the front value must always be no larger than the rear value.

T        F

1-13

In most restaurants, we follow one principle called "First come, first served". This principle can be implemented by a queue.

T        F

1-14

循环队列也存在空间溢出的问题。

T        F

1-15

队列的特性

队列是后进先出的线性表。

T        F

单选题

2-1

若已知一队列用单向链表表示，该单向链表的当前状态（含3个对象）是：1->2->3，其中x->y表示x的下一节点是y。此时，如果将对象4入队，然后队列头的对象出队，则单向链表的状态是：

A.1->2->3

B.2->3->4

C.4->1->2

D.答案不唯一

2-3

若用大小为6的数组来实现循环队列，且当前front和rear的值分别为0和4。当从队列中删除两个元素，再加入两个元素后，front和rear的值分别为多少？

(2分)

A.2和0        B.2和2        C.2和4        D.2和6

2-4

现有队列 Q 与栈 S，初始时 Q 中的元素依次是{ 1, 2, 3, 4, 5, 6 }（1在队头），S 为空。若允许下列3种操作：（1）出队并输出出队元素；（2）出队并将出队元素入栈；（3）出栈并输出出栈元素，则不能得到的输出序列是：

(2分)

A.1, 2, 5, 6, 4, 3        B.2, 3, 4, 5, 6, 1        C.3, 4, 5, 6, 1, 2        D.6, 5, 4, 3, 2, 1

2-5

循环队列的引入，目的是为了克服( )。

(1分)

A.假溢出问题        B.真溢出问题        C.空间不够用        D.操作不方便

2-6

循环队列的队满条件为 ( )。

(2分)

A.(sq.rear+1) % maxsize ==(sq.front+1) % maxsize

B.(sq.front+1) % maxsize ==sq.rear

C.(sq.rear+1) % maxsize ==sq.front

D.sq.rear ==sq.front

2-7

栈和队列的共同点是（ ）。

(2分)

A.都是先进先出

B.都是先进后出

C.只允许在端点处插入和删除元素

D.没有共同点

2-8

已知初始为空的队列 Q 的一端仅能进行入队操作，另外一端既能进行入队操作又能进行出队操作。若 Q 的入队序列是 1、2、3、4、5，则不能得到的出队序列是：

(2分)

A.5、4、3、1、2

B.5、3、1、2、4

C.4、2、1、3、5

D.4、1、3、2、5

2-9

有六个元素以6、5、4、3、2、1的顺序进栈，问哪个不是合法的出栈序列？

(2分)

A.2 3 4 1 5 6

B.3 4 6 5 2 1

C.5 4 3 6 1 2

D.4 5 3 1 2 6

2-10

若采用带头、尾指针的单向链表表示一个堆栈，那么该堆栈的栈顶指针top应该如何设置？

(2分)

A.将链表头设为top

B.将链表尾设为top

C.随便哪端作为top都可以

D.链表头、尾都不适合作为top

2-11

利用大小为n的数组（下标从0到n-1）存储一个栈时，假定栈从数组另一头开始且top==n表示栈空，则向这个栈插入一个元素时，修改top指针应当执行：

(2分)

A.top=0        B.top++        C.top--        D.top不变

2-12

Given the pushing sequence of a stack as {1, 2, 3, 4, 5}. If the first number being popped out is 4, then the last one out must be:

(2分)

A.1        B.3        C.5        D.1 or 5

2-13

To delete a node from a linked stack with ST being its top pointer, and save the key value of the deleted node into X, we must do:

(2分)

A.X= ST->data;

B.X= ST; ST = ST->next;

C.X= ST->data; ST = ST->next;

D.ST = ST->next; X= ST->data;

2-14

下列关于栈的叙述中，错误的是：

1. 采用非递归方式重写递归程序时必须使用栈
2. 函数调用时，系统要用栈保存必要的信息
3. 只要确定了入栈次序，即可确定出栈次序
4. 栈是一种受限的线性表，允许在其两端进行操作

(2分)

A.仅 1        B.仅 1、2、3        C.仅 1、3、4        D.仅 2、3、4

2-15

若栈S1​中保存整数，栈S2​中保存运算符，函数F()依次执行下述各步操作：

• （1）从S1​中依次弹出两个操作数a和b；
• （2）从S2​中弹出一个运算符op；
• （3）执行相应的运算b op a；
• （4）将运算结果压入S1​中。

假定S1​中的操作数依次是{ 5, 8, 3, 2 }（2在栈顶），S2​中的运算符依次是{ *, -, + }（+在栈顶）。调用3次F()后，S1​栈顶保存的值是：

(2分)

A.-15        B.15        C.-20        D.20

2-16

对空栈 S 进行 Push 和 Pop 操作，入栈序列为 a, b, c, d, e，经过 Push, Push, Pop, Push, Pop, Push, Push, Pop 操作后，得到的出栈序列是：

(2分)

A.b, a, c        B.b, a, e        C.b, c, a        D.b, c, e

2-17

设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6 , s5,s1,则栈的容量至少应该是( )。

(2分)

A.2        B.3        C.5        D.6

2-18

元素A,B,C,D依次入栈，出栈无限制，则以下（ ）是可能的出栈序列。

(2分)

A.C, A, B, D        B.B, A, D, C        C.B, D, A, C        D.A, D, B, C

2-19

用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为( )。

(2分)

A.SXSSSXXX        B.SXSXSXSX        C.SSSSXXXX        D.SXSSXSXX

2-20

Given the popping sequence of a stack as { a, b, c, d, e, f }. Among the following, the impossible pushing sequence is:

(2分)

A.c b a f e d        B.d f e a c b        C.f e a b c d        D.f e d a b c

2-21

Given the popping sequence of a stack as { 1, 2, 3, 4, 5, 6 }. Among the following, the impossible pushing sequence is:

(2分)

A.3 2 1 6 5 4        B.6 5 1 2 3 4        C.6 5 4 1 2 3        D.4 6 5 1 3 2

程序填空题

略.

本文标签： 考试题数据结构算法