1.通常递归所采用的数据结构？递归和循环的区别？

 ->采用的数据结构为：栈

->(1)递归算法与循环算法的设计思路区别在于：

函数或算法是否具备收敛性，当且仅当一个算法存在预期的收敛效果时，采用递归算法才是可行的，否则，就不能使用递归算法。

(2)递归其实是方便了程序员难为了机器。优点就是易理解，容易编程。但递归是用栈机制实现的，每深入一层，都要占去一块栈数据区域，对嵌套层数深的一些算

 法，递归会力不从心，空间上会以内存崩溃而告终，而且递归也带来了大量的函数调用，这也有许多额外的时间开销。所以在深度大时，它的时空性就不好了。

循环其缺点就是不容易理解，编写复杂问题时困难。优点是效率高。运行时间只因循环次数增加而增加，没什么额外开销。空间上没有什么增加。

局部变量占用的内存是一次性的，也就是O(1)的空间复杂度，而对于递归（不考虑尾递归优化的情况），每次函数调用都要压栈，那么空间复杂度是O(n)，和递归次数呈线性关系。

(3)递归程序改用循环实现的话，一般都是要自己维护一个栈的，以便状态的回溯。原理上讲，所有递归都是可以消除的，代价就是可能自己要维护一个栈。而且我个人认为，很多情况下用递归还是必要的，它往往能把复杂问题分解成更为简单的步骤，而且很能反映问题的本质。

2.A,B,C,D四个进程，A向一个缓冲区写数据，B,C,D从该缓冲区读数据，A要等到B,C,D都已经读好才能写下一个。用p,v操作实现通讯。

设置五个信号量。缓冲区是否正在被使用信号量：S=1（初值，下同）；B有数据可读：bs=0；C有数据可读：cs=0；D有数据可读：ds=0；另外增加一个全局变量SA=3，表示b、c、d均读完。

3.补码:写出0，－1，－5的二进制补码

在计算机系统中，数值一律用补码来表示（存储）。 主要原因：使用补码，可以将符号位和其它位统一处理；同时，减法也可按加法

来处理。另外，两个用补码表示的数相加时，如果最高位（符号位）有进位，则进位被舍弃。 

求给定数值的补码表示分以下两种情况:

(1)正数的补码：与原码相同.【例1】+9的补码是00001001。 

(2)负数的补码：符号位为1，其余位为该数绝对值的原码按位取反；然后整个数加1.

0的补码是00000000
-1的补码是11111111
-5的补码是10000110

4.DNS的原理

DNS分为Client和Server，Client扮演发问的角色，也就是问Server一个Domain Name，而Server必须要回答此Domain Name的真正IP地址。而当地的DNS先会查自己的资料库。如果自己的资料库没有，则会往该DNS上所设的的DNS询问，依此得到答案之后，将收到的答案存起来，并回答客户。为了加快速度，通常将常用的域名地址存在就近的dns服务器的高速缓存区。这样可以提高速度。

5.项目开发：软件流程，瀑布模型；黑盒测试

->软件开发流程
需求说明，
结构化分析，结果需要得到系统的数据流图，数据字典和加工处理说明
总体设计，
详细设计
软件生存周期包括：
可行性分析与项目开发计划，需求分析，概要设计，详细设计，编码，测试，维护等活动

软件生存周期的模型：

瀑布模型：各活动依线性顺序连接，适合于软件需求很明确的软件项目

演化模型：先够造一个初始运行版本（原型），然后根据用户使用中的建议不断的改进，获得最终软件产品的过程。适用于对软件需求缺乏准确认识的情况

螺旋模型：将瀑布模型和演化模型结合起来，加入了两种模型均忽略的风险分析，将开发过程分为几个螺旋周期，每个螺旋周期大致和瀑布模型符合，每个周期用户评估结束后在进入下一个周期的开发计划。

喷泉模型：克服了瀑布模型不支持软件重用和多项开发活动集成的局限性，它开发过程中具有迭代性和无间隙性，迭代意味着模型中的开发活动常常需要重复多次，迭代过程中不断的完善，开发活动间没有明显的界限，交叉迭代进行，以用户需求为动力，以对象作为驱动的模型。适合于面向对象的开发方法。

测试：
软件测试的策略：
有效的软件测试实际上分成4步进行：
1)单元测试
2)集成测试
3) 确认测试
4) 系统测试
测试方法
静态测试，动态测试
测试用例的设计
(1)用黑盒法(又叫功能测试或数据驱动测试)设计测试用例
等价类划分，边值分析，错误猜测和因果图等
(2)白盒测试(又称为结构测试或逻辑驱动测试)
逻辑覆盖
循环覆盖
基本路径测试

6.全局变量和局部变量有什么区别？实怎么实现的？操作系统和编译器是怎么知道的

全局变量和局部变量的区别是作用域不同,全局变量从定义位置开始到程序结束,而局部变量只限定义的函数内可使用,全局变量在数据段,而局部变量在栈,局部变量在函数结束时内存空间就被系统收回,所以要返回的数组或字符串不要用局部变量定义.extren和在main()函数外定义的变量都称为全局变量,操作系统和编译器从定义变量为变量分配内存时,从变量的定义和存储区域来分别局部变量和全局变量.

编译器通过语法词法的分析，判断出是全局变量还是局部变量。如果是全局变量的话，编译器在将源代码翻译成二进制代码时就为全局变量分配好一个虚拟地址 (windows下0x00400000以上的地址，也就是所说的全局区)，所以程序在对全局变量的操作时是对一个硬编码的地址操做。局部变量的话，编译时不分配空间，而是以相对于ebp或esp的偏移来表示局部变量的地址，所以局部变量内存是在局部变量所在的函数被调用时才真正分配。以汇编的角度来看：函数执行时，局部变量在栈中分配，函数调用完毕释放局部变量对应的内存，另外局部变量可以直接分配在寄存器中。操作系统通过变量的分配地址就可以判断出是局部变量和全局变量。

7.C++ 的类和C++里面的struct有什么区别？ 

C++中的struct扩充了C的struct功能，其实它还拥有class的其他特性，例如继承、虚函数等。区别在于：

关于默认访问权限
class中默认的成员访问权限是private的，而struct中则是public的。
关于继承方式
class继承默认是private继承，而struct继承默认是public继承。
另外，在C++模板中，类型参数前面可以使用class或typename，如果使用struct，则含义不同，struct后面跟的是“non-type template parameter”，而class或typename后面跟的是类型参数。

－>C++中保留struct的关键字是为了使C++编译器能够兼容C开发的程序。

补充：C是一种过程化的语言，struct只是作为一种复杂数据类型定义，struct中只能定义成员变量，不能定义成员函数。

8.

面经中高频知识点归纳（六）