支付宝2011暑期实习笔试(C/C++类)
?
1 二叉树的前序遍历是ABC，后续遍历是CBA，其中序遍历是
关于二叉树的三种遍历：
前序遍历+中序遍历 可以确定二叉树的结构
后序遍历+中序遍历 可以确定二叉树的结构
前序遍历+后序遍历无法确定二叉树的结构
?
2?
?
char *stra = "hello"char strb[] = "world"char strc[10] = "world"a = strlen(stra);b = strlen(strb);c = sizeof(stra);d = sizeof(strb);e = sizeof(strc);?
求a,b,c,d的值
a = b = 5
c = 4
d = 6
e = 10
strlen不解释，关于sizeof：
The sizeof keyword gives the amount of storage, in bytes, associated with a variable or a?
type (including aggregate types). This keyword returns a value of type size_t.
sizeof可以计算type的大小，也可以计算variable对应的type大小。
stra的类型为char *，指针占4个字节大小
加上末尾的\0，strb的类型为char[6]，占6个字节大小
strb的类型为char[10]，占10个字节的大小
?
3?张三说；李四撒谎。李四说；王五撒谎。王五说；他们两个都撒谎。问，哪个说的真话？
张三说的话用A表示，李四说的话用B表示，王五说的话用C表示，A、B、C的取值为1和0，
0表示假话，1表示说的是真话，根据题意，必须满足：
if A = 1 ?then B = 0
if A = 0 ?then B = 1
if B = 1 ?then C = 0
if B = 0 ?then C = 1
if C = 1 ?then ?A = 0 and B = 0
if C = 0 ?then ?A = 1 or ? ?B = 1
然后枚举A，B，C的所有值，判断哪些与上面的条件矛盾，最后得出
当A = 0, B = 1, C = 0时，与条件不矛盾。所以
李四说的是真话
?
?
4 1-100个数排好序了，使用二分查找找一个数，最多要比较多少次
?
int bsearch(int *A, int e, int s, int t){int m;while (s <= t) {m = (s+t)/2;printf("%d %d\n", s, t);if (A[m] == e) return m;if (A[m] > e) t = m-1;else s = m+1;}return -1;}?1-100 ?比较a[50]和e
1-49 ? 比较a[25]和e
1-24 ? 比较a[12]和e
1-11 ? 比较a[6]和e
1-5 ? ?比较a[3]和e
1-2 ? ?比较a[1]和e
2-2 ? ?比较a[2]和e
总共7次比较，事实上二分查找最多的比较次数为|log2(n)|+1
另外，二分查找到s和t位置相邻的时候，总是先比较a[s]和e，再比较a[t]和e
?
5 广义表
x,x,(x,x),x的广义表表头是什么？
?
6 中缀表达式转后缀表达式
求a+b*c-d+e的后缀表达式，看书去，不解释
?
7 数据库SQL语句，group by和 having count distinct
?
8 哪个select语句不会用到索引
A select * from employer where id = 7744;
B select * from employer where id = '7744';
C select * from employer where id = to_char(7744);
D select * from employer where to_char(id) = '7744';
选D,如果查询时某个字段被函数包裹了，一般的索引是不会用到的，
除非对这个字段创建函数索引：
create index id_to_char_index on employer(to_char(id))
才能用索引
?
9 要求某个字段可以为空，但不能出现重复的值，使用的约束是：
UNIQUE
?
10 对12345排序，哪种方法最快?
当然是插入排序
?
11 在一棵二叉查找树中搜索一个数，不会出现的搜索过程是
?
12 石油和塑料推理题
?
13 扑克推理题
?
14 支付宝早上9：00上班，下午18：00下班，中午12：00到13：00休息，
问上班时间，时钟和分钟的指针会重合多少次？包括12:00和13:00
?
15 下列哪种说法是错误的？
A.指向指针的指针：int **p
B.指向10个整树的指针 int *a[10]
C.参数为int，返回值为int的函数指针：int (*func)(int);
D.参数为int，返回值为int的10个函数指针：int (*func[10])(int);
考察如何声明函数指针和函数指针数组，联想：如何使用typedef定义函数指针的类型
?
typedef int (*func_t)(int);int f(int a){return a;}int main(){int (*func)(int);int (*funcs[10])(int);func_tfp;int i;func = f;fp = f;for (i = 0; i < 10; i++) {funcs[i] = f;}return 0;}??
?
1 C++的继承和多态
?
2 p = new int[30][20],p应如何声明
A. int *p;
B. int **p;
C. int *p[20];
D. int (*p)[20];
选D，这题蒙对了，c++的类型声明比c语言要求更严格
?
3?
?
typedef union {int n;char p[sizeof(int)];} union_t;union_t ut;memset(&ut,0, sizeof(ut));ut.p[0] = 13;printf("%d\n", ut.n);?输出结果是什么？
结果是13，考察大端法和小端法，一般来说，大部分用户的操作系统（如windows, FreeBsd,Linux）是Little Endian
的。少部分，如MAC OS ,是Big Endian 的。
?
所谓MSB (Most Significant Byte)就是,一个数字中,最重要的那位,
比如,12004,中文读作,一万两千零四,那最高位的1,就表示了一万,此处就称作MSB,最有意义的位.
而LSB (Least Significant Byte)与MSB相反，个位数4就可以称为LSB，
在草稿纸上演示的时候，我们习惯左边写数的MSB，右边写数的LSB。
?
使用Little Endian方式存储数据时,数据的MSB存放在高地址，LSB存放在低地址
比如 0x11223344 ，它在内存中存储为
44 33 22 11?
低地址-->高地址
使用Big Endian方式存储数据时,数据的MSB存放在低地址，LSB存放在高地址
比如 0x11223344 ，它在内存中存储为
11 22 33 44
低地址-->高地址
?
值得注意的是，大端法和小端法讨论的都是字节与字节之间的顺序，至于一个字节内的8个比特，无论大端法还是
小端法，顺序都是一样的，即右边存储低位，左边存储高位。再看一个例子:
?
已知内存中从低地址到高地址存储的4个字节依次是：
11 22 33 44
求这个数是多少？
关键是找出哪头是MSB，哪头是LSB
?
如果该机器是Little Endian，
则低地址存放的是LSB，所以11是LSB，高地址是MSB，所以44是MSB
所以这个数等于
0x44332211
?
如果该机器是Big endian，
则低地址存放的是MSB，所以11是MSB，高地址是LSB，所以44是LSB
0x11223344
?
支付宝这个笔试题的意思是，已知内存中从低地址到高地址存储的4个字节是
0D 00 00 00
使用小端法表示，这个数等于0x0000000D，即13。
?
再引申一个问题，试写一个函数判断机器是否为Big Endian。
思想是取一个short数0x1122的第1个字节，若这个字节等于0x11，则是大端法
?
int is_big_endian(){unsigned short test = 0x1122;if(*( (unsigned char*) &test ) == 0x11)return 1;elsereturn 0;}??
?
?
4 关于c++的容器、顺序表、multimap，哪种说法是正确的？
直接蒙，选项不记得了
?
5 关于c++的异常，哪种说法是不正确的？
直接蒙，选项不记得
?
1 给出了一段代码，具体不记得了，大意是父进程调用fork创建
子进程，然后子进程无限休眠，父进程调用waitpid等待子进程退出，一旦
退出，调用fork继续创建子进程，如此反复。
问：程序运行的时候，使用ps命令加grep命令查看当前有多少个进程在运行。
我只记得fork后，子进程返回0，父进程返回子进程的id，这个id大于0。
本来打算留到最后再做这题，结果最后一题程序写得太认真，时间不够了。。。
这题白板，以后笔试发的红牛不要喝了，可以节省一点时间，另外带个手表，
既可以看时间，还可以用来辅助做第14题。
?
2 1000万条学生成绩，找出排名第200万的学生的成绩，用C++实现，分析算法最坏和最好情况下的复杂度
这题告诉我们，算法导论还是要看地。
使用快速排序的partition过程，递归的搜索，代码如下：
?
void swap(int *p, int *q){inttmp;tmp = *p;*p = *q;*q = tmp;}/* 把a[t]作为参考，将数组分成三部分: 小于等于a[t]， * a[t]以及大于a[t]，分割完毕后，a[t]所在的下标即是a[t]的顺序 */int partition(int *a, int s, int t){inti, j;/* i用来遍历a[s]...a[t-1], j指向大于x部分的第一个元素 */for (i = j = s; i < t; i++) {if (a[i] < a[t]) {swap(a+i, a+j);j++;}}swap(a+j, a+t);return j;}/* 选择数组中第i大的元素并返回 */int quick_select(int *a, int s, int t, int i){intp, m;if (s == t) return a[t];p = partition(a, s, t);/* 用a[t]分割数组 */m = p - s + 1;/* m是a[t]在小组内的排名 */if (m == i) return a[p];if (m > i) {return quick_select(a, s, p-1, i);}return quick_select(a, p+1, t, i-m);}?调用：
select(a, 1, 10000000, 2000000);
复杂度分析：
最好情况：O(1)
最坏情况：O(n^2)
平均情况：O(n)
证明看算法导论第9章，不是一般的复杂，我表示没看懂。。。