补充复习题

《算法设计与分析》补充复习题2015年5月一、是非判断题1、算法可以不满足确定性的要求。2、算法是求解问题的程序化解决方案。3、n*(n+1)∈O(n3)4、n*(n+1)∈O(n2)3、快速排序应用了蛮力法技术，并且是一个稳定的排序算法。4、0-1背包问题实例中的动态规划表中某一列值的序列总是非递减的。5、计算二项式系数的过程中，系数C(6,3)=216、如果e是加权连通图的权重最小的边，那么它必定是每一棵最小生成树的边。7、如果e是加权连通图的权重最小的边，那么它至少是图的一棵最小生成树的边。8、如果加权连通图的每条边权重值是互不相同，该图必定只有一颗最小生成树。9、如果加权连通图的每条边权重值不是各不相同，该图必定不止有一颗最小生成树。10、Huffman树的生成是应用了动态规划技术11、频率较高的字符的码长总是小于等于频率较低字符的码长。12、频率最低的2个字符具有相同的码长。13、n后问题和0-1背包问题都可以用回溯法来求解。14、插入排序应用了贪婪技术，且是一个不稳定的排序算法。15、Floyd算法应用了分治法技术16、旅行商问题可以用回溯法求解。二、简答题1、请用欧几里得算法求gcd(31415,14241)，并比较它们除法操作的次数。2、分别说明插入排序、合并排序、快速排序、选择排序、冒泡排序各采用了什么算法设计技术？分别用上述二种排序方法对序列F，X，B，N，P,L，F，E进行排序,要求写出它们的排序过程和结果。3、对下列邻接矩阵定义的有向图，用Warshall算法求它的传递闭包。01000010000100004、对于下图所示的无向联通带权图，请分别说明并画出Prime、Kruskal算法的选边过程，及所生成的最小生成树。65154364265、有一个不带权的无向图如下所示,请表示该图的邻接矩阵和邻接链表；并运用深度优先算法,从a点开始进行遍历该图。123456fbcgead6、对于下列0-1背包问题，分别用动态规划算法求出其最优解，并给出最优解的物品组成。物品重量价值132522203112444055507、动态规划技术与贪婪技术各有什么特点？它们有什么区别,各适合什么场合？以背包问题(包括0-1背包问题）为例说明之。8、对于下面的数据，请构造Huffman编码，并对ACBDFDCAC进行编码。9、对于n后问题，若每个皇后限定放置在不同的行，设解表示成(X1、X2、X3…Xi…Xn)。问Xi表示什么意思，整个解空间多大，如何判断两个元素是否在同一列和同一斜线，对于4皇后问题，写出满足条件的一个解。10、考虑包含5个字符的字符表{A,B,C,D,E)，他们的频率如下，请构造一套Huffman编码。并对文本ABEACABADE进行编码。字符ABCDF出现频率0.40.20.10.150.15字符ABCDE出现频率0.350.10.20.20.15对于币值为1,3,5且n=9的找零问题，利用动态规划算法求其所有解.11.对附图所示有向图，给出它的邻接矩阵，并用Warshall算法求它的传递闭包。12.如果要在下列文本中寻找模式“GARDEN”，请确定用蛮力法执行字符比较的次数。THERE_IS_MORE_TO_LIFE_THAN_INCREASING_ITS_SPEED13、对附图所示的有向图，给出它的邻接矩阵，并用Warshall算法求它的传递闭包。14、有一个不带权的有向图如下所示,请运用源删除算法进行拓扑排序。ADCBACDBadbec15、对于下列0-1背包问题中物品重量和价值，且背包的承重量W=5，请用动态规划算法求出其最优解，并给出最优解的物品组成。16、对于币值为1,3,5且n=9的找零问题，利用动态规划算法求其所有解三、算法设计题1、设计一个算法，它返回给定查找键在列表中的出现次数，给出算法的伪代码描述，并分析它的效率。比较它与经典顺序查找算法的效率差异。2、试给出合并排序MergeSort(a[0..N-1])、快速排序QuickSort(a[0..N-1])算法的伪代码描述，分析它的效率；并举例说明其执行过程。3、试写出选择排序法对数据进行排序的函数ChooseSort(a[0..N-1])，并说明在此蛮力法是如何运用的。给出它的时间复杂度分析。4、元素唯一性问题：请给出验证给定数组中所有元素是否唯一的算法伪代码描述。5、写出插入排序的伪代码描述InsertionSort(a[0..N-1])分析它的效率；并举例说明其执行过程。物品重量价值12122110332042156、实现一个算法求n个元素的列表中的最大元素并分析它的效率。MaxElement(a[0..n-1])//求列表中最大元素，