笔试题目整理

<1> 完全二叉树的叶子节点数的计算;

<2> Http的返回码含义

1.完全二叉树的叶子节点数的计算;

  1.完全二叉树

  若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。叶子节点只可能在最大的两层上出现,对任意结点,若其右分支下的子孙最大层次为L,则其左分支下的子孙的最大层次必为L 或 L+1;

  满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树。

  如果已知一个完全二叉树的节点数如何来进行计算呢?简单地思路是:直接判断层数:以2位底对节点数进行曲对数log,然后将得到的结果进行取整,取整后+1.一般要求我们熟练知道2的幂次,2的8次方是256,记住一个就好了。

  第一种方式:

  知道了数的深度,我们就可以去自己推测该二叉树的叶子节点数,因为完全二叉树的叶子节点都是集中在最后一层和倒数第二层。

  如果一个题目中的节点数总共为699,如何计算呢?首先699直接获取他的深度:10层,前九层全部铺满为511个节点所以前九层全部铺满,剩余699-511=188个节点,这188全部都是子节点位于第10层,在这188个节点将会占用自己左侧的父节点94个,也就是在第九层会有94个节点被占有,剩余256-94=162个节点,没有子节点了,也就是我们呢想要的叶子节点,此时得到最后的结果是162+188 = 350.一共350个叶子节点。

  第二种方式:

  可以根据公式进行推导,假设n0是度为0的结点总数(即叶子结点数),n1是度为1的结点总数,n2是度为2的结点总数,由二叉树的性质可 知:n0=n2+1,且n= n0+n1+n2(其中n为完全二叉树的结点总数),由上述公式把n2消去得:n= 2n0+n1-1,由于完全二叉树中度为1的结点数只有两种可能0或1,由此得到n0=(n+1)/2或n0=n/2,就可根据完全二叉树的结点总数计算出叶子结点数。

关于第二种方式的解释:以及二叉树的度

  首先说说什么是度:通俗的讲二叉树中连接节点和节点的线就是度,有n个节点,就有n-1个度,节点数总是比度要多一个,那么度为0的节点一定是叶子节点,因为该节点的下面不再有线;度为1的节点即:该节点只有一个分支;同理度为2的节点就是有两个分支。在二叉树中不可能存在度为3或大于3的节点!
  关于度和节点之间的关系还有很多公式:度为0的节点数为度为2的节点数加1,即n0=n2+1
这个公式的推理方法如下:
设:
k:总度数
k+1:总节点数
n0:度为0的节点
n1:度为1的节点
n2:度为二的节点
根据二叉树中度和节点的守衡原理,可列出以下一组方程:
k=n2*2+n1;
k+1=n2+n1+n0;
将上面两式相减得到:n0=n2+1;
例如:已知767个节点的完全二叉树,求其叶子节点个数:

n0=n2+1;

n=n0+n1+n2;

由上面,消掉n2得到:n=2n0+n1-1;

由于完全二叉树度为1的只有0个或1个两种情况,所以,将0或1带入上面公式,整理后得:

n0=(n+1)/2或者n0=n/2;

看看n是否能被2整除,能则用n0=n/2。否则用n0=(n+1)/2

既叶子节点为n0=(n+1)/2=384

-----------------------------------------------------------------

再比如一棵二叉树有10个度为1的节点,7个度为2的节点,则二叉树有多少个节点(25)

根据刚才说的,节点数比度数多1,可以列出计算式子:

10 * 1 + 7 * 2 + 1 = 25

2.HTTP返回码的含义

HTTP协议状态码表示的意思主要分为五类 ,大体是 :  
~~~~~~~~~~~~~~~~~~~~~~~~~~~~  
1××   保留   
2××   表示请求成功地接收   
3××   为完成请求客户需进一步细化请求   
4××   客户错误       403?
5××   服务器错误   

100 Continue

指示客户端应该继续请求。回送用于通知客户端此次请求已经收到,并且没有被服务器拒绝。

客户端应该继续发送剩下的请求数据或者请求已经完成,或者忽略回送数据。服务器必须发送
最后的回送在请求之后。

101 Switching Protocols 
服务器依照客服端请求,通过Upgrade头信息,改变当前连接的应用协议。服务器将根据Upgrade头立刻改变协议
在101回送以空行结束的时候。

 Successful 

=================================
200 OK 
指示客服端的请求已经成功收到,解析,接受。

201 Created 
请求已经完成并一个新的返回资源被创建。被创建的资源可能是一个URI资源,通常URI资源在Location头指定。回送应该包含一个实体数据
并且包含资源特性以及location通过用户或者用户代理来选择合适的方法。实体数据格式通过煤体类型来指定即content-type头。最开始服务 器
必须创建指定的资源在返回201状态码之前。如果行为没有被立刻执行,服务器应该返回202。

202 Accepted 
请求已经被接受用来处理。但是处理并没有完成。请求可能或者根本没有遵照执行,因为处理实际执行过程中可能被拒绝。

203 Non-Authoritative Information

204 No Content 
服务器已经接受请求并且没必要返回实体数据,可能需要返回更新信息。回送可能包含新的或更新信息由entity-headers呈现。

205 Reset Content 
服务器已经接受请求并且用户代理应该重新设置文档视图。

206 Partial Content 
服务器已经接受请求GET请求资源的部分。请求必须包含一个Range头信息以指示获取范围可能必须包含If-Range头信息以成立请求条件。

Redirection 
==================================
300 Multiple Choices
请求资源符合任何一个呈现方式。

301 Moved Permanently 
请求的资源已经被赋予一个新的URI。

302 Found 
通过不同的URI请求资源的临时文件。
303 See Other

304 Not Modified 
如果客服端已经完成一个有条件的请求并且请求是允许的,但是这个文档并没有改变,服务器应该返回304状态码。304
状态码一定不能包含信息主体,从而通常通过一个头字段后的第一个空行结束。

305 Use Proxy
请求的资源必须通过代理(由Location字段指定)来访问。Location资源给出了代理的URI。

306 Unused

307 Temporary Redirect

 

Client Error 
=====================
400 Bad Request 
因为错误的语法导致服务器无法理解请求信息。

401 Unauthorized 
如果请求需要用户验证。回送应该包含一个WWW-Authenticate头字段用来指明请求资源的权限。

402 Payment Required 
保留状态码

403 Forbidden 
服务器接受请求,但是被拒绝处理。

404 Not Found 
服务器已经找到任何匹配Request-URI的资源。

405 Menthod Not Allowed 
Request-Line 请求的方法不被允许通过指定的URI。

406 Not Acceptable

407 Proxy Authentication Required

408 Reqeust Timeout 
客服端没有提交任何请求在服务器等待处理时间内。

409 Conflict

410 Gone

411 Length Required 
服务器拒绝接受请求在没有定义Content-Length字段的情况下。

412 Precondition Failed

413 Request Entity Too Large 
服务器拒绝处理请求因为请求数据超过服务器能够处理的范围。服务器可能关闭当前连接来阻止客服端继续请求。

414 Request-URI Too Long 
服务器拒绝服务当前请求因为URI的长度超过了服务器的解析范围。

415 Unsupported Media Type 
服务器拒绝服务当前请求因为请求数据格式并不被请求的资源支持。

416 Request Range Not Satisfialbe

417 Expectation Failed

 

Server Error 
===================================
500 Internal Server Error 
服务器遭遇异常阻止了当前请求的执行

501 Not Implemented 
服务器没有相应的执行动作来完成当前请求。

502 Bad Gateway

503 Service Unavailable 
因为临时文件超载导致服务器不能处理当前请求。

504 Gateway Timeout

505 Http Version Not Supported

 

 

原文地址:https://www.cnblogs.com/fuck1/p/5833813.html