杭电算法分析与设计复习提纲

《杭电算法分析与设计复习提纲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、杭电算法设计与分析复习提纲杭电算法设计与分析复习提纲1学弟学妹求送点财富1填空题5快速排序的随机化版本5计数排序6学弟学妹求送点财富这份答案是在2014年上半年总结，红色部分为考到的题目，老师没有对题目做无任何修改选择判断蒙一下就可以了40分。简答题5*8=40分5.2-3求骰子期望值略7.1-4应如何修改QUICKSORT，才能使其按非增序进行排序？在划分子树组时，将大于主元的元素放左边，小于主元的元素放右边7.2-2当数组A的所有元素都具有相同值时，QUICKSORT的运行时间是什么？7.2-4银行经常按照交易时间，来记录有关某一账户的交易情况，但是，很多人喜欢按照票据号来收到其银行对

2、账单。因此，如何将按交易时间排序转换成按支票编号来排序，就成为一个对几乎排好序的输入进行排序的问题。证明在这个问题上，过程INSERT_SORT的性能往往优于过程QUIKSORT。（引用自网络)对于QUIKSORT来说，输入一个已排序的数组属于最坏的情况，则每次区间划分都是最大程度的不对称。其算法运行的递归时间为T(n)=T(n-1)+Θ(n)，算法时间复杂度为Θ(n^2)；而对INSERT-SORT来说，输入一个已排序的数组却属于最佳的情况，算法时间复杂度为O(n)。也就是说当输入一个几乎排好序的数组，快速排序趋于最坏的情况，而插入排序却趋于最佳的情况7.3-2在过程RANDOMIZED

3、_QUIKSORT的运行过程中，最坏情况下对随机排序产生器RANDOM调用了多少次？最佳情况下调用了多少次？以Θ记号形式个给出你的答案。（引用自网络)随机快速排序中，只要区间包含元素数目大于1，则需调用RANDOMIZED-PARTITION，选取主元（pivot）进行区间划分，而主元的选取需调用Random。主元（pivot）一旦被选出来后，就不会在加入到后续的排序了。直白来说就是，有多少次主元（pivot）选取就有多少次随机数生成。另一方面从算法的递归二叉树树上来看，递归树二叉树的非叶子节点可表示一个主元（pivot）；而叶子节点分为两种，一种节点是包含0个元素，另一种节点是包含1个元

4、素，而且该元素不是主元（pivot）。非叶子节点和包含1个元素的叶子节点的数目之和就是输入序列的大小n。即递归树的非叶子节点的数目就是调用RANDOM的次数。调用RANDOM次数T(RANDOM)≤n，即T(RANDOM)=O(n)。　　又根据二叉树的性质，对于任意一棵二叉树，如果其叶结点数为a，而度数为2的结点（非叶子节点）总数为b，则a=b+1；对于快速排序的递归二叉树中，非叶子节点度数均为2。假设含有0个元素的叶子节点数目a0（≥0），含有1个元素的叶子节点数目为a1，所以b=a-1≥a1-1；又b+a1=n，可得b≥n/2-1，即T(RANDOM)=Ω(n)。这里有错误8.2-4请

5、给出一个算法，使之对给定的介于0到k之间的n个整数进行预处理，并能在O(1)时间内回答出输入的整数中有多少个落在[a...b]区间内。你给出的算法的预处理时间为Θ(n+k)。略....8.3-4说明如何在O(n)时间内，对0~n^2-1之间的n个数进行排序。把整数转换为n进制再排序，每个数有两位，每位的取值范围是[0..n-1]，再进行基数排序引用自http://blog.csdn.net/mishifangxiangdefeng/article/details/76858398.4-2桶排序的最坏情况运行时间是什么？如果要在保持其线性运行时间的同时，使最坏情况时间为O(nlgn)，要对算

6、法做什么样的修改？当分布不均匀时，全部元素都分到一个桶中，则O(n^2)，当然[算法导论8.4-2]也可以将插入排序换成堆排序、快速排序等，这样最坏情况就是O(nlgn)。9.1-1证明：在最坏情况下，利用n+(lgn)-2次比较，即可得到n个元素中的第2小元素。（提示：同时找最小元素）.对所有元素，两个一组比较大小，小的一个进入下一轮比较。一直到比较出最小的元素。此时所有比较结果构成一棵二叉树。比较次数为n-1。略....详情百度，懒的打了。9.2-1证明:在RANDOMIZED-SELECT中,对于长度为0的数组,不会进行递归调用.从RANDOMIZED-SELECT函数知，长度为0的

7、数组p=r，那么直接返回A[p].不做下面的随机划分和递归调用。9.3-3假定元素的值不同，说明如何才能使快速排序在最坏情况下以O(nlgn)时间运行.以RANDOMIZED-SELECT作为选择中值的算法9.3-7给出一个O(n)时间的算法，在给定一个有n个不同数字的集合S以及一个正整数k<=n后，它能确定出S中最接近其中位数的k个数.step1：求出数组的中位数的值O(n)step2：计算数组每个数与中位数差的绝对值