算法第四章拟考试题

1、算法分析第四章电信1306班试题知识点分布 时间复杂度分析证明：基于比较的排序算法平均时间复杂度=O(nlogn) 与=O(nlogn) 。归并排序的复杂度分析及优化措施时间复杂度3. 快速排序算法时间复杂度分析及优化措施二排序算法的具体应用4.n个数据元素，设计算法输出其中不相同的数据元素，并说明你的算法有多快？要求：输出时，不改变输入的顺序。（用到了归并排序知识点）5. 给出情况下，只需7次比较的5个元素排序算法。输入n个不同元素，输出其和为m的全部整数对。给出一个 C ( A B) (B A)的算法给出n个正整数数组，将偶数排在奇数前边，并说明算法的比较次数和移动次数。（类似快速排序中的

2、一趟比较）9 对一个数值在(1,100)之间的正整数数组进行排序，假设共有n个元素。三np问题10 用马步图判断回路1.证明：基于比较的排序算法平均时间复杂时间复杂度=O(nlogn) 。度=O(nlogn) 与比较排序可以被抽象的视为判定树。要使排序算 法正确地工作，其必要条件是，n个元素的n!种排列中的每一种都要作为判定树的一个叶子而出现。对于n个元素来说，判定树的叶子树为n!，其高度对应最深叶子的深度，而最深叶子的深度对应最坏时间，即若要证明就要证明判定树高度时间复杂度= O(nlogn)， nlogn)。=由二叉树的性质，深度为h的二叉树，最多有2h个叶子节点，因而叶子数为n!的判定树

3、高度= log(n!)。所以比较排序的大高度 log(n!)。时间W(n) 判定树的最即W(n)= log(n!)= log(n) + log(n1)+log(n2)+.+log2+log1=log(n)+log(n1)+log(n2)+.+log(n/2)=(n/2)log(n/2)=(n/2)log(n)n/2=O(nlogn)比较排序的平均时间A(n) 判定树的平均叶子深度。判定树的平均叶子深度：叶子数为n!,高度=log(n!)Logn!1高度，其叶子数至多为2logn!1=n!/2缩放： 将高度logn!的叶子节点（n!/2个）的高度都缩放为0剩余n!/2个叶子的高度均为log(n!

4、)2归并排序的复杂度分析及优化措施1.复杂度分析在次的情况下，n个元素合并，比较次数为n1因此W(n)=Wn/2+Wn/2+n1 其中W(1)=0W(n) = 2W(n/2)+n1= 2(2W(n/4)+n/21)+n1= 4W(n/4)+2n21 递归迭代K次其中k=logn W(n)=2k W(n/ 2k)+kn(1+2+3+ 2k1) W(n)=nW(1)+nlogn(n1)W(n)=nlogn(n1)因此归并排序的时间复杂度为O(nlogn)(n= 2k )归并排序的优化措施1.不回写2.不递归3.与相结合4.无逆序（对相对有序的序列来说，可以将有序的部分合为一个集合，减少比较次数）具

5、体改进的算法描述：A.将原数据集合分成若干组，分组策略如下：第一组：从第1个元素a1 开始到第20个元素a20 ，用插入排序排成有序集，从第21个元素起，按无逆序原则向后找到第一个出现逆序的元素ak 为止。那么第一组的元素为,a1 a20 ak .（杂度为O(n2/4)当n=16时，排序平均时间复优于归并）第二组：从ak开始按照找第一组的方法，找出第二组;第三组、第四组依次类推。按此方出与数据集分成若干组，在分组的过程中体现排序相结合和无逆序的改进。B.对划分的组进行如下处理：假定初始的元素存放在数组A中，申请同样大存储空间的数组B。奇数趟归并排序时（此时元素在数组A中），B。偶数趟归并排序时

6、（此时元素在数组B中），两两相邻的分组归并后存放到数组A。重复上述操作，直到最后归并到成一个集合为止。按此方法对组进行归并排序，体现了不回写和不递归的改进。3.快速排序算法时间复杂度分析及优化措施快速排序选取E时间复杂度为O(n2)作为轴元素pivot，在调用partition时让轴元素与其余各元素比较，以此确定轴元素的位置，在的情况下，每次选取的pivot都是最大或最小，所以关键字比较的次数为k=2.n(k1)=n(n1)/2 =O(n2)快速排序平均时间复杂度为O(nlogn)假定序列的每个元素被选为参考元素的可能性相等A(1)=A(0)=0n11A(n)n ( 1 (A)k A(n1k)

7、nk 0n11 2 nA(k )nk 0假设A(k)=klogknn21121A (n)n 1 kknlogklnknn ln 2k 1k 1n1nk ln k x ln xdx1k 112n ln(n) 114nx ln xdx 2n2412111 A(n) n 12n2(nln(n) 4nln2241(n2 ln(n) 11 n 1n2) 2nln2121nO(logn (1)n 21 2lnnlnnlogn )快速排序的改进方法 与法结合使用，当分割集a4,a3和a4对换；若a1a2,a1和a2对换；若a2a4,a2和a4对换 且a1和a3对换.生成序列为a1a2a4a3a42)将a5以

8、上序列（用折半查找，共需2次比较）结果可能为：3）.将a3可，用折半查找，最多需要2次比较由1、2、3得，此方法只需7次比较。6.输入n个元素，输出其和为m的全部整数对。首先进行排序，对排好序元素设置首尾两个指针low hih,当lowhigh时进行如下运算：如果Elow+Ehigh=m,则; low+;high,输出数对如果Elow+Ehighm, high当Low=high时，程序结束。7.给出一个的算法C ( A B) (B A)即把A与B中所有不相同的元素组成一个集合解.假设A中元素个数为n,B中元素个数为m.算法：输入两个序列A、B分别对A、B进行归并排序同时扫描A、B,设两个指针分

9、别指向A、B的当前扫描元素。初始时i、j分别指向A0、B0若AiBj 则将若Bi存入C中，j后移若Ai= Bj 则同时将i、j后移，直到分别出现与其前一个元素值不同的元素为止。d 重复c直至A、B同时扫描完或某一个扫描完，此时将另一个序列所有剩余元素直接C中即可。归并排序的时间复杂度O为(nlog2n lomg) m2扫描的时间复杂度为O(nm)总的时间复杂度为Olog2n (nlomg) m28.给出n个正整数内置分奇偶的算法，偶数排在奇数前边，并说明算法的比较次数和移动次数。（类似快速排序中的一趟比较）答算法描述第一个元素放入temp中， low指向第一个元素，high指向最后一个元素先从

10、右向左依次扫描判断high指向的元素的奇偶，Void partion (* a ,n)low=0,high=n1;temp=a0; While(lowE(low+)While(ahigh是奇数&high=0) high;然后再从右向左扫描判断low指向的元素的奇偶性若E(low)为偶数 low +If(high!=0)alow+=ahigh;While a low 是偶数&lowE(high)3 若lowE(low)中 程序结束。If(high!=0&low!=n1)Alow=temp;本算法在比较次数上：因为第一个元素没有参加比较，故为n1次在移动元素次数上，是来回移动的，情况下，n1个元素

11、都要相互移动，为n1次，还要将首位置元素移动到temp和从temp移入最终空位 2次，共需要n1+2次。9 对一个数值在(1,100)之间的数组进行排序，假设共有n个元素。试给出基数排序的空间消耗，桶数，总需要时间。给出在基数排序过程中找出n个元素（n10）前10个最大的算法。空间复杂度：桶的个数m(如m取100),此时只需一次装桶倒桶完成排序。n个元素需要n个空间存放，还需要n个链表(2n)空间，因此总共需要(3n+m)个空间.时间复杂度：在元素链表时，将元素链头，这样的时间为O(n)，然后将m个桶中的元素链接到一起所需要的时间为O(m) ，所以基数排序所需的时间为O(m+n) 。（2）算法：1 清桶2 把a0，a2，an1依次装桶，不考虑相同元素被选出的前后顺序。3从最大的桶开始，依桶的序号递减依次倒桶，直至够10个元素为止。马步图判断回路10n,m)/构建gijvoid GetGraph(for( i = 0;il;i+) for(j = 0;jl;j+)gij = 0;for(i= 0;il1;i+)ri = i/n; ci = i%n;for(j=i+1