数据结构课件：17 【习题课】第7 - 8章

1、第7、8章习题17-2若对序列（7，3，1，8，6，2，4，5）按从小到大排序，请写出冒泡排序的第一趟结果。思想：通过比较相邻记录的关键词，交换存在逆序的记录；使关键词较大的记录如气泡一般逐渐往上“飘移”直至浮出“水面”。3 ，1， 7， 6，2，4，5 ， 827-5设计一算法，在尽可能少的时间内重排数组，使所有取负值的关键词放在所有取非负值的关键词之前，并分析算法的时间复杂度。基本思想：以0为基准记录，使用快速排序的一次分划过程即可，时间复杂度为O(n).3采用两端扫描的方法，左边遇到正数停止，右边遇到负数停止，交换两端记录，扫描一趟即完成排序。Void Resort(int R, int

2、 n) int i=1; j=n; temp; while(ij) while(Ri0) /正数则继续向左移动 j-; temp=Ri; Ri=Rj; Rj=temp; /交换记录 i+; /移动指针 j-; 每个元素都与0比较，n个元素则n次比较 时间复杂度为o（n)47-18奇偶交换排序算法的基本思想描述如下：排序过程通过对文件xi(lin)的若干次扫描来完成，第奇数次扫描，对所有下标为奇数的记录xi与其后面的记录xi+1(l i n1)相比较，若xi.KEYxi+1.KEY，则交换xi和xi+1的内容；第偶数次扫描，对所有下标为偶数的记录xi与其后面的记录xi+1(2in1)相比较，若x

3、i.KEYxi+1. KEY，则交换xi和xi+1之内容;重复上述过程直到排序完成为止. 57-18(l)排序的终止条件是什么？ 该算法类似于冒泡排序，终止条件是，一趟扫描中没有出现反序对。 实现时，可以用一个变量记录是否本次扫描是否交换记录，若存在交换，则继续下一趟扫描，否则，结束排序。(2)完成该算法的具体设计. (3)分析该算法的平均运行时间(最好/最坏). 6算法Sort(X, n)S1一趟扫描过程中，均没有记录交换则算法终止 change 1. while (change) ( change 0. /没有交换 for i=1 to n-2 step 2 /奇交换 if (Xi.key

4、Xi+1.key) ( Xi Xi+1. change 1.) for i=0 to n-2 step 2 /偶交换 if (Xi.keyXi+1.key) ( Xi Xi+1. change 1.) ) 77-18对所有奇数项扫描一趟，关键词比较次数n/2 ； 对所有偶数项扫描一趟，关键词比较次数(n-1)/2次；所以每趟排序总比较次数为(n-1)/2 + n/2 =n-1次最好情况下，序列中的记录按照关键词从小到大排列，执行一趟奇偶排序，结束。没有记录交换最坏情况下，记录按照关键词从大到小排列，执行(n+1)/2趟排序每次比较都交换记录，总比较及交换次数为(n-1)* (n+1)/2次结论

5、：最好时间O(n)；最坏时间O(n2)；平均时间O(n2)87-24填充如下排序算法中的方框，并证明该算法的正确性. (实质是一趟快速排序)算法PartA(R,s,e) /分划文件(Rs,Rs+1,Re),且Ks-1=-,Ke+1=+PA1初始化 i s. j . K Ks. R Rs.e+19PA2分划过程 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.).PA3 KjKiKicounti counti+111计数排序的基本思

6、想： 针对数组中每个记录x扫描待排序的数组一趟，统计数组中有多少记录的关键词比该记录的关键词小；之后，就可以确定x在最终输出序列的正确位置。例如，如果输入序列中只有5个元素的值小于x的值，则x可以直接存放在输出序列的第6个位置上。注意：这里数组中待排序记录的关键词互不相同。如果有多个记录具有相同的关键词，则这些记录得到的正确位置相同，无法完成排序。此时，上述算法需要作适当的修改。该算法是稳定的127-11 交替冒泡排序算法上浮：把最大的元素向后移，一趟冒泡，至少把关键词最大的记录送到最后位置上；下沉：把最小的元素向前移，一趟冒泡，至少把关键词最小的记录送到最前位置上；交替冒泡思想：相邻两趟排序

7、是向相反方向起泡的，把上浮和下沉过程交替进行。例如：序列7,9,2,16,8,5,12,13,14 上浮：7,2,9,8,5,12,13,14,16 下沉：2,7,5,9,8,12,13,14,1613Void bubble2(int a, int n) int change=1; low=0; high=n-1; i; t; while(lowhigh & change) change=0; for(i=low;iai+1) t=ai; ai=ai+1; ai+1=t; change=1; high-; for(i=high;ilow;i-) if(aiai-1) t=ai; ai=ai-1

8、; ai-1=t; change=1; low+; 148-8对长度为12的有序表（a1,a2,a12）(其中aiaj, 当ij时)进行折半查找，在设定查找不成功时，关键词xa12, aixai+1(i=1,2,11)等情况发生的概率相等，则查找不成功的平均查找长度是多少？思路：建立二叉判定树，再计算长度12个元素，开始i=(12+1)/2=6查找失败长度=（3+4+4+3+4+4+3+4+4+4+4+4+4）/(12+1)=49/13158-10已知关键词和它们对应的散列函数值。构造哈希表，用线性探测法解决冲突，计算平均查找长度ASL。(拉链法?)Key（zhao , sun, li, wa

9、ng, chen, liu, zhang）H(key) (6,5,7,4,1,6,4)线性探测法：以固定的次序检索表中的结点，直到找到一个关键词为K的结点或者找到一个空缺位置. 其循环探查路径： h(K)，h(K)+1，M-1，0，1，h(K)-1 16chenzhangliuwangsunzhaoli成功 （1+4+7+1+1+1+1）/7=16/7失败 717拉链法：假定表T包含M个散列地址T0，Tl，TM-l，拉链就是令散列地址等于i的记录组成一个链表，且指针Ti是该单链表的头指针.1234chenlisunwangzhangzhaoliu567查找成功 (1*5+2*2)/7=9/7查

10、找失败 （1+0+0+2+1+2+1）/7=18-13已知序列17, 31, 13, 11, 20, 35, 25, 8, 4, 11, 24, 40, 27 , 画出该序列的二叉查找树，并分别给出下列操作后的二叉树。1. 插入92. 删除173. 删除131819q无右儿子；若左孩子非空，则用q的左儿子代替q所指结点(删除13)。q有右儿子r，但r无左儿子，q的右儿子r，且r有左儿子，首先不断寻找r的左孩子，直到空；设左孩子为空的结点为s，则以s取代q，同时，将s的父结点以原s的右子树为左子树。 (删除结点17)8-22编写判定给定的二叉树是否是二叉查找树的算法。中根遍历二叉查找树，得到一个

11、从小到大排序的序列。思想：在中根遍历过程中，不断判断当前访问结点和其前驱结点之间是否有序，若遍历结束时，各节点和其前驱都有序，则为二叉查找树；否则，不是。2021算法InOrder(t)InOrder1 递归遍历 IF tNULL THEN (InOrder(left(t). PRINT(data(t). InOrder(right(t).) 算法bist(T,pre,flag. flag) /初始时pre=null，flag=true；bist1.树是否为空 IF T=null or flagtrue RETURN.22bist2.递归访问左子树 bist(llink(T),pre,flag

12、. flag) .bist3. 判断pre与T是否有序 IF pre=null THEN (flagtrue. pre T.) /访问中根序列第一个结点，不需要比较 ELSE（IF key(pre)key(T) THEN (flagtrue. pre T.) ELSE flagfalse. ) bist(rlink(T),pre,flag. flag) .8-23给定整型数组B0.m,0.n,已知B中数据在每一维方向上都按从小到大的次序排列,且变量x在B中存在。写算法找出满足BI,j的i和j值。算法find(B,x. i,j)find1.初始化 i0. j n.Find2.查找 while (

13、 Bi,j x) do /& i=0 ( IF Bi,jx THEN i i+1. ELSE j j-1. ).23练习设待排序的关键字序列为12,2,16,30,28,10,16,20,6,18，对下述排序算法，分别写出每趟排序的结果。1.直接插入排序2. 希尔排序（增量为5,2,1）3.直接选择排序4.堆排序5.二路合并排序24直接插入排序：将一个记录插入到已排好序的有序表中，从而得到一个新的记录数增一的有序表。希尔排序：把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。直接选择排序：对

14、待排序的文件进行n次选择操作，选择第 i （i = 1,2, , n-1）大的记录的具体办法：在剩余的n-i+1个记录中进行一趟比较，确定出第i大记录，放在第n-i+1位置上。 2526堆排序：建立最大堆；之后堆排序。将以序号n/2，n/21 , 1的结点为根的子树都调整为堆即可。重建堆：R1与Ri交换后，只有R1与其左右儿子不满足堆的性质。二路合并排序：设初始文件有 n 个记录，首先把它看成是 n 个长度为 1 的有序子序列 (合并项)，先做两两合并，得到 n / 2 个长度为 2 的合并项 (如果 n 为奇数，则最后一个有序子序列的长度为1)；再做两两合并，如此重复，最后得到一个长度为 n

15、 的有序序列。题1假设用链表表示集合，要求写一个函数Intersection，其功能是求两个用链表表示的集合的交集。集合链表p和q的交集求法： 从前向后扫描p的每个节点，如果该节点在q中，则该节点是交集的一个元素，将该节点插入链表r。bool inlist(int t, SLNode* p) /t是否在链表p中 SLNode*temp; for(temp=p-next ;temp!=0;temp=temp-next) if(temp-data=t) return true; return false; 27SLNode* Intersection(SLNode *p, SLNode *q) /

16、求交集SLNode* r=new SLNode();SLNode* t=r;SLNode* i;for(i=p-next ;i!=0;i=i-next) if( inlist(i-data, q) t-next=new SLNode(i-data); t=t-next; return r;28题2求一棵二叉树每层叶结点的数目。要求：编写函数LeafInEachLevel(root)，其中root为指向某二叉树根结点的指针。思想：用队列层次遍历，与传统层次遍历的不同在于：需要识别每层的结束，可以设置一个不同于队列中其他结点的特殊结点（比如空结点NULL）来表示每层的结束，遍历第一层时，先将根节点

17、入队，再将NULL入队。在遍历过程中，当NULL出队时，表示已经遍历完一层，输出该层的叶节点数目，并将NULL再入队，此时NULL即为下一层的结尾。29templatevoid BinTree: LeafInEachLevel (BinTreeNode *root ) if(root=NULL) cout空树endl; return; /* 按层次次序遍历以指针t所指结点为根的树，利用一个辅助队列*/ BinTreeNode *p; AQueueBinTreeNode * q ; int level=0 , cnt=0; q.QInsert ( root );/ 根结点入队 q.QInsert ( NULL );30while (! q.IsEmpty ( ) q.QDelete ( p ); / 出队一个结点 if(p=NU