数据结构习题课7.pptVIP

算法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 (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).). ) ▌ 7-8 讨论冒泡排序算法的稳定性。 参考答案 冒泡排序中，每一趟冒泡，相邻的关键词只有满足(RjRj+1)时才会发生交换，关键词相同的记录不会发生交换，即相同位置不变，因此是冒泡排序算法是稳定的。 7-10 类似于冒泡过程（从下到上），与之对应的是下沉过程（从上到下）。如果排序是冒泡和下沉的交替过程，证明如果经过一趟冒泡和一次下沉后发现Rj和Rj+1（1?j?n?1）没有交换，则它们已经进入最终排序位置。 参考答案 证明： 如果经过一趟冒泡和一次下沉后发现Rj和Rj+1（1?j?n?1）没有交换，那么有 R1=R2=R3=…=Rn 即所有记录已经进入最终排序位置。 正确性证明：数学归纳法 对元素个数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个元素正确排序。 7-26 分析算法HSort中的堆栈S可能包含的最大元素个数（表示成M和n的函数）。 参考答案 当 n/2 =M，才会在辅助堆栈中压入第1个元素 当n/(22)=M，才会在辅助堆栈中压入第2个元素 ……，依此类推， 当n/(2k)=M，才会在辅助堆栈中压入第k个元素 则 2k = n/M. k=log2(n/M) 因此最多为 floor ( log2(n/M)) 个 7-30 证明：用淘汰赛找n个元素的最大元素正好需要n–1次元素比较。 参考答案 证明：在淘汰赛中，每进行一场比赛，即进行依次比较，都恰淘汰1个元素，找到最大元素需要淘汰n-1个元素，因此需要n-1比较。 7-31 证明：用淘汰赛找 n个元素的最大元素所形成的树高为?log2n? . 参考答案 证明： 当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=klog2n+1，即形成的树高为?log2n? . 7-35 设文件(R1，R2，…，Rn)是一个堆，Rn+1是任意一个结点。请设计一个算法，该算法把Rn+1添加到堆(R1，R2，…，Rn)中，并使(R1，R2，…，Rn，Rn+1)成为一个堆（要求算法的时间复杂度为O(log2n) ）. 分析：堆有大根堆和小根堆。教材上用的是大根堆。 参考答案 算法Insert (R,n,x.R,n) /*在堆中插入元素x，从下往上调整堆*/ U1 [x放入R[n+1]] n ← n+1. R[n] ←x. U2 [从下往上调整，称上浮] i←n. WHILE(i1 AND R[i/2]R[i]) DO i ← i/2. ▌ C++ int h[MAXN]; int n=0; void insert(x) { h[++n]=x; for(int j=n;j1;j=1)//上浮 if(a[j] a[j1