支付宝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_t	fp;
	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;
	else
		return 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)
{
	int		tmp;

	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)
{
	int		i, 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)
{
	int		p, 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章，不是一般的复杂，我表示没看懂。。。