Applicant PK Examiner

 

拿到一份对应届毕业生的面试题：

2． 问题：

a) 请描述数组(array)和链表(link list)的相同点和不同点？

答案：

都是线性有序结构，数组是一块连续的内存区，可以通过index直接存取，访问速度较快，但是插入删除要移动其他单元。增加长度时可能需要重新分配内存。占用内存较少。

链表每个存储单元有指针指到下一个单元，占用内存较多，插入删除方便快速，只需要重设指针，增加长度无需重新分配内存。

b) 哪一个占用内存少，哪一个插入删除比较快。为什么？

答案: 数组占用内存较少，不需要额外空间保存指针。插入删除要批量移动数据所以较慢。链表插入删除只需要调整指针，所以较快，要存储指针所以内存占用多。

数组是不能插入和删除的，问题应该精确一点，应该说“基于数组的数据结构”

3． 问题：

a) 请问哈希表(hashtable)是如何存储数据的？

答案： Hashtable是用来存储key和value对的数据结构, 根据设定的hash函数H(key)和处理冲突的方法将一组关键字（key）映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”作为记录在表中存储位置，这种表便成为hashtable.

b) 是否两个键值通过hash函数产生的映射地址会一样？怎么办？

答案: 是，一般情况下，完全避免冲突是很难的。因为通常关键字集合会比目标地址空间大。哈希函数要尽量避免冲突（避免不同的关键字产生相同的hash值），使一组关键字的哈西地址尽可能的均匀分布在整个地址区间。所以有一些冲突处理方法：开放定址法，再哈希法，链地址法（用链表保存冲突的值），公共溢出区。

关于哈希表，有个与实际编程更密切的问题可以一问：为保证逻辑上的正确性，哈希表对可以作为键值的类型有什么要求？

• C++：除容器对元素类型的标准需求外，还需overload == 和 <

• Java：需override equals(逻辑上的正确性)和hashCode(性能)

• C#：需override Equals(逻辑上的正确性)和HashCode(性能)

 

4． 问题：

a) 冒泡(bubble sort)和快速排序(quick sort)的区别？它们的时间复杂度？

冒泡：每趟排序将最大值安置到最后一个位置上，时间复杂度为 O(n平方).

快速排序法是对起泡排序法的一种改进，基本思想是通过一趟排序将待排序纪录分割成独立的两部分，其中一部分纪录的关键字均比另一部分纪录的关键字小，则可以分别对这两部分纪录继续进行排序，以达到整个序列有序。时间复杂度为 O(NlogN).

b) 在什么情况下快速排序的效果最差？

答案：输入数据逆序排列时效果最差，蜕化成冒泡

5． 问题：

a) 程序运行时，在堆(heap)和栈(stack)上分配内存有什么区别？

栈用来保存局部变量，函数返回值，参数等。在函数返回时会退栈（pop）.

堆用来分配空间给动态生成的对象。

6． 问题

C/C++或者java中函数调用时传递参数有几种方法，区别是什么？

答案：传值和传引用或指针

int,float,long等primitive是传值

对值的修改会在函数返回退栈时丢失。

对象类型传引用或指针

通过指针或引用可以访问并修改对象的属性。

这个问题的答案基本上是语无伦次的，居然还有传指针这种方式

• C++：缺省传值，不管primitive还是custom class类型，显式使用&修饰后传引用，不管primitive还是custom class类型

• Java：只有传值一种方式，不管primitive还是custom class

• C#：缺省传值，不管primitive还是custom class，显式使用out或ref修饰后传引用，不管primitive还是custom class

总之，参数传递方式和数据类型是没有关系的，关于这个问题，误解甚多，之前曾经也说过，其实对C++的误解倒不是很多，受害的基本都是被 业余教材耽误的Java程序员，请转载，转贴下面这段话，一定要把这个错误观念纠正过来！纠正过来！纠正过来！

“Some people will say incorrectly that objects are passed "by reference." In programming language design, the term pass by reference properly means that when an argument is passed to a function, the invoked function gets a reference to the original value, not a copy of its value. If the function modifies its parameter, the value in the calling code will be changed because the argument and parameter use the same slot in memory. If the Java programming language actually had pass-by-reference parameters, there would be a way to declare halveIt so that the above code would modify the value of one, or so that commonName could change the variable sirius to null. This is not possible. The Java programming language does not pass objects by reference; it passes object references by value. Because two copies of the same reference refer to the same actual object, changes made through one reference variable are visible through the other. There is exactly one parameter passing modepass by valueand that helps keep things simple.”

---<The Java Programming Language> 4th Edition, 2.6.5. Parameter Values

其实，在Java中，是无法写出一个swap函数，来交换两个参数的值的

a = object1 = new SomeClass();

b = object2 = new SomeClass();

swap(a, b);

assert a == object2; //这样一个swap函数是不存在的

assert b == object1; //这样一个swap函数是不存在的

7． 问题：

a) 面向对象设计的3个原则是什么?

答案：

Encapsulation（封装）, Inheritance（继承）, Polymorphism（多态）.

首先问题本身还是不够确切，如果是问原则的话，可以回答诸如“Liskov替换原则”，“开闭原则”，“依赖倒置原则”等，甚至“包含优先继承”，“针对接口编程”等，从答案看，似乎“面向对象的3个本质特征是什么”，或者“满足哪3个特征的程序才是面向对象程序”更合适些

其次，答案也不算准确，我的理解是“多态”才是面向对象的本质特征，继承只是实现多态的一种手段，或许有复用目的，但复用与面向对象无关；举例来说：

• 不支持继承的C语言，依然可以写出面向对象的程序，使用函数指针来得到多态行为

• 如果C语言的例子不足以说明问题，那么Java总可以了吧，Java中使用反射按方法名称调用，依然可以实现多态，写出面向对象的程序，在此过程中，继承无影无踪

• AOP，呵呵，不是Aspect，讨论Attribute Oriented足矣，此时继承依然不见踪影，而程序依然多态，依然面向对象

 

b) Java:

Java中class是否可以继承多少个父类？不能，只能继承一个

Java中class是否可以实现多少个接口？没有限制

Java中一个interface可以继承多少个interface？没有限制

Java中所有类都继承同一个父类吗？YES, from Object.

这样做有什么好处？Vector, Hashmap等操作Object，可应用于各种class.

这样做有什么坏处？没有编译时类型检查。JDK1.5增加了类似模板的语法来解决这类问题。

单根和多根之间的争论不是这么简单就说清楚的，不过面试题毕竟是对应届毕业生

c) C++:

class是否可以继承多个父类？是

所有类都继承一个父类吗？否

一个子类的指针可以指向一个父类的实例吗？不行。

命名空间解决什么问题？避免几个不同库中的命名冲突。

模板的用途是什么？用相同的代码处理不同的对象类型，可以有编译时类型检查。

可以定义Virtual destructor吗?是