python 面试题：三

一、题目部分

1、tcp和udp的区别？
2、对内存中栈和堆的了解？
3、爬虫框架scrapy的工作流程
4、字典、列表查询时的时间复杂度是怎样的？　
5、递归中如果没有终止条件会怎样？

二、 解答部分：

1、tcp和udp的区别？
TCP（Transmission Control Protocol，传输控制协议）是面向连接的协议，也就是说，在收发数据前，必须和对方建立可靠的连接。一个TCP连接必须要经过三次“对话”才能建立起来，其中的过程非常复杂，只简单的描述下这三次对话的简单过程：主机A向主机B发出连接请求数据包：“我想给你发数据，可以吗？”，这是第一次对话；主机B向主机A发送同意连接和要求同步（同步就是两台主机一个在发送，一个在接收，协调工作）的数据包：“可以，你什么时候发？”，这是第二次对话；主机A再发出一个数据包确认主机B的要求同步：“我现在就发，你接着吧！”，这是第三次对话。三次“对话”的目的是使数据包的发送和接收同步，经过三次“对话”之后，主机A才向主机B正式发送数据。

TCP三次握手过程：

1 主机A通过向主机B 发送一个含有同步序列号的标志位的数据段给主机B ,向主机B 请求建立连接,通过这个数据段，主机A告诉主机B 两件事:我想要和你通信;你可以用哪个序列号作为起始数据段来回应我.
　　2 主机B 收到主机A的请求后,用一个带有确认应答(ACK)和同步序列号(SYN)标志位的数据段响应主机A,也告诉主机A两件事:我已经收到你的请求了,你可以传输数据了;你要用哪佧序列号作为起始数据段来回应我
　　3 主机A收到这个数据段后,再发送一个确认应答,确认已收到主机B 的数据段:"我已收到回复,我现在要开始传输实际数据了这样3次握手就完成了,主机A和主机B 就可以传输数据了.

3次握手的特点：

• 没有应用层的数据
• SYN这个标志位只有在TCP建产连接时才会被置1
• 握手完成后SYN标志位被置0

SYN攻击
在三次握手过程中，服务器发送SYN-ACK之后，收到客户端的ACK之前的TCP连接称为半连接(half-open connect).此时服务器处于Syn_RECV状态. 当收到ACK后，服务器转入ESTABLISHED状态.

SYN攻击就是 攻击客户端 在短时间内伪造大量不存在的IP地址，向服务器不断地发送syn包，服务器回复确认包，并等待客户的确认，由于源地址是不存在的，服务器需要不断的重发直至超时，这些伪造的SYN包将长时间占用未连接队列，正常的SYN请求被丢弃，目标系统运行缓慢，严重者引起网络堵塞甚至系统瘫痪。

Syn攻击是一个典型的DDOS攻击。检测SYN攻击非常的方便，当你在服务器上看到大量的半连接状态时，特别是源IP地址是随机的，基本上可以断定这是一次SYN攻击。

TCP 4次挥手：

1 当主机A完成数据传输后,将控制位FIN置1,提出停止TCP连接的请求
　　2 主机B收到FIN后对其作出响应,确认这一方向上的TCP连接将关闭,将ACK置1
　　3 由B 端再提出反方向的关闭请求,将FIN置1
　　4 主机A对主机B的请求进行确认,将ACK置1,双方向的关闭结束.
　　由TCP的三次握手和四次断开可以看出,TCP使用面向连接的通信方式,大大提高了数据通信的可靠性,使发送数据端和接收端在数据正式传输前就有了交互,为数据正式传输打下了可靠的基础。

名词解释：
ACK TCP报头的控制位之一,对数据进行确认.确认由目的端发出,用它来告诉发送端这个序列号之前的数据段都收到了.比如,确认号为X,则表示前X-1个数据段都收到了,只有当ACK=1时,确认号才有效,当ACK=0时,确认号无效,这时会要求重传数据,保证数据的完整性.
SYN 同步序列号,TCP建立连接时将这个位置1
FIN 发送端完成发送任务位,当TCP完成数据传输需要断开时,提出断开连接的一方将这位置1

TCP的包头结构：
　　源端口 16位
　　目标端口 16位
　　序列号 32位
　　回应序号 32位
　　TCP头长度 4位
　　reserved 6位
　　控制代码 6位
　　窗口大小 16位
　　偏移量 16位
　　校验和 16位
　　选项 32位(可选)
　　这样我们得出了TCP包头的最小长度，为20字节。

UDP（User Data Protocol，用户数据报协议）
　　（1） UDP是一个非连接的协议，传输数据之前源端和终端不建立连接，当它想传送时就简单地去抓取来自应用程序的数据，并尽可能快地把它扔到网络上。在发送端，UDP传送数据的速度仅仅是受应用程序生成数据的速度、计算机的能力和传输带宽的限制；在接收端，UDP把每个消息段放在队列中，应用程序每次从队列中读一个消息段。
　　（2） 由于传输数据不建立连接，因此也就不需要维护连接状态，包括收发状态等，因此一台服务机可同时向多个客户机传输相同的消息。
　　（3） UDP信息包的标题很短，只有8个字节，相对于TCP的20个字节信息包的额外开销很小。
　　（4） 吞吐量不受拥挤控制算法的调节，只受应用软件生成数据的速率、传输带宽、源端和终端主机性能的限制。
　　（5）UDP使用尽最大努力交付，即不保证可靠交付，因此主机不需要维持复杂的链接状态表（这里面有许多参数）。
　　（6）UDP是面向报文的。发送方的UDP对应用程序交下来的报文，在添加首部后就向下交付给IP层。既不拆分，也不合并，而是保留这些报文的边界，因此，应用程序需要选择合适的报文大小。
　　我们经常使用“ping”命令来测试两台主机之间TCP/IP通信是否正常，其实“ping”命令的原理就是向对方主机发送UDP数据包，然后对方主机确认收到数据包，如果数据包是否到达的消息及时反馈回来，那么网络就是通的。
UDP的包头结构：
　　源端口 16位
　　目的端口 16位
　　长度 16位
　　校验和 16位

小结TCP与UDP的区别：
　　1.基于连接与无连接；
　　2.对系统资源的要求（TCP较多，UDP少）；
　　3.UDP程序结构较简单；
　　4.流模式与数据报模式 ；
　　5.TCP保证数据正确性，UDP可能丢包，TCP保证数据顺序，UDP不保证。
2、对内存中栈和堆的了解？
栈：
什么是栈，它是你的电脑内存的一个特别区域，它用来存储被每一个function（包括mian（）方法）创建的临时变量。栈是FILO，就是先进后出原则的结构体，它密切的被CPU管理和充分利用。每次function声明一个新的变量，它就会被“推”到栈中。然后每次一个function退出时，所有关于这个函数中定义的变量都会被释放（换句话说就是删除）。一旦栈中的变量释放，这块区域就会变成可用的，提供给其他栈中的变量。
用栈存储变量的好处是，内存是被你管理的。你不用手动的创建内存，不用当你不在需要它的时候手动释放内存。另外，由于CPU组织栈内存很高效。读出和写入栈变量是很快的。
理解栈的关键是理解概念，当一个function退出时，所有它的变量都会从栈中弹出,以后都会永远消失。因此栈中的变量本质是局部的。这和我们原来理解为变量作用域或者本地或者全局变量是相关的。在C中，一个公共的bug 是从你程序中的一个function外尝试访问一个在栈中的这个function的变量（在该function已经退出后）。
关于栈的另一个特点我们应该记住，就是存储在栈中的变量的大小有限制。而堆上创建变量不用考虑。
总结栈：
a、栈的伸长和伸缩就是函数压入或者推出局部变量。
b、我们不用自己去管理内存，变量创建和释放都是自动的。
c、栈中的变量只有在函数创建运行时存在。
堆：
堆也是我们的计算机内存中的一个区域，但是他不是自动管理的。而且也不是被CPU密切的管理着。它是一片更加自由的内存区域（很大）。要想在堆上创建内存，我们必须使用malloc() 或者calloc（），他们都是C语言编译的。一旦你在堆上分配内存，当你不在需要的时候你必须用free()去销毁。如果你不销毁或者销毁失败，你的程序就会有内存泄露。换句话说就是堆内存会一直在，其他进程无法使用。
不像栈，堆没有变量大小的限制（除了你电脑的物理限制条件外）。堆内存读出和写入都比较慢，因为它必须使用指针图访问堆内存。
栈和堆的优缺点：
栈：
a、快速访问。
b、没有必要明确的创建分类变量，因为它是自动管理的。
c、空间被CPU高效地管理着，内存不会变成碎片。
d、只有局部变量
e、受限于栈大小(取决于操作系统)
f、变量不能调整大小。
堆：
a、变量可以被全局访问
b、没有内存大小限制
c、（相对）访问比较慢
d、没有高效地使用空间，随着块内存的创建和销毁，内存可能会变成碎片。
e、你必须管理内存（变量的创建和销毁你必须要负责）
f、变量大小可以用realloc( )调整
3、爬虫框架scrapy的工作流程

a、spider解析下载器下下来的response，返回item或是links
b、item或者link经过spidermiddleware的process_spider_out( )方法，交给engine
c、engine将item交给item pipeline ，将links交给调度器
d、在调度器中，先将requests对象利用scrapy内置的指纹函数生成一个指纹对象
e、如果requests对象中的don't filter参数设置为False，并且该requests对象的指纹不在信息指纹的队列中，那么就把该request对象放到优先级队列中
f、从优先级队列中获取request对象，交给engine
g、engine将request对象交给下载器下载，期间会通过downloadmiddleware的process_request方法
h、下载器完成下载，获得response对象，将该对象交给engine，期间会经过downloadmiddleware的process_response（ ）方法
i、engine将获得的response对象交给spider进行解析，期间会经过spidermiddleware的process_spider_input()的方法
j、从a开始循环

4、字典、列表查询时的时间复杂度是怎样的？　
列表是序列，可以理解为数据结构中的数组，字典可以理解为数据结构中的hashmap，python中list对象的存储结构采用的是线性表，因此其查询复杂度为O(n),而dict对象的存储结构采用的是散列表(hash表)，其在最优情况下查询复杂度为O(1)。dict的占用内存稍比list大，会在1.5倍左右。

5、递归中如果没有终止条件会怎样？
概念：递归算法是一种直接或者间接的调用自身算法的过程。在计算机编写程序中，递归算法对解决一大类问题是十分有效的。

特点：

①递归就是在过程或者函数里调用自身。

②在使用递归策略时，必须有一个明确的递归条件，称为递归出口。

③递归算法解题通常显得很简洁，但递归算法解题的效率较低。所以一般不倡导使用递归算法设计程序。

④在递归调用的过程当中系统的每一层的返回点、局部变量等开辟了栈来存储。递归函数次数过多容易造成栈溢出等。 所以一般不倡导用递归算法设计程序

递归如果没有终止条件会导致递归调用成为死循环而不能正常结束，并且会造成栈溢出