当前位置：文档之家 › 《数据结构》习题汇编03 第三章 栈和队列 试题(答案)

《数据结构》习题汇编03 第三章 栈和队列 试题(答案)

  • 格式：doc
  • 大小：156.50 KB
  • 文档页数：7

第三章 栈和队列

一、单项选择题

参考答案： 1. A 2. B 3. C 4. A 5. B

6. B 7. D 8. D 9. C 10. A

11. D 12. A 13. A 14. D 15. C

二、填空题

参考答案：

1. 先进后出 2. 先进先出 3. 队尾，队头 4. 栈顶指针 5. 栈顶指针

6. MaxSize-1 7. top==0 8. 空栈 9. 栈顶指针 10. p->link=top，top=p

11. top=top->link 12. Q.front==Q.rear 13. (Q.rear+1)%MaxSize==Q.front

14. 队尾指针 15. 空，只含有一个结点

16. front == rear && front != NULL或者front == rear && rear != NULL

17. 两端 18. 3x2+*5- 19. 15 20. 3

三、判断题

参考答案： 1. 是 2. 是 3. 否 4. 是 5. 是

6. 否 7. 否 8. 是 9. 否 10. 否

11. 否 12. 是 13. 否 14. 是 15. 否

16. 否

四、运算题

参考答案：

1. 根据以上规则，给出计算中缀表达式a + b * c – d / e时两个栈的变化。

步 扫描项 项类型 动 作 OPND栈 OPTR栈

0 OPTR栈与OPND栈初始化, ‘#’ 进OPTR栈,

取第一个符号 #

1 a 操作数 a进OPND栈, 取下一符号 a #

2 + 操作符 icp (‘+’ ) > isp (‘#’ ), 进OPTR栈, 取下一符号 a # +

3 b 操作数 b进OPND栈, 取下一符号 a b # +

4 * 操作符 icp (‘*’ ) > isp (‘+’ ), 进OPTR栈, 取下一符号 a b # + *

5 c 操作数 c进OPND栈, 取下一符号 a b c # + *

6 - 操作符 icp (‘-’ ) < isp (‘*’ ), 退OPND栈 ‘c’,

退OPND

栈 ‘b’, 退OPTR栈 ‘*’, 计算 b * c → s1,

结果

进OPND栈 a s1 # +

7 同上 同上 icp (‘-’ ) < isp (‘+’ ), 退OPND栈 ‘s1’,

退OPND

栈 ‘a’, 退OPTR栈 ‘+’, 计算 a * s1 →

s2, 结果

进OPND栈 s2 # 8 同上 同上 icp (‘-’ ) > isp (‘#’ ), 进OPTR栈, 取下一符号 s2 # -

9 d 操作数 d进OPND栈, 取下一符号 s2 d # -

10 / 操作符 icp (‘/’ ) > isp (‘-’ ), 进OPTR栈, 取下一符号 s2 d # - /

11 e 操作数 e进OPND栈, 取下一符号 s2 d e # - /

12 # 操作符 icp (‘#’ ) < isp (‘/’ ), 退OPND栈 ‘e’,

退OPND

栈 ‘d’, 退OPTR栈 ‘/’, 计算 d / e →

s5, 结果

进OPND栈 s2 s3 # -

13 同上 同上 icp (‘#’ ) < isp (‘-’ ), 退OPND栈 ‘s3’,

退OPND

栈 ‘s2’, 退OPTR栈 ‘-’, 计算 s2 – s3 →

s4, 结

果进OPND栈 s4 #

14 同上 同上  icp (‘#’ ) == isp (‘#’ ), 退OPND栈 ‘s4’, 结束 #

2. 利用运算符优先数，画出将中缀表达式a + b * c - d / e 改为后缀表达式时运算符栈OPTR的变化。

步 扫描项 项类型 动 作 OPTR栈 输 出

0 '#' 进栈, 读下一符号 #

1 a 操作数 直接输出, 读下一符号 # a

2 + 操作符 isp ( '#' ) < icp ( '+' ), 进栈, 读下一符号 # + a

3 b 操作数 直接输出, 读下一符号 # + a b

4 * 操作符 isp ( '+' ) < icp ( '*' ), 进栈, 读下一符号 # + * a b

5 c 操作数 直接输出, 读下一符号 # + * a b c

6 - 操作符 isp ( '*' ) > icp ( '-' ), 退栈输出 '*' # + a b c *

7 同上 同上 isp ( '+' ) > icp ( '-' ), 退栈输出 '+' # a b c * +

8 同上 同上 isp ( '#' ) < icp ( '-' ), 进栈, 读下一符号 # - a b c * +

9 d 操作数 直接输出, 读下一符号 # - a b c * + d

10 / 操作符 isp ( '-' ) < icp ( '/' ), 进栈, 读下一符号 # - / a b c * + d

11 e 操作数 直接输出, 读下一符号 # - / a b c * + d e

12 # 操作符 isp ( '/' ) > icp ( '#' ), 退栈输出 '/' # - a b c * + d e /

1同上 同上 isp ( '-' ) > icp ( '#' ), 退# a b c * + d 3 栈输出 '-' e / -

14 同上 同上 isp ( '#' ) == icp ( '#' ), 结束 # a b c * + d e / -

3. 画出对后缀算术表达式a b c * + d e / - 求值时运算对象栈OPND的变化

步 扫描项 项类型 动 作 OPND栈

1

置空栈 空

2 a

操作数 进栈 a

3 b 操作数 进栈 a b

4 c 操作数 进栈 a b c

5 * 操作符 c、b退栈，计算b * c，结果s1进栈 a s1

6 + 操作符 s1、a退栈，计算a + s1，结果s2进栈 s2

7 d 操作数 进栈 s2 d

8 e 操作数 进栈 s2 d e

9 / 操作符 e、d退栈，计算d / e，结果s3进栈 s2 s3

10 - 操作符 s3、s2退栈，计算s2 - s3，结果s4进 s4

11 # 操作符 结束，在栈顶得到运算结果

4. 将二项式 (a + b) i 展开, 其系数构成杨辉三角形。画出当n = 3的情况下，在打印过程中队列的变化。

步 n s Q→t s+t→Q t→s 输出s 队列Q的变化

(0) (1) (2) (3) (4) (5)

0 0 【1 1 0】

1 1 0 1 1 1 1 【1 0 1】

2 1 1 2 1 1 【0 1 2】

3 1 0 1 0 ― 【1 2 1】

0 0】 【1 2 1

4 2 0 1 1 1 1 0 1】 【2 1

5 1 2 3 2 2 0 1 3】 【1

6 2 1 3 1 1 【0 1 3 3】

7 1 0 1 0 ― 【1 3 3 1】

0 【1 3 3 1 0】

8 3 0 1 1 1 1 1】 【3 3 1 0

9 1 3 4 3 3 1 4】 【3 1 0

10 3 3 6 3 3 1 4 6】 【1 0

11 3 1 4 1 1 1 4 6 4】 【0

12 1 0 1 0 ― 【1 4 6 4 1】

5. stack

6. char

7. 利用"栈"作为辅助存储,将队列中的元素进行逆置.

五、算法分析题

参考答案：

1. 本算法的功能是判断一个字符数组（字符串）是否回文，即正读与反读都一样的字符串。

针对A[ ] = {m, a, d, a, m, i, m, a, d, a, m }，它先将串中的字符逐个进栈，再将栈中存放的字符逐个出栈，与串中的字符从头进行比较，若发现不等，则停止比较，返回0，表示该字符串不是回文。若所有栈中字符与串中字符都相等，则函数返回1，表示该字符串是回文。

2. 本算法的功能是将单链表逆置，即将链表中各结点的链接顺序逆转。

针对题中的输入实例：{ u, n, i, v, e, r, s, i, t, y }，将其逐个进栈后，从栈顶看，顺序为 { y, t, i, s, r, e, v, i, n, u }。顺序出栈后，链入结果单链表的链尾，最终得到的单链表中各结点中数据的逻辑顺序变为：{ y, t, i, s, r, e, v, i, n, u }。

六、算法设计题

参考答案：

1. 循环队列的定义

template class Queue { //循环队列的类定义

public:

Queue ( int=10 );

int EnQueue ( T x );

int DeQueue ( T& x );

private:

int rear, front, tag; //队尾指针、队头指针和队满标志

T *Q; //存放队列元素的数组

int m; //队列最大可容纳元素个数

}

template

int Queue :: EnQueue ( T x ) { //插入函数

if ( front == rear && tag == 1 ) return 0; //判队列是否满，满则返回0

rear = ( rear + 1 ) % m; //队尾进1, 队尾指针指示实际队尾位置

Q[rear] = item; //进队列

tag = 1; //标志改1，表示队列不空

}

template

int Queue :: DeQueue ( T& x ) { //删除函数

if ( front == rear && tag == 0 ) return 0; //判断队列是否不空，空则返回0

front = ( front + 1 ) % m; //队头进1, 队头指针指示实际队头的前一位置

tag = 0; //标志改0, 表示栈不满

x = Q[front]; //返回原队头元素的值

return 1;

合集下载

数据结构第3章栈和队列练习题

数据结构第3章栈和队列练习题

数据结构第3章栈和队列练习题

第三章栈和队列

一、 多项选择题

1.以下不是栈的基本运算的是()

a） 删除堆栈的顶部元素b）删除堆栈的底部元素C）判断堆栈是否为空d）将堆栈设置为空堆栈

2.若进栈序列为1,2,3,4,进栈过程中可以出栈,则下列不可能的一个出栈序列是()a)1,4,3,2b)2,3,4,1c)3,1,4,2d)3,4,2,1

3.堆栈和队列的共同点（）

a)都是先进先出b)都是后进先出

c） 仅在端点d）插入和删除元素没有任何共同之处

4.若已知一个进栈序列是1,2,3,……,n,其输出序列是p1,p2,vp3,……pn,若p1=n,则pi(1

a） ib）n-i

c)n-i+1d)不确定

5.判断堆栈st（最大大小）为空的条件是（a）st->Top==1b）st->Top==1

c)st->top!=maxsize-1d)st->top==maxsize-1

6.当使用堆栈指针HS将s指示的节点插入链堆栈时，执行（）a）HS->next=s；

b)s->next=hs->next;hs->next=s;c)s->next=hs;hs=s;

d） s-。下一个=hs；hs=hs->next；

7.在一个链式队列中.假设f和r分别为队头和队尾指针,则插入s所指的结点运算是()a)f->next=s;f=s;b)r->next=s;r=s;c)s->next=s;r=s;d)s->next=f;f=s;

8.在链式队列中，假设f和R分别是头指针和尾指针，删除节点的操作是（）a）R=f->next；b） r=r->next；c） f=f->next；d） f=r->next；9.以下关于线性表、堆栈和队列的描述错误（）

a)线性表是给定的n(n必须大于零)个元素组成的序列b)线性表允许在表的任何位置进行插入和删除操作c)栈只允许在一端进行插入和删除操作 d） 队列只能在一端插入，在另一端删除

数据结构课后习题答案第三章

数据结构课后习题答案第三章

第三章 栈和队列(参考答案)

// 从数据结构角度看，栈和队列是操作受限的线性结构，其顺序存储结构

// 和链式存储结构的定义与线性表相同，请参考教材，这里不再重复。

3.1 1 2 3 4 2 1 3 4 3 2 1 4 4 3 2 1

1 2 4 3 2 1 4 3 3 2 4 1

1 3 2 4 2 3 1 4 3 4 2 1

1 3 4 2 2 3 4 1

1 4 3 2 2 4 3 1

设入栈序列元素数为n，则可能的出栈序列数为C2nn=(1/n+1)*(2n!/(n!)2)

3.2 证明：由jpk 说明pj在pk之后出栈，即pj被pk 压在下面，后进先出。由以上两条，不可能存在i

3.3 void sympthy(linklist *head, stack *s)

//判断长为n的字符串是否中心对称

{ int i=1; linklist *p=head->next;

while (i<=n/2) // 前一半字符进栈

{ push(s,p->data); p=p->next; }

if (n % 2 !==0) p=p->next;// 奇数个结点时跳过中心结点

while (p && p->data==pop(s)) p=p->next;

if (p==null) printf(“链表中心对称”)；

else printf(“链表不是中心对称”)；

} // 算法结束

3.4

int match()

//从键盘读入算术表达式，本算法判断圆括号是否正确配对

第三章 栈与队列 习题及答案

第三章 栈与队列 习题及答案

第三章 栈与队列 习题及答案

第三章 栈与队列 习题及答案 一、基础知识题

3.1 设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：

(1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4),

Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈)?

(2) 能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。

(3)请分析 1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。 3.2 链栈中为何不设置头结点?

答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。 3.3 循环队列的优点是什么? 如何判别它的空和满?

答：循环队列的优点是：它可以克服顺序队列的\假上溢\现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的\空\或\满\不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间。每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。

3.4 设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何?

若只设尾指针呢?

答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。

帮你掌握数据结构(第三章系列经典试题及答案)

帮你掌握数据结构(第三章系列经典试题及答案)

1 第3章 栈和队列

一、填空题（每空1分，共15分）

1。 向量、栈和队列都是 线性 结构，可以在向量的 任何 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾

插入和 队首 删除元素。

2。 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。

3。 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。

4。 在一个循环队列中，队首指针指向队首元素的 前一个 位置。

5。 在具有n个单元的循环队列中，队满时共有 n-1 个元素.

6. 向栈中压入元素的操作是先 存入元素 ，后 移动栈顶指针。

7. 从循环队列中删除一个元素时，其操作是 先 移动队首指针 ，后 取出元素 。

8。 〖00年统考题〗带表头结点的空循环双向链表的长度等于 0 。

解：

二、判断正误(判断下列概念的正确性，并作出简要的说明。）（每小题1分，共10分）

（ × ）1。 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。

（ × ）2。 在表结构中最常用的是线性表,栈和队列不太常用。

错，不一定吧？调用子程序或函数常用，CPU中也用队列。

（ √ ）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。

（ √ ）4. 对于不同的使用者，一个表结构既可以是栈,也可以是队列，也可以是线性表.

正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。

( × ）5. 栈和链表是两种不同的数据结构。