数据结构习题课ppt.pptx

数据结构习题课第第7 7章作业章作业l l247页:每组得第1题就是必交得,即7-2、7-5、7-18、7-24、7-49l l7-2、7-3、l l7-5、7-8、7-10、l l7-18、l l7-24、7-26、7-30、7-31、7-35、7-36l l7-49、7-507-27-2l若对序列若对序列(7,3,1,8,6,2,4,5)按从小到大排序按从小到大排序,请写出冒泡排序得第一趟结果。请写出冒泡排序得第一趟结果。l参考答案 3,1,7,6,2,4,5,87-37-3l设文件(R1,R2,Rn)以单链表方式表示,指针变量FIRST指向表头结点,且表中得结点结构为:l其中KEY为该结点得关键词域,LINK为链接域。请给出这种线性表得直接插入排序算法,并要求算法得时间复杂度为O(n2),且算法就是稳定得。KEYLINKl算法InsertSort(FIRST、FIRST)/*对单链表直接插入排序,FIRST指向表头结点*/IS1边界 IF(LINK(FIRST)=NULL OR LINK(LINK(FIRST)=NULL)THEN RETRUN、IS2插入排序 q LINK(FIRST)、q0 LINK(q)、WHILE(qNULL)(p LINK(FIRST)、p0 FIRST、WHILE(KEY(p)=KEY(q)AND LINK(p)q)DO (p0p、pLINK(p)、)、IF(KEY(p)KEY(q)THEN(LINK(q0)LINK(q)、LINK(p0)q、LINK(q)p、q LINK(q0)、)、ESLE(q0 q、q LINK(q0)、)、)7-57-5l设计一算法设计一算法,在尽可能少得时间内重排数组在尽可能少得时间内重排数组,使所有取负值得关键词放在所有取非负值使所有取负值得关键词放在所有取非负值得关键词之前得关键词之前,并分析算法得时间复杂度。并分析算法得时间复杂度。l基本思想:以0为基准记录,使用快速排序得一次分划过程即可,时间复杂度为O(n)、算法Part(A,n、A)/*以0为基准元素一次分划*/P1 初始化 i1、jn、P2以0分划 WHILE ij DO (WHILE Ki0 AND i0 AND iRj+1)时才会发生交换,关键词相同得记录不会发生交换,即相同位置不变,因此就是冒泡排序算法就是稳定得。大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流可以互相讨论下，但要小声点可以互相讨论下，但要小声点可以互相讨论下，但要小声点可以互相讨论下，但要小声点7-107-10l类似于冒泡过程(从下到上),与之对应得就是下沉过程(从上到下)。如果排序就是冒泡与下沉得交替过程,证明如果经过一趟冒泡与一次下沉后发现Rj与Rj+1(1jn1)没有交换,则它们已经进入最终排序位置。参考答案参考答案l证明:l如果经过一趟冒泡与一次下沉后发现Rj与Rj+1(1jn1)没有交换,那么有 R1=R2=R3=Xi+1、key)(Xi Xi+1、change 1、)for i 2 to n-1 step 2 /偶交换偶交换 if(Xi、keyXi+1、key)(Xi Xi+1、change 1、)l(1)最好情况下最好情况下,比较一趟、每趟中奇交换偶交换比较一趟、每趟中奇交换偶交换比较次数共比较次数共(n-1)次次,无记录交换、无记录交换、/正序正序l(2)最坏情况下比较最坏情况下比较 (n/2)+1趟趟,总比较次数为总比较次数为(n-1)*(n/2+1)次、每次比较都交换次、每次比较都交换,总交换次数为总交换次数为(n-1)*n/2 或或 (n-1)*3n/2、/逆逆序序l(3)最好时间最好时间O(n)最坏时间最坏时间O(n2)平均时间平均时间O(n2)(书上书上P201反序对得平均数反序对得平均数)正确性证明正确性证明:数学归纳法数学归纳法l对元素个数n进行归纳l当n=1就是,算法正确l假设当n=k时,算法能对n个元素得数组进行排序,则当n=k+1时,进行一趟分划后,轴心元素Rs进入了最终排序应在得位置Ri,即Ri之前得元素RsRi-1都小于等于Ri,Ri之后得元素Ri+1Re都大于等于Ri。由于RsRi-1,Ri+1Re任意一部分最多为k个,按照假设,都能正确排序。因此,该算法能对全部k+1个元素正确排序。7-247-24l填充如下排序算法中得方框填充如下排序算法中得方框,并证明该算法得并证明该算法得正确性正确性、(实质就是一趟快速排序算法实质就是一趟快速排序算法)l算法算法PartA(R,s,e)/分划文件分划文件(Rs,Rs+1,Re),且且Ks-1=-,Ke+1=+PA1初始化初始化 i s、j 、K Ks、R Rs、e+1lPA2分划过程分划过程 while ij do (jj-1、while do jj-1、if (ij)then ji、else (Ri Rj、i=i+1、while KiK do i i+1、if then Rj Ri、)、lPA3 KjKi=M,才会在辅助堆栈中压入第1个元素l当n/(22)=M,才会在辅助堆栈中压入第2个元素l,依此类推,l当n/(2k)=M,才会在辅助堆栈中压入第k个元素l则 2k=n/M、k=log2(n/M)l因此最多为 floor(log2(n/M)个7-307-30l证明:用淘汰赛找n个元素得最大元素正好需要n1次元素比较。参考答案参考答案l证明:在淘汰赛中,每进行一场比赛,即进行依次比较,都恰淘汰1个元素,找到最大元素需要淘汰n-1个元素,因此需要n-1比较。7-317-31l证明:用淘汰赛找 n个元素得最大元素所形成得树高为log2n、参考答案参考答案l证明:当n=2K时,第1轮后剩下n/2=2K-1,第二轮后剩下n/4=2K-2,依次类推,第k轮淘汰赛后就剩下1个选手,就就是最大元素。每一轮淘汰赛都对应比赛树中得一层,因此当n=2K时,比赛树得最大层数就是k,比赛树得高度就是log2n 当n为任意数时,总可以找到一个k,使得2K-1n=2k,只需要k轮淘汰赛就可以最大元素,对应得比赛树高为k。由2K-1n=2k,得log2n=k1 AND Ri/21;j=1)/上浮 if(aj aj1)swap(aj,aj1);7-367-36l文件(R1,R2,Rn)就是一个堆,1in,请给出一个算法,该算法从(R1,R2,Rn)中删除 Ri,并使删除后得文件仍然就是堆,要求算法得时间复杂度为O(log2n)、参考答案参考答案l算法Delete(R,n,i、R,n)/*在堆中删除元素Ri,从上往下调整堆*/D1 Ri与Rn交换 Ri Rn、n n-1、D2 从上往下调整,称下沉 ji、WHILE(2*jRj OR 2*j+1Rj)DO(y 2*j、IF(2*j+1R2*j)THEN y y+1、Rj Ry、j y、)C+C+int hMAXN;int n=0;void delete(int i)hi=hn-;while(2*i hi|2*i+1hi)int y=2*i;if(y+1hy)y+;swap(hi,hy);i=y;7-497-49l填充如下排序算法中得方框填充如下排序算法中得方框,并讨论该算法得并讨论该算法得稳定性稳定性、l算法算法C(R,n)/*比较计数比较计数,本算法按关键词本算法按关键词K1,K2,Kn排序记录排序记录R1,R2,Rn、一维数组一维数组COUNT1:n用来记录各用来记录各个记录得排序位置个记录得排序位置*/C1 FOR i=1 TO n DO 、C2 FOR i=n TO 2 DO FOR j=i1 TO 1 STEP 1 DO IF THEN COUNTj COUNTj+1 ELSE STEP 1STEP 1K Kj jKKi icounti counti+1counti counti+1counti 1counti 1稳定性讨论稳定性讨论该算法就是稳定得该算法就是稳定得