数据结构第5章：树与二叉树
1 树的定义和基本概念树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界国是大量存在的，例如家谱、行政组织机构都可用树形象地表示。
树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程，等等。
1.1 树的定义定义：树(tree)是n(n>0)个结点的有限集T，其中：有且仅有一个特定的结点，称为树的根（root）。
当$n>1$时，其余结点可分为$m(m>0)$个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树（subtree）。
特点：
树中至少有一个结点——根
树中各子树是互不相交的集合
1.2 基本概念
结点(node)——指树中的一个数据元素，包括数据项及若干指向其子树的分支。一般用一个字母表示。
结点的度(degree)——结点拥有的子树数
叶子(leaf)——度为0的结点，也叫终端结点。
分支结点——除叶子结点外的所有结点，也k叫非终 ...
数据结构第6章：图
1 图的存储图的存储结构至少要保存两类信息：
顶点的数据
顶点间的关系
如何表示顶点间的关系？
1.1 邻接矩阵图的邻接矩阵(Adjacency Matrix) 存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。
设图 G 有 n 个顶点，则邻接矩阵 A 是一个$n ∗ n$的方阵，定义为:
下图是一个无向图和它的邻接矩阵：
可以看出：
无向图的邻接矩阵一定是一个对称矩阵(即从矩阵的左上角到右下角的主对角线为轴，右上角的元与左下角相对应的元全都是相等的)。 因此，在实际存储邻接矩阵时只需存储上(或下)三角矩阵的元素。
对于无向图，邻接矩阵的第i行(或第i列)非零元素(或非∞元素)的个数正好是第i个顶点的度。
有向图中：
顶点 $ V_{i} $ 的出度是A中第 i 行元素之和
顶点 $ V_{i} $ 的入度是A中第 i 列元素之和
邻接矩阵存储适用于稠密图。
1.2 邻接表当一个图为稀疏图时（边数相对顶点较少），使用邻接矩阵法显然要浪费大量的存储空间，如下图所示：
而图的邻接表法结合了顺序存储和链式 ...
数据结构第7章：查找
1 总览查找表：查找表是由同一类型的数据元素（或记录）构成的集合。由于“集合”中的数据元素之间存在着完全松散的关系，因此查找表是一种非常灵便的数据结构，可以用其他的数据结构来实现。
动态查找表：若在查找的同时对表做修改操作（插入删除等）则相应的表称之为动态查找表；否则称之为静态查找表。
平均查找长度ASL（查找算法的评价指标）：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度（Average Search Length）。
对查找表常进行的3种操作：
查询某个特定的值是否在表中
插入一个元素
删除一个元素
2 顺序查找和折半查找2.1 顺序查找算法思想：通过数组下标递增来顺序操作每个元素，返回结果。
优点：对数据存储结构没有任何要求。
缺点：平均查找长度$ASL=n$，效率较低。
2.2 折半查找折半查找是一种效率高效的查找方法，但是仅适用于有序的顺序表。
折半查找算法思路：（非递归）
设表长为n、low、high和mid分别指向待查元素所在区间的上界、下界和中点，key为给定的要查找的值。
初始时，令lo ...
计算机网络第2章：物理层
1 物理层的基本概念物理层考虑的是怎样才能在连接各种计算机的传输媒体上传输数据比特流，而不是指具体的传输媒体。
物理层的作用是要尽可能地屏蔽掉不同传输媒体和通信手段的差异。
用于物理层的协议也常称为物理层规程 (procedure)。
物理层的主要任务：确定与传输媒体的接口的一些特性。
机械特性：指明接口所用接线器的形状和尺寸、引线数目和排列、固定和锁定装置等。
电气特性：指明在接口电缆的各条线上出现的电压的范围。
功能特性：指明某条线上出现的某一电平的电压的意义。
过程特性 ：指明对于不同功能的各种可能事件的出现顺序。
2 数据通信的基础知识2.1 数据通信系统的模型一个数据通信系统包括三大部分：源系统（或发送端、发送方）、传输系统（或传输网络）和目的系统（或接收端、接收方）。
2.1.1 常用术语
数据 (data) —— 运送消息的实体。
信号(signal) —— 数据的电气的或电磁的表现。
模拟信号 (analogous signal) —— 代表消息的参数的取值是连续的。
数字信号 (digital signal) —— 代表消息的参数的取值是离散的。
码 ...
计算机网络第6章：应用层
每个应用层协议都是为了解决某一类应用问题，而问题的解决又往往是通过位于不同主机中的多个应用进程之间的通信和协同工作来完成的。应用层的具体内容就是规定应用进程在通信时所遵循的协议。
应用层的许多协议都是基于客户服务器方式。客户(client)和服务器(server)都是指通信中所涉及的两个应用进程。
客户服务器方式所描述的是进程之间服务和被服务的关系。客户是服务请求方，服务器是服务提供方。
1 域名系统 DNS1.1 域名系统概述域名系统 DNS (Domain Name System) ：
互联网使用的命名系统。
用来把人们使用的机器名字（域名）转换为 IP 地址。
为互联网的各种网络应用提供了核心服务。
互联网的域名系统DNS被设计称为一个联机分布式数据库系统，并采用客户服务器方式。DNS使大部分名字都在本地进行解析，仅少量解析需要在互联网上通信。
域名到 IP 地址的解析是由若干个域名服务器程序共同完成。
域名服务器程序在专设的结点上运行，运行该程序的机器称为域名服务器。
解析过程如下：当某一个应用进程需要把主机名解析为IP地址时，该应用进程就调用解析程 ...
计算机网络第5章：传输层
1 传输层协议概述1.1 进程之间的通信从通信和信息处理的角度看，运输层向它上面的应用层提供通信服务，它属于面向通信部分的最高层，同时也是用户功能中的最低层。
当网络的边缘部分中的两个主机使用网络的核心部分的功能进行端到端的通信时，只有位于网络边缘部分的主机的协议栈才有运输层，而网络核心部分中的路由器在转发分组时都只用到下三层的功能。
运输层为相互通信的应用进程提供了逻辑通信：
1.1.1 应用进程之间的通信
两个主机进行通信实际上就是两个主机中的应用进程互相通信。
应用进程之间的通信又称为端到端的通信。
运输层的一个很重要的功能就是复用和分用。应用层不同进程的报文通过不同的端口向下交到运输层，再往下就共用网络层提供的服务。
“运输层提供应用进程间的逻辑通信”。“逻辑通信”的意思是：运输层之间的通信好像是沿水平方向传送数据。但事实上这两个运输层之间并没有一条水平方向的物理连接。
运输层协议和网络层协议的主要区别：
在运输层有一个很重要的功能——复用和分用。
复用是指发送方不同的应用进程都可以使用同一个运输层协议传送数据
分用是指接收方的 ...
计算机网络第4章：网络层
1 网络层提供的两种服务在计算机网络领域，网络层应该向运输层提供怎样的服务（“面向连接”还是“无连接”）曾引起了长期的争论。
争论焦点的实质就是：在计算机通信中，可靠交付应当由谁来负责？是网络还是端系统？
1.1 观点1：面向连接，即让网络负责可靠交付建立虚电路（Virtual Circuit），以保证双方通信所需的一切网络资源。设计并使用可靠传输的网络协议，使源端所发送的分组实现通过虚电路无差错地按序地到达目的端。
1.1.1 虚电路服务
当在H1（源端）和H2（目的端）建立了虚电路后，H1 发送给 H2 的所有分组都沿着同一条虚电路传送，分组传输完毕后可以拆除该虚电路，也可长期保留。
虚电路表示这只是一条逻辑上的连接，分组都沿着这条逻辑连接按照存储转发（由中间路由器完成）方式传送，而并不是真正建立了一条物理连接。
请注意，电路交换是先建立了一条真正的连接。因此分组交换的虚连接和电路交换的连接只是类似，并不完全一样。
1.2 观点2：不面向连接，即不让网络负责可靠交付网络层向上（如传输层或调用IP协议的协议）只提供简单灵活的、无连接的、尽最大努力交付的数据报服务。
网络在发送分组时不 ...
计算机组成原理第3章：系统总线
1 总线的基本概念计算机系统的五大部件之间的互连方式有两种：
各部件之间使用单独的连线——分散连接
将各部件连到一组公共信息传输线上——总线连接
总线是连接各个部件的信息传输线，是各个部件共享的传输介质，同一时刻，只允许有一个部件向总线发送信息，而多个部件可以同时从总线上接受相同的信息。
这里有点像局域网的广播信道，同一时刻只能由一个主机发送数据，其他只能监听。
1.1 总线结构的计算机举例1.1.1 面向 CPU 的双总线结构框图
这种结构在I/O设备与主存交换信息时仍然要占用CPU，因此会影响CPU的工作效率。
1.1.2 单总线结构框图
当主存与I/O交换信息时，原则上不影响CPU的工作，CPU仍可继续处理不访问主存或I/O设备的操作，工作效率有所提升。
由于只有一组总线，当某一时刻各部件都要占用系统总线时，就会发生冲突。
1.1.3 以存储器为中心的双总线结构框图
在单总线基础上又开辟出一条CPU与主存之间的总线，称为存储总线，只供主存与CPU之间传输信息。既提高了传输效率，又减轻了系统总线的负担，还保证了IO设备与存储器交换信息时不经过C ...
数据库第10章：数据库恢复技术
1 事务的基本概念1.1 事务定义事务：是用户定义的一个数据库操作序列，这些操作要么全做，要么全不做，一个不可分割的工作单位。
事务和程序比较：
在关系数据库中，一个事务可以是一条或多条SQL语句，也可以包含一个或多个程序
一个程序通常包含多个事务
1.2 定义事务1.2.1 显式定义方式
COMMIT：表示提交，即提交事务的所有操作
ROLLBACK：表示回滚，将事务中对数据库的所有已完成的操作全部撤销，回滚到事务开始时的状态
12345BEGIN TRANSACTION BEGIN TRANSACTION SQL 语句1 SQL 语句1 SQL 语句2 SQL 语句2 。。。。。 。。。。。COMMIT ROLLBACK
1.2.2 隐式方式
当用户没有显式地定义事务时，DBMS按缺省规定自动划分事务。
1 ...
计算机网络第3章：数据链路层
1 使用点对点信道的数据链路层数据链路层使用的信道主要有以下两种类型：
点对点信道。这种信道使用一对一的点对点通信方式。
广播信道。这种信道使用一对多的广播通信方式，因此过程比较复杂。广播信道上连接的主机很多，因此必须使用专用的共享信道协议来协调这些主机的数据发送。
数据链路层的简单模型，主机 H1 向 H2 发送数据
1.1 数据链路和帧链路（link）是一条无源的点到点的物理线路段，中间没有任何其他的交换结点。
一条链路只是一条通路的一个组成部分
数据链路（data link）除了物理线路外，还必须有通信协议来控制这些数据的传输。若把实现这些协议的硬件和软件加到链路上，就构成了数据链路。
现在最常用的方法是使用适配器（即网卡）来实现这些协议的硬件和软件。
一般的适配器都包括了数据链路层和物理层这两层的功能。
2 数据链路层的 3H 问题
How to 封装成帧
How to 透明传输
How to 差错控制
2.1 封装成帧
封装成帧(framing)就是在一段数据的前后分别添加首部和尾部，然后就构成了一个帧。确定帧的界限。
首部和尾部的一个重要 ...
