多传感器信息融合技术课程总结

 2120101050

       通过学习“多传感器信息融合技术”这门课程，不仅学到了有关数据融合技术的各种方法，例如：贝叶斯推理、卡尔曼滤波、D-S方法、模糊数学、人工神经网络、遗传算法，而且还学到了许多其他方面的知识，可以说是受益匪浅。戴老师渊博的学识，和对学问一丝不苟的态度给我留下了深刻的印象，永远是我们学习的榜样。

多传感器数据融合在地球资源监测，天气预报，交通管理及军事目标的分类与跟踪等方面有着广泛的应用。数据融合是一个多级，多层面的数据处理过程，主要完成对来自多个信息源的数据进行自动检测，关联，相关，估计及组合等的处理。

现总结如下：

1.      贝叶斯方法

贝叶斯推理是一种统计融合算法，它主要是基于贝叶斯法则来进行推理的，和其他需要先验知识的算法一样，该方法也需要观测空间的先验知识，从而实现对观测空间里的物体的识别。在给定证据的条件下，贝叶斯推理能提供一种计算条件概率即后验概率的方法。

：在给定证据的情况下，假设事件发生的后验概率；

：在假设事件发生的条件下，证据出现的概率（有时也被称为假设事件的似然函数）；

：假设事件发生的先验概率，且有；

：出现E证据的全概率，即在各假设事件Hj都可能发生的情况下，证据E出现的概率和。

2.      卡尔曼滤波方法

卡尔曼全名Rudolf Emil Kalman，匈牙利数学家，1930年出生于匈牙利首都布达佩斯。1953，1954年于麻省理工学院分别获得电机工程学士及硕士学位。1957年于哥伦比亚大学获得博士学位。我们现在要学习的卡尔曼滤波器，正是源于他的博士论文和1960年发表的论文《A New Approach to Linear Filtering and Prediction Problems》（线性滤波与预测问题的新方法）。

       简单来说，卡尔曼滤波器是一个“optimal recursive data processing algorithm（最优化自回归数据处理算法）”。对于解决很大部分的问题，他是最优，效率最高甚至是最有用的。他的广泛应用已经超过30年，包括机器人导航，控制，传感器数据融合甚至在军事方面的雷达系统以及导弹追踪等等。近年来更被应用于计算机图像处理，例如头脸识别，图像分割，图像边缘检测等等。

    首先，我们先要引入一个离散控制过程的系统。该系统可用一个线性随机微分方程（Linear Stochastic Difference equation）来描述：

X(k)=A X(k-1)+B U(k)+W(k)

再加上系统的测量值：

Z(k)=H X(k)+V(k)

     上两式子中，X(k)是k时刻的系统状态，U(k)是k时刻对系统的控制量。A和B是系统参数，对于多模型系统，他们为矩阵。Z(k)是k时刻的测量值，H是测量系统的参数，对于多测量系统，H为矩阵。W(k)和V(k)分别表示过程和测量的噪声。他们被假设成高斯白噪声(White Gaussian Noise)，他们的协方差分别是Q，R（这里我们假设他们不随系统状态变化而变化）。
     对于满足上面的条件(线性随机微分系统，过程和测量都是高斯白噪声)，卡尔曼滤波器是最优的信息处理器。下面我们来用他们结合他们的协方差来估算系统的最优化输出。
     首先我们要利用系统的过程模型，来预测下一状态的系统。假设现在的系统状态是k，根据系统的模型，可以基于系统的上一状态而预测出现在状态：

X(k|k-1)=A X(k-1|k-1)+B U(k) ……… (1)

     式(1)中，X(k|k-1)是利用上一状态预测的结果，X(k-1|k-1)是上一状态最优的结果，U(k)为现在状态的控制量，如果没有控制量，它可以为0。
     到现在为止，我们的系统结果已经更新了，可是，对应于X(k|k-1)的协方差还没更新。我们用P表示协方差：

P(k|k-1)=A P(k-1|k-1) A’+Q ……… (2)

     式(2)中，P(k|k-1)是X(k|k-1)对应的协方差，P(k-1|k-1)是X(k-1|k-1)对应的协方差，A’表示A的转置矩阵，Q是系统过程的协方差。式子1，2就是卡尔曼滤波器5个公式当中的前两个，也就是对系统的预测。
     现在我们有了现在状态的预测结果，然后我们再收集现在状态的测量值。结合预测值和测量值，我们可以得到现在状态(k)的最优化估算值X(k|k)：

X(k|k)= X(k|k-1)+Kg(k) (Z(k)-H X(k|k-1)) ……… (3)

     其中Kg为卡尔曼增益：

Kg(k)= P(k|k-1) H’ / (H P(k|k-1) H’ + R) ……… (4)

     到现在为止，我们已经得到了k状态下最优的估算值X(k|k)。但是为了要另卡尔曼滤波器不断的运行下去直到系统过程结束，我们还要更新k状态下X(k|k)的协方差：

P(k|k)=（I-Kg(k) H）P(k|k-1) ……… (5)

     其中I 为1的矩阵，对于单模型单测量，I=1。当系统进入k+1状态时，P(k|k)就是式子(2)的P(k-1|k-1)。这样，算法就可以自回归的运算下去。卡尔曼滤波器的原理基本描述了，式子1，2，3，4和5就是他的5 个基本公式。

3. D-S方法

    当各传感器对它们各自的判决并不能100%确信时，我们可以采用一种基于统计方法的数据融合分类算法，即Dempster-Shafer算法。该算法能捕捉并融合来自各传感器在模式分类中能确定某些因素的能力，使用Dempster规则来融合各传感器事件（也称之为命题）的知识，最后找到各命题的交集（也叫命题的合取）及与之对应的概率分配值。

DS 算法是基于证据理论的一种推理算法，它由Dempster 首先提出,并由Shafer 加以扩充发展,故称之为DS 证据理论。该算法解决了概率论中的2个困难问题：一是能够对“未知”给出显式的表示；二是当证据对一个假设部分支持时，该证据对假设否定的支持也能用明确的值表示出来。

设Ω为变量x所有可能值的穷举集合，且Ω中的各元素是相互排斥的,则称Ω为样本空间。如果Ω中元素的个数为N ,则Ω幂集合的元素个数为。幂集合中的每个元素对应于一个关于x取值情况的命题(子集) 。

对任一个属于的子集A (命题),令它对应一个数 ,且满足:

(1) m(Φ) = 0 ,Φ为空集或称为不可能事件;

(2)。

则称函数为上的基本概率分配函数, m(A)为A的基本概率数。

值得注意的是,在实际工作中,人们从对于事件A的相信程度并不一定能够得到他对的相信程度,其中=Ω- A。因此,在概率论中成立的P (A) + P () = 1 ,在DS证据理论中将成为m (A) + m (A)≤1 ,这说明m(A)不是概率。

定义命题的信任函数Bel：为

，

其中A =Ω- A

Bel (A)表示对A的总的信任程度,又称之为可信度。

定义命题的似然函数Pl : 为，

其中，。

Pl (A)表示不否定A的信任程度,又称之为拟信度。

Bel (A)和Pl (A)分别为命题A的下限函数和上限函数,两者的关系满足Pl (A)≥Bel(A)。当Pl (A) = Bel (A)时,DS方法就等同于Bayes算法。事实上,在获得的关于命题A的证据中,一部分是支持命题A的,称之为支持证据,另一部分是反对命题A或支持A的,称之为拒绝证据,此外还有既不明显支持又不明显反对A的证据,称之为中性证据。

其中,Bel (A)是所有支持命题A的证据所能获得的关于A的极大可信度值, Pl (A)是所有不反对命题A的证据(支持证据和中性证据) 所能获得的关于A的极大可信度值,由Bel (A)和Pl (A)度量命题A二值可信度的不确定性,其中Bel (A)和Pl (A)对应于未知概率的下界和上界,即:

Pl (A) - Bel (A)的值反映了我们对命题A的“未知”信息,该差值越小,则表明“未知”成分越小,证据对假设的支持越明确。

4.      模糊数学方法

模糊控制是用模糊数学的知识模仿人脑的思维方式，对模糊现象进行识别和判决，给出精确的控制量，对被控对象进行控制。与经典控制理论和现代控制理论相比，模糊控制的主要特点是不需要建立对象的数学模型。操作人员根据对象的当前状态和以往的控制经验，用手动控制的方法给出适当的控制量，对被控对象进行控制。用计算机模拟操作人员手动控制的经验，对被控对象进行控制。

模糊控制的基本思想：首先根据操作人员手动控制的经验，总结出一套完整的控制规则，再根据系统当前的运行状态，经过模糊推理、模糊判决等运算，求出控制量，实现对被控对象的控制。

模糊控制发展的三个阶段：（1）基本模糊控制：针对特定对象设计，控制效果好。控制过程中规则不变，不具有通用性，设计工作量大。（2）自组织模糊控制：某些规则和参数可修改，可对一类对象进行控制。（3）智能模糊控制：具有人工智能的特点，能对原始规则进行修正、完善和扩展，通用性强。

一般模糊控制系统包含了五个主要部分，即:定义变量、模糊化、知识库、逻辑判断及反模糊化，以下将就每一部分做简单的说明：

(1) 定义变量

也就是决定程序被观察的状况及考虑控制的动作，例如在一般控制问题上，输入变量有输出误差E与输出误差之变化率EC，而控制变量则为下一个状态之输入U。其中E、EC、U统称为模糊变量。

(2) 模糊化（fuzzify）

将输入值以适当的比例转换到论域的数值，利用口语化变量来描述测量物理量的过程，依适合的语言值（linguistic value）求该值相对之隶属度，此口语化变量我们称之为模糊子集合（fuzzy subsets）。

(3) 知识库

　　包括数据库（data base）与规则库（rule base）两部分，其中数据库是提供处理模糊数据之相关定义；而规则库则藉由一群语言控制规则描述控制目标和策略。

(4) 逻辑判断

模仿人类下判断时的模糊概念，运用模糊逻辑和模糊推论法进行推论，而得到模糊控制讯号。此部分是模糊控制器的精髓所在。

(5) 解模糊化（defuzzify）

将推论所得到的模糊值转换为明确的控制讯号，做为系统的输入值。

5.      遗传算法

遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《Adaptation in Natural and Artificial Systems》，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算法（SGA）。

遗传算法的基本运算过程如下: 　　

a)初始化:设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。 　　

b)个体评价:计算群体P(t)中各个个体的适应度。 　　

c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。 　　

d)交叉运算；将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。 　　

e)变异运算:将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t 1)。 　　

f)终止条件判断:若tT,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。

6.      人工神经网络

人工神经网络（ArtificialNeuralNetworks，简写为ANNs）也简称为神经网络（NNs）或称作连接模型（ConnectionistModel），它是一种模范动物神经网络行为特征，进行分布式并行信息处理的算法数学模型。这种网络依靠系统的复杂程度，通过调整内部大量节点之间相互连接的关系，从而达到处理信息的目的。人工神经网络具有自学习和自适应的能力，可以通过预先提供的一批相互对应的输入－输出数据，分析掌握两者之间潜在的规律，最终根据这些规律，用新的输入数据来推算输出结果，这种学习分析的过程被称为“训练”。

根据连接的拓扑结构，神经网络模型可以分为：

（1）前向网络 网络中各个神经元接受前一级的输入，并输出到下一级，网络中没有反馈，可以用一个有向无环路图表示。这种网络实现信号从输入空间到输出空间的变换，它的信息处理能力来自于简单非线性函数的多次复合。网络结构简单，易于实现。反传网络是一种典型的前向网络。

（2）反馈网络 网络内神经元间有反馈，可以用一个无向的完备图表示。这种神经网络的信息处理是状态的变换，可以用动力学系统理论处理。系统的稳定性与联想记忆功能有密切关系。Hopfield网络、波耳兹曼机均属于这种类型。

第二篇：数据结构课程总结

?

?

?

?

? 数据：能够被计算机识别、存储和加工处理的信息的载体。 数据元素：数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。 数据结构的定义： 逻辑结构：从逻辑结构上描述数据，独立于计算机。线性结构：一对一关系。线性结构：多对多关系。 存储结构：是逻辑结构用计算机语言的实现。顺序存储结构：如数组。链式存储结构：如链表。索引结构：索引表。散列存储结

构：如散列表。

?

? 对数据的操作：定义在逻辑结构上，每种逻辑结构都有一个运算集合。常用的有：检索、插入、删除、更新、排序。 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。原子类型：简单类型，由语言提供。结构类型：由用户借助

于描述机制定义，是导出类型。

?

?

?

? 程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。算法取决于数据结构。 算法是一个自定义的计算过程，以一个或多个值输入，并以一个或多个值输出。 评价算法的好坏的因素：算法是正确的;执行算法的时间;执行算法的存储空间;算法易于理解、编码、调试。 时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。渐近时间复杂度：是指当问题规模趋向无穷大时，

该算法时间复杂度的数量级。评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。

?

?

?

?

?

? 算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。 时间复杂度按数量级递增排列依次为：常数阶、对数阶、线性阶、线性对数阶、平方阶、立方阶、……k次方阶、指数阶。 空间复杂度：是某个算法的空间耗费，它是该算法所求解问题规模n的函数。 算法的时间复杂度和空间复杂度合称算法复杂度。 线性表是由n≥0个数据元素组成的有限序列。n=0是空表;非空表，只能有一个开始结点，有且只能有一个终端结点。 线性表上定义的基本运算：构造空表：Initlist；求表长：Listlength；取结点：GetNode；查找：LocateNode；插入：InsertList；删

除：Delete。

? 顺序表是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中。在存储单元中的各元素的物理位置和逻辑结构中各结

点相邻关系是一致的。地址计算：？

? 在顺序表中实现的基本运算：插入：平均移动结点次数为？;平均时间复杂度均为？。删除：平均移动结点次数为？;平均时间复杂

度均为？。

? 线性表的链式存储结构中结点的逻辑次序和物理次序不一定相同，为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，

还存储了其后继结点的地址信息。这两部分信息组成链表中的结点结构。一个单链表由头指针的名字来命名。

? 单链表运算：建立单链表（头插法：生成的顺序与输入顺序相反。平均时间复杂度均为？。尾插法：平均时间复杂度均为？。加

头结点的算法：对开始结点的操作无需特殊处理，统一了空表和非空表。查找（按序号：与查找位置有关，平均时间复杂度均为？。

按值：与输入实例有关，平均时间复杂度均为。插入运算：p=GetNode;s-next=p-next;p-next=s;平均时间复杂度均为？，删除运算：平均时间复杂度均为？）

? 单循环链表是一种首尾相接的单链表，终端结点的指针域指向开始结点或头结点。链表终止条件是以指针等于头指针或尾指针。

采用单循环链表在实用中多采用尾指针表示单循环链表。优点是查找头指针和尾指针的时间都是O？，不用遍历整个链表。

? 双链表就是双向链表，就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior，形成两条不同方向的链。由头指针

head惟一确定。双链表也可以头尾相构成双循环链表。双链表上的插入和删除时间复杂度均为O？。

?

? 顺序表和链表的比较： 基于空间：顺序表的存储空间是静态分配，存储密度为1;适于线性表事先确定其大小时采用。链表的存储空间是动态分配，存储

密度1;适于线性表长度变化大时采用。

? 基于时间：顺序表是随机存储结构，当线性表的操作主要是查找时，宜采用。以插入和删除操作为主的线性表宜采用链表做存储

结构。若插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。

? 栈是仅限制在表的一端进行插入和删除运算的线性表，称插入、删除这一端为栈顶，另一端称为栈底。表中无元素时为空栈。栈

的修改是按后进先出的原则进行的，我们又称栈为LIFO表。通常栈有顺序栈和链栈两种存储结构。

? 栈的基本运算有六种：构造空栈：InitStack，判栈空：StackEmpty，判栈满：StackFull，进栈：Push，退栈：Pop，取栈顶元素：

StackTop

? 在顺序栈中有“上溢”和“下溢”的现象。“上溢”是栈顶指针指出栈的外面是出错状态。“下溢”可以表示栈为空栈，因此用来作为控制

转移的条件。

?

?

?

? 顺序栈中的基本操作有六种：构造空栈，判栈空，判栈满，进栈，退栈，取栈顶元素 链栈则没有上溢的限制，因此进栈不要判栈满。链栈不需要在头部附加头结点，只要有链表的头指针就可以了。 链栈中的基本操作有五种：构造空栈，判栈空，进栈，退栈，取栈顶元素 队列是一种运算受限的线性表，插入在表的一端进行，而删除在表的另一端进行，允许删除的一端称为队头，允许插入的一端称

为队尾，队列的操作原则是先进先出的，又称作FIFO表.队列也有顺序存储和链式存储两种存储结构。

? 队列的基本运算有六种：置空队：InitQueue，判队空：QueueEmpty，判队满：QueueFull，入队：EnQueue，出队：DeQueue，取

队头元素：QueueFront

? 顺序队列的“假上溢”现象：由于头尾指针不断前移，超出向量空间。这时整个向量空间及队列是空的却产生了“上溢”现象。为了克

服“假上溢”现象引入循环向量的概念，是把向量空间形成一个头尾相接的环形，这时队列称循环队列。

? 判定循环队列是空还是满，方法有三种：一种是另设一个布尔变量来判断;第二种是少用一个元素空间，入队时先测试%m=front)?

满：空;第三种就是用一个计数器记录队列中的元素的总数。

? 队列的链式存储结构称为链队列，一个链队列就是一个操作受限的单链表。为了便于在表尾进行插入的操作，在表尾增加一个尾

指针，一个链队列就由一个头指针和一个尾指针唯一地确定。链队列不存在队满和上溢的问题。在链队列的出队算法中，要注意当原队中只有一个结点时，出队后要同进修改头尾指针并使队列变空。

?

? 串是零个或多个字符组成的有限序列。 概念 空串：是指长度为零的串，也就是串中不包含任何字符。空白串：指串中包含一个或多个空格字符的串。在一个串中任意

个连续字符组成的子序列称为该串的子串，包含子串的串就称为主串。子串在主串中的序号就是指子串在主串中首次出现的位置。空串是任意串的子串，任意串是自身的子串。

?

? 串分为两种：串常量在程序中只能引用不能改变;串变量的值可以改变。 串的基本运算有：求串长strlen，串复制strcpy，串联接strcat，串比较charcmp，字符定位strchr。串是特殊的线性表，所以串的存

储结构与线性表的存储结构类似。串的顺序存储结构简称为顺序串。

? 顺序串又可按存储分配的不同分为：静态存储分配：直接用定长的字符数组来定义。优点是涉及串长的操作速度快，但不适合插

入、操作。动态存储分配：是在定义串时不分配存储空间，需要使用时按所需串的长度分配存储单元。

? 串的链式存储就是用单链表的方式存储串值，串的这种链式存储结构简称为链串。链串与单链表的差异只是它的结点数据域为单

个字符。为了解决“存储密度”低的状况，可以让一个结点存储多个字符，即结点的大小。

? 顺序串上子串定位的运算：又称串的“模式匹配”或“串匹配”，是在主串中查找出子串出现的位置。在串匹配中，将主串称为目标，

子串称为模式。这是比较容易理解的，串匹配问题就是找出给定模式串P在给定目标串T中首次出现的有效位移或者是全部有效位移。最坏的情况下时间复杂度是Om)，假如m与n同阶的话则它是O。链串上的子串定位运算位移是结点地址而不是整数。 ?

?

? 数组一般用顺序存储的方式表示。 存储的方式有：行优先顺序，也就是把数组逐行依次排列。PASCAL、C。列优先顺序，就是把数组逐列依次排列。FORTRAN 地址的计算方法：按行优先顺序排列的数组：LOC（a）=？.。按列优先顺序排列的数组：LOC（a）=？ .矩阵的压缩存储：为多

个相同的非零元素分配一个存储空间;对零元素不分配空间。

?

?

?

?

?

? 特殊矩阵的概念：所谓特殊矩阵是指非零元素或零元素分布有一定规律的矩阵。 稀疏矩阵的概念：一个矩阵中若其非零元素的个数远远小于零元素的个数，则该矩阵称为稀疏矩阵。 特殊矩阵的类型：对称矩阵：三角矩阵：上三角阵,下三角阵,对角矩阵k=f(I,j)， 广义表是n个元素的有限序列，其中的元素是原子或者是一个广义表。广义表表头和表尾的概念： 广义表有两种表示法，一种是括号表示法，一种是图形表示法。 广义表有两个特殊的基本运算：取表头head：取表中的第一个数据元素，不能对空表操作。取表尾tail;取除表头外，其余数据元

素构成的子表，不能对空表操作

? 树是n个结点的有限集合，非空时必须满足：只有一个称为根的结点;其余结点形成m个不相交的子集，并称根的子树。根是开始

结点;结点的子树数称度;度为0的结点称叶子;度不为0的结点称分支结点;除根外的分支结点称内部结点;

?

? 树的四种不同表示方法：树形表示法;嵌套集合表示法;凹入表示法;广义表表示法。 二叉树的定义：是n≥0个结点的有限集，它是空集或由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树

组成。二叉树不是树的特殊情形，与度数为2的有序树不同。二叉树的4个重要性质：

?

? 二叉树的顺序存储结构就是把二叉树的所有结点按照层次顺序存储到连续的存储单元中。 树的存储结构多用的是链式存储。二叉树的链式存储结构，称为二叉链表。它就是由根指针root唯一确定的。共有2n个指针域，

n+1个空指针。

?

? 根据结点的次序不同可得三种遍历：先序遍历，中序遍历、后序遍历。时间复杂度为 。 利用二叉链表中的n+1个空指针域来存放指向某种遍历次序下的前趋结点和后继结点的指针，这些附加的指针就称为“线索”，加

上线索的二叉链表就称为线索链表。线索使得查找中序前趋和中序后继变得简单有效，但对于查找指定结点的前序前趋和后序后继并没有什么作用。

? 树和森林及二叉树的转换是唯一对应的。二叉树变树：结点的右孩子与其双亲连。森林变二叉树：树变二叉树，各个树的根相连。

转换方法?

?

?

?

? 树的存储结构：有双亲链表表示法：孩子链表表示法：双亲孩子链表表示法：孩子兄弟链表表示法： 树的前序遍历与相对应的二叉树的前序遍历一致;树的后序遍历与相对应的二叉树的中序遍历一致。 树的带权路径长度?最优二叉树?完全二叉树?哈夫曼树及其性质， 变长编码技术可以使频度高的字符编码短，而频度低的字符编码长，但是变长编码可能使解码产生二义性。如00、01、0001这三

个码无法在解码时确定是哪一个，所以要求在字符编码时任一字符的编码都不是其他字符编码的前缀，这种码称为前缀码。哈夫曼树的应用。

?

?

? 图的逻辑结构特征就是其结点的前趋和后继的个数都是没有限制的，即任意两个结点之间之间都可能相关。 图，有向图，无向图，简单路径,简单回路,网络等及其性质。 图的存储结构：邻接矩阵表示法：适合稠密图。无向邻接矩阵是对称的。有向行是出度，列是入度。建立邻接矩阵算法的时间是

O，其时间复杂度为O。邻接表表示法：适合稀疏图。时间复杂度为O，空间复杂度为O。

? 图的遍历：深度优先遍历：借助于邻接矩阵的列。使用栈保存已结点。广度优先遍历：借助于邻接矩阵的行。使用队列保存已结

点。

? 生成树的定义：最小生成树：Prim算法的时间复杂度为O与边数无关适于稠密图。Kruskal算法的时间复杂度为O，主要取决于边

数，较适合于稀疏图。

?

? 最短路径的算法：Dijkstra算法，时间复杂度为O。 拓扑排序：无前趋的顶点优先：每次输出一个无前趋的结点并删去此结点及其出边，最后得到的序列即拓扑序列。无后继的结点

优先：每次输出一个无后继的结点并删去此结点及其入边，最后得到的序列是逆拓扑序列。

?

?

?

? 关键字项，关键字。 排序是使文件中的记录按关键字递增次序排列起来。 基本操作：比较关键字大小;改变指向记录的指针或移动记录。 存储结构：顺序结构、链表结构、索引结构。经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方

法是稳定的，否则排序算法是不稳定的。

?

?

?

? 排序过程中不涉及数据的内、外存交换则称之为“内部排序”，反之，若存在数据的内外存交换，则称之为外排序。 内部排序方法可分五类：插入排序、选择排序、交换排序、归并排序和分配排序。 评价排序算法好坏的标准主要有两条：执行时间和所需的辅助空间，另外算法的复杂程序也是要考虑的一个因素。 插入排序：直接插入排序;逐个向前插入到合适位置;哨兵有两个作用;作为临变量存放R[i];是在查找循环中用来监视下标变量j是否

越界;直接插入排序是稳定排序。时间复杂度为O ？比较次数为/2;移动次数为？。希尔排序：等间隔的数据比较并按要求顺序排列，最后间隔为1;希尔排序是就地的不稳定排序。时间复杂度为O，比较次数为;移动次数为;

? 交换排序：冒泡排序：自下向上确定最轻的一个。自上向下确定最重的一个。冒泡排序是就地的稳定排序。时间复杂度为O？比

较次数为？;移动次数为？;快速排序：以第一个元素为参考基准，设定、动两个指针，发生交换后指针交换位置，直到指针重合。重复直到排序完成。快速排序是不稳定排序。时间复杂度为O？比较次数为？。

? 选择排序：直接选择排序;选择最小的放在比较区前;直接选择排序不稳定排序。时间复杂度为O？。比较次数为？。堆排序：建堆：

按层次将数据填入完全二叉树，从int处向前逐个调整位置。然后将树根与最后一个叶子交换值并断开与树的连接并重建堆，直到全断开。堆排序是就地不稳定的排序，时间复杂度为O，不适宜于记录数较少的文件。

?

?

?

?

?

?

?

?

?

?

?

? 归并排序：先两个一组排序，形成/2组，再将两组并一组，直到剩下一组为止。归并排序是非稳定排序，时间复杂度是O？ 基数排序：从低位到高位依次对关键字进行箱排序。基数排序是非就稳定的排序，时间复杂度是O？。 各种排序方法的比较和选择： 1、待排序的记录数目n;n较大的要用时间复杂度为O的排序方法; 2、记录的大小;记录大最好用链表作为存储结构，而快速排序和堆排序在链表上难于实现; 3、关键字的结构及其初始状态; 4、对稳定性的要求; 5、语言工具的条件; 6、存储结构;时间和辅助空间复杂度。 关于查找 查找的同时对表做修改操作则相应的表称之为动态查找表，否则称之为静态查找表。 衡量查找算法效率优劣的标准是在查找过程中对关键字需要执行的平均比较次数。

? 线性表查找的方法：顺序查找：逐个查找，ASL=？;二分查找：取中点int比较，若小就比左区间，大就比右区间。用二叉判定树

表示。ASL=？;分块查找：要求“分块有序”，将表分成若干块内部不一定有序，并抽取各块中的最大关键字及其位置建立有序索引表。

? 二叉排序树定义是二叉排序树是空树或者满足如下性质的二叉树：若它的左子树非空，则左子树上所有结点的值均小于根结点的

值;若它的右子树非空，则右子树上所有结点的值均大于根结点的值;左、右子树本身又是一棵二叉排序树。

?

? 二叉排序树的插入、建立、删除的算法平均时间性能是O？。 二叉排序树的删除操作可分三种情况进行处理：*P是叶子，则直接删除*P，即将*P的双亲*parent中指向*P的指针域置空即可。

*P只有一个孩子*child，此时只需将*child和*p的双亲直接连接就可删去*p。*p有两个孩子，则先将*p结点的中序后继结点的数据到*p，删除中序后继结点。

?

? 关于B-树。它适合在磁盘等直接存取设备上组织动态的查找表，是一种外查找算法。建立的方式是从下向上拱起。 散列技术：将结点按其关键字的散列地址存储到散列表的过程称为散列。散列函数的选择有两条标准：简单和均匀。常见的散列

函数构的造方法：平方取中法,除余法,相乘取整法,随机数法。

? 处理冲突的方法：开放定址法：一般形式为?，开放定址法要求散列表的装填因子α≤1。开放定址法类型：线性探查法，二次探查

法，双重散列法。拉链法：是将所有关键字为同义词的结点在同一个单链表中。

? 拉链法的优点：拉链法处理冲突简单，且无堆积现象;链表上的结点空间是动态申请的适于无法确定表长的情况;拉链法中α可以大

于1，结点较大时其指针域可忽略，因此节省空间;拉链法构造的散列表删除结点易实现。

? 拉链法也有缺点：当结点规模较小时，用拉链法中的指针域也要占用额外空间，还是开放定址法省空间。