下载文档原格式
《算法设计与分析》期中试卷一、叙述分治算法的基本思想及一般算法设计模式；二、叙述动态规划算法的基本步骤及动态规划算法的基本要素；三、改进课本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公⽄的⼈作为招⽣条件，表⽰该条件的布尔表达式为。
《算法分析与设计》2021-2021-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}，则对所有的nn 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. 实践表明可操作性最好且最有实际价值的是（B）情况下的时间复杂性。
A.最好B.最坏C.平均D.特殊2. 算法的时间复杂性函数用T(n)表示，其中参数n是指（ A ）。
A.问题规模B.运行时间C.输入量D.输出量3. 函数105logn2+n2logn+n3的渐近表达式为（C）。
A.logn2B.n2lognC.n3D. 1054. 二分搜索算法中，如果待查找元素x不在已排好序的n个元素中，则完成该搜索任务需用（B）时间。
A.O(nlogn)B.O(logn)C.O(n)D.O(n2)5. Strassen矩阵乘法问题中，改进算法的计算复杂性关键在于（ A ）。
A.减少矩阵乘法B.增加矩阵乘法C.减少矩阵加法D.增加矩阵加法6. 最优子结构和重叠子问题是（A）算法的两个基本要素。
A.动态规划B. 贪心C.分支限界D. 分治7. 使用贪心算法解决活动安排问题时使用了（B）优先的贪心选择策略。
A.最早开始活动B.最早结束活动C.时间最短活动D.时间最长活动8. f(n)= log7n,g(n)= 100logn，满足f(n)= （ B ）(g(n))。
A. OB.ΩC.Θ9. f(n)= logn8,g(n)= log(100n)，满足f(n)= （C）(g(n))。
A. OB.ΩC.Θ10. f(n)= 30(logn)10,g(n)= 30n5,满足f(n)= （A）(g(n))。
A. OB.ΩC.Θ11. f(n)= 105n,g(n)= log10n,满足f(n)= （ C ）(g(n))。
A. OB.ΩC.Θ12. f(n)= 4n ,g(n)= 410(3n),满足f(n)= （B）(g(n))。
A. OB.ΩC.Θ13. 贪心法解装载问题时，采用的解题策略是（B）。
P95A.平均分配两艘轮船的载重B. 按集装箱重量从轻至重装船C. 将第一艘轮船尽可能装满D. 将第二艘轮船尽可能装满14. 用回溯法解0-1背包问题时，解空间可构造为（C）的形式。
算法设计分析期中试题.pdf《算法设计与分析》期中试卷一、叙述分治算法的基本思想及一般算法设计模式；二、叙述动态规划算法的基本步骤及动态规划算法的基本要素；三、改进课本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不再数组中时，返回小于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个数组成的序列的最长单调递增子序列。
十、给定n中物品和一背包，物品i的重量是ω，体积是b i，其价值为v i ，背包的容量为C，容积为D。
测试题1. 简述下列策略的基本思想 (15) (1) 分治将输入规模为n 的问题分成k （一般取k=2）个子问题，子问题相互独立，与原问题性质相同。
先分别对k 个子问题求解，再将子问题的解合并成原问题的解。
由于子问题还很大，故采用递归技术对子问题不断分割，直至子问题可直接简单地解出。
(2) 贪心贪心法希望从求局部最优达到全局最优，即依据贪心策略逐步构造最优解。
即先按确定贪心策略，将输入量排序。
再依次做出当前最优的选择，即当前输入可以构成合法的部分解，则将此输入量选入。
决策一旦做出，就不可再更改。
(3) 动态规划动态规划也是将问题求解过程分成k 个阶段（划分子问题），逐步决策的方法。
与贪心法不同的是，动态规划采用划分子问题，自底向上规划的方法。
要求子问题的划分具备最优子结构性质，即“最优化原理”成立。
需列出当前决策对前阶段决策状态的依赖关系（贝尔曼方程），求出各子问题的最优解，并将子问题的最优解代到下一步的决策中，逐步规划，解出原问题的解。
贝尔曼方程：⎪⎩⎪⎨⎧+==≠}.{min ,0ij i j i j s w u u u2. 下列数组4,1,3,2,16,9,10,14,8,7构成一个堆吗？如果不是，请用自底向上算法建一个 a max-heap.(10) 1) 不是一个最大堆2）按照算法，从i=n/2-5处开始测试i=5 它的孩子节点 2*i=10 ，满足最大堆的规定i=4 ，2i=8，2i+1=9 不满足，整理如下：i=3 ，2i=6，2i+1=7 不满足，整理如下：i=2 ，2i=4，2i+1=5不满足，整理如下：i=1 ，2i=2，2i+1=3不满足，依次整理如下：3. 针对下列叙述，根据正确或错误，选择T或F，并简要说明卫生么.(30)(1) T F nlogn=O(n3) 是上界(2) T F根据master定理, 递归方程T(n)=3T(n/3)+n 的解是T(n)=Θ(n)正确答案：T(n)=O(nlogn)（3）T F 最坏情况下, 归并排序的时间渐进阶是O（n2）.归并排序最坏情况下的时间是：T(n)=O(nlogn)（4）T F 图的深度优先搜索的时间是O（n+|E|）。
平湖中学2007学年第二学期信息技术期中考试卷考试时间90分钟命题：吴海忠审题：史玮卷Ⅰ客观题本部分题目的答案请涂写在机读卡上一、判断题（每小题2分，共20分；认为正确的在机读卡上涂A，认为错误的涂C）1、事件就是发生在该对象上的事情。
（）2、用户在键盘上按下一个键，则会产生一个Click事件。
（）3、在面向对象的程序设计中，用属性来描述对象的状态。
（）4、在VB中，文本框具有Caption属性。
（）5、语句Dim r As Double，意思是声明变量r为双精度实数型。
（）6、函数Sqr(X)是求X的算术平方根。
（）7、函数Fix(-5.1)和函数Int(-5.1)的返回值都是-5。
（）8、a=3:b=2:c=-4是三个赋值语句。
（）9、确定性是算法的一个主要特征。
（）10、符号常量在程序运行过程中其值也是可以改变的。
（）二、选择题(每小题2分，共50分)11、算法是解决问题的（）A．程序代码B．方法与步骤C．计算公式D．最终结果12、结构化程序设计的三种基本结构是（）A．顺序结构、选择结构、树型结构B选择结构、树型结构、循环结构C．选择结构、赋值结构、树型结构D顺序结构、选择结构、循环结构13、流程图中开始／结束框用来表示算法的开始和结束，以下哪个表示开始／结束框（）A． B. C. D.14、“高速公路上的某处有一测速拍照系统，当车速超过规定时速时，照相机启动拍照，否则不拍照”。
用算法描述照相机的工作流程，合适的算法模式是（）A．顺序模式B．选择模式C．循环模式D．树型模式15、Visual Basic是一种面向（）的程序设计语言。
A．用户B．系统C．电脑D．对象16、如果要改变窗体的标题，则需要设置的属性是（）A．Caption B．Name C．Text D．Label17、VB控制工具箱中的控件是（）A．文本框B．单选按钮C．图片框D．标签18、下列控件中既可用于接受用户输入文本，又可用于显示文本的是（）A．Label 控件B．T extBox 控件C．Timer 控件D．CommandButton 控件19、下列可以作为VB变量名的是（）A．num-3 B．3num C．True D．num_220、在程序中用到某一整型变量的数据范围是-40000～40000，则该变量类型应说明为（）A．Integer B．Byte C．Long D．Boolean21、用下面语句定义的数组的元素个数是（）Dim A (-3 To 5) As IntegerA．6 B．7 C．8 D．922、下列给出的赋值语句中正确的是（）A．4 = M B．-M =MC．B=A－3D．x + y = 023、要从文本框TxtShow中输出“中国您好！”，则以下语句正确的是（）A．T extBox.Text="中国您好！" B．TxtShow.Text="中国您好！"C．bel="中国您好！" D．TxtShow.Text=“中国您好！”24、与数学表达式｜x-31｜对应的ＶＢ表达式是（）A．Sqr(x-31) Ｂ．Val(x-31) C．Abs(x-31) D．Str(x-31)25、Len(“Friend”)的值是（）。
成都理工大学2011-2012学年第二学期《算法语言与程序设计》期中考试试题考试时间：100分钟； 考试形式：开卷一、选择题（每小题2分，共30分）1. 下列不能用于描述算法的是（ ）。
(A) 数据流图 (B) 自然语言 (C) 程序设计语言 (D) 形式语言2. 一个C 程序执行是从（ ）。
(A)本程序的main()函数开始，到本程序main()函数结束；(B) 本程序的main()函数开始，到本程序的最后一个函数结束； (C) 本程序的第一个函数开始，到本程序的最后一个函数结束； (D) 本程序的第一个函数开始，到本程序main()函数结束。
3. 在高级语言编译过程中，生成可执行程序(.exe)的是（ ）阶段。
(A)编辑 (B)编译 (C)链接 (D)调试 4.判断字符型变量ch 是否为大写字母，应使用表达式( )。
(A) ch<='A'||ch>='Z' (B) ch>='A'&ch<='Z' (C) 'A'<=ch<='Z' (D) ch>='A'&&ch<='Z'5. 若int 型变量x 的初始值为10，则执行完y=x--运算后，变量x 和y 的值分别为（ ）。
(A)9,9 (B)10,10 (C)9,10 (D)10,9 6. 下列程序的执行结果是（ ）。
#include <stdio.h> void main(){ float x=213.825754; printf("%-5.3f\n",x); }(A)格式错误 (B)213.825 (C)213.826 (D)-213.826 7. 以下选项中不能用作C程序合法常量的是 A)1,234 B)'123' C)123D)"\x7G"8. 算法具有五个方面的性质，下列（ ）不是算法必须具备的性质。
