【计算机类职业资格】程序员面试-试卷1及答案解析.doc

1、程序员面试-试卷 1 及答案解析(总分：8.00，做题时间：90 分钟)1.输入 n 个整数，输出其中最小的 k 个。例如输入 1，2，3，4，5，6，7 和 8 这 8 个数字，则最小的 4 个数字为 1，2，3 和 4。（分数：2.00）_2.输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回 true，否则返回false。 例如输入 5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果： 8 / 6 10 / / 5 7 9 11 因此返回 true。如果输入 7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回 false。（分数：2

2、.00）_3.输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。例如输入“I am a student.”，则输出“student. a am I”。（分数：2.00）_4.求 1+2+n，要求不能使用乘除法、for、while、if、else、switch、case 等关键字以及条件判断语句（A?B:C）。（分数：2.00）_程序员面试-试卷 1 答案解析(总分：8.00，做题时间：90 分钟)1.输入 n 个整数，输出其中最小的 k 个。例如输入 1，2，3，4，5，6，7 和 8 这 8 个数字，则最小的 4

3、个数字为 1，2，3 和 4。（分数：2.00）_正确答案：(正确答案：我们可以开辟一个长度为 k 的数组。每次从输入的 n 个整数中读入一个数。如果数组中已经插入的元素少于 k 个，则将读入的整数直接放到数组中。否则长度为 k 的数组已经满了，不能再往数组里插入元素，只能替换了。如果读入的这个整数比数组中已有 k 个整数的最大值要小，则用读入的这个整数替换这个最大值；如果读入的整数比数组中已有 k 个整数的最大值还要大，则读入的这个整数不可能是最小的 k 个整数之一，抛弃这个整数。这种思路相当于只要排序 k 个整数，因此时间复杂可以降到 O(n+nlogk)。通常情况下 k 要远小于 n，所

4、以这种办法要优于前面的思路。 这是我能够想出来的最快的解决方案。不过从给面试官留下更好印象的角度出发，我们可以进一步把代码写得更漂亮一些。从上面的分析，当长度为 k 的数组已经满了之后，如果需要替换，每次替换的都是数组中的最大值。在常用的数据结构中，能够在 O(1)时间里得到最大值的数据结构为最大堆。因此我们可以用堆（heap）来代替数组。另外，自己重头开始写一个最大堆需要一定量的代码。我们现在不需要重新去发明车轮，因为前人早就发明出来了。同样，STL 中的 set 和 multiset 为我们做了很好的堆的实现，我们可以拿过来用。既偷了懒，又给面试官留下熟悉 STL 的好印象，何乐而不为之？

5、 参考代码： #include #include #include using namespace std; typedef multiset IntHeap; / / find k least numbers in a vector / void FindKLeastNumbers ( const vector if(k = 0 | data.size() root) break; / the nodes in the right sub-tree are greater than the root int j = i; for(; j 0) left = verifySquenceOfBS

6、T(squence, i); / verify whether the right sub-tree is a BST bool right = true; if(i Sum(n-1)+n; ; int solution2_Sum(int n) A a; B b; Array0 = Array1 = int value = Array1-Sum(n); return value; 这种方法是用虚函数来实现函数的选择。当 n 不为零时，执行函数 B:Sum；当 n 为 0 时，执行 A:Sum。我们也可以直接用函数指针数组，这样可能还更直接一些： typedef int (*fun)(int);

7、 int solution3_f1(int i) return 0; int solution3_f2(int i) fun f2=solution3_f1, solution3_f2; return i+f!i(i-1); 另外我们还可以让编译器帮我们来完成类似于递归的运算，比如如下代码： template struct solution4_Sum enum Value N = solution4_Sum:N + n; ; template struct solution4_Sum enum Value N = 1; ; solution4_Sum:N 就是 1+2+.+100的结果。当编译器看到 solution4_Sum 时，就是为模板类 solution4_Sum 以参数 100 生成该类型的代码。但以 100 为参数的类型需要得到以 99 为参数的类型，因为 solution4_Sum:N=solution4_Sum:N+100。这个过程会递归一直到参数为 1 的类型，由于该类型已经显式定义，编译器无需生成，递归编译到此结束。由于这个过程是在编译过程中完成的，因此要求输入 n 必须是在编译期间就能确定，不能动态输入。这是该方法最大的缺点。而且编译器对递归编译代码的递归深度是有限制的，也就是要求 n 不能太大。)解析：