数据结构习题课7

1、数据结构习题第7章,吉林大学计算机科学与技术学院谷方明,第7章作业,247页：每组的第1题是必交的，即7-2、7-5、7-18、7-24、7-497-2、7-3、7-5、7-8、7-10、7-18、7-24、7-26、7-30、7-31、7-35、7-367-49、7-50,7-2,若对序列（7，3，1，8，6，2，4，5）按从小到大排序，请写出冒泡排序的第一趟结果。,参考答案3，1，7，6，2，4，5，8,7-3,设文件（R1，R2，Rn）以单链表方式表示，指针变量FIRST指向表头结点，且表中的结点结构为：其中KEY为该结点的关键词域，LINK为链接域。请给出这种线性表的直接插入排序算法，

2、并要求算法的时间复杂度为O(n2)，且算法是稳定的。,算法InsertSort(FIRST.FIRST)/*对单链表直接插入排序,FIRST指向表头结点*/IS1边界IF(LINK(FIRST)=NULLORLINK(LINK(FIRST)=NULL)THENRETRUN.IS2插入排序qLINK(FIRST).q0LINK(q).WHILE(qNULL)(pLINK(FIRST).p0FIRST.WHILE(KEY(p)q)DO(p0p.pLINK(p).).IF(KEY(p)KEY(q)THEN(LINK(q0)LINK(q).LINK(p0)q.LINK(q)p.qLINK(q0).).

3、ESLE(q0q.qLINK(q0).).),7-5,设计一算法，在尽可能少的时间内重排数组，使所有取负值的关键词放在所有取非负值的关键词之前，并分析算法的时间复杂度。,基本思想：以0为基准记录，使用快速排序的一次分划过程即可，时间复杂度为O(n).,算法Part(A,n.A)/*以0为基准元素一次分划*/P1初始化i1.jn.P2以0分划WHILEi0ANDiRj+1)时才会发生交换，关键词相同的记录不会发生交换，即相同位置不变，因此是冒泡排序算法是稳定的。,7-10,类似于冒泡过程（从下到上），与之对应的是下沉过程（从上到下）。如果排序是冒泡和下沉的交替过程，证明如果经过一趟冒泡和一次下沉

4、后发现Rj和Rj+1（1jn1）没有交换，则它们已经进入最终排序位置。,参考答案,证明：如果经过一趟冒泡和一次下沉后发现Rj和Rj+1（1jn1）没有交换，那么有R1=R2=R3Xi+1.key)(XiXi+1.change1.),(1)最好情况下，比较一趟每趟中奇交换偶交换比较次数共(n-1)次，无记录交换/正序(2)最坏情况下比较(n/2)+1趟，总比较次数为(n-1)*(n/2+1）次每次比较都交换，总交换次数为(n-1)*n/2或(n-1)*3n/2/逆序(3)最好时间O(n)最坏时间O(n2)平均时间O(n2)(书上P201反序对的平均数),正确性证明：数学归纳法,对元素个数n进行归

5、纳当n=1是，算法正确假设当n=k时，算法能对n个元素的数组进行排序，则当n=k+1时，进行一趟分划后,轴心元素Rs进入了最终排序应在的位置Ri，即Ri之前的元素RsRi-1都小于等于Ri，Ri之后的元素Ri+1Re都大于等于Ri。由于RsRi-1,Ri+1Re任意一部分最多为k个，按照假设，都能正确排序。因此，该算法能对全部k+1个元素正确排序。,7-24,填充如下排序算法中的方框，并证明该算法的正确性.(实质是一趟快速排序算法)算法PartA(R,s,e)/分划文件(Rs,Rs+1,Re),且Ks-1=-,Ke+1=+PA1初始化is.j.KKs.RRs.,e+1,PA2分划过程while

6、ijdo(jj-1.whiledojj-1.if(ij)thenji.else(RiRj.i=i+1.whileKi=M，才会在辅助堆栈中压入第2个元素，依此类推，当n/(2k)=M，才会在辅助堆栈中压入第k个元素则2k=n/M.k=log2(n/M)因此最多为floor(log2(n/M)个,7-30,证明：用淘汰赛找n个元素的最大元素正好需要n1次元素比较。,参考答案,证明：在淘汰赛中，每进行一场比赛，即进行依次比较，都恰淘汰1个元素，找到最大元素需要淘汰n-1个元素，因此需要n-1比较。,7-31,证明：用淘汰赛找n个元素的最大元素所形成的树高为log2n.,参考答案,证明：当n=2K时

7、，第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=1)/上浮if(ajaj1)swap(aj,aj1);,7-36,文件(R1，R2，Rn)是一个堆，1in，请给出一个算法，该算法从(R1，R2，Rn)中删除Ri，并使删除后的文件仍然是堆，要求算法的时间复杂度为O(log2n).,参考答案,算

8、法Delete(R,n,i.R,n)/*在堆中删除元素Ri，从上往下调整堆*/D1Ri与Rn交换RiRn.nn-1.D2从上往下调整，称下沉ji.WHILE(2*jRjOR2*j+1Rj)DO(y2*j.IF(2*j+1R2*j)THENyy+1.RjRy.jy.),C+,inthMAXN;intn=0;voiddelete(inti)hi=hn-;while(2*ihi|2*i+1hi)inty=2*i;if(y+1hy)y+;swap(hi,hy);i=y;,7-49,填充如下排序算法中的方框，并讨论该算法的稳定性.算法C(R，n)/*比较计数，本算法按关键词K1，K2，Kn排序记录R1，

9、R2，Rn.一维数组COUNT1:n用来记录各个记录的排序位置*/,C1FORi=1TOnDO.C2FORi=nTO2DOFORj=i1TO1STEP1DOIFTHENCOUNTjCOUNTj+1ELSE,STEP1,KjKi,counticounti+1,counti1,稳定性讨论,该算法是稳定的,7-50,有一种简单的排序算法，叫做计数排序(CountSorting).这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键词互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键词比该记录的关键词小，假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c.(1)给出适用于计数排序的数据表定义。(2)对于有n个记录的表，关键词比较次数是多少？(3)与简单选择排序相比较，这种方法是否更好？为什么？,参考答案,(