CS203 2016秋 期中

2016-2017 学年 秋季学期 期中考试 A

一 填空题、简答题 40分

1-1

已知入栈序列依次为 $\mathrm{a},\mathrm{b},\mathrm{c},\mathrm{d}$ 请选择下列所有不可能出现的出栈序列 $\underset{―}{}$

• A．$a,d,b,c$
• B．$a,d,c,b$
• C．$b,a,c,d$
• D．$b,d,a,c$
• E．$b,d,c,a$

选 AD

1-2

请写出中缀表达式 $3+((1+2)\ast 2-2)\ast 3$ 所对应的后缀表达式

$312+2\ast 2-3\ast +$

1-3

请写出后缀表达式$3451-\ast +3-$的计算结果 $\underset{―}{}$

16

1-4

设栈 S 和队列 Q 的初始状态为空, 元素 $e_1,e_2,e_3,e_4,e_5$ 和 $e_6$ 依次通过栈, 一个元素出栈后即进入队列 Q , 若 6 个元素出队的序列为 $e_2,e_4,e_3,e_6,e_5,e_1$ , 则栈 S 的容量至少应该是 $\underset{―}{}$

3

1-5

在具有 n 个单元的顺序存储的循环队列中, 假设 front 和 rear 分别为队头、队尾的索引, 请分别写出：

• a．判断队空条件 $\underset{―}{}$.
• b．判断队满条件 $\underset{―}{}$.

1-6

使用一个大小为 6 的数组来实现循环队列, 若当前 rear 和 front 的值分别为 4和 2 , 则向队列中加入两个元素后, rear 的值变为 $\underset{―}{}$ , 再删除一个元素后, front 的值变为 $\underset{―}{}$

0, 3

1-7

请写出字符串"hello"中子串的数目 $\underset{―}{}$

15

1-8

字符串匹配：在串 $S=$"aababcbcabcababc"中查找 $\mathrm{T}=$"abcaba"

1-8-1

请写出 KMP 算法中模式函数的值 $\mathrm{next}(\mathrm{n})$

下标	0	1	2	3	4	5
T[n]	a	b	c	a	b	a
next(n)

-1, 0, 0, 0, 1, 2

1-8-2

请根据 1)中的 $\mathrm{next}(\mathrm{n})$ 数组, 请仿照下图画出匹配过程, 即用图示表示出每一轮匹配 T 在 S 中的位置, 并写出下标

1-8-3

请写出简单匹配算法(朴素匹配算法)的时间复杂度 $\underset{―}{}$ (简单匹配算法请见下图). 根据 2)中匹配规律, 写出 KMP 算法时间复杂度 $\underset{―}{}$

	a	a	b	a	b	c	b	c	a	b	c	a	b	a	b	c
Loop1	a	b	c	a	b	a										0
Loop2		a	b	c	a	b	a
Loop3			a	b	c	a	b	a
...
Loop9									a	b	c	a	b	a

$O(MN)$, $O(M+N)$

算法题

2-1 14分(7+7)

对一个整数连续做这样的运算, 即除2之后再减一, 连续做n次之后的运算结果为1, 问这个数字初始值为多少? 请分别用下列两种方式实现.

1. 用递归方式实现
2. 用非递归方式实现

2-2 12分

建立两个单链表, 长度未知. 设计算法找出两个单链表中第一个公共节点, 尽可能设计优化算法降低时间复杂度

请在编码前, 用一两句文字简要的描述一下你的逻辑

• 如果算法时间复杂度为 $O(m+n)$, 12分
• 如果算法时间复杂度为 $O(mn)$, 8分

2-3 12分

利用下列已经定义好的 double 型栈结构, 实现根据已知的后缀表达式, 求出该后缀表达式的运算结果

Stack_Double
- capacity: int
- S: double[]
- top: int
+ Stack_Double(int)
+ isEmpty(): boolean
+ push(double): void
+ top(): double
+ pop(): double

2-4 10分

给出链式队列的类定义, 并写出相应的入队和出队方法

2-5 12分

已知"回文字符串"表示一个字符串是从左读、右读都一样的字符串, 例如 "level", "aa", "noon"．设计算法判断字符串是否含有回文字符串, 例如： "analyze"为包含, "alone"为不包含.

请在编码前, 用一两句文字简要概述一下你的逻辑