笔试错题

  • 从尚未排序的N名学生的考试分数中挑出排名第K的分数，平均时间复杂度最优可以达到多少？

    • O(N) c(n) = o(n)+c(n/2), 使用递归树求，计算等比数列的和， a1=n; q = 1/2; n = log2n;

  • 1，2，3，4，5 五个数字，能组成多少种不同的二叉搜索树的结构？

    • 卡特兰数 笔试错题 - 图1%3Df(n-1)f(0)%2Bf(n-2)f(1)%2B…%2Bf(1)f(n-2)%2Bf(0)f(n-1)#card=math&code=f%28n%29%3Df%28n-1%29%2Af%280%29%2Bf%28n-2%29%2Af%281%29%2B…%2Bf%281%29%2Af%28n-2%29%2Bf%280%29%2Af%28n-1%29)
    • 笔试错题 - 图2%3Df(4)f(0)%2Bf(3)f(1)%2Bf(2)f(2)%2Bf(1)f(3)%2Bf(0)*f(4)#card=math&code=f%285%29%3Df%284%29%2Af%280%29%2Bf%283%29%2Af%281%29%2Bf%282%29%2Af%282%29%2Bf%281%29%2Af%283%29%2Bf%280%29%2Af%284%29)
    • 笔试错题 - 图3%20%3D%201#card=math&code=f%280%29%20%3D%201) 笔试错题 - 图4%3D%201#card=math&code=f%281%29%3D%201) 笔试错题 - 图5%3D2#card=math&code=f%282%29%3D2) 笔试错题 - 图6%3D5#card=math&code=f%283%29%3D5) 笔试错题 - 图7%3D14#card=math&code=f%284%29%3D14) 笔试错题 - 图8%3D42#card=math&code=f%285%29%3D42)
    • 可以看作是左右子树的个数的排列

  • 有向无环图不能转化为树，因为不能保证只有一个根（出度>1)

  • 栈或队列的均摊时间复杂度（最好情况时间复杂度）

    • 1个堆栈可以通过1个数组或者1个单向链表来实现，出栈和入栈的均摊复杂度均为O(1) 正确
    • 1个先进先出队列可以通过1个数组或者1个单向链表来实现，出队和入队的均摊复杂度均为O(1) 正确

    • 1个堆栈可以通过2个先进先出队列来实现, 出栈和入栈的均摊复杂度均为O(1) 错误

      • 每次都把新加的元素加入到空的队列A中，然后把满的队列B的所有元素倒入A中，此刻B空。O(n*n/n);

    • 1个先进先出队列可以通过2个堆栈来实现，出队和入队的均摊复杂度均为O(1) 正确 O((n+n)/n)

      • 第一次出队时，需要将第一个队列的所有元素放到第二个队列中。以后每次出队只需要放1个元素。

  • 虚拟内存的容量只受 (计算机地址位数) 的限制

  • MYSQL 唯一索引UNIQUE 的目的是为了避免数据出现重复，唯一索引可以有多个但索引列的值必须唯一，索引列的值允许有空值。如果能确定某个数据列将只包含彼此各不相同的值，在为这个数据列创建索引的时候就应该使用关键字UNIQUE。

  • 以下哪一项不能有效利用程序的局部性？

    • 顺序读取数据对象 （对，按照数据在存储器的顺序读，使空间局部性最大）
    • 将相关代码拆散到多个C文件中 （错误）
    • 精简程序binary的大小 （对）
    • 将主要的计算逻辑集中在内部循环并做优化 （对，将注意力集中在内部循环上，大部分计算与存储器访问都放在那里）

  • 2019! 的末尾有多少个零？

    • 一个2一个5相乘会在结尾得到一个0， 在阶乘当中，2比5多，所以每个5都肯定可以分配到一个2，所以只要数清楚一共有多少个5，就能数清楚有多少0.

  • A,B两台机器都正常工作,B机器未监听任何端口.如果A机器向B机器80端口发送SYN包,会收到何种类型的回包?

    • RST包用来强制关闭TCP链接。 什么时候发送RST包 1. 建立连接的SYN到达某端口，但是该端口上没有正在 监听的服务。 2. TCP收到了一个根本不存在的连接上的分节。 3. 请求超时。 使用setsockopt的SO_RCVTIMEO选项设置recv的超时时间。接收数据超时时，会发送RST包。

  • 各种攻击：

    • DNS欺骗攻击

      • DNS欺骗技术常见的有内应攻击和序列号攻击两种。内应攻击即黑客在掌控一台DNS Server后,对其Domain Database内容进行更改，将虚假IP Address指定给特定的Domain Name，当Client请求查询这个特定域名的IP时，将得到伪造的IP。
      • 序列号攻击是指伪装的DNS Server在真实的DNS Server之前向客户端发送应答数据报文，该报文中含有的序列号ID与客户端向真实的DNS Server发出请求数据包中含有的ID相同，因此客户端会接收该虚假报文，而丢弃晚到的真实报文，这样DNS ID序列号欺骗成功。客户机得到的虚假报文中提供的域名的IP是攻击者设定的IP，这个IP将把客户带到攻击者指定的站点。
    • DDoS攻击：Dos攻击叫拒绝服务攻击，如向一台服务器发送大量的IP数据报，使服务器要花很多时间处理所接收到的数据报，导致合法用户被拒绝服务。
    • SYN Flooding攻击；SYN Flooding攻击是通过伪造的IP地址，大量的向服务器发送SYN报文，服务器不断的申请资源建立控制块，从而大量占用资源直至资源耗尽，使正常请求服务变慢，或者完全停止服务；
    • 重放攻击：重复的会话请求就是重放攻击，可能是因为用户重复发起请求，也可能是因为请求被攻击者获取，然后重新发给服务器。

  • 死锁

    • 某台计算机连接了8个相同的设备，有N个进程在竞争使用，每个进程最多会同时占用3个设备，请问当N大于等于多少时，系统可能发生死锁？4

  • 当有3个进程时，1号和2号占用3个设备，3号占用2个，等待1号或2号执行完成之后，释放资源。3号可以获得设备。

    • 但有4个进程时，假如每个进程都先分配2个，若其中一个进程想要再申请设备，但其余进程都在占用着，故发生了死锁。

    • 避免方式

      • 预防死锁发生

      • 检测与拆除死锁（抢占剥夺，kill掉进程，回滚系统等）

      • 动态避免，在资源分配过程中，确保资源请求批准后系统不会进入死锁或潜在的死锁状态。

    • 银行家算法

      • 基本思想：分配资源之前，判断系统是否安全，如果安全才会进行资源分配。
      • 我们把操作系统看做是银行家，操作系统管理的资源相当于银行家的资金，线程向操作系统请求分配资源就是用户向银行家要贷款。

    • 在一个真实的计算机系统中，资源会损坏或被替换，新的进程会进入和离开系统，新的资源会被购买和添加到系统中。如果用银行家算法控制死锁，下面哪些变化是安全的（不会导致可能的死锁）？（BC ）

      • 增加可用资源（新的资源被添加到系统） 安全
      • 减少可用资源（资源被从系统中永久性地移出） 可能会影响系统，不安全
      • 增加一个进程的Max（进程需要更多的资源，超过所允许给予的资源） 可能会影响系统
      • 减少一个进程的Max（进程不再需要那么多资源）安全

    • 在一个真实的计算机系统中，可用的资源和进程命令对资源的要求都不会持续很久是一致的长期（几个月）。资源会损坏或被替换，新的进程会进入和离开系统，新的资源会被购买和添加到系统中。如果用银行家算法控制死锁，下面哪 些变化是安全的（不会导致可能的死锁）？（BC）

      • 增加可用资源（新的资源被添加到系统） 安全
      • 减少可用资源（资源被从系统中永久性地移出） 不安全
      • 增加一个进程的Max（进程需要更多的资源，超过所允许给予的资源）不安全
      • 减少一个进程的Max（进程不再需要那么多资源） 安全

  • MYSQL索引类型

    • 普通索引

      • 无限制，用于加速查询

    • 唯一索引 unique

      • 索引列的值必须唯一，但允许有空值。如果是组合索引，则列值的组合必须唯一。

    • 主键索引 PRIMARY

      • 是一种特殊的唯一索引，一个表只能有一个主键，不允许有空值。

    • 组合索引

      • 多个字段上创建的索引，只有在查询条件中使用了创建索引时的第一个字段，索引才会被使用。

    • 全文索引

      • 用来查找文本中的关键字，而不是直接与索引中的值相比较。

  • java语法

    • 接口的方法默认是 public abstract
    • 接口的变量默认是public static final
    • java设置守护线程在start之前，join在start之后。 t.join()表示将线程t加入到容器中，调用这句的线程如main()线程，则要等到t线程结束后，才能结束。

  • 贝叶斯+全概率公式

    • 某种产品中，合格品率为85%，一个合格品被检查成次品的概率是10%，一个次品被检查成合格品的概率为5%。问题：求一个被检查成合格品的产品确实为合格品的概率为（）

      • 设是合格品的事件为A=1, 被检查成合格品的事件为B=1,求P(A=1|B=1)

      • 根据贝叶斯定理: 笔试错题 - 图9%3D%5Cfrac%7BP(B%7CA)*P(A)%7D%7BP(B)%7D#card=math&code=P%28A%7CB%29%3D%5Cfrac%7BP%28B%7CA%29%2AP%28A%29%7D%7BP%28B%29%7D)

        • 笔试错题 - 图10%3D%5Cfrac%7BP(B%3D1%7CA%3D1)*P(A%3D1)%7D%7BP(B%3D1)%7D#card=math&code=P%28A%3D1%7CB%3D1%29%3D%5Cfrac%7BP%28B%3D1%7CA%3D1%29%2AP%28A%3D1%29%7D%7BP%28B%3D1%29%7D)
      • 已知笔试错题 - 图11%3D0.85#card=math&code=P%28A%3D1%29%3D0.85) 笔试错题 - 图12%3D1-P(B%3D0%7CA%3D1)%3D0.9#card=math&code=P%28B%3D1%7CA%3D1%29%3D1-P%28B%3D0%7CA%3D1%29%3D0.9) 笔试错题 - 图13%3D0.05#card=math&code=P%28B%3D1%7CA%3D0%29%3D0.05)
      • 全概率公式 笔试错题 - 图14%3D%5Csum%7Bi%3D1%7D%5En%7BP(A_i)*P(B%7CA_i)%7D#card=math&code=P%28B%29%3D%5Csum%7Bi%3D1%7D%5En%7BP%28A_i%29%2AP%28B%7CA_i%29%7D)
      • 笔试错题 - 图15%3DP(A%3D1)P(B%3D1%7CA%3D1)%2BP(A%3D0)P(B%3D1%7CA%3D0)%3D0.7725#card=math&code=P%28B%3D1%29%3DP%28A%3D1%29%2AP%28B%3D1%7CA%3D1%29%2BP%28A%3D0%29%2AP%28B%3D1%7CA%3D0%29%3D0.7725)

  • 派生类的对象不能访问基类的所有成员,(私有成员)

  • 一个有64MB物理内存的机器使用32位虚拟地址空间。假设内存页面大小为4KB，单个页表项的大小对齐到Byte，则整个页表的大小约为:(2MB)

    • 内存以Byte为一个单位，32位指的是2的32次方Byte, 虚拟地址32位，即4GB
    • 页面大小为4KB,即12位页内地址, 虚拟页号20位,可能有2的20次方个虚页.
    • 实际物理内存为64MB,页内地址为12位,则实页号为14位.
    • 实页号（14）位就是一个页表项，需要14bit空间存储一个页表项，又因为页表项大小对其到Byte，所以用2B存储一个页表项. 共有虚页数个页表项，即有2的20次方个页表项，则整个页表大小位2的20+1次方个B，即2MB

  • linux指令

    • cat 一次性将文件内容全部输出, more 可以分页查看 less使用光标向上或向下移动一行

  • 局域网的协议结构一般不包括网络层,只包含数据链路层和物理层.

  • 数据库

    • 数据库文件中主数据文件扩展名和次数据库文件扩展名分别为.mdf (primary data file)和.ndf (Secondary data files)
    • 一个数据库从逻辑上说是由一个或多个表空间所组成，表空间是数据库中物理编组的数据仓库，每一个表空间是由段(segment)组成，一个段是由一组区(extent)所组成，一个区是由一组连续的数据库块(database block)组成，而一个数据库块对应硬盘上的一个或多个物理块。一个表空间存放一个或多个数据库的物理文件（即数据文件）.一个数据库中的数据被逻辑地存储在表空间上
    • select count(*) from table 表示返回表中包括空行和重复行在内的行数,但是会扫描所有列
    • select count(1) from table 也是返回表中包括空行和重复行在内的行数，不会扫描所有列,1其实就是表示有多少个符合条件的行，但是此时没有where,所有没条件也就是返回总行数
    • drop是完全删除表，包括表结构
    1. delete是删除表数据，保留表的结构，而且可以加where,只删除一行或者多行
    2. truncate 只能删除表数据，会保留表结构，而且不能加where

  • 向一个有59个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动几个元素（） 29.5

    • 笔试错题 - 图16

  • 3的方幂及不相等的3的方幂的和排列成递增序列{1,3,4,9,10,12,13…}，则数列第100项是

    • 第1项 二进制为001，值为1=3^0
    • 第2项 二进制为010，值为3^1=3
    • 第3项二进制为011，值为30 = 9
    • 故第100项的二进制为1100100，将其转化为三进制数=981

  • 关系型数据库：是指采用了关系模型来组织数据的数据库，关系模型指的就是二维表格模型

    • 常见的关系型数据库：Oracle，SQL Server，Sybase，DB2，Access，MySql，VFP，INGRES

  • 非关系型数据库，以键值对进行存储，

    • 常见的非关系型数据库（NoSQL）:SQLite, Redis ,MongoDB ,Cassandra , Voldemort, CouchDB, LevelDB

  • 当一个线程抛出OOM异常后，它所占据的内存资源会被快速地释放掉，从而不会影响其它线程的运行。

  • try-catch-finally 带return的执行顺序

    • finally中的代码总会被执行。

      • try中调用了System.exit(0);时，finally代码块不会被执行。
      • try中写了无线循环时，finally代码块不会被执行。
    • 当try、catch中有return时，也会执行finally。return的时候，要注意返回值的类型，是否受到finally中代码的影响。
    • finally中有return时，会直接在finally中退出，导致try、catch中的return失效

  • >>和>>>的区别

    • >>带符号右移，最高位是1就补1，0就补0
    • >>>无符号右移，最高位补0

  • 关键路径的长度

    • AOE网：在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示活动的持续时间，称这样的有向图叫做边表示活动的网，简称AOE网。AOE网中没有入边的顶点称为始点（或源点），没有出边的顶点称为终点（或汇点）。
    • 关键路径：在AOE网中，从始点到终点具有最大路径长度（该路径上的各个活动所持续的时间之和）的路径称为关键路径。

  • 树

    • 双亲结点：一个结点的直接前驱称为该结点的双亲结点
    • 兄弟结点：同一双亲结点的孩子结点间互称兄弟结点
    • 堂兄结点：父亲是兄弟关系或堂兄弟关系的堂兄弟结点
    • 祖先结点：一个结点的祖先结点是指从根结点到该结点的路径上的所有结点
    • 子孙结点：一个结点的直接后继和间接后继称为该节点的子孙结点
    • 前辈：层号比该结点小的结点
    • 后辈：层号比该结点大的结点

  • 后缀表达式

    • 中缀表达式转后缀表达式（逆波兰表达式）

      • 堆栈为空，直接将操作符存储到堆栈中。
      • 若要进栈的操作符优先级高于栈顶操作符或遇到左括号，则入栈。
      • 若要进栈的操作符优先级低于栈顶操作符或遇到右括号，则弹出栈顶元素，直到不满足条件或遇到左括号，再将该操作符压入栈。

    • 后缀表达式的计算求值

      • 从左往右扫描表达式，遇到数字时，将数字压入堆栈
      • 遇到运算符时，弹出栈顶的两个数，计算。
      • 并将结果入栈，重复上述过程直到表达式最右端
      • 最后结果即为计算结果

  • linux权限

    • 7 5 4 对应3种用户的权限：文件所有者，同组用户、其他用户；

      • 7=4+2+1 文件所有者对该文件的的权限为可读可写可执行
      • 5 = 4+1 同组用户对该文件的权限为可读可执行
      • 4 = 4 其他用户对该文件的权限为可读。
    • 权限 权限数值 具体作用
      r 4 read，读取。当前用户可以读取文件内容，当前用户可以浏览目录。
      w 2 write，写入。当前用户可以新增或修改文件内容，当前用户可以删除、移动目录或目录内文件。
      x 1 execute，执行。当前用户可以执行文件，当前用户可以进入目录。

  • linux awk命令

    • awk是行处理器，通常用来格式化文本信息，在处理庞大文件时不会出现内存溢出或是处理缓慢的问题。
    • 笔试错题 - 图17
    • 注意，NF 和 NF 要表达的意思是不一样的，对于awk来说，NF表示最后一个字段，NF表示当前行被分隔符切开以后的列数。

  • 设计模式：

    • 创建型模式：工厂模式，工厂方法模式，单例模式，建造者模式，原型模式。
    • 结构型模式：适配器模式、装饰器模式、代理模式、外观模式、组合模式、享元模式。
    • 行为模式：策略模式、模板方法模式、观察者模式、迭代子模式、责任链模式、命令模式、备忘录模式、状态模式、访问者模式、中介者模式、解释器模式。
    • 创建者模式关注如何创建对象。
    • 结构型模式关注如何将现有类或对象组织在一起形成更加强大的结构。
    • 行为模式，关注系统中对象之间的相互交互，研究系统在运行时对象之间的相互通信和协作，进一步明确对象的职责。

  • 顺序存储结构的优缺点

    • 存储密度大，存储空间利用率高
    • 插入或删除元素时不方便，需要移动元素。

  • 链式存储结构的优缺点

    • 插入或删除元素时方便
    • 存储密度小，存储空间利用率低。

  • 排序算法

    • 笔试错题 - 图18
    • 稳定性：在每趟排序中，基本不会改变元素的大小相对位置，称为稳定的。否则不稳定。

    • 冒泡排序

      • 两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录位置。
      • 每趟排序后会有一个最值浮现出来。
      • 是稳定的排序
      • 时间复杂度笔试错题 - 图19#card=math&code=O%28n%5E2%29)

    • 简单选择排序

      • 每一趟在笔试错题 - 图20个记录中选取出关键字最小的记录作为有序序列的第i个记录。
      • 是不稳定的排序
      • 时间复杂度笔试错题 - 图21#card=math&code=O%28n%5E2%29)

    • 直接插入排序

      • 将一个记录插入到已经排好序的有序表中，从而得到一个新的，记录数+1的有序表。
      • 是稳定的排序
      • 时间复杂度笔试错题 - 图22#card=math&code=O%28n%5E2%29)

    • 希尔排序

      • 对直接插入排序算法的改进。
      • 选择一个合适的增量，将相隔某个增量的记录组成一个子序列，使子序列有序。
      • 减少增量，继续排序子序列，直到增量减少为1.
      • 是一种非稳定的排序算法
      • 时间复杂度为笔试错题 - 图23#card=math&code=O%28n%5E%7B%5Cfrac%7B3%7D%7B2%7D%7D%29)

    • 堆排序

      • 对简单选择排序算法的改进。
      • 构建大根堆
      • 将堆顶元素与最后一个元素交换，调整大根堆，直到所有元素有序。
      • 不稳定的排序算法
      • 时间复杂度为笔试错题 - 图24#card=math&code=O%28nlogn%29)

    • 归并排序

      • 2路归并，类似完全二叉树
      • 将序列长度为n的记录分为两部分，分别对左右部分进行归并排序，再对两部分进行跨区间排序，一直递归到子序列长度为1，最后得到有序序列。
      • 在进行跨区间排序的时候，需要借助辅助数组。
      • 是一种比较占用内存，效率高且稳定的算法。
      • 时间复杂度为笔试错题 - 图25

    • 快速排序

      • 对冒泡排序的改进

      • 基本思想：

        • 通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，可分别对这两部分记录继续进行排序，已达到整个序列有序。

    • 是一种不稳定的排序算法。

      • 最优时间复杂度为笔试错题 - 图26#card=math&code=O%28nlogn%29),最坏的时间复杂度，当待排序的数组有序时，每次划分只是比上次少一个记录，故退化为笔试错题 - 图27#card=math&code=O%28n%5E2%29)

  • 堆排序

    • 堆是具有以下性质的完全二叉树，每个节点的值都大于或等于其左右孩子节点的值，成为大根堆。每个节点的值都小于或等于其左右孩子的值，成为小根堆。

    • 原理：

      • 将带排序的序列构造成一个大顶堆，此时整个序列的最大值就是堆顶的根节点，将其与末尾元素进行交换，然后将剩余的n-1个序列重新构造成一个大根堆，这样就会得到次大值，如此反复执行，就能得到一个有序序列了。

    • 堆调整：

      • 先将所有节点构建成完全二叉树。
      • 从下标为n/2的节点到第一个节点循环，调整堆。（因为它们都有孩子节点）
      • 若该节点的值小于孩子节点的值，那么进行交换。循环进行，直到节点下标超过n

  • 汉诺塔

    • 递推公式 笔试错题 - 图28%3D2(fn-1)%2B1#card=math&code=f%28n%29%3D2%28fn-1%29%2B1),相当于a,b,c三个柱子，先把a上的n-1个移动到b,需f(n-1)次，然后移动1个到c，需1次,最后将b的n-1个移动到c,需f(n-1)次。
    • 笔试错题 - 图29%3D2%5En-1#card=math&code=f%28n%29%3D2%5En-1)

  • 二次探测法：

    • 设发生冲突的地址为d,则新的地址序列为 笔试错题 - 图30

  • 广义表

    • 广义表(Lists，又称列表)是一种非线性的数据结构，是线性表的一种推广。即广义表中放松对表元素的原子限制，容许它们具有其自身结构（即可以有子表）。
    • 表的深度：表展开后所含括号的层数；
    • 表的长度：长度为第一层的元素个数（原子和子表都只算一个）；
    • head() 返回列表的第一个元素；
    • tail() 返回列表的删去第一个元素之后的剩余列表；

  • 平衡二叉树 AVL树

    • 是一种二叉排序树，其中每个节点的左子树和右子树的高度差至多为1.
    • 节点的左子树深度减去右子树深度的值成为平衡因子BF。
    • 距离插入节点最近的，且平衡因子的绝对值>1的结点为根的子树称为最小不平衡子树。
    • BF>1，需要对最小不平衡子树进行右旋。BF<-1,需要对最小不平衡子树进行左旋。
    • 若最小不平衡子树的BF正负不一致，需要先将其旋转为正负号一致，然后再进行旋转。

  • 跳跃表

    • 笔试错题 - 图31

    • 特点：
      (1) 由很多层结构组成
      (2) 每一层都是一个有序的链表
      (3) 最底层(Level 1)的链表包含所有元素
      (4) 如果一个元素出现在 Level i 的链表中，则它在 Level i 之下的链表也都会出现。
      (5) 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。

  • 红黑树

    • 红黑树其实就是一种数据结构，设计它的目的就是为了高效地进行增删改查。

    • 在大量查找的情况下，平衡二叉树的效率更高，也是首要选择。在大量增删的情况下，红黑树是首选。

    • 笔试错题 - 图32

    • 特征：
      （1）每个节点只有两种颜色：红色和黑色。
      （2）根节点是黑色的。
      （3）每个叶子节点（NIL）都是黑色的空节点。
      （4）从根节点到叶子节点，不会出现两个连续的红色节点。
      （5）从任何一个节点出发，到叶子节点，这条路径上都有相同数目的黑色节点。

    • 查询结点跟AVL树是一样的

    • 插入结点：

      • 将新插入的节点标记为红色

      • 如果 X 是根结点(root)，则标记为黑色

      • 如果 X 的 parent 不是黑色，同时 X 也不是 root:

      • 3.1 如果 X 的 uncle (叔叔) 是红色

        • 3.1.1 将 parent 和 uncle 标记为黑色
        • 3.1.2 将 grand parent (祖父) 标记为红色
        • 3.1.3 让 X 节点的颜色与 X 祖父的颜色相同，然后重复步骤 2、3
      • 未完待续…

  • 多路查找树B树

    • 每个结点的孩子数可以多于两个，且每个结点处可以存储多个元素。

    • 4种形式：2-3树、2-3-4树、B树和B+树

    • 2-3树：

      • 每个结点都具有两个孩子（2结点）或3个孩子（3结点）。
      • 一个2结点包含1个元素和两个孩子（或没有孩子），左子树包含的元素小于该元素，右子树包含的元素大于该元素。
      • 一个3结点包含一小一大两个元素和三个孩子（或没有孩子），1个3结点要么没有孩子，要么具有三个孩子。若某个3结点有孩子的话，左子树包含小于较小元素的元素，右子树包含大于较大元素的元素，中间子树包含介于两元素之间的元素。
      • 2-3树的所有叶子结点都在同一层次上。

    • B树(B-树)

      • 是一种平衡的多路查找树，2-3树和2-3-4树都是B树的特例，结点最大的孩子数目成为B树的阶；2-3树是3阶B树，2-3-4树是4阶B树。

      • m阶的B树必须满足如下条件：

        • 每个结点至多有m个子结点；
        • 除根结点和叶结点外，其它每个结点至少有笔试错题 - 图33个子结点；
        • 根结点至少有两个子结点；（唯一例外的是根结点就是叶子结点）
        • 所有的叶结点在同一层；
        • 有k个子结点的非根结点恰好包含k-1个关键码，关键码按照递增次序进行排列。
      • 笔试错题 - 图34
      • B树的插入过程

    • B+树

      • 一棵m阶的B+树和m阶的B树差异在于：

        • 有k个子树的中间节点包含有k个元素，每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
        • 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
        • 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素

      • 笔试错题 - 图35

      • B+树的另外一个重要特点是卫星数据。所谓卫星数据，指的就是索引元素所指向的数据记录，比如数据库中的某一行。在B-树中，无论是中间节点还是叶子结点都带有卫星数据，而在B+树当中，只有叶子节点带有卫星数据，其余中间节点仅仅是索引，没有任何数据关联。
        笔试错题 - 图36

        • B+树的优势：
          　　　　1.单一节点存储更多的元素，使得查询的IO次数更少。
          　　　　2.所有查询都要查找到叶子节点，查询性能稳定。
          　　　　3.所有叶子节点形成有序链表，便于范围查询,远远高于B-树

  • Telnet协议是TCP/IP协议族中的一员，是Internet远程登录服务的标准协议和主要方式。

  • 某计算机字长32位，其存储容量为4MB，若按半字编址，它的寻址范围是

    • 笔试错题 - 图37
    • 笔试错题 - 图38

  • 由于CPU内部的操作速度较快，而CPU访问一次主存所花的时间较长，因此机器周期通常用( 主存中读取一个指令字的最短时间)来规定。

  • 通信信道带宽为1Gb／s，端到端时延为10ms。TCP的发送窗口为65535字节。试问:可能达到的最大吞吐量是多少?信道的利用率是多少?

    • 吞吐量= 数据包总长度/往返时延

    • 笔试错题 - 图39ms%3D25.5Mb%2Fs#card=math&code=%E5%90%9E%E5%90%90%E9%87%8F%3D65535%2A8%2F%282%2A10%29ms%3D25.5Mb%2Fs)

    • 笔试错题 - 图40

  • SMTP协议和POP3协议

    • 简单邮件传送协议SMTP 发件人->发送方服务器->接收方服务器。
    • 邮件读取协议POP3 接收方服务器->收件人。

  • 已知Cache的容量为4MB，分为4块，每块1MB，读写时间为3ns，主存的容量为512MB，读写时间为30ns。若平均读写时间为3.54ns，则Cache的命中率为：

    • 设cache命中率为x;
    • 平均读写时间=cache命中+cache不命中=笔试错题 - 图41*30%3D3.54#card=math&code=x%2A3%2B%281-x%29%2A30%3D3.54)

  • 一个机器人玩抛硬币的游戏，一直不停的抛一枚不均匀的硬币，硬币有A,B两面，A面的概率为3/4，B面的概率为1/4。问第一次出现连续的两个A年的时候，机器人抛硬币的次数的期望是多少？28/9

    • 笔试错题 - 图42

    • 笔试错题 - 图43#card=math&code=T%28s%29)表示从状态s到状态AA的期望步数
      笔试错题 - 图44

  • 小a和小b一起玩一个游戏，两个人一起抛掷一枚硬币，正面为H，反面为T。两个人把抛到的结果写成一个序列。如果出现HHT则小a获胜，游戏结束。如果HTT出现则小b获胜。小a想问一下他获胜的概率是多少？

    • 第一步分析法

    • 笔试错题 - 图45

    • PNill = 1/2_P_Nill + 1/2_P_H
      P_H = 1/2_P_HH + 1/2       P_HT
      P_HH = 1/2_P_HH + 1/2_P_HHT
      P_HT = 1/2_P_H + 1/2_P_HTT
      p_HHT = 1
      P_HTT = 0
      最后可以解得 P_Nill = 2/3。

  • 下列叙述中，有关线性链表叙述正确的是（）

    • 线性链表中的表头元素一定存储在其他元素的前面 （错误，循环链表）

    • 线性链表中的各元素在存储空间中的位置不一定是连续的，但表头元素一定存储在其他元素的前面 （错误，循环链表）

    • 线性链表中的各元素在存储空间中的位置必须是连续的 （错误，不连续）

    • 线性链表中的各元素在存储空间中的位置不一定是连续的，且各元素的存储顺序也是任意的

  • 串的朴素模式匹配算法，最坏情况的时间复杂度：笔试错题 - 图46*m#card=math&code=%28n-m%2B1%29%2Am)

    • 每次匹配到字串的最后一位，匹配次数为m次。
    • 匹配到主串的尾部，匹配次数为n-m+1次。

  • linux用户权限：

    • r:4 w:2 x:1
    • 笔试错题 - 图47
    • 笔试错题 - 图48

  • 合法的shell头：

    • -/bin/bash

    • !/bin/bash

  • 笔试错题 - 图49

  • redis集群使用数据分片引入哈希槽(hash slot)来实现

  • threadlocal 使用开放地址法 - 线性探测法：当前哈希槽有其他对象占了，顺着数组索引寻找下一个，直到找到为止

  • hashset 中调用 hashmap 来存储数据的，hashmap 采用的链地址法：当哈希槽中有其他对象了，使用链表的方式连接到那个对象上

  • try中执行完return的语句后，不返回，执行finally块，finally块执行结束后，返回到try块中，返回try块中最后return的值

  • ArrayList的初始容量为10，每次扩容为原来的1.5倍。

  • 计算主机号： IP地址 &（子网掩码取反）

  • 字符串“baiducdn”有多少个不同的排列？

    • 字符串个数：8 重复字符个数2
    • A(8,8)/A(2,2)

  • linux是如何避免外碎片的？

    • 伙伴系统，两个内存碎片大小一样，记作b，物理地址连续，第一块的第一个页框的物理地址是2×b×2^12的倍数。
    • 把所有的空闲页框分组为11个块链表，每个链表分别包含大小为1,2,4,8,16,32,64,128,256,512,1024个连续的页框，对1024个页框的最大请求对应着4MB大小的连续RAM（每页大小为4KB），每个块的第一个页框的物理地址是该块大小的整数倍，例如，大小为16个页框的块，其起始地址是16*2^12的倍数。

    • 假设现在要请求一个256个页框的块（1MB），算法步骤如下：

      • 在256个页框的链表中检查是否有一个空闲快，如果没有，查找下一个更大的块，如果有，请求满足。
      • 在512个页框的链表中检查是否有一个空闲块，如果有，把512个页框的空闲块分为两份，第一份用于满足请求，第二份链接到256个页框的链表中。如果没有空闲块，继续寻找下一个更大的块。

  • 两个人玩抛硬币的游戏，谁先抛到正面就获胜。那么先抛的人获胜概率为（2/3）。

  • 一棵完全二叉树共有2018个结点，则叶子结点的个数是？

    • 完全二叉树某一层的节点数目是 2^(h-1)
    • 满完全二叉树的所有结点数目= 2^h-1
    • 由题意可知该二叉树有10层是满的，结点总数为2^10-1 = 1023个结点
    • 第11层结点个数为 2018-1023 = 995个
    • 对应到第10层的结点个数有 995/2=498个，而第10层一共有512个结点，所以多余的14个可以看作叶子节点。
    • 总的叶子结点数目=995+14 = 1009

  • 袋子里面有4枚硬币，其中有1枚不均衡的硬币，其正反面朝上的概率分别为1/4, 3/4，剩下的3枚为均衡硬币，正反面朝上的概率都为1/2，现在从袋子里面随机选取一枚硬币，连续抛2次，结果2次都是正面朝上，请问刚才随机选取到的硬币为不均衡硬币的概率是多少？

    • 贝叶斯公式，找准事件
    • 设事件A为一个硬币两次正面朝上， 事件B是选出的硬币是不均衡硬币。求P(B|A)
    • 由贝叶斯公式可以得出：
    • 笔试错题 - 图50%3D%5Cfrac%7BP(A%7CB)P(B)%7D%7BP(A)%7D#card=math&code=P%28B%7CA%29%3D%5Cfrac%7BP%28A%7CB%29P%28B%29%7D%7BP%28A%29%7D)
    • P(B) = 1/4 P(A|B) = 1/16
    • 笔试错题 - 图51%20%3D%20P(B)P(A%7CB)%2BP(%5Chat%7BB%7D)P(A%7C%5Chat%7BB%7D)#card=math&code=P%28A%29%20%3D%20P%28B%29%2AP%28A%7CB%29%2BP%28%5Chat%7BB%7D%29%2AP%28A%7C%5Chat%7BB%7D%29)=13/64

  • 求x1+x2+x3+x4=7的非负整数解的个数

    • 由于解中可能存在0，所以假设提前有4个篮子，每个篮子是0.

    • 然后题目等于把7个内容为1的篮子和4个内容为0的篮子，用隔板法求划分成4部分的可能性。

      • 故放法是 C(10,3) = 120