数据结构复习笔记

第2章 线性表

算法设计题

1.设计一个O(N)的算法, 将$a_1, a_2, \cdots, a_n$的链表转换为$a_1, a_3, \cdots, a_n, \cdots, a_4, a_2$的链表.

第3章 栈和队列

算法设计题

1.设计用两个栈模拟一个队列的算法, 以及用两个队列模拟一个栈的算法.

2.中缀表达式求值 后缀表达式求值

3.对于一个双端队列, 给出一个输入序列, 如1, 2, 3, 4, 分别求出满足下列条件的输出序列.

• 能由输入受限的双端队列得到, 但不能由输出受限的双端队列得到.

• 能由输出受限的双端队列得到, 但不能由输入受限的双端队列得到.

• 既不能由输入受限的双端队列得到, 也不能由输出受限的双端队列得到.

输入受限/输出受限的双端队列

• 允许在一段进行插入和删除, 另一端只允许插入的双端队列称为输出受限的双端队列

• 允许在一段进行插入和删除, 另一端只允许删除的双端队列称为输入受限的双端队列

Answer

可能没太多意思, 答案方法是枚举所有排列逐一检查的.

123

4 1 3 2

4 2 1 3

4 2 3 1