前言
我明天上午9点还有面试，今天突然看到某大牌IT公司笔试题目，必须做一下了
题目
一、单选题
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的整数
选择C，解释：开始纠结于C和D，但是hash的特性在于常数的时间执行插入、删除和查找操作，用D作为hash函数无法满足该条件，用C产生碰撞可以用链接法解决冲突，感谢@zdw12242的纠正
2.下面排序算法中，初始数据集的排列顺序对算法的性能无影响的是：
A: 堆排序 B：插入排序
C: 冒泡排序 D:快速排序
选择A，解释：(1)堆排序的时间复杂度一直都是O(nlogn),不稳定(2)插入排序在初始有序情况下，时间复杂度为O(n),平均时间复杂度为O(n^2)，稳定排序(3)冒泡排序在初始有序的情况下，增加交换标示flag可将时间复杂度降到O(n),稳定排序(4)快速排序在初始有序的情况下，可能会退化到O(n^2)，不稳定排序
3. 下面说法错误的是：
A: CISC计算机比RISC计算机指令多
B: 在指令格式中，采用扩展操作码设计方案的目的是为了保持指令字长不变而增加寻址空间
C:增加流水线段数理论上可以提高CPU频率
D:冯诺依曼体系结构的主要特征是存储程序的工作方式
选择B，解释(1)CISC复杂指令集，RISC精简指令集，从名字上就可以得出A正确(2)保持指令字长度不变而增加指令操作的数量(3)看样子都觉得正确(4)冯诺依曼体系结构的主要特点：存储程序控制(要求计算机完成的功能，必须事先编制好相应的程序，并输入到存储器中，计算机的工作过程是运行程序的过程);程序由指令构成，指令和数据都用二进制表示;指令由操作码和地址码构成;机器以cpu为中心
4. 不属于冯诺依曼体系结构必要组成部分是：
A:CPU B: Cache C:RAM D:ROM
B，解释：冯诺依曼体系结构必要组成部分：运算器、控制器、存储器、输入设备、输出设备，Cache属于缓存了
5. 一个栈的入栈序列式ABCDE则不可能的.出栈序列是:
A:DECBA B:DCEBA C:ECDBA D:ABCDE
C，不解释
.你认为可以完成编写一个C语言编译器的语言是：
A：汇编 B:C语言 C:VB D:以上全可以
D,解释：其实你学好编译原理用什么语言都能写出来
7. 关于C++/JAVA类中的static成员和对象成员的说法正确的是：
A：static成员变量在对象构造时候生成
B: static成员函数在对象成员函数中无法调用
C: 虚成员函数不可能是static成员函数
D: static成员函数不能访问static成员变量
C,解释：虽然博主主要以php和c为主，php也能面向对象，我来简单说明一下。(1)static成员变量可以直接定义，例如public statci $a = 10; 所以A错(2)在对象成员函数里可以通过类名：：static函数名的方法调用，我的项目中超过静态方法(4)同样道理，类名：：static成员变量名，这也是访问static成员变量唯一的方法(3)是正确的，虽然我都不知道什么是虚函数，排除法可以完成
9：某进程在运行过程中需要等待从磁盘上读入数据，此时进程的状态将：
A: 从就绪变为运行 B:从运行变为就绪
C: 从运行变为阻塞 D:从阻塞变为就绪
C，解释：I/O事件让进程从running->waitting
10：下面算法的时间复杂度为：
Int f(unsigned int n) { If(n==0||n==1) Return 1; Else Return n*f(n-1); }A: O(1) B:O(n) C:O(N*N) D:O(n!)
B，解释：没啥好解释的
11: n从1开始，每个操作可以选择对n加1或者对n加倍。若想获得整数2013，最少需要多少个操作。
A:18 B:24 C:21 D;不可能
A，解释：数学方法->从 2013 倒推， 奇数 减一，偶数 除2，编程实现->是一个明显的bfs题目，编程实现为18,共享一下自己的bfs代码：
#include <stdio.h> #include <stdlib.h> #define FINAL 2013 #define MAX 25 typedef struct num { int d, time; } num; typedef struct queue { int front, rear, count; num data[10000000]; } queue; void enQueue(queue *q, num d) { q->data[q->rear ++] = d; q->count ++; } num deQueue(queue *q) { num res; res = q->data[q->front ++]; q->count --; return res; } int main(void) { int flag = 0; num bt, one, two, s; bt.d = 2; = 1; queue *q = (queue *)malloc(sizeof(queue)); q->front = q->rear = q->count = 0; enQueue(q, bt); while (q->count > 0) { s = deQueue(q); if (s.d == FINAL) { flag = 1; printf("%dn", ); break; } one.d = s.d + 1; = + 1; if (one.d <= FINAL && <= MAX) { enQueue(q, one); } two.d = s.d * 2; = + 1; if (two.d <= FINAL && <= MAX) { enQueue(q, two); } printf("%dn", q->count); } if (flag == 0) printf("不可能!n"); return 0; }12：对于一个具有n个顶点的无向图，若采用邻接表数据结构表示，则存放表头节点的数组大小为：
A: n B: n+1 C: n-1 D:n+边数
A，解释：感觉没啥好解释的，n个顶点数组大小应该就是n吧，如果非要从下标从1开始，那就是n+1，蛋疼的题目，话说在ACM上写bfs，dfs，最短路径全是用邻接矩阵，就谁会用邻接表这么蛋疼的设计，又不是hash
13.考虑一个特殊的hash函数h，能将任一字符串hash成一个整数k，其概率p(k) = 2^(-k),k = 1,2,3,4,....对于一个未知大小的字符串集合S中的每一个元素取hash值所组成的集合为h(S).若h(s)中最大元素max h(s) =10,那么s的大小期望是
A：1024 B：512 C：5 D:10
我读不懂题啊有没有，我想选c
14.如下函数，在32bit系统foo(2^31-3)的值是：
Int foo(int x) { Return x&-x; }A： 0 B: 1 C:2 D:4
C,解释：我只想说注意运算符优先级，注意^是异或
15.对于顺序存储的线性数组，访问节点和增加节点删除节点的时间复杂度为：
A: O(n),O(n) B:O(n),O(1) C:O(1),O(n) D:O(n),O(n)
C，解释：给定下标，访问为O(1)，增加和删除节点涉及到移动操作为O(n)
16:在32为系统环境，编译选项为4字节对齐，那么sizeof(A)和sizeof(B)是：
Struct A
{
int a;
short b;
int c;
char d;
};
Struct B
{
int a;
short b;
char c;
int d;
};
A: 16,16 B:13,12 C:16,12 D:11,16
C，解释：字节对齐包含了每个变量自身对齐和复杂类型整体对齐。pragma pack参考链接：_1988/article/details/11834881
对于A：
int a自身对齐是4,pragma pack指定对齐也是4,因此其有效对齐为4,起始地址0x0000满足0x0000 % 4 == 0
short b自身对齐是2,指定对齐是4,因此有效对齐为其最小值2,起始地址0x0004满足0x0004 % 2 == 0
int c自身对齐是4,pragma pack指定对齐也是4,因此其有效对齐为4,起始地址0x0006不满足0x0006 % 4 == 0,因此需要填充空字节，起始地址为0x0008
char d自身对齐是1,指定对齐是4,因此有效对齐为其最小值1,起始地址0x000C满足0x000C % 1 == 0
结构体还需要整体对齐，也就是结构体成员最大有效对齐的倍数，0x000D不满足 % 4 ==0, 需要需要补充3个字节，总字节数为16
对于B：
int a自身对齐是4,pragma pack指定对齐也是4,因此其有效对齐为4,起始地址0x0000满足0x0000 % 4 == 0
short b自身对齐是2,指定对齐是4,因此有效对齐为其最小值2,起始地址0x0004满足0x0004 % 2 == 0
char d自身对齐是1,指定对齐是4,因此有效对齐为其最小值1,起始地址0x0006满足0x000C % 1 == 0
int c自身对齐是4,pragma pack指定对齐也是4,因此其有效对齐为4,起始地址0x0007不满足 % 4 ==0,需要补充一个空字节，起始地址为0x0008
结构体需要整体对齐，结构体整体有效对齐是4,0x000C % 4 == 0,因此总字节为12
