算法(4th ed)(142):基础——背包、队列和栈 5.6

阅读数:6 2019 年 11 月 6 日 07:41

算法(4th ed)(142):基础——背包、队列和栈 5.6

(练习)

1.3.1 为 FixedCapacityStackOfStrings 添加一个方法 isFull()

1.3.2 给定以下输入,java Stack 的输出是什么?

复制代码
it was - the best - of times - - - it was - the - -

1.3.3 假设某个用例程序会进行一系列入栈和出栈的混合栈操作。入栈操作会将整数 0 到 9 按顺序压入栈;出栈操作会打印出返回值。下面哪种序列是不可能产生的?

a. 4 3 2 1 0 9 8 7 6 5

b. 4 6 8 7 5 3 2 9 0 1

c. 2 5 6 7 4 8 9 3 1 0

d. 4 3 2 1 0 5 6 7 8 9

e. 1 2 3 4 5 6 9 8 7 0

f. 0 4 6 5 3 8 1 7 2 9

g. 1 4 7 9 8 6 5 3 0 2

h. 2 1 4 3 6 5 8 7 9 0

1.3.4 编写一个 Stack 的用例 Parentheses,从标准输入中读取一个文本流并使用栈判定其中的括号是否配对完整。例如,对于 ()]{}{[()() } 程序应该打印 true,对于 [(]) 则打印 false

1.3.5 当 N50 时下面这段代码会打印什么?从较高的抽象层次描述给定正整数 N 时这段代码的行为。

复制代码
Stack<Integer> stack = new Stack<Integer>();
while (N > 0)
{
stack.push(N % 2);
N = N / 2;
}
for (int d : stack) StdOut.print(d);
StdOut.println();

:打印 N 的二进制表示(当 N50 时打印 110010)。

1.3.6 下面这段代码对队列 q 进行了什么操作?

复制代码
Stack<String> stack = new Stack<String>();
while (!q.isEmpty())
stack.push(q.dequeue());
while (!stack.isEmpty())
q.enqueue(stack.pop());

1.3.7 为 Stack 添加一个方法 peek(),返回栈中最近添加的元素(而不弹出它)。

1.3.8 给定以下输入,给出 DoublingStackOfStrings 的数组的内容和大小。

复制代码
it was - the best - of times - - - it was - the - -

1.3.9 编写一段程序,从标准输入得到一个缺少左括号的表达式并打印出补全括号之后的中序表达式。例如,给定输入:

复制代码
1 + 2 ) * 3 - 4 ) * 5 - 6 ) ) )

你的程序应该输出:

复制代码
( ( 1 + 2 ) * ( ( 3 - 4 ) * ( 5 - 6 ) ) )

1.3.10 编写一个过滤器 InfixToPostfix,将算术表达式由中序表达式转为后序表达式。

1.3.11 编写一段程序 EvaluatePostfix,从标准输入中得到一个后序表达式,求值并打印结果(将上一题的程序中得到的输出用管道传递给这一段程序可以得到和 Evaluate 相同的行为)。

1.3.12 编写一个可迭代的 Stack 用例,它含有一个静态的copy() 方法,接受一个字符串的栈作为参数并返回该栈的一个副本。注意:这种能力是迭代器价值的一个重要体现,因为有了它我们无需改变基本 API 就能够实现这种功能。

1.3.13 假设某个用例程序会进行一系列入列出列的混合队列操作。入列操作会将整数 0 到 9 按顺序插入队列;出列操作会打印出返回值。下面哪种序列是不可能产生的?

a. 0 1 2 3 4 5 6 7 8 9

b. 4 6 8 7 5 3 2 9 0 1

c. 2 5 6 7 4 8 9 3 1 0

d. 4 3 2 1 0 5 6 7 8 9

1.3.14 编写一个类 ResizingArrayQueueOfStrings,使用定长数组实现队列的抽象,然后扩展实现,使用调整数组的方法突破大小的限制。

1.3.15 编写一个 Queue 的用例,接受一个命令行参数 k 并打印出标准输入中的倒数第 k 个字符串(假设标准输入中至少有 k 个字符串)。

1.3.16 使用 1.3.1.5 节中的 readInts() 作为模板为 Date 编写一个静态方法 readDates(),从标准输入中读取由练习 1.2.19 的表格所指定的格式的多个日期并返回一个它们的数组。

1.3.17 为 Transaction 类完成练习 1.3.16。

评论

发布