吉林大学自考算法设计与分析01345复习资料

算法设计与分析-01345-19日上-新资料1.n+n*log10n2=（Θ(n*logn2)）2.设S={x|x{1,2,…,20}且x是素数}，则︱S︱＝（8）3.对算法的分析必须脱离具体的（计算机结构和程序设计语言）4.如果f(n)和g(n)都是单调递增的，则f(n)+g(n)（单调递增）5.Log(n!)=（Θ(n*lnn)）6.可以用来求最优解的是最优解分支界限法常用于求（分支界限法）7.设S={x|x{1,2,…,30}且x是素数}，则︱S︱＝（10）8.设S={x|x{1,2,…,200,201}且x是奇数}，则︱S︱＝（101）9.EULER函数Ψ(74)的值为（343）10.属于分配排序技术的是（基数排序）11.用基数排序法对下面数据进行排序：312，290，180，653，358，432，865，264，451，526，239；首先按照第一位的大小依次放到0到9的桶中，把各桶中的数据收集起来，把收集好的数据再按第二位排序，依次放到0到9的各桶中，则第6号桶的数据为（865）12.如果f(n)和g(n)都是加法非负的增函数，则f(n)g(n)（单调递增）13.设D是输入的集合，N(I)是ID出现的概率，M(I)是算法在输入I时执行的次数。则算法的最坏情形复杂性为（Max(M(I))(ID)）14.同步并行算法是指某些进程（必须等待）别的进程的一类并行算法。15.用基数排序法对下面数据进行排序：312，290，180，653，358，432，865，264，451，526，239；首先按照最高位的大小依次放到0到9的桶中，把各桶中的数据收集起来，把收集好的数据再按第二位排序，依次放到0到9的各桶中，则第2号桶的数据为（526）16.算法设计方法主要有分治法、回溯法、贪心法、动态规划法、分支界限法。17.数据压缩是指用较少的信息表示原有较多的信息，已达到节省存储空间的目的。18.是指在同一时间间隔内增加操作数量的技术是（并行处理技术）。19.序列c(n,0),c(n,1),…,c(n,n)对应的毋函数是（(1+x)n）20.常用来支持细粒度和中粒度的并行计算是（共享变量通信）21.同步并行算法是指某些进程必须等待别的进程的一类并行算法。22.并行算法的加速比为求解相应问题的最快串行算法在最坏情况下的运行时间除以该并行算法在最坏情况下的求解该问题的运行时间。23.由程序的控制和数据的相关性决定的是（软件并行性）24.对算法的分析必须脱离具体的（计算机结构和程序设计语言）25.求解有限期的作业调度问题一般应采用（贪心法）26.EULER函数Ψ(21)的值为（18）27.如果f(n)和g(n)都是单调递减的，则g(g(n))（单调递减）28.对于并行算法，除了研究所需的运行时间之外还需要研究算法所需（处理器的数目）29.简单字符串匹配算法在最坏情形下，总共要执行字符的匹配比较操作次数为（(n-m+1)*m）30.序列(7，10，5，3，8，21，2)的逆序总数为（12）31.下列哪个属性是单向的HASH函数不需要满足的性质（安全性）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.衡量算法的优劣通常依据（平均和最坏时间开销）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.BranchandBound的含义为（分支限界）42.异步并行算法是指各进程之间无需相互等待的一类并行算法。43.并行算法的复杂度主要考量两方面，它们是运行时间和处理器数目。44.设S={x|x{1,2,…,10}且x是素数}，则︱S︱＝（4）45.DES密码体制是（非对称密码体制）46.对于给定的序列，其毋函数（唯一确定）47.如果f(n)和g(n)都是单调递增的，则f(n)+2g(n)（单调递增）48.EULER函数Ψ(7)的值为（6）49.处理机的通信模型由所采用的通信算法和（系统结构决定）50序列c(n,0),c(n,1),…,c(n,n-1)对应的毋函数是（(1+x)n-xn）51设S={x|x{1,2,…,20}且x是合数}，则︱S︱＝（12）51.EULER函数Ψ(8)的值为（4）52.ASCII码压缩法对纯数据文本的压缩率量为（62.5%）53冒泡排序的方式是（数遍扫描数据序列）54对n个元素的线性表进行冒泡排序，最好情况下的时间复杂度为（O(n)）55.利用归并方法可以实现（数据排序）56.RSA密码体制的困难性是（大数分解）57.在讨论算法复杂性时必须加以考虑其（同步时间）58.设模式Pattern=”aabaaaa”，利用KMP算法计算出的next(5)值为（2）59.通常用来衡量算法的优劣的是（平均性态和最坏情形）60.结合KMP算法思想改进后的BM算法速度较快，其不足是需要时间计算（delta函数）61.算法分析方法主要有递归展开法和毋函数法。62.设模式串长为m，正文串长为n；则在最坏情况下，BM算法的时间复杂度为Θ(mn)。63.具有计算机复杂性的里程碑的时间段是（20世纪60年代）64采用大整数相乘算法，主要依据是（乘法开销比加法大）65.序列c(n,0),c(n,1),…,c(n,n)对应的毋函数是（(1+x)n）66.并行算法运行的物质基础是（并行计算机体系结构）67.数据压缩是（可逆或不可逆的）68.序列(17，10，15，3，8，21，2)的逆序总数为（14）69.对n个元素的线性表进行冒泡排序，平均时间复杂度为（O(n2)）70.计算机要充分发挥作用离不开（计算机软件）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.BM算法在最坏情形下的时间复杂度是（Θ(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.如果f(n)和g(n)都是单调递减的，则f(g(f(n)))（单调递减）83分布式并行算法是指由通讯链路连接的多结点（计算机）并行完成某一计算任务的一类并行算法。84对于一个m*n的矩阵A和一个n*q的矩阵B，WINOGRAD算法中整个算法总的乘法次数是（(mnp/2)+mn/2+qn/2）85.EULER函数Ψ(23)的值为（22）86.下列哪一项不属于单向HASH函数的应用范围（加密）87.第一台电子计算机产自（美国）88.序列(7，10，15，3，8，21，2)的逆序总数为（11）89.毋函数的实质是（把一个值域变换到另一值域）90.用基数排序法对下面数据进行排序：312，290，180，653，358，432，865，264，451，526，239；首先按照第一位的大小依次放到0到9的桶中，把各桶中的数据收集起来，把收集好的数据再按第二位排序，依次放到0到9的各桶中，则第0号桶的数据为（无数据）91.有助于编译器更好的发挥并行性的（硬件处理机）92.在BM算法中，设模式P=“text”,则滑动距离函数dist[e]值为（2）93.计算机图灵的评选是（一年一评）94.对于非对称密码体制，每个当事人所需要的密钥数是（2）95.简单字符串匹配算法在最好情形下，进行的匹配比较操作次数为（(n-m+1)）96.序列(1，7，10，15，13，21，28)经起泡排序所需的趟数为（2）97.算法分析方法主要有递归展开法和毋函数法。98设模式串长为m，正文串长为n；则在最坏情况下，KMP算法的时间复杂度为O(m+n)。99.在顺序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找关键码1，所需比较的次数是3。100.单向的HASH函数可应用于（数字签名）101.基于关键字比较的排序时间复杂度的下界是（O(n*logn)）102.改进的KMP算法比KMP算法更加有效是因为模式中（重复出现的字符较多）103.用基数排序法对下面数据进行排序：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.在非对称多处理机系统中，可以被称为执行处理机的是（一个或一组处理机具有执行能力）109.在顺序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找关键码21，所需比较的次数是2。110.RSA密码体制主要涉及的运算是（模运算）111.不基于关键字比较的排序是（基数排序）为了提高软件和硬件的并行性的匹配程度，我们可以通过增加硬件并行性的灵活程度和开发控制密集程序的（软件并行性）112.用基数排序法对下面数据进行排序：312，290，180，653，358，432，865，264，451，526，239；首先按照第一位的大小依次放到0到9的桶中，把各桶中的数据收集起来，把收集好的数据再按第二位排序，依次放到0到9的各桶中，则第3号桶的数据为（432）113.粒度问题的求解既要考虑并行程序中颗粒的数目还要考虑（颗粒的大小）114.在BM算法中，设模式P=“text”,则滑动距离函数dist[t]值为（3）115.设模式Pattern=”aabaaaa”，利用改进的KMP算法计算出的newnext(6)值为（3）116.在多处理机系统上，可以保持也可以不保持程序的状态，这取决于（存储器模型）117.回溯法属于（穷举方法）118.时间复杂性达到下界的算法称为最优算法119.算法设计方法主要有分治法、回溯法、贪心法、动态规划法、分支界限法。120.常见的数据压缩方法主要有ASCII码压缩法、模式置换压缩法LZ压缩法。121.模式置换压缩多用哪类情况（多次重复出现的信息）122.分治法常伴随着（递归）123.ASCII码压缩法对纯数据文本的压缩率量为（62.5%）124.设S={x|x{1,2,…,20}且x是合数}，则︱S︱＝（12）125.在指令级或循环级上借助