学步园

作者：独酌逸醉
时间：2012.02.29

题目来源:http://www.cppleyuan.com/viewthread.php?tid=8033 (它是来自那里我就不知道了!)
答案来自一些书籍、网站和我个人的想法，如果存在错误或者您有不同的看法，请联系我(博客的右上方)。

一 数据结构和算法
1. 简述什么是 hashtable ，如何解决 hash 冲突
答: 首先要明确的一点是建立 hashtable 是为了查找的高效，也就说是用来做查找的。关于查找算法，我们知道的有“折半查找”、“二叉排序树”、“B-树”等查找方法。我列举的几种查找方法，他们的共性是:“查找的效率取决于比较的次数”，当然比较的次数越少，效率当然越好了。

“理想的情况是希望不经过任何的比较，一次存取便能得到所查的记录，那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系 f ，使每个关键字和结构中的一个唯一的存储位置想对应。因而在查找时，只需要根据这个对应关系 f 找到给定值 K 的像 f(K) 。若结构中存在关键字和 K 相等的记录，则必定在 f(K) 的存储位置上，由此，不需要进行比较便可直接取得所查记录。在此，我们称这个对应关系 f 为哈希(Hash) 函数，按这个思想建立的表称为哈希表。”——严蔚敏《数据结构(C语言版)》。

使用哈希表的难点在于哈希函数的构造和如何解决冲突。如何构造哈希函数需要具体问题具体分析了，我觉得没有特定的方法。
冲突是如何产生的？“由关键字得到的哈希地址上已经存在记录”。如何处理冲突？为关键字的记录找到一个“空”的哈希地址来存放记录。严蔚敏书中提到了几种处理冲突的方法:
(1) 开放定址法：听名字不好理解，其实很好理解。就是为关键字进行特定的(某个定值或者随机值)偏移，直到找到一个空的记录，放进去。找工作的时候，面试官可能听到的是“线性探测再散列”、“二次探测再散列”、“随机探测再散列”，其实就是一个偏移而已，根据不同的偏移方法起了这 3 个名字。
(2)再哈希法：使用另一种哈希方法确定位置
(3)链地址法：在没看书之前，我想到的就是这个方法。也就是当出现冲突的时候，在记录的后面再加一条记录。这时，一维表就变成了二维表。也就是出现了 1 对 n 的情况，而这 n 条记录是一个数组或者链表。

2．什么叫二叉树，满二叉树，完全二叉树
答：二叉树：“每个结点至多有两个结点”。
满二叉树：“每一层的结点数都是最大结点数”
完全二叉树：每一层的结点不一定是最大结点数，但是所有的结点都是从左向右排列的，中间没有空缺。
以上 3 种说法是最通俗的解释了。

3．数组和链表有什么区别，分别用在什么场合
答：数组和链表的区别在于它们的存储方式。数组在内存是顺序排列的；链表是分散开的，使用后继指针来连接起来。根据它们的存储方式便可以确定了它们的使用场合。顺序排列的优势在于查找方便、节省内存、访问效率高；链式的优势在于插入和删除效率远高于顺序排列，不需要大量的元素搬迁。这道题真的是算非常简单的了，不过就我的经历再说，假如可以从数组和链表的问题扯到其他问题上，一定是你熟悉的问题，这就需要技术了。
顺便扯一扯面试吧，不要让面试官去问你问题，这样你很被动，如果你可以从一个问题扯到另外一个问题，而这个问题又是你擅长的。时间很快就过去了，面试官也对你有了一个不错的印象。比如，从链式存储，你可以扯到链表，扯到你曾经做过的一个项目怎样的存储，造成了怎样的后果。再如，链式存储，可以扯到磁盘的访问，操作系统。很多人去面试，不是因为自己的能力不强，而是没有把自己强势的一面展现给面试官。一定要告诉面试官，你做过那些事情，你能做那些事情。让他对你这个人感兴趣，那么，你就等 offer 吧。

二 操作系统
1.什么叫虚拟内存
答：http://zh.wikipedia.org/wiki/%E8%99%9A%E6%8B%9F%E5%86%85%E5%AD%98
挺好理解，想一想，又挺不好理解的。

2.块设备和字符设备有什么区别
答：这是针对 linux 系统的吧，在 windows 至少没有听过这两个概念。
区别在于它们的访问方式不同，块设备是以块为单位(大小固定)随机无序，字符设备是字符流顺序访问。根本区别在于是否可以被随机访问。
块设备：硬盘
字符设备：键盘

3.进程和线程的区别
答：http://blog.csdn.net/andy6355/article/details/2506171 写的挺好的。
(1)进程最大的访问空间是 4G (32位机)。
(2)现在操作系统的调度单位一般为线程，原因很简单，线程更小，调度起来方便。
(3)线程一般没有自己的独立内存，使用进程的内存空间。
(4)一个进程的执行，至少需要一个线程。
(5)进程的线程，共享进程的内存。

4．简述TCP网关连接交互细节
答：网络方面我真是不懂，你自己在网上找些资料吧。说到这个问题，在面试的时候不要打肿脸充胖子。没听过就是说没听过，不要胡乱猜测，闹笑话。

三 Linux
1.写出10个常用的linux命令和参数
答：这个就多了，随便写几个吧。
ls -l
ls -a
cd /
cd ~
sudo -i
rm -r
touch
mkdir
rmdir
emacs
ps
kill
shutdown -r
shutdown -h
man
tar
…

2.如何查看磁盘剩余空间
答：df -hl

3.如何查看端口是否被占用
答：使用 netstat 命令，具体怎么用，自己 man 去吧。

4.如何查看某个进程所占用的内存
答：首先找到进程的 pid， 然后cat /proc/[pid]/status

四 程序题（具体题目记不太清了）
1.用两个线程实现1-100的输出
答：这个题目是什么意思，我没怎么懂。考点在哪里？我想是加锁吧。

2.把一个文件夹中所有01结尾的文件前十行内容输出
答：这道题我觉得考点是：
(1) 文件夹下文件的遍历。像这种题其实是最简单的，因为不同的操作系统会提供不同的 API ，直接去调用就行了。比如 windows 的 FindFirstFile FindNextFile 。
(2) 字符串的处理。获取文件路径(字符串)的后两个字母，然后和 “01″ 比较
(3) 文件读写。这个就更简单了。文件打开，一行一行的读就行了。