算法设计分析期中试题

《算法设计与分析》期中试卷一、叙述分治算法的基本思想及一般算法设计模式；二、叙述动态规划算法的基本步骤及动态规划算法的基本要素；三、改进课本P74的Lcs算法，使改进算法不用数组b亦可在O（m+n）的时间内构造最长公共序列；四、求下列函数的渐近表达式(1). 3n2+10n(2).n2/10+2n(3)21+1/n(4)logn3(5)10log3n五、对于下列各组函数发f（n）和g（n），确定f （n）=O(（g(n)）)或者f（n）= (（g(n)）)或者f（n）=θ(（g(n)）)，并简述理由(1). f（n）=logn2 , g(n)=logn+5;(2). f（n）=logn2 , g(n)= √n;(3), f（n）=n , g(n)= logn2;(4). f（n）=nlogn+n,g(n)=logn;(5). f（n）=10.g(n)=log10;(6). f（n）=log2n g(n)=logn(7). f（n）=2n g(n)= 3n;(8). f（n）=2n g(n)= 100n2;六、设a[0:n-1]是已排好序的数组，请改写二分搜索算法，使得当搜索元素x不----------------------------精品word文档值得下载值得拥有----------------------------------------------再数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。

当搜索元素在数组中时，i和j相同，均为x在数组中的位置七、设a[0:n-1]是有n个元素的数组，k（0<=k<=n-1）是非负整数。

试设计一个算法将子数组a[0:k]与a[k+1:n-1]换位。

要求算法在最坏的情况下耗时O(n),且只用到O(1)的辅助空间。

八、在一个由元素组成的表中出现次数最多的元素称为众数。

试写一个寻找众数的算法，并分析其计算复杂性。

九、设计一个O(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。

算法与程序设计期中考试试题算法与程序设计期中考试试题⼀、选择题：每题2分，30题，共60分（）1．以下问题中最适合⽤计算机编程处理的是。

A．制定本学期的学习计划B．计算正⽅形的周长C．创作⼀⾸歌曲D．求1000以内的所有素数（）2．⽤计算机解决问题的步骤⼀般为。

①编写程序②设计算法③分析问题④调试程序A．①②③④B．③④①②C．②③①④D．③②①④（）3．下⾯说法正确的是。

A．算法+数据结构=程序B．算法就是程序C．数据结构就是程序D．算法包括数据结构（）4．以下是算法具有的特征。

①有穷性②确定性③可⾏性④输⼊⑤输出A．①②③B．②③④C．③④⑤D．①②③④⑤（）5．常⽤的算法描述⽅法有。

A．⽤⾃然语⾔描述算法B．⽤流程图描述算法C．⽤伪代码描述算法D．以上都是（）6．流程图中表⽰判断框的是。

A．矩形框B．菱形框C．圆形框D．椭圆形框（）7．程序设计语⾔的发展阶段不包括。

A．⾃然语⾔B．机器语⾔C．汇编语⾔D．⾼级语⾔（）8．要使命令按钮显⽰⽂字“确定”，正确的设置是把该命令按钮的。

A．Font属性设置为“确定”B．ForeColor属性设置为“确定”C．Caption属性设置为“确定”D．BorderStyle属性设置为“确定”（）10．下⾯的属性中，⽤于设定控件⾼度的是。

A．F ont B．H eight C．Caption D．W idth （）11．窗体的BackColor属性⽤于设置窗体的＿＿＿＿。

(p18)A．宽度B．前景⾊C．⾼度D．背景⾊12．在VB中，若要将变量N定义为单精度型数据，则下列表⽰⽅法中正确的是化。

A．Dim N as String B．Dim N as Single C．Dim N as Integer D．Dim N as Long（）14．在程序设计的过程中，错误的声明⼀个变量会导致程序不能正常编译。

因此，需要规范合理地声明⼀个变量，下列合法的变量名是。

A．if B．zf3 C．8-a D．a#2（）17．某学校打算选拔⾝⾼T超过1.75⽶且体重W不⼤于55公⽄的⼈作为招⽣条件，表⽰该条件的布尔表达式为。

设计与算法分析考试题库一、选择题（每题2分，共20分）1. 在算法分析中，时间复杂度用来衡量算法的什么？A. 可读性B. 执行速度C. 资源消耗D. 可维护性2. 以下哪个排序算法的时间复杂度为O(n^2)？A. 快速排序B. 归并排序C. 选择排序D. 堆排序3. 动态规划与分治算法的主要区别是什么？A. 递归使用B. 子问题重叠C. 问题分解方式D. 算法效率4. 递归算法的基本原理是什么？A. 循环调用B. 重复执行C. 问题分解D. 迭代求解5. 在图算法中，深度优先搜索（DFS）和广度优先搜索（BFS）的主要区别在于？A. 搜索顺序B. 搜索深度C. 使用的数据结构D. 搜索效率6. 哈希表的冲突解决方法中，开放定址法和链地址法的主要区别是什么？A. 存储方式B. 冲突处理机制C. 访问速度D. 空间利用率7. 贪心算法在解决优化问题时，其选择的策略是？A. 随机选择B. 局部最优C. 全局最优D. 动态选择8. 以下哪个算法是解决最近公共祖先问题的？A. 二分查找B. 欧拉路径C. 弗洛伊德算法D. 树的深度优先搜索9. 算法的时间复杂度为O(1)表示该算法的执行时间与输入规模的大小？A. 成正比B. 成反比C. 无关D. 指数关系10. 在大O符号中，O(1)、O(log n)、O(n)、O(n log n)、O(n^2)、O(2^n)，按算法效率从高到低排序正确的是？A. O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n)B. O(2^n), O(n^2), O(n log n), O(n), O(log n), O(1)C. O(1), O(log n), O(n log n), O(n), O(n^2), O(2^n)D. O(1), O(n), O(log n), O(n log n), O(n^2), O(2^n)二、简答题（每题10分，共30分）11. 简述二分查找算法的基本思想及其时间复杂度。

《算法分析与设计》2012-2013-2学期期中测试（信息安全专业DQ 教学班）姓名： 学号： 得分：1. 证明()()()()()()()O f n O g n O f n g n +=+。

（10分）证明：对于任意f 1(n ) ∈ O (f (n ))，存在正常数c 1和自然数n 1，使得对所有n ≥ n 1，有f 1(n ) ≤ c 1f (n )成立。

类似，对于任意g 1(n ) ∈ O (g (n ))，存在正常数c 2和自然数n 2，使得对所有n ≥ n 2，有g 1(n ) ≤ c 2g (n )成立。

令c 3 = max{c 1, c 2}，n 3 = max{n 1, n 2}，则对所有的n ≥ n 3，有 f 1(n ) +g 1(n ) ≤ c 1f (n ) + c 2g (n ) ≤ c 3f (n ) + c 3g (n ) = c 3(f (n ) + g (n ))即()()()()()()()O f n O g n O f n g n +=+成立。

2. 将下列5个函数按渐近增长率由低至高进行排序，要求写出比较过程。

（15分）解： 100log 2log log log 24()log 100log ,()2log ,n n n f n n n f n n n +====(1) 2()f n 是对数函数的幂，5()f n 是幂函数，因此()25()()f n O f n =; (2) ()()()491105log limlimlim log n n n f n n nn n f n n →∞→∞→∞===∞，因此()54()()f n O f n =; (3) ()()423log 1limlimlim 0log n n n f n n n f n n n n→∞→∞→∞===，因此()43()()f n O f n =;(4) 对1()f n 和3()f n 取对数，有()()() 13log ()log loglog loglog ,log ()2log loglog log f n n n n n n n f n n n n =+=Θ=Ω=+=Θ，因为()log n O n =，所以()31()()f n O f n =;因此，5个函数按渐近增长率由低至高排序为25431(),(),(),(),()f n f n f n f n f n 。

算法分析与设计试题及答案一、选择题1. 下列哪个是属于分治算法的例子？A. 冒泡排序B. 归并排序C. 顺序查找D. 选择排序答案：B2. 在排序算法中，时间复杂度最优的是：A. 冒泡排序B. 插入排序C. 归并排序D. 快速排序答案：C3. 哪个不是动态规划的特点？A. 具有重叠子问题B. 通过递归求解C. 需要保存子问题的解D. 具有最优子结构答案：B4. 在图的广度优先搜索算法中，使用的数据结构是：A. 栈B. 队列C. 数组D. 堆栈答案：B5. 在最小生成树算法中，下列哪个不属于贪心策略？A. Kruskal算法B. Prim算法C. Dijkstra算法D. Prim-Kruskal混合算法答案：C二、简答题1. 请简述分治算法的思想和应用场景。

答案：分治算法的思想是将原问题分解成若干个规模较小且类似的子问题，然后解决子问题，最后将子问题的解合并得到原问题的解。

其应用场景包括排序算法（如归并排序、快速排序）、搜索算法（如二分查找）等。

2. 什么是动态规划算法？请给出一个动态规划算法的示例。

答案：动态规划算法是一种通过将问题分解成子问题并解决子问题来解决复杂问题的方法。

它的特点是具有重叠子问题和最优子结构性质。

以斐波那契数列为例，可以使用动态规划算法求解每一项的值，而不需要重复计算。

3. 图的深度优先搜索和广度优先搜索有什么区别？答案：图的深度优先搜索（Depth First Search，DFS）是一种先访问子节点再访问兄弟节点的遍历算法，通常使用递归或者栈实现。

而广度优先搜索（Breadth First Search，BFS）则是以层次遍历的方式展开搜索，使用队列来实现。

DFS更适合用于搜索路径，BFS则适用于寻找最短路径等。

4. 请简述贪心算法的特点及其应用场景。

答案：贪心算法的特点是每一步都采取当前状态下最优的选择，以期望得到全局最优解。

然而，贪心算法并不一定能求解所有问题的最优解，但对于一些特定问题，贪心算法往往能得到近似最优解。

选择题：(每题2分，共30分)1.衡量一个算法好坏的标准是（ C ）。

A.运行速度快B.占用空间少C.时间复杂度低D.代码短2.当输入规模为n时，算法增长率最快的是（ C ）。

A.12nB. 100log2nC.2n2D.3nlog3n3.渐进算法分析是指（ B ）。

A.算法在最好情况、最坏情况和平均情况下的代价B.当规模逐步往极限方向增大时，对算法资源开销“增长率”上的简化分析C.数据结构所占用的空间D.在最小输入规模下算法的资源代价4.当上下限表达式相等时，我们使用下列（ C ）来描述算法代价？A.大O 表示法B.大Ω表示法C.θ表示法D.小o表示法5.二分搜索算法是利用（ A ）实现的算法。

A.分治策略B.动态规划法C.贪心法D.回溯法6.下列不是动态规划算法基本步骤的是（ A ）。

A.找出最优解的性质B.构造最优解C.算出最优解D.定义最优解7.动态规划算法的基本要素为（ C ）。

A. 最优子结构性质与贪心选择性质B．重叠子问题性质与贪心选择性质C．最优子结构性质与重叠子问题性质D. 预排序与递归调用8.能采用贪心算法求最优解的问题，一般具有的重要性质为（ A ）。

A. 最优子结构性质与贪心选择性质B．重叠子问题性质与贪心选择性质C．最优子结构性质与重叠子问题性质D. 预排序与递归调用9.备忘录方法是那种算法的变形。

（ B ）。

A．分治法 B.动态规划法 C.贪心法 D.回溯法10.实现大整数乘法利用的算法是（ A ）。

A.分治策略B.动态规划法C.贪心法D.回溯法11.使用分治法求解不需要满足的条件是（ A ）。

A. 子问题必须是一样的B. 子问题不能够重复C. 子问题的解可以合并D. 原问题和子问题使用相同的方法解12.贪心算法与动态规划算法的主要区别是（ B ）。

A.最优子结构B.贪心选择性质C.构造最优解D.定义最优解13.实现最长公共子序列利用的算法是（ B ）。

A.分治策略B.动态规划法C.贪心法D.回溯法14.使用二分搜索算法在1000个有序元素表中搜索一个特定元素，在最坏情况下，搜索总共需要比较的次数是（ A ）。

算法设计与分析试卷一、填空题（20分，每空2分）1、算法的性质包括输入、输出、＿＿＿、有限性。

2、动态规划算法的基本思想就将待求问题＿＿＿＿＿、先求解子问题，然后从这些子问题的解得到原问题的解。

3、设计动态规划算法的4个步骤：（1）找出＿＿＿＿，并刻画其结构特征。

（2）＿＿＿＿＿＿＿。

（3）＿＿＿＿＿＿＿。

（4）根据计算最优值得到的信息，＿＿＿＿＿＿＿。

4、流水作业调度问题的johnson算法：（1）令N1=＿＿＿,N2={i|ai>=bj};（2）将N1中作业依ai的＿＿＿。

5、对于流水作业高度问题，必存在一个最优调度π，使得作业π（i）和π（i+1）满足Johnson 不等式＿＿＿＿＿。

6、最优二叉搜索树即是＿＿＿的二叉搜索树。

二、综合题（50分）1、当（a1,a2,a3,a4,a5,a6）=(-2,11,-4,13,-5,-2)时，最大子段和为∑ak(2<=k<=4)＿＿＿＿（5分）2、由流水作业调度问题的最优子结构性质可知，T（N，0）=＿＿＿＿＿＿（5分）3、最大子段和问题的简单算法(10分)int maxsum(int n,int *a,int & bestj){intsum=0;for (int i=1;i<=n;i++)for (int j=i;j<=n;j++)int thissum=0;for(int k=i;k<=j;k++)＿＿＿＿＿;if(thissum>sum){sum=thissum;＿＿＿＿＿＿；bestj=j;}}return sum;}4、设计最优二叉搜索树问题的动态规划算法OptimalBinarysearchTree? (15分)Void OptimalBinarysearchTree(int a,int n,int * * m, int * * w){for(int i=0;i<=n;i++) {w[i+1][i]=a[i]; m[i+1][i]=＿＿＿＿;}for(int r=0;r<n;r++)for(int i=1;i<=n-r;i++){int j=i+r;w[i][j]=w[i][j-1]+a[j]+b[j];m[i][j]=＿＿＿＿＿＿;s[i][j]=i;for(int k=i+1;k<=j;k++){int t=m[i][k-1]+m[k+1][j];if(＿＿＿＿＿) {m[i][j]=t; s[i][j]=k;}}m[i][j]=t; s[i][j]=k;}}5、设n=4, (a1,a2,a3,a4)=(3,4,8,10), (b1,b2,b3,b4)=(6,2,9,15) 用两种方法求4个作业的最优调度方案并计算其最优值？（15分）三、简答题（30分）1、将所给定序列a[1:n]分为长度相等的两段a[1:n/2]和a[n/2+1:n]，分别求出这两段的最大子段和，则a[1:n]的最大子段和有哪三种情形？(10分)答：2、由0——1背包问题的最优子结构性质，可以对m（i,j）建立怎样的递归式? (10分)3、0——1背包求最优值的步骤分为哪几步？（10分）参考答案：填空题：确定性分解成若干个子问题最优解的性质递归地定义最优值以自底向上的方式计算出最优值构造最优解{i|ai<bi} ai的非减序排序；将N2中作业依bi的非增序排序min{bπ(i),aπ(i+1)}≥min{bπ(i+1),aπ(i)}最小平均查找长度综合题：20 min{ai+T(N-{i},bi)}(1=<i<=n) thissum+=a[k] besti=i 0 m[i+1][j] t<m[i][j]法一：min(ai,bj)<=min(aj,bi)因为min(a1,b2)<=min(a2,b1) 所以1→2 (先1后2) 由min(a1,b3)<=min(a3,b1) 得1→3 （先1后3）同理可得：最后为1→3→4→2法二：johnson算法思想 N1＝{1，3，4} N2＝{2} N¹1＝{1，3，4} N¹2＝{2} 所以 N¹1→N¹2 得：1→3→4→2简答题：1 、（1）a[1:n]的最大子段和与a[1:n/2]的最大子段和相同。