网易 TTT 计划 2015 年春季笔试题目（回顾版本）不是很记得有些题了

[wind3110991]

PS：考试地点在广州，我是面试实习生
全试卷分为4个大题，考试时间2个小时。我去的时候一堆北大和中大的。。我这个华工人倍感压力啊。。。
不过这份题出的真心有水平。。我真心不是偷题的，我认认真真把会做的做了。。才有印象回来写这个回顾的。。也当是查缺补漏了。

一、选择题（顺序不计）
1.sizeof计算字节是在什么时候？
答：编译时

2.请问下列哪本书最厚（这题我也是醉了）
A.c++ prime
B.Head First
C.Effective c++
D.windows内核编程
答：应该是D吧 ＝ ＝其他c++几本都挺厚

3.Linux哪个命令是。。。记不得题目了，反正是这几个命令：
cat 显示整个文件
more 以百分比形式查看文件（会分页）
less 和more差不多
head 从文件头开始查看
tail 尾开始查看文件

4.一个盒子里有5个颜色的小球，小球视为无限多，每个人一次可以从里面拿出2个来，那么问：可以最多多少人来拿小球，可以保证有两个人拿出来的球中有相同颜色？
答：应该是6吧，考虑前五个人拿出的每一对都是同样颜色（例：A：红红 B：黄黄 C：绿绿 D：白白 E：蓝蓝 那么第六个人，不管拿到什么颜色都会和其中一个人有同样颜色）

5.死锁是如何产生的？
答：是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。
（等待～关键词）

6.我有20块钱，如果一瓶可乐1块（好便宜＝ ＝），两个空瓶子可以换1瓶新可乐，那么请问你最多可以喝到多少瓶？
答：20——》10——》5——》2 ——》1（这些是兑换的过程）38瓶
然后5——》2时手头上有一个多的空瓶子，加上最后喝的一瓶可以换多一瓶 ＋1
所以是最多39瓶

7.栈和队列有什么共同点？
答：只允许在端点处删除或插入的顺序表。
堆和队列都是先进先出，栈是先进后出。
还有3题不太记得了。。不过可以能看出，这些知识点考察的基本都是最基础的知识点

二、填空题

1.冒泡排序法的时间复杂度

答：O（n^2）

2.如何用程序判断一个float类型变量x是不是为0
答：这题当时没想到，好像直接用了个if去判断＝ ＝，后来觉得自己好sb啊。
其实正确的思路来想－－－这题考察的是c++的位运算。
float，8字节的话，32bit，对于x如果直接逻辑与0来运算的话，x被约等于了0，那么有可能x其实是一个无限接近0的数字(如0.0000000000000123)
所以正确的思路应该是：位运算中的掩码
unsigned c;
unsigned bitmask=1<<32;
for(c=1;c<=32;c++)
{
if((x&bitmask?1:0)==1) std::cout<<"x is not 0!"
x>>=1; //x右移1位
}

3.在执行main函数之前，编译器会运行什么代码？（这个不懂，求教大神 ＝ ＝55555）
答：
（1）.设置栈指针
（2）.初始化static静态和global全局变量，即data段的内容
（3）.将未初始化部分的全局变量赋初值
（4）.运行全局构造器，估计是C++中构造函数之类的吧
（5）.将main函数的参数，argc，argv等传递给main函数，然后才真正运行main函数
（网上google下，有人说是start函数）

4.结构struct定义时默认其成员是__,类class定义时默认成员为__.
默认的访问权限不同。struct默认为public ，class默认为private；
默认的继承权限不同。struct的继承默认为public继承，class的继承默认为private继承。

5.TCP在请求连接时进行次握手，断开时是次握手。
答：3 ，2

6.下列IP地址的书写格式正确吗？为什么？
（1）162.21.045.22 对
（2）142.23.274.13 错，子网号不可能大于255
（3）168.51.233.25.55 错，主机号之后没东西了，ip是32 位的只有4段
（4）10001111.41.235.12 错，ip地址要不纯用2进制，要不纯用十进制，可以用ping来检测该ip无效

三、简答题

1.简述事务的四个特性
事务是控制并发的单位，用户定义操作的一个序列。
A:原子性(Atomicity)
事务是数据库的逻辑工作单位，事务中包括的诸操作要么全做，要么全不做。
B:一致性(Consistency)
事务执行的结果必须是使数据库从一个一致性状态变到另一个一致性状态。一致性与原子性是密切相关的。
C:隔离性(Isolation)
一个事务的执行不能被其他事务干扰。
D:持续性/永久性(Durability)
一个事务一旦提交，它对数据库中数据的改变就应该是永久性的。

2.DDos是什么？
分布式拒绝服务(DDoS:Distributed Denial of Service)攻击指借助于客户/服务器技术，将多个计算机联合起来作为攻击平台，对一个或多个目标发动DDoS攻击，从而成倍地提高拒绝服务攻击的威力。

3.用SQL语句编程，有A，B，C三个列，如果A比B大，那么输出A，如果B比C大输出B（不太记得了，也不知道这个题目是什么意思。。。）

4.请简述浅拷贝与深拷贝，c++中的拷贝构造函数是什么拷贝？
在有指针的情况下，浅拷贝只是增加了一个指针指向已经存在的内存，而深拷贝就是增加一个指针并且申请一个新的内存，使这个增加的指针指向这个新的内存，采用深拷贝的情况下，释放内存的时候就不会出现在浅拷贝时重复释放同一内存的错误！
当然是深拷贝。

5.当你在浏览器输入cc.163.com ,浏览器会打开网易cc语音的主页，请问这个过程计算机做了些什么？
（这个就是网络数据传输工作原理吧。。我扯了一堆分层、TCP三次握手之类的东西）

6.Linux哪个命令是查看当前进程
ps 查看进程（我写的是aux，应该也对吧。。。）
最常用的方法是ps aux,然后再通过管道使用grep命令过滤查找特定的进程,然后再对特定的进程进行操作。
crontab crond是linux下用来周期性的执行某种任务或等待处理某些事件的一个守护进程

四、编程题（重头戏）
1、学校有个教务系统，里面有三个表
Student(sno,sname,sex,grade,class)
Teacher(tno,tcourse,tname)
Course(cno,cname,ctime)
用SQL语句作答
（1）找出选了“计算机编程”课程的同学名字和学号。
（2）找出和“谭维维”同学有关的所有课程
（3）不记得了＝ ＝ sorry

2、编写一个简单函数add(a,b) ,目的为了计算a和b的和。
条件：已知a和b都为正整数，不考虑溢出，若a的百位数字为0，那么函数直接输出0；反之则计算两个数的和；例如（a＝1001，b＝31，那么直接输出0； a＝123，b＝2，输出125）
答：我当时想的比较复杂。。。我觉得这题绝对没那么简单。。。如果正常思路肯定是直接对a不断除，不断余。。。然后得到百位，判断后计算
但是我觉得，考虑到如果a是一个特别大的数字，那么对a做那么多次运算。。是不是会效率好低。。。比如a是214214212152152131231231231231231231231231231255129595717239139213218321737，你难道要从头到尾算出百位？
我直接把a赋值给a1，然后把a1转化为字符串。。。存到vector<char> v里，然后用v.size()取长度，然后直接取v[v.size()-3]就是百位了
如果等于字符'0' ,那么直接输出0（不知道这个想法对不对。。。）

3.写出堆排序的伪代码（如果可以写代码，可以用自己喜欢的语言）PS：这份卷子可以用c＋＋、java、c或者python写
这个当时就跪了＝ ＝数据结构没复习完。。。

c语言版：
[cpp] view plaincopy

!/usr/bin/envpython

--coding:utf-8--

def heapsort(lst):

for startinrange((len(lst)-2)/2,-1,-1):

sift_down(lst,start,len(lst)-1)

for endinrange(len(lst)-1,0,-1):

lst[0],lst[end]=lst[end],lst[0]

sift_down(lst,0,end-1)

return lst

def sift_down(lst,start,end):

root=start

while True:

child=2*root+1

if child>end:

break

if child+1<=end and lst[child]<lst[child+1]:

child+=1

if lst[root]<lst[child]:

lst[root],lst[child]=lst[child],lst[root]

root=child

else:

break

def main():

l=[9,2,1,7,6,8,5,3,4]

heap_sort(l)

ifname=="main_":

main()

Python版：
[python] view plaincopy

!/usr/bin/envpython

--coding:utf-8--

def heapsort(lst):

for startinrange((len(lst)-2)/2,-1,-1):

sift_down(lst,start,len(lst)-1)

for endinrange(len(lst)-1,0,-1):

lst[0],lst[end]=lst[end],lst[0]

sift_down(lst,0,end-1)

return lst

def sift_down(lst,start,end):

root=start

while True:

child=2*root+1

if child>end:

break

if child+1<=end and lst[child]<lst[child+1]:

child+=1

if lst[root]<lst[child]:

lst[root],lst[child]=lst[child],lst[root]

root=child

else:

break

def main():

l=[9,2,1,7,6,8,5,3,4]

heap_sort(l)

ifname=="main_":

main()

4、（压轴）滑雪问题（一堆废话。。。。balabala。。。）
大概就是说，例如给你一个二维数组，ary[R][C] ，比如 R＝5，C＝5，里面的元素是从1到R*C的，也就是1到25都有，而且只会出现一次。
eg：
INPUT: R=5,C=5 ,以及二维数组每一个元素（任意导入的，可能是乱序，但是最大数肯定是R*C,最小是1），如下：
1 4 5 6 10
2 3 7 8 13
15 25 20 23 24
21 9 11 14 12
19 18 17 16 22
OUTPUT:（输出该数组的最大滑雪落差）
25
编写程序，输入滑雪的“地图”，给出该地图的最大滑雪落差。

分析：
其实，你可以把上面这个例子的数组这个样子看作是从上到下俯视海拔的图，每一个数视为一个点，数值即是这个点的高度，比如20这个点，上有7，下有11，左是25，右边是23
如果你要“从20这么高滑雪冲下去”那么肯定要找个比20要低的点吧，！！！！题目规定，你只能从一个点滑倒上下左右四个点的其中一个。例如20，你只能选择滑到7或者11，那么，例如你滑到了7那么“高”，那么你可以继续“往下滑”，就是滑倒3，3再到2，2再到1；那么最大滑雪落差就是20-1＋1=19＋1=20 （因为你在1后要回到地面，
默认＋1）
本例子的25就是这样来的：25——》15———》2——》1
（注意：不一定是从最大数值那个高度滑下来可以到达最大落差，因为你可能到了某一个点就没有办法继续“往下”了）
例如：这是个8行 8列的二维数组，如果你选了最大值64，那么你会发现，64滑倒邻点的高度差明显不是最大的。最大的高度差是63-－》7-－》1

。。。。。。。
45 52 3 4 22 8 51 13
64 48 56 1 12 9 41 19
43 59 63 7 11 15 2 20
。。。。。。。
答：（没做，只写了思路，求教大神！）
总结：这份试卷主要考察了操作系统，c++，SQl，Linux，计算机等基础知识，不能说难。。。但是考察的很全面，就算不进面试。。也算学到东西了！

[wind3110991]

忘记补充了，简答题还有一题：如何编程判断CPU是大端还是小端？

Big-endian是一种大值的一端（序列中更典型值）存在前面（在最小的存储地址）的顺序。Little-endian是一种小值的一端（序列中较不典型的值）存储在前的顺序。比如，在Big-endian的电脑中，需要两个字节把十六位数4F52当作4F52存在存储器中（如果4F存在存储地址1000中，比如说，52将存在1001中）。在little-endian系统里，将被存为524F（52存在存储地址1000中，比如说，4F将存在1001中）。

[banri]

话说瓶子问题那个，小学做过类似的
最后老师貌似是说，和别人借个瓶子，换了喝完再还掉啥的

我印象特深！！！

[sina012345]

难得楼主记得这么详细，我做完发现大端小端刚好记反了，最后一题少写了些大小，堆排没写对。还有其他很多错误。。。目测是跪了

[gracece]

去年考过 TTT，只记得被虐了，完全忘记考了什么。我觉得考完还能记得题目的人都是神一样的存在。

[monnand]

5.死锁是如何产生的？

死锁的条件有四个：
- Mutual Exclusion
- Hold and Wait
- No Preemption
- Circular Wait:

[wind3110991]

@banri 嗯嗯，这个题其实不难，穷举下就好，n个的话，做个递归公式就好

[wind3110991]

@gracece 我挺多都忘了，就当考完回来回顾知识点吧。。。感觉本科念的东西真的好不够。。

[wind3110991]

@sina012345 话说听说300多人只要30个，然后进个培训班，培训后再做一个项目，又刷20多个留下6、7个。。。残忍啊

[sina012345]

@wind3110991 这确实是凶残，，而且要求实习6个月至少得到10月份，基本错过大公司的校招了。那时候刷人岂不是坑爹

[tpwow]

中大人飘过。昨天也刚考完，在B201

[illuz]

TCP在请求连接时进行 3 次握手，断开时是 2 次握手？
不是 4 次吗？
兄弟我书读得少，不要骗我，我还要拿你这个好好复习一下呢。

[logeable]

默认拷贝构造函数是浅拷贝

[chaucerling]

没复习去果然是要跪

[jamesxu]

这题给跪了，为什么要“对a不断除，不断余。。。然后得到百位，判断后计算”
如果 a 的百位数字为零，那么 (a / 100) % 10 == 0 啊，你想太多了

[wind3110991]

@illuz 我错了＝ ＝是4次，太晚写脑子出毛病了

[wind3110991]

我昨晚太晚回忆了。。技术有限加上脑子有点乱，更正下：
TCP断开4次挥手
c＋＋默认的拷贝构造函数是浅拷贝
欢迎各位大神来回复，共同学习！

[wind3110991]

@jamesxu 嗯嗯。。。但是我觉得我的思路也没错吧。。

[wind3110991]

有没有大神做出最后一题了，求源码

[GtDzx]

最后一题滑雪是北大各种编程课程上经常用的DP作业/例题。
http://cxsjsxmooc.openjudge.cn/2014hw13/D/
搜一下"openjudge 滑雪"能找到不少代码

[Dwayne]

最后一题出处是上海市NOI’2002选拔赛
简单的动态规划问题, 在VJ上随便找了份代码可以在http://poj.org/problem?id=1088测试
#include <cstdio>
int n,m,a[110][110] = {{0}},f[110][110] = {{0}},d[4][2] = {{1,0},{-1,0},{0,1},{0,-1}},ans;
int max(int a,int b){
return a > b ? a : b;
}
int g(int i,int j){
if (i < 1 || i > n || j < 1 || j > m) return 0;
if (f[i][j]) return f[i][j];
int k = 1,x,y;
for (int r = 0;r < 4;r++){
x = i + d[r][0];
y = j + d[r][1];
if (a[i][j] > a[x][y]) k = max(k,g(x,y) + 1);
}
f[i][j] = k;return k;
}
int main(){
scanf("%d%d",&n,&m);
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
scanf("%d",&a[i][j]);
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
f[i][j] = g(i,j);
ans = 0;
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
ans = max(ans,f[i][j]);
printf("%d",ans);
}

[bcxx]

@wind3110991 大小端可以通过 char 来强制转换 int / float 来分辨出来。 CSAPP 里面有。

[xiaohanqing]

mysql ABC三列的那个题，是不是要考case？

[wind3110991]

@xiaohanqing 不清楚。。。记不得题目了，反正sql语句要重点复习啊。。

[XVXVXXX]

@banri 碉堡了。。。。hah

[liubiantao]

就冲你的记忆能力也必须要你啊，反正我考完试什么都不记得

[claylin]

非985 211的只能观望你们这些 名校才子了

[nideyangzi1989]

大小端可以用union判断
union {
int i;
char c;
}test;

test.i = 1;
printf("%s\n", test.c == 1 ? "little_endian" : "big_endian");

[hustlike]

为什么我没听到过这个TTT计划。。网易实习招聘不是还没开始吗。。

[wind3110991]

补充下：
2.如何用程序判断一个float类型变量x是不是为0
这题想了下，直接用一个if其实就搞定了。。

if(x>0.000001&&x<-0.000001)

[aaronzhou67]

@wind3110991 原来做过还写了solution…小白勿喷…
http://aaron67.cc/blog/acm校赛2013-滑雪/

[wind3110991]

@aaronzhou67 谢谢！有空我学习下～

[HayesPan]

我也参加了今年的TTT笔试，现在在等hr面了，楼主是研究生么

[HayesPan]

@xiaohanqing 是的，用case when ... then ... else ...

[wind3110991]

@HayesPan 本科生－ －表示被刷了