算法设计与分析--01345--19日上-复习资料

算法设计与分析--01345--19日上-复习资料一、填空1.解递归方程可利用（毋函数法）2.设且x是素数}，则︱S︱＝（8）3.对算法的分析必须脱离具体的（计算机结构和程序设计语言）4.如果f(n)和g(n)都是单调递增的，则f(n)+g(n)（单调递增）5.EULER函数Ψ(17)的值为（16）6.设S={x|xÎ{1,2,…,10}且x是合数}，则︱S︱＝（6）7.如果f(n)和g(n)都是单调递增的，则f(2g(n))（单调递增）8.EULER函数Ψ(16)的值为（8）9.序列(7，10，15，3，18，21，2)的逆序总数为（9）10.属于分配排序技术的是（基数排序）11.用基数排序法对下面数据进行排序：312，290，180，653，358，432，865，264，451，526，239；首先按照第一位的大小依次放到0到9的桶中，把各桶中的数据收集起来，把收集好的数据再按第二位排序，依次放到0到9的各桶中，则第6号桶的数据为（865）12.在BM算法中，设模式P=“pattern”,则滑动距离函数dist[e]值为（2）13.设模式Pattern=”aabaaaa”，利用KMP算法计算出的next(6)值为（3）14.同步并行算法是指某些进程（必须等待）别的进程的一类并行算法。15.在最坏情况下，分配分块排序的复杂性为（O(nlogn)）16.算法设计方法主要有分治法、回溯法、贪心法、动态规划法、分支界限法。17.数据压缩是指用较少的信息表示原有较多的信息，已达到节省存储空间的目的。18.字符串模式匹配操作是字符串所有运算的基础。19.在顺序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找关键码11，所需比较的次数是4。20.可以从不同的角度将并行算法分类，如数值并行算法和非数值并行算法；同步并行算法和异步并行算法；SIMD、MIMD并行算法；VLSI并行算法。21.同步并行算法是指某些进程必须等待别的进程的一类并行算法。22.并行算法的加速比为求解相应问题的最快串行算法在最坏情况下的运行时间除以该并行算法在最坏情况下的求解该问题的运行时间。23.图的深度优先遍历一般应采用（回溯法）24.对算法的分析必须脱离具体的（计算机结构和程序设计语言）25.广泛应用于数据安全与加密领域的算法是（大整数相乘算法）26.EULER函数Ψ(21)的值为（18）27.如果f(n)和g(n)都是单调递减的，则g(g(n))（单调递减）28.设且x是素数}，则︱S︱＝（4）29.简单字符串匹配算法在最坏情形下，总共要执行字符的匹配比较操作次数为（(n-m+1)*m）30.序列(7，10，5，3，8，21，2)的逆序总数为（12）31.不属于分配排序技术的是（冒泡排序）32.用基数排序法对下面数据进行排序：312，290，180，653，358，432，865，264，451，526，239；首先按照第一位的大小依次放到0到9的桶中，把各桶中的数据收集起来，把收集好的数据再按第二位排序，依次放到0到9的各桶中，则第5号桶的数据为（451）33.所谓全信息压缩是指（可以采用逆向方式恢复信息原形）34.采用大整数相乘算法，计算2368×3925所做的一位整数乘法的次数为（9）35.在BM算法中，设模式P=“pattern”,则滑动距离函数dist[n]值为（7）36.设模式Pattern=”aabaaaa”，利用KMP算法计算出的next(7)值为（3）37.Flynn分类法将并行计算机分为（4）类。38.对于算法设计来说，递归是著名的分治策略。39.函数f(n)=logn和g(n)=log3n这两个函数阶的关系是f(n)=Θ(g(n))。40.在顺序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找关键码10，所需比较的次数是3。41.并行计算机上的分类主要有两类方法：Flynn分类法和Handler分类法。42.异步并行算法是指各进程之间无需相互等待的一类并行算法。43.并行算法的复杂度主要考量两方面，它们是运行时间和处理器数目。44.设且x是素数}，则︱S︱＝（4）45.分支界限法常用于求（最优解）46.对于给定的序列，其毋函数（唯一确定）47.如果f(n)和g(n)都是单调递增的，则f(n)+2g(n)（单调递增）48.EULER函数Ψ(7)的值为（6）49.EULER函数Ψ(19)的值为（18）50.序列c(n,0),c(n,1),…,c(n,n-1)对应的毋函数是（(1+x)n-xn）51.设,2,…,20}且x是合数}，则︱S︱＝（12）52.EULER函数Ψ(8)的值为（4）53.ASCII码压缩法对纯数据文本的压缩率量为（62.5%）54.序列(7，10，3，3，8，21，2)的逆序总数为（11）55.对n个元素的线性表进行冒泡排序，最好情况下的时间复杂度为（O(n)）56.用基数排序法对下面数据进行排序：312，290，180，653，358，432，865，264，451，526，239；首先按照第一位的大小依次放到0到9的桶中，把各桶中的数据收集起来，把收集好的数据再按第二位排序，依次放到0到9的各桶中，则第2号桶的数据为（526）57.分配和归并混合排序算法在最坏情形下的时间复杂性为（O(n*logn)）58.在BM算法中，设模式P=“abcdae”,则滑动距离函数dist[a]值为（1）59.设模式Pattern=”aabaaaa”，利用KMP算法计算出的next(5)值为（2）60.Strassen方法的思想是将相乘的A、B矩阵分成（4）个矩阵块。61.结合KMP算法思想改进后的BM算法速度较快，其不足是需要时间计算（delta函数）62.算法分析方法主要有递归展开法和毋函数法。63.设模式串长为m，正文串长为n；则在最坏情况下，BM算法的时间复杂度为Θ(mn)。64.在顺序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找关键码30，所需比较的次数是4。65.设且x是偶数}，则︱S︱＝（100）66.序列c(n,0),c(n,1),…,c(n,n)对应的毋函数是（(1+x)n）67.EULER函数Ψ(18)的值为（6）68.数据压缩是（可逆或不可逆的）69.序列(17，10，15，3，8，21，2)的逆序总数为（14）70.对n个元素的线性表进行冒泡排序，平均时间复杂度为（O(n2)）71.在BM算法中，设模式P=“pattern”,则滑动距离函数dist[a]值为（5）72.设模式Pattern=”aabaaaa”，利用KMP算法计算出的next(3)值为（2）73.在顺序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找关键码11，所需比较的次数是（4）74.KMP算法是以下面的人来命名的（Knuth-Morris-Pratt）75.设模式串长为m，正文串长为n；1970年，S.A.Cook在理论上证明了字符串模式匹配问题可在时间（O(m+n)）内完成。76.使用大整数相乘算法计算两个n位整数的乘积，所需的一位数乘法次数约为n1.59次77.用较少信息表示原有的较多的信息，以达到节省存储空间的技术是数据压缩技术。78.设模式串长为m，正文串长为n；则在最坏情况下，BM算法的时间复杂度为Θ(mn)。79.在顺序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找关键码6，所需比较的次数是4。80.并行算法的复杂度主要考量两方面，它们是运行时间和处理器数目。81.瑞士的N.Wirth教授提出的著名公式是：算法+数据结构=程序。82.可以从不同的角度将并行算法分类，如数值并行算法和非数值并行算法；同步并行算法和异步并行算法；SIMD、MIMD、VLSI并行算法。83.分布式并行算法是指由通讯链路连接的多结点（计算机）并行完成某一计算任务的一类并行算法。84.序列c(n,1),c(n,2),…,c(n,n)对应的毋函数是（(1+x)n–1）85.EULER函数Ψ(23)的值为（22）86.下列哪一项不属于单向HASH函数的应用范围（加密）87.设且x是素数}，则︱S︱＝（8）88.序列(7，10，15，3，8，21，2)的逆序总数为（11）89.对n个元素的线性表进行冒泡排序，最坏情况下的时间复杂度为（O(n2)）90.BM算法对待搜索串的扫描方式是（自右至左无回溯）91.在BM算法中，设模式P=“text”,则滑动距离函数dist[e]值为（2）92.设模式Pattern=”aabaaaa”，利用改进的KMP算法计算出的newnext(4)值为（0）93.对于非对称密码体制，每个当事人所需要的密钥数是（2）94.简单字符串匹配算法在最好情形下，进行的匹配比较操作次数为（(n-m+1)）95.计算机算法按数据类型可以分为两类，它们是数值运算和非数值运算96.算法分析方法主要有递归展开法和毋函数法。97.设模式串长为m，正文串长为n；则在最坏情况下，KMP算法的时间复杂度为O(m+n)。98.在顺序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找关键码1，所需比较的次数是3。99.单向的HASH函数可应用于（数字签名）单向的HASH函数可应用于（消息摘要）100.设且x是合数}，则︱S︱＝（6）101.基于关键字比较的排序时间复杂度的下界是（O(n*logn)）102.序列(7，1，15，3，8，21，2)的逆序总数为（9103.用基数排序法对下面数据进行排序：312，290，180，653，358，432，865，264，451，526，239；首先按照第一位的大小依次放到0到9的桶中，把各桶中的数据收集起来，把收集好的数据再按第二位排序，依次放到0到9的各桶中，则第1号桶的数据为（312）104.简单串匹配算法对正文串的扫描方式是（自左至右有回溯）105.在BM算法中，设模式P=“text”,则滑动距离函数dist[x]值为（1）106.设模式Pattern=”aabaaaa”，利用改进的KMP算法计算出的newnext(7)值为（2）107.计算机算法按数据类型可以分为两类，它们是数值运算和非数值运算。108.改进的冒泡法对n个数据进行排序，在最坏的情况下，该算法所需的数据比较次数为n(n-1)/2。110.设模式串长为m，待搜索串长为n；则在最坏情况下，KMP算法的时间复杂度为O(m+n)。111.在顺序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找关键码21，所需比较的次数是2。112.RSA密码体制主要涉及的运算是（模运算）113.不基于关键字比较的排序是（基数排序）114.序列(7，10，15，3，8，1，2)的逆序总数为（15）115.用基数排序法对下面数据进行排序：312，290，180，653，358，432，865，264，451，526，239；首先按照第一位的大小依次放到0到9的桶中，把各桶中的数据收集起来，把收集好的数据再按第二位排序，依次放到0到9的各桶中，则第3号桶的数据为（432）116.KMP算法对待搜索串的扫描方式是（自左至右无回溯）117.在BM算法中，设模式P=“text”,则滑动距离函数dist[t]值为（3）118.设模式Pattern=”aabaaaa”，利用改进的KMP算法计算出的newnext(6)值为（3）119.基数排序属于（分配排序）120.回溯法属于（穷举方法）121.时间复杂性达到下界的算法称为最优算法122.算法设计方法主要有分治法、回溯法、贪心法、动态规划法、分支界限法。123.常见的数据压缩方法主要有ASCII码压缩法、模式置换压缩法LZ压缩法。124.在顺序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找关键码8，所需比较的次数是2。125.分治法常伴随着（递归）126.解递归方程可利用