面试ack

A. 寻求文思和华为关于软件工程师的面试题目

华为从事通信网络技术与产品的研究、开发、生产与销售，是中国电信市场的主要供应商之一，并已成功进入全球电信市场。每年华为都要在各大高校招聘大批的应界生，特别是华中科技大学。公司网址是：http://www.huawei.com
下面据说是华为公司的笔试题，其实我想它一次笔试不可能出这么多题，也许是多年笔试题的合集，或者也包括了其他公司的笔试内容。最近国际商用工程集团（http://www.ibegroup.com/）的网管告诉我这是他们的题目，是网上以讹传讹的说成是华为的题目了，我想应该是这样的，毕竟题目中赫然出现了他们公司的网址呢（见题2），希望大家转贴的时候也能写上这段声明。
另外我发现白云黄鹤有人不声不响的贴出我做的答案，还没有声明出处，俺很严肃的告诉他，俺很生气angry，后果很严重。
个人答案，仅供参考。呵呵，不过保证绝大多数答案的准确性。
1.写出判断ABCD四个表达式的是否正确, 若正确, 写出经过表达式中 a的值(3分)
int a = 4;
(A)a += (a++); (B) a += (++a) ;(C) (a++) += a;(D) (++a) += (a++);
a = ?
答：C错误，左侧不是一个有效变量，不能赋值，可改为(++a) += a;
改后答案依次为9,10,10,11

2.某32位系统下, C++程序，请计算sizeof 的值(5分).
char str[] = “www.ibegroup.com”
char *p = str ;
int n = 10;
请计算
sizeof (str ) = ？（1）
sizeof ( p ) = ？（2）
sizeof ( n ) = ？（3）
void Foo ( char str[100]){
请计算
sizeof( str ) = ？（4）
}
void *p = malloc( 100 );
请计算
sizeof ( p ) = ？（5）
答：（1）17 （2）4 （3） 4 （4）4 （5）4

3. 回答下面的问题. (4分)
(1).头文件中的 ifndef/define/endif 干什么用？预处理
答：防止头文件被重复引用
(2). #include 和 #include “filename.h” 有什么区别？
答：前者用来包含开发环境提供的库头文件，后者用来包含自己编写的头文件。
(3).在C++ 程序中调用被 C 编译器编译后的函数，为什么要加 extern “C”声明？
答：函数和变量被C++编译后在符号库中的名字与C语言的不同，被extern "C"修饰的变量和函数是按照C语言方式编译和连接的。由于编译后的名字不同，C++程序不能直接调用C 函数。C++提供了一个C 连接交换指定符号extern“C”来解决这个问题。
(4). switch()中不允许的数据类型是?
答：实型

4. 回答下面的问题(6分)
(1).

Void GetMemory(char **p, int num){
*p = (char *)malloc(num);
}
void Test(void){
char *str = NULL;
GetMemory(&str, 100);
strcpy(str, "hello");
printf(str);
}
请问运行Test 函数会有什么样的结果？
答：输出“hello”
(2).

void Test(void){
char *str = (char *) malloc(100);
strcpy(str, “hello”);
free(str);
if(str != NULL){
strcpy(str, “world”);
printf(str);
}
}
请问运行Test 函数会有什么样的结果？
答：输出“world”，因为free(str)后并未改变str所指的内存内容。
(3).

char *GetMemory(void){
char p[] = "hello world";
return p;
}
void Test(void){
char *str = NULL;
str = GetMemory();
printf(str);
}
请问运行Test 函数会有什么样的结果？
答：无效的指针，输出不确定

5. 编写strcat函数(6分)
已知strcat函数的原型是char *strcat (char *strDest, const char *strSrc);
其中strDest 是目的字符串，strSrc 是源字符串。
（1）不调用C++/C 的字符串库函数，请编写函数 strcat
答：
VC源码：

char * __cdecl strcat (char * dst, const char * src)
{
char * cp = dst;
while( *cp )
cp++; /* find end of dst */
while( *cp++ = *src++ ) ; /* Copy src to end of dst */
return( dst ); /* return dst */
}
（2）strcat能把strSrc 的内容连接到strDest，为什么还要char * 类型的返回值？
答：方便赋值给其他变量

6.MFC中CString是类型安全类么？
答：不是，其它数据类型转换到CString可以使用CString的成员函数Format来转换

7.C++中为什么用模板类。
答：(1)可用来创建动态增长和减小的数据结构
（2）它是类型无关的，因此具有很高的可复用性。
（3）它在编译时而不是运行时检查数据类型，保证了类型安全
（4）它是平台无关的，可移植性
（5）可用于基本数据类型

8.CSingleLock是干什么的。
答：同步多个线程对一个数据类的同时访问

9.NEWTEXTMETRIC 是什么。
答：物理字体结构，用来设置字体的高宽大小

10.程序什么时候应该使用线程，什么时候单线程效率高。
答：1．耗时的操作使用线程，提高应用程序响应
2．并行操作时使用线程，如C/S架构的服务器端并发线程响应用户的请求。
3．多CPU系统中，使用线程提高CPU利用率
4．改善程序结构。一个既长又复杂的进程可以考虑分为多个线程，成为几个独立或半独立的运行部分，这样的程序会利于理解和修改。
其他情况都使用单线程。

11.Windows是内核级线程么。
答：见下一题

12.Linux有内核级线程么。
答：线程通常被定义为一个进程中代码的不同执行路线。从实现方式上划分，线程有两种类型：“用户级线程”和“内核级线程”。用户线程指不需要内核支持而在用户程序中实现的线程，其不依赖于操作系统核心，应用进程利用线程库提供创建、同步、调度和管理线程的函数来控制用户线程。这种线程甚至在象 DOS 这样的操作系统中也可实现，但线程的调度需要用户程序完成，这有些类似 Windows 3.x 的协作式多任务。另外一种则需要内核的参与，由内核完成线程的调度。其依赖于操作系统核心，由内核的内部需求进行创建和撤销，这两种模型各有其好处和缺点。用户线程不需要额外的内核开支，并且用户态线程的实现方式可以被定制或修改以适应特殊应用的要求，但是当一个线程因 I/O 而处于等待状态时，整个进程就会被调度程序切换为等待状态，其他线程得不到运行的机会；而内核线程则没有各个限制，有利于发挥多处理器的并发优势，但却占用了更多的系统开支。
Windows NT和OS/2支持内核线程。Linux 支持内核级的多线程

13.C++中什么数据分配在栈或堆中，New分配数据是在近堆还是远堆中？
答：栈: 存放局部变量，函数调用参数,函数返回值，函数返回地址。由系统管理
堆: 程序运行时动态申请，new 和 malloc申请的内存就在堆上
近堆还是远堆不是很清楚。

14.使用线程是如何防止出现大的波峰。
答：意思是如何防止同时产生大量的线程，方法是使用线程池，线程池具有可以同时提高调度效率和限制资源使用的好处，线程池中的线程达到最大数时，其他线程就会排队等候。

15函数模板与类模板有什么区别？
答：函数模板的实例化是由编译程序在处理函数调用时自动完成的，而类模板的实例化必须由程序员在程序中显式地指定。

16一般数据库若出现日志满了，会出现什么情况，是否还能使用？
答：只能执行查询等读操作，不能执行更改，备份等写操作，原因是任何写操作都要记录日志。也就是说基本上处于不能使用的状态。

17 SQL Server是否支持行级锁，有什么好处？
答：支持，设立封锁机制主要是为了对并发操作进行控制，对干扰进行封锁，保证数据的一致性和准确性，行级封锁确保在用户取得被更新的行到该行进行更新这段时间内不被其它用户所修改。因而行级锁即可保证数据的一致性又能提高数据操作的迸发性。

18如果数据库满了会出现什么情况，是否还能使用？
答：见16

19 关于内存对齐的问题以及sizof()的输出
答：编译器自动对齐的原因：为了提高程序的性能，数据结构（尤其是栈）应该尽可能地在自然边界上对齐。原因在于，为了访问未对齐的内存，处理器需要作两次内存访问；然而，对齐的内存访问仅需要一次访问。

20 int i=10, j=10, k=3; k*=i+j; k最后的值是？
答：60，此题考察优先级，实际写成： k*=(i+j);，赋值运算符优先级最低

21.对数据库的一张表进行操作,同时要对另一张表进行操作,如何实现?
答：将操作多个表的操作放入到事务中进行处理

22.TCP/IP 建立连接的过程?(3-way shake)
答：在TCP/IP协议中，TCP协议提供可靠的连接服务，采用三次握手建立一个连接。
第一次握手：建立连接时，客户端发送syn包(syn=j)到服务器，并进入SYN_SEND状态，等待服务器确认；
第二次握手：服务器收到syn包，必须确认客户的SYN（ack=j+1），同时自己也发送一个SYN包（syn=k），即SYN+ACK包，此时服务器进入SYN_RECV状态；
第三次握手：客户端收到服务器的SYN＋ACK包，向服务器发送确认包ACK(ack=k+1)，此包发送完毕，客户端和服务器进入ESTABLISHED状态，完成三次握手。

23.ICMP是什么协议,处于哪一层?
答：Internet控制报文协议，处于网络层（IP层）

24.触发器怎么工作的?
答：触发器主要是通过事件进行触发而被执行的，当对某一表进行诸如UPDATE、 INSERT、 DELETE 这些操作时，数据库就会自动执行触发器所定义的SQL 语句，从而确保对数据的处理必须符合由这些SQL 语句所定义的规则。

25.winsock建立连接的主要实现步骤?
答：服务器端：socker()建立套接字，绑定（bind）并监听（listen），用accept（）等待客户端连接。
客户端：socker()建立套接字，连接（connect）服务器，连接上后使用send()和recv（），在套接字上写读数据，直至数据交换完毕，closesocket()关闭套接字。
服务器端：accept（）发现有客户端连接，建立一个新的套接字，自身重新开始等待连接。该新产生的套接字使用send()和recv（）写读数据，直至数据交换完毕，closesocket()关闭套接字。

26.动态连接库的两种方式?
答：调用一个DLL中的函数有两种方法：
1．载入时动态链接（load-time dynamic linking），模块非常明确调用某个导出函数，使得他们就像本地函数一样。这需要链接时链接那些函数所在DLL的导入库，导入库向系统提供了载入DLL时所需的信息及DLL函数定位。
2．运行时动态链接（run-time dynamic linking），运行时可以通过LoadLibrary或LoadLibraryEx函数载入DLL。DLL载入后，模块可以通过调用 GetProcAddress获取DLL函数的出口地址，然后就可以通过返回的函数指针调用DLL函数了。如此即可避免导入库文件了。

27.IP组播有那些好处?答： Internet上产生的许多新的应用，特别是高带宽的多媒体应用，带来了带宽的急剧消耗和网络拥挤问题。组播是一种允许一个或多个发送者（组播源）发送单一的数据包到多个接收者（一次的，同时的）的网络技术。组播可以大大的节省网络带宽，因为无论有多少个目标地址，在整个网络的任何一条链路上只传送单一的数据包。所以说组播技术的核心就是针对如何节约网络资源的前提下保证服务质量。

B. UDP如何转为可靠协议面试回答了TCP和UDP

任何tcp连接都是一样的，三次握手过程
第一次发送syn包，回复syn/ack包，再恢复ack包，然后建立连接

C. TCP/IP协议面试题目,关于UDP面试题目.

任何tcp连接都是一样的，
三次握手
过程
第一次发送syn包，回复syn/ack包，再恢复ack包，然后建立连接

D. 各大公司笔试题及答案

腾讯笔试题：const的含义及实现机制
const的含义及实现机制，比如：const int i,是怎么做到i只可读的？
const用来说明所定义的变量是只读的。
这些在编译期间完成，编译器可能使用常数直接替换掉对此变量的引用。
更多阅读：
http://www.92ask.net/Archive/?action=show&id=18
初探编译器static、const之实现原理
腾讯笔试题：买200返100优惠券，实际上折扣是多少？
到商店里买200的商品返还100优惠券（可以在本商店代替现金）。请问实际上折扣是多少？
由于优惠券可以代替现金，所以可以使用200元优惠券买东西，然后还可以获得100元的优惠券。
假设开始时花了x元，那么可以买到 x + x/2 + x/4 + ...的东西。所以实际上折扣是50%.（当然，大部分时候很难一直兑换下去，所以50%是折扣的上限）
如果使用优惠券买东西不能获得新的优惠券，那么
总过花去了200元，可以买到200+100元的商品，所以实际折扣为 200/300 = 67%.
腾讯笔试题：tcp三次握手的过程，accept发生在三次握手哪个阶段？
accept发生在三次握手之后。
第一次握手：客户端发送syn包(syn=j)到服务器。
第二次握手：服务器收到syn包，必须确认客户的SYN（ack=j+1），同时自己也发送一个ASK包（ask=k）。
第三次握手：客户端收到服务器的SYN＋ACK包，向服务器发送确认包ACK(ack=k+1)。
三次握手完成后，客户端和服务器就建立了tcp连接。这时可以调用accept函数获得此连接。
腾讯笔试题：用UDP协议通讯时怎样得知目标机是否获得了数据包
用UDP协议通讯时怎样得知目标机是否获得了数据包？
可以在每个数据包中插入一个唯一的ID，比如timestamp或者递增的int。
发送方在发送数据时将此ID和发送时间记录在本地。
接收方在收到数据后将ID再发给发送方作为回应。
发送方如果收到回应，则知道接收方已经收到相应的数据包；如果在指定时间内没有收到回应，则数据包可能丢失，需要重复上面的过程重新发送一次，直到确定对方收到。
关于UDP协议的简单介绍，可以参考
http://ke..com/view/30509.htm
腾讯笔试题：统计论坛在线人数分布
求一个论坛的在线人数，假设有一个论坛，其注册ID有两亿个，每个ID从登陆到退出会向一个日志文件中记下登陆时间和退出时间，要求写一个算法统计一天中论坛的用户在线分布，取样粒度为秒。
一天总共有 3600*24 = 86400秒。
定义一个长度为86400的整数数组int delta[86400]，每个整数对应这一秒的人数变化值，可能为正也可能为负。开始时将数组元素都初始化为0。
然后依次读入每个用户的登录时间和退出时间，将与登录时间对应的整数值加1，将与退出时间对应的整数值减1。
这样处理一遍后数组中存储了每秒中的人数变化情况。
定义另外一个长度为86400的整数数组int online_num[86400]，每个整数对应这一秒的论坛在线人数。
假设一天开始时论坛在线人数为0，则第1秒的人数online_num[0] = delta[0]。第n+1秒的人数online_num[n] = online_num[n-1] + delta[n]。
这样我们就获得了一天中任意时间的在线人数。
腾讯笔试题：从10G个数中找到中数
在一个文件中有 10G 个整数，乱序排列，要求找出中位数。内存限制为 2G。
不妨假设10G个整数是64bit的。
2G内存可以存放256M个64bit整数。
我们可以将64bit的整数空间平均分成256M个取值范围，用2G的内存对每个取值范围内出现整数个数进行统计。这样遍历一边10G整数后，我们便知道中数在那个范围内出现，以及这个范围内总共出现了多少个整数。
如果中数所在范围出现的整数比较少，我们就可以对这个范围内的整数进行排序，找到中数。如果这个范围内出现的整数比较多，我们还可以采用同样的方法将此范围再次分成多个更小的范围（256M=2^28，所以最多需要3次就可以将此范围缩小到1，也就找到了中数）。
腾讯笔试题：两个整数集合A和B，求其交集
两个整数集合A和B，求其交集。
1. 读取整数集合A中的整数，将读到的整数插入到map中，并将对应的值设为1。
2. 读取整数集合B中的整数，如果该整数在map中并且值为1，则将此数加入到交集当中，并将在map中的对应值改为2。
通过更改map中的值，避免了将同样的值输出两次。
腾讯笔试题：找出1到10w中没有出现的两个数字
有1到10w这10w个数，去除2个并打乱次序，如何找出那两个数？
申请10w个bit的空间，每个bit代表一个数字是否出现过。
开始时将这10w个bit都初始化为0，表示所有数字都没有出现过。
然后依次读入已经打乱循序的数字，并将对应的bit设为1。
当处理完所有数字后，根据为0的bit得出没有出现的数字。
首先计算1到10w的和，平方和。
然后计算给定数字的和，平方和。
两次的到的数字相减，可以得到这两个数字的和，平方和。
所以我们有
x + y = n
x^2 + y^2 = m
解方程可以得到x和y的值。
腾讯笔试题：需要多少只小白鼠才能在24小时内找到毒药
有1000瓶水，其中有一瓶有毒，小白鼠只要尝一点带毒的水24小时后就会死亡，至少要多少只小白鼠才能在24小时时鉴别出那瓶水有毒？
最容易想到的就是用1000只小白鼠，每只喝一瓶。但显然这不是最好答案。
既然每只小白鼠喝一瓶不是最好答案，那就应该每只小白鼠喝多瓶。那每只应该喝多少瓶呢？
首先让我们换种问法，如果有x只小白鼠，那么24小时内可以从多少瓶水中找出那瓶有毒的？
由于每只小白鼠都只有死或者活这两种结果，所以x只小白鼠最大可以表示2^x种结果。如果让每种结果都对应到某瓶水有毒，那么也就可以从2^x瓶水中找到有毒的那瓶水。那如何来实现这种对应关系呢？
第一只小白鼠喝第1到2^(x-1)瓶，第二只小白鼠喝第1到第2^(x-2)和第2^(x-1)+1到第2^(x-1) + 2^(x-2)瓶....以此类推。
回到此题，总过1000瓶水，所以需要最少10只小白鼠。
腾讯笔试题：根据上排的数填写下排的数，并满足要求。
根据上排给出十个数，在其下排填出对应的十个数, 要求下排每个数都是上排对应位置的数在下排出现的次数。上排的数：0，1，2，3，4，5，6，7，8，9。
腾讯笔试题：判断数字是否出现在40亿个数中？
给40亿个不重复的unsigned int的整数，没排过序的，然后再给几个数，如何快速判断这几个数是否在那40亿个数当中?
答案：
unsigned int 的取值范围是0到2^32-1。我们可以申请连续的2^32/8=512M的内存，用每一个bit对应一个unsigned int数字。首先将512M内存都初始化为0，然后每处理一个数字就将其对应的bit设置为1。当需要查询时，直接找到对应bit，看其值是0还是1即 可。
1、请定义一个宏，比较两个数a、b的大小，不能使用大于、小于、if语句#define Max(a,b) ( a/b)?a:b
2、如何输出源文件的标题和目前执行行的行数
int line = __LINE__;
char *file = __FILE__;
cout<<"file name is "<<(file)<<",line is "<
3、两个数相乘，小数点后位数没有限制，请写一个高精度算法
4、写一个病毒
while (1)
{
int *p = new int[10000000];
}
5、不使用额外空间,将 A,B两链表的元素交*归并
6、将树序列化 转存在数组或 链表中
struct st{
int i;
short s;
char c;
};
sizeof(struct st)；
7、
char * p1;
void * p2;
int p3;
char p4[10];
sizeof(p1...p4) =?
8、
4，4，4，10
二分查找
快速排序
双向链表的删除结点
面试基本上都是和项目相关的，并当场说几个程序题的输出，不能用草稿纸

微软笔试题：写程序找出二叉树的深度
一个树的深度等于max（左子树深度，右子树深度）+1。可以使用递归实现。
假设节点为定义为
1. struct Node {
2. Node* left;
3. Node* right;
4. };
5. int GetDepth(Node* root) {
6. if (NULL == root) {
7. return 0;
8. }
9. int left_depth = GetDepth(root->left);
10. int right_depth = GetDepth(root->right);
11. return left_depth > right_depth ? left_depth + 1 : right_depth + 1;
12. }
微软笔试题：利用天平砝码，三次将140克的盐 分成50、90克两份？
有一个天平，2克和7克砝码各一个。如何利用天平砝码在三次内将140克盐分成50，90克两份。
第一种方法：
第一次:先称 7+2克盐 (相当于有三个法码2,7,9)
第二次:称2+7+9=18克盐 (相当于有2,7,9,18四个法码)
第三次:称7+18=x+2,得出x是23，23+9+18=50克盐.
剩下就是90克了.
第二种方法：
1.先把140克盐分为两份，每份70克
2.在把70克分为两份，每份35克
3.然后把两个砝码放在天平两边，把35克面粉分成两份也放在两边（15+7=20+2）
现在有四堆面粉70，35，15，20，分别组合得到
70+20=90
35+15=50
微软笔试题：地球上有多少个满足这样条件的点
站在地球上的某一点，向南走一公里，然后向东走一公里，最后向北走一公里，回到了原点。地球上有多少个满足这样条件的点?
北极点满足这个条件。
距离南极点很近的一个圈上也满足这个条件。在这个圆圈上，向南走一公里，然后向东走一公里恰好绕南极点一圈，向北走一公里回到原点。
所以地球上总共有无数点满足这个条件。
或者
首先，在地球表面上，南北走向是沿着经度方向，东西是沿着纬度方向。如果你一直往北走就会达到北极点，往南走就到了南极点。因此，向南走一公里，然 后向东走一公里，最后向北走一公里，回到了原点，一种情况就是，出发点是在北极点，这样向南走一公里，然后向东走任意几公里，最后向北走一公里，最后都会 回到北极点；
其次，可以这么认为如果从A点向南走一公里到达B点，那么若向东走一公里能回到B，那么最后向北走一公里，就能回到了原点A。这样就可以先找出在南 北极点附近找出绕一周只有1公里的圈，那么这个圈落在南极附近时，只要往北推1公里，此时该圈上的点都能满足；若这个圈落在北极附近时，能不能往北推1公 里我就不分析了。反正在南极附近能找到任意多个点就能回到这个问题了
微软笔试题：正确标注水果篮
有三个水果篮。其中一个里面只有苹果，一个里面只有橘子，另外一个既有苹果又有橘子。每个水果篮上都有标签，但标签都是错的。如何检查某个水果篮中的一个水果，然后正确标注每个水果篮？
从标注成既有苹果也有橘子的水果篮中选取一个进行检查。
如果是橘子，则此篮中只有橘子；标有橘子的水果篮中只有苹果；标有苹果的水果篮中既有苹果也有橘子。
如果是苹果，则此篮中只有苹果；标有苹果的水果篮中只有橘子；标有橘子的水果篮中既有苹果也有橘子。
微软笔试题：不利用浮点运算，画一个圆
不利用浮点运算，在屏幕上画一个圆 (x**2 + y**2 = r**2，其中 r 为正整数)。
考虑到圆的对称性，我们只需考虑第一象限即可。
等价于找到一条连接点（0，r）到点（r，0）的一条曲线，曲线上的点距圆心（0，0）的距离最接近 r。
我们可以从点（0，r）开始，搜索右（1，r），下（0，r-1），右下（1，r-1）三个点到圆心的距离，选择距圆心距离最接近 r 的点作为下一个点。反复进行这种运算，直至到达点（r，0）。
由于不能利用浮点运算，所以距离的比较只能在距离平方的基础上进行。也就是比较 x**2 + y**2 和 r**2之间的差值。
微软笔试题：将一个句子按单词反序
将一个句子按单词反序。比如 “hi com mianshiti”，反序后变为 “mianshiti com hi”。
可以分两步走：
第一步按找字母反序，“hi com mianshiti” 变为 “itihsnaim moc udiab ih”。
第二部将每个单词中的字母反序，“itihsnaim moc udiab ih” 变成 “mianshiti com hi”。
这个方法可以在原字符串上进行，只需要几个整数变量来保持指针即可，空间复杂度低。
微软笔试题：计算n bit的整数中有多少bit 为1
设此整数为x。
方法1：
让此整数除以2，如果余数为1，说明最后一位是1，统计值加1。
将除得的结果进行上面运算，直到结果为0。
方法2：
考虑除法复杂度有些高，可以使用移位操作代替除法。
将 x 和 1 进行按位与操作（x&1），如果结果为1，说明最后一位是1，统计值加1。
将x 向右一位（x >> 1），重复上面过程，直到移位后结果为0。
方法3：
如果需要统计很多数字，并且内存足够大，可以考虑将每个数对应的bit为1的数量记录下来，这样每次计算只是一次查找操作。
1. int n = 0;while (x)
2. {
3. xx = x & (x - 1);
4. n++;
5. }
6. return n;
微软笔试题：快速求取一个整数的7倍
乘法相对比较慢，所以快速的方法就是将这个乘法转换成加减法和移位操作。
可以将此整数先左移三位（×8）然后再减去原值：X << 3 - X。
微软笔试题：判断一个数是不是2的n次幂
设要判断的数是无符号整数X。
首先判断X是否为0，如果为0则不是2的n次幂，返回。
X和X-1进行按位与操作，如果结果是0，则说明这个数是2的n次幂；如果结果非0，则说明这个数不是2 的n次幂。
证明：
如果是2的n次幂，则此数用二进制表示时只有一位是1，其它都是0。减1后，此位变成0，后面的位变成1，所以按位与后结果是0。
如果不是2的n次幂，则此数用二进制表示时有多位是1。减1后，只有最后一个1变成0，前面的 1还是1，所以按位与后结果不是0。
微软笔试题：三只蚂蚁不相撞的概率是多少
在三角形的三个顶点上各有一只蚂蚁，它们向另一个顶点运动，目标随机（可能为另外两个顶点的任意一个）。问三只蚂蚁不相撞的概率是多少？
如果蚂蚁顺时针爬行记为0，逆时针爬行记为1。那么三只蚂蚁的状态可能为000，001，...，110，111中的任意一个，且为每种状态的概率相等。在这8种状态中，只有000和111可以避免相撞，所以蚂蚁不相撞的概率是1/4。
微软笔试题：判断数组中是否包含重复数字
给定一个长度为N的数组，其中每个元素的取值范围都是1到N。判断数组中是否有重复的数字。（原数组不必保留）
给定一个长度为N的数组，其中每个元素的取值范围都是1到N。判断数组中是否有重复的数字。（原数组不必保留）
微软笔试题：如何将蛋糕切成相等的两份
一块长方形的蛋糕，其中有一个小长方形的空洞（角度任意）。使用一把直刀，如何一刀将蛋糕切成相等的两份？
通过长方形中心的的任意直线都能将长方形等分，所以连接两个长方形的中心点的直线可以等分这个蛋糕。
一个没有排序的链表，比如list={a,l,x,b,e,f,f,e,a,g,h,b,m}，请去掉重复项，并保留原顺序，以上链表去掉重复项后为newlist={a,l,x,b,e,f,g,h,m}，请写出一个高效算法(时间比空间更重要)。
建立一个hash_map，key为链表中已经遍历的节点内容，开始时为空。
从头开始遍历链表中的节点：
- 如果节点内容已经在hash_map中存在，则删除此节点，继续向后遍历；
- 如果节点内容不在hash_map中，则保留此节点，将节点内容添加到hash_map中，继续向后遍历。
微软笔试题：小明一家5口如何过桥？
小明一家过一座桥，过桥时是黑夜，所以必须有灯。现在小明过桥要1秒，小明的弟弟要3秒，小明的爸爸要6秒，小明的妈妈要8秒，小明的爷爷要12秒。每次此桥最多可过两人，而过桥的速度依过桥最慢者而定，而且灯在点燃后30秒就会熄灭。问：小明一家如何过桥？
小明与弟弟过去，小明回来，用4s；
妈妈与爷爷过去，弟弟回来，用15s；
小明与弟弟过去，小明回来，用4s；
小明与爸爸过去，用6s；
总共用29s。
题目的关键是让速度差不多的一起走，免得过于拖累较快的一个人。
微软笔试题：编一个程序求质数的和
编一个程序求质数的和，例如F(7) = 2+3+5+7+11+13+17=58。
方法1：
对于从2开始的递增整数n进行如下操作：
用 [2，n-1] 中的数依次去除n，如果余数为0，则说明n不是质数；如果所有余数都不是0，则说明n是质数，对其进行加和。
空间复杂度为O(1)，时间复杂度为O(n^2)，其中n为需要找到的最大质数值（例子对应的值为17）。
方法2：
可以维护一个质数序列，这样当需要判断一个数是否是质数时，只需判断是否能被比自己小的质数整除即可。
对于从2开始的递增整数n进行如下操作：
用 [2，n-1] 中的质数（2，3，5，7，开始时此序列为空）依次去除n，如果余数为0，则说明n不是质数；如果所有余数都不是0，则说明n是质数，将此质数加入质数序列，并对其进行加和。
空间复杂度为O(m)，时间复杂度为O(mn)，其中m为质数的个数（例子对应的值为7），n为需要找到的最大质数值（例子对应的值为17）。
方法3：
也可以不用除法，而用加法。
申请一个足够大的空间，每个bit对应一个整数，开始将所有的bit都初始化为0。
对于已知的质数（开始时只有2），将此质数所有的倍数对应的bit都改为1，那么最小的值为0的bit对应的数就是一个质数。对新获得的质数的倍数也进行标注。
对这样获得的质数序列累加就可以获得质数和。
空间复杂度为O(n)，时间负责度为O(n)，其中n为需要找到的最大质数值（例子对应的值为17）。

E. 网络工程师面试题

网络工程师面试题 1: 交换机是如何转发数据包的?

交换机通过学习数据帧中的源MAC地址生成交换机的MAC地址表，交换机查看数据帧的目标MAC地址，根据MAC地址表转发数据，如果交换机在表中没有找到匹配项，则向除接受到这个数据帧的端口以外的所有端口广播这个数据帧。

2 简述STP的作用及工作原理.

作用:(1) 能够在逻辑上阻断环路，生成树形结构的拓扑;
(2) 能够不断的检测网络的变化，当主要的线路出现故障断开的时候，STP还能通过计算激活阻起到断的端口，起到链路的备份作用。
工作原理: STP将一个环形网络生成无环拓朴的步骤：
选择根网桥（Root Bridge）
选择根端口（Root Ports）
选择指定端口（Designated Ports）

生成树机理
每个STP实例中有一个根网桥
每个非根网桥上都有一个根端口
每个网段有一个指定端口
非指定端口被阻塞 STP是交换网络的重点,考察是否理解.

3:简述传统的多层交换与基于CEF的多层交换的区别

简单的说:传统的多层交换:一次路由,多次交换

基于CEF的多层交换:无须路由,一直交换.

4:DHCP的作用是什么,如何让一个vlan中的DHCP服务器为整个企业网络分配IP地址?

作用:动态主机配置协议,为客户端动态分配IP地址.
配置DHCP中继,也就是帮助地址.(因为DHCP是基于广播的,vlan 或路由器隔离了广播)

5:有一台交换机上的所有用户都获取不了IP地址,但手工配置后这台交换机上的同一vlan间的用户之间能够相互ping通,但ping不通外网,请说出排障思路.

1:如果其它交换机上的终端设备能够获取IP地址,看帮助地址是否配置正确;
2:此交换机与上连交换机间是否封装为Trunk.
3:单臂路由实现vlan间路由的话看子接口是否配置正确,三层交换机实现vlan间路由的话看是否给vlan配置ip地址及配置是否正确.
4:再看此交换机跟上连交换机之间的级连线是否有问题;
排障思路.

6:什么是静态路由？什么是动态路由？各自的特点是什么？

静态路由是由管理员在路由器中手动配置的固定路由，路由明确地指定了包到达目的地必须经过的路径，除非网络管理员干预，否则静态路由不会发生变化。静态路由不能对网络的改变作出反应，所以一般说静态路由用于网络规模不大、拓扑结构相对固定的网络。

静态路由特点
1、它允许对路由的行为进行精确的控制；
2、减少了网络流量；
3、是单向的；
4、配置简单。
动态路由是网络中的路由器之间相互通信，传递路由信息，利用收到的路由信息更新路由表的过程。是基于某种路由协议来实现的。常见的路由协议类型有：距离矢量路由协议（如RIP）和链路状态路由协议（如 OSPF）。路由协议定义了路由器在与其它路由器通信时的一些规则。动态路由协议一般都有路由算法。其路由选择算法的必要步骤
1、向其它路由器传递路由信息；
2、接收其它路由器的路由信息；
3、根据收到的路由信息计算出到每个目的网络的最优路径，并由此生成路由选择表；
4、根据网络拓扑的变化及时的做出反应，调整路由生成新的路由选择表，同时把拓扑变化以路由信息的形式向其它路由器宣告。
动态路由适用于网络规模大、拓扑复杂的网络。
动态路由特点：
1、无需管理员手工维护，减轻了管理员的工作负担。
2、占用了网络带宽。
3、在路由器上运行路由协议，使路由器可以自动根据网络拓朴结构的变化调整路由条目；
能否根据具体的环境选择合适的路由协议

7:简述有类与无类路由选择协议的区别

有类路由协议:路由更新信息中不含有子网信息的协议,如RIPV1,IGRP
无类路由协议:路由更新信息中含有子网信息的协议,如OSPF,RIPV2,IS-IS，EIGRP 是否理解有类与无类
8:简述RIP的防环机制
1.定义最大跳数 Maximum Hop Count （15跳）
2.水平分割 Split Horizon （默认所有接口开启，除了Frame-Relay的物理接口，可用sh ip interface 查看开启还是关闭）
3.毒化路由 Poizoned Route
4.毒性反转 Poison Reverse （RIP基于UDP，UDP和IP都不可靠，不知道对方收到毒化路由没有；类似于对毒化路由的Ack机制）
5.保持计时器 hold­-down Timer （防止路由表频繁翻动）
6.闪式更新 Flash Update
7.触发更新 Triggered Update （需手工启动，且两边都要开 Router (config-if)# ip rip triggered ）
当启用触发更新后，RIP不再遵循30s的周期性更新时间，这也是与闪式更新的区别所在。

RIP的4个计时器：
更新计时器（update）： 30 s
无效计时器（invalid）： 180 s （180s没收到更新，则置为possible down状态）
保持计时器（holddown）： 180s （真正起作用的只有60s）
刷新计时器（flush）： 240s （240s没收到更新，则删除这条路由）
如果路由变成possible down后，这条路由跳数将变成16跳，标记为不可达；这时holddown计时器开始计时。
在holddown时间内即使收到更优的路由，不加入路由表；这样做是为了防止路由频繁翻动。
什么时候启用holddown计时器： “当收到一条路由更新的跳数大于路由表中已记录的该条路由的跳数”

9:简述电路交换和分组交换的区别及应用场合. 电路交换连接

根据需要进行连接
每一次通信会话期间都要建立、保持，然后拆除
在电信运营商网络中建立起来的专用物理电路

分组交换连接
将传输的数据分组
多个网络设备共享实际的物理线路
使用虚电路/虚通道（Virtual Channel）传输

若要传送的数据量很大，且其传送时间远大于呼叫时间，则采用电路交换较为合适；当端到端的通路有很多段的链路组成时，采用分组交换传送数据较为合适。

10:简述PPP协议的优点. 支持同步或异步串行链路的传输

支持多种网络层协议
支持错误检测
支持网络层的地址协商
支持用户认证
允许进行数据压缩

11: pap和chap认证的区别

PAP(口令验证协议 Password Authentication Protocol)是一种简单的明文验证方式。NAS（网络接入服务器，Network Access Server）要求用户提供用户名和口令，PAP以明文方式返回用户信息。很明显，这种验证方式的安全性较差，第三方可以很容易的获取被传送的用户名和口令，并利用这些信息与NAS建立连接获取NAS提供的所有资源。所以，一旦用户密码被第三方窃取，PAP无法提供避免受到第三方攻击的保障措施。

CHAP(挑战-握手验证协议 Challenge-Handshake Authentication Protocol)是一种加密的验证方式，能够避免建立连接时传送用户的真实密码。NAS向远程用户发送一个挑战口令（challenge），其中包括会话ID和一个任意生成的挑战字串（arbitrary challengestring）。远程客户必须使用MD5单向哈希算法（one-way hashing algorithm）返回用户名和加密的挑战口令，会话ID以及用户口令，其中用户名以非哈希方式发送。

CHAP对PAP进行了改进，不再直接通过链路发送明文口令，而是使用挑战口令以哈希算法对口令进行加密。因为服务器端存有客户的明文口令，所以服务器可以重复客户端进行的操作，并将结果与用户返回的口令进行对照。CHAP为每一次验证任意生成一个挑战字串来防止受到再现攻击（replay attack）。在整个连接过程中，CHAP将不定时的向客户端重复发送挑战口令，从而避免第3方冒充远程客户（remote client impersonation）进行攻击。

12:ADSL是如何实现数据与语音同传的?

物理层:频分复用技术.(高频传输数据,低频传输语音)具体讲解的话可以说明:调制,滤波,解调的过程.

13:OSPF中那几种网络类型需要选择DR,BDR?

广播型网络和非广播多路访问NBMA网络需要选.

14:OSPF中完全末梢区域的特点及适用场合

特点:不能学习其他区域的路由
不能学习外部路由
完全末梢区域不仅使用缺省路由到达OSPF自主系统外部的目的地址,而且使用这个缺省路由到达这个区域外部的所有目的地址.一个完全末梢区域的ABR不仅阻塞AS外部LSA,而且阻塞所有汇总LSA.
适用场合:只有一出口的网络.

15:OSPF中为什么要划分多区域?

1、减小路由表大小
2、限制lsa的扩散
3、加快收敛
4、增强稳定性

16:NSSA区域的特点是什么?

1.可以学习本区域连接的外部路由；
2.不学习其他区域转发进来的外部路由

17:你都知道网络的那些冗余技术,请说明.

交换机的冗余性：spanning－tree、ethernet－channel
路由的冗余性:HSRP,VRRP,GLBP.
(有必要的话可以详细介绍)

18:HSRP的转换时间是多长时间?

10s

19:标准访问控制列表和扩展访问控制列表的区别.

标准访问控制列表:基于源进行过滤
扩展访问控制列表: 基于源和目的地址、传输层协议和应用端口号进行过滤

20:NAT的原理及优缺点.

原理:转换内部地址,转换外部地址,PAT,解决地址重叠问题.
优点:节省IP地址,能够处理地址重复的情况,增加了灵活性,消除了地址重新编号,隐藏了内部IP地址.
缺点:增加了延迟,丢失了端到端的IP的跟踪过程,不能够支持一些特定的应用(如:SNMP),需要更多的内存来存储一个NAT表,需要更多的CPU来处理NAT的过程.

21: 对称性加密算法和非对称型加密算法的不同？

对称性加密算法的双方共同维护一组相同的密钥，并使用该密钥加密双方的数据，加密速度快，但密钥的维护需要双方的协商，容易被人窃取；非对称型加密算法使用公钥和私钥，双方维护对方的公钥（一对），并且各自维护自己的私钥，在加密过程中，通常使用对端公钥进行加密，对端接受后使用其私钥进行解密，加密性良好，而且不易被窃取，但加密速度慢.

22: 安全关联的作用？

SA分为两步骤：1.IKE SA，用于双方的对等体认证，认证对方为合法的对端；2.IPSec SA，用于双方认证后，协商对数据保护的方式.

23: ESP和AH的区别？

ESP除了可以对数据进行认证外，还可以对数据进行加密；AH不能对数据进行加密，但对数据认证的支持更好 .

24: snmp的两种工作方式是什么,有什么特点?

首先,SNMP是基于UDP的,有两种工作方式,一种是轮询,一种是中断.
轮询:网管工作站随机开端口轮询被管设备的UDP的161端口.
中断:被管设备将trap报文主动发给网管工作站的UDP的162端口.
特点:轮询一定能够查到被管设备是否出现了故障,但实时性不好.
中断实时性好(触发更新),但不一定能够将trap报文报告给网管工作站.