4. 下面哪一种属于“creational”的设计模式？
A. Façade
B. Singleton
C. Bridge
D. Composite
E. 上面都不是
答案：B
Creational包括下面几种： Singleton ；Factory Method ；Abstract Factory；Builder ；Prototype
具体可以参看这里： http://terrylee.cnblogs.com/archive/2006/01/16/318285.html 简单记忆就就是 abspf （对比之前的DOSLI）
常见的五种创建型模式
单件模式（Singleton Pattern）解决的是实体对象的个数问题，其他的都是解决new所带来的耦合关系问题。
工厂方法模式（Factory Pattern）在工厂方法中，工厂类成为了抽象类，其实际的创建工作将由其具体子类来完成。工厂方法的用意是定义一个创建产品对象的工厂接口，将实际创建工作推迟到子类中去，强调的是“单个对象”的变化。
抽象工厂模式（Abstract Factory）抽象工厂是所有工厂模式中最为抽象和最具有一般性的一种形态。抽象工厂可以向客户提供一个接口，使得客户可以在不必指定产品的具体类型的情况下，创建多个产品族中的产品对象，强调的是“系列对象”的变化。
生成器模式（Builder Pattern）把构造对象实例的逻辑移到了类的外部，在这个类的外部定义了这个类的构造逻辑。他把一个复杂对象的构造过程从对象的表示中分离出来。其直接效果是将一个复杂的对象简化为一个比较简单的目标对象。他强调的是产品的构造过程。
原型模式（Prototype Pattern）和工厂模式一样，同样对客户隐藏了对象创建工作，但是，与通过对一个类进行实例化来构造新对象不同的是，原型模式是通过拷贝一个现有对象生成新对象的。
------------------------------------------------------------------------------------------------------------------
18. 下面哪些使用的是贪心算法
A. 单源最短路径中的Dijkstra算法
B. 最小生成树的Prim算法
C. 最小生成树的Kruskal算法
D. 计算每对顶点最短路径的Floyd-Warshall算法
E. 字符串匹配中的KMP算法
答案：A，B，C
贪心：Dijkstra，Prim，Kruskal （算法导论中已明确说明）。
Kruskal：初始化每个顶点为只有一个根几点的树，将边的权值按从小到大排序，选择权值最小的边(u,v)，如果u和v不在一颗树中，则将u和v所在两棵树合并，边(u,v)加入到集合中，直到所有的边都找完。
Prim：从任意顶点出发，维护一个树A，每一步，选择最小的边连接G(V,A)，将结点V加入到树A中，直到所有的顶点都找完。
动态规划：Floyd-Warshall，KMP
-------------------------------------------------------------------------------
19.
Class A{
Public:
Intk1;int k2;
};
一个数组A a[5]={{3,4},{6,5},{2,7},{3,1},{1,2}}
下面哪一个是函数调用之后的结果
{{1,2},{2,7},{3,1},{3,4},{6,5}}
A. f1(a,5,cmp)
B. f2(a,5,cmp)
C. f3(a,5,cmp)
D. f4(a,5,cmp)
E. 以上都不对
答案：A，D
这道题出的很有意思，乍一看，题干这么大，可能会被唬住，其实冷静下来看一下，很简单，就是一个排序的稳定性非稳定性的分析。所谓稳定性，即：保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同，如果排序的结点仅仅是一个数，则稳定性意义不大，但是如果有多个键值，就需要考虑稳定性的分析。例如，对于本题，如果排序算法是稳定的，那么因为原数组{3,4}排在{3,1}前，根据稳定性的定义，排序的结果就一定不会出现{3,1}排在{3,4}前的情况。而如果算法是不稳定的，那么只能说，{3,1}有排在{3,4}前面的可能，需要根据具体的排序过程判断是否相等的值会变换位置。关于八种算法稳定性的分析，可以查看http://hi.baidu.com/shismbwb/item/404c94898cfd2855850fab24。选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。
所以，首先明确四个函数都采用了什么样的排序算法：
f1:选择排序；f2:直接插入排序；f3:冒泡，f4:快排
f2和f3是稳定的，直接pass掉。然后非稳定的再看是否变换了位置。A和D如果走一遍程序的话，会发现{3,4}和{3,1}这两个元素是变了顺序的。
对于A答案，a[5]={{3,4},{6,5},{2,7},{3,1},{1,2}}
第一遍排序：{{1,2},{6,5},{2,7},{3,1},{3,4}}
第二遍排序：{{1,2},{2,7},{6,5},{3,1},{3,4}}
第三遍排序：{{1,2},{2,7},{3,1},{6,5},{3,4}}
第四遍排序：{{1,2},{2,7},{3,1},{3,4},{6,5}}
所以正确
对于D答案，a[5]={{3,4},{6,5},{2,7},{3,1},{1,2}}
第一遍排序的运行过程是这样的。
初始：low=0,high=4,i=0,t={3,4}
For循环：
J=1, c({6,5},t)>0,i=0,没有交换(a[i],a[j]),{{3,4},{6,5},{2,7},{3,1},{1,2}}
J=2,c({2,7},t)<0,i=1,交换({6,5},{2,7}),{{3,4},{2,7},{6,5},{3,1},{1,2}}
J=3, c({3,1},t)=0,i=2,交换({6,5},{3,1})，{{3,4},{2,7},{3,1},{6,5},{1,2}}
J=4, c({1,2},t)<0,i=3，交换({6,5},{1,2})，{{3,4},{2,7},{3,1},{1,2},{6,5}}
最后，执行exchange(a,low,i), 交换({3,4},{1,2})，{{1,2},{2,7},{3,1},{3,4},{6,5}}
得到第一遍排序结果：{{1,2},{2,7},{3,1},{3,4},{6,5}}，找到了{3,1}的位置，已经在{3,4}的前面，所以最后的结果一定与预期结果相同。这里需要非常注意的是在_f41函数中,if(c(a[j],t)<=0)，如果写成c(a[j],t)<0的话，则该答案也不会选择。所以最终的答案是A和D