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章,不是一般的复杂,我表示没看懂。。。
分享到:
相关推荐
2011腾讯北京暑期实习非技术类笔试笔经
2014年3月阿里巴巴暑期实习笔试题目,精彩奉献,开发类的题目除附加题目外全一样,该文档中附加题目是系统工程师的题目。
腾讯暑期实习算法/后台/数据分析网申真题腾讯暑期实习算法/后台/数据分析网申真题腾讯暑期实习算法/后台/数据分析网申真题
米哈游笔试题目2022 米哈游暑期实习笔试题2022 米哈游暑期实习笔试题2022 米哈游暑期实习笔试题2022 米哈游暑期实习笔试题2022 米哈游暑期实习笔试题2022 米哈游暑期实习笔试题2022 米哈游暑期实习笔试题2022 米哈游...
2013微软暑期实习笔试题(英文版),仅供参考
百度笔试题目,很有用,经典的题目,是本人亲身体验,亲身经历过。
2011百度暑期实习生招聘笔试题-web前端开发,有部分答案
找工作非常有用的资源,有公共部分、JAVA、测试、C/C++、系统部分
2019腾讯产品暑期实习提前批笔试题(1).pdf
微软暑期实习笔试题.docx
阿里巴巴2017暑期实习生笔试题(1).pdf
腾讯_2012暑期实习笔试 包含了腾讯笔试题 欢迎下载
中国移动2013暑期实习笔试行测题(照片)
这是我大一暑假写的一个网上购书系统用到了C 和c++来写的 ,程序代码大约1200行,资源内附源代码
清晰版,微软2013年暑期实习笔试题,笔试题的覆盖面还是很挺广泛的,操作系统进程、线程概念,C++语法,重中之重算法
文档中 有09年和10年百度实习笔试题 请需要的同学去看看
百度2012实习生校园招聘机器学习数据挖掘笔试试题,花了很多时间才找到的
微软2013.4.6暑期实习笔试题.docx
2020届腾讯暑期实习交互设计笔试.pdf
2019腾讯产品暑期实习提前批笔试题.pdf