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

杭电算法设计与分析复习提纲TOC杭电算法设计与分析复习提纲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银行经常按照交易时间，来记录有关某一账户的交易情况，但是，很多人喜欢按照票据号来收到其银行对账单。因此，如何将按交易时间排序转换成按支票编号来排序，就成为一个对几乎排好序的输入进行排序的问题。证明在这个问题上，过程INSERT_SORT的性能往往优于过程QUIKSORT。 （引用自网络)对于QUIKSORT来说，输入一个已排序的数组属于最坏的情况，则每次区间划分都是最大程度的不对称。其算法运行的递归时间为T(n)=T(n-1)+Θ(n)，算法时间复杂度为Θ(n^2)；而对INSERT-SORT来说，输入一个已排序的数组却属于最佳的情况，算法时间复杂度为O(n)。也就是说当输入一个几乎排好序的数组，快速排序趋于最坏的情况，而插入排序却趋于最佳的情况7.3-2在过程RANDOMIZED_QUIKSORT的运行过程中，最坏情况下对随机排序产生器RANDOM调用了多少次？最佳情况下调用了多少次？以Θ记号形式个给出你的答案。 （引用自网络)随机快速排序中，只要区间包含元素数目大于1，则需调用RANDOMIZED-PARTITION，选取主元（pivot）进行区间划分，而主元的选取需调用Random。主元（pivot）一旦被选出来后，就不会在加入到后续的排序了。直白来说就是，有多少次主元（pivot）选取就有多少次随机数生成。另一方面从算法的递归二叉树树上来看，递归树二叉树的非叶子节点可表示一个主元（pivot）；而叶子节点分为两种，一种节点是包含0个元素，另一种节点是包含1个元素，而且该元素不是主元（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请给出一个算法，使之对给定的介于0到k之间的n个整数进行预处理，并能在O(1)时间内回答出输入的整数中有多少个落在[a...b]区间内。你给出的算法的预处理时间为Θ(n+k)。略8.3-4说明如何在O(n)时间内，对0~n^2-1之间的n个数进行排序。把整数转换为n进制再排序，每个数有两位，每位的取值范围是[0..n-1]，再进行基数排序引用自/mishifangxiangdefeng/article/details/76858398.4-2桶排序的最坏情况运行时间是什么？如果要在保持其线性运行时间的同时，使最坏情况时间为O(nlgn)，要对算法做什么样的修改？当分布不均匀时，全部元素都分到一个桶中，则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的数组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：计算数组每个数与中位数差的绝对值，存于另一个数组B中O(n)step3：求出数组B中第k小的数retO(n)step4：计算数组S中与ret差的绝对值小于ret的数并输出O(n)其中，step4也可以通过划分的方法找出数组S中与ret差的绝对值小于ret的数13.1-5证明:在一棵红黑树中,从某结点x到其后代叶结点的所有简单路径中,最长的一条是最短一条的至多两倍.在一棵红黑树中，从某结点x到其后代叶结点的所有简单路径中，最长的一条是最短一条的至多两倍。反证法：假设存在一条最长路径长度是最短路径长度的2倍多1，即L1=k，L2=2k+1。为保证从根节点到L1和L2的黑高度相同，最小黑高为k，否则L2上必然出现两个红色是父子关系。那么L2中有k个黑色，k+1个红色，由于根节点必须是黑色，那么lL2中必定存在红色的子节点不是黑色的情况，因此与假设矛盾，命题得证。14.1-4写出一个递归过程OS-KEY-RANK(T,k)使得顺序统计树T和某个关键字k为输入，输出k的秩（排序）。14.1-5给定含有n个元素的顺序统计树中的一个元素x和一个自然数i，如何在O(lgn)的时间内找到元素x的第i个后继？15.2-2请给出一个递归算法MATRIX-CHAIN-MULTIPLY(A,s,i,j)，使之在给出矩阵序列<A1,A2,...,An>，和由MATRIX-CHAIN-ORDER计算出的表s，以及下标i和j后，能得出一个最优的矩阵链乘法。(初始调用为MATRIX-CHAIN-MULTIPLY(A,s,1,n))。MATRIX-CHAIN-MULTIPLY(A,s,i,j)if(j>i)x=MATRIX-CHAIN-MULTIPLY(A,s,i,s(i,j))y=MATRIX-CHAIN-MULTIPLY(A,s,s(i,j)+1,j)returnMATRIX_MULTIPLY(x,y)elsereturnAi15.3-2画出2.3.1节的过程MERGE-SORT作用于一个包含16个元素的数组上的递归树。请解释在加速一个好的分治算法如MERGE-SORT方面，做备忘录方法为什么没有效果？没有重叠子问题16.1-2假设不再总是选择第一个结束的活动，而是选择最后一个开始、且与之前选入活动兼容的活动。试说明这种方式如何成为一个信心算法，并证明它能得到一个最优解。16.2-4Midas教授从Newark开一辆车沿着80号洲际公司到Reno。他车子的油箱在满的时候可以存放够跑n英里的汽油，并且他的地图标出子在他的路途中加油站之间的距离。教授希望在路途中尽量少加油。请给出一个高效的方法，来帮助教授决定哪一