相控阵雷达接收技术-相控阵雷达技术丛书
接收技术是相控阵雷达最基本的技术之一。本书全面分析了相控阵雷达通道接收技术、相参频率合成技术、波形产生和激励源技术，这三部分内容涵盖了完整的相控阵雷达接收技术，具体有：相控阵雷达对接收机性能的要求，接收机的构成和主要功能；噪声的特性、来源，噪声系数及其测量方法和动态范围；多通道接收、计算机辅助测试和接收机监控技术；现代雷达中开始出现的数字接收技术；相位噪声的特点，在时域和频域表征它的参数和术语，对它的测量方法以及它对雷达性能的影响；基本的频率合成技术，特别详细地介绍了近年来出现的直接数字式频率合成技术；雷达发射波形和激励信号产生技术；相控阵雷达数字化接收技术的新进展。.目录Ⅻ3.4普遍情况下的网络噪声特性2了3.4.1多频网终的噪声特性303.4.2级联网络的噪声特性pt.自d鲁333.4.3超外差雷达接收机网络级联分析…39接收机灵敏度403.6相控阵雷达接收阵面的有效噪声温度3.6.1相控阵雷达有源天馈线阵面的主要类型433.6.2各类天线阵的有效噪声温度453.7噪声系数的测量463.7.1噪声源…463.7.2Y因子法…∴……483.7.3自动测量法3.7.4噪声直接测量法543.8内部干扰——电磁兼容性设计………553.8.1滤波与带宽的优化56.8.2中频频率的优化59参考文献…60第4章通道接收机的其他性能…624.1动态范围………624.1.1增益设计和增益分配634.1.2接收机输入端回波信号的动态范围……644.1.3接收机设备的动态范围674.1.4接收机的增益控制704.1.5接收机动态范围对MTI改善因子的影响4.2多通道接收机…………724.2.1多通道接收机的特性……724.2.2多通道接收机性能对相控阵雷达性能的影响…………………724.3通道接收机的计算机辅助测试(CAT)技术………734.3.1计算机自动测试基本原理和系统构成鲁非■鲁鲁章鲁∴…744.3.2单通道性能测试………………764.3.3通道间幅相一致性测试77相控阵雷达接收机的监控与BIT784.4.1相控阵雷达接收机监控和BⅠT的必要性、内容与方法4.4.279参考文献80Ⅻ相控阵雷达接收技术第5章数字接收机及采样定理1数字接收机的意义815.1.1雷达数字接收机的关键技术5.1.2数字接收机对雷达通道接收机性能的影响82低通采样定理…825.2.1采样845.2.2量化883中频数字化895.3.1带通釆样定理。曲自B自鲁鲁鲁5.3.2带通采样的进一步分析94降低噪声和杂散的方法97参考文献106第6章模数变换(ADC)技术…………………………………1086.1ADC的类型及其特性1086.1.1闪烁型或全并行型1096.1.2流水线型1106.1.3逐次逼近型………………·即.·看··罪·如自鲁6.1.4∑一△型……1126.2ADC主要性能分析…………………………………1146.2.1转换速率1166.2.2分辨力∴…1176.2.3增益误差非自自1176.2.4量化噪声1176.2.5输出信噪比暂最DD1216.2.6有效位……1226.2.7非线性失真及无杂散动态范围………………………………1246.2.8谐波失真…1256.2.9输入带宽,小信号带宽,全功率带宽…∴1266.2.10积分非线性误差和微分非线性误差1276.2.11漏码…1306.2.12直流偏移……………1306.2.13采集时间、孔径时间、孔径延迟时间和有效孔径延迟时间…1306.2.14孔径不确定性噪声1326.2.15噪声功率比1346.2.16缓冲放大器…136日录上絮6.2.17数字接收机与系统噪声系数………………1366.2.18ADC对雷达性能的影响138参考文献140第7章解调技术…1417.1解调技术的主要性能指标7.2模拟信号的解调●·普鲁啬1443无混频数字信号的解调1467.3.1数字正交检相器的一般原理∴…1477.3.2希尔伯特滤波法1487.3.3低通滤波法…………………1497.3.4插值法………………………1517.3.5数字乘积检相(DPD)法………1527.4采样率转换技术1537.4.1抽取……1537.4.2内插1545高效数字滤波器1567.6数字下变频器…7.6.1实现数字下变频的方法1617.6.2ASIC方法1617.6.3FPGA方法……甲·普···………………165参考文献…171第8章频率合成器的各项性能、相位噪声及其测量方法∴……1738.1频率合成器的主要性能指标1738.1.1工作频率范围及频率捷变点数…1738.1.2工作频率、频率准确度及长期频率稳定度……1748.1.3输出功率1748.1.4频率转换时间及其测试技术174频率稳定度或相位噪声………………1758.1.6谐波与杂散1768.1.7撷率推移1778.1.8频率牵引●●4……1778.1.9频率复现性1778.1.10开机特性1778.2频率稳定度及其表征………1788.2.1频率稳定度对于现代雷达的意义178Ⅻ相控阵霅达接收技术82.2相位噪声的产生………1838.2.3雷达频率源的频率稳定度砑究特点1938.2.4相位噪声的谱密度分布∴……………………19582.5频率稳定度的表征……1978.3频率稳定度的测量技术·。由击●果●………………………2128.3.1时域一阿仑方差测量法…2138.3.2频域测量方法之直接频谱仪法………………218.3.3频域测量方法之二—一相位检波法…∴…2178.3.4频域测量方法之三——鉴频法2238.3.5附加噪声的测量………………2248.3.6信号源调幅噪声的测量……2258.3.7脉冲信号相位噪声的测量技术…………226参考文献………230第9章频率源性能对雷达性能的影响……2329,1对雷达接收机噪声系数的影响2329.2对雷达接收机选择性的影响………2339.3对接收机动态范围的影响………2339.4对脉冲压缩性能的影响……鲁·鲁命鲁自着·非最单·非“·p看自·鲁·要罪要·D·身看2339.5对动目标显示性能的影响…2349.5.1动目标显示技术的基本原理……D●鲁2349.5.2颊率稳定度对MTI的影响…2369.6对脉冲多普勤雷达的影响240参考文献241第10章频率合成器的构成●鲁。看,·自·非24210.1直接模拟式频率合成技术……24210.2间接模拟式频率合成技术(锁相环技术)…………………24410.3直接数字式频率合成技术24610.3.1DDS的基本工作原理24710.3.2DDS输出信号的质量…25010.3.3DDS杂散的抑制……25710.3.4DDS输出频率的扩展26010.3.5数模变换器(DAC)26010.4组合式频率合成技术……………26710.4.1锁相环/直接式合成技术26710.4.2DDS/锁相环式合成技术268目录X参考文献………………………268第11章发射波形和激励信号产生技术27011.1发射波形的产生…………270模拟产生法27111.1.2数字产生法27411.2激励信号的产生……………28011.2.1直接中频信号产生…28011.2.2正交调制技术和上变频技术……………28111.3激励信号带宽的扩展一超宽带信号的产生……………28511.3,1基带信号带宽的展宽…………………………28511.3.2调制器的选择28611.3.3倍频技术28711.4激励信号质量分析自自自自「非28711.4.1基带波形的质量…28711.4.2正交调制器输出信号的质量……鲁。·香卵2811.4.3信号质量对匹配滤波一脉冲压缩性能的影响……290I1.4.4信号质量对去斜处理性能的影响……………293参考文献…297第12章数字化接收技术的新进展…………………………29912.1数字阵雷达(DAR)的发展历史及现状29912.2数字收发组件和数字接收机30312.3微波ADC技术…看·曲·鲁·鲁非自●。·带垂垂…30712.4光学ADC技术…………………………………31012.4.1电子ADC在提高ADC的动态范围一釆样频率积时的局限性……31112.4.2光学ADC的分类及几种主要类型的特性…31412.4.3光电ADC芯片……………32412.4.4光学模数变换器的应用…∴………32612.5多芯片组件(MCM)技术32612.6直接数字频率合成技术、数字波形产生和数字上变频技术……327参考文献328符号表………331缩略语340第1章概论1.1相控阵雷达接收分系统的构成部完整的相控阵雷达接收分系统的构成如图1.1所示,它包含了通道接收机、频率源和激励源(含雷达波形产生器)三个组成部分通道接收机模拟接收机或模拟前端数字接收机来自天线阵面的去DBF网络或射频信号模拟接收机或模拟前端数字接收机信号处理机1模拟接收机或模拟前端数字接收机频率源基准频率变频器及僧频器霎达基带波形产生器激励源图1.1相控阵雷达接收分系统的构成通道接收机是雷达回波信号的通道,它接收来自相控阵天线阵面的雷达回波信号。模拟接收机对回波信号首先进行一系列模拟处理,包含保护接收机免烧毁或饱和的有源/无源小功率限幅器、为机内检测(BⅠT)而设置的低插损定向耦合器、低噪声放大器(LNA)、下变频器。第一下变频器是借助于雷达频率源产生的本振信号(f()将微波射频回波信号下变频至固定的中频频率。变频次数可以是一次、两次或三次,视雷达的工作频段高低和中频频率优化结果而定,它们的作用2相控庥管达接取技术是逐渐将中频频率降低到合适的频率。接收机在中频频段,除对回波信号进行放大之外,还会对回波信号的带宽进行匹配或准匹配滤波;为了压缩回波信号的瞬时动态范围,在射频段或中频段,对通道的总增益进行灵敏度时间控制(STC);对多路通道之间的幅度/相位一致性进行调整;为后续的数字接收机设置防混叠滤波器。结构简单的模拟接收机有时又称为模拟前端雷达回波信号,经过模拟接收机的上述处理之后进人数字接收机,在数字接收机中首先是对模拟回波信号进行采样和量化分层,变换为特定字长和特定数据率的数字信号,高速率的数字信号进入数字下变频器(DDC),在一对正交数字乘法器中,借助于数控振荡器(NCO)把模数变换器采集到的数字信号解调出数字基带信号。为了与后续的数字信号处理机速率匹配,往往还要进行数据率的抽取和进步的数字匹配滤波,最后以极坐标或直角坐标的格式输出数字信号去进行数字波束形成或雷达数字信号处理回波信号数字化的切入点是根据雷达工作频段、回波信号带宽和模数变换器的采样速率等因素决定的,可以是在低中频,高中频,甚至于射频、微波频毀进行数字化。目前模数变换器的釆样率多在几兆赫至1吉赫范围内,国际上也出现了几吉赫以上采样率的模数变换器。模数变换器的采样率高低,决定了模拟接收机的繁简程度,技术的发展趋势是促成直接在射频或微波频段进行回波信号的数字化相控阵雷达接收分系统的第一个重要组成部分是通道接收机。通道接收机的通道数目多少取决于相控阵雷达的功能,这在本书第2章进行详细叙述。最简化的情况是采用三通道的单脉冲测角体制,为了进行副瓣对消,会增加副瓣对消接收通道,如果作为机载、星载相控阵雷达,还会设置对海接收通道和保护通道。对于采用数字波束形成技术的相控阵雷达,可以将天线阵面分割成若干个子阵,每个子阵后置一路通道接收机,也可以每个天线辐射单元后置一路通道接收机。相控阵雷达接收分系统另一个重要组成部分是雷达频率源,有时又称为雷达频率合成器,它是以一个高质量振荡器作为频率基准,经过不同方法的综合形成的,在本书第10章介绍了三种不同的类型,即直接模拟式频率源、间接模拟式频率源(即锁相环式频率源)、直接数字式频率源,以及它们相互结合的组合式频率源它提供通道接收机和雷达激励源所需的各本振信号、数字接收机和雷达波形产生器所需的采样信号()和时钟信号(f),除此之外,雷达频率源还向雷达定时器提供定时基准信号。相控阵雷达接收分系统第三个组成部分是所谓的雷达激励源,它实际上就是相控阵雷达发射机的前端部分。雷达激励源由上变频器和雷达波形产生器组成雷达波形产生器往往是数字式可编程的,它以直接式频率综合器(DDS)芯片为核心。理论上讲这种构成的波形产生器可以产生任意多种雷达工作波形,可以任意改变脉冲宽度和雷达重复频率,可以进行任意形式的调制:例如脉冲雷达常用的线第1章概论性调频、非线性调频和脉冲编码调制等,可以产生基带波形,也可以产生中频波形,可以产生正交的1/Q分量信号,也可以产生合成单边带信号上变频器:正如同通道接收机的下变频方式,雷达激励源可以采用上变频方式,将雷达波形产生器输出的中频信号借助雷达频率源输出的本振信号上变频至发射频率,也可以在上变频基础上再倍频至雷达发射频率,这要视雷达工作频段而定。激励源输出的功率一般在几十毫瓦至几百毫瓦之间,到雷达发射机内部再经过前级放大后驱动发射机的末级功率放大器1.2相控阵雷达对通道接收技术的要求雷达接收分系统为雷达能在噪声、杂波和干扰中检测到有用目标回波信号提供通道,并进行必要的处理。相控阵雷达一般是相参雷达,接收机常常是超外差式体制,它有一个或多个中频频率。接收机首先对信号进行低噪声放大并预选,最大限度地降低内部产生的噪声和带外干扰,并使进入的射频或微波回波信号与相参本振进行变频,频率变换到中频后进一步放大和对信号带宽进行匹配滤波,再进行正交相参解调和模数变换(对于数字接收机是先进行模数变换再进行正交相参解调);为了适应回波信号在大动态范围内的变化,而通道又能工作在线性状态,需要对通道进行适当的增益控制。除以上常规功能之外,相控阵雷达对接收分系统还有如下的一些突出要求对天线接收到的目标回波信号提供污染尽量小的信号通道,并高保真地传输回波信息。因此,一般情况下,相控阵雷达接收机应为线性接收机,对信号提供线性通道。所谓“污染”,包含了设备内部产生的各种噪声以及寄生调幅和调相噪声;模数变换器的量化噪声、采样脉冲产生的孔径抖动噪声;由设备的非线性产生的谐波、互调产物;频率组合产生的组合干扰频率;各种源产生的杂散频谱。这些成分均会污染信号空间。接收机的主要任务之一就是减小这些污染源的影响,尽量扩大无污染空间。所谓信号空间,在频域的宽度是接收机的带宽,信号强度的下限就是最小可检测信号电平,但这受限于噪声电平高低,这就要抑制各种噪声来降低接收机的噪声系数,提高接收机的灵敏度,以扩展信号空间的下限,扩展信号空间的上限就是通道各电路的线性输出能力,为此,就要减小器件的各种非线性失真,合理地设计系统,比如系统增益的合理分配,增益控制的合理设计,被选用器件的线性输出能力。相控阵雷达,当采用DBF技术时,通道接收机往往是多通道的,其中对接收机最突出的要求是:为了高性能自适应天线波束的形成,对通道的幅相一致性和相互之间的隔离都提出了很高的要求,特别是在信号全动态范围内及雷达工作频段内的幅相一致性和隔离度提出了严格的要求。如果说,通道的幅相…一致性还可以通过计算机进行误差修正的话,那么通道工作的稳定性就显得更为突出。
- 2020-12-11下载
- 积分：1
上海大学数据结构试卷及答案
很好的考试复习资料，内容很多，讲解很细致，而且涉及的也是重点数据结构试卷(一)参考答案选择题2.C3.DC 5. A6,C7.C8,B9.810.B填空题1.(F+!2.0(n),0(n1,4. s->rext=p-7nexl: y>neext=sn, 2e6.m=2了,CBA8.4,1610.n-1、应用题1.链式存储结构略,前序 ABDEL,中序 DBEAC,后序 DEBCA,2.哈夫曼树略,WPL=783.(i8,5,16,19,21,23),(5,16,21,19,18,23)h1012345674.线性探测:链地址法:h2->1人8∧1025322768h4->25->326865.深度:125364,广度:123456,最小生成树T的边集为E={(1,4),(1,3)(3,5,(,如,(.6)}四、算法设计题1.设计判断单链表中结点是否关于中心对称算法typedef struct (int s[100]; int top, y sqstack;int lklistsymmetry(iklist *head)sqstack stack; stack top=-1; Iklist"p;forip=head;pl=O; p=p->next)(stack. op++;stack s[stack top=p->data; 3for(p=head;pl=0;p=p->next)iE (p->data==stack s(stackLop!)stack top=stack top- 1; else return(0);return(1);2.没计链式存储结构上建立一楳二又树的算法。typedef char datatype,typedef struct node (datatype data; struct node *lchild, *rchild; bitreevoid createbitree( bilree*&bt)char ch; scanf("%c, &eif(ch==")(bt=0; return; Jbt=(bitree*)malloc(sizeof(bitree)); bt->data=chreatebitree(bt->lchild); createbitree(bt->rchild);3.设计判断一棵二叉树是否是二义排序树的算法。int minnum=-32768, flag=1typedef struct nodefint key; struct node"Child, *rchild; bitree;yoid inorder ( bitree *bt)if (bt =0)[inorder(bt->child ); if(minnum>bt->key)flag=0; minnum=bt->key, inorder (bt->rchild); h数据结构试卷(二选择题(24分)1.卜面关于线性表的叙述错误的是(D)(A)线性表采用顺序存储必须:用一片连续的存储空间(B)线性表采用链式存儐不必山用一片迕续的存储空闫(C)线性表用链式存便丁插入和删除操作的实现D)线性表釆用顺序存储便亍插入和删除操作的实现设哈大曼树中的叶子结点总数为m,若用二叉链表作为存储结构,则该哈夫曼树中总共有(A界个空指针域,9有叶万为的纸且2(A)2m-1(B)2mC)2m+1妤没顺序循环队列Q0:M1]的头指针和尾指针分别为P和R,头指针F总是指向队头元素的前一位置尾指针R总是指向队尾元的当前位置,则该循环队列中的元素个数为()(A)R-T(B)F-R(C)(R-F+M)%M()(F-R+M)%M√4!设某棵二叉树的中序遍历序列为ABCD,前序遍历序列为CABD,则后序遍历该二叉树得到序列为A(A)BADC(B)BCDA(C CDAB(D) CBDA5.设某完全无向图有n个顶点,则该完全无向图中有(A条边(A)n(n-1)/2(B)n(n-1)(C)n26.设某棵二叉树中有2000个结点,则该二叉树的最小高度为(O)。(C)11D)12设采图中有m个顶点,则该有向图对应的剑趣中有()个表头结点(B)n(D)2n-18.设一组初始记录关键字序列(5,2,6,3,8),以笫一个记录关键字5为基准进行一趟快速排序的结果为(C)。(A)2,3,5;8,6(B)3,2,5,8,6(C)3,2,5:6,8①D)2,3,6,5,8、填空题(24分)1.为了能有效地应用HASH查找技术,必须解决的两个问题是和下面程序段的功能实现数据x进栈,要求在下划线处填上正确的语句typedef struct (int s[ 100]; int top: f sqsiack;void push (sqstack &stack, int x)if( stackop==m-1) printf(“ overflow”)lies9tk二x;“a少+:3.中序遍历二叉排序树所得到的序列是有度序列(填有序或无序铁邀神厅的最间复弟度为1),平均时间复杀度为地D(3设某倮二叉树中度数为0的结点数为N,度数为1的结点数为N,则该二叉树中度数为2的结点数若采用二叉链表作为该二叉树的存储结构,则该二叉树中共有山+41个空指针域6.设某无向各中顶点数和边数分别为n和e,所有顶点的度数之和为d,则e=7.设一缃初始记录关键字序列为(55,63,44,38,75,80,31,56),则利用筛选法建立的初始堆为8.改某无向图G的邻接表为2->1>3又v--1->4->2·从点W开始的深度优先遍历序圳为1,24:切度优先遍历序列为省三、应用题(36分)].设一组初始记录关键字序为(45,80,48,40,22,78),则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果2.设指针变p指向双向链表中结点A,指针变量q指向被插入结点B,要求给出在结点A的后面插入结点B的操作序列(设双向链表中结京的两个指针域分别为11ink和 rlink)a设一组有序的记录关键字序圳为(13,18,24,35,47,50,62,83,90),查找方法用二分查找要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度4设一棵树T中边的集合为联A,B),(A,C,(A,D),(B,E),(C,F,(C,G)},要求用孩子兄弟表示法(二叉链表)表示出该树的存储结构并将该树转化成对应的二叉树5.设有无向图G(如右图所示),要求给出用普里姆算法构造最小生成树所走6过的边的集合。6.设有—组初始记录关键字为(45,80,48,4,2,178,要求构造一楔二(56叉排序树并给出构造过程。四、算法设计题(16分)1.设有一组初始记录关键字序列(K,K2,…,K),要求设计一个算法能够在0(n)的时间复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于K,右半部分的每个关键字均大于等于K2.设有两个集合A和集合B,要求设计生成集合C=A∩B的算法,其中集合A、B和C用链式存储结构表示数据结构试卷(二)参考答案选择题ltd 2. B5,A7,B8.C二、填空题构造一个好的HASH凼数,确定解决冲突的方法2. stack top+t, stack s[stack top ]=3.有序4.0(n2),0( logan)5.N-1,2N+N6.d/27.(31,38,54,56,75,80,55,638.(1,3,4,2),(14)应用题1.(22,40,45,48,80,78),(40,45,48,80,22,78)2. q>llink=p: g->rlink=p->rlink; p->rlink->link=q; p->rlink=q·3.2,ASL=91*1+2*2+3*4+4*2)=25/94.树的链式存储绪构略,二叉树略E={(1,3),(1,2),(3,5),(5,6),(6,4)}6.略四、算法设计题1.设有组初始记录关键字序列(K1,K2,…,Kn),要求设计一个算法能够在0(n)的时间复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于K1,右半部分的每个关键字均大于等于KYoid quickpass(int r[, int s, int t)int i=s,j=t, x=r[s]While(inext: p->data=g->data: p->next=g->next: free(q)B)gp->next: g->data=p->data: p->next=g >next free(g):(C)q=p->next: p->next=q->next: free(q)(D)q=p->next: p->data=q->data: free q)4.设有n个待排序的记录关键字,则在堆排序中需要(小个辅助记录单元(A)1(B)n(c)nlogen5.设一组初始关键字记录关键字为(20,15,14,18,21,36,40,10),则以20为基准记录的一趟快速排序结束后的结果为(A)10,15,14,18,20,36,40,21(B)10,15,14,18,20,40,36,2I(C)10,15,14,20,18,40,36,21(D)15,10,14,18,20,36,40,21y/设二叉排序树中有n个结点,则在二叉排序树的平均平均查找长度为)(A)0(1)(B)0(10g2n)((D)O(n2)7.设无向图G中有n个顶点e条边,则其对应的邻接表中的表头结点和表结点的个数分别为(D(B)e,nC)2D)n,28.设某强连通图中有n个顶点,则该强连通图中至少有(C)条边(A)n(n-1)(B)n+1D)n(+19.设有5000个待排序的记录关键字,如果需要用最快的方法选出其中最小的10个记录关键字,则用下列)方法可以达到此目的(A)快速排序(B)堆排序(C)归并排序D)插入排序0下列四种排序中()的空间复杂度最大。(A)插入排序(B)冒泡排序(C)堆排序(D)归并排序二、填空殖(48分,其中最后两小题各6分)数据的物理结构主要包括座不构利和环结堆两种情况设一棵完全:叉树中有500个结点,则该二叉树的深度为4:若用二叉链表作为该完全二叉树的存情结构,则共有55个空指针域3.设输入序列为1、2、3,则经过栈的作用后可以得到种不同的输出序列。4.设有向图G用邻接矩阵An]「m作为存储结构,则该邻接矩阵中第i行上所有元素之和等于顶点i的友,第1列上所有元素之和等于顶点i的入区毕设哈夫曼树中共有n小结点,则该哈夫曼树中有日个度数为1的结点6.没有向图G中有n个顶点e条有向边,所有的顶人度散之和为d则形和d的关系为=e遍历二义排序树中的结点可以得到一个递增的关键字序列(填先序、中序或后序)8.改奁找表中有100个元素,如果川二分法查找方法查找数据元素X,则最多需要比较次就可以断定数据元素K是否在查找表中9.·不论是顺序存储结构的栈还烂链式存储结构的栈:其入饯和出栈榤作的间复柒度均为的10.设有a个结点的完全一义树,如果按照从自上到下、从左到右从1开始顺序编号,则第i个结点的义结点编号为“,右孩子结点的编号为2计11.设一组初始记录关键字为(72,73,71,23,94,16,5),则以记录关键字72为基准的·趟快速排序结果为!2.设有向图G中有向边的集合F=(,,,,key==k)Y七; else if(t->key>k)tt>lchd;lse七飞→YC三、算法设计题(22分设计在单链表中删除值相同的多余结点的算法2.设计-个求结点x在二叉树中的双亲结点算法。数据结构试卷(三)参考答案、选择题B4.A5.A6.B7.D8.C9.B10. D第3小题分析:首先用指针变量q指向结点A的后继结点B,然后将结点B的值复制到结点A中,最后删除结点B第9小题分析;9快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的10个数,而堆排序只需要在初始堆的基础上再进行10次筛选即可,每次筛选的时间复杂度为0(1ogn)。土、填空题1.顺序存储结构、链式存储结构2.9,5013.54.出度,入度6.7.中序8.79.0(1)10.豆/2,2i+111.(5,16,71,23,72,94,73)12.(1,4,3,2)13. j+l, hashtable[i]. key==k14. return(t),t=t-rchild第8小題分析:二分査找的过程可以用一棵二叉树来描述,该二叉树称为二叉判定树。在有序表上进行分查找时的查找长度不超过二叉判定树的高度1+log2n三、算法设计题设计在单链表中删除值相同的多余结点的算法。typedef int datatype;typedef struct node datatype data; struct node *next; lklistvoid delredundant (lklist *&head)Iklist *p,响q,*s;for(p=head; pl=0; p=p->next)tor(q=p>nex s=4;q!=0;if (q->data==p->data)[s->next=q->next; free(q); q=s->next; 1else (s=q, q=q->next; y。2.设计个求结点x在二义树中的双亲结点算法。typedef struct node (datatype data; struct node *Child, *rchild; bitree;bitree*q[20]; int r=0, f=0, flag=0void preorder (bitree * bt, char x)
- 2021-05-07下载
- 积分：1
图论算法理论、实现及应用.pdf
图论算法理论、实现及应用.pdf清华大学前言、图论研究及图论教学0图论( Graph Theory)是数学的一个分支,它以图为研究对象。图论中的图是由若干个给定的顶点、及若干条连接两个顶点的边所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用顶点代表事物,用连接两个顶点的边表示相应两个事物间具有这种关系。这种图提供了一个很自然的数据结构,可以对自然科学和社会科学中许多领域的问题进行恰当的描述或建模,因此图论研究越来越得到这些领域的专家和学者的重视。图论最早的研究源于瑞士数学家莱昂哈德·欧拉( Leonhard euler,1707~1783),他在1736年成功地解决了哥尼斯堡(Kω nigsberg)七桥问题,从而开创了图论的研究。哥尼斯堡七桥问题。东普鲁士哥尼斯堡市(今俄罗斯加里宁格勒)有一条布格( Pregel)河,如图1白a)所示。布格河横贯哥尼斯堡城区,它有两条支流,在这两条支流之间夹着一块岛形地带,这里是城市的繁华地区。全城分为北、东、南、岛四个区,各区之间共有七座桥梁联系着。人们长期生活在河畔、岛上,来往于七桥之间。有人提出这样一个问题:能不能一次走遍所有的七座桥,而每座桥只准经过一次?问题提出后,很多人对此很感兴趣,纷纷进行试验,但在相当长的时间里,始终未能解决。(B)东(D)C南C)(a)(b)图1七桥问题欧拉在1736年解决了这个问题,他将这个问题抽象为一个图论问题:把每一块陆地用一个顶点来代替,将每一座桥用连接相应两个顶点的一条边来代替,从而得到一个图(如图1(b)所示)欧拉证明了这个问题没有解(详见本书5.1节),并且推广了这个问题,给出了“对于一个给定的图,能否用某种方式走遍所有的边、且没有重复”的判定法则。这项工作使欧拉成为图论及拓扑学的创始人。在此后的两百多年时间里,图论的研究从萌芽阶段,逐渐发展成为数学的一个新分支。特别是从20世纪初期开始,在生产管理、交通运输、计算机和通讯网络等方面涌现了许多离散性问题,这极大地促进了图论的发展。20世纪70年代以后,由于高性能计算机的出现,使大规模的图论问题的求解成为可能。现在,图论理论广泛应用在运筹学、计算机科学、电子学、信息论、控制论、网络理论、经济管理等领域。由于图论的重要性,越来越多的大学将图论单独作为一门课程来开设,把它作为数学、计算本文中关于图论课程教学改革的一些思想,已经发表在《计算机教育》2009年第20期上,论文题目为《计算机专业图论课程教学改革探索》,即参考文献[20获得《计算机教育》杂志社举办的“英特尔杯”20090年全国计算机教育优秀论文评比二等奖)。图论算法理论、实现及应用杋科学、电子学、管理学等专业本科生和硏究生的必修课或选修课。很多其他课程的内容也都涉及到图论知识,如离散数学、运筹学、拓扑学等。介绍图论理论的教材逐渐增多,其中也不乏优秀的教材,如文献[。这些课程和教材或者是侧重于完整的图论知识体系介绍、以及复杂的图论定理的数学证明,或者是侧重于从应用数学的角度研究图论在各领域的应用。另外,为了实现用计算杋程序求解各种应用问题,计算机科学家抽象岀许多数据结构,如栈队列、堆、树及二叉树、图等,其中图是最重要的数据结构之一,也是应用得最广的数据结构之。数据结构课程是专门硏究这些数据结枃的描述、实现及应用的课程。数据结构课程讲到图论部分时,侧重于图结构的描述、图结构的存储、少量基本的图论算法的实现等等许多学生(特别是计算机专业的学生)在学习图论时,都不满足于图论算法的手工和草稿纸演算,迫切地想知道如何用程序实现图论中的算法,以及如何将这些算法思想用来求解实际问题据作者调査统计,市面上侧重于用程序实现图论算法、并通过例题阐述图论算法思想及其应用的教材少之又少。本教材希望能弥补这一缺憾。所以本书立足于图论算法理论和思想的描述及程序实现,并以大量的 ACM/ICPC竞赛题目来阐述图论算法思想在求解这些题目中的应用。接下来简要地介绍 ACMICPC程序设计竞赛。、 ACM/ICPC程序设计竞赛1.ACMIICPCACM/ICPO( ACM International Collegiate Programming Contest,国际大学生程序设计竞赛)是由美国计算机协会ACM( Association for Computing Machinery)主办的,世界上公认的规模最大、水平最高的国际大学生程序设计竞赛,其目的旨在使大学生运用计算机来充分展示自己分析问题和解决问题的能力。该项竞赛从1977年第一次举办世界总决赛以来,至今已连续举办30多届了。该项竞赛一直受到国际各知名大学的重视,并受到全世界各著名计算机公司的高度关注。ACM/ICPC竞赛分区域预赛和总决赛两个阶段进行,各预赛区第一名自动获得参加世界总决赛的资格。世界总决赛安排在每年的3~4月举行,而区域预赛安排在上一年的9~12月在各大洲举行。ACMICPC竞赛以组队方式进行比赛,每支队伍由不超过3名队员组成,比赛时每支队伍只能使用一台计算机。在5个小时的比赛时间里,参赛队伍要解答610道指定的题目。排名时,首先根据解题数目来排名,如果多支队伍解题数量相同,则根据队伍的总用时进行排名(用时越少,排名越靠前)。每支队伍的总用时为每道解答正确的题目的用时总和。每道解答正确的题目的用时为从比赛开始计时到该题目解答被判定为正确的时间,其间每一次错误的提交运行将被加罚20分钟时间。最终未正确解答的题目不记入总时间,其提交也不加罚时间。ACMICPC竞赛在公平竞争的前提下,提供了一个让大学生充分展示用计算机解决问题的能力与才华的平台。 ACMICPC竞赛鼓励创造性和团队协作精神,鼓励在编写程序时的开拓与创新,它考验参赛选手在承受相当大的压力下所表现出来的非凡能力。竞赛所触发的大学生的竞争意识为加速培养计算机人才提供了最好的动力。竞赛中对解决问题的苛刻要求和标准使得大学生对解决问题的深度和广度展开最大程度的追求,也为计算机科学的研究和发展作了一个最好的导向。2.在线评判网站随着 ACMICPC程序设计竞赛的推广,各种程序在线评判( Online judge,简写为OJ)网站也应运而生,这为程序设计爱好者提供了一种新的程序实践方法:在线程序实践。①作者对互动出版网站(www.china-pub.com)和卓越亚马逊网站(www.amazon.cn)上列出的全部图论相关书目及目录进行了仔细的分析,从而得出的结论在线程序实践是指由OJ网站提供题目,用户在线提交程序,OJ网站的在线评判系统实时评判并反馈评判结果。这些题目一般具有较强的趣味性和挑战性,评判过程和结果也公正及时,因此能引起用户的极大兴趣。用户在解题时编写的解答程序通过网页提交给在线评判系统称为提交运行,每一次提交运行会被判为正确或者错误,判决结果会及时显示在网页上用户从评判系统收到的反馈信息包括:" Accepted程序通过评判!Compile error"—程序编译出错。" Time limit exceeded"—程序运行超过该题的时间上限还没有得到输出结果。" Memory Limit Exceeded-内存使用量超过题目里规定的上限。"outpυ ut Limit exceeded"—输出数据量过大(可能是因为陷入死循环了)。" Presentation error"—输出格式不对,可检査空格、空行等等细节。" Run Time error"—程序运行过程中出现非正常中断,如数组越界等。Wrong Answer"—用户程序的输出错误。等等。用户可以根据OJ系统反馈回来的评判结果反复修改程序,直到最终收获 Accept(程序正确)。这个过程不仅能培养用户独立分析问题、解决问题的能力,而且每成功解决一道题目都能给用户带来极大的成就感。、本书安排本书共分9章,每章内容安排如下:第1章介绍图论的一些基本概念,以及图的两种重要存储表示方法:邻接矩阵和邻接表,并初步讨论了存储方式对图论算法复杂度的影响。第2章讨论了图的遍历,遍历是很多图论算法的基础。本章介绍了两种重要的遍历方法:深度优先搜索和广度优先搜索,并对这两种遍历算法的思想、程序实现、算法复杂度作了详细的分析和讨论。本章还讨论了活动网络,包括AOV网络与拓扑排序问题、AOE网络和关键路径问题。第3章讨论树与生成树问题,主要介绍求无向连通图最小生成树的三个算法:克鲁斯卡尔( Kruskal)算法、 boruvka算法和普里姆(Prin)算法,并对这三个算法的思想、程序实现、算法复杂度作了详细的分析和讨论。另外,本章还讨论了判断生成树是否唯一的方法。第4章讨论了有向网(或无向网)中一个典型的问题:最短路径问题。本章介绍了求解最短路径问题的4个算法:Dsa算法、 Bellman-FoH算法、SPH算法和Fod算法,这4个算法分别适用于有向网(或无向网)中各边权值的取值的不同情形及问题求解的不同需要。本章着重对这4个算法的思想、递推过程、算法复杂度作了详细的讨论,并对这4个算法作了详细的对比分析。本章还介绍了求最短路径的算法思想在求解差分约束系统中的应用。第5章讨论了可行遍性问题,包括欧拉回路、汉密尔顿回路以及中国邮递员问题。前两个概念容易混淆,欧拉回路要求经过每条边一次且仅一次并回到出发点,而汉密尔顿回路要求经过每个顶点一次且仅一次并回到出发点。本章介绍这相关概念及定理,并讨论这两种回路及中国邮递员问题的求解方法和应用。第6章讨论了网络流问题。许多系统包含了流量问题,例如,公路系统中有车辆流,控制系统中有信息流,供水系统中有水流,金融系统中有现金流等等。从问题求解的需求出发,网络流问题可以分为:网络最大流,流量有上下界的网络的最大流和最小流,最小费用最大流,流量有图论算法理论、实现及应用上下界的网络的最小费用最大流等。本章介绍各种网络流问题的求解方法。第7章讨论了点支配集、点覆盖集、点独立集、边覆盖集、边独立集(匹配),这些概念之间存在一定的联系,也容易混淆。本章主要讨论了各种匹配问题,以及求解二部图最大匹配的算法程序实现和应用。第8章讨论图的连通性,这是图论中一个重要的概念。本章介绍了无向连通图和非连通图无向图的点连通性(包括割顶集、割点、顶点连通度、点双连通图等)、边连通性(包括割边集、割边、边连通度、边双连通图等)、有向图的强连通性(包括强连通、弱连通和单连通)。本章着重介绍上述概念及求解算法。第9章讨论平面图和着色问题。本章介绍了平面图和非平面图的概念、平面图的判定方法,以及图的顶点着色、边着色、平面图的面着色等概念和求解算法。四、本书读者对象及本书特点本书的读者对象为计算机专业学生或对 ACM/ICPC竞赛感兴趣的学生,可以作为高等院校计算机(或相关专业)的图论等相关课程的主教材,也可作为 ACMICPO竞赛的辅导教材。学生或读者应该具备CC艹语言知识,已经掌握了一定的程序设计思想和方法,具备一定的算法分析与设计能力,并能熟练使用数据结构。本书在内容取材、描述上具有如下特点。1)许多图论教材对图论概念的描述不一致,造成读者的阅读困难,本书试图改变这一现状。在每个概念的表述上作者査阅了大量的图论著作并进行比较分析。在本书中,作者对每个概念采用大多数图论教材采用(或约定)的名词、定义方法等。2)本书对图论算法思想的描述尽可能采用浅显易懂的语言来描述。3)本书忽略所有图论定理的证明,着重分析图论算法的思想,重点在于这些图论算法的程序实现。对图论算法的程序实现是以 ACMICPC例题来阐述的。上下两册书共收录了130余道ACMICPC竞赛题目,例题和练习题各约占一半。本书附录列出了本书所有例题和练习题在ZOJ、POJ及UVA上的题号。4)本书图表内容丰富。全书共绘制了270余幅图表,为此在目录后专门列出了本书的图录5)为方便读者阅读和使用,作者对本书中出现的图论术语、符号、图论算法及应用分别作了索引,列在本书后面五、致谢本书收录了130余道 ACMICPC竞赛题目,这些题目在阐述图论算法思想、演示图论算法应用等方面起着重要的作用,部分例题的解答程序也参考了网络上发布的一些源代码。同时,本书在编写过程中还参考了国内外多本优秀的图论教材(详见参考文献)。在此,编者对这些题目、源代码和图论教材的作者一并表示忠心的谢意。本书的编写和岀版得到了2010年浙江省教育科学规划研究课题“以大学生学科竞赛为契机推动课程群的规划与建设”(编号:SCG156)的支持,在此表示感谢。另外,本书的岀版得到了北京大学出版社的大力支持,在此表示衷心的感谢。由于作者水平有限,在编写本书时难免出错,欢迎读者指正,或者读者有什么好的建议,都可以联系编者:wguiping@163.com。不胜感激!!!编者2010年1月目录第1章图的基本概念及图的存储3.1.1树11基本概念1113.1.2森林5551.1.1有向图与无向图32生成树及最小生成树1.1.2完全图、稀疏图、稠密图321生成树1.1.3顶点与顶点、顶点与边的关系…3322最小生成树1.14顶点的度数及度序列33克鲁斯卡尔()算法1.1.5二部图与完全二部图3.3.1算法思想116图的同构332等价类与并查集1.17子图与生成树3.3.3 Kruskal算法实现118路径56778993.34Boruvka.951.19连通性3.35例题解析1.1.10权值、有向网与无向网34普里姆(Pim)算法图的存储表示341Prim算法思想106121邻接矩阵……342Prim算法实现1071.2.2邻接表15343关于普里姆算法的进一步讨论.11012.3关于邻接矩阵和邻接表的进一步344例题解析111讨论5判定最小生成树是否唯120第2章图的遍历与活动网络问题3.5.1最小生成树不唯一的原因分析.1202.1DFS遍历3.52判定最小生成树是否唯一的方法12122.1DFS算法思想4443.53例题解析212DFS算法的实现及复杂度分析……25第4章最短路径问题1272.1.3例题解析284.1边上权值非负情形的单源最短路径问题22BFS遍历Dijkstra算法12722.1BFS算法思想4.1.1算法思想12722.2BFS算法的实现及复杂度分析…414.1.2算法实现1292.2.3关于DFS算法和BFS算法的说明.434.1.3关于 Dijkstra算法的进一步讨论.1322.2.4例题解析.…434.14例题解析13323活动网络一AOV网络614.2边上权值为任意值的单源最短路径问题2.3.1AOV网络与拓扑排序61一 Bellman-Ford算法…1432.3.2拓扑排序实现方法42.1算法思想1432.3.3关于拓扑排序的进一步说明….6742.2算法实现1452.34例题解析42.3关于 Bellman-Ford算法的进一步24活动网络一AOE网络78讨论1482.4.1AOE网络与关键路径4.24例题解析2.42关键路径求解方法794.3 Bellman-Ford算法的改进一SPFA算法.161第3章树与图的生成树4.3.1算法思想….163.1树与森林…4.32算法实现图论算法理论、实现及应用4.3.3关于SPFA算法的进一步讨论…16564.1基本概念3244.34例题解析……166642最小费用最大流算法32544所有顶点之间的最短路径一Foyd算法…175644例题解析3274.4.1算法思想176第7章支配集、覆盖集、独立集与匹配3404.42算法实现…1777.1点支配集、点覆盖集、点独立集34044.3关于Foyd算法的进一步分析….1807.1.1点支配集3404.44例题解析1807.1.2点覆盖集3414.5差分约束系统7.1.3点独立集4.5.1差分约東系统与最短路径7.1.4点支配集、点覆盖集、点独立集4.52例题解析之间的联系第5章可行遍性问题2087.2点支配集、点覆盖集、点独立集的求解.34551欧拉回路2087.2.1逻辑运算34551.1基本概念及定理2087.22极小点支配集的求解34551.2欧拉回路的判定2117.2.3极小点覆盖集、极大点独立集的52欧拉回路的求解219求解52.1DFS搜索求解欧拉回路21973边覆盖集与边独立集.347522 Fleury(佛罗莱)算法.7.3.1边覆盖集….34753中国邮递员问题2337.32边独立集(匹配)54汉密尔顿回路2347.3.3最大边独立集(最大匹配)与最541基本概念及定理235小边覆盖集之间的联系5.42汉密尔顿回路求解74匹配问题350第6章网络流问题242741完美匹配3516.1网络最大流242742二部图的完备匹配与完美匹配..35161.1基本概念24274.3最佳匹配3526.1.2最大流最小割定理2477.44匹配问题求解的基本概念及思路3526.1.3网络最大流的求解2487.5二部图最大匹配问题的求解3536.1.4般增广路方法7.5.1网络流解法353Ford- Fulkerson算法2487.42匈牙利算法3556.1.5最短增广路算法2567.4.3例题解析6.16连续最短增广路算法- Dinic算法260第8章图的连通性问题.380617一般预流推进算法2628.1基本概念3806.1.8最高标号预流推进算法26581.1连通图与非连通图.3806.1.9网络最大流算法总结2668.1.2无向图的点连通性3816.1.10例题解析2668.1.3无向图的边连通性38262最小割的求解8.14无向图顶点连通性和边连通性的6.3流量有上下界的网络的最大流和最小流.300联系3846.3.1流量有上下界的容量网络8.1.5有向图的连通性6.3.2流量有上下界的网络的最大流.30382无向图点连通性的求解及应用6.3.3流量有上下界的网络的最小流.3048.21关节点的求解6.34例题解析310322重连通分量的求解64最小费用最大流323顶点连通度的求解2目录83无向图边连通性的求解及应用40192.1欧拉公式440831割边的求解401922欧拉公式的应用4418.32边双连通分量的求解4059.3平面图的判定445833边连通度的求解41294图的着色问题44684有向图强连通性的求解及应用416941地图染色与四色猜想4468.41有向图强连通分量的求解算法416942图的着色447842有向图强连通分量的应用418943图着色的应用449第9章平面图及图的着色问题4379.44图着色求解算法及例题解析…..4509.1基本概念…437索引91.1平面图与非平面图437、图论术语索引91.2区域与边界、符号索引4599.1.3极大平面图与极小非平面图.…438、图论问题及算法索引….46914平面图的对偶图439附录本书例题和练习题目录…91.5关于平面图的一些定理439参考文献92欧拉公式及其应用440
- 2020-12-08下载
- 积分：1
