1. 假设把整数关键码K散列到N个槽列表，以下哪些散列函数是好的散列函数
A: h(K)=K/N;
B: h(K)=1;
C: h(K)=K mod N;
D: h(K)=(K+rand(N)) mod N, rand(N)返回0到N-1的整数
D 最复杂, 选D
开放地址法: http://blog.csdn.net/w_fenghui/article/details/2010387
a. 线性探测再散列
b. 二次探测再散列
开放地址法不能直接删除某个元素, 这样会阻断后面的查询, 一般是设置无效位
再哈希法: 使用多个哈希函数
链地址法:冲突时, 延长冲突位的链表. 用于冲突比较严重的情况.
2.你认为可以完成编写一个C语言编译器的语言是：
A：汇编 B:C语言 C:VB D:以上全可以
解析：汇编肯定的可以的；任何语言都是可以自解释的，也就是可以用自己编写编译器解释自己，所以B也是对的；C应该也可以，不过答案已经出来了。
答案：D
3. 关于C++/JAVA类中的static成员和对象成员的说法正确的是：
C: 虚成员函数不可能是static成员函数
解析：
A：static成员变量在类的定义时初始化，不可以在对象的构造函数中初始化
B：static成员函数在对象成员函数中可以调用，同属于一个类作用域
C：static成员函数不可以声明为const和virtual
D：static成员函数只能访问static成员变量
答案：C
4.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 |
struct
A{ int
a; short
b; int
c; char
d;};struct
B{ int
a; short
b; char
c; int
d;};int
main() { cout << sizeof(A) << endl; cout << sizeof(B) << endl;} |
sizeof(A) sizeof(B) 的大小分别为 16, 12
对齐问题总结:
四个重要概念
1. 自身对齐值, 数据成员本身的大小. int 4byte, short 2byte, char 1 byte, double 8 byte.
2. 结构体自身对齐值, 结构体或类内最大的数据成员.
3. 指定对齐值, Linux 一般是 4 Byte, Visual Studio 中一般是结构体自身对齐值
4. 数据成员, 类, 结构体有效对齐值, 自身对齐值和指定对齐值中较小的那一个.
假设有效对齐值是 N, 那么
1. 一个数据成员的存放地址 % N = 0
2. 结构体占用内存的总长度是结构体有效长度的倍数.
有了这些知识, 我们来分析两个例子
|
1
2
3
4
5 |
struct
A { char
a; int
b; short
c; } |
假定默认的指定对齐值是 4
对于第一个数据成员 a, 其有效对齐值是 1, 放在 0x0000 位置时可以的.
第二个数据成员 b, 其有效对齐值是 4, 因此必须放到 0x0004 才可以
第三个数据成员 c, 有效对齐值是 2, 必须放到 0x0008 才可以
另外, 结构体的长度必须是结构体对齐值得倍数, 因此为 12
详细: http://blog.csdn.net/acorld/article/details/9104579
5. 用两种颜色去染排成一个圈的6个棋子，如果通过旋转得到则只算一种，一共有多少种染色：
A: 10 B:11 C:14: D:15
解析：应该有14种方案，设只有黑白两色，默认白色，那么，用p（n）表示有n个黑棋的种类
p（0）=p（6）=1
p（1）=p（5）=1
p（2）=p（4）=3 //相邻的一种，隔一个的一种，两个的一种
p（3）=4 //都相邻的一种，BB0B的一种，BB00B的一种，B0B0B的一种，一共4种
综上是14种
答案：C
6. 关于Linux系统的负载，以下表述正确的是：
A: 通过就绪和运行的进程数来反映
B: 通过 TOP 命令查看
C: 通过 uptime 查看
D: Load:2.5,1.3,1.1表示系统的负载压力在逐渐变小
答案：BC（对于A不确定）
三个数分别代表不同时间段的系统平均负载(一分钟、五 分钟、以及十五分钟)，它们的数字当然是越小越好。“有多少核心即为有多少负荷”法则： 在多核处理中，你的系统均值不应该高于处理器核心的总数量
7. 假设函数rand_k会随机返回一个【1，k】之间的随机数（k>=2）,并且每个整数出现的概率相等。目前有rand_7,通过调用rand_7（）和四则运算符，并适当增加逻辑判断和循环控制逻辑，下列函数可以实现的有：
A: rand_3 B: rand_21 C: rand_23 D: rand_49
答案：ABCD
解释：对于rand_x（x<7）的直接截断，只要rand数大于x直接忽略，保证rand_x能够做到概率相等。而对于其他的则采用7×rand_7+rand_7，可以-7得到rand_49，然后截断成rand_42，统一除以2，则是rand_21，其他类似。
8. 某二叉树的前序遍历序列为-+a*b-cd/ef，后序遍历序列为abcd-*+ef/-，问其中序遍历序列是___。
答案：a+b*c-d-e/f
9. 一次内存访问，SSD硬盘访问和SATA硬盘随机访问的时间分别是（）
A、几微秒，几毫秒，几十毫秒 B、几十纳秒，几十微秒，几十毫秒
C、几十纳秒，几十微秒，几十毫秒 D、几微秒，几十微秒，几十毫秒
解析：内存访问速度通常在50ns到80ns范围内，SSD硬盘的访问速度一般是SATA硬盘的一千多倍，所以答案选C
10. 判断有向图是否存在回路，利用（A）方法最佳
（1）每个内部节点有两个或三个子节点；
（2）所有的叶节点到根的路径长度相同；
如果一颗2-3树有9个叶节点，下列数量个非叶节点的2-3树可能存在的有（BE）
A、8 B、7 C、6 D、5 E、4
15. 下列有关进程的说法中，错误的是（ABC）
假设磁盘物理块大小为1KB，并且FAT序号以4bits为单位向上扩充空间。请计算下列两块磁盘的FAT最少需要占用多大的存储空间？
（1）一块540MB的硬盘 （2）一块1.2GB的硬盘
已知三个升序整数数组a[l]、b[m]、c[n]，请在三个数组中各找一个元素，使得组成的三元组距离最小，三元组的距离定义是：假设a[i]、b[j]和c[k]是一个三元组，那么距离为distance=max(|a[i]-b[j]|,|a[i]-c[k]|,|b[j]-c[k]|)，请设计一求最小三元组距离的最优算法，并分析时间复杂度。（不用写代码，不分析时间复杂度不得分）
解析：用三个指针分别指向a,b,c中最小的数，计算一次他们最大距离的Distance ，然后在移动三个数中较小的数组指针，再计算一次，每次移动一个，直到其中一个数组结束为止，最慢(l+ m + n)次，复杂度为O(l+ m + n)
详情请参考http://blog.csdn.net/thebestdavid/article/details/11975809的第4题
18. 在黑板上写下50个数字：1至50。在接下来的49轮操作中，每次做如下动作：选取两个黑板上的数字a和b檫去，在黑板上写|b-a|。请问最后一次动作之后剩下数字可能是什么？为什么？（不用写代码，不写原因不得分）
解析：参考两个解法：
http://blog.csdn.net/qqsxdong/article/details/12184707
http://www.cnblogs.com/ksedz/p/3346294.html
19. 请设计一个算法，在满足质因数仅为3,5,7或其组合的数中，找出第K大的数。比如K=1,2,3时，分别应返回3,5,7。要求算法时间复杂度最优。
20. 浮点数在计算中如何表示，如何对浮点数判等。
21. 写函数，输出前N个素数。不需要考虑整数溢出问题，也不需要使用大数处理算法
22. 长度为n的数组乱序存放着0至n-1. 现在只能进行0与其他数的swap，请设计并实现排序
原文：http://www.cnblogs.com/zhouzhuo/p/3632232.html