数据结构习题课7

数据结构习题第7章2021/5/91第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-502021/5/927-2若对序列（7，3，1，8，6，2，4，5）按从小到大排序，请写出冒泡排序的第一趟结果。2021/5/93参考答案

3，1，7，6，2，4，5，82021/5/947-3设文件（R1，R2，…，Rn）以单链表方式表示，指针变量FIRST指向表头结点，且表中的结点结构为：其中KEY为该结点的关键词域，LINK为链接域。请给出这种线性表的直接插入排序算法，并要求算法的时间复杂度为O(n2)，且算法是稳定的。KEYLINK2021/5/95算法InsertSort(FIRST.FIRST)/*对单链表直接插入排序,FIRST指向表头结点*/IS1[边界]IF(LINK(FIRST)=NULLORLINK(LINK(FIRST))=NULL)THENRETRUN.IS2[插入排序]q←LINK(FIRST).q0←LINK(q).WHILE(q<>NULL)(p←LINK(FIRST).p0←FIRST.WHILE(KEY(p)<=KEY(q)ANDLINK(p)<>q)DO(p0←p.p←LINK(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).).)▌2021/5/967-5设计一算法，在尽可能少的时间内重排数组，使所有取负值的关键词放在所有取非负值的关键词之前，并分析算法的时间复杂度。2021/5/97基本思想：以0为基准记录，使用快速排序的一次分划过程即可，时间复杂度为O(n).2021/5/98算法Part(A,n.A)/*以0为基准元素一次分划*/P1[初始化]i←1.j←n.P2[以0分划]WHILEi<jDO(

WHILEKi<0AND

i<jDOi←i+1.WHILEKj>0ANDi<jDOj←j–1.IFi＜jTHENRiRj

．)

▌

2021/5/997-8讨论冒泡排序算法的稳定性。2021/5/910参考答案冒泡排序中，每一趟冒泡，相邻的关键词只有满足(Rj>Rj+1)时才会发生交换，关键词相同的记录不会发生交换，即相同位置不变，因此是冒泡排序算法是稳定的。2021/5/9117-10类似于冒泡过程（从下到上），与之对应的是下沉过程（从上到下）。如果排序是冒泡和下沉的交替过程，证明如果经过一趟冒泡和一次下沉后发现Rj和Rj+1（1jn1）没有交换，则它们已经进入最终排序位置。2021/5/912参考答案证明：如果经过一趟冒泡和一次下沉后发现Rj和Rj+1（1jn1）没有交换，那么有R1<=R2<=R3<=…<=Rn

即所有记录已经进入最终排序位置。2021/5/9137-18奇偶交换排序算法的基本思想描述如下：排序过程通过对文件x[i](l≤i≤n)的若干次扫描来完成，第奇数次扫描，对所有下标为奇数的记录x[i]与其后面的记录x[i+1](l≤i≤n–1)相比较，若x[i].KEY＞x[i+1].KEY，则交换x[i]和x[i+1]的内容；第偶数次扫描，对所有下标为偶数的记录x[i]与其后面的记录x[i+1](2≤i≤n–1)相比较，若x[i].KEY＞x[i+1].KEY，则交换x[i]和x[i+1]之内容，重复上述过程直到排序完成为止.2021/5/914(1)排序的终止条件是什么？(2)完成该算法的具体设计.(3)分析该算法的平均运行时间.2021/5/915算法Sort(X,n)S1[一趟扫描过程中，均没有记录交换则算法终止]change←1.while(change)(change←0.fori←1ton-1step2//奇交换if(X[i].key>X[i+1].key)(X[i]X[i+1].change←1.)fori←2ton-1step2//偶交换if(X[i].key>X[i+1].key)(X[i]X[i+1].change←1.)))▌2021/5/916(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反序对的平均数)2021/5/917正确性证明：数学归纳法对元素个数n进行归纳当n=1是，算法正确假设当n<=k时，算法能对n个元素的数组进行排序，则当n=k+1时，进行一趟分划后,轴心元素R[s]进入了最终排序应在的位置R[i]，即R[i]之前的元素R[s]~R[i-1]都小于等于R[i]，R[i]之后的元素R[i+1]~R[e]都大于等于R[i]。由于R[s]~R[i-1],R[i+1]~R[e]任意一部分最多为k个，按照假设，都能正确排序。因此，该算法能对全部k+1个元素正确排序。2021/5/9187-24填充如下排序算法中的方框，并证明该算法的正确性.(实质是一趟快速排序算法)算法PartA(R,s,e)//分划文件(Rs,Rs+1,…,Re),且Ks-1=-∞,Ke+1=+∞PA1[初始化]i←s.j←

①.K←Ks.R←Rs.e+12021/5/919PA2[分划过程]whilei<jdo(j←j-1.while②

doj←j-1.if(i≥j)thenj←i.else(Ri←Rj.i=i+1.whileKi<Kdoi←i+1.if③

thenRj←Ri.)).PA3④▌Kj≥Ki<jRj←R2021/5/9207-26分析算法HSort中的堆栈S可能包含的最大元素个数（表示成M和n的函数）。2021/5/921参考答案当n/2>=M，才会在辅助堆栈中压入第1个元素当n/(22)>=M，才会在辅助堆栈中压入第2个元素……，依此类推，当n/(2k)>=M，才会在辅助堆栈中压入第k个元素则2k<=n/M.k<=log2(n/M)因此最多为floor(log2(n/M))个2021/5/9227-30证明：用淘汰赛找n个元素的最大元素正好需要n–1次元素比较。2021/5/923参考答案证明：在淘汰赛中，每进行一场比赛，即进行依次比较，都恰淘汰1个元素，找到最大元素需要淘汰n-1个元素，因此需要n-1比较。2021/5/9247-31证明：用淘汰赛找n个元素的最大元素所形成的树高为log2n.2021/5/925参考答案证明：当n=2K时，第1轮后剩下n/2=2K-1，第二轮后剩下n/4=2K-2,依次类推,第k轮淘汰赛后就剩下1个选手，就是最大元素。每一轮淘汰赛都对应比赛树中的一层，因此当n=2K时，比赛树的最大层数是k，比赛树的高度是log2n当n为任意数时，总可以找到一个k，使得2K-1<n<=2k，只需要k轮淘汰赛就可以最大元素，对应的比赛树高为k。由2K-1<n<=2k，得log2n<=k<log2n+1，即形成的树高为log2n.

2021/5/9267-35设文件(R1，R2，…，Rn)是一个堆，Rn+1是任意一个结点。请设计一个算法，该算法把Rn+1添加到堆(R1，R2，…，Rn)中，并使(R1，R2，…，Rn，Rn+1)成为一个堆（要求算法的时间复杂度为O(log2n)）.分析：堆有大根堆和小根堆。教材上用的是大根堆。2021/5/927参考答案算法Insert(R,n,x.R,n)/*在堆中插入元素x，从下往上调整堆*/U1[x放入R[n+1]]n←n+1.R[n]←x.U2[从下往上调整，称上浮]i←n.WHILE(i>1ANDR[i/2]<R[i])DOi←i/2.▌2021/5/928C++inth[MAXN];intn=0;voidinsert(x){ h[++n]=x;for(intj=n;j>1;j>>=1)//上浮if(a[j]>a[j>>1])swap(a[j],a[j>>1]);}2021/5/9297-36文件(R1，R2，…，Rn)是一个堆，1≤i≤n，请给出一个算法，该算法从(R1，R2，…，Rn)中删除Ri，并使删除后的文件仍然是堆，要求算法的时间复杂度为O(log2n).2021/5/930参考答案算法Delete(R,n,i.R,n)/*在堆中删除元素R[i]，从上往下调整堆*/D1[R[i]与R[n]交换]R[i]←R[n].n←n-1.D2[从上往下调整，称下沉]j←i.WHILE(2*j<=nANDR[2*j]>R[j]OR2*j+1<=nANDR[2*j+1]>R[j])DO(y←2*j.IF(2*j+1<=nANDR[2*j+1]>R[2*j])THENy←y+1.R[j]↔R[y].j←y.)▌2021/5/931C++inth[MAXN];intn=0;voiddelete(inti){ h[i]=h[n--];while(2*i<=n&&h[2*i]>h[i]||2*i+1<=n&&h[2*i+1]>h[i]) inty=2*i;if(y+1<=n&&h[y+1]>h[y])y++;swap(h[i],h[y]);i=y;}}2021/5/9327-49填充如下排序算法中的方框，并讨论该算法的稳定性.算法C(R，n)/*比较计数，本算法按关键词K1，K2，…，Kn排序记录R1，R2，…，Rn.一维数组COUNT[1:n]用来记录各个记录的排序位置*/

2021/5/933［C1］FORi=1TOnDO①.

［C2］FORi=nTO2②DO

FORj=i–1TO1STEP–1DO

IF③