《数据结构基础教程》习题及解答.docx

ptr=r->Ncx(:)7.一个单能表1.k的表头指针为1.kj不同结点的Data域值有可能相同,期"个驾法，功能是计算出Daui域值为X的结点的个数，答：算法应当遍历链表的每一个结点，遇到一个结点的Ddla域侑为X时，计数器n就加1。最终返回计数器!UC<Minl-1.k(1.k-h)(n=0;p<r=1.kJi;whileIplH:NU1.1.)(if(pr->Dau=x)n=n*l;ptr=p<r->NextIreturn(n):第3章习题解答一、填空限定插入和删除操作只能在一端进行的线性表,被称为是2 .假如在依次栈满时仍准备进行进栈操作，就称为发生了“上溢”出错.3 .黄如在依次栈空时仍准爸迸行出栈操作，就称为发生了“下溢”出错，4 .在具有“个数据结点的循环队列中，队满时共有个数据元素。5 .忸如操作依次是先让字母A、B,C进栈.做两次出栈：可让字母D、E.F进栈，做一次出栈：最终让字母G进栈，做三次山栈.最终这个堆校从校顶到栈底的余留元素应当是_DA_.6 .中一衣达式(u+bMc(d÷e)洌应的后衣达式是abde+/-)7 .函数的递灯调用行两种形式：假如一个函数是干脆调用自己.就称其为一曲递归阿用：假如一个函数是通过另一个函数来调用自己，就称其为间接递归正用.8 .设某栈的元素输入依次是I、2、3、4、5.S!得到4、3、5、2、1的输出依次。那么push,pop的操作序列应“i是push、push、push、push*pop、pop、push、pop、PoP、POP，9 .设鞋栈的栈顶指针为1.sop.那么它非空的条件应当是1.Stop!=Nu1.1.10 .队列中，允许进行删除的一米称为队首.二、选界1. 一个栈的元素进栈序列是a、b、c、d.e,瘠么下面的C不能做为一个出栈序列.A.c»d、c、taB.d、e、c、b、aC.d、c、e、a、bD.a、b、c、d、eelseH队列/空！/qlr=Qx_tr<>nl：while(qtr<=QJrcar)IPnrHf*qr>:qlr*+：3.编写一个算法，它能够取得链式队列首元素的值。答：取得链式队列百元索的值,只有在队列非空的前途下才有意义。算法端写如卜GetfJ-q(lA|_fr(»nt,lxi_rcair)(if(1.q_fron(=1.q_tear)/队丹f!*fprinl(Ibelinkedqueueiempty!、else卢队列作空！/(tr=1.q_front->Ncxi:x=pcr>l(a;return(x);I)4 .有万.个人依次坐在一起，问第5个人多少岁，回答说比第4个人大2岁：问第4个人多少岁.回答说比第3个人大2岁：何笫3个人多少岁.回答说比第2个人大2岁：问第2个人多少岁，I可答说比第I个人大2岁：问第I个人多少岁，叵1答说是IO岁.试给出该递归的公式、结束条件，并编写出相应的遢心算法，答；递归公式为：agc(n)=agc(n-l)+22<=11<=5递日的结束条件是：age(l)=10相应绊法为：Age(n)(if(n=I>return(IOkelse(x=ag<!(nl)*2rcur11(K);I)5 .将中缀表达式转化为后级表达式的方法类似于中级表达式求伯。详细地，要开拓一个运蚱符栈。P和一个数组st,在自左至右扫描算术表达式时，遇到操作数就干脆依次存入的比较而得到的结论.6 .设有或klamateacher,.该一的长度是14.设有三个申：SI="Good"，s2="",s3=-bye!,eWlsi,$2、s3连接后的站果申应当是6otlbve!”，7 .所谓“数组”,是指”(n>l个具有相同类型的数描的有序集十.8 .矩阵与通常所说的二数组有关.9 .所谓“特别矩阵”,是指那些元素在矩阵中的分布具干i确定规律性的矩阵：而矩阵中的零元崇个数远远多于非零元素的个数,但非零元素的分布却没有规律，这样的矩阵被称为“稀"矩口10 .在一个”阶方阵A中，若全部元素都有性质：ay=1(7n).就称其为对林矩二、选异I.设有两个由Sl和$2.求s2在SI中首次出现的位置的操作称为_5_.连接B.模式匹桎C.求子申D.求申长2 .有用：P那么它的长度是B。A.0B.1C.2D.33 .设有率sl='ABCDEFG'Bs2=PQRST-.已知：尊法COn(x.y)返回中X和y的连接申；SUbS(S.i.j)返回申S的第i个字符起先往后j个字符殂成的子中：Ien(三)返回申$的长度.那么，COn(SUbS(si.2,Ien(s2)>.subs(sl.Ien(s2).2)的操作结果是用D。A.BCDEEB.BCDEFGC.BCPQRSD.BCDEMiFA.33B.30C.13D.235 .一个由”的对称电阵,假如以行优先的方式压缩存入内存.那么所需存储区的容量应当是C.A.m*(m-l)1f2B.ntt,tn2C.M(m+X2D.(m+1)(«+1X26 .二维数组M的每个元素含4个字符(句个字符占用一个存储单元),行卜标，从1变到5.列下标j从I交到6,那么按行依次存储时元素MHH6的起始地址与M按列依次存储时元素立的起始地址相同，A.M351B.M451C.M461D.M(51157 .二维数组M中的每个元素占用3个存储单元，行下标i从1变到8.列下标j从!变到10.现从首地址为SA的存储区起先存放A.那么该数组以行优先存放时,元素A85的起始地址应当是.SA+141B.SA+180C.SA+222D.SA+2258 .设有一个S阶上三角矩阵A,将其元素按列优先依次存放在一维数组B中.己知年个元素占用2个存储单元,B川的地址是I(Xh那么A网闾的地址是工_.A.116B.118C.120D.122(分析：把一个上三角矩阵按列优先依次存放在一个一维数组B中，元素的依次是：aa2a22a3A3.4的地址=100+3前面的元南个A*2=I(XH(前3列的个数+本列a”前面的个数*2=100+<(l+2+3)+2>*2=116Moveij(St,i,j)(if(i+j<三StJcn)(for(k=i+j;k<=S(_lCT；k+>*将i+j起先往后的全都字符的移j个位贸/SUk-j=S<k;St_len=Sj_lai-j;SiISi-Ien=,'J"I*修改SI的长度*)/安胶款的小结束符/Prin参攻不合理,无法进行BH除【,I;)6.在算法412的最终,为了群放被刷结点运用的存储空间,先做了操作:p<r->Ncxt-NU1.1.;把出指计Pu指向的最终个要林放宽间的结点的Next域设汽为NU1.1.,然后通过while循环完成择放.其实，由于知道要移放空间的结点共有r个，因此可以取消这一操作,改用Ior循环通过m来限制好放空间的结点个数.请试着依据这一思路改写那一小段算法.答：改写-小段算法如下.Forg:卜二(ptr=rtr;rtr=11r>Ncxt;fnx<p(r>7.弟写一个葬法,功能是复制一个鞋串.答：复制一个完整的鞋中，是一件比较简洁的事情.其算法起名为CoPy-1.1(),参数为1.tk详细编写如下.COPy_1.M1.d)p<r=UI_h;rtr-nalloc(size);rtr->Dala=p(r->Dala;U2_h=rtnp<r三p(f->NcM;while(r!=N1.1.1.>(qtr=mai!oc(sizc):qtr->Data=<r->Daa.rtr>el=q(r;ptr=p<r->Ncx(;IHrQNeXNU1.1.:rctum(1.l2h):4.将-棵有50个结点的完全二叉树按层编号,承么潟号为25的结点是A.无左、右孩子B.有左孩子，无右孩子C.有右孩子，无左孩子D.有左、有孩子A.63B.64C.127D.1286 .在一探非空二叉树的中序遍历序列里，根结点的右边，上结点，A只有左子树上的部分B,只有左子树上的全部C.只有右子椅上的部分D,只有右子树上的全部7 .在任何一棵二叉树的各种遍历序列中.叶结点的相对次序是AA.不发生变更B.发生变更C.不能确定D.以上都不对8.权值为1、2、6、8的四个结点，所构造的哈夫曼树的带权路径长度是旦.A.18B.28C.19D.29A.6B.7C.8D.910.在一棵二叉树中，第S层上的结点数最多是上个.A.8B.15C.16D.32三、问答1 .试问满二叉树与完全二叉树之间有何关系？答，由满二叉豺与完全二叉树的定义可知.满二叉树确定是一棵完全二叉树，但完全二叉树却不确定是一棵满二叉树.假如一棵：叉树不是完全：叉树,那么它确定不行能是棵满二叉树。这就是海：叉树与完全：叉树之间的关系，2 .请画出由3个结点构成的全部二叉树，它们的高度分别是多少？答：大小为3的不同的二叉树共有5种,如下图所示.其中，4棵树的高度为2,1棵树的高度为I.3 .一黑高度为3的满：叉树有多少个叶站点？有多少个度为2的结点？总共有多少个结点？孥有218个叶结点,有度为2的结点2口=7个，总共有2"U=K1=15个结点.4 .有人说，任何一探其空满：叉树，它的叶结点数等于其分支结点数加I-这样的一个结论正确吗？请说明理由.（提示：利用性质，3）答：在我初介绍的二叉树性质中,只有性麻S-3是涉及叶结点数与（度为2的）分支结点数的关系的.对于满二叉树来说,全部的分支结点都是度为2的结点.因此,正好可以干脆利用性质5-3褥出所须要的结论.所以，此人说的结论是完全正确的.5 .有人说，有一棵结点数为，a1的二叉树，只包含有一个叶站点.这可能吗？假如可能的话，这样一-棵二叉树应当是个什么样子呢？答：这是完全可能的,这种二叉树是从根结点起先只有左子树.或只有右子树的单支二叉树,如图所示.二叉构.答：这株二叉树如应用即3答案图所示.4 .若一棵二叉树的左、右子树均有3个结点，其左子树的先序遍历序列与中序避历序列相同，右子树的中序论历序列与后序溺历序列相同,请画出这株二叉树。答：这棵二又树如“用即4答案图所示.5 .理解算法5-10在图S25(b)的基础上,进行下一次组合。试给出第2次组合后数组的情彬,以及那时二叉树的样子.答：第2次组合后数组的情形如下图所示，那时二叉树的样子如下图(b)所示.6 .权值序列为：10、16、20,6、30、24,请用图示来表达构造一棵哈夫曼树的全过程。答：构造这棵哈夫变树的全过程如下所示.双亲的孩子链表表示法(我们介绍过双亲表示法和孩子融表表示法,没有介绍过带双亲的孩子链非表示法.里能够把两者结合起来)：(3)孩子/兄弟链衣衣示法.答：双亲去示法如下图依)所示:(2)带双亲的孩子链求去示法如图下(b)所示;(3)孩子/兄弟链表表示法如卜图(c)所示。loot-»|IIAlB÷jTcTlIlDl+TeF11ItIf4÷g|ha1Ihl÷11N3 .将图626所示的二叉树转换成相应的森林。答；转换成的森林如下图所示。4 .给出如图6-27所示树的先序遍历序列和后序通历序列，答：该树的先序泗历序列为：A-B-E-F-K-1.-M-C-G-D-H-I-J;该树的后序遍历序列是:E-K-M-1.-F-B-G-C-H-I-J-D-A.答：这两个舞法的处理思路的确较为相像.主要区分在于：Pnm算法是从V-U里选择山下一个与MST中某个顶点相距最近的顶点,而DijkStra算法是从V-U里选择山下一个离源点燃近的顶点，5 .对有,“个顶点的无向图G,如何通过它的邻接矩阵判定下列问甥；(1)图中有多少条边？(2)随意两个顶点iHlj之间是否有边相连？(3)随意一个顶点i的度是多少？答：(1)邻接矩阵中非零元泰个数的一半，是图中边的数目：(2)通过推断邻接矩阵中元索AwJl和AR是否不为0.可知顶点i和/之间是否有边相连：(3)第i行或第i列上非零元素的个数,就是顶点i的度.6 .对图724回答下列何SS：<3)<5)每个顶点X的度D(X);一个长度为4的回路:(1)顶点集合V；(2)边集合E：(4)一个长度为5的路径：(6)答：(I)顶点集合V=v.-2.V3.EVsjyJ(2)(3)(4)(5)(6)(7)(8)边集合E=<V,»'2>,<V：,1>3>,<V2,l*>,<13,V>,<内，V5>,<V4,Vj>,<V),l>,<»'4,D(v2)=3,D(VJ)=D34)=4,D<)=D(V6)=2.Vl->V2->V->l->V4->V5“Vj->vj->V5->V4->Vj.等个顶点的度：D(l>=l,一个长度为5的路径是：一个长度为4的回路是:如下图所示。O3OO2J2一如卜图(b)所示,加下图(C)所示“l-Al"A*I5I*H6II-z*<SI-+«16IaITnI何答S的(6>-<8)答案答：(1)的二叉查找树如图（八）所示.平均查找长度是,AS1.a=(I+2*2+2*3V5=11/5=2.2(2)的二叉杳找树如图(b)所示，平均铳找长度是：AS1.h=(I+2+3+4+5)/5=15/5=32.利用折华杳找法对一个长度为IO的有序表进行杳找,请填写杳找表中每个元素时所须要的比较次数.元会下标I12345678910请埃笏M校次数：答：依据折半杳找算法，因此首先用给定值K与区间I1.10的中点比较,因此卜标为5的元素比较次数为1.若没仃找到.接著应当在区间1,4或610中接着折半查找因此下标为2和下标为8的元素的比较次数为2.接器下去,下标为I、3、6、9的元素的比较次数为3,出终，下标为4、7、IO的元素的比较次数为4。于是，所填结果为：元*T标I12345678910错填笏比倏次数113234134234四、应用1 .有关犍字序列:20、10、30.15.25.5.35、12、27.请一步步画出构造二叉雀找树的过程.答；构造：又管找树的过程如下：2 .给出如图8-21所示的一棵二又查找树.在其基础上分别做操作：(1捌除关雄字为15的记录：(2)插入关雄字为20的记录.画出这两个操作完成后该树的形态.答：1删除美键字为15的记录后,干脆前胆（或左子树根结点）取代所得,该树的形态如图（八）或（b）所示，（八）是用特删结点的而（b）则是用待捌结点的干脆后第（或右子树根结点）取代所得：（2）插入关键字为20的记录后该树的形态如图（C）所示.3 .设敌列函数为h（key）=key%ll,敌列表长为11（索引地址为010）,给定：SUN.MON,TUE.WED,THU.FRI.SAT取单句第I个字母在英讲字母衣中的序号为关犍字值（比如S的关键字值为19，采纳雒地址法解决散列地址冲突.请画出对应的散列龙.答：对应的散列表如下.4 .有关键字序列：36、27、68、33、97.40,81、24、23、90.32、1%放列表长为13.采纳的数列函数为：h（key>=kcy%13.运用开放地址法的线性探测解抉冲突,请完成下面散列表的填写比如.第I个插入的是36,它的散列地址为10.由于没有发生冲突，所以比较次就存放在了地址为IO的位置），求出其平均查找长度AS1.,地址美依字比核.次效012712103611112答：最终的散列衣如图所示.其平均IS我长度AS1.为：AS1.-性探测=(2+l+2+l+2+5+l+!+3+l+l+3>/12=1.92数到地址关依字比较次圾09021271240236814812514569717331g22391036111241122335 .已知由12个关键字祖成的序列:Jan-Feb.Mar.Apr.May.Jun.Jul>AugSep.Oct.Nov.Dec(1)依据所给依次构造一棵初始为空的二叉查找树.画出最终形成的二叉查找树,求在等概率下查找胜利的平均查找长度.(2>若对关键字序列依据字母递埴的依次排列成有序表，求在等概率下这黑二叉食找树查找胜利的平均杳找长度。答：(1)最终形成的二叉查找树如下图所示,其平均查找长度为：AS1.=<l+2*2+3*3+34+2*5+6)/12=42/12=3.5(Jai)De，Oct(2)这时成为只有右子国的总支树,其平均查找长度为：AS1.=<I+2+3+4+5*6+7+8-+1(H11+12)2=782=6.56 .已知由12个关键字祖成的序列：Jan,Feb,Mar.Apr.May.Jun.Jul>Aug.Sep.Oct.Nov.Dec散列表长为13(地址为(kl2),散列函数为：h(kcy)=iZ2,其中i为关健字中第1个字母在字母表里的序号.(I)用线性探测法解决冲突，给出所构造的敌列衣以及直找胜利的平均位找长度。(2)用链地址法斛决冲突，给出所构迨的散列表以及杳找胜利的平均查找长度。答：(1)用线性探测法解决冲突时,插入地址及比较次数如下：h(Jan)=10.2=5.比较1次插入：h(f%b)=6=3.比较I次插入：.构造的股列表如图所示。MMarK2=6,比较I次插入;h(Apr)=l2=3,比较I次插入:h(MayE32=6,比较2次插入:h(Jun)=lW2=5,比较4次插入；h(Jul尸Iw2=5,比较5次插入：h(Aug>=l2=0,比较2次插入：h(Scp)三192=9,比较2次插入:h(Oct-7,比较5次插入:UNov)=l4,',2=7.比较6次插入：h<DecRf2=2,比较I次插入，所以，构造的散列表如图所示。O234567g9】OuI213141516AUglDeClFeblIJanlMarJUnIJUlISepI。CtlNVFIAPlAUglDeClFeblIJanlMarlMaylJUnlJullSePlOetlNOVl|平均也我长度为：AS1.=(I+1+1+1+2+4+5+2+2+5+6÷1)12=3112-2.6(2)用链地址法解决冲突时,构造的散列表如图所示.平均查找长度为：AS1.=<1+2+1+1+1+2+3+1+2+1+2+1)/12=18/12=1.5第9章习题解答一、填空1 .一次箍选的目的，就是将不满童堆性质的完全二叉树丛结点，调整到其适当的位用上，以使构成一个新堆。2 .若经过某种排序之后,那些有相同关键字值的记录间的相对位置保持不变.那么称这种排序方法是稳定的.3 .有恃排关键字序列；54、38、96、23、18、73、61、46、88.采纳干脆插入排序算法.在进行到找寻第7个关犍字61的插入位置时须要做工_次比较.（留意：在进行到找寻第7个关键字61的插入位置时，曲面的6个关键字已羟挂好了序：18、23、38、54,73、96,由于比较是从后往前iS行的，所以在与96、73、54比较后，就能终确定60的插入位置了）4 .国IJ非序方法是从未排序的序列中选择出元素,然后将其依次放入排好序的序列的一端.5 .快速排序方法是通过适:，的位置.交换,把序列中的元素次性地放到了它的最终位置上。6 .有待排序的关犍字序列：54.38.96,23,15,72、60.45,83.对这样的一个特定的序列进行甘泡排序.整个排序过程箭进行工楞扫描.才能完成排序任务.（留意：第4甜已经排好，第5楞时由于推断没有交换而结束排序7 .对关键字序列22、86、19、49、12、30、65,35、18做一趟排序后，得到的结果是18.12.19,22,49、30.65.35.86.因此,可以认为采纳的排序方法是快速排序.8 .个堆中全部非叶结点的关犍字伯都小于或等于其左、右孩子的关键字值.二、选押1 .在下面给出的各种排序算法中,只有是稳定排序算法.A.囱泡排序B.快速排序C.干脆选择排序D.堆排序2 .在下面给出的各种排序算法中，只彳不是稳定揖序算法，A.日泡排序B快速排序C.干脆插入排序D.折半插入排序3 .在给出的四棵二叉树中,只有C满意一个堆的条件.4 .已知无序的待排关援字序列为：46、79、56.38、40,84.利用堆排序方法创建的初始堆应当是_5,A.38,56.40.79.46.84B.38,40.56.79.46.84C.38.«）,46.56.79.84D.38.46.40.56.79.845 .对关次字序列：46,79、56、38、40、84采纳快速排序方法.若以46为枢轴，那么一次划分后的结果应当是上。A.38.40.46.79.56.84B.38,40.46.84.56.79C.40,38.46.79.84.56D,40.38,46.56.79.846 .从待排序序列中依次取出元素与已排好序的序列里的元索进行比较.并存放到已排序序列的正确位置上，这种排序方法是4A.干脆插入排序B.交换排序C.日泡排序D.选择排序7 .当两个元素出现逆序时就交换它们的位置.这种排序方法是A.干脆插入排序B.H泡排序C.交换排序D.选择排序8 .典力24个记录的待拧序列,采纳冒泡排序时,最少须要进行的比较次数足_B_-A.IB.23C.24D.5129 .用某种排序方法对序列:24、84、21,47、16、28、66.35、20进行持序，序列的变更状况为：20.16.21.24.47.28.66.35.«416.20.21,24,35,28.47,66.8416,20,21.24,28.35,47,66.84那么，这里采纳的排序方法是D.选择排序A.干脆插入排序B."泡持序C.快速排序三、问答1 .在干脆插入排序算法中，什么条件保证了该算法的柩定性？答：在该獴法中.可能停止while循环的一个条件是lcmpkcy>=ArU.kcy正是它保证了干16插入排序算法的稔定性.比如在例9-2里，由于比较到第2个76大于、等于第I个K，所以WhiIe循环就结束了，不再往后移动比较范附内的记录。因此，第2个76确定在第I个筌的后面，不会跑到它的前面去F假如将while循环改为：while(tcmp.kcy>=Aryj.kcy)&&(j>=l)那么，它就不会保证干脆插入排序舞法是桧定的了.2 .在肾泡抖.序和法里，是什么条件保证它的枪定性？答：臼泡排序是种稳定排序尊.法，主要是因为算法里母鹤扫描时的判定条件设定为：ArUIkCy>ArU+1Jkcy,它保证原先在前面的记录.排序后仍旧排在前面.不会变史它们之间的相对依次.假如把大于号改为大于等于，那么算法就不是稳定的3 .试问内排序与外排序有什么区分？答：内、外序虽然都是排序，但由于排序过程中所运用存储器的不同，而被分为内排序和外排序.所消“内排序”,是指待排记录序列全部存放在内存,整个排序过程福在内存里完成：所谓“外排序”,是指内存中容纳不下全部待排记录序列,排序过程中须要不断地与外存进行数据交换，4 .有两个关键字序列：3、10、12、22、36、18.28、40和5、8、II、15、23、20、32、7.试问谁是堆,谁不足推？把不足堆的序列通过筛选将它谓整为一个堆.答：依照序列的依次，画出对应的完全二叉例如（八）和(b)所示.可以看出，（八）是一个堆，(b)则不是，因为结点7破坏了堆的性质，为此，先将7和15对换，如图(C)所示：然后再将23,21.28.15.19.3.73.7.15.19.21.23.2819.23.3,15,7.21.2819.7.15.28,23.21.3对它们果纳快速排序方法进行排序,试问哪一种状况速度最慢？答：在爆终一种状况时，序列己经排好序，因此对它的排序速度嫉慢,四、应用I.将冒泡排序算法修改成记录关键字由大到小递减排列.答；己却有”个记录的无序序列，存放在一个一维数殂Ar里，对它进行递减的旨泡排序，井呆终得到排序结果.算法名为BUkSort10,参数为Ar,小Bub_S<>rt1(Ar.n)f<<(i=:i;i÷*>对无存记录序列进行n-l超打描*1flag=0;for(j=hj<=>i:j*÷)if(A1j.key<A*l).ke)/这趟发生交换湿记/送培也将的JiiH是从I到n-i*/通过IemP进行交换/(c11=Ar(j÷l;Artjl=Ar(j>l;Affj-*11=temp:Ilag=I;if(Hag=0)break:/»若没有发生.交族就结束打法”J2.有待排关雄字序列：68、70、67,73、23、67、28、92、18，以图示的方式对它进行快速排序，并说明快速排序是种不枪定的排序算法.答：图(U)是快速排序一次划分前的初始状态，图(b)是一次划分完成时的结果，这时关A4A5A1AR；IiIlowI67I6?67I23|(力Iow=Hight彳2A3A4A5三67I67Ia(e)-l丘_jh67I'(0,三hI28IaI67I¢21(g).一O2328I67I及(NIOW=high下面特地来看左边的待排子序列，它由AIJ=I8.A(2)28>A(3=fi2>4J=67.A5=23组成，对其进行快速排序一次划分前的初始状态如图所示，一次划分完成时的结果，关过:18已经到达它的股终位置，其他关键字只有右子序列,如图(d)所示.图(C下图（三）和小对右字序列一次划分的过程.从最终结果可以看出，原来在左边的61现在被支也到了右边，如图（三）所示，这表明快速排序不具有检定性，3 .把干脆选择排序算法修改成各关键字最终由大到小排列，Sc1.SOa(Ar.n)(<x(i=ji<=n-hi÷+)(large-i;fur(j=i+l;jv=n：j+)if<rj.key>1large.key>Iarjjc=j;if(Iaigc!=i)I«emp=ri;rfi=Arlarc;答：修改的算法如下所示./T限制nl衲门描/*用-IiUal趾记住当IW最大关彼字的位置*/Qj限制这越扫揄的比校范用*/祖如发觉更大若，的时修改IarjtC的帆”larI批较莅IH酋兀东卜林不问.姬交换”/*交换是利用临时变fittemp进行的!Aiilargcl=«mp:4 .已知待排的关雄字序列：70、83、99、65、10、32、7.9.请给出果纳干腌插入排序方法时好皑的图示过程，答：采纳干脆插入持序方法时俗措的图示过程如K.初始技奇：PO第1次扫描IPO第2次扫描：PO83I到8399991»6565103279第3次扫捕：BT7083叨10第4次扫描“布-6570839932第5次扫描：10657083997第6次加描：式一1032657083999I料火扫描(7J9103265708399J,行待排序的关键字序列：18、02、22、15、56、18、88、27、68.说给出采纳国泡排序方法时越越的图示过程(留.京：这里有两个关键字都是18>.答：采纳印泡推序方法时每建的图示过程如下.1202221556188827630218152218562768880215IS1822275668880215182227566888初姑伏态1第1於柏格;笫2蜷柏搐:第3必启楼:AlA2AA4A5A6A7A同A9