新浪技术部笔试题

答: 首先要明确的一点是建立 hashtable 是为了查找的高效，也就说是用来做查找的。 关于查找算法，我们知道的有「折半查找」、「二叉排序树」、「B-树」等查找方法。 我列举的几种查找方法，他们的共性是：「查找的效率取决于比较的次数」，当然比较的次数越少，效率当然越好了。

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

– 严蔚敏《数据结构(C语言版)》

使用哈希表的难点在于哈希函数的构造和如何解决冲突。如何构造哈希函数需要具体问题具体分析了，我觉得没有特定的方法。

冲突是如何产生的？「由关键字得到的哈希地址上已经存在记录」。如何处理冲突？为关键字的记录找到一个「空」的哈希地址来存放记录 f 。 严蔚敏书中提到了几种处理冲突的方法:

• 开放定址法：听名字不好理解，其实很好理解。就是为关键字进行特定的(某个定值或者随机值)偏移，直到找到一个空的记录，放进去。 找工作的时候，面试官可能听到的是「线性探测再散列」、「二次探测再散列」、「随机探测再散列」，其实就是一个偏移而已， 根据不同的偏移方法起了这 3 个名字。
• 再哈希法：使用另一种哈希方法确定位置。
• 链地址法：在没看书之前，我想到的就是这个方法。也就是当出现冲突的时候，在记录的后面再加一条记录。这时，一维表就变成了二维表。也就是出现了 1 对 n 的情况，而这 n 条记录是一个数组或者链表。

答：

• 二叉树：每个结点至多有两个结点。
• 满二叉树：每一层的结点数都是最大结点数。
• 完全二叉树：每一层的结点不一定是最大结点数，但是所有的结点都是从左向右排列的，中间没有空缺。

答：数组和链表的区别在于它们的存储方式。数组在内存是顺序排列的；链表是分散开的，使用后继指针来连接起来。 根据它们的存储方式便可以确定了它们的使用场合。顺序排列的优势在于查找方便、节省内存、访问效率高； 链式的优势在于插入和删除效率远高于顺序排列，不需要大量的元素搬迁。

http://zh.wikipedia.org/wiki/%E8%99%9A%E6%8B%9F%E5%86%85%E5%AD%98

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

块设备：硬盘
字符设备：键盘

答：http://blog.csdn.net/andy6355/article/details/2506171 写的挺好的。

• 进程最大的访问空间是 4G (32位机)。
• 现在操作系统的调度单位一般为线程，原因很简单，线程更小，调度起来方便。
• 线程一般没有自己的独立内存，使用进程的内存空间。
• 一个进程的执行，至少需要一个线程。
• 进程的线程，共享进程的内存。

df -hl

• netstat
• lsof

首先找到进程的 pid， 然后 cat /proc/[pid]/status 。

这个题目是什么意思，我没怎么懂。考点在哪里？我想是加锁吧。

答：这道题我觉得考点是：

• 文件夹下文件的遍历。像这种题其实是最简单的，因为不同的操作系统会提供不同的 API，直接去调用就行了。 比如 windows 的 FindFirstFile FindNextFile 。
• 字符串的处理。获取文件路径(字符串)的后两个字母，然后和 "01" 比较
• 文件读写。这个就更简单了。文件打开，一行一行的读就行了。