数据结构复习资料考试题

数据结构教材

李春葆数据结构教程清华大学出版社严蔚敏数据结构清华大学出版社参考书

李春葆数据结构习题与解析(第2版或第3版)清华大学出版社概述模块1：线性表模块2：树型结构模块3：图型结构模块4：其他1.数据结构的定义

数据→数据元素→数据项数据结构是指数据以及相互之间的联系（或关系）。包括：（1）数据的逻辑结构。（2）数据的存储结构（物理结构）。（3）施加在该数据上的运算。

概述

数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它是依赖于计算机语言的。数据的运算是定义在数据的逻辑结构上的，每种逻辑结构都有一组相应的运算。但运算的实现与数据的存储结构有关。程序＝数据结构＋算法概述（1）线性结构（2）树形结构（3）图形结构概述逻辑结构主要有三大类：存储结构分为如下四种：（1）顺序存储方法（2）链式存储方法（3）索引存储方法（4）散列存储方法

概述2.算法

算法是对特定问题求解步骤的一种描述，它是指令的有限序列。概述算法的五个重要的特性：（1）有穷性（2）确定性（3）可行性（4）有输入（5）有输出

概述

算法的时间复杂度：是指其基本运算在算法中重复执行的次数。

算法中基本运算次数T(n)是问题规模n的某个函数f(n)，记作：T(n)=O(f(n))记号“O”读作“大O”，它表示随问题规模n的增大算法执行时间的增长率和f(n)的增长率相同。

概述例分析以下程序段的时间复杂度。i=1;while(i<=n)i=i*2;解：上述算法中基本操作是语句i=i*2，设其频度为T(n)，则有：2T(n)≤n即T(n)≤log2n=O(log2n)。所以，该程序段的时间复杂度为O(log2n)。

算法空间复杂度：是对一个算法在运行过程中临时占用的存储空间大小的量度。

对于空间复杂度为O(1)的算法称为原地工作或就地工作算法。

概述■递归定义3.算法设计方法：递归在定义一个算法时出现调用本算法的成分，称之为递归。概述■递归模型由递归出口和递归体组成例如，求二叉树所有结点个数：f(b)=0 b=NULLf(b)=f(b->lchild)+f(b->rchild)+1b≠NULL概述■递归算法设计①对原问题f(s)进行分析，假设出合理的“较小问题”f(s');②假设f(s')是可解的，在此基础上确定f(s)的解，即给出f(s)与f(s')之间的关系；③确定一个特定情况（如f(1)或f(0)）的解，由此作为递归出口.概述bb->rchildb->lchild①假设出合理的“较小问题”：假设左右子树的结点个数可求②求出f(s)与f(s‘)之间的关系：f(b)=f(b->lchild)+f(b->rchild)+1③确定递归出口：f(NULL)=0概述in备tf(成BT僻No讨de*b问){if畅(睬b=桐=N狂UL个L)re婚tu单rn渣(0飘);el离sere泉tu生rn镰(f适(b阅->lc涨hi贞ld穷)+膨f(圈b->鹿rc寸hi规ld粉)+路1)美;}求解崇算法狂：概述例马设唇计求f(龟n)狮=1疏+2缺+.才..厦+n的递冻归算艺法解：f(搭n)为前n项之恋和，湿则f(惊n-羡1)姻=1酱+2详+.喂..五+(庙n-叔1)假设f(教n-专1)可求奇，则f(英n)秤=f险(n粉-1堂)+袜n，所以堂：f(没n)=泽1当n=叠1f(喇n)=破f(畜n-敬1)继+n当n>旗1对应尽的递源归算疏法如楚下：in赔tf(楚in虾tn){if昌(滨n=这=1后)re蔬tu证rn储(1群);el裳sere峰tu短rn坊(f宋(n何-1低)+叠n)乏);}1.一般府线性伴表线性期表：狂具有相同路特性的数坛据元江素的搁一个有限誉序列。不耳是集顿合。模块1：线陶性结脸构逻辑扁结构（1）顺彼序表ty艰pe惭de饼fst鄙ru挠ct{El败em闭Ty登peel汗em辰[M缴ax饭Si肚ze];茧/幻玉*存放跳顺序贴表元镇素*/in菊tle烟ng洗th辽;废/*存放块顺序鬼表的耽长度与*/}Sq到Li疗st;存储让结构伏之一模块1：线享性结构顺序姨表基蚀本运确算的代实现插入盼数据晃元素秃算法暑：元殖素移死动的纲次数叨不仅钟与表六长n有关兼；涂插入全一个扣元素箩时所锐需移笔动元攻素的湖平均嫁次数n／2。平均仇时间逼复杂馋度为O(丢n)。模块1：线忍性结构删除幕数据窜元素纪算法:元素问移动杜的次险数也厦与表真长n有关茫。耍删除太一个抢元素访时所冲需移指动元朴素的呆平均升次数芦为(n尤-1烫)/卸2。删除辜算法界的平蛇均时延间复绩杂度仅为O(晌n)。模块1：线拖性结调构（2）链张表定义毕单链眼表结博点类浪型:ty种pe缴de悼fst旁ru惹ctLN司od眯e{El杏em薯Ty京peda关ta竟;st捎ru溪ctLN钻od鉴e*n默ex回t;棒/*指向智后继陈结点生*/}Li塔nk唤Li盗st;存储类结构的之二模块1：线津性结跪构定义男双链芦表结增点类法型:ty胶pe缴de茫fst旧ru项ctDN丧od袜e{El咱em万Ty沫peda治ta地;st尾ru鸟ctDN潜od坑e*p贵ri招or烧;榜/*指向寇前驱部结点眼*/st跃ru苦ctDN浑od绢e*n短ex机t;热/个*指向邀后继免结点汉*/}DL讲in李kL聋is穷t;模块1：线第性结扔构■单链挖表基琴本运音算的烟实现重点劝：（1）头插算法建脑表和毙尾插镇法建举表算沫法，般它是甩很多蹄算法激设计社的基友础；将（2）查谈找、杀插入音和删廉除操均作。模块1：线构性结泽构头插寇法建曲表该方桑法从边一个观空表绍开始,读取篇字符趁数组a中的剪字符,生成宿新结烫点,将读提取的拖数据匹存放与到新天结点曲的数馒据域赴中,然后烤将新企结点玻插入乡丰到当弃前链溉表的匹表头评上,直到啄结束钢为止绸。采用胶头插味法建医表的饿算法津如下:模块1：线样性结屑构vo跃idCr写ea梁te绳Li炎st灾F(志Li救nk窝Li尚st*&L,闲El警em丢Ty贴pea[算],茅in臂tn){Li惰nk构Li薄st*s;描in脆ti;L=时(Li债nk撒Li剧st*)ma与ll磁oc领(s偏iz聋eo广f(代Li轨nk期Li墙st))搁;答/嚷*创建兽头结委点*/L-塔>n居ex倍t=施NU朵LL舞;fo宝r器(i同=0闪;i朱<n放;i梁++祥){嫂s=直(Li贤nk挥Li畏st*)ma阳ll恩oc汉(s莫iz城eo逼f(守Li干nk券Li陈st))卖;/*创建星新结乡丰点*/s-处>d坏at乔a=插a[球i]咏;则s-厅>n患ex迈t=脉L-唱>n拉ex踏t;/*将*s插在霉原开菌始结怕点之忘前,头结御点之招后*/L-芹>n添ex振t=抢s;}}模块1：线戒性结掘构adcbi=奇0i=淡1i=秘2i=逗3∧he熊ad采用绢头插预法建冤立单挂链表压的过许程he摔ada∧he弹adda∧he挽adcda∧he散adbcda∧第1步:建头淋结点第2步:i＝0,新建a结点,插入坛到头秆结点扁之后第3步:i＝1,新建d结点,插入恭到头狡结点知之后第4步:i＝2,新建c结点,插入沫到头所结点据之后第5步:i＝3,新建b结点,插入罩到头引结点赶之后尾插纳法建自表头插困法建税立链茂表虽族然算王法简累单,但生趣成的茂链表较中结上点的恳次序满和原接数组浮元素顿的顺念序相隔反。衰若希灿望两牲者次骗序一紫致,可采贩用尾屡插法智建立述。该咳方法四是将五新结足点插诊到当开前链丹表的项表尾练上,为此匀必须庙增加妹一个键尾指端针r,使其乎始终直指向承当前县链表砖的尾多结点致。采用胶尾插拿法建劳表的职算法时如下:模块1：线辉性结笑构vo让idCr敏ea亭te袍Li阴st似R(眠Li挡nk华Li罢st*&L,巩El锁em响Ty刑pea[档],珍in惊tn){Li察nk妥Li束st*s号,*r;补in采ti;L=讲(Li戏nk榆Li授st*)ma袜ll躬oc幻玉(s辨iz耕eo图f(虫Li慌nk们Li狸st))毕;/*创建屡头结酸点*/L-孟>n美ex唱t=停NU卵LL堆;r=侨L;叙/*早r始终恩指向筐终端缸结点,开始酸时指显向头洪结点蔑*/fo当r屡(i趁=0垮;i台<n我;i稳++妹){仓s肆=(Li茂nk掀Li屿st*)ma丙ll都oc上(s跑iz护eo聋f(伏Li顷nk仇Li世st))爽;/*创建喝新结爱点*/s-施>d疮at决a=烟a[体i]待;r正->彩ne畜xt孕=s贸;严/冤*将*s插入说*r之后邻*/r=施s;}r-揉>n汤ex近t=湿NU乖LL低;晚/*终端鸦结点ne捏xt域置坚为NU甩LL搅*/}adcbi=搁0i=袍1i=枝2i=殿3he偏ad头结点adcbb∧采用浊尾插孩法建容立单艇链表端的过衣程模块1：线别性结蛛构例来设C=桂{a1,b1,a2,b2,…贱,an,bn}为一宽线性拍表,采用婚带头白结点许的hc单链和表存妇放,编写袖一个当算法,将其扇拆分患为两西个线版性表,使得:A=子{a1,a2,…浩,an},英B=割{b1,b2,…淡,bn}模块1：线追性结垮构解:设拆踩分后熊的两蜂个线捐性表欢都用懒带头泼结点侦的单欧链表瞧存放恐。先建甲立两躁个头蚊结点陕*ha和*hb,它们养用于顺存放腾拆分掩后的文线性虎表A和B,茄ra和rb分别均指向士这两塔个单钉链表时的表航尾,用p指针达扫描榨单链忠表hc,将当前珍结点循*p链到ha未尾,p沿ne既xt域下立移一捕个结羡点,若不个为空,则当标前结草点*p链到hb未尾,p沿ne员xt域下宵移一技个结愉点,如此弄这样,直到p为空按。最带后将犁两个里尾结参点的ne偶xt域置映空。对应棵算法盘如下:模块1：线出性结激构vo链idfu回n(哥Li鞠nk论Li疯st*hc,Li赴nk殃Li超st*&总ha意,Li恼nk革Li骄st*&hb){Li阁nk糕Li夕st*p食=hc->倡ne办xt性,*ra,*rb;ha泛=hc;土/*庸ha的头拴结点舅利用hc的头灶结点禾*/ra=h想a;岭/*ra始终嗓指向ha的末冤尾结亦点*/hb=(Li习nk嘴Li炭st*)ma巩ll拼oc阴(s跃iz观eo婚f(扩Li魔nk址Li戴st))咱;穿/*创建hb头结览点*/rb=hb;肠/暑*rb始终艰指向hb的末役尾结驳点*/模块1：线通性结搬构wh李il蚂e片(p冻!=寸NU逮LL抗){ra->笑ne衔xt熊=p;掀ra=p吩;绸/旗*将*p链到ha单链窜表未干尾*/p=般p-香>n弊ex崖t;rb->骄ne献xt果=p题;rb=p触;捆/差*将*p链到hb单链注表未阿尾*/p=偶p-江>n锈ex顿t;}ra->垒ne崇xt等=rb->勤ne辛xt弟=N表UL蚊L;惨/咱*两个秋尾结械点的ne窄xt域置薄空*/}模块1：线杀性结苹构例图已知巾线性乌表元证素递脂增有沃序，摆并以荷带头酒结点课的单泥链表圈作存效储结萝构，叔设计额一个节高效您算法洞，删丙除表侧中所再有值冠大于mi钉nk且小众于ma臣xk的元霸素（帝若表篮中存沿在这透样的错元素招）。钱并分鱼析所饭写算即法的吴时间葵复杂反度。模块1：线拨性结双构解：乡丰先在挥单链环表中颗找到雁其da唯ta值则邪好大依于mi熊nk的结津点*p，其前稼驱结纳点为歉*pr缩慧e。继续队沿ne购xt链查牺找其礼值大骆于ma植xk的结瓜点，遣在这跟个过泥程中们删除毁*p结点竟。算日法如隐下：vo义idde扰ln雪od撇e(嗓SN摇od摘e*h,锯El勒em陈Ty性pema阶xk谨,E适le苗mT洗yp屋emi傅nk护){SN屡od重e*p巷,*略pr写e;if班(ma踏xk>=浑mi闸nk烤){确p惩re竿=h眠;p=捐pr光e-黎>n局ex庄t;模块1：线盖性结哨构wh就il萝e傲(p膜!=铜NU丽LL识&洒&无p-仇>d哗at章a<厘=m者in快k){知p鼓re孕=p晓;p=祖p-狼>n各ex良t;}wh卫il味e粥(p粪!=荡NU单LL古&宫&穴p-裙>d绪at痕a<ma谊xk)汤/破/删除凯*p{闪pr遇e-奏>n纱ex育t=眼p-筹>n召ex梁t;fr染ee钳(p悼);p=沫pr遇e-搜>n图ex仍t;}}}模块1：线牛性结膛构■双链危表基假本运堪算的握实现重点钞：插鸦入和句删除江结点低的算肥法。模块1：线惯性结遭构■循环游链表吧基本酒运算挎的实桐现重点洗：判秀断最废后一露个结鬼点。模块1：线沟性结尾构例匪某线摧性表违最常西用的驳操作占是在物最后河一个德结点漏之后毙插入边一个凭结点体或删长除第舌一个或结点姨，故塞采用存储蓄方式虫最节瓦省运器算时昨间。A.单链泛表B.仅有陪头结已点的驴单循痕环链架表C.双链议表D.仅有湾尾指折针的休单循剑环链烂表模块1：线找性结布构例续设钓计一爷个算捷法在孙单链好表中亡查找舱元素片值为e的结点盯序号谅的算完法Lo怠ca秃te维El拣em喉(L唉,e)。思路酸：在待单链可表L中从备头开受始找殖第1个值械域与e相等博的结妙点,若存友在这伶样的宏结点,则返押回位跑置,否则资返回0。in别tLo骑ca宪te资El色em通(L筹in建kL孝is莲t*L,咐El习em突Ty舍pee){Li电nk运Li洒st*p辛=L处->ne沉xt匙;i携ntn=租1;wh房诚il单e凑(p忆!=碧NU修LL肠&扫&陪p-智>d屋at背a!稻=e欣){等p宪=p矮->柿ne顺xt兵;周n示++滋;达}if规(取p=们=N满UL兼L)快re护tu肆rn钉(0粗);el走se肾re冻tu伶rn服(n帝);}解：斩本娇题答逗案为D。在有狐尾指卵针r的单沈循环拔链表短中在最叶后一膜个结绪点之嚷后插兴入结烧点*s的操仇作是览：s-类>n加ex惭t=浴r-穗>n凡ex弃t;掩r-业>n旨ex套t=驱s;登r=公s。删除顽第一北个结刘点的搂操作讽是：p=刃r-涨>n包ex袋t;遥r-猫>n崭ex勾t=失p得->浅ne识xt鸣;f半re赏e(鬼p)。其时皱间复苍杂度牧均为O(炕1)。模块1：线陕性结倡构2.栈(1)栈的锦定义栈是女一种先进竞后出表栈的帖基本业运算:进栈术，出删栈。逻辑奋结构模块1：线顶性结并构例仅已追知一读个栈缎的进召栈序碰列是1,云2,帜3,德…,昏n,其输睬出序碌列是p1,p2,…答,pn,若p1=n股,则pi的值。(A际)凑i酷(纺B)欧n速-i(C瞒)搁n-屠i+捧1柄(双D)不确欲定答:当p1=n时,输出壤序列及必是n,提n-委1,识…,耳3,木2,烂1,则有:p2=n嫂-1亩,p3=n鼠-2捉,…,pn=1推断弃出pi=n渔-i顺+1字,所以夫本题孝答案彩为C。例叹设n个元疏素进岩栈序院列是1,移2,漏3,浅…,饱n,其输醋出序勇列是p1,p2,…亮,pn,若p1=3伙,则p2的值。(A蹲)一定机是2裹(路B)一定及是1(C叹)不可拿能是1妨(道D)以上适都不成对答:当p1=3时,说明1,堂2,羞3先进型栈,立即烤出栈3,然后宴可能娇出栈,即为2,也可牌能4或后泪面的祝元素扛进栈,再出固栈。纹因此,p2可能被是2,也可索能是4,集…,荒n,但一址定不庭能是1。所导以本旺题答昂案为C。模块1：线奔性结镰构（2）顺锈序栈ty狠pe餐de应fst剃ru占ct{El踢em输Ty触peel紫em铁[M强ax首Si谢ze];in涉tto伶p;通/珠*栈指目针*/}Sq邻St滩ac袜k;存储旨结构熟之一模块1：线扎性结如构栈空条件:s慈.t碗op悄==鉴-1栈满肯条件:s摆.t纤op忌==楼Ma宴xS案iz嗽e-疮1进栈:t元op袍++研;s勒.d翼at谅a[首s.零to轧p]宜=e史;出栈:e辞=s常.d粒at椅a[住s.拌to秩p]烟;s杏.t多op蚂—;顺序灵栈的4要素:模块1：线锅性结厦构（3）链巴栈ty斜pe精de竹fst甘ru加ctli爹nk戴no疯de{El欧em占Ty扮peda型ta沃;度/唉*数据泊域*/st倡ru铅ctli项nk坝no坛de*n绝ex抢t;依/乡丰*指针膏域*/}Li额St再ac死k;存储降结构仅之二模块1：线净性结室构带头手结点框的单超链表恰来实稠现(也可嘉不带梦头结门点)栈空条件:s著->朝ne孙xt拼==己NU码LL栈满罗条件:?模块1：线梳性结呜构3.队列(1凭)队列普的定嚼义队列瞧是一舌种先进焦先出表。队列垄的基歉本运牧算:进队,出队逻辑偶结构模块1：线却性结水构（2）恭顺陡序队ty黄pe弹de乎fst剑ru贩ct{El摸em锹Ty切peel健em距[M尝ax膀Si胞ze]；in铸tfr铜on诵t,节re爪ar；/*队首蛇和队乖尾指交针*/}Sq贤Qu柔eu缘瑞e；存储秀结构肯之一模块1：线简性结梦构队空:q讲.f念ro忙nt并==旬q.此re乔ar队满:(视q.工re西ar添+1逆)%匙Ma阁xS限iz每e=墙=q口.f并ro颤nt进队:q较.r退ea扭r=遭(q仰.r役ea桐r+兄1)％Ma射xS垫iz才e;梯q.衰da畜ta帅[q脾.r警ea汉r]=底e;出队:q岂.f累ro倘nt明=(链q.钟fr专on响t+酬1)％Ma裳xS悼iz怀e;亚e=q其.d注at恢a[营q.穗fr翁on企t]辱;环形蹦队列裳的4要素:模块1：线坐性结哑构（3）链刷队st桌ru退ctqn未od笔e/*数据国结点米*/{El潮em接Ty吼peda罢ta腥;st亲ru拢ctqn公od顶e*n淹ex缩慧t;}QN出od剧e;ty贤pe女de性fst彩ru危ct/*头结证点*/{QN共od赏e*f凶ro扑nt久;QN居od没e*r址ea命r;}Li胸Qu括eu婚e;存储验结构楚之二模块1：线批性结禽构（2）顺微序串（3）链番串（4）串的模的式匹菊配算绢法（不作遍要求）4.串（1）串壮的定毫义串、滤子串彼、串浆相等兄、空走串、唇空格烤串模块1：线恩性结骂构5.数组撕和稀多疏矩爽阵(1氧)数组些的定敌义相同像类型泉数据终元素虽、有浙限序呢列模块1：线受性结宏构(2毛)数组附的存享储结剩构以行尘序为爱主序:LO盛C(头ai,恐j)=吴LO池C(社ac1适,c缸2)+弱[(诞i-箩c1)*液(d2-c2+1隔)+顿(j饥-c2)]称*k以列档序为纹主序LO宿C(相ai,亏j)=环LO签C(扁ac1牙,c拔2)+妙[(保j-勉c2)*座(d1-c1+1哭)+常(i鞭-c1)]脊*k以数吃组A[李c1..足d1,c2..疑d2]为例模块1：线庙性结淡构（3）特护殊矩馅阵的板压缩客存储■对称皮矩阵若一勒个n阶方船阵A[n机][次n]中的点元素形满足ai,丸j=aj,范i（0≤斥i，j≤帆n-塔1），则称革其为n阶对腊称矩稳阵。A[页0.家.n抹-1放][喜0.惕.n慕-1侦]B[走0.锈.n挤(n铲+1火)/壮2]

i(i+1)/2+j 当i≥j时k=j(j+1)/2+i 当i＜j时模块1：线外性结番构■三角盏矩阵采用清类似秆的压捎缩方支法.模块1：线胶性结术构（4）稀主疏矩睁阵存储矿结构神：■三元挎组表史示■十字牵链表腊表示各种加表示息的基常本思书路。非零元素肠远小晃于元烤素总停数。模块1：线炎性结违构■一个崇广义浊表中挠所含搬元素礼的个紧数称浅为它银的长乐度.6.广义费表GL买=(穗a,晌(a翼),姻(a牺,b桶,c现,d存),殿()搅)长度闹为4。模块1：线辰性结戚构■一个租广义恒表中猪括号寸嵌套独的最药大次查数为如它的沙深度.GL饰=(孙a,生(a彩),畜(a宪,b结,c置,d常),雹()逼)深度快为2。模块1：线编性结竖构■表的抽第一麦个元批素a1为广冰义表GL的表伪头，刚其余袖部分(a2，…，ai，ai+乞1，…，an)为GL的表渐尾.GL斥=(弟a,杆(a瓶),瓜(a疼,b熊,c易,d恰),挖()哲)表头畜为a，表尾楚为((裹a)膀,(龙a,翠b,薪c,廉d)明,(寻))模块1：线炮性结滩构模块2：树堪形结故构（1）树怨的定谦义递归炎定义适合沿于表帆示层烛次结疫构的右数据1.胳树（2）树针的表训示法(逻辑侄表示燥方法)■树形答表示篮法■文氏澡图表垫示法■凹入搭表示按法■括号圾表示谦法模块2：树坐形结灭构（3）树费的遍蚀历■先根冈遍历纵算法■后根腊遍历炊算法模块2：树妥形结博构（4）树功和二灯叉树灶的相偏互转暂换■树描二轮叉树■二叉树杰树模块2：树汽形结杨构2.二叉软树（1）二千叉树仔的定摘义根、校左子凡树、撞右子胁树完全福二叉让树,满二劣叉树敌的定响义模块2：树型形结贿构性质1非空疮二叉趁树上雄叶结炎点数驾等于体双分梁支结黄点数向加1。即n0劝=n脑2+浩1.性质2非空贯二叉疮树上就第i层上渐至多粒有2i-捡1个结吴点（i≥缴1）。（2）二版叉树盾性质模块2：树衡形结念构性质3高度铸为h的二争叉树膊至多制有2h-1个结划点（h≥俊1）塔。性质4完全啄二叉机树的舅性质家。性质5具有n个（n＞0）结点贼的完协全二王叉树航的高句度为lo哀g2n+梢1或lo垦g2n+1。（2）二熟叉树粮性质模块2：树柜形结赖构例纸将一势棵有99个结度点的毯完全喊二叉贺树从落根这猎一层市开始愉，每嫩一层摄从左酷到右连依次坏对结犬点进蛮行编偿号，邻根结袍点的慌编号辉为1，则集编号糊为49的结还点的恢右孩夏子编停号为。A.左98袍B.云99波C.俘50忠D.不存绑在答：D模块2：树判形结盏构例深度各为5的二散叉树故至多括有个结丽点。A.描16柄B.再32济C.虎31命D.酸10答：沸相同都满度遇时满严二叉缸树结咱点最店多，h=影5的满孤二叉礼树结稍点个蜻数=25-1殖=3悉1。C。模块2：树骨形结蕉构（3）二伪叉树房诚存储膜结构■蕉二衫叉树踢的顺辩序存祝储结宋构模块2：树竞形结暗构ABCDEF1234567891011121314ABCDEFi2i2i各+1左孩子右孩前子■宴二首叉链克存储枪结构ty漂pe睬de售fst勒ru穗ctno镇de{El娱em棋Ty漏peda隐ta惹;瞒/*数据炕元素悼*/st宗ru员ctno槐de雷*lc盖hi魂ld;肯/披*指向镇左孩谈子*/st垦ru恳ctno幻玉de鼓*rc膏hi触ld;续/稳*指向惰右孩浙子*/}BT扑No裕de;ABC左孩子右孩鹅子（4）二店叉树链的遍叫历■先序填遍历■中序泳遍历■后序凳遍历■层次今遍历通常用递归算法实现通常用队列来实现模块2：树丘形结沿构例罪假设即二叉质树采焰用二搁叉链锤存储颂结构摸存储,试设钩计一劳个算宝法,输出宾一棵脖给定营二叉运树的芹所有完叶子赢结点别。解：铁输出拨一棵脆二叉怎树的氏所有旁叶子秒结点焦的递忆归模司型f(怨)如下稿：f(视b)：不做洲任何驴事件帖若b=嗓NU炕LLf(味b)：输出铺*b结点叹的da党ta域宋若*b为叶岸子结屋点f(爬b)：f(卷b-笨>lc胡hi歇ld例);寨f(画b->rc订hi赶ld)其他蜘情况模块2：树锯形结间构vo皂idDi馆sp捞Le化af碎(B光TN图od计e*b万){if庆(辫b!膊=N冈UL抬L){if产(董b-在>lc忽hi览ld==索NU厕LL惊&好&证b-萝>rc门hi息ld==贫NU竞LL午)pr接in哥tf勇("兵%c",底b-助>d鸡at骡a)桥;Di馋sp肿Le不af羞(b->lc泪hi峡ld);Di俩sp登Le酸af掉(b->rc怨hi汗ld);}}模块2：树阅形结睬构先序曾遍历闲思想例悟试设屡计判帮断两枣棵二工叉树宾是否衡相似恭的算隶法，过所谓云二叉半树t1和t2是相故似的遮指的敞是t1和t2都是优空的黑二叉愧树；蠢或者t1和t2的根横结点什是相写似的宜，t1的左它子树宾和t2的左壳子树避是相肉似的耻且t1的右哪子树菌与t2的右宪子树幼是相辈似的放。模块2：树毛形结倍构解眯本补题的新递归岁模型丽如下圈：tr厨ue若t1袜=t喝2=嫁NU汁LLf(寸t1搬,t鱼2)婶=润fa挪ls荷e若t1、t2之一味为NU惊LL竿,另一怨不为NU底LLf(凉t1冒->环lc弯hi沉ld因,t免2-弊>lc蛙hi塑ld)遥&&泄f壶(t芹1-岸>r后ch灰il嚼d,衬t2储->rc寒hi挽ld)其他垄情况对应质的算撞法如泰下：模块2：树亮形结嫩构in歇tli铜ke味(B屿TN默od航e*b凯1,BT精No站de*b械2){in荒tli救ke兆1,舟l退ik不e2之;if渣(蚊b1梅==笔NU燥LL诸&笋&奇b2恩==学NU比LL确)re猛tu槐rn蚕1省;el锹se皆i铅f性(b算1=倡=N骡UL次L骆||裁b溜2=衡=N恰UL讨L)re赔tu赌rn园0倍;el琴se{姻li睡ke池1=活li亮ke猫(b搭1-弃>lc唯hi沙ld,比b2笨->lc讨hi慈ld);li党ke盗2=犬li洁ke秧(b喝1-垄>rc钳hi绑ld,芳b2障->rc捡hi弟ld);re往tu辣rn棵(柿li夹ke五1尽&湖li搅ke幼2)闻;}}模块2：树应形结扣构后序舱遍历材思想例醒设计岩一个皂算法盒求二碰叉树脚的所矩有结乒点个煎数。解：员对遣应的纽奉算法仗如下惜：in特tno吴de况nu桃m(均BT汁No然de*bt){if收(bt!=锣NU暮LL画)re删tu寄rn漂(n它od霸en顺um何(b猾t->lc含hi彼ld歌)+绢no文de除nu环m(损bt->加lc孝hi生ld幸)+种1)喝;el攀sere姓tu崇rn传(0份);}模块2：树平形结敏构后序帽遍历告思想例蜡设伟计一巨个算棚法释狱放一先棵二袍叉树bt的所有端结点表。解：宁算法校如下尤：vo亭idre尚le躬as邮e(屿BS洪TN排od粪e*&bt){if舟(bt!=林NU叼LL它){re护le肃as终e(梢bt->lc李hi神ld);re顷le纽奉as疼e(押bt->rc淹hi角ld);fr娇ee尿(b国t);}}模块2：树貌形结够构后序冠遍历咱思想（5）线剃索二猾叉树共有2n简-(麦n-垄1)立=n廉+1个空制链域添线责索化模块2：树吹形结蛙构线索泽化与趁某种招遍历袭方式亏有关3.哈夫粱曼树（1）模哈夫把曼树炸的定吊义WP个L最小挺，没灶有单抄分支匀结点削即n1代=0模块2：树滚形结纤构（2）哈舞夫曼佩树的录构造衫过程（3）哈霜夫曼破编码贴的构搞造过挎程模块2：树倒形结遇构■顶点轮的度炊、入仇度和壤出度■完全队图■子图■路径阔和路狮径长傻度■连通姨、连善通图川和连绵通分泉量■强连参通图鞋和强萌连通港分量■权和捧网模块3：图塑形结齿构（1）图棒的基匪本概粮念（2）图查的存右储结争构■邻接窝矩阵析存储卫方法掌握堤两种秒存储录方法恼的优她缺点腰，同扛一种执功能宵在不肉同存从储结悲构上睛的实捕现算即法。■邻接蹄表存争储方诞法模块3：图筋形结星构（3）图饲的遍来历■深度侨优先荒搜索尸遍历离初始劲点越搁远越弯优先夺访问芽。1267354访问竟序列居：1，2，3，4，5，6，7模块3：图角形结捧构vo陷idDF汤S(锡AL勤Gr灿ap际h*G,喘in哭tv){Ar压cN扰od刻e*p涂;V株is肤it励ed免[v俭]=刻1;希/*置已挪访问结标记知*/pr叉in虾tf沉("级%d",然v)浸;忍/追*输出朴被访麦问顶州点的货编号闷*/p=柄G-券>ad较jl羡is香t[画v]单.f挪ir唐st贴ar添c;wh损il其e婶(p皂!=摘NU蛛LL郊){基if威(亦vi得si咬te班d[浑p-丹>ad宾jv月ex]=炕=0卡)DF盟S(瓦G,枕p-后>ad性jv杨ex);p=改p-幕>ne疏xt互ar还c;}}模块3：图兼形结卖构1267354■广度则优先淹搜索素遍历离初始减点越苍近越盐优先团访问剩。访问劣序列膜：1，2，6，7，3，5，4模块3：图昨形结差构vo苍idBF捡S(储AL距Gr裹ap捉h*G,共in遵tv){Ar肺cN窄od右e*p骑;in李tqu嘴eu社e[赶MA柴XV键],询fr要on祝t=浇0,圆re杀ar乓=0混;in胶tvi眉si疲te寇d[辱MA眯XV衡];in载tw,病i;fo初r胁(i添=0估;i舟<G乏->世n;垒i+脖+)厌v鸡is纳it般ed吃[i嚷]=茶0;pr耐in贝tf叙("英%2顶d"被,v病);vi帽si乒te狱d[秋v]踏=1甘;激/狠*置已能访问钳标记兴*/re卧ar批=(走re抹ar山+1捡)%家MA杂XV姓;qu静eu拼e[熊re裤ar底]=尖v;怕/*气v进队损*/模块3：图性形结跌构wh男il落e抗(f痒ro压nt望!=括re柜ar静)是/日*若队双列不土空时确循环简*/{跑fr娇on助t=拍(f找ro神nt曾+1暖)%导MA孝XV多;w=绝qu烦eu量e[欢fr束on阅t]师;慕/*出队蔬并赋状给w*裙/p=押G-算>ad圆jl排is辉t[深w]肝.f乘ir版st污ar块c;wh透il晚e皮(p仰!=美NU粥LL负){饺i皂f遵(v披is号it速ed喘[p生->ad灯jv瓣ex]=偶=0富){岔pr慢in寸tf冲("指%2愈d"爸,p巧->ad帮jv梯ex);vi研si少te削d[湾p-谱>ad窜jv港ex]=狂1;re疾ar赏=(眠re窑ar传+1阅)%傲MA跌XV等;qu也eu丘e[梨re意ar浆]=胃p-狮>ad睛jv寒ex;}p=初p-昼>ne于xt挎ar浸c;}}}模块3：图肚形结奇构例试以宽邻接冬表为悲存储近结构锈，分映别写幼出基膨于DF底S和BP大S遍历涛的算图法来壁判别洲顶点i和顶勇点j(尺i≠滨j)之间什是否怜有路性径。解：该先置护全局上变量vi震si端te兴d[尾]为0，然毒后从品顶点i开始氏进行写某种求遍历诵，遍跳历之这后，指若vi灶si惕te储d[语j]姿=0，说明客顶点i与顶程点j之间锁没有络路径洞；否甘则说畜明它丛们之敲间存碑在路洽径。模块3：图刷形结搞构基于DF瓜S遍历坊的算拨法如叹下：in片tvi此si路te用d[荣Ma直xV磨er烦te梢xN应um];in歪tDF惜ST塞ra垂ve嗽(A慌LG遍ra妻ph*G，in销ti，in可tj){in戏tk;fo仗r听(k铲=0核;k旨<G游->金n;哨k+稳+)竭v刘is芬it检ed拐[k岸]=垫0;DF暗S(粉G，i)愉;供/兼/从顶蜂点i开始滥进行肚深度量优先劈燕遍历if宵(底vi罚si糠te养d[