第三章 二值图像分析
一幅数字图像是一个二维阵列，阵列元素值称为灰度值或强度值．实际上，图像在量化成数字图像前是一个连续强度函数的集合，场景信息就包含在这些强度值中．图像强度通常被量化成256个不同灰度级，对某些应用来说，也常有32、64、128或512个灰度级的情况，在医疗领域里甚至使用高达4096(12bits ）个灰度级．很明显，灰度级越高，图像质量越好，但所需的内存也越大．
在机器视觉研究的早期，由于内存和计算能力非常有限，而且十分昂贵，因此视觉研究人员把精力主要集中在研究输入图像仅包含两个灰度值的二值视觉系统上．人们注意到，人类视觉在理解仅由两个灰度级组成的线条、轮廓影像或其它图像时没有任何困难，而且应用场合很多，这一点对研究二值视觉系统的研究人员是一个极大的鼓舞．
随着计算机计算能力的不断增强和计算成本的不断下降，人们普遍开始研究基于灰度图像、彩色图像和深度图像的视觉系统．尽管如此，二值视觉系统还是十分有用的，其原因如下：⑴ 计算二值图像特性的算法非常简单，容易理解和实现，并且计算速度很快．⑵ 二值视觉所需的内存小，对计算设备要求低．工作在256个灰度级的视觉系统所需内存是工作在相同大小二值图像视觉系统所需内存的八倍．如若利用游程长度编码等技术（见3．4节）还可使所需内存进一步减少．由于二值图像中的许多运算是逻辑运算而不是算术运算，所以所需的处理时间很短．（3）许多二值视觉系统技术也可以用于灰度图像视觉系统上．在灰度或彩色图像中，表示一个目标或物体的一种简易方法就是使用物体模板(mask)，物体模板就是一幅二值图像，其中1表示目标上的点，0表示其它点．在物体从背景中分离出来后，为了进行决策，还需要求取物体的几何和拓扑特性，这些特性可以从它的二值图像计算出来．因此，尽管我们是在二值图像上讨论这些方法，但它们的应用并不限于二值图像．
一般来说，当物体轮廓足以用来识别物体且周围环境可以适当地控制时，二值视觉系统是非常有用的．当使用特殊的照明技术和背景并且场景中只有少数物体时，物体可以很容易地从背景中分离出来，并可得到较好的轮廓，比如，许多工业场合都属于这种情况．二值视觉系统的输入一般是灰度图像，通常使用阈值法首先将图像变成二值图像，以便把物体从背景中分离出来，其中的阈值取决于照明条件和物体的反射特性．二值图像可用来计算特定任务中物体的几何和拓扑特性，在许多应用中，这种特性对识别物体来说是足够的．二值视觉系统已经在光学字符识别、染色体分析和工业零件的识别中得到了广泛应用．
在下面的讨论中，假定二值图像大小为n m ?，其中物体像素值为1，背景像素值为0．
3．1 阈值
视觉系统中的一个重要问题是从图像中识别代表物体的区域（或子图像），这种对人来说是件非常容易的事，对计算机来说却是令人吃惊的困难．为了将物体区域同图像其它区域分离出来，需要首先对图像进行分割．把图像划分成区域的过程称为分割，即把图像],[j i F 划分成区域k p p p ,,,21???，使得每一个区域对应一个候选的物体．下面给出分割的严格定义． 定义 分割是把像素聚合成区域的过程，使得：
==i k
i P 1 整幅图像 (}{i P 是一个完备分割 )．
●
j i P P j i ≠?=, ，(}{i P 是一个完备分割)． ● 每个区域i P 满足一个谓词，即区域内的所有点有某种共同的性质．
● 不同区域的图像，不满足这一谓词．
正如上面所表明的，分割满足一个谓词，这一谓词可能是简单的，如分割灰度图像时用的均匀灰度分布、相同纹理等谓词，但在大多数应用场合，谓词十分复杂．在图像理解过程中，分割是一个非常重要的步骤．
二值图像可以通过适当地分割灰度图像得到．如果物体的灰度值落在某一区间内，并且背景的灰度值在这一区间之外，则可以通过阈值运算得到物体的二值图像，即把区间内的点置成1，区间外的点置成0．对于二值视觉，分割和阈值化是同义的．阈值化可以通过软件来实现，也可以通过硬件直接完成．
通过阈值运算是否可以有效地进行图像分割，取决于物体和背景之间是否有足够的对比度．设一幅灰度图像],[j i F 中物体的灰度分布在区间],[21T T 内，经过阈值运算后的图像为二值图像],[j i F T ，即：
???≤≤=其它
如果0],[ 1],[21T j i F T j i F T (3．1) 如果物体灰度值分布在几个不相邻区间内时，阈值化方案可表示为：
?
??∈=其它如果0],[ 1],[Z j i F j i F T (3．2) 其中Z 是组成物体各部分灰度值的集合．图3．1是对一幅灰度图像使用不同阈值得到的二值图像输出结果．
阈值算法与应用领域密切相关．事实上，某一阈值运算常常是为某一应用专门设计的，在其它应用领域可能无法工作．阈值选择常常是基于在某一应用领域获取的先验知识，因此在某些场合下，前几轮运算通常采用交互式方式来分析图像，以便确定合适的阈值．但是，在机器视觉系统中，由于视觉系统的自主性能（autonomy ）要求，必须进行自动阈值选择．现在已经研究出许多利用图像灰度分布和有关的物体知识来自动选择适当阈值的技术．其中的一些方法将在3．2节介绍．
图3．1 一幅灰度图像和使用不同阈值得到的二值图像结果．上左：原始灰度图像，上右：阈
值T=100；左下：T=128．右下：T1=100|T2=128．
3．2 几何特性
通过阈值化方法从图像中检测出物体后，下一步就要对物体进行识别和定位．在大多数工业应用中，摄像机的位置和环境是已知的，因此通过简单的几何知识就可以从物体的二维图像确定出物体的三维位置．在大多数应用中，物体的数量不是很多，如果物体的尺寸和形状完全不同，则可以利用尺度和形状特征来识别这些物体．实际上在许多工业应用中，经常使用区域
的一些简单特征，如大小、位置和方向，来确定物体的位置并识别它们．
3．2．1 尺寸和位置
一幅二值图像区域的面积（或零阶矩）由下式给出：
∑∑-=-==101
0],[n i m j j i B A （3．3）
在许多应用中，物体的位置起着十分重要的作用．工业应用中，物体通常出现在已知表面（如工作台面）上，而且摄像机相对台面的位置也是已知的．在这种情况下，图像中的物体位置决定了它的空间位置．确定物体位置的方法有许多，比如用物体的外接矩形、物体矩心（区域中心）等来表示物体的位置．区域中心是通过对图像进行“全局”运算得到的一个点，因此它对图像中的噪声相对来说是不敏感的．对于二值图像，物体的中心位置与物体的质心相同，因此可以使用下式求物体的中心位置：
∑∑∑∑∑∑∑∑-=-=-=-=-=-=-=-=-==10101010101
01010]
,[],[]
,[],[n i n i m j m j n i m j n i m j j i iB j i B y j i jB j i B x (3．4)
其中x 和y 是区域相对于左上角图像的中心坐标．物体的位置为： A
j i iB y A
j i jB x n i m j n i m j ∑∑∑∑-=-=-=-=-==
10101010]
,[]
,[ (3．5)
这些是一阶矩．注意，由于约定y 轴向上，因此方程3．4和3．5的第二个式子的等号右边加了负号． 3．2．2 方向
计算物体的方向比计算它的位置稍微复杂一点．某些形状（如圆）的方向不是唯一的，为了定义唯一的方向，一般假定物体是长形的，其长轴方向被定义为物体的方向．通常，二维平面上与最小惯量轴同方向的最小二阶矩轴被定为长轴．
图像中物体的二阶矩轴是这样一条线，物体上的全部点到该线的距离平方和最小．给出一幅二值图像],[j i B ，计算物体点到直线的最小二乘方拟合，使所有物体点到直线的距离平方和最小：
χ2
20101==-=-∑∑r B i j ij j m i n [,] (3．6)
其中r ij 是物体点],[j i 到直线的距离．为了避免直线处于近似垂直时所出现的数值病态问题，人们一般把直线表示成极坐标形式：
θθρsin cos y x += (3．7)
如图3．2所示，θ是直线的法线与x 轴的夹角，ρ是直线到原点的距离．把点),(j i 坐标代入直线的极坐标方程得出距离r ：
22)sin cos (ρθθ-+=y x r (3．
8)
图3．2 直线的极坐标表示
将方程3．8代入方程3．6并求极小化问题，可以确定参数ρ和θ：
∑∑-=-=-+=101
022
],[)sin cos (n i m j ij ij j i B y x ρθθχ (3．9) 令2χ对ρ的导数等于零求解ρ得：
)sin cos (θθρy x += (3．10) 它说明回归直线通过物体中心),(y x ．用这一ρ值代入上面的2χ，则极小化问题变为：
θθθθχ222sin cos sin cos c b a ++= (3．11)
其中的参数： ]
,[)(],[))((2]
,[)(1021
0101
0101
02j i B y y c j i B y y x x b j i B x x a n i m j ij n i m j ij ij n i m j ij ∑∑∑∑∑∑-=-=-=-=-=-=-=--=-= (3．12)
是二阶矩．表达式2χ可重写为：
θθχ2sin 212cos )(21)(212b c a c a +-++=
(3．13) 对2χ微分，并置微分结果为零，求解θ 值：
c
a b -=
θ2tan (3．14) 因此，惯性轴的方向由下式给出：
222
2)(2cos )(2sin c a b c
a c a
b b -+-±
=-+±
=θθ (3．15) 所以由2χ的最小值可以确定方向轴．注意，如果c a b ==,0，那么物体就不会只有唯一的方向轴．物体的伸长率E 是2χ的最大值与最小值之比：
min
max χχ=E (3．16) 3．2．3 密集度和体态比
区域的密集度（compact ）可用下面的式子来度量：
2p
A C = (3．17) 其中，p 和A 分别为图形的周长和面积．根据这一衡量标准，圆是最密集的图形，其密集密度为最大值π4/1，其它一些图形的比值要小一些．让我们来看一下圆，当圆后仰时，形状成了一椭圆，面积减小了而周长却不象面积减小的那么快，因此密集度降低了．在后仰到极限角时，椭圆被压缩成了一条无限长直线，椭圆的周长为无穷大，故密集度变成了零．对于数字图像， 2p A 是指物体尺寸（像素点数量）除以边界长度的平方．这是一种很好的散布性或密集性度量方法．这一比值在许多应用中被用作为区域的一个特征．
密集度的另一层意义是：在给定周长的条件下，密集度越高，围成的面积就越大．注意在等周长的情况下，正方形密集度大于长方形密集度．
体态比定义为区域的最小外接矩形的长与宽之比，正方形和圆的体态比等于1，细长形物体的体态比大于1．图3.3所示的是几种形状的外接矩形．
图3.3 几种外接矩形示意图 3．3 投影
给定一条直线，用垂直该直线的一簇等间距直线将一幅二值图像分割成若干条，每一条内像素值为1的像素个数为该条二值图像在给定直线上的投影（projection ）．当给定直线为水平或垂直直线时，计算二值图像每一列或每一行上像素值为1的像素数量，就得到了二值图像的水平和垂直投影，如图3．4所示．由于投影包含了图像的许多信息，所以投影是二值图像的一种
简洁表示方式．显然，投影不是唯一的，同样的投影可能对应不同的图像．
图3．4 一幅二值图像及其水平投影图
在某些应用中，投影可以作为物体识别的一个特征．投影既是一种简洁的图像表示，又可以实现快速算法．下面介绍对角线投影的求解方法．对角线投影的关键是计算当前行和列对应的投影分布图位置标号．设行和列的标号分别用i 和j 表示．若图像矩阵为n 行m 列，则i 和j 的范围分别为0到1-n 和0到1-m ．假设对角线的标号d 用行和列的仿射变换（线性组合加上常数）计算，即：
c bj ai
d ++= (3．18) 对角线投影共对应1-+m n 个条，其中仿射变换把右上角像素映射成对角线投影的第一个位置，把左下角像素映射成最后一个位置，如图3.5所示，则当前行列对应的标号d 的公式为：
1-+-=m j i d (3．19)
图3．5 二值图像及其对角线上的投影图
3．4 游程长度编码
游程长度编码(run-length encoding)是另一种二值图像的简洁表示方法，它是用图像像素值连续为1的个数（像素1的长度）来描述图像．这种编码已被用于图像传输．另外，图像的某些性质，如物体区域面积，也可以从游程长度编码直接计算出来．
在游程长度编码中经常运用两种方法，一种是使用1的起始位置和1的游程长度，另一种是仅仅使用游程长度，但须从1的游程长度开始描述，如图3.6所示．
1的游程（2,2） （6,3） （13,6） （20,1）
（4,6） （11,10）
（1,5 ） （11，1） （17，4）
1和0的游程长度：0，2，2，3，4，6，1，1
0，3，6，1，10
5，5，1，5，4
图3．6 一幅简单二值图像的游程长度编码．
如果用第二种方法来表示图像每行的游程长度，并用k i r ,代表图像第i 行的第k 个游程长度，则全部1的游程长度之和就是所求物体的面积．
∑∑-=??????-=+=1021012,n i m k k i i r A (3．20)
其中i m 是第i 行游程个数，2/)1(-i m 取整，表示1的游程个数．
由游程长度编码能很容易地计算水平投影而无需变成原来的图像．使用更巧妙的方法也能从游程长度编码计算出垂直和对角线投影．
3．5 二值图像算法
从背景中分离出物体是一个困难的问题，在此将不讨论这个问题．这里假设物体可以从背景中分离，并且使用某一谓词，可以对图像中属于物体的点进行标记．因此，问题就变为如何将一幅图像中所有被标记的点组合成物体图像．这里还假设物体点在空间上是非常接近的．利用空间接近概念可以严格定义，利用此定义研究的算法可以把空间上非常接近的点聚合在一起，构成图像的一个成分（component ）．下面首先引进一些定义，然后讨论有关算法．
3．5．1 定义
(1) 近邻
在数字图像中，一个像素在空间上可能非常接近其它一些像素．在用方格表示的数字图像中，一个像素与其它四个像素有公共边界，并与另外四个像素共享顶角．如果两个像素有公共边界，则把它们称为4－近邻(4-neighbors)．同样，如果两个像素至少共享一个顶角，则称它们为8－近邻．例如，位于],[j i 的像素有四个4－近邻：],1[j i -，],1[j i +，]1,[-j i ，]1,[+j i ．
它的8－近邻包括这四个4－近邻，再加上]1,1[--j i ，]1,1[-+j i ，]1,1[+-j i ，]1,1[++j i ．一
个像素被认为与它的4－近邻是4－连通(4－connected)关系，与它的8－近邻是8－连通关系(如图3．7）．
图3．7 矩形像素网格的4－近邻和8－近邻示意图．像素],[j i 位于图的中心．
(2) 路径
从像素],[00j i 到像素],[n n j i 的路径(path)是指一个像素序列],[00j i ，],[11j i ，．．．， ],[n n j i ，其中像素],[k k j i 是像素],[11++k k j i 的近邻像素，10-≤≤n k ．如果近邻关系是4－连通的，则路径是4－路径；如果是8－连通的，则称为8－路径．图3．8即为路径的两个简单例子．
图3．8 4－路径和8—路径示意图
(3) 前景
图像中值为1的全部像素的集合称为前景(foreground)，用S 表示．
(4) 连通性
已知像素S q p ∈,，如果存在一条从p 到q 的路径，且路径上的全部像素都包含在S 中，则称p 与q 是连通的．
注意，连通性(connectivity)是等价关系．对属于S 的任意三个像素p 、q 和r ，有下列性质：
1．像素p 与p 本身连通（自反性）．
2．如果p 与q 连通，则q 与p 连通（互换性）．
3．如果p 与q 连通且q 与r 连通，则p 与r 连通（传递性）．
(5) 连通成份
一个像素集合，如果集合内的每一个像素与集合内其它像素连通，则称该集合为一个连通成份(connected component)．
[i-1, j ]
[i, j-1] [i, j ] [i, j+1]
[i+1, j ] [i-1,j-1] [i-1,j ] [i-1,j+1] [i,j-1] [i, j ] [i,j+1] [i+1,j-1] [i+1,j ] [i+1,j+1]
(6) 背景
?S（S的补集）中包含图像边界点的所有连通成份的集合称为背景(background)．?S中所有其它元称为洞．考虑下面的两个图像．
首先看左图中有几个洞和几个物体．如果从前景和背景来考虑4－连通，有四个大小为－个像素的物体和一个洞．如果考虑8－连通，那么有一个物体而没有洞．直观地，在这两种情况下出现了不确定性情况．右图为另一个类似的不确定问题．其中如果1是连通的，那么0就应该是不连通的．
为了避免这种难以处理的情况，对物体和背景应使用不同的连通．如果我们对S使用8－连通，那么对?S就应使用4－连通．
(7) 边界
S的边界(boundary)是S中与?S中有4－连通关系的像素集合．边界通常记为S'．
(8) 内部
内部(interior)是S中不属于它的边界的像素集合．S的内部等于S－S'．
(9) 包围
如果从S中任意一点到图像边界的4－路径必须与区域T相交，则区域T包围(surrounds)区域S（或S在T内）．图3．9即为一幅简单二值图像和它的边界、内部、包围示意图．
图3．9 ，内部和包围
3．5．2连通成份标记
在一幅图像中找出连通成份是机器视觉中最常见的运算之一．连通区域内的点构成表示物体的候选区域．机器视觉中的大多数物体都有表面，显然，物体表面点投影到图像平面上会形
成空间上密集的点集．这里应该指出，连通成份算法常常会在二值视觉系统中形成瓶颈效应，原因是连通成份运算是一个全局性的运算，这种算法在本质上是序贯的．如果图像中仅有一个物体，那么找连通成份就没有必要；如果图像中有许多物体，且需要求出物体的特性与位置，则必须确定连通成份．
连通标记算法可以找到图像中的所有连通成份，并对同一连通成份中的所有点分配同一标记．图3．10表示的是一幅图像和已标记的连通成份．在很多应用中，要求在标记连通成份的同时算出连通成份的特征，如尺寸、位置、方向和外接矩形．下面介绍两种连通成份标记算法：递归算法和序贯算法[Jain 1995]．
图3.10 一副图像及其连通成分图像
（１）递归算法
递归算法在串行处理器上的计算效率是很低的，因此，这一算法主要用于并行机上．
算法3．1连通成份递归算法
1．扫描图像，找到没有标记的1点，给它分配一个新的标记L．
3．递归分配标记L给1点的邻点．
3．如果不存在没标记的点，则停止．
4．返回第一步．
（２）序贯算法
序贯算法通常要求对图像进行二次处理．由于这一算法一次仅运算图像的两行，因此当图像以文件形式存贮且空间不允许把整幅图像载入内存时也能使用这一算法．这一算法(见算法3．2)可以查看某一点的邻点，并且可以给像素值为1的邻点分配一个已经使用过的标记．如果图像的邻点有两种不同的标记，则用一个等价表(equivalent table)来记录所有的等价标记．在第二次处理过程中，使用这一等价表来给某一连通成份中所有像素点分配唯一的标记．本算法在从左到右、从上到下扫描图像时，算法仅能查询到某一像素点的4－近邻中的两个近邻点，即上点与左点．设算法已经查到了该像素的这两个近邻点，此时出现三种情况：(1) 如果这两个近邻点中没有一点为1，则该像素点需要一个新的标记．(2) 如果这两个近邻点中只有一点为1，且分配了标记L，那么该像素点的标记也为L．(3) 如果这两个邻点都为1，且已分配了标记L，则该像素点的标记还是L；但是当近邻点被分配了不同标记M与N，则这两个标记被用于了同一组元，应该把它们合并．在这种情况下，应把其中的一个标记（一般选用最小的那个标记）分配给该像素点，并在等价表中登记为等价标记．
等价表包含了给每一连通成份分配唯一标记的信息．在第一次扫描中，所有属于同一连通成份的标记被视为是等价的．在第二次扫描中，从一个等价集(equivalent set)中选择一个标记并分配给连通成份中所有像素点．通常将最小的标记分配给一个连通成份．第二次扫描将给每一连通成份分配唯一的标记．
在找到所有的连通成份后，应该统计等价表，以便删除其中的空格；然后将等价表作为查
找表对图像重新进行扫描，以便重新统计图像中的标记．
计算每一连通成份的面积、一阶矩、二阶矩是序贯连通成份算法的一个部分．当然，必须使用分离变量来累加每一区域的矩信息．当区域合并后，每一区域的矩累计值也应加到一起．算法3．24－连通序贯连通成份算法
1．从左至右、从上到下扫描图像．
2．如果像素点为1，则：
(a) 如果上面点和左面点有一个标记，则复制这一标记．
(b) 如果两点有相同的标记，复制这一标记．
(c) 如果两点有不同的标记，则复制上点的标记且将两个标记输入等价表中作为等价
标记．
(d) 否则给这一个像素点分配一新的标记并将这一标记输入等价表．
3．如果需考虑更多的点，则回到第二步．
4．在等价表的每一等价集中找到最低的标记．
5．扫描图像，用等价表中的最低标记取代每一标记．
3．5．3 欧拉数
在许多应用中，亏格数(genus)或欧拉数可作为识别物体的特征．亏格数定义为连通成份数减去空洞数，
E-
=(3．21)
C
H
其中，E，C和H分别是欧拉数、连通成份数与空洞数．这个式子给出了一个简单的拓朴特征，这种拓扑特征具有平稳、旋转和比例不变特性．图3．11给出了一些例子及其对应的欧拉数．
=
=
E
E2
=
E1-
图3．11 字母“A”、“B”、“i”及它们的欧拉数．注意前景
用了8－连通，而背景用了4－连通．
3．5．4 区域边界
连通成份S的边界是那些属于S且与?S邻接的点集．使用简单的局部运算就可找到边界点．在大多数应用中，我们都想用一特定的顺序跟踪边界点．一般的算法是按顺时针方向跟踪区域的所有点．此处讨论一个简单的边界跟踪算法．
假定物体边界不在图像的边界上（即物体完全在图像内部），边界跟踪算法先选择
一起始点S s ∈，然后跟踪边界直到回到起始点．这种算法概括在算法3．3中．这种算法对尺寸大于1个象素的所有区域都是有效的．用这种算法求区域8－邻点的边界如图3．12(a)所示．为了得到平滑的图像边界，可以在检测和跟踪图像边界后，利用边界点的方向信息来平滑边界。显然，图像边界噪声越大，图像边界点变化越剧烈，图像边界相邻点的方向变化数（与差分链码有一点区别，链码见第七章）也越大．根据这一特点，设置一个边界点方向变化数阈值，把方向变化数大于这一阈值的图像边界点滤除，由此可得到平滑的图像边界。图3.12（b ）所示的是一个经过平滑过的区域边界示意图，其中的方向变化数阈值为1。注意，由于采用8－邻点边界跟踪，因此方向变化数的最大值为4。如果阈值设成4，则对原始边界没有平滑。边界跟踪和平滑常常结合在一起使用，见计算机作业3.5。
图3．12 边界跟踪算法结果，(a) 图像边界跟踪结果；（b ）边界跟踪与平滑结果．
算法3．3 边界跟踪算法
① 从左到右、从上到下扫描图像，求区域S 的起始点0)),(),(()(==k k y k x k s . ② 用c 表示当前边界上被跟踪的像素点．置)(k s c =，记c 左4－邻点为b ，S b ∈． ③ 按逆时针方向从b 开始将c 的8个8－邻点分别记为8,21,,n n n ???，1+=k k , ④ 从b 开始，沿逆时针方向找到第一个S n i ∈，
⑤ 置i n k s c ==)(，1-=i n b ，
⑥ 重复步骤③、④、⑤，直到)0()(s k s =。
3．5．5 距离测量
在许多应用中，找到一幅图像中两个像素点或两个连通成份之间的距离是很有必要的．目前还没有定义数字图像距离的唯一方法，但对所有的像素点p 、q 和 r ，任何距离度量都必须满足下列性质：
1． 0),(≥q p d ，当且仅当q p =时，0),(=q p d
2． ),(),(p q d q p d =
3． ),(),(),(r q d q p d r p d +≤
下面是一些常用的距离函数
欧几里德距离：
2212212211Euclidean )()(]),[],,([j j i i j i j i d -+-= ( 3．22) 街区距离：
.||||2121Block j j i i d -+-= (3．23)
棋盘距离：
|).||,max(|2121Chess j j i i d --= (3．24)
3．5．6 中轴
如果对S 中像素],[j i 的所有邻点],[v u 有下式成立：
)],,([)],,([S v u d S j i d ≥ (3．25)
则S 中像素],[j i 到S 的距离)],,([S j i d 是局部最大值．S 中所有到S 的距离是局部最大值的像素点集合称为对称轴或中轴，通常记为*S ．使用],[v u 4－近邻的中轴变换的一些例子见图
3．13．图3．13b 表明少量噪声会使中轴变换结果产生显著的差异．
由*S 和*S 中每一点到S 的距离能重构原始像素集S ．*S 是S 的简洁表示．*S 可用来表示一个区域的形状．通过去除*S 中与S 距离较小的像素点，可以生成一个简化的*S 集．
中轴可作为物体的一种简洁表示．但是，二值图像中的区域也可用其边界来表示．边界跟踪算法可用来获得表示边界的序列点．在第七章还将讨论用链码来简洁地表示边界的方法．对任意物体，边界将是区域的简洁表示．但要明确给定像素点是否在某一区域内，中轴则是更好的表示，因为使用中轴上的像素点和每一个给定像素点的最大距离圆盘（中轴距离变换），可以很容易地检测出给定像素是否在中轴定义的区域中．
图 3．13 中轴变换举例
3．5．7 细化
细化(thinning)是一种图像处理运算，可以把二值图像区域缩成线条，以逼近区域的中心线，也称之为骨架或核线．细化的目的是减少图像成份，直到只留下区域的最基本信息，以便进一步分析和识别．虽然细化可以用在包含任何区域形状的二值图像，但它主要对细长形(而不是凸圆形或水滴状)区域有效．细化一般用于文本分析预处理阶段，以便将文本图像中线条图画或字符笔画表示成单像素线条．细化要求如下：
(1) 连通图像区域必须细化成连通线结构．
(2) 细化结果最少应该是8－连通（下面将要解释）．
(3) 保留近似终止线的位置．
(4) 细化结果应该近似于中轴线．
(5) 由细化引起的附加突刺(短分支)应该是最小的．
细化结果应该保证第一条要求中所定义的连通性，这一点是最基本的要求，它保证了连通线结构的数量等于原始图像中连通区域的数量．第二条要求保证所得到的线条总是含有8－连通图像的最小数量．第三条要求说明终止线位置应该保持不变．细化可以通过迭代方式不断去除边界点来实现，重要的是在迭代过程中不要去除端点像素，因为这样不仅会缩短细化线，丢掉结构信息，而且不能保持其位置不变．第四条要求说明所得线段应能最好地逼近原始区域的中线，如两个像素点宽的竖线或水平线的真正中线应该位于这两个像素之间半个像素间距的位置．在数字图像中表示半个像素间距是不可能的，因此得到的结果是一条位于原直线一侧的直线．第五条要求没有明确指出噪声的影响控制到最低程度，因为判断噪声本身是一件很难的事．一般不希望原始区域含有会引起突刺的隆起，但当某些较大隆起是区域特征时，却必须识别它们．应该指出，某些细化算法有去除突刺的参数，不过最好将细化和去除噪声分开进行，这是由于某些情况下不需要的突刺，可能是另一些情况下所需要的短线．因此，最好的办法是先进行细化，然后单独去除长度低于某一特定最小值的任何突刺．
一种常用的细化手段是在至少33?邻域内检查图像的每一点，剥去区域边界．一次剥去一层图像，直至区域被细化成一条线．这一过程是用迭代法实现的，如算法３．4．在每次迭代时，每一个像素点用n n ?窗函数检查，为了保持连通性或线末端位置，将单像素厚的边界擦除．在图3．14中将会看到，在每次迭代中，值为1的外层区域就是用这种方式削掉的．当迭代结果没有变化时，迭代过程结束，图像得到细化
算法３．４ ４－近邻细化迭代算法
对于每一个像素，如果
（１）没有上近邻（下近邻＼左近邻＼右近邻）
（２）不是孤立点或终止线
（３）去除该像素点不会断开区域
则去除该像素点．
重复这一步骤直到没有像素点可以去除．
图3．14 细化手写体“华”的迭代过程．(a) 原图像，(b)—(f)为
五次迭代过程，每次迭代削去一层边界．
3．5．8 扩展与收缩
图像中的一个连通成份可以进行全方位的扩展(expanding)或收缩(shrinking)．如果某一连通
成份可以变化，使得一些背景像素点变成1，这一运算就称为扩展．如果物体像素点全方位地消减或变为0时，则称为收缩．一种简单的扩展与收缩实现方法如下：
扩展：如果近邻点是1，则将该点从0变为1．
收缩：如果近邻点是0，则将该点从1变为0．
这样，收缩可以看作是扩展背景．这类运算的例子见图3．15．
需要指出，扩展与收缩这样简单的运算可以完成非常有用而又貌似很复杂的运算．下面引进符号
)(k S ： S 扩展k 倍．
)(k S -：S 收缩k 倍．
其中下列性质必须满足：
)()()(n m m n n m S S S ---≠≠
k k S S -?)(
k k S S )(-?
先扩展后收缩算法能补上不希望存在的洞，如图3.15（b ）（d ）所示；先收缩后扩展算法则能去除孤立的噪声点，见图3．15（c ）（e ）．请注意，扩展与收缩可用来确定孤立组元或簇．注意，扩展后收缩有效地填满了空洞却没有去除噪声；相反，收缩后扩展能去除噪声却没有填满空洞．在地形图像处理和膨胀与腐蚀运算中，扩展与收缩算法的一般形式被广泛地用于许多任务中．
图3．15 对字母“h ”收缩与扩展算法实验结果．（a ）原始噪声图像；(b) 扩展运算；（c ）收缩
运算；（d ）扩展后收缩运算；（e ）收缩后扩展运算．
3．6 形态算子
数学形态（morphology ）这一名称是从形状研究得来的．这种方法也说明了一个事实，即在许多机器视觉算法设计中，根据形状来思考问题是最自然，也是最容易的．形态方法有助于进行基于形状或图形思考．形态方法中图像信息的基本单元是二值像素．
任意两个二值图像A 和B 的交是一个二值图像，记为B A ，即A 与B 中皆为1的图像点
p 的集合：
{}B p A p p B A ∈∈=,| (3．26) A 和B 的并，记为B A ，是一个二值图像，是A 或B 或两者中为1的所有图像点p 的集合，用符号表示为：
{}B p or A p p B A ∈∈=| (3．27) 设Ω是全值二值图像（所有的像素值皆为１），A 是二值图像．A 的补集是A 中1与0互相交换后的二值图像，即：
?{}A p p p A ?Ω∈=,| (3．28) 标号为],[j i 与],[l k 的两像素点p 和q ，其向量和是标号为],[l j k i ++的像素点q p +．向量差是标号为],[l j k i --的像素点q p -．
若A 是二值图像，p 是二值图像B 中的一个像素点，则A 被p 平移后的二值图像由下式表示：
{}A a p a A p ∈+=| (3．29)
即二值图像A 被一个像素点p 平移是指将A 的原点移到p
(1) 膨胀
已知二值图像A ，如果n b b b A A A ,,,21???是由二值图像{}n b b b B ,,21 =中像素值为1的点平移得到的，则A 由B 平移的并称为A 被B 膨胀，即；
i i b b A
B A =⊕ (3．30)
膨胀具有结合性、交换性．这样，在进行膨胀的步骤序列中，完成运算的顺序就不重要了．这就允许我们将一个复杂的形状拆成几个简单的形状，然后重新组合成为膨胀序列．
(2) 腐蚀
腐蚀是膨胀的相反过程．二值图像A 经二值图像B 腐蚀后在p 点仍为1的充分必要条件是：B 平移到p 后，B 中的1像素也是A 中的1像素．A 被B 腐蚀可用下式表示：
}|{A B p B A p ?=Θ (3．31)
二值图像B 常常是规则图像，是作用于图像中的一种探针，也称为结构元．腐蚀在许多应用中起着十分重要的作用．结构元对一幅图像进行腐蚀会生成一幅包含结构元所有位置的图像． 图3．16到3．17是一个倒T 形结构元对一个简单物体进行膨胀与腐蚀运算的示意图．用结构元进行膨胀或腐蚀运算也可以描述为：结构元的原点像素经过待膨胀的二值图像中所有1像素点时，对应结构元所有１像素的待膨胀二值图像像素置为１像素；在腐蚀运算过程中，结构元的原点像素经过待腐蚀的二值图像中所有1像素点时，如果结构元中有一个１像素没有对应待腐蚀二值图像的１像素，则对应结构元原点的待腐蚀二值图像１像素置为０．
图3．16 原始测试图像A(左)与结构元B(右)．注意结构元B的原点
比B中的其它像素点要黑一些．
(a) (b)
图3．17 膨胀与腐蚀实验结果．（a）A被B膨胀，其中原始像素A的边界用粗黑线表示．(b)A被B腐蚀，其中原始像素A的边界用粗黑线表示．
膨胀和腐蚀展示了几何的而不是逻辑的对偶特性，这种特性也包含了几何互补性与逻辑互补性．二值图像的几何互补称为它的反射．二值图像B的反射B'是与B关于原点对称的二值图像，即：
B∈
-
p
='(3．32)
}
|
{B
p
膨胀与腐蚀的对偶性由下面关系式表示：
Θ
A'
⊕(3．33)
=
B
B
A
=
Θ(3．34)
⊕
A'
B
A
B
与几何对偶性相比，逻辑对偶性的关系式为：
A
=(3．35)
A
B
B
B
=(3．36)
A
A
B
上式也称为DeMorgan定律．
腐蚀与膨胀常常用于图像滤波．如果已知噪声特性，则可选用适当的结构元和一系列腐蚀与膨胀运算来去除噪声．请注意，这样的滤波会影响图像中物体的形状．
数学形态中的基本运算可以组合成很复杂的运算．用同一结构元(探针)腐蚀后再膨胀可去除比结构元小的所有区域像素点，而留下其余部分，这一顺序称为“开”运算．如，用一圆形
的探针将所有比探针小的区域删除，实现抑制加性空域细节的滤波．
与上述处理顺序相反的过程是膨胀后再腐蚀，称为“关”运算，这种顺序会填满比探针小的孔洞和凹状区．这些运算见图3．18和图3．17，其中结构元采用了相同的T形结构．这里仍然存在一个问题是去除的图像可能与保留的图像一样重要．这样的滤波器可用来抑制空域特征或区分基于尺寸的物体类型．所用的结构元不一定是简洁的或规则的，可以是任意模式的像素点集合．这样可以探测到具有一定分布的图像特征．
关于数学形态的详细内容参见[Dougherty 1988, Haralick 1992] ,关于数学形态在字符识别中的应用见[Mitchell 1989].
图3．18“开”运算．左：腐蚀；右：膨胀．图中的粗黑线表示原始图像边界．
图3．19 “关”运算．左：膨胀；右：腐蚀．图中的粗黑线表示原始图像边界．
思考题
3．1考虑一幅二进制图像如图3.20所示．
(a) 分别使用4－连通和8－连通，求黑像素集合中包含有多少个区域．
(b) 分别使用4－连通和8－连通，求白像素集合中包含有多少个区域．
图3.20 题3.1图
3．2假定图3.21的白色像素是边缘点．请分别使用4－连通和8－连通细化算法去除多余的白点（把去除的白点用阴影线表示）．
图3.21 题3.2图
3．3连通域标记算法是许多应用中的“瓶颈”问题．连通域标记可以看作是视觉系统中连接高层和低层算法的桥梁．请你给出一种连通标记快速算法设计的构思？请问能否开发出一种并行算法，为什么？
计算机练习题
3．1开发一个算法来计算区域面积和游程代码的第一、二阶矩．
3．2开发一个中轴算法．将这一算法作用于具有不同规则物体的二值图像上，并研究这种技术在表示物体形状时的优点与缺点．
3．3构造一种算法来实现膨胀与收缩运算．使用这些算法来实现二值图像中不同噪声的滤波．3．4设计一个机器视觉系统，该系统可以获取场景的二值图像并识别物体．考虑一些常用物体，如，硬币、钢笔、笔记本和其它的办公用品．根据你在本章中学到的物体特征来建立物体识别策略，完成所有的运算并测试你的系统．
《数据结构与算法设计》 实验报告 ——实验四 学院： 班级： 学号： 姓名：
一、实验目的 1. 通过实验实践、巩固线性表的相关操作； 2. 熟悉VC 环境，加强编程、调试的练习； 3. 用C 语言实现线性表的抽象数据类型，实现线性表构造、插入、取数据等基本操作； 4. 理论知识与实际问题相结合，利用上述基本操作实现三种排序并输出。 二、实验内容 从键盘输入10个数，编程实现分别用插入排序、交换排序、选择排序算法进行排序，输出排序后的序列。 三、程序设计 1、概要设计 为了实现排序的功能，需要将输入的数字放入线性表中，进行进一步的排序操作。 (1)抽象数据类型： ADT SqList{ 数据对象：D={|,1,2,,,0}i i a a ElemSet i n n ∈=≥ 数据关系：R1=11{,|,,1,2,,}i i i i a a a a D i n --<>∈= 基本操作： InPut(SqList &L) 操作结果：构造一个线性表L 。 OutPut(SqList L) 初始条件：线性表L 已存在。 操作结果：按顺序在屏幕上输出L 的数据元素。 InsertSort(SqList &L) 初始条件：线性表L 已存在。 操作结果：对L 的数据元素进行插入排序。 QuickSort(SqList &L) 初始条件：线性表L 已存在。 操作结果：对L 的数据元素进行快速排序。 SelectSort(SqList &L) 初始条件：线性表L 已存在。 操作结果：对L 的数据元素进行选择排序。 }ADT SqList ⑵主程序流程 由主程序首先调用InPut(L)函数创建顺序表，调用InsertSort(L)函数进行插入排序， 调用OutPut(L)函数显示排序结果。调用QuickSort(L)函数进行交换排序，调用OutPut(L) 函数显示排序结果。调用SelectSort(L)函数进行选择排序，调用OutPut(L)函数显示排序 结果。 ⑶模块调用关系 由主函数模块调用创建顺序表模块，排序模块与显示输出模块。
------------------------------------------------------------------------------------------------------------------------------ 北理工《自动控制理论1》在线作业 一、单选题： 1.（单选题）系统稳定的充分必要条件是其特征方程式的所有根均在根平面的（）。(满分 A右半部分 B左半部分 C实轴上 D虚轴上 正确:B 2.（单选题）最小相角系统闭环稳定的充要条件是（） (满分 A奈奎斯特曲线不包围（-1，j0）点 B奈奎斯特曲线包围（-1，j0）点 C奈奎斯特曲线顺时针包围（-1，j0）点 D奈奎斯特曲线逆包围（-1，j0）点 正确:A 3.（单选题）两个或多个环节具有同一输入信号，而以各自环节输出信号代数和作为系统总输出信号，这种结构成为（）。 (满分 A串联 B并联 C开环 D闭环 正确:B 4.（单选题）典型欠阻尼二阶系统，当开环增益K增加时，系统（） (满分 A阻尼比增大，超调量增大 B阻尼比减小，超调量增大 C阻尼比增大，超调量减小 D无阻尼自然频率减小 正确: 5.（单选题）两典型二阶系统的超调量δ％相等，则此两系统具有相同的（）。 (满分 A自然频率 B相角裕度 C阻尼振荡频率 D开环增益K 正确: 6.（单选题）对于代表两个或两个以上输入信号进行（）的元件又称比较器。 (满分:) A微分 B相乘 C加减 D相除 正确: 7.（单选题）状态变量具有（）的特征。 (满分:)
------------------------------------------------------------------------------------------------------------------------------ A唯一性 B特征值不变性 C特征值可变 D以上均不正确 正确: 8.（单选题）频率从0变化到+∞时，延迟环节频率特性极坐标图为（）。 (满分:) A圆 B半圆 C椭圆 D双曲线 正确: 9.（单选题）按照系统是否满足叠加原理可分为（）。 (满分:) A线性系统与非线性系统 B计算机控制系统和模拟系统 C开环系统和闭环系统 D定值控制系统和伺服系统 正确: 10.（单选题）已知单位反馈控制系统在阶跃函数作用下，稳态误差为常数，则此系统为（）。(满分:) A0型系统 BI型系统 CII型系统 D高阶系统 正确: 11.（单选题）用实验法求取系统的幅频特性时，一般是通过改变输入信号的（）来求得输出信号的幅值。 (满分:) A相位 B频率 C稳定裕量 D时间常数 正确: 12.（单选题）Bode图包括幅频特性图和相频特性图，横坐标均为（）。 (满分:) A时间 B弧度 C角频率 D相位 正确: 13.（单选题）系统的频率特性（） (满分:) A是频率的函数 B与输入幅值有关 C与输出有关 D与时间t有关 正确:
1.系统稳定的充分必要条件是其特征方程式的所有根均在根平面的 （）。 A.右半部分 B.左半部分 C.实轴上 D.虚轴上 【参考答案】: B 2.最小相角系统闭环稳定的充要条件是（） A.奈奎斯特曲线不包围（-1，j0）点 B.奈奎斯特曲线包围（-1，j0）点 C.奈奎斯特曲线顺时针包围（-1，j0）点 D.奈奎斯特曲线逆包围（-1，j0）点 【参考答案】: A 3.两个或多个环节具有同一输入信号，而以各自环节输出信号代数和作 为系统总输出信号，这种结构成为（）。 A.串联 B.并联 C.开环 D.闭环 【参考答案】: B 4.典型欠阻尼二阶系统，当开环增益K增加时，系统（） A.阻尼比增大，超调量增大 B.阻尼比减小，超调量增大 C.阻尼比增大，超调量减小 D.无阻尼自然频率减小 【参考答案】: B 5.两典型二阶系统的超调量δ％相等，则此两系统具有相同的（）。 A.自然频率 B.相角裕度 C.阻尼振荡频率 D.开环增益K 【参考答案】: B 6.对于代表两个或两个以上输入信号进行（）的元件又称比较器。 A.微分 B.相乘 C.加减 D.相除
【参考答案】: C 7.状态变量具有（）的特征。 A.唯一性 B.特征值不变性 C.特征值可变 D.以上均不正确 【参考答案】: B 8.频率从0变化到+∞时，延迟环节频率特性极坐标图为（）。 A.圆 B.半圆 C.椭圆 D.双曲线 【参考答案】: A 9.按照系统是否满足叠加原理可分为（）。 A.线性系统与非线性系统 B.计算机控制系统和模拟系统 C.开环系统和闭环系统 D.定值控制系统和伺服系统 【参考答案】: A 10.已知单位反馈控制系统在阶跃函数作用下，稳态误差为常数，则此 系统为（）。 A.0型系统 B.I型系统 C.II型系统 D.高阶系统 【参考答案】: A 11.用实验法求取系统的幅频特性时，一般是通过改变输入信号的（） 来求得输出信号的幅值。 A.相位 B.频率 C.稳定裕量 D.时间常数 【参考答案】: B 12.Bode图包括幅频特性图和相频特性图，横坐标均为（）。 A.时间 B.弧度 C.角频率 D.相位
偏微分方程数值解大作业
目录 第一题 (3) 第二题 (7) 第三题 (16) 第四题 (20) 第五题 (26) 第六题（附加题1） (39) 第七题（附加题2） (45) 第八题（附加题3） (51)
第一题 习题1 3. （1）解曲线图 图1 （2）误差曲线图
图2 （3）表格 表1 部分点处精确解和取不同步长时所得的数值解 表2 取不同步长时部分结点处数值解的误差的绝对值和数值解的最大误差
（4）MATLAB源代码 M=64; a=0; b=pi/2; h=(b-a)/M; x=[a+h:h:b-h]; u=zeros(M-1,M-1); u(1,1)=(2/h^2)+(x(1)-1/2)^2; u(1,2)=-(1/h^2); u(M-1,M-1)=(2/h^2)+(x(M-1)-1/2)^2; u(M-1,M-2)=-(1/h^2); for i=2:M-2 u(i,i-1)=-(1/h^2); u(i,i)=(2/h^2)+(x(i)-1/2)^2; u(i,i+1)=-(1/h^2); end f=zeros(M-1,1) f(1)=(x(1).*x(1)-x(1)+5/4).*sin(x(1)); f(M-1)=(x(M-1).*x(M-1)-x(M-1)+5/4).*sin(x(M-1))+1/h^2; for j=2:M-2 f(j)=(x(j).*x(j)-x(j)+5/4).*sin(x(j)); end
y=inv(u)*f; true=sin(x); plot(x,y'-true)
1.一元多项式相加(10分) 成绩: 10 / 折扣: 0.8 题目说明： 编写一元多项式加法运算程序。要求用线性链表存储一元多项式（参照 课本）。该程序有以下几个功能： 1. 多项式求和 输入：输入三个多项式，建立三个多项式链表Pa、Pb、Pc （提示：调用CreatePolyn(polynomial &P,int m)。 输出：显示三个输入多项式Pa、Pb、Pc、和多项式Pa+Pb、多项式Pa+Pb+Pc （提示：调用AddPolyn(polynomial &Pa, polynomial Pb), 调用 PrintPolyn(polynomial P))。 0. 退出 输入： 根据所选功能的不同，输入格式要求如下所示（第一个数据是功能选择编号，参见测试 用例）： ? 1 多项式A包含的项数，以指数递增的顺序输入多项式A各项的系数（整数）、指数（整数） 多项式B包含的项数，以指数递增的顺序输入多项式B各项的系数（整数）、指数（整数） 多项式C包含的项数，以指数递增的顺序输入多项式C各项的系数（整数）、指数（整数） ?0 －－－操作终止，退出。 输出： 对应一组输入，输出一次操作的结果（参见测试用例）。 ? 1 多项式输出格式：以指数递增的顺序输出: <系数,指数>,<系数,指数>,<系数,指数>,参见测试用例。零多项式的输出格式为<0,0> ?0 无输出 1.
#include 一. (10分) 用三角分解（LU 分解）求解下方程组,要求写出L,U 矩阵： 1232644145361182x x x -?????? ? ? ? -= ? ? ? ? ? ?-???? ??. 二. (10分) 已知矩阵6 37398785A -?? ? =- ? ?--?? ,求1cond()A 和cond()A ∞,要求计算过程保留三位 有效数字,并简要分析所得结果. 三. (10分) 设矩阵1001005a A b b a ?? ? = ? ??? ,且0det()A ≠,试求用,a b 表示的求解线性方程组 Ax d =的Jacobi 及Gauss-Seidel 迭代法收敛的充分必要条件. 四. (10分) 试确定下求积公式中的待定参数,使求积公式的代数精确度尽量高,并指明所确定的求积公式具有的代数精确度 []20 002 '' ()()()()()h h f x dx f f h h f f h α??≈ ++-??? . 五. (10分) 已知非线性方程240x x +-=在014.x =附近有根，试构造一种收敛的迭代格式,并说明理由. 六. (10分) 求形如e (,)bx y a a b =为常数的经验公式,使它能和下表给出的数据相拟合 x １ ２ ３ ４ ５ ６ ７ ８ y 15.3 20.5 27.4 36.6 49.1 65.6 87.8 117.6 七. (10分) 分别用Euler 法和改进Euler 法求解下问题的数值解,取01.h =,计算过程保留四位小数. 00201',., (). y x y x y =+≤≤?? =? 八. (15分) 用下数据表构造不超过3次的插值多项式,建立导数型插值误差公式,并证明. 889数据结构 考试内容： 数据结构主要考查考生以下几个方面： 1.理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。 2.掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。 3.能够选择合适的数据结构和方法进行问题求解。 应掌握的具体内容为： 一、线性表 （一）线性表的定义和基本操作 （二）线性表的实现 1.顺序存储结构 2.链式存储结构 3.线性表的应用 二、栈、队列和数组 （一）栈和队列的基本概念 （二）栈和队列的顺序存储结构 （三）栈和队列的链式存储结构 （四）栈和队列的应用 （五）特殊矩阵的压缩存储 三、树与二叉树 （一）树的概念 （二）二叉树 1.二叉树的定义及其主要特征 2.二叉树的顺序存储结构和链式存储结构 3.二叉树的遍历 4.线索二叉树的基本概念和构造 5.二叉排序树 6.平衡二叉树 （三）树、森林 1.书的存储结构 2.森林与二叉树的转换 3.树和森林的遍历 （四）树的应用 1.等价类问题 2.哈夫曼（Huffman）树和哈夫曼编码 四、图 （一）图的概念 （二）图的存储及基本操作 1.邻接矩阵法 2.邻接表法 （三）图的遍历 1.深度优先搜索 2.广度优先搜索 （四）图的基本应用及其复杂度分析 1.最小（代价）生成树 2.最短路径 3.拓扑排序 4.关键路径 五、查找 （一）查找的基本概念 （二）顺序查找法 （三）折半查找法 （四）B-树 （五）散列（Hash）表及其查找 （六）查找算法的分析及应用 六、内部排序 （一）排序的基本概念 （二）插入排序 1.直接插入排序 2.折半插入排序 （三）起泡排序（bubble sort） （四）简单选择排序 （五）希尔排序（shell sort） （六）快速排序 （七）堆排序 （八）二路归并排序（merge sort） （九）基数排序 （十）各种内部排序算法的比较 （十一）内部排序算法的应用 题型和分值 填空题20分、选择题30分、问答题70分、算法题30分 参考书目 数据结构（C语言版）严蔚敏吴伟民清华大学出版社 课程编号：12000044 北京理工大学2009-2010学年第二学期 2008级计算机学院《数值分析》期末试卷A 卷 班级 学号 姓名 成绩 注意：① 答题方式为闭卷。 ② 可以使用计算器。 请将填空题和选择题的答案直接填在试卷上，计算题答在答题纸上。 一、 填空题（每空2分，共30分） 1. 设函数f (x )区间[a ，b]内有二阶连续导数，且f (a )f (b )<0, 当 时，用双点 弦截法产生的解序列收敛到方程f (x )=0的根。 2. n 个求积节点的插值型求积公式的代数精确度至少为______次，n 个求积节点的高斯 求积公式的代数精度为 。 3. 已知a =3.201，b =0.57是经过四舍五入后得到的近似值，则a ?b 有 位有 效数字，a +b 有 位有效数字。 4. 当x =1，-1，2时，对应的函数值分别为f (-1)=0，f (0)=2，f (4)=10，则f (x )的拉格朗 日插值多项式是 。 5. 设有矩阵?? ????-=4032A ，则‖A ‖1＝_______。 6. 要使...472135.420=的近似值的相对误差小于0.2%，至少要取 位有效数字。 7. 对任意初始向量0()X 和常数项N ，有迭代公式1()()k k x Mx N +=+产生的向量序列 {}() k X 收敛的充分必要条件是 。 8. 已知n=3时的牛顿-科特斯系数,8 3,81)3(1) 3(0 ==C C 则=) 4(2C ，=) 3(3C 。 9. 三次样条函数是在各个子区间上的 次多项式。 10. 用松弛法 (9.0=ω)解方程组??? ??=+-=++--=++3 1032202412 25322 321321x x x x x x x x x 的迭代公式是 。 一、选择题 1、从逻辑结构上可以把数据结构分为【 C 】。 A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 2、在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）之前插入一个新元素时，需要从后向前依次后移【 B 】个元素。 A、n-i B、n-i+1 C、n-i-1 D、i 3、链表结构不具有下列【 B 】特点。 A、插入和删除无需移动元素 B、可随机访问链表中的任意元素 C、无需实现分配存储空间 D、所需空间与结点个数成正比。 4、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行【 C 】。 A、s->next = p->next; p->next = s; B、p->next = s->next; s->next = p; C、q->next = s; s->next = p; D、p->next = s; s->next = q; 5、一个栈的入栈序列是1，2，3，4，5，则栈不可能输出的序列是【C 】。 A、54321 B、45321 C、43512 D、12345 6、判断一个队列Q（元素最多为M个）为空的条件是【 C 】。 A、Q->rear – Q->front = M B、Q->rear – Q->front -1 ==M C、Q->rear == Q->front D、Q->rear + 1 == Q->front 7、在一个链队列中，假设f和r分别指向队首和队尾，则插入s所指结点的运算是【A 】。 A、r->next = s; r=s; B、f->next = s; f=s; C、s->next = r; r=s; D、s->next = f; f=s; 8、深度为5的二叉树至多有【 A 】个结点。 A、31 B、32 C、16 D、10 9、在一非空二叉树的中序遍历序列中，根结点的右边【A 】。 北京理工大学2014-2015学年第二学期 2013级数值代数与数值分析期末试题B 卷 一、（10 31.953=有5位有效数字，试求方程233204 x x -+ =的两个根，使它们至少有4位有效数字。 二、（10分）已知矩阵100024024A ?? ?= ? ?-?? ，求A 的1-范数，∞-范数，F-范数，2-范数。 三、（15分）用LU 分解求解方程组12321374321261513x x x ?????? ??? ?= ??? ? ??? ??????? ，要求写出LU 矩阵。 四、（15分）用迭代公式()1,0,1,k k k x x Ax b k α+=+-= 求解方程组12323121x x ??????= ? ? ?-???? ??，求α的范围使迭代收敛。 五、（10分）用插值多项式理论证明：00n n i k k i x k x i i k ==≠??- ?= ?- ???∑∏。 六、（10分）已知下面的数据表，写出用最小二乘法求形如2 y a bx =+的经验公式的正则方程组。 七、（15分）已知方程1552sin 0x x -+=在03x =附近有根，试构造一种收敛的迭代格式，并说明理由。 八、（ 3次的插值多项式，建立导数型插值误差公式，并证明。 注：本课程自2014级起改为大二上学期必修和大三上学期选修两部分，名称分别为数值计算方法Ⅰ和数值计算方法Ⅱ。 北京理工大学2016-2017学年第一学期 2015级数值计算方法Ⅰ期末试题A 卷 一、（10 30.952=有5位有效数字，试求方程233104 x x -+ =的两个根，使它们至少有4位有效数字。 二、（10分）已知矩阵100024024A ?? ?= ? ?-?? ，求A 的1-范数，2-范数，1-条件数，2-条件数。 三、（15分）用LU 分解求解方程组123212124312261526x x x ?????? ??? ?= ??? ? ??? ??????? ，要求写出LU 矩阵。 四、（10分）已知{}k α收敛于a ，且1lim 0k k k a c a αα+→∞-=≠-，试构造一种收敛速度更快的序列。 五、（15分）用收敛的迭代法解下列线性方程组，要求写出迭代矩阵。 （1）12312251112022143x x x -?????? ??? ?= ??? ? ??? ??????? ； （2）12311116101210211012x x x --?????? ??? ?-= ??? ? ??? ?-??????。 六、（15分）用迭代公式()1,0,1,k k k x x Ax b k α+=+-= 求解方程组12323121x x ??????= ? ? ?-??????，求α的范围使迭代收敛。 七、（10分）用插值多项式理论证明：00n n i k k i x k x i i k ==≠??- ?= ?- ???∑∏。 八、（20分）用下表数据构造不超过3次的插值多项式，建立导数型插值误差公式，并证明。 2015级题目的分值不保证正确。 北理工《实用数据结构与算法》在线作业 一、单选题： 1.（单选题）当两个元素比较出现反序时就相互交换位置的排序方法称为()。 (满分 A归并排序 B选择排序 C交换排序 D插入排序 正确:C 2.（单选题）设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为() (满分 Afront=front+1 Bfront=(front+1)%m Crear=(rear+1)%m Dfront=(front+1)%(m+1) 正确:D 3.（单选题）快速排序方法在()情况下最不利于发挥其长处。 (满分 A被排序的数据量太大 B被排序数据中含有多个相同值 C被排序数据已基本有序 D被排序数据数目为奇数 正确:C 4.（单选题）具有65个结点的完全二叉树其深度为（根的层次号为1）()。 (满分 A8 B7 C6 D5 正确: 5.（单选题）稀疏矩阵一般的压缩存储方法有两种，即()。 (满分 A二维数组和三维数组 B三元组表和散列表 C三元组表和十字链表 D散列表和十字链表 正确: 6.（单选题）从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为()排序法。 (满分:) A插入 B选择 C交换 D二路归并 正确: 7.（单选题）下列排序方法中效率最高的排序方法是()。 (满分:) A起泡排序 B堆排序 C快速排序 D直接插入排序 正确: 8.（单选题）栈与一般的线性表的区别在于()。 (满分:) A数据元素的类型不同 B运算是否受限制 C数据元素的个数不同 北理工《自动控制理论2》在线作业 -0001 试卷总分:100 得分:0 一、单选题(共10 道试题,共30 分) 1.基于能量的稳定性理论是由（）构建的。 A.Lyapunov B.Kalman C.Routh D.Nyquist 正确答案:A 2.引入状态反馈的目的是（）。 A.配置系统的极点 B.改变系统的能控性 C.改变系统的能观性 D.使得系统能观 正确答案:A 3.齐次状态方程就是指状态方程中不考虑（）的作用。 A.输入 B.输出 C.状态 D.系统 正确答案:A 4.对于单变量系统，特征方程的根就是传递函数的（）。 A.零点 B.极点 C.拐点 D.死点 正确答案:B 5.齐次状态方程的解就是系统在无外力作用下由初始条件引起的（）。 A.自由运动 B.强迫运动 C.离心运动 D.旋转运动 正确答案:A 6.线性系统的系数矩阵A如果是非奇异的，则系统存在（）平衡点。 A.一个 B.两个 C.三个 D.无穷多个 正确答案:A 7.原系统的维数是n，则全维状态观测器的维数是（）。 A.2n B.n C.3n D.n-1 正确答案:A 8.能够完整的描述系统运动状态的最小个数的一组变量称为（）。 A.状态变量 B.状态空间 C.状态方程 D.输出方程 正确答案:A 9.由初始状态所引起的自由运动称为状态的（）。 A.零输入响应 B.零状态响应 C.输入响应 D.输出响应 正确答案:A 10.以状态变量为坐标轴所构成的空间，称为（）。 A.状态变量 B.状态空间 C.状态方程 D.输出方程 正确答案:B 二、多选题(共10 道试题,共30 分) 1.由动态方程导出可约传递函数时，表明系统是（）。 A.可控不可观测 B.可观测不可控 C.不可控不可观测 课程编号：12000044 北京理工大学2010-2011学年第一学期 2009级计算机学院《数值分析》期末试卷A 卷 班级 学号 姓名 成绩 注意：① 答题方式为闭卷。 ② 可以使用计算器。 请将填空题和选择题的答案直接填在试卷上，计算题答在答题纸上。 一、 填空题 （2 0×2′） 1. 设x =0.231是精确值x *=0.229的近似值，则x 有 位有效数字。 2. 设 ?? ????-=? ?????-=32,1223X A ，‖A ‖∞＝___ ____，‖X ‖∞＝__ _____， ‖AX ‖∞≤____ ___ (注意：不计算‖AX ‖∞的值) 。 3. 非线性方程f (x )=0的迭代函数x =?(x )在有解区间满足 ，则使用该迭代函 数的迭代解法一定是局部收敛的。 4. 若f (x )=x 7－x 3＋1，则f [20,21,22,23,24,25,26,27]= ， f [20,21,22,23,24,25,26,27,28]= 。 5. 区间[a ,b ]上的三次样条插值函数S (x )在[a ,b ]上具有直到 阶的连续导数。 6. 当插值节点为等距分布时，若所求节点靠近首节点，应该选用等距节点下牛顿差商 公式的 （填写前插公式、后插公式或中心差分公式），若 所求节点靠近尾节点，应该选用等距节点下牛顿差商公式的 （填写前插公式、后插公式或中心差分公式）；如果要估计结果的舍入误差，应该选用插值公式中的 。 7. 拉格朗日插值公式中f (x i )的系数a i (x )的特点是：=∑=n i i x a 0)( ；所以当 系数a i (x )满足 ，计算时不会放大f (x i )的误差。 8. 要使 20的近似值的相对误差小于0.1%，至少要取 位有效数字。 9. 对任意初始向量X (0)及任意向量g ，线性方程组的迭代公式x (k +1)=Bx (k )+g (k =0,1,…)收 敛于方程组的精确解x *的充分必要条件是 。 10. 由下列数据所确定的插值多项式的次数最高是 。 2019年北京理工大学889《数据结构》考试大纲 考试内容： 数据结构主要考查考生以下几个方面： 1.理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。 2.掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。 3.能够选择合适的数据结构和方法进行问题求解。 应掌握的具体内容为： 一、线性表 （一）线性表的定义和基本操作 （二）线性表的实现 1.顺序存储结构 2.链式存储结构 3.线性表的应用 二、栈、队列和数组 （一）栈和队列的基本概念 （二）栈和队列的顺序存储结构 （三）栈和队列的链式存储结构 （四）栈和队列的应用 （五）特殊矩阵的压缩存储 三、树与二叉树 （一）树的概念 （二）二叉树 1.二叉树的定义及其主要特征 2.二叉树的顺序存储结构和链式存储结构 3.二叉树的遍历 4.线索二叉树的基本概念和构造 5.二叉排序树 6.平衡二叉树 （三）树、森林 1.书的存储结构 2.森林与二叉树的转换 3.树和森林的遍历 （四）树的应用 1.等价类问题 2.哈夫曼（Huffman）树和哈夫曼编码 四、图 （一）图的概念 （二）图的存储及基本操作 1.邻接矩阵法 2.邻接表法 （三）图的遍历 1.深度优先搜索 2.广度优先搜索 （四）图的基本应用及其复杂度分析 1.最小（代价）生成树 2.最短路径 3.拓扑排序 4.关键路径 五、查找 （一）查找的基本概念 （二）顺序查找法 （三）折半查找法 （四）B-树 （五）散列（Hash）表及其查找 （六）查找算法的分析及应用 六、内部排序 （一）排序的基本概念 （二）插入排序 1.直接插入排序 2.折半插入排序 （三）起泡排序（bubble sort） （四）简单选择排序 （五）希尔排序（shell sort） （六）快速排序 （七）堆排序 （八）二路归并排序（merge sort） （九）基数排序 （十）各种内部排序算法的比较 （十一）内部排序算法的应用 题型和分值 填空题20分、选择题30分、问答题70分、算法题30分 参考书目 数据结构（C语言版）严蔚敏吴伟民清华大学出版社 2017秋17春北理工《自动控制理论I》在线作业 一、单选题（共20 道试题，共60 分。） 1. 开环控制系统特征是没有（）环节。 A. 给定 B. 放大 C. 反馈 D. 执行 正确答案： 2. 系统在作用下的稳态误差，说明( )。 A. 型别ν<2 B. 系统不稳定 C. 输入幅值过大 D. 闭环传递函数中有一个积分环节 正确答案： 3. 最小相位系统的开环增益越大，其（）。 A. 振荡次数越多 B. 稳定裕量越大 C. 相位变化越小 D. 稳态误差越小 正确答案： 4. 开环频域性能指标中相角裕度对应时域性能指标( ) 。 A. 超调 B. 稳态误差 C. 调整时间 D. 峰值时间 正确答案： 5. 两个或多个环节具有同一输入信号，而以各自环节输出信号代数和作为系统总输出信号，这种结构成为（）。 A. 串联 B. 并联 C. 开环 D. 闭环 正确答案： 6. 系统的数学模型是指（）的表达式。 A. 输入信号 B. 输出信号 C. 系统动态特性 D. 系统的特征方程 正确答案： 7. 在信号流图中，支路上标明的是（）。 A. 输入 B. 引出点 C. 比较点 D. 传递函数 正确答案： 8. 分析的性能指标，哪个指标是反映相对稳定性的（）。 A. 上升时间 B. 峰值时间 C. 调整时间 D. 最大超调量 正确答案： 9. 二阶系统单位阶跃响应曲线呈现出等幅振荡，则其阻尼比可能为（）。 A. 0.6 B. 0.707 C. 0 D. 1 正确答案： 10. 下列哪种措施对提高系统的稳定性没有效果( )。 A. 增加开环极点 B. 在积分环节外加单位负反馈 C. 增加开环零点 D. 引入串联超前校正装置 正确答案： 11. 已知单位反馈控制系统在阶跃函数作用下，稳态误差为常数，则此系统为（）。 A. 0型系统 B. I型系统 C. II型系统 D. 高阶系统 正确答案： 12. 主导极点的特点是（）。 A. 距离虚轴很近 B. 距离实轴很近 C. 距离虚轴很远 D. 距离实轴很远 正确答案： 13. 对于代表两个或两个以上输入信号进行（）的元件又称比较器。 A. 微分 B. 相乘 C. 加减 数值分析上机作业 第 1 章 1.1计算积分，n=9。（要求计算结果具有6位有效数字） 程序： n=1:19; I=zeros(1,19); I(19)=1/2*((exp(-1)/20)+(1/20)); I(18)=1/2*((exp(-1)/19)+(1/19)); for i=2:10 I(19-i)=1/(20-i)*(1-I(20-i)); end format long disp(I(1:19)) 结果截图及分析：在MATLAB中运行以上代码，得到结果如下图所示：当计算到数列的第10项时，所得的结果即为n=9时的准确积分值。取6位有效数字可得. 1.2分别将区间[-10.10]分为100,200,400等份，利用mesh或surf 命令画出二元函数 z= 的三维图形。 程序： >> x = -10:0.1:10; y = -10:0.1:10; [X,Y] = meshgrid(x,y); Z = exp(-abs(X))+cos(X+Y)+1./(X.^2+Y.^2+1); subplot(2,2,1); mesh(X,Y,Z); title('步长0.1') >> x = -10:0.2:10; y = -10:0.2:10; [X,Y] = meshgrid(x,y); Z = exp(-abs(X))+cos(X+Y)+1./(X.^2+Y.^2+1); subplot(2,2,1); mesh(X,Y,Z); title('步长 0.2') >>x = -10:0.05:10; y = -10:0.05:10; [X,Y] = meshgrid(x,y); Z = exp(-abs(X))+cos(X+Y)+1./(X.^2+Y.^2+1); subplot(2,2,1); mesh(X,Y,Z); title('步长0.05') 一、单选题（共20道试题，共60分。）V1.开环控制系统特征是没有（）环节。 A.给定 B.放大 C.反馈 D.执行 2.系统在作用下的稳态误差，说明()。 A.型别ν<2 B.系统不稳定 C.输入幅值过大 D.闭环传递函数中有一个积分环节 3.最小相位系统的开环增益越大，其（）。 A.振荡次数越多 B.稳定裕量越大 C.相位变化越小 D.稳态误差越小 4.开环频域性能指标中相角裕度对应时域性能指标()。 A.超调 B.稳态误差 C.调整时间 D.峰值时间 5.两个或多个环节具有同一输入信号，而以各自环节输出信号代数和作为系统总输出信号，这种结构成为（）。 A.串联 B.并联 C.开环 D.闭环 6.系统的数学模型是指（）的表达式。 A.输入信号 B.输出信号 C.系统动态特性 D.系统的特征方程 7.在信号流图中，支路上标明的是（）。 A.输入 B.引出点 C.比较点 D.传递函数 8.分析的性能指标，哪个指标是反映相对稳定性的（）。 A.上升时间 B.峰值时间 C.调整时间 D.最大超调量 9.二阶系统单位阶跃响应曲线呈现出等幅振荡，则其阻尼比可能为（）。 A.0.6 B.0.707 C.0 D.1 10.下列哪种措施对提高系统的稳定性没有效果()。 A.增加开环极点 B.在积分环节外加单位负反馈 C.增加开环零点 D.引入串联超前校正装置 11.已知单位反馈控制系统在阶跃函数作用下，稳态误差为常数，则此系统为（）。 A.0型系统 B.I型系统 C.II型系统 D.高阶系统 12.主导极点的特点是（）。 A.距离虚轴很近 B.距离实轴很近 C.距离虚轴很远 D.距离实轴很远 13.对于代表两个或两个以上输入信号进行（）的元件又称比较器。 A.微分 B.相乘 C.加减 D.相除 14.闭环控制系统通常对（）进行直接或间接的测量，通过反馈影响控制信号。 A.输入量 B.输出量 C.扰动量 D.设定量 15.系统的频率特性（） A.是频率的函数 B.与输入幅值有关 C.与输出有关 D.与时间t有关 16.系统稳定的充分必要条件是其特征方程式的所有根均在根平面的（）。 A.右半部分 B.左半部分 C.实轴上 D.虚轴上 17.带动控制对象，直接改变被控变量的控制元件称为（）。 A.放大元件 B.执行元件 C.测量元件 D.补偿元件 18.典型欠阻尼二阶系统，当开环增益K增加时，系统（） A.阻尼比增大，超调量增大 一、填空题：(共20分) 1.非奇异矩阵的条件数为，条件数的大小反映了方程组的 。 2.的相对误差和的相对误差之间的关系是。 3．给出一个求解对任意初值都收敛的迭代公式 ，说明如何获得及收敛理由。 4. 设为互异节点，为对应节点上的拉格朗日插值基函数，则, 。 5．设互异，则当时，；。 6．数值积分公式的代数精确度 是，____ Gauss型求积公式。 二、（10分）设阶矩阵对称正定，用迭代公式 求解。问实数取何值时迭代收敛？ 三、（13分）设有线性方程组， (1)将系数矩阵A分解为 ，求；(2)求解方程组。 四、（10分）用最小二乘法确定中的参数和，使该函数曲线 拟合于下 列形式的数据（推导满足的正则方程组）。 五、（10分）求四次插值多项式，使其满足条件 ，并写出插值余项。 六、（10分）设，考虑方程，证明求解该方程的牛 顿法产生的序列（其中）是收敛的；并求，使得 。 七、（15分）对于积分，当要求误差小于时，用复化梯 形公式及 复化抛物线公式计算近似值时，所需节点数及步长分别为多少？计算满足精度要求的 近似值。 八、（12分）试求系数，使3步公式 的阶数尽可能高，并写出其局部截断误差的主项。 一、（12分）设有线性方程组， （1）将系数矩阵A分解为L和U的乘积，其中L是单位下三角阵，U是上三角阵； （2）解线性方程组。 二、（18分） （1）已知数据： 试分别用线性及二次插值计算的近似值，并估计误差。 （2）设，试求三次插值多项式使得 , 并对任一写出误差估计式。 三、（20分） （1）设线性方程组的系数矩阵 试写出收敛的迭代计算公式； （2）若线性方程组的系数矩阵，用表示 迭代法和迭代法收敛的充分必要条件。四、（15分） （1）若用复化梯形、复化辛普森公式计算积分的近似值，要求计算结果有5位有效数字，分别应取多大？ （2）选一复化求积公式计算积分的近似值，要求截断误差小于。 五、（10）确定，使求积公式 的代数精确度尽可能高，并指出是否是型求积公式。 六、（15分）试用法推导出求近似值的迭代 格式, 并用导出的公式计算的近似值，要求误差不超过。 七、（10分）已有求解常微分方程的二步公式： 欲使此格式的整体截断误差达到最高阶，应取何值，并说明公式是几阶方法。 1.对于代表两个或两个以上输入信号进行（）的元件又称比较器。 A.微分 B.相乘 C.加减 D.相除 【参考答案】: C 2.系统的数学模型是指（）的表达式。 A.输入信号 B.输出信号 C.系统动态特性 D.系统的特征方程 【参考答案】: C 3.某0型单位反馈系统的开环增益为K，则在r(t)=1/(2t*t) 输入下， 系统的稳态误差为（） A.0 B.无穷大 C.1/K D.A/(K) 【参考答案】: B 4.典型二阶系统的超调量越大，反映出系统（） A.频率特性的谐振峰值越小 B.阻尼比越大 C.闭环增益越大 D.相角 裕度越小 【参考答案】: D 5.适合应用传递函数的系统是（）。 A.单输入，单输出的线性定常系统 B.单输入，单输出的线性时变系统 C.单输入，单输出的定常系统 D.非线性系统 【参考答案】: A 6.系统的传递函数在右半S平面上没有零点和极点，则该系统称作（）。 A.非最小相位系统 B.最小相位系统 C.不稳定系统 D.振荡系统 【参考答案】: B 7.采用负反馈形式连接后，则 ( )。 A.一定能使闭环系统稳定 B.系统动态性能一定会提高 C.一定能使干扰引起的误差逐渐减小，最后完全消除 D.需要调整系统的结构参数，才能改善系统性能 【参考答案】: D 8.系统的动态性能主要取决于开环对数幅频特性的（）。 A.低频段 B.开环增益 C.高频段 D.中频段 【参考答案】: D 9.两典型二阶系统的超调量δ％相等，则此两系统具有相同的（）。 A.自然频率 B.相角裕度 C.阻尼振荡频率 D.开环增益K 【参考答案】: B 10.最小相位系统的开环增益越大，其（）。 A.振荡次数越多 B.稳定裕量越大 C.相位变化越小 D.稳态误差越 小 【参考答案】: D 11.状态变量具有（）的特征。 A.唯一性 B.特征值不变性 C.特征值可变 D.以上均不正确 【参考答案】: B 12.二阶系统的调整时间长，则说明（）。 A.系统响应快 B.系统响应慢 C.系统的稳定性差 D.系统的精度 差 【参考答案】: B 2008级计算机学院《数值分析》期末试卷A 卷 班级 学号 姓名 成绩 一、 填空题（每空2分，共30分） 1. 设函数f (x )区间[a ，b]内有二阶连续导数，且f (a )f (b )<0, 当 时，用双点 弦截法产生的解序列收敛到方程f (x )=0的根。 2. n 个求积节点的插值型求积公式的代数精确度至少为______次，n 个求积节点的高斯 求积公式的代数精度为 。 3. 已知a =3.201，b =0.57是经过四舍五入后得到的近似值，则a ?b 有 位有 效数字，a +b 有 位有效数字。 4. 当x =1，-1，2时，对应的函数值分别为f (-1)=0，f (0)=2，f (4)=10，则f (x )的拉格朗 日插值多项式是 。 5. 设有矩阵?? ????-=4032A ，则‖A ‖1＝_______。 6. 要使...472135.420=的近似值的相对误差小于0.2%，至少要取 位有效数字。 7. 对任意初始向量0()X 和常数项N ，有迭代公式1()()k k x Mx N +=+产生的向量序列 {}() k X 收敛的充分必要条件是 。 8. 已知n=3时的牛顿-科特斯系数,8 3,81)3(1) 3(0 ==C C 则=) 4(2 C ，=) 3(3C 。 9. 三次样条函数是在各个子区间上的 次多项式。 10. 用松弛法 (9.0=ω)解方程组??? ??=+-=++--=++3 1032202412 25322 321321x x x x x x x x x 的迭代公式是 。 11. 用牛顿下山法求解方程03 3 =-x x 根的迭代公式是 ，下山条件是 。北京理工大学数学专业数值计算方法Ⅰ期末试题2010级B卷(MTH17170)
北理工889数据结构考纲
北京理工大学2008级数值分析试题及答案
北京理工大学2013级数据结构B试题(A卷)-答案
北京理工大学数学专业数值计算方法Ⅰ期末试题2013级B卷,2015级A卷(MTH17170)
北理工《实用数据结构与算法》在线作业
北理工《自动控制理论2》在线作业1答案
北京理工大学 级数值分析试题及答案
2019 北京理工大学 889《数据结构》 考试大纲
17春北理工《自动控制理论I》在线作业
北理工数值分析大作业
北理工17春秋自动控制理论I在线作
北理工考博数值分析——试卷
北理工20年春季《自动控制理论1 》在线作业.doc
数值分析
相关主题
文本预览