人行笔试题知识点汇总.docx

1、 死锁所谓死锁: 是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。死锁必要条件：（1） 互斥条件：指进程对所分配到的资源进行排他性使用，即在一段时间内某资源只由一个进程使用（2） 请求和保持条件：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不妨。（3） 不剥夺条件：指进程已获得的资源，在未使用完之前，不能剥夺，只能在使用完时由自己释放（4） 环路等待条件：指在发生死锁时，必然存在一个进程资源的环形链处理死锁的基本方法：（1） 预防死锁：通过设置某些限制条件，去破坏产生死锁的几个必要条件中的一个或者几个优点：易于实现缺点：条件过于严格，导致系统资源利用率低和系统吞吐量低方法：有序资源分配法（2） 避免死锁：在资源的动态分配过程中，用某种方法防止系统进入不安全状态经典算法：银行家算法（3） 检测死锁：允许系统死锁，但是能够检测出与死锁相关的进程和资源，并采取措施解除死锁（4） 解除死锁：和检测死锁配套使用，撤销或者挂起一些进程，以便回收一些资源，再将这些资源分配给处于阻塞状态的进程，使之能够继续运行优点：有较好的系统资源利用率和系统吞吐量缺点：实现难度较大2、 后缀表达式不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行。常用于计算机进行表达式计算中。例如：a+b*c-(d+e)这样的表达式，后缀表达式为abc*+de+-3、 计算机网络的拓扑结构物理层：数据单位是bit数据链路层：在不可靠的物理介质上提供可靠的传输，作用包括：物理地址寻址，数据的成帧，流量控制，数据的检错，重发等。协议包括：HDLC、帧中继等网络层：将网络地址翻译成对应的物理地址，并决定数据的路由，只有当两个计算机系统处于不同的由路由器分割开的网段这种情况才会用。路由协议包括：IP传输层：流量控制和发送速率，以及按照网络能处理的最大尺寸将较长的数据包进行强制分割。数据单位是包。协议包括：TCP。会话层：建立通信链接，保持会话过程通信链接的长痛，同步两个节点之间的对话，决定通信是否被中断以及通信中断时决定从何处重新发送。表示层：应用程序和网络之间的翻译，将数据按照网络能理解的方案进行格式化，例如管理数据的解密和加密，对图片和文件格式信息进行解码和编码。应用层：主要负责对软件提供接口以使程序能使用网络服务，并不是指运行在网络上的某个特别应用程序。通信子网：由用作信息交换的节点计算机NC和通信线路组成的独立的通信系统，它承担全网的数据传输、转接、加工和交换等通信处 理工作。对应底三层。资源子网：包括计算机、终端、通信子网接口设备、外部设备及各种软件资源等，它负责全网的数据处理和向网络用户提供网络资源及网络服务。对应上三层。星型网络：特点：结构简单，建网容易，便于控制和管理缺点：中央节点负担重，容易形成系统瓶颈，线路利用率不高环形网络：只能一个方向传播，每个节点需要安装中继器，以接收、放大、发送信号特点：结构简单，建网容易，便于管理缺点：节点过多时，影响传输效率，不利于扩充总线型网络：特点：结构简单灵活，建网容易，使用方便，性能好缺点：主干总线对网络起决定性作用树形网络：每条通路都是双向特点：扩充方便、灵活，成本低，易推广，适合分主次或者分等级的层次型管理系统4、 网络互联设备物理层：（1） 中继器：一个以太网中最多有4个，仅用于相同的网络段，作用主要是延长网络的传输距离（2） 集线器：无源集线器只负责把多段介质连接在一起，不对信号做任何处理；有源集线器可以对信号进行再生和放大；智能集线器除上述功能外，还能进行网络管理、选择网络传输线路等。数据链路层：（1） 网桥：将同一个网络号的网络划分成不同的网络段，对源地址和目的地址不在同一个网络段的数据帧进行转发，相同则不转发。作用是使得段间的通信量最小，缓解网络通信繁忙的程度，并且隔离了不同的网络段使得它们之间不能互相影响，提高网络的可靠性。（2） 交换机：工作过程如下，三种交换技术：端口交换，帧交换和信元交换。网络层：（1） 路由器：用于连接多个逻辑上分开的网络。单协议路由器是针对互联网络的第三层协议相同使用，多协议路由器是针对互联网络的第三层协议不同使用。作用是：路径选择，过滤，存储和转发，流量控制和介质转换等。应用层：（1） 网关：当连接不同类型而协议差别又较大的网络时，需要使用网关。5、 局域网IEEE802局域网标准中，只有物理层和数据链路层两层，而数据链路层又被分为逻辑链路控制子层（LLC）和介质访问控制子层(MAC)，所以原ISO/OSI中网络层的部分功能放在了LLC中实现。MAC：主要是控制对传输介质的访问LLC：两种控制类型，即面向连接服务和非连接服务，主要功能是寻址，数据帧的封装和拆除，差错控制和流量控制等。6、 内部排序（1） 直接插入排序：最坏情况下，总比较次数i=2ni=n+2(n-1)2，总移动次数i=2ni+1=n+3(n-2)2，时间复杂度O(n2)，空间复杂度O(1)具体做法：在插入第i个记录时，前i-1个记录已经有序，这时将Ri依次与前i-1个进行比较，从而找到插入位置，并将其插入，插入位置及其后的记录依次向后移动（2） 冒泡排序：时间复杂度为O(n2)，空间复杂度为O(1)，因为只有移动数据时需要辅助内存具体做法：第一趟：第一个记录和第二个记录比较，若为逆序，则交换这两个记录，再比较第二个和第三个记录，依次类推，直至第n-1个记录和第n个记录比较过为止，这样，最大的记录就被放到第n个位置上。依次最多进行n-1趟即可排号序，如果在某一趟过程中，没有交换元素，就可以直接终止。（3） 简单选择排序：时间复杂度O(n)，空间复杂度O(1)具体做法：第一次比较：从n个记录中找到最小的记录，然后将第一个记录和其交换，第二次比较：从n-1个记录中找到最小的记录，然后将第二个记录和其交换，依次类推，第i次比较：从n-1+1个记录中找到最小的记录，然后将第i个记录和其交换（4） 快速排序：不是稳定的排序方法，时间复杂度为O(nlogn)，空间复杂度为O(logn)，若初始记录逆序或基本有序时，快速排序退化为冒泡排序基本思想：通过一趟排序将待排的记录分割为两个独立的部分，其中一部分的记录均不大于另一部分的记录，然后分别对两部分进行排序具体做法：附设两个指针low和high，初始指向第一个记录和最后一个记录，设枢纽记录pivotkey为low所指的记录，首先high从后向前搜索，找到第一个比pivotkey小的记录然后与pivotkey进行交换，然后，low从前向后搜索，直到找到第一个比pivotkey大的记录然后与pivotkey交换，直至low等于high为止。递归对分成的两个部分继续上述过程。（5） 归并排序：时间复杂度为O(nlogn)，空间复杂度为O(n)具体做法：把一个有n个记录的无序文件看成是由n个长度为1的有序子文件组成的文件，然后两两归并，得到n2个长度为2或1的有序文件，再两两归并，如此重复，直至最后形成包含n个记录的有序文件为止。（6） 堆排序：不稳定的排序方法，时间复杂度O(nlogn)，空间复杂度一个记录的大小，对大记录量有较有效基本思想：对一个待排序的数组（按照数组的顺序排成的堆），首先按照大顶堆的定义排成一个堆，从而输出堆顶的最大关键字，然后再把剩下的数据建成一个堆，可以得到次大的关键字。如果用链表作为存储结构，那么快速排序和堆排序就不适用了。7、 外部排序常用的是归并排序方法，一般分为两个阶段：第一阶段：将外存中的一部分数据读入内存，利用某种内部排序的方法对其进行排序，然后输出到外存中第二阶段：将第一个阶段形成的有序的记录段使用某种归并方法进行一趟一趟的归并，直至整个文件都有序为止K路平衡归并：用于第二阶段，K表示的是有几个归并段，以下两个方法都是以8路归并为例。树形选择排序：胜者树和败者树胜者树：两两比较取出较小者，然后再在较小者中两两比较，依次下推，直至得到最小者。树中节点是记录。 取出2后，调整树得到败者树：用数组ls表示，lsi的值为败者所在归并段的段号，ls1是树根节点，ls0是ls1的父节点，也是选出的优胜者所在归并段的段号，优胜者就是ls0所指示的归并段的当前记录。树中节点是段号。0和1比，失败的是1，2和3比，失败的是2，0和3将进入更上一层的比较 删除b4中的2后，b4当前的记录是10，10和bls6（5）比较，优胜者还是b4，失败者是b5，所以父节点ls6为5；优胜者b4和上一层中的bls3(就是b6)当前记录相比，优胜者是b6，失败者是b4，所以ls3改为4，b6参与再上一层的比较；同样，b6当前记录和bls1（就是b0）当前记录比较，优胜者是b6，所以ls0就是6，次小者是b6，即3。 优胜者所在的归并段的段号就是所有段号中除了ls1到ls7之外的剩下的段号。两者比较：败者树比较胜者树更加容易实现，因为每次调整树的时候只需要和父节点 比较，而不用和兄弟节点比较，并且改动的节点数目较少。8、 动态查找表特点：表结构本身是在查找过程中动态生成的（1） 二叉排序树：递归定义如下它的左子树非空，则左子树上所有节点的值均小于根节点的值；它的右子树非空，则右子树上所有节点的值均大于根节点的值；查找过程省略；插入节点的操作：若树为空，则作为根节点；若树不空，则将该节点和根比较，小于 则插入左子树，大于则插入右子树；树的形态完全由输入序列决定。删除节点的操作：待删除节点为*p若*p是叶子节点若*p只有左子树或者只有右子树若*p既有左子树又有右子树，如下图（2） 平衡二叉树通过以上发现，二叉排序树只有在平衡时才能达到查找的最佳效果，平衡的的定义是左子树和右子树都是平衡二叉树，且左子树与右子树的高度的绝对值不能超过1（平衡因子）。最小不平衡子树是指离插入节点最近且平衡因子大于1的节点作为根的子树。平衡二叉树的插入操作：设*a表示最小不平衡子树的根节点1） 若在*a的左子树的左子树插入了新节点，使得*a的平衡因子由1变为2，则需要进行单向右旋2） 若在*a的右子树的右子树插入了新节点，使得*a的平衡因子由-1变为-2，需要进行单向左旋3） 若在*a的左子树的右子树插入了一个节点，使得*a的平衡因子由1变为2，则需要进行先左后右的双向旋转4） 若在*a的右子树的左子树插入了一个节点，使得*a的平衡因子由-1变为-2，则需要进行先右后左的双向旋转（3） B树一棵m阶B树，或为空树，或为满足下列性质的m叉树：1） 树中每个节