[计算机类试卷]程序员面试模拟试卷1及答案与解析.doc

1、程序员面试模拟试卷 1及答案与解析 1 输入 n个整数，输出其中最小的 k个。 例如输入 1， 2， 3， 4， 5， 6， 7和 8这 8个数字，则最小的 4个数字为 1， 2， 3和4。 2 输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回 true，否则返回 false。 例如输入 5、 7、 6、 9、 11、 10、 8，由于这一整数序列是如下树的后序遍历结果： 8 / 6 10 / / 5 7 9 11 因此返回 true。 如果输 入 7、 4、 6、 5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。 3 输入一个英文句子，翻转句子中单词的

2、顺序，但单词内字符的顺序不变。句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。 例如输入 “I am a student.”，则输出 “student. a am I”。 4 求 1+2+n ，要求不能使用乘除法、 for、 while、 if、 else、 switch、 case等关键字以及条件判断语句（ A?B:C）。 程序员面试模拟试卷 1答案与解析 1 【正确答案】 我 们可以开辟一个长度为 k的数组。每次从输入的 n个整数中读入一个数。如果数组中已经插入的元素少于 k个，则将读入的整数直接放到数组中。否则长度为 k的数组已经满了，不能再往数组里插入元素，只能替换了。

3、如果读入的这个整数比数组中已有 k个整数的最大值要小，则用读入的这个整数替换这个最大值；如果读入的整数比数组中已有 k个整数的最大值还要大，则读入的这个整数不可能是最小的 k个整数之一，抛弃这个整数。这种思路相当于只要排序 k个整数，因此时间复杂可以降到 O(n+nlogk)。通常情况下 k要远小于 n，所以这种办法要优于前面的思路 。 这是我能够想出来的最快的解决方案。不过从给面试官留下更好印象的角度出发，我们可以进一步把代码写得更漂亮一些。从上面的分析，当长度为 k的数组已经满了之后，如果需要替换，每次替换的都是数组中的最大值。在常用的数据结构中，能够在 O(1)时间里得到最大值的数据结构

4、为最大堆。因此我们可以用堆（ heap）来代替数组。 另外，自己重头开始写一个最大堆需要一定量的代码。我们现在不需要重新去发明车轮，因为前人早就发明出来了。同样， STL中的 set和 multiset为我们做了很好的堆的实现，我们可以拿过来用。既偷了懒，又给 面试官留下熟悉 STL的好印象，何乐而不为之？ 参考代码： #include #include #include using namespace std; typedef multiset IntHeap; / / find k least numbers in a vector / void FindKLeastNumbers ( c

5、onst vector if(k = 0 | data.size() :const_iterator iter = data.begin(); for(; iter != data.end(); + iter) / if less than k numbers was inserted into leastNumbers if(leastNumbers.size() root) break; / the nodes in the right sub-tree are greater than the root int j = i; for(; j 0) left = verifySquence

6、OfBST(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不能太大。