还剩22页未读，继续阅读
本资源只提供10页预览，全部文档请下载后查看！喜欢就下载吧，查找使用更方便
文本内容:
一、选择题算法分析中，记号表示记号标售，记号表示L B,A GD渐进下界渐进上界非紧上界紧渐进界非紧下界A BC DE.以下关于渐进记号的性质是正确的有2AA fn=®gn,gn=®hn=fn=®hnB fn=Ogn,gn=Ohn=hn=OfnC Ofn+Ogn=Omin{fn,gn}D fn=Ogn=gn=Ofn记号的定义正确的是
3.A存在正常数和使得对所有》有；A Ogn={fn|c nO n nO OW fn W cgn存在正常数和使得对所有，有}；B Ogn={fn|c nO n nOOW cgn W fn对于任何正常数〉存在正数和使得对所有有}；C Ogn={fn|c0,nO0nnO0W fncgn对于任何正常数存在正数和使得对所有有}；D Ogn={fn|c0,nO0n2nO0W cgnfn记号的定义正确的是
4.Q B存在正常数和使得对所有有；A Ogn={fn|c nO nNnO OWfnW cgn存在正常数和使得对所有有；B Ogn={fn|c nO n2nOOWcgnWfn}对于任何正常数〉存在正数和使得对所有有}；C gn={fn|c0,n00nNnO0W fncgn对于任何正常数存在正数和使得对所有有}；D gn={fn|c0,nO0nenO0Wcgnfn表示当输入规模为时的算法效率，以下算法效率最优的是
5.T n n C AT n=T n-1+1,T1=1BT n=2n2CT n=T n/2+1,T1=1D T n=3nlog2n动态规划算法的基本要素为
6.C最优子结构性质与贪心选择性质A重叠子问题性质与贪心选择性质B最优子结构性质与重叠子问题性质C预排序与递归调用D,下列不是动态规划算法基本步骤的是7A找出最优解的性质构造最优解A B算出最优解定义最优解C D.能采用贪心算法求最优解的问题，一般具有的重要性质为8A最优子结构性质与贪心选择性质Areturn false;（1分）else return true;（分）1（）void Color::Backtrack int t（）〃判断是否到叶节点（分）{if tn1{sum++;（）输出每个点的色号for int i=l;i=n;i++//cout«x[i]«;（分）cout«endl;2）else（）依次检查当前点（第点）是否可着第与）种颜色（分）for int i=l;i=4;i++//t/02（分）{x[t]=i;1（（））（）〃若当前点（第点）可着第种颜色,则递归调用（分）if Okt Backtrackt+1;ti3分请设计一个算法，实现优先队列的出队操作要求指出用什么数据结构实现优先
3.101队列；用语言描述算法2C答此题解法不唯一用堆实现优先队列分12算法2分SIFTk,i,m{temp=k[i];j=2*i;1分while j=m1分分{ifjmR[j].keyR|j4-l].keyj++;1if temp.key R[j].key1{R[i]=RUl;；分i=j;j=2*i1分else break;
0.5分R[i]=temp;
0.5}Delete n{temp=R
[1];R[l]=R[i];R[i]=temp;1分分SIFTk,l,n-l;1算法导论试题题型选择+解答一，选择1动态规划的设计思想是a自底向上自上而下从左向右从右向左a b c d2贪心算法的设计思想是b自底向上自上而下从左向右从右向左a b c d3以下哪一个更可能描述实际一个有效的算法da b c d4蝶形操作的设计思想是a分治法贪心算法动态规划回溯a bc d5以下哪一个不是问题NPC⑶单源最短路径巡回售货员问题布尔可满足性问题大数分解bc d6以下哪个不是几何研究中的基本操作a+b-cX d/7哪个问题不能用贪心算法解决⑶活动安排哈夫曼编码分数背包背包bc dO-l8哪个问题不能用动态规划解决c⑶分数背包背包最长简单路径最短简单路径bO-l c d9插入排序的最好时间复杂度是aan bnA2cnlgn dlgn10归并排序的时间复杂度是can bnA2cnlgn dlgn二，解答题共题，此处少题61编写伪代码并分析时间复杂度，需要设计的程序是运用递归算法设计插入排1序，并且用到折半查找提示要排序先排插入用折半查找a[l……n],……n-1],a[n]能否在给定的中判断是否存在两个数的和为并且时间复杂度是如2s[n]x,nlgn,果可以写出程序的伪代码，否则给出理由两个维矩阵乘法将分解为个维的矩阵，分析以下算法的时间3n AXB=C,A,B4n/2复杂度A=,B=,C=定义Pl=A11+A22B11+B22,P2=A11+A22Bll,P3=A11B11-B22,P4=A22-B11+B22,P5=A12+A11B22,P6=-A1HA21B11+B12,P7=A12-A22B114-B22则CU=P1+P4-P5+P7,C12=P3+P5,C21=P2+P4,C22=P1+P3-P2+P6递归斐波纳切数列的时间复杂度4矩阵链乘法计算最优代价，需要画出和书本上类似的三角形图动态规5p200划选择题-O、二分搜索算法是利用（）实现的算法1A、分治策略、动态规划法、贪心法、回溯法A BC D、下列不是动态规划算法基本步骤的是（）2A、找出最优解的性质、构造最优解、算出最优解、定义最优解A BC D、最大效益优先是（）的一搜索方式3A、分支界限法、动态规划法、贪心法、回溯法A BC D、在下列算法中有时找不到问题解的是（）4Bo、蒙特卡罗算法、拉斯维加斯算法、舍伍德算法、数值概率算法A BC D回溯法解旅行售货员问题时的解空间树是（
5.A）o、子集树、排列树、深度优先生成树、广度优先生成树A BC D下列算法中通常以自底向上的方式求解最优解的是（）
6.Bo、备忘录法、动态规划法、贪心法、回溯法A BC D、衡量一个算法好坏的标准是（）7Co运行速度快占用空间少时间复杂度低代码短A BC D、以下不可以使用分治法求解的是（）8Do棋盘覆盖问题选择问题归并排序背包问题A BC D0/1实现循环赛日程表利用的算法是（）
9.Ao、分治策略、动态规划法、贪心法、回溯法A BC D、下列随机算法中运行时有时候成功有时候失败的是（）10C数值概率算法舍伍德算法拉斯维加斯算法蒙特卡罗算法A BC D下面不是分支界限法搜索方式的是（）
11.D、广度优先、最小耗费优先、最大效益优先、深度优先A BC D下列算法中通常以深度优先方式系统搜索问题解的是（）
12.Do、备忘录法、动态规划法、贪心法、回溯法A BC D.备忘录方法是那种算法的变形（）13B、分治法、动态规划法、贪心法、回溯法A BC D哈弗曼编码的贪心算法所需的计算时间为（）
14.B oA、0（n2n）B、O（nlogn）C、0（2n）D、O（n）分支限界法解最大团问题时，活结点表的组织形式是（）
15.B、最小堆、最大堆、栈、数组A BC D最长公共子序列算法利用的算法是（）
16.B o、分支界限法、动态规划法、贪心法、回溯法A BC D实现棋盘覆盖算法利用的算法是（）
17.A o、分治法、动态规划法、贪心法、回溯法A BC D.下面是贪心算法的基本要素的是（）18C、重叠子问题、构造最优解、贪心选择性质、定义最优解A BC D.回溯法的效率不依赖于下列哪些因素（）19D满足显约束的值的个数计算约束函数的时间A.B.计算限界函数的时间确定解空间的时间C.D..下面哪种函数是回溯法中为避免无效搜索采取的策略（）20B递归函数剪枝函数随机数函数搜索函数A.B.Co D.、下面关于问题说法正确的是（）21NP B问题都是不可能解决的问题A NP类问题包含在类问题中B PNP完全问题是类问题的子集C NPP类问题包含在类问题中D NPP、蒙特卡罗算法是（）的一种22B、分支界限算法、概率算法、贪心算法、回溯算法A BC D,下列哪一种算法不是随机化算法（）23C蒙特卡罗算法拉斯维加斯算法动态规划算法舍伍德算法A.B.C.D.（）是贪心算法与动态规划算法的共同点
24.D、重叠子问题、构造最优解、贪心选择性质、最优子结构性质A BC D矩阵连乘问题的算法可由（）设计实现
25.B、分支界限算法、动态规划算法、贪心算法、回溯算法A BC D分支限界法解旅行售货员问题时，活结点表的组织形式是（）
26.A、最小堆、最大堆、栈、数组A BC D、矩阵乘法是利用（）实现的算法27Strassen A、分治策略、动态规划法、贪心法、回溯法A BC D、使用分治法求解不需要满足的条件是（）29A o子问题必须是一样的A子问题不能够重复B子问题的解可以合并C原问题和子问题使用相同的方法解D、下面问题（）不能使用贪心法解决30B单源最短路径问题皇后问题A BN最小花费生成树问题背包问题C D、下列算法中不能解决背包问题的是（）310/1A贪心法动态规划回溯法分支限界法A BC D、回溯法搜索状态空间树是按照（）的顺序32C中序遍历广度优先遍历深度优先遍历层次优先遍历、下列随机算法中运行时有时A BC D33候成功有时候失败的是（）C数值概率算法舍伍德算法拉斯维加斯算法蒙特卡罗算法A BC D实现合并排序利用的算法是（）
34.A、分治策略、动态规划法、贪心法、回溯法A BC D下列是动态规划算法基本要素的是（
35.D）o、定义最优解、构造最优解、算出最优解、子问题重叠性质A BC D下列算法中通常以自底向下的方式求解最优解的是（
36.B）o、分治法、动态规划法、贪心法、回溯法A BC D采用广度优先策略搜索的算法是（）
37.Ao、分支界限法、动态规划法、贪心法、回溯法、合并排序算法是利用（）A BC D38A实现的算法、分治策略、动态规划法、贪心法、回溯法、在下列算法中得到的解未必正确的是A BC D39（）Bo、蒙特卡罗算法、拉斯维加斯算法、舍伍德算法、数值概率算法A BC D、背包问题的贪心算法所需的计算时间为（）40BA、On2n B、O nlognC、O2n D、On实现大整数的乘法是利用的算法（）
41.Co、贪心法、动态规划法、分治策略、回溯法A BC D背包问题的回溯算法所需的计算时间为（）
42.0-1A、（）、（）、（）、（）A On2n BO nlognC O2n DOn采用最大效益优先搜索方式的算法是（）
43.Ao、分支界限法、动态规划法、贪心法、回溯法A BC D贪心算法与动态规划算法的主要区别是（）
44.Bo、最优子结构、贪心选择性质、构造最优解、定义最优解A BC D实现最大子段和利用的算法是（）
45.Bo、分治策略、动态规划法、贪心法、回溯法A BC D.优先队列式分支限界法选取扩展结点的原则是（46C）o、先进先出、后进先出、结点的优先级、随机A BC D.背包问题的贪心算法所需的计算时间为（）47BoA、0（n2n）B、0（nlogn）C、0（2n）D、O（n）、广度优先是（）的一搜索方式48A、分支界限法、动态规划法、贪心法、回溯法、舍伍德算法是（）的一种A BC D49B、分支界限算法、概率算法、贪心算法、回溯算法、在下列算法中有时找不到问A BC D50题解的是（）Bo、蒙特卡罗算法、拉斯维加斯算法、舍伍德算法、数值概率算法A BC D下列哪一种算法是随机化算法（）51D贪心算法回溯法动态规划算法.舍伍德算法A.B.C.D一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（）
52.Bo、重叠子问题、最优子结构性质、贪心选择性质、定义最优解A BC D采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法
53.的时间复杂度为（）BoA、O（n2n）B、O（nlogn）C、O（2n）D、O（n）以深度优先方式系统搜索问题解的算法称为（）
54.Do、分支界限算法、概率算法、贪心算法、回溯算法A BC D实现最长公共子序列利用的算法是（）
55.Bo、分治策略、动态规划法、贪心法、回溯法A BC D
二、填空题.算法的复杂性有时间复杂性和空间复杂性之分
1、程序是.算法用某种程序设计语言的具体实现
2、算法的“确定性”指的是组成算法的每条指令是清晰的,无歧义的
3.矩阵连乘问题的算法可由动态规划设计实现
4、拉斯维加斯算法找到的解一定是正确解
5、算法是指解决问题的一种方法或一个过程
6、从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法
7、问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征
8、以深度优先方式系统搜索问题解的算法称为回溯法
9、数值概率算法常用于数值问题的求解
10、计算一个算法时间复杂度通常可以计算循环次数、基本操作的频率或计算步
11、利用概率的性质计算近似值的随机算法是一数值概率算法,运行时以一定的概率得到正确12解的随机算法是_蒙特卡罗算法___________________________O、解决背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是动态规140/1划，需要排序的是回溯法，分支限界法、使用回溯法进行状态空间树裁剪分支时一般有两个标准约束条件和目标函数的界，15皇后问题和背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进N0/1行裁剪的是背包问题，只使用约束条件进行裁剪的是皇后问题、贪心选择性质是贪0/1N o16心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别、矩阵连乘问题的算法可由动态规划设计实现
17、拉斯维加斯算法找到的解一定是正确解
18.贪心算法的基本要素是.贪心选择质和最优子结构性质19o动态规划算法的基本思想是将待求解问题分解成若干子问题，先求解子问题，然后
21.从这些子问题的解得到原问题的解.算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和有限22性—四条性质、大整数乘积算法是用分治法来设计的
23、以广度优先或以最小耗费方式搜索问题解的算法称为分支限界法24o、舍伍德算法总能求得问题的一个解
25、贪心选择性质是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区26别.快速排序算法是基于分治策略的一种排序算法
27.动态规划算法的两个基本要素是.最优子结构性质和重叠子问题性质28回溯法是一种既带有系统性又带有跳跃性的搜索算法
30..分支限界法主要有队列式分支限界法和优先队列式分支限31FIFO界法分支限界法是一种既带有系统性又带有跳跃性的搜索算法
32.回溯法搜索解空间树时，常用的两种剪枝函数为约束函数和限界函数
33.o.任何可用计算机求解的问题所需的时间都与其规模有关
34.快速排序算法的性能取决于划分的对称性35o
三、算法填空背包问题的贪心算法
1.void Knapsackint n,float M,float v|],float w|],float x|]{Sortn,v,w;int i;for i=l;i=n;i++x[i]=0;float c=M;for i=l;i=n;i++{if w[i]c break;；x[i]=l「c--w i];if iv=n x[i]=c/w-i];}.最大子段和动态规划算法2int MaxSumint n,int a[]；存储当前最大的存储int sum=O,b=0//sum b[j],b b[j]；；forintj=l j=n j++{；if b0b+=a[j]；〃一旦某个区段和为负，则从下一个位置累和else b=a[i];ifbsum sum=b;}；return sum,贪心算法求装载问题3templateclass TypevoidLoadingint x[],Type w[],Type c,int n int=new int[n+1];for int i=1;i=n;i++x[i]=0;for int i=1;i=nw[t[i]]=c;i++{x[t[i]]=l;_____；,贪心算法求活动安排问题4templateclass TypevoidGreedySelectorint n,Type s|],Type f[|,bool A||{A]=true;int j=l;for int i=2;i=n;i++{ifs[i]=f[j]{A-i]=true;••旦；else A[i]=false;.快速排序5templateclass TypevoidQuicksort Typea[],int p,int r{ifPr{int q=Partitiona,p,r;对左半段排序Quicksort a,p,q-l;//对右半段排序Quicksort a,q+l,r;//.排列问题6Template classTypevoid permTypelist[],int k,int m{〃产生的所有排列ifk==m{〃只剩下一个元素for inti=0;i=m;i++cout«list[i];cout«endl;〃还有多个元素待排列，递归产生排列〈=else for inti=k;i m;i++swaplist[k],list[i];peirnlist,k+l;m;swaplist[k],list[i];
四、问答题1・分治法的基本思想时将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同递归地解这些子问题，然后将各个子问题的解合并得到原问题的解设计动态规划算法的主要步骤为2（）找出最优解的性质，并刻划其结构特征（）递归地定义最优值（）以自底向上的123方式计算出最优值（）根据计算最优值时得到的信息，构造最优解4分治法与动态规划法的相同点是将待求解的问题分解成若干个子问题，先求解子问题，然
3.后从这些子问题的解得到原问题的解两者的不同点是适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的而用分治法求解的问题，经分解得到的子问题往往是互相独立的分支限界法与回溯法的相同点是都是一种在问题的解空间树中搜索问题解的算法
4.T不同点（）求解目标不同；1（）搜索方式不同；2（）对扩展结点的扩展方式不同；3（）存储空间的要求不同4用回溯法搜索子集树的算法为5（）void backtrackintt（（）（）if tnoutput x;else（）for inti=0;iv=l;i++{（（）（））（）1f constraintt boundt backtrackt+l;））分治法所能解决的问题一般具有的几个特征是
6.（）该问题的规模缩小到一定的程度就可以容易地解决；1（）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；2（）利用该问题分解出的子问题的解可以合并为该问题的解；3（）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题4用分支限界法设计算法的步骤是
7.⑴针对所给问题，定义问题的解空间（对解进行编码）；分⑵确定易于搜索的解空间结构（按树或图组织解）；⑶以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索重叠子问题性质与贪心选择性质B最优子结构性质与重叠子问题性质C预排序与递归调用D.下面是贪心算法的基本要素的是（）9Co重叠子问题构造最优解贪心选择性质定义最优解A BC D（）是贪心算法与动态规划算法的共同点10D重叠子问题构造最优解A B贪心选择性质最优子结构性质C D.使用分治法求解不需要满足的条件是（）11Ao子问题必须是一样的子问题不能够重复A B子问题的解可以合并原问题和子问题使用相同的方法解C D.实现循环赛日程表利用的算法是（）12Ao分治策略动态规划法A B贪心法回溯法C D.使用分治法求解不需要满足的条件是（）13Ao子问题必须是一样的子问题不能够重复A B子问题的解可以合并原问题和子问题使用相同的方法解C D.下列算法中不能解决背包问题的是（）140/1A贪心法动态规划回溯法分支限界法A BC D.以下（）不能不能在线性时间完成排序15C计数排序基数排序堆排序桶排序A BC D.下列哪一种算法是随机化算法（）16D贪心算法回溯法动态规划算法舍伍德算法A BC D下列算法中通常以自底向上的方式求解最优解的（）分治法动态规划法贪心法
17.B A B Co回溯法D个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水，水流恒定
18.n如下（）说法不正确？A A让水桶大的人先打水，可以使得每个人排队时间之和最小A让水桶小的人先打水，可以使得每个人排队时间之和最小B让水桶小的人先打水，在某个确定的时间内，可以让尽可能多的人打上水C t若要在尽可能短的时间内，个人都打完水，按照什么顺序其实都一样D n.哈弗曼编码的贪心算法所需的计算时间为（）19B（）（）（）（）A On2n BO nlognC O2n DOn.下面关于问题说法正确的是（）20NP B问题都是不可能解决的问题A NP类问题包含在类问题中BP NP完全问题是类问题的子集C NPP常见的两种分支限界法的算法框架
8.队列式分支限界法按照队列先进先出原则选取下一个节点为扩展节点1FIFO FIFO2优先队列式分支限界法按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点回溯法中常见的两类典型的解空间树是子集树和排列树
9.当所给的问题是从个元素的集合中找出满足某种性质的子集时，相应的解空间树称为子集n S树这类子集树通常有个叶结点，遍历子集树需计算时间2n02n当所给的问题是确定个元素满足某种性质的排列时，相应的解空间树称为排列树这类排列n树通常有个叶结点遍历排列树需要计算时间n!0n!分支限界法的搜索策略是
10.在扩展结点处，先生成其所有的儿子结点分支，然后再从当前的活结点表中选择下一个扩展结点为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值限界，并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解
五、算法题给定已按升序排好序的个元素现要在这个元素中找出一特定元素返回其在数组L na[0:n-l],n x,中的位置，如果未找到返回-1写出二分搜索的算法，并分析其时间复杂度
1.templateclass TypeintBinarySearchType a[],const Typex,intn{〃在中搜索找到时返回其在数组中的位置，否则返回a[0:n]x,x-1Int left=0;int right=n-l;While left=right{int middle=left+right/2;if x=a[middle]return middle;if xa[middle]left=middle+l;else right=middle-l;Return-1;时间复杂性为Ologn利用分治算法写出合并排序的算法，并分析其时间复杂度
2.
1.void MergeSortTypea[],int left,int right至少有个元素if leftright{//2〃取中点inti=left+right/2;mergeSorta,left,i;mergeSorta,i+1,right;〃合并到数组mergea,b,left,i,right;b〃复制回数组copya,b,left,right;a算法在最坏情况下的时间复杂度为Onlogn皇后回溯法
3.Nbool Queen::Placeint k{〃检查位置是否合法x[k]for intj=l;jk;j++if absk-j==absx[j]-x[k]||x[j]==x[k]return false;returntrue;void Queen::Backtrackint tiftn sum++;else for inti=l;i=n;i++{x[t]=i;约束函数ifBacktrackt+1;.最大团问题4计算最大团void Clique::Backtrackint i//{〃到达叶结点{ifin；for intj=1;j=n;j++bestx[j]=x[j]bestn=cn;return;}//检查顶点与当前团的连接iint OK=1;；for intj=1;ji j++〃与不相连ifx[ja[i][j]==0{i jOK=0;break;}进入左子树ifOK{//x[i]=1;cn++;Backtracki+1;x[i]=0;cn—;}{//进入右子树ifcn+n-ibestn x[i]=0;Backtracki+1;}.最长公共子序列问题5哈弗曼编码算法
6.算法设计与分析试题
一、概念题队列完全二叉树堆类问题问题
1.
2.
3.
4.P
5.NP
二、程序填空题宽度优先图周游算法
2.procedure bftg,n的宽度优先周游////g declarevisitedn//将所有结点标记为未访问//⑴for iBlto ndorepeat//反复调用fori—1to ndo bfs//if visitedi=0then2endifrepeat endbft找一个图的所有着色方案
3.m—procedure mcoloringk//这是图着色的一个递归回溯算法图用它的布尔邻接矩阵表示它计算g graPhln,1n并打印出符合以下要求的全部解，把整数，分配给图中各个结点且使相邻近的结点的1,2,…m有不同的整数是下一个要着色结点的下标//k；global integerm,n,xl nbooleangraPh1n,1ninteger k//产生对所有的合法赋值//loop xk//将一种合法的颜色分配给call nextvaluekxk//o//没有可用的颜色了//if1then exitendifif2//至多用了种颜色分配给个结点//then printxm n//所有着色方案均在此反复递归调用中产生//else call mcoloringk+lm—endifrepeatend mcoloring
三、问答题.二分查找的思想是什么？1,请用递归方法写出归并排序法的主要思想和算法
2.已知如下多段图，请用动态规划方法的向后处理法写出求解此问题的递推公式并完成对各3结点的计算最小自然数求具有下列两个性质的最小自然数
4.n的个位数是；1n6若将的个位数移到其余各位数字之前，所得的新数是的倍2n n4提示仍用穷举法寻找，当找到一个符合条件者便停止“找到便停止”的重复，宜采用循环repeat—until以二叉链表为存储结构，分别写出求二叉树结点总数及叶子总数的算法
5.类问题包含在类问题中D NPP.背包问题贪心算法所需的计算时间为21B A0n2n BOnlogn CO2n D0n.背包问题的回溯算法所需的计算时间为22A AOn2n BOnlogn CO2n D0n,采用最大效益优先搜索方式的算法是23A分支界限发动态规划法贪心法回溯法A BC D在棋盘覆盖问题中，对于的特殊棋盘有一个特殊方块，所需的型骨牌的个数是
24.2kX2k LA A4k-1/3B2k/3C4k D2k下列随机算法中运行时有时候成功有时候失败的是
25.C数值概率算法舍伍德算法拉斯维加斯算法蒙特卡罗算法A BC D实现大整数的乘法是利用的算法
26.Co贪心法动态规划法分治策略回溯法A BC D
二、填空题,算法的复杂性有时间复杂性和空间复杂性之分
1.矩阵连乘问题的算法可由动态规划设计实现
2.从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法
3.算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和有限性四条性质
4.快速排序算法的性能取决于划分的对称性
5.使用二分搜索算法在个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复6n杂性为,在最坏情况下，搜索的时间复杂性为
三、解答题010logno,给定已按升序排好序的个元素现要在这个元素中找出一特定元素返回其在数组中的位1nnx,置，如果未找到返回写出二分搜索的算法，并分析其时间复杂度-1分析最有搜索二叉树和背包的时间复杂度
2.0/
1.试用动态规划算法实现最大子矩阵和问题求矩阵的一个子矩阵，使其各元素之各3nXm A为最大已知输入向量给出用的蝶形操作求输出向量的结果，并分析出的计4a=1,3,4,-2,FFT yFFT算时间复杂度,采用递归算法求递归方程算法描述如下就是递归问算法共1Fn=Fn-l+Fn-2,Fibonacci!需要进行多少次递归调用算法中没引用⑴一次称为一次递归调用有没有更好的算法来计F算若有请描述算法并分析复杂度Fn•如下算法是否产生平均分布的随即置换？为什么？2Permute-With-AllAn-lengthAfor i—1to nswapA[i],A[RANDOMl,n]注,随机、等可能地返回整数〈〈RANDOM nk,l kn能否在给定的中判断是否存在两个数的和为并且时间复杂度是如果可以写出程
3.s[n]x,nlgn,序的伪代码，否则给出理由活动选择问题
6.递归的时间复杂度分析1动态规划的时间复杂度分析2写出一个更优的算法，并且对其进行时间复杂度分析
3.多项式乘法问题7描述一个高效的算法来解决复数之间的多项式乘法，多项式的系数为复数，未知数也为复数并且对此进行时间复杂度分析郑算法考试题552013填空给一系列的函数，根据渐进性，从大到小排列nA3/2,nlgn,lgn,eAn,n!,nA2动归的两个性质贪心的两个性质问题问题1NP2P面试问题雇一个人的概率，雇个人的概率n复杂度分为和；动归是牺牲复杂度换取复杂度使用二分搜索算法在个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复杂性n为,在最坏情况下，搜索的时间复杂性为选择010logno摊还排序是情况下的代价1最优最坏平均最好A BC D动态规划的设计思想是2a自底向上自上而下从左向右从右向左a bc d贪心算法的设计思想是3b自底向上自上而下从左向右从右向左a bc d以下哪一个更可能描述实际一个有效的算法4da bcd蝶形操作的设计思想是5a分治法贪心算法动态规划回溯a bcd以下哪一个不是问题6NPC单源最短路径巡回售货员问题布尔可满足性问题大数分解a bcd以下哪个不是几何研究中的基本操作7a+b-cX d/哪个问题不能用贪心算法解决83活动安排哈夫曼编码分数背包背包bcdO-l哪个问题不能用动态规划解决9c分数背包背包最长简单路径最短简单路径a bO-l cd插入排序的最好时间复杂度是10aan bnA2cnlgn dlgn归并排序的时间复杂度是11can bnA2cnlgn dlgn算法分析中，记号表示记号标售，记号◎表示12B,Q AD渐进下界渐进上界非紧上界紧渐进界非紧下界ABC DE个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水，水流恒定13m如下说法不正确？AA让水桶大的人先打水，可以使得每个人排队时间之和最小A让水桶小的人先打水，可以使得每个人排队时间之和最小B让水桶小的人先打水，在某个确定的时间内，可以让尽可能多的人打上水C t若要在尽可能短的时间内，个人都打完水，按照什么顺序其实都一样D n.哈弗曼编码的贪心算法所需的计算时间为14BA On2n BOnlogn CO2n DOn.下面关于问题说法正确的是15NP B问题都是不可能解决的问题A NP类问题包含在类问题中B PNP完全问题是类问题的子集C NPP类问题包含在类问题中D NPP大题四路归并排序分解时分成四个，合并等其他步骤与二路归并相似，请写出核心算法，并分析时间复杂度矩阵链乘积的递归算法
1.Tn=1n=ln=2请详细分析该算法的时间复杂度给出最优二叉搜索树的程序代码和，概率
1.p q根据概率求画出二叉树的结构请说出有什么意义1e,w,roo323root[i,j]见大班试卷影印版的第五题3621蝶形操作见大班试卷的影印版第九题
1.FFt3621字符串自动机构造，见书
2.学年第二学期《计算机算法设计与分析》试题
2006.2007院系软件学院专业软件工程年级级2004一.简答题（共分）10略二.计算题（分）35（6分）对下列各组函数f（n）和g（n）,确定fn=Ogn或fn=Q gn或fn=gno⑴fn=3n,gn=2n2fn=log〃+5,gn=log n23fn=log n,gn=答⑴fn=（2Qgn分）2fn=9gn（2分）3fn=Ogn（分）采用动态规划策略，计算的最大子段和，并给出这个最大
2.8a={5,-3,7,4-5,9,210,32}子段和的起始下标和终止下标［设数组中的元素下标从开始］要求给出过程a1答；b[l]=5二b
[2]=max{b[l]+a
[2],a
[2]}max{2,-3}=2b
[3]=max{b
[2]+a
[3],a
[3]}=max{9,7}=9b
[4]=max{b
[3]+a
[4],a
[4]}=max{5,-4}=5b
[5]=max{b
[4]+a
[5],a
[5]}=max{0,-5}=0b
[6]=max{b
[5]+a
[6],a
[6]}=max{9,9}=9二b
[7]=max{b
[6]+a
[7],a
[7]}max{7,-2}=7b
[8]=max{b
[7]+a
[8],a
[8]}=max{17,10=17b
[9]=max{b
[8]+a
[9]a
[9]=max{14,-3=14b[l0]=max{b
[9]+a
[10],a
[10]}=max{16,2=16上述每两行分，共分15最大子段和为分171若数组下标从开始起始下标分，终止下标分16181若数组下标从开始起始下标分，终止下标分
050.
570.5（分）设有件工作分配给个人，将工作分配给第个人所花的费用为现将为
3.1133i jCij,每一个人都分配件不同的工作，并使总费用达到最小设要求1（）画出该问题的解空间树；（分）16（）写出该问题的剪枝策略（限界条件）；（分）21（）按回溯法搜索解空间树，并利用剪枝策略对应该剪掉的子树打；（分）3’2（）最终给出该问题的最优值和最优解（分）42答（）1231316169999X XXX（每个分枝分，或者是每层分，共分）126（）当耗费大于等于当前最优值时，剪枝（分）21（）见上图（每个分，共分）32X12（）最优值（分）491最优解2,1,3（分）给定两个序列请采用动态规划策略求出其最长公
4.8X=A,B,C,B,A,Y=B,D,C,A,B,共子序列要求给出过程答j012345i j,B DCAB0x000000z1A0000112B0111123C0112224B0112235A012223上述表内每一行一分，共分6最长公共子序列为分B,C,B2分考虑时的背包问题的实例、当
5.2n=30-1W={15,10,10},P={50,30,30},c=20x[l]=L x
[2]=0时,请计算Bound2o答分Bound3=50+5/10*20=652
三、算法填空题共分，每空分102给定种物品和一个背包，物品的重量是其价值是背包的容量为设物品已按单n iw[i],p[i],c位重量价值递减的次序排序每种物品不可以装入背包多次，但可以装入部分的物品求解i背包问题的贪心算法如下float Knapsackfloat xf],float w[],float p[],float c,intn表示装进包的物品价值总和{float maxsum=;//maxsum表示第个物品未装进包forinti=l;i=n;i++x[i]=0//x[i]=0ifor if；{x[i]=1maxsum+=;c-=w[i];else break;if c0{x[i]=c/w[i];;}return maxsum;答:共个空，每空分，总计分52100；；inti=l i=ni++w[i]=Cp[i]maxsum+=p[i]*c/w[i]
四、算法设计及分析题共分45分请用分治策略设计递归的二分检索算法，并分析其时间复杂性要求给出每个阶段
1.20所花的时间，在此基础上列出递归方程，并求出其解的渐进阶答此题解法不唯一算法分int bsearchA[l,K,L,H1分{if HLreturn-l;2else分{mid=L+H/2;2分if A[mid]==K1；分returnmid1分else ifA[midJK2分returnbsearchA,K,L,mid-1;2分else returnbsearchK,mid+l,H;2算法时间复杂性分析阶段所花时间为分V Divide011阶段所花时间为分Conquer Tn/21阶段没有花时间或者说，阶段所花时间为分merge merge011，算法时间复杂性递归方程如下当Tn=Ol nWO当分Tn=Tn/2+O12用套用公式法求解递归方程master methodVa=l,b=2,，，与同阶fn=Ol fn，分Tn=Olog n2分请用回溯法设计算法，用四种颜色给地图着色若在调用了其它算法，也需将该算
2.15法写出请在每个循环语句和条件判断语句后加注释答此题解法不唯一算法boolColor::Okint k「也叮=卜旧++//检查前个点与当前点第点颜色是否冲突分{{01;1-1k2if a[k]|j]==lx|j]==x[k]〃判断第点与当前点第点颜色是否冲突分j k2。
个人认证
优秀文档
获得点赞 0
