数据结构习题课ppt课件.ppt

《数据结构习题课ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构习题课ppt课件.ppt（37页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构习题数据结构习题 第第 7 章章吉林大学计算机科学与技术学院谷方明第第7章作业章作业7-2l若对序列（若对序列（7，3，1，8，6，2，4，5）按从小）按从小到大排序，请写出冒泡排序的第一趟结果。到大排序，请写出冒泡排序的第一趟结果。l参考答案 3 ，1， 7， 6，2，4，5 ， 87-3l设文件（R1，R2，Rn）以单链表方式表示，指针变量FIRST指向表头结点，且表中的结点结构为：l其中KEY为该结点的关键词域，LINK为链接域。请给出这种线性表的直接插入排序算法，并要求算法的时间复杂度为O(n2)，且算法是稳定的。KEYLINKl算法InsertSort(FIRST. FIRS

2、T) /*对单链表直接插入排序, 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).).

3、 ESLE (q0 q. q LINK(q0).). ) 7-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)时才会发生交换，关键词相同的记录不会发生交

4、换，即相同位置不变，因此是冒泡排序算法是稳定的。7-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)最好情况

5、下，比较一趟每趟中奇交换偶交换最好情况下，比较一趟每趟中奇交换偶交换比较次数共比较次数共(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假设当

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

7、化 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-30l证明：用淘汰赛找n个元素的

8、最大元素正好需要n1次元素比较。 参考答案参考答案l证明：在淘汰赛中，每进行一场比赛，即进行依次比较，都恰淘汰1个元素，找到最大元素需要淘汰n-1个元素，因此需要n-1比较。7-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轮淘汰赛就可以最大元素，对

9、应的比赛树高为k。由2K-1n=2k ，得log2n=k1 AND Ri/21;j=1)/上浮 if(aj aj1) swap(aj, aj1); 7-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+1R

10、2*j ) THEN y y+1. Rj Ry. j y. ) 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-49l填充如下排序算法中的方框，并讨论该算法的填充如下排序算法中的方框，并讨论该算法的稳定性稳定性. l算法算法C(R，n)/*比较计数，本算法按关键词比较计数，本算法按关键词K1，K2，Kn排序记排序记录录R1，R2，Rn . 一维数组一维数组COUNT1 : n用来记用来记录各个记录的排序位置录各

11、个记录的排序位置*/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 稳定性讨论稳定性讨论该算法是稳定的该算法是稳定的7-50l有一种简单的排序算法，叫做计数排序(Count Sorting). 这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键词互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键词比该记录的关键词小，假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c .l (1) 给出适用于计数排序的数据表定义。l(2) 对于有n个记录的表，关键词比较次数是多少？l(3) 与简单选择排序相比较，这种方法是否更好？为什么？参考答案参考答案l(1) 数据表放在数组R中，元素个数为n ，下标从0开始（因为小于关键词的个数为c,就放在c的位置）。l(2) 对于每个记录，扫描待排序的表一趟，即比较n次。一共n个记录，共需比较n2次。l(3)与简单选择排序相比，比较次数增加，移动次数减少。整体上时间效率要低于简单选择排序，辅助空间要高于简单选择排序。