chapter03
复制本地路径 | 在线编辑
1. 插入排序
1.1 分别分析数组和列表的复杂度
1.2 证明列表的比较次数，数组的移动次数是n^2/4
1.3 证明平均有O(logn)个元素不需要移动
2. 选择排序
2.1 Trick1 如何确保稳定性
2.2 Trick2 如何减少移动的操作次数
3. 归并排序
3.1 说出列表中使用归并排序的方法
3.2 说明为什么每次都需要用O(n)的时间去找中点
4. 插入排序和逆序对之间的关系
4.1 证明: 在插入排序过程中逆序对间距不会扩大
4.2 证明: 插入排序运行时间为O(I+n)
5. 反转链表的方法，要求给出详细代码
1. 栈混洗问题
1.1 证明B不含{k,i,j}(i<j<k) === B是栈混洗
1.2 证明B不含{j+1,i,j}(i<j) ==> B是栈混洗
1.3 证明B不含{k,j-1,j}(j<k) ==> B是栈混洗
1.4 证明栈混洗等价于n对括号组成的表达式
1.5 求栈混洗的数目(4-4)
2. 计算表达式
2.1 详细给出转为中缀表达式的代码
2.2 若某一时刻，操作符栈中有x个括号，计算此时操作符栈的最大规模数
2.3 对于教材中的计算表达式代码，给出一个反例，并且给出修补措施
3. 回溯法问题
3.1 编写程序，要求给定一个整数S，给出所有值为S的表达式(+*!/-^())
3.2 编写程序，解决八皇后问题
4. 环形队列为什么最后要空一个？即为什么tail指向的是空单元？
如果不指向空单元，即tail指向最后一个存放的单元位置。
判断是否满的依据就是 head == (tail + 1) (忽略模)
判断是否空的依据也是 head == (tail + 1) (忽略模)
这样就没法判断了。
你可以说为什么不增加valid bit。我觉得两种可能。
1. 空间上假如存储一个单元是64 bit，那么只要队列大于64，那就空间而言，牺牲一个存储单元比增加valid bit要好。
2. 时间上也是如此，每次还要更改valid bit，相当于增加一次数据访问。
valid bit好处
如果要放东西的时候，那考虑是否是满的，判断tail+1是否valid即可。
如果要取东西的时候，要考虑是否是空的，判断tail是否valid即可。
5. 如何实现Stack的getMax操作，此时push和pop操作仍为O(1)
6. 如何实现Queue的getMax操作，此时enqueue可宽容为分摊复杂度为O(1)