4. end for
5. End for
问:1. 最少执行多少次元素的赋值操作?何时最少? 2. 最多执行多少次元素的赋值操作?何时最多?
4. (10分)给定n=4的0-1背包问题:背包承重量为C=10,各物品的相关信息如下表所示。
现考虑使用优先队列式分支限界法求解该问题。搜索结点的上界ub 设置如下:把已经选择的物品总价值(v ),加上背包剩余承重量(C w -)与剩下可选择的物品的最高“价值/重量比”的乘积,即
()
max
()
i i
v w ub v C w =+-。试画出搜索生成树。
5. (10分)给出一个求解二项式系数Cnk 的高效算法,并分析其时间复杂度。
《计算机算法设计与分析》习题及答案
《计算机算法设计与分析》习题及答案 一.选择题 1、二分搜索算法是利用( A )实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是( A )。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是(A )的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是( A )。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5.下列算法中通常以自底向上的方式求解最优解的是(B )。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是( C )。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是( D )。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是(A )。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9.下面不是分支界限法搜索方式的是(D )。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10.下列算法中通常以深度优先方式系统搜索问题解的是(D )。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法
11.备忘录方法是那种算法的变形。( B ) A、分治法 B、动态规划法 C、贪心法 D、回溯法 12.哈夫曼编码的贪心算法所需的计算时间为(B )。 A、O(n2n) B、O(nlogn) C、O(2n) D、O(n) 13.分支限界法解最大团问题时,活结点表的组织形式是(B )。 A、最小堆 B、最大堆 C、栈 D、数组 14.最长公共子序列算法利用的算法是(B)。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15.实现棋盘覆盖算法利用的算法是(A )。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是(C )。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素( D ) A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略(B ) A.递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. (D)是贪心算法与动态规划算法的共同点。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 20. 矩阵连乘问题的算法可由( B )设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法 21. 分支限界法解旅行售货员问题时,活结点表的组织形式是( A )。
算法设计与分析考试题及答案
算法设计与分析考试题及 答案 It was last revised on January 2, 2021
一、填空题(20分) 1.一个算法就是一个有穷规则的集合,其中之规则规定了解决某一特殊类型问题的一系列运算, 此外,算法还应具有以下五个重要特性:确定性有穷性可行性 0个或多个输入一个或多 个输出 2.算法的复杂性有时间复杂性空间复杂性之分,衡量一个算法好坏的标准是时间复杂度高低 3.某一问题可用动态规划算法求解的显着特征是该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D},Y={A,C,B,A,B,D,C,D},请给出序列X和Y的一个最长公共子序列{BABCD}或{CABCD}或{CADCD} 5.用回溯法解问题时,应明确定义问题的解空间,问题的解空间至少应包含一个(最优)解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题,先求解_子问题,然后从这些 子问题的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法 背包问题的回溯算法所需的计算时间为o(n*2n) ,用动态规划算法所需的计算时间为o(min{nc,2n}) 9.动态规划算法的两个基本要素是最优子结构_和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题(50分) 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质;②构造最优值的递归关系表达式;③最优值的算法描述;④构造 最优解; 2.流水作业调度问题的johnson算法的思想。 ①令N 1={i|a i =b i };②将N 1 中作业按a i 的非减序排序得到N 1 ’,将N 2 中作业按b i 的非增序排序得到N 2’;③N 1 ’中作业接N 2 ’中作业就构成了满足Johnson法则的最优调度。 3.若n=4,在机器M1和M2上加工作业i所需的时间分别为a i 和b i ,且 (a 1,a 2 ,a 3 ,a 4 )=(4,5,12,10),(b 1 ,b 2 ,b 3 ,b 4 )=(8,2,15,9)求4个作业的最优调度方案,并计算最优 值。 步骤为:N1={1,3},N2={2,4}; N 1’={1,3}, N 2 ’={4,2}; 最优值为:38 4.使用回溯法解0/1背包问题:n=3,C=9,V={6,10,3},W={3,4,4},其解空间有长度为3的0-1向量组成,要求用一棵完全二叉树表示其解空间(从根出发,左1右0),并画出其解空间树,计算其最优值及最优解。 解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为: 该问题的最优值为:16 最优解为:(1,1,0)
高一数学必修三《算法初步》单元测试题
一、单项选择题(共12小题,每小题5分,共60分) 1. 算法的有穷性是指() A. 算法必须包含输出 B. 算法中每个操作步骤都是可执行的 C. 算法的步骤必须有限 D. 以上说法均不正确 【答案】C 【解析】 试题分析:所谓算法有穷性是指一个算法应包含有限的操作步骤,即在执行有限操作后算法结束,从而可得结论. 解:一个算法必须在有限步内结束,简单的说就是没有死循环 即算法的步骤必须有限 故选C. 点评:本题主要考查了算法的特点,属于基本概念的考查,是容易题. 2.2.算法共有三种逻辑结构,即顺序结构、条件结构、循环结构,下列说法正确的是( ) A. 一个算法只能含有一种逻辑结构 B. 一个算法最多可以包含两种逻辑结构 C. 一个算法必须含有上述三种逻辑结构 D. 一个算法可以含有上述三种逻辑结构的任意组合 【答案】D 【解析】 分析:根据算法中三种逻辑结构的定义,顺序结构是最基本的结构,每个算法一定包含顺序结构,选择结构是算法中出现分类讨论时使用的逻辑结构,循环结构一定包含一个选择结构,从而即可得出答案. 详解:算法有三种逻辑结构, 最基本的是顺序结构, 一个算法一定包含有顺序结构,但是可以含有三种逻辑结构的任意组合. 故选:D. 点睛:本题考查的知识点是算法的概念及算法的特点,是对概念的直接考查,属基础题,熟练掌握相关概念是解答本题的关键.
3.3.下列给出的赋值语句中正确的是() A. B. C. D. 【答案】B 【解析】 【分析】 根据赋值语句定义判断选择. 【详解】赋值语句一般格式是:变量=表达式(或变量),所以选B. 【点睛】赋值语句用符号“=”表示,其一般格式是变量=表达式(或变量),其作用是对程序中的变量赋值; 4.4.程序执行后输出的结果是() A. -1 B. 0 C. 1 D. 2 【答案】B 【解析】 试题分析:开始满足,第一次循环:; 满足,第二次循环:; 满足,第三次循环:; 满足,第四次循环:; 满足,第五次循环:; 此时不满足,结束循环,所以输出n的值为0。
算法初步练习题(附详细答案).doc
算法初步练习题 一、选择题: 1.阅读下面的程序框图,则输出的S = A .14 B .20 C .30 D .55 2.阅读图2所示的程序框图,运行相应的程序,输出的结果是 A .1 B. 2 C. 3 D. 4 3.阅读右图所示的程序框图,运行相应的程序,输出的结果是 A .2 B .4 C .8 D .16 4.某程序框图如图所示,该程序运行后输出的k 的值是 A .4 B .5 C .6 D .7 5.执行右面的程序框图,输出的S 是 3题 2题 1题 4题
A .378- B .378 C .418- D .4186.如图的程序框图表示的算法的功能是 A .计算小于100的奇数的连乘积 B .计算从1开始的连续奇数的连乘积 C .从1开始的连续奇数的连乘积,当乘积大于100时,计算奇数的个数 D .计算100531≥???????n 时的最小的n 值. 7.右图是把二进制数)2(11111化为十进制数的一个程序框图,判断框内应填入的 条件是 A .4i > B .4i ≤ C .5i > D .5i ≤ 8.某程序框图如图所示,则该程序运行后输出的B 等于 A .15 B .29 C .31 D .63 5题 6题
9.如果执行右边的程序框图,输入2,0.5x h =-=,那么输出的各个数的和等于 A .3 B .3.5 C .4 D . 10.某店一个月的收入和支出总共记录了N 个数据1a ,2,,N a a ???,其中 收入记为 正数,支出记为负数。该店用右边的程序框图计算月总收入S 和月 净盈利V ,那么在图中空白的判断框和处理框中,应分别填入下列四个选项中 的 A .0,A V S T >=- B .0,A V S T <=- C .0,A V S T >=+ D .0,A V S T <=+ 11. 如图1所示,是关于闰年的流程,则 以下年份是闰年的为 A .1996年 B .1998年 C .2010年 D .2100年 12. 某流程如右上图所示,现输入如下四个函数,则可以输出的函数是 否 y x = 是 否 开始 0x < 0y = x x h += 是 结束 1x < 输入,x h 否 是 1y = 输出y 2x ≥ 是 开始 1,0,0k S T === i A a = 输出,S V 1k k =+ 否 结束 输入12,,,,N N a a a ??? T T A =+ S S A =+ N k < 是 否 10题 11题 9题
算法设计与分析考试题及答案
算法设计与分析考试题 及答案 Company number:【WTUT-WT88Y-W8BBGB-BWYTT-19998】
一、填空题(20分) 1.一个算法就是一个有穷规则的集合,其中之规则规定了解决某一特殊类型问题的一系列运算,此外,算法还应具有以下五个重要特性:确定性 有穷性 可行性 0个或多个输入 一个或多个输出 2.算法的复杂性有时间复杂性 空间复杂性之分,衡量一个算法好坏的标准是 时间复杂度高低 3.某一问题可用动态规划算法求解的显着特征是 该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D},Y={A,C,B,A,B,D,C,D},请给出序列X 和Y 的一个最长公共子序列{BABCD}或{CABCD}或{CADCD } 5.用回溯法解问题时,应明确定义问题的解空间,问题的解空间至少应包含一个(最优)解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题 ,先求解_子问题 ,然后从这些子问题 的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法 背包问题的回溯算法所需的计算时间为o(n*2n ) ,用动态规划算法所需的计算时间为o(min{nc,2n }) 9.动态规划算法的两个基本要素是最优子结构 _和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题(50分) 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质;②构造最优值的递归关系表达式; ③最优值的算法描述;④构造最优解; 2. 流水作业调度问题的johnson 算法的思想。 ①令N 1={i|a i =b i };②将N 1中作业按a i 的非减序排序得到N 1’,将N 2中作业按b i 的非增序排序得到N 2’;③N 1’中作业接N 2’中作业就构成了满足Johnson 法则的最优调度。 3. 若n=4,在机器M1和M2上加工作业i 所需的时间分别为a i 和b i ,且 (a 1,a 2,a 3,a 4)=(4,5,12,10),(b 1,b 2,b 3,b 4)=(8,2,15,9)求4个作业的最优调度方案,并计算最优值。 步骤为:N1={1,3},N2={2,4}; N 1’={1,3}, N 2’={4,2}; 最优值为:38 4. 使用回溯法解0/1背包问题:n=3,C=9,V={6,10,3},W={3,4,4},其解空间有长度为3的0-1向量组成,要求用一棵完全二叉树表示其解空间(从根出发,左1右0),并画出其解空间树,计算其最优值及最优解。 解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为: 该问题的最优值为:16 最优解为:(1,1,0) 5. 设S={X 1,X 2,···,X n }是严格递增的有序集,利用二叉树的结点来存储S 中的元素,在表示S 的二叉搜索树中搜索一个元素X ,返回的结果有两种情形,(1)在二叉搜索树的内结点中找到X=X i ,其概率为b i 。(2)在二叉搜索树的叶结点中确定X ∈(X i ,X i+1),其概率为a i 。在表示S 的二叉搜索树T 中,设存储元素X i 的结点深度为C i ;叶结点(X i ,X i+1)的结点深度为d i ,则二叉搜索树T 的平均路长p 为多少假设二叉搜索树T[i][j]={X i ,X i+1,···,X j }最优值为m[i][j],W[i][j]= a i-1+b i +···+b j +a j ,则m[i][j](1<=i<=j<=n)递归关系表达式为什么 .二叉树T 的平均路长P=∑=+n i 1 Ci)(1*bi +∑=n j 0 dj *aj
算法设计与分析考试题及答案
1.一个算法就是一个有穷规则的集合,其中之规则规定了解决某一特殊类型问题的一系列运算,此外,算法还应具有以下五个重要特性:_________,________,________,__________,__________。 2.算法的复杂性有_____________和___________之分,衡量一个算法 好坏的标准是______________________。 3.某一问题可用动态规划算法求解的显著特征是 ____________________________________。 4.若序列X={B,C,A,D,B,C,D},Y={A,C,B,A,B,D,C,D},请给出序列X 和Y的一个最长公共子序列_____________________________。 5.用回溯法解问题时,应明确定义问题的解空间,问题的解空间至少应包含___________。 6.动态规划算法的基本思想是将待求解问题分解成若干____________,先求解___________,然后从这些____________的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题(50分) 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。
1.4算法初步单元测试
1.4算法初步单元测试 1.如图所示程序框图,能判断任意输入的数x的奇偶性:其中判断框内的条件是()A.m=0 B.x=0 C.x=1 D.m=1 2.算法的过程称为“数学机械化”,数学机械化的最大优点是可以让计算机来完成,中国当代数学家在这方面研究处于世界领先地位,为此而获得首届自然科学500万大奖的是( ) A.袁隆平B.华罗庚 C.苏步青D.吴文俊 3.算法 S1 m=a S2 若b5.计算机执行下面的程序段后,输出的结果是() A.1,3 B.4,1 C.0,0 D.6,0 6.用“辗转相除法”求得459和357的最大公约数是() A.3 B.9 C.17 D.51 7.算法的三种基本结构是( ) A.顺序结构、模块结构、条件结构 B.顺序结构、循环结构、模块结构 C.顺序结构、条件结构、循环结构 D.模块结构、条件结构、循环结构8.下面为一个求20个数的平均数的程序,在横线上应填充的语句为( ) A.i>20 B.i<20 C.i>=20 D.i<=20 9.用秦九韶算法计算多项式当时的值时,需 要做乘法和加法的次数分别是( ) A.6 , 6 B.5 , 6 C.5 , 5 D.6 , 5 10.给出以下一个算法的程序框图(如图所示),该程序框图的功能是( ) A.求输出a,b,c三数的最大数 B.求输出a,b,c三数的最小数 C.将a,b,c按从小到大排列 D.将a,b,c按从大到小排列
计算机算法试题(含答案)
算法设计与分析试卷 一、填空题(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]=_
高二数学算法初步单元测试题及答案
高二数学算法初步单元 测试题及答案 Last revised by LE LE in 2021
江苏省南通中学高二(上)数学单元测试08。9。25 算法初步(题目) 一 填空题 1.描述算法的方法通常有: (1)自然语言;(2) ▲ ;(3)伪代码. 2.已知流程图符号,写出对应名称. (1) ▲ ;(2) ▲ ;(3) ▲ . 3.下列给出的几个式子中,正确的赋值语句是(填序号) ▲ ①3←A ; ②M ← —M ; ③B ←A ←2 ; ④x+y ←0 4. 用秦九韶算法计算多项式1876543)(23456++++++=x x x x x x x f 当4.0=x 时的值时,至多需要做乘法和加法的次数分别是 ▲ _和 ▲ 5.简单随机抽样,系统抽样的共同特点是 ▲ 。 6.采用系统抽样从含有8000个个体的总体(编号为0000,0001,…,, 7999)中抽取一个容量为50的样本,已知最后一个入样编号是7900,则最前面2个入样编号是 ▲ 7.某校有老师200人,男学生1200人,女学生1000人,现用分层抽样的方法 从所有师生中抽取一个容量为n 的样本,已知从女学生中抽取的人数为80人,则n= ▲ . 8.11.下面是一个算法的伪代码.如果输出的y 的值是20,则输入的x 的值是 ▲ . 2或6 二 填空题 9下面伪代码运行后的输出的结果是(1) ▲ (2) ▲ (3) ▲ Read x If x≤5 Then y←10x Else y←+5 End If Print y
10.( 1) 下面这段伪代码的功能是 ▲ 。 (2) 下列算法输出的结果是(写式子) ▲ (3)下图为一个求20个数的平均数的程序,在横线上应填充的语句为 ▲ 。 11(1)在如图所示的流程图中,输出的结果是 ▲ . (2) 右边的流程图最后输出的n 的值是 ▲ . (3 )下列流程图中,语句1(语句1与i 无关)将被执行的次数为 ▲ . (4)右图给出的是计算1111 2 4 6 100 +++ + 的值的一个流程图,其中判断 框内应填入的条件是 ▲ 。 第9(2) 第10(1)题 第10(2)题 第10(3)题
2018届人教A版算法初步单元测试13
2017-2018学年度xx学校xx月考卷 一、选择题(共15小题,每小题5.0分,共75分) 1.阅读下图所示的程序框图,运行相应的程序,输出的结果是() A. 1 B. 2 C. 3 D. 4 2.如图程序中,输出的是4,则输入的x可以是() A.-8 B. 4
C. 8 D.-16 3.下列关于算法的描述正确的是() A.算法与求解一个问题的方法相同 B.算法只能解决一个问题,不能重复使用 C.算法过程要一步一步执行,每步执行的操作必须确切 D.有的算法执行后,可能无结果 4.早上从起床到出门需要洗脸刷牙(5 min)、刷水壶(2 min)、烧水(8 min)、泡面(3 min)、吃饭(10 min)、听广播(8 min)几个过程.则下列选项中最好的一种算法是() A.第一步,洗脸刷牙.第二步,刷水壶.第三步,烧水.第四步,泡面.第五步,吃饭.第六步,听广播 B.第一步,刷水壶.第二步,烧水同时洗脸刷牙.第三步,泡面.第四步,吃饭.第五步,听广播C.第一步,刷水壶.第二步,烧水同时洗脸刷牙.第三步,泡面.第四步,吃饭同时听广播 D.第一步,吃饭同时听广播.第二步,泡面.第三步,烧水同时洗脸刷牙.第四步,刷水壶 5.下面程序运行的结果是() A. 1,2,-1 B. 1,2,1 C. 1,-2,-1 D. 1,-2,1
6.将下列不同进位制下的数转化为十进制,这些数中最小的数是() A. 20(7) B. 30(5) C. 23(6) D. 31(4) 7.下面的程序运行后,输出的结果为() A. 13,7 B. 7,4 C. 9,7 D. 9,5 8.如图所示,程序的输出结果为S=132,则判断框中应填() A.i≥10? B.i≥11?
高中数学必修三《算法初步》练习题(内含答案)[1]
2、基本算法语句: ①输入语句。输入语句的格式:INPUT “提示内容”;变量 ②输出语句。输出语句的一般格式:PRINT“提示内容”;表达式 ③赋值语句。赋值语句的一般格式:变量=表达式 ④条件语句。 (1)“IF—THEN—ELSE”语句 格式: IF 条件THEN 语句1 ELSE 语句2 END IF ⑤循环语句。 (1)当型循环语句 当型(WHILE型)语句的一般格式为:WHILE 条件 循环体 WEND (2)“IF—THEN”语句 格式: IF 条件THEN 语句 END IF (2)直到型循环语句 直到型(UNTIL型)语句的一般格式为:DO 循环体 LOOP UNTIL 条件
高中数学必修三《算法初步》练习题 一、选择题 1.下面对算法描述正确的一项是 ( ) A .算法只能用伪代码来描述 B .算法只能用流程图来表示 C .同一问题可以有不同的算法 D .同一问题不同的算法会得到不同的结果 2.程序框图中表示计算的是 ( ). A . B C D 3 将两个数 8,17a b ==交换,使17,8a b ==,下面语句正确一组是 ( ) A B C D . 4. 计算机执行下面的程序段后,输出的结果是( ) 1a = 3b = a a b =+ b a b =- PRINT a ,b A .1,3 B .4,1 C .0,0 D .6,0 5.当2=x 时,下面的程序运行后输出的结果是 ( ) A .3 B .7 C .15 D .17 6. 给出以下四个问题: ①输入一个数x , 输出它的相反数 ②求面积为6的正方形的周长 ③输出三个数,,a b c 中的最大数 ④求函数1,0 ()2,0 x x f x x x -≥?=?+
算法设计与分析考试题及答案(1)
一、填空题(20 分) 1. 一个算法就是一个有穷规则的集合,其中之规则规定了解决某一特殊 类型问题的一系列运算,此外,算法还应具有以下五个重要特性: , , , _________ , _______ 。 2. 算法的复杂性有_____________ 和__________ 之分,衡量一个算法 好坏的标准是_______________________ 。 3. 某一问题可用动态规划算法求解的显著特征是 4. 若序列X={B,C,A,D,B,C,D} ,Y={A,C,B,A,B,D,C,D} ,请给出序列X 和Y 的一个最长公共子序列 ____________________________ 。_ 5. 用回溯法解问题时,应明确定义问题的解空间,问题的解空间至少 应包含__________ 。 6. 动态规划算法的基本思想是将待求解问题分解成若干 _______ , 先求解_____ ,然后从这些_____ 的解得到原问题的解。 7. 以深度优先方式系统搜索问题解的算法称为_____________ 。 8.0-1 背包问题的回溯算法所需的计算时间为 _______________ ,用动态 规划算法所需的计算时间为 ____________ 。 9. 动态规划算法的两个基本要素是 ____________ 和_________ 。 10. 二分搜索算法是利用______________ 实现的算法。 二、综合题(50 分) 1. 写出设计动态规划算法的主要步骤。
2. 流水作业调度问题的johnson 算法的思想。 3. 若n=4,在机器M1和M2上加工作业i所需的时间分别为日和b i, 且(a i,a2,a3,a4)=(4,5,12,10) , (b i,b2,b3,b4)=(8,2,15,9) 求 4 个作业 的最优调度方案,并计算最优值。 4. 使用回溯法解0/1 背包问题:n=3,C=9,V={6,10,3} , W={3,4,4}, 其解空间有长度为3 的0-1 向量组成,要求用一棵完全二叉树表示其解空间(从根出发,左 1 右0) ,并画出其解空间树,计算其最优值及最优解。 5. 设S={X i,准…,X n}是严格递增的有序集,利用二叉树的结点 来存储S中的元素,在表示S的二叉搜索树中搜索一个元素X,返回的结果有两种情形,(1)在二叉搜索树的内结点中找到X=X i ,其概率为b i。( 2)在二叉搜索树的叶结点中确定X€( X , X+1),其概率为 a i。在表示S的二叉搜索树T中,设存储元素X的结点深度为C ;叶结点(X , X+1)的结点深度为d i,则二叉搜索树T的平均路长p为多少?假设二叉搜索树T[i][j]= {X , X+i,?…,X}最优值为m[i][j], W[i][j]= a i-1 +b i+ ? ? ? +b+a,贝S m[i][j](1<=i<=j<=n) 递归关系表达式为什么? 6. 描述0-1 背包问题。 三、简答题 ( 30分) 1?流水作业调度中,已知有n个作业,机器M1和M2上加工作业i所需的时间分别为a i 和b i ,请写出流水作业调度问题的johnson 法则中对 a i 和 b i 的排序算法。(函数名可写为sort(s,n) )
计算机算法设计与分析习题及答案
计算机算法设计与分析习 题及答案 Prepared on 24 November 2020
《计算机算法设计与分析》习题及答案 一.选择题 1、二分搜索算法是利用( A )实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是( A )。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是(A )的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是( A )。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5.下列算法中通常以自底向上的方式求解最优解的是(B )。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是( C )。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是( D )。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是(A )。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9.下面不是分支界限法搜索方式的是(D )。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先
10.下列算法中通常以深度优先方式系统搜索问题解的是(D )。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形。( B ) A、分治法 B、动态规划法 C、贪心法 D、回溯法 12.哈夫曼编码的贪心算法所需的计算时间为(B )。 A、O(n2n) B、O(nlogn) C、O(2n) D、O(n) 13.分支限界法解最大团问题时,活结点表的组织形式是(B )。 A、最小堆 B、最大堆 C、栈 D、数组 14.最长公共子序列算法利用的算法是(B)。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15.实现棋盘覆盖算法利用的算法是(A )。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是(C )。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素( D ) A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略(B ) A.递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. (D)是贪心算法与动态规划算法的共同点。
算法设计与分析试卷及答案.doc
湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型:开卷 试卷类型: C 卷 考试时量: 120 分钟 题号 一 二 三 四 五 总分 统分人 得 分 阅卷人 一、填空题(每小题 3 分,共计 30 分) 1. 用 O 、Ω和θ表示函数 f 与 g 之间的关系 ______________________________ 。 f n n lo g n g n log n 1, n 1 2. 算法的时间复杂性为 f (n) n ,则算法的时间复杂性的阶 8 f (3n / 7) n, 2 为__________________________ 。 3. 快速排序算法的性能取决于 ______________________________ 。 4. 算法是 _______________________________________________________ 。 5. 在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的 是_________________________ 。 6. 在算法的三种情况下的复杂性中, 可操作性最好且最有实际价值的是 _____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限,这个下限的阶越 ___________,结果就越有价值。 。 8. ____________________________ 是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指 ________________________________________________________ ____________________________________________________________ 。
算法初步单元测试题
算法初步单元测试题 一、选择题()04410'='? 1、已知直角三角形两直角边长为a ,b ,求斜边长c 的一个算法分下列三步: ①计算22b a c += ②输入直角三角形两直角边长a ,b 的值 ③输出斜边长c 的值 其中正确的顺序是 ( ) A.①②③ B.②③① C.①③② D.②①③ 2、下列给出的输入语句、输出语句和赋值语句 ①输出语句INPUT a ;b ;c ②输入语句INPUT 3=x ③赋值语句B =3 ④赋值语句2==B A 其中正确的个数是 ( ) A.0个 B.1个 C.2个 D.3个 3、某程序框图如图所示,若输入x 的值为1,则输出y 的值是 ( ) A.2 B.3 C.4 D.5 第3题 4、某程序框图如右图所示,若3=x ,则输出y 的值为( ) A.5 B.17 C.19 D.34 5、把二进制数)(21011001化为十进制数是 ( ) A.178 B.89 C.88 D.77 6、阅读下面的程序框图,则输出的=S ( ) A.14 B.20 C.30 D.55 7、某程序框图如图所示,该程序运行后输出的k 的值是 ( ) A.4 B.5 C.6 D.7 8、某程序框图如图所示,则该程序运行后输出的B 等于 ( ) A.15 B.29 C.31 D.63 第4题
第6题 第7题 第8题 9、根据下列算法语句,当输入x 为60时,输出y 的值为 ( ) A.25 B.30 C.31 D.61 第9题 10、某程序框图如图所示,若输出的57=s ,则判断框内的条件为 ( ) A.?>4k B.?>5k C.?>6k D.?>7k 二、填空题()04410'='? 11、将194化成八进制数为 12、下列所给问题: ①求半径为1的圆的面积. ②二分法解方程032=-x . ③解方程组???=+=+10525 y x y x . 其中可以设计算法求解的是 13、给出算法: 第一步,先求41?,得到结果4. 第二步,将第一步所得结果4再乘以7,得到结果28. 第10题
人教A版高中数学必修三练习:第一章算法初步分层训练进阶冲关1.3算法案例Word版含答案
分层训练·进阶冲关 A组基础练(建议用时20分钟) 1.在对16和12求最大公约数时,整个操作如下:16-12=4,12-4=8,8-4=4.由此可以看出12和16的最大公约数是 ( A ) A.4 B.12 C.16 D.8 2.在m=nq+r(0≤r6.用秦九韶算法求n次多项式f(x)=a n x n+a n-1x n-1+…+a1x+a0的值,当 x=x0时,求f(x0)需要算乘方、乘法、加法的次数分别为( C ) A.,n,n B.n,2n,n C.0,n,n D.0,2n,n 7.用更相减损术求36与134的最大公约数时,第一步应为先除以2,得到18与67. 8.用辗转相除法求294和84的最大公约数时,需要做除法的次数是2. 9.三位七进制数表示的最大的十进制数是342. 10.秦九韶是我国南宋时期的数学家,普州(现四川省安岳县)人,他在所著的《数书九章》中提出的多项式求值的秦九韶算法,至今仍是比较先进的算法,如图所示的程序框图给出了利用秦九韶算法求某多项式值的一个实例.若输入n,x的值分别为3,3,则输出v的值为 48. 11.将1234(5)转化为八进制数. 【解析】先将1234(5)转化为十进制数: 1234(5)=1×53+2×52+3×51+4×50=194.
算法考试试题及答案
一、填空题(本题10分,每空1分) 1、算法的复杂性是的度量,是评价算法优劣的重要依据。 2、设n为正整数,利用大“O(·)”记号,将下列程序段的执行时间表示为n的函数,则下面 程序段的时间复杂度为。 i=1; k=0; while(i新课改高中数学数学必修三《算法初步》单元测试[技巧]
数学必修三《算法初步》单元测试 一、选择题 1. 下列关于算法的说法中正确的个数有( ) ①求解某一类问题的算法是唯一的 ②算法必须在有限步操作之后停止 ③算法的每一步操作必须是明确的,不能有歧义或模糊④算法执行后一定产生确定的结果 A. 1 B. 2 C. 3 D. 4 2 ) A. 输出a=10 B. 赋值a=10 C. 判断a=10 D. 输入a=1 3.条件语句的一般形式如右所示,其中B 表示的是( ) A .条件 B .条件语句 C .满足条件时执行的内容 D .不满足条件时执行的内容 4.将两个数a=2, b= -6交换,使 a= -6, b=2,下列语句正确的是( ) A ... 5.用秦九韶算法求多项式()543254321f x x x x x x =+++++, 当2x =时的值的过程中,做的乘法和加法次数分别为( ) A 、4,5 B 、5,4 C 、5,5 D 、6,5 6.x=5 y=6: PRINT x+y=11 END 上面程序运行时输出的结果是( ) A.xy=11 B.11 C.xy=11 D.出错信息 7.图中程序运行后输出的结果为( )(A )3 43 (B ) 43 3 (C )-18 16 (D )16 -18 8.如果下边程序执行后输出的结果是990,那么在程序中UNTIL 后面的“条件”应为( ) A. i>10 B. i<8 C. i<=9 D. i<9 9.阅读下面的流程图,若输入的a 、b 、c 分别是21、32、75,则输出的a 、b 、c 分别是:() A .75、21、32 B .21、32、75C .32、21、75 D .75、32、21 10.给出以下一个算法的程序框图(如图所示),该程序框图的功能是?( )A.求输出a,b,c 三数的最大数 B. 求输出a,b,c 三数的最小数 C.将a,b,c 按从小到大排列 D. 将a,b,c 按从大到小排列
算法初步练习题(附详细答案)好
一、选择题: 1.(2014,5,5分)执行如图的程序框图,如果输入的x,y∈R,那么输出的S的最大值为( ) A.0 B.1 C.2 D.3 2. (2014,6,5分)执行如图所示的程序框图,如果输入的t∈[-2,2],则输出的S 属于( ) A.[-6,-2] B.[-5,-1] C.[-4,5] D.[-3,6] 3.(2014,4,5分)当m=7,n=3时,执行如图所示的程序框图,输出的S值为( ) A.7 B.42 C.210 D.840
4.(2014课标全国卷Ⅱ,7,5分)执行下面的程序框图,如果输入的x,t 均为2,则输出的S=( ) A.4 B.5 C.6 D.7 5.(2014课表全国Ⅰ,7,5分)执行下面的程序框图,若输入的a,b,k 分别为1,2,3,则输出的M=( ) A. B. C. D.
6. (2014高三第一次模拟考试,5) 执行下边的程序框图,则输出的是( ) A. 5040 B. 2450 C. 4850 D. 2550 7. (2014第三中学第一次高考模拟考试,5) 若按下侧算法流程图运行后,输出 的结果是7 6 , 则输入的 的值为( ) A. B. C. D.
8、(2014红色六校高三第二次联考理数试题,4)一算法的程序框图如右图所示,若输出的2 1 =y ,则输入的x 可能为( ) A. B. C. 或 D. 或 1.(09天津文)阅读下面的程序框图,则输出的S = A .14 B .20 C .30 D .55 2.(09)阅读图2所示的程序框图,运行相应的程序,输出的结果是 A .1 B. 2 C. 3 D. 4 开始 11S S = - 2S = 输出n 是 2,1S n == 1n n =+ 否 结束 开始 输出S 0,1S i == 4?i > 1i i += 2S S i =+ 是 结束 否 第8题