下载文档原格式
2016-2017学年高中数学专题1.5 算法案例练习（含解析）新人教A版必修3编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（2016-2017学年高中数学专题1.5 算法案例练习（含解析）新人教A版必修3）的内容能够给您的工作和学习带来便利。
同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。
本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快业绩进步，以下为2016-2017学年高中数学专题1.5 算法案例练习（含解析）新人教A版必修3的全部内容。
12 1。
5 算法案例一、选择题1．用更相减损术求1 515和600的最大公约数时，需要做减法次数是( ）A ．15B ．14C ．13D ．12【解析】 1 515－600＝915，915－600＝315，600－315＝285，315－285＝30,285－30＝255，255－30＝225，225－30＝195，195－30＝165，165－30＝135，135－30＝105，105－30＝75，75－30＝45，45－30＝15,30－15＝15．∴1 515与600的最大公约数是15．则共做14次减法．【答案】 B2.用更相减损术可求得78与36的最大公约数是…( ）A.24B.18 C 。
12 D 。
63.下列四个数中,数值最小的是（ )A ．25(10）B ．54（4）C ．10 110(2)D ．10 111（2)【解析】 统一成十进制，B 中54(4)＝5×41＋4＝24，C 中10 110(2)＝1×24＋1×22＋2＝22，D 中，10 111（2)＝23．【答案】 C4.用秦九韶算法求多项式 a x a x a x f n n +++=-11)(时，求)( x f 需要算乘方、乘法、 加法的次数分别为（ ）A 。
算法分类题库及答案详解1. 算法按其设计方法可以分为哪几类？A. 暴力解法B. 贪心算法C. 分治算法D. 动态规划E. 所有以上答案：E2. 以下哪个算法不属于贪心算法？A. 活动选择问题B. 最小生成树C. 快速排序D. 霍夫曼编码答案：C3. 分治算法的基本思想是什么？A. 将问题分解成更小的子问题B. 直接求解问题C. 选择最优子问题D. 迭代求解答案：A4. 动态规划与分治算法的主要区别是什么？A. 动态规划需要存储中间结果B. 分治算法需要存储中间结果C. 动态规划不需要分解问题D. 分治算法不需要分解问题答案：A5. 暴力解法通常用于什么问题？A. 问题规模较小B. 问题规模较大C. 需要最优解D. 需要近似解答案：A6. 以下哪个算法是使用贪心算法解决的？A. 汉诺塔问题B. 旅行商问题C. 背包问题D. 八皇后问题答案：C7. 快速排序算法属于哪种算法类别？A. 暴力解法B. 贪心算法C. 分治算法D. 动态规划答案：C8. 动态规划通常用于解决什么问题？A. 线性问题B. 组合问题C. 排序问题D. 查找问题答案：B9. 以下哪个问题可以通过贪心算法得到最优解？A. 旅行商问题B. 背包问题C. 0/1背包问题D. 所有以上答案：B10. 汉诺塔问题通常使用什么算法解决？A. 暴力解法B. 贪心算法C. 分治算法D. 动态规划答案：C11. 以下哪个算法是动态规划算法的典型应用？A. 斐波那契数列B. 最长公共子序列C. 最短路径问题D. 所有以上答案：D12. 贪心算法在哪些情况下可能无法得到最优解？A. 问题具有最优子结构B. 问题不具有最优子结构C. 问题具有重叠子问题D. 问题不具有重叠子问题答案：B13. 动态规划算法的一般步骤是什么？A. 确定状态B. 确定状态转移方程C. 确定边界条件D. 所有以上答案：D14. 分治算法的一般步骤包括哪些？A. 分解问题B. 解决子问题C. 合并子问题的解D. 所有以上答案：D15. 以下哪个算法不是排序算法？A. 冒泡排序B. 选择排序C. 快速排序D. 霍夫曼编码答案：D16. 快速排序算法的时间复杂度在最坏情况下是多少？A. O(n log n)B. O(n^2)C. O(n)D. O(1)答案：B17. 动态规划算法在解决什么问题时会使用记忆化搜索？A. 线性问题B. 组合问题C. 排序问题D. 查找问题答案：B18. 贪心算法在选择策略时通常遵循什么原则？A. 选择当前最优B. 选择全局最优C. 选择随机D. 选择平均最优答案：A19. 以下哪个问题不适合使用贪心算法？A. 单源最短路径问题B. 旅行商问题C. 背包问题D. 霍夫曼编码答案：B20. 分治算法在解决哪些问题时特别有效？A. 线性问题B. 组合问题C. 排序问题D. 查找问题答案：B。
算法习题算法设计与分析试卷⼀、填空题（20分，每空2分）1、算法的性质包括输⼊、输出、确定性、有限性。
2、动态规划算法的基本思想就将待求问题分解成若⼲个⼦问题、先求解⼦问题，然后从这些⼦问题的解得到原问题的解。
3、设计动态规划算法的4个步骤：（1）找出最优解的性质，并刻画其结构特征。
（2）递归地定义最优值。
（3）以⾃底向上的⽅式计算出最优值。
（4）根据计算最优值得到的信息，构造最优解。
4、流⽔作业调度问题的johnson算法：（1）令N1={i|ai=bj};（2）将N1中作业依ai的ai的⾮减序排序；将N2中作业依bi的⾮增序排序。
5、对于流⽔作业⾼度问题，必存在⼀个最优调度π，使得作业π（i）和π（i+1）满⾜Johnson不等式min{bπ(i),aπ(i+1)}≥min{bπ(i+1),aπ(i)}。
6、最优⼆叉搜索树即是最⼩平均查找长度的⼆叉搜索树。
⼆、综合题（50分）1、当（a1,a2,a3,a4,a5,a6）=(-2,11,-4,13,-5,-2)时，最⼤⼦段和为∑ak(2<=k<=4)=20（5分）2、由流⽔作业调度问题的最优⼦结构性质可知，T（N，0）=min{ai+T(N-{i},bi)}(1=3、最⼤⼦段和问题的简单算法(10分)int maxsum(int n,int *a,int & bestj){Int sum=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++)this sum+=a[k];if(thissum>sum){sum=thissum;besti=i；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]= 0;}for(int r=0;rfor(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]= m[i+1][j];s[i][j]=i;for(int k=i+1;k<=j;k++){int t=m[i][k-1]+m[k+1][j];if(t}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分）法⼀：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}N11＝{1，3，4} N12＝{2}所以N11→N12得：1→3→4→2三、简答题（30分）1、将所给定序列a[1:n]分为长度相等的两段a[1:n/2]和a[n/2+1:n]，分别求出这两段的最⼤⼦段和，则a[1:n]的最⼤⼦段和有哪三种情形？(10分)答：（1）a[1:n]的最⼤⼦段和与a[1:n/2]的最⼤⼦段和相同。
题1运行下面的程序时，WHILE循环语句的执行次数是（）A.3B.4C.15D.19题2执行下面的程序框图，输出的S＝()A．25 B．9C．17 D．20题3阅读如下图所示的程序框图，则运行后输出的结果是________．如果执行如图所示的程序框图，输入n＝6，m＝4，那么输出的p等于()A．720 B．360C．240 D．120题5执行下面的程序语句，输入a＝3，b＝－1，n＝4后，输出的结果是________．a ＝input a ＝；b ＝input b＝；n ＝input n ＝；i ＝1；while i <＝nc ＝a ＋b ； a ＝b ；b ＝c ；i ＝i ＋1；endprint io ，c ；题6若a =11时,下面的程序段输出的结果是______.题7读如下两个程序，完成下列题目：程序（1）:程序（2）:（1）程序（1）的运行结果为_________.（2）若程序（1），（2）运行结果相同，则程序（2）输入的值为_________.题8用秦九韶算法计算多项式f（x）=1+5x+10x2+10x3+5x4+x5在x= 2时，v3的值为（）A.1B.2C.3D.4课后练习详解题1答案：B详解：0＜20,1＜20,2×2＜20,3×3<20,4×4<20,5×5＞20,程序结束.故WHILE循环语句共执行了4次，所以选B.题2答案：C详解：由结构框图中循环体执行了2次输出的结果为17.题3答案：－3详解：依次执行的是S＝1，i＝2；S＝－1，i＝3；S＝2，i＝4；S＝－2，i＝5；S＝3，i＝6；S＝－3，i＝7，此时满足i＞6，故输出的结果是－3.题4答案：B详解：由框图可知：当n＝6，m＝4时，第一次循环：p＝(6－4＋1)×1＝3，k＝2.第二次循环：p＝(6－4＋2)×3＝12，k＝3.第三次循环：p＝(6－4＋3)×12＝60，k＝4.第四次循环：p＝(6－4＋4)×60＝360，此时k＝m，终止循环．输出p＝360，故选B.题5答案：4详解：循环体被执行了4次，第一次执行循环体得的结果是：c＝2，a＝－1，b＝2，i＝2；执行第二次的结果是：c＝1，a＝2，b＝1，i＝3；执行第三次的结果是：c＝3，a＝1，b＝3，i ＝4；执行第四次的结果是：c＝4，a＝3，b＝4，i＝5，此时c的值输出．题6答案：1详解：由于当a=11时,不满足条件a<10,所以执行y=a MOD 10,得到的结果是y=1.注意“a MOD 10”是a除以10的余数.题7答案：（1）6 （2）0详解：赋值语句给变量赋值时，变量的值总是最后一次所赋的值，故程序（1）中x的值最后为6．要使程序（2）中y的值为6,即x2+6=6，故x=0.即输入的x的值为0.题8答案：B详解：f（x）=1+5x+10x2+10x3+5x4+x5=（x4+5x3+10x2+10x+5）x+1=（（x3+5x2+10x+10）x+5）x+1=（（（（x+5）x+10）x+10）x+5）x+1∴在x= 2时，v3的值为（（x+5）x+10）x+10=2，故选B.。
算法设计与分析常见习题及详解⽆论在以后找⼯作还是⾯试中，都离不开算法设计与分析。
本博⽂总结了相关算法设计的题⽬，旨在帮助加深对贪⼼算法、动态规划、回溯等算法的理解。
1、计算下述算法执⾏的加法次数：输⼊：n =2^t //t 为整数输出：加法次数 k K =0while n >=1 do for j =1 to n do k := k +1 n = n /2return k解析：第⼀次循环执⾏n次加法，第⼆次循环执⾏1/2次加法，第三次循环执⾏1/次加法…因此，上述算法执⾏加法的次数为==2n-12、考虑下⾯每对函数 f(n) 和 g(n) ，如果它们的阶相等则使⽤Θ记号，否则使⽤ O 记号表⽰它们的关系解析：前导知识：，因为解析：，因为解析:，因为解析：解析:3、在表1.1中填⼊ true 或 false解析：利⽤上题的前导知识就可以得出。
2=21/4n +n +21n +41...+1n +n −n +21n −21n +41....−1f (n )=(n −2n )/2，g (n )=6n1<logn <n <nlogn <n <2n <32<n n !<n ng (n )=O (f (n ))f (n )=Θ(n ),g (n )=2Θ(n )f (n )=n +2,g (n )=n n 2f (n )=O (g (n ))f (n )=Θ(n ),g (n )=Θ(n )2f (n )=n +nlogn ,g (n )=n nf (n )=O (g (n ))f (n )=Θ(nlogn ),g (n )=Θ(n )23f (n )=2(log ),g (n )=n 2logn +1g (n )=O (f (n ))f (n )=log (n !),g (n )=n 1.05f (n )=O (g (n ))4、对于下⾯每个函数 f(n),⽤f(n) =Θ(g(n))的形式，其中g(n)要尽可能简洁，然后按阶递增序排列它们（最后⼀列）解析：最后⼀个⽤到了调和公式：按阶递增的顺序排列：、、、、、、、、、(n −2)!=Θ((n −2)!)5log (n +100)=10Θ(logn )2=2n Θ(4)n 0.001n +43n +31=Θ(n )4(lnn )=2Θ(ln n )2+3n logn =Θ()3n 3=n Θ(3)n log (n !)=Θ(nlogn )log (n )=n +1Θ(nlogn )1++21....+=n1Θ(logn )=∑k =1nk 1logn +O (1)1++21....+n 15log (n +100)10(lnn )2+3n logn log (n !)log (n )n +10.001n +43n +313n 22n (n −2)!5、求解递推⽅程前导知识：主定理前导知识：递归树：例⼦：递归树是⼀棵节点带权的⼆叉树，初始递归树只有⼀个结点，标记为权重W(n)，然后不断进⾏迭代，最后直到树种不再含有权为函数的结点为⽌，然后将树根结点到树叶节点的全部权值加起来，即为算法的复杂度。
一、选择题（每小题3分，共15分）1．算法与程序的主要区别在于算法具有（）。
A．能行性 B．确定性 C．有限性 D．输入和输出答案：C。
2．对一个有序序列，以比较为基础的搜索算法的最坏情况时间复杂性的下界为（）。
A．Ω(n) B．Ω(n2) C.Ω(n log n) D．Ω(log n)答案：D。
3．背包问题：n=6，C=10，V(1:6)=(15,59,21,30,60,5)，W(1:6)=(1,5,2,3,6,1）。
该问题的最大价值为（）。
A．101 B．110 C．115 D．120答案：C。
4．矩阵连乘积问题：M1(5×10), M2(10×4), M3(4×6)。
矩阵链乘M1M2M3需要的最少乘法次数为（）。
A．348 B．328 C．720 D．320答案：D。
5．用贪心策略设计算法的关键是（）。
A．将问题分解为多个子问题来分别处理 B．选好贪心策略C．获取各阶段间的递推关系式 D．满足最优性原理答案：B。
二、填空题（每小题4分，共20分）1．某算法的计算时间T(n)满足递归关系式：T(n)=2T(n-1)+O(1)，n>1；T(1)=1。
则T(n)= 。
答案：2n-1。
2．用方法对状态空间树进行搜索时，每个结点有可能多次成为扩展结点。
3．子集和数问题一般陈述如下：已知n+1个正数：w i(1≤i≤n)和M，要求找出w i的和数是M 的所有子集。
其解可以表示为n-元组(x1, x2,⋯, x n)，这里x i∈{0,1}，1≤i≤n。
如果没有选择w i，则相应的x i=0；如果选择了w i，则x i=1。
此解空间的空间树上有个叶结点，共有个结点。
答案：2n,2n+1-1。
4．已知将两个分别包含n个和m个记录的已分类文件归并在一起得到一个分类文件需作n+m 次记录移动。
现有五个已分类文件F1,F2,F3,F4,F5，它们的记录个数分别为25,40,15,10,40，将这五个文件归并成一个分类文件需作次记录移动。
黄宇《算法设计与分析》课后习题解析（⼆）第2章：从算法的视⾓重新审视数学的概念2.1：(向下取整)题⽬：请计算满⾜下⾯两个条件的实数的区间解析：根据向下取整的含义，令，讨论a的取值范围即可解答：令，则可得：即：故的取值区间为：2.2: (取整函数)题⽬：证明：对于任意整数,（提⽰：将n划分为）。
解析：根据提⽰将n进⾏划分，根据取整函数的定义⽤k表⽰取整函数，即可证明；证明如下：因为对于任意整数,可划分为，则:① ；② ；综上：对于任意整数,, 得证；2.3: (斐波拉契数列)对于斐波拉契数列，请证明：1）题⽬：是偶数当且仅当n能被3整除解析：由斐波拉契数列的递归定义式，容易联想到数学归纳法；证明如下：（采⽤数学归纳法）i)当n = 1,2,3时，依次为1，1，2，符合命题；ii)假设当（k>=1）时命题均成⽴，则：① 当n = 3k+1时，是奇数，成⽴；② 当n = 3k+2时，是奇数，成⽴；③ 当 n = 3(k+1)时，是偶数，成⽴；综上：归纳可得为偶数当且仅当，得证;2）题⽬：x x =1+a (0<a <1)x =1+a (0<a <1)⌊x ⌋=1⇒⌊x ⌋=21⌊x ⌋=2⌊1+a +22a ⌋=1a +22a <1⇒0<a <−21⇒1<a +1<⇒21<x <2x (1，)2n ≥1⌈log (n +1)⌉=⌊logn ⌋+12≤k n ≤2−k +11n ≥12≤k n ≤2−k +11k +1=⌈log (2+k 1)⌉≤⌈log (n +1)⌉≤⌈log (2)⌉=k +1k +1=>⌈log (n +1)⌉=k +1k =⌊log (2)⌋≤k ⌊logn ⌋≤⌊log (2−k +11)⌋=k =>⌊logn ⌋=k n ≥1⌈log (n +1)⌉=k +1=⌊logn ⌋+1F n F n n ≤3k F =n F +n −1F =n −2F +3k F =3k −1>F 3k +1F =n F +3k +1F =3k >F 3k +2F =n F +3k +2F =3k +1>F 3k +3F n 3∣n F −n 2F F =n +1n −1(−1)n +1解析：同1）理，容易联想到数学归纳法证明如下：（采⽤数学归纳法）i)当n = 2时，, 易知成⽴；ii)假设当 n = k 时命题成⽴，① 若k = 2m, 则,当n = k+1 = 2m+1时，要证命题成⽴，即证： => ,代⼊递推式, 得：, 易知是恒等式，故命题成⽴；②当 k=2m+1时，同①理可证命题成⽴；综上：归纳可得，得证；2.4：(完美⼆叉树)给定⼀棵完美⼆叉树，记其节点数为，⾼度为，叶节点数为，内部节点数为1）题⽬：给定上述4个量中的任意⼀个，请推导出其他3个量解析：根据完美⼆叉树的结构特点易得解答：（仅以已知⾼度h推导其他三个量为例，其余同理）已知⾼度为h，可得：节点数：叶节点数：内部节点数：2）题⽬：请计算完美⼆叉树任意⼀层的节点个数：① 如果任意指定深度为的⼀层节点，请计算该层节点个数；② 如果任意指定⾼度为的⼀层节点，请计算该层节点个数；解析：根据完美⼆叉树的结构特点易得（注意节点深度和节点⾼度是互补的，相加为树⾼）解答：① ; ② ;2.5: (⼆叉树的性质)对于⼀棵⾮空的⼆叉树T，记其中叶节点的个数为，有1个⼦节点的节点个数为，有两个⼦节点的节点个数为1）题⽬：如果T是⼀棵2-tree，请证明。
Hanoi双塔问题(递推法)【问题描述】给定A,B,C三根足够长的细柱，在A柱上放有2n个中间有空的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的(下图为n=3的情形）。
现要将这些国盘移到C柱上，在移动过程中可放在B柱上暂存。
要求:(1)每次只能移动一个圆盘；(2)A、B、C三根细柱上的圆盘都要保持上小下大的顺序；任务:设A n为2n个圆盘完成上述任务所需的最少移动次数，对于输入的n，输出A n。
【输入】输入为一个正整数n，表示在A柱上放有2n个圆盘。
【输出】输出仅一行，包含一个正整数，为完成上述任务所需的最少移动次数A n。
【输入样例】12【输出样例】26火力网(递归法)【问题描述】假设我们有一个有n条横向街道和n条竖向街道的正方形城市，其中的街道都是笔直的。
并且在某些街道上造有碉堡或墙（图中方形黑块是墙，园形黑块是碉堡）。
每个碉堡对四面街道都开有射击孔。
而每个碉堡都可以被另一个处在同一条街道上且没有墙阻挡的碉堡摧毁，但墙是不能被摧毁的。
你的任务是在一个给定的城市地图上布置尽可能多碉堡，使碉堡之间是不能互相摧毁的。
【输入】第一行包含一个整数n，接下来的n行包含此城市的地图，‘.’表示空的街道，‘X’表示此处有堵墙。
【输出】对给出的地图输出所能布置的碉堡的最多数。
【输入样例】4.X......XX......【输出样例】5高精度计算(应用数组来记录位数非常多的数)用程序实现下列高精度运算一、高精度数与高精度数的加法二、高精度数与高精度数的减法三、高精度数与普通数的乘法四、高精度数与高精度数的乘法五、高精度数与普通数的除法六、根据下面圆周率π的级数展开形式以及上面的高精度计算法，求出π的值（精确到小数点后1000位）π=2+2×13+2×13×25+2×13×25×37+···活动选择(贪心法)【问题描述】假设有n个活动在学校的大礼堂里举行，每个活动有一个开始时间b i和结束时间e i （b i≤e i）。
第4讲算法初步【基础知识】一、算法的概念（1）算法概念：在数学上，现代意义上的“算法”通常是指可以用计算机来解决的某一类问题是程序或步骤，这些程序或步骤必须是明确和有效的，而且能够在有限步之内完成.（2）算法的特点:①有限性：一个算法的步骤序列是有限的，必须在有限操作之后停止，不能是无限的.②确定性：算法中的每一步应该是确定的并且能有效地执行且得到确定的结果，而不应当是模棱两可.③顺序性与正确性：算法从初始步骤开始，分为若干明确的步骤，每一个步骤只能有一个确定的后继步骤，前一步是后一步的前提，只有执行完前一步才能进行下一步，且每一步都准确无误，才能完成问题.④不唯一性：求解某一个问题的解法不一定是唯一的，对于一个问题可以有不同的算法.⑤普遍性：很多具体的问题，都可以设计合理的算法去解决，如心算、计算器计算都要经过有限、事先设计好的步骤加以解决.二、程序框图（1）程序框图基本概念：①程序构图的概念：程序框图又称流程图，是一种用规定的图形、指向线及文字说明来准确、直观地表示算法的图形。
一个程序框图包括以下几部分：表示相应操作的程序框；带箭头的流程线；程序框外必要文字说明。
②构成程序框的图形符号及其作用三、基本算法语句1、输入、输出语句和赋值语句（1）输入语句①输入语句的一般格式INPUT “提示内容”；变量②输入语句的作用是实现算法的输入信息功能；③“提示内容”提示用户输入什么样的信息，变量是指程序在运行时其值是可以变化的量；④输入语句要求输入的值只能是具体的常数，不能是函数、变量或表达式；⑤提示内容与变量之间用分号“；”隔开，若输入多个变量，变量与变量之间用逗号“，”隔开。
（2）输出语句①输出语句的一般格式PRINT “提示内容”；变量②输出语句的作用是实现算法的输出结果功能；③“提示内容”提示用户输入什么样的信息，表达式是指程序要输出的数据；④输出语句可以输出常量、变量或表达式的值以及字符。
（3）赋值语句①赋值语句的一般格式变量=表达式②赋值语句的作用是将表达式所代表的值赋给变量；③赋值语句中的“＝”称作赋值号，与数学中的等号的意义是不同的。
算法题库及答案高中生1. 二分查找算法- 问题描述：在一个已排序的数组中，使用二分查找算法找出一个特定元素的位置。
- 算法步骤：- 确定数组的中间位置。
- 比较中间元素与目标值。
- 如果目标值等于中间元素，则查找成功。
- 如果目标值小于中间元素，则在左半部分继续查找。
- 如果目标值大于中间元素，则在右半部分继续查找。
- 重复以上步骤，直到找到目标值或搜索范围为空。
- 答案：二分查找的时间复杂度为O(log n)，适用于已排序的数组。
2. 快速排序算法- 问题描述：快速排序是一种分治算法，用于对数组进行排序。
- 算法步骤：- 选择一个元素作为“基准”。
- 重新排列数组，使得所有比基准小的元素都在基准的左边，所有比基准大的元素都在基准的右边。
- 递归地将上述步骤应用于基准左边和右边的子数组。
- 答案：快速排序的平均时间复杂度为O(n log n)，但在最坏情况下为O(n^2)。
3. 归并排序算法- 问题描述：归并排序是一种分治算法，用于对数组进行排序。
- 算法步骤：- 将数组分成两半，直到每个子数组只有一个元素。
- 将两个有序的子数组合并成一个有序数组。
- 重复以上步骤，直到整个数组有序。
- 答案：归并排序的时间复杂度为O(n log n)，并且是稳定的排序算法。
4. 深度优先搜索（DFS）- 问题描述：在图或树中，深度优先搜索用于遍历所有节点。
- 算法步骤：- 从根节点开始，沿着一个分支尽可能深地搜索。
- 当无法继续深入时，回溯并沿着其他分支继续搜索。
- 答案：DFS可以用于解决路径搜索问题，如迷宫求解或图的连通性问题。
5. 广度优先搜索（BFS）- 问题描述：在图或树中，广度优先搜索用于遍历所有节点。
- 算法步骤：- 从根节点开始，逐层遍历所有节点。
- 使用队列来保持访问顺序。
- 答案：BFS常用于寻找最短路径或解决最短路径问题。
6. 动态规划算法- 问题描述：动态规划是一种解决复杂问题的方法，通常用于求解优化问题。
一、选择题1、二分搜索算法是利用（ A ）实现的算法。
A、分治策略B、动态规划法C、贪心法D、回溯法2、下列不是动态规划算法基本步骤的是（ A ）。
A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解3、最大效益优先是（ A ）的一搜索方式。
A、分支界限法B、动态规划法C、贪心法D、回溯法4、在下列算法中有时找不到问题解的是（ B ）。
A、蒙特卡罗算法B、拉斯维加斯算法C、舍伍德算法D、数值概率算法5. 回溯法解旅行售货员问题时的解空间树是（ A ）。
A、子集树B、排列树C、深度优先生成树D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。
A、备忘录法B、动态规划法C、贪心法D、回溯法7、衡量一个算法好坏的标准是（ C ）。
A 运行速度快B 占用空间少C 时间复杂度低D 代码短8、以下不可以使用分治法求解的是（ D ）。
A 棋盘覆盖问题B 选择问题C 归并排序D 0/1背包问题9. 实现循环赛日程表利用的算法是（ A ）。
A、分治策略B、动态规划法C、贪心法D、回溯法10、下列随机算法中运行时有时候成功有时候失败的是（ C ）A 数值概率算法B 舍伍德算法C 拉斯维加斯算法D 蒙特卡罗算法11．下面不是分支界限法搜索方式的是（ D ）。
A、广度优先B、最小耗费优先C、最大效益优先D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。
A、备忘录法B、动态规划法C、贪心法D、回溯法13.备忘录方法是那种算法的变形。
（ B ）A、分治法B、动态规划法C、贪心法D、回溯法14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。
A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）15．分支限界法解最大团问题时，活结点表的组织形式是（ B ）。
A、最小堆B、最大堆C、栈D、数组16．最长公共子序列算法利用的算法是（ B ）。
A、分支界限法B、动态规划法C、贪心法D、回溯法17．实现棋盘覆盖算法利用的算法是（ A ）。
可编辑修改精选全文完整版3.2.1算法（2）-粤教版（2019）高中信息技术必修一练习学校:___________姓名：___________班级：___________考号：___________一、选择题1．某算法的部分流程图如第7题图所示。
执行这部分流程后，输出s和i的值分别是（）A．-3 5B．-4 5C．-3 6D．-2 6【答案】A【解析】【分析】【详解】本题考查流程图。
Int(X)求不大于X 的最大整数，Int(s/10)=-3，故本题选A。
2．某算法的部分流程图如图所示，执行这部分流程后，变量s的值是（）A．26B．30C．14D．10【答案】C【解析】【详解】本题考查流程图。
最终可得s=14，故本题选C。
试卷第2页，总15页3．以下哪个是算法的描述方法？（）A．流程图描述法B．枚举法C．顺序法D．列表法【答案】A【解析】【详解】本题考查算法相关知识。
算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。
也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。
如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。
不同的算法可能用不同的时间、空间或效率来完成同样的任务。
一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
算法的描述有流程图，自然语言和计算机语言。
故本题选A。
4．关于算法的描述，下列选项中正确的是（）A．算法本身就是一种程序设计语言B．算法必须有输入C．算法的步骤可以是无穷的D．算法的每一步骤必须有确切的含义【答案】D【解析】【详解】本题考查的是算法相关知识。
所谓算法就是解题方法的精确描述，由有限个步骤组成，故选项A错误；有0 个或多个输入，故选项B错误；算法的步骤是有穷的，故选项C错误；算法具有确定性，指算法的每一步骤必须有确切的含义，故选项D正确。
5．以下不属于算法基本特征的是（）A．可执行性B．确定性C．有穷性D．无限性【答案】D【解析】【详解】本题考查的是算法的特征。
算法练习题及答案一、排序算法1. 冒泡排序冒泡排序是一种简单但效率较低的排序算法。
它的基本思想是，重复地走访待排序的元素，依次比较相邻的两个元素，如果顺序错误就交换它们，直到整个序列有序。
实现代码如下：```pythondef bubble_sort(arr):n = len(arr)for i in range(n):for j in range(0, n-i-1):if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j]return arr```2. 快速排序快速排序是一种常用且高效的排序算法。
它的基本思想是通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的小，然后再按此方法对这两部分数据分别进行快速排序，整个过程递归进行，直到序列有序。
实现代码如下：```pythondef quick_sort(arr):if len(arr) <= 1:return arrpivot = arr[0]left = [x for x in arr[1:] if x < pivot]right = [x for x in arr[1:] if x >= pivot]return quick_sort(left) + [pivot] + quick_sort(right)```二、查找算法1. 二分查找二分查找是一种针对有序数据集合的查找算法。
它的基本思想是，在有序数据集合中，取中间元素与目标元素进行比较，如果相等则查找成功；如果不相等，则根据比较结果，选择继续在前半部分或后半部分查找，以此类推，直到找到目标元素或确定目标元素不存在。
实现代码如下：def binary_search(arr, target):low, high = 0, len(arr) - 1while low <= high:mid = (low + high) // 2if arr[mid] == target:return midelif arr[mid] < target:low = mid + 1else:high = mid - 1return -1```2. 插值查找插值查找是一种自适应的查找算法，适用于数据分布比较均匀的有序数据集合。
2-34、Gray码是一个长度为2n的序列。
序列中无相同元素。
每个元素都是长度为n位的串。
相邻元素恰好只有一位不同。
用分治策略设计一个算法对任意的n构造相应的Gray码。
答：设序列中元素由0、1组成。
当n=1 时Gray码的序列有2个元素（21=2），分别为：0，| 1当n=2 时Gray码的序列有4个元素（22=4），分别为：00，10，| 11，01当n=3 时Gray码的序列有8个元素（23=8），分别为：000，100，110，010，| 011，111，101，001当n=4 时Gray码的序列有16个元素（24=16），分别为：0000，1000、1100、0100，0110，1110，1010，0010，| 0011，1011，1111，0111，0101，1101，1001，0001从上面的列举可得如下规律：n=k时，Gray码的序列有2k个元素，分别为：n=k-1时的Gray码元素正向后加0，得前2k-1个元素，反向后加1的后2k-1个元素。
如n=2时Gray码序列的4个元素分别为：00，10，11，01当n=3 时Gray码序列的前4个元素（23=8），分别为：000，100，110，010是n=2时Gray码四个元素正向后加0，即：000，100，110，010Gray码序列的后4个元素（23=8），分别为：011，111，101，001 是n=2时Gray码四个元素反向后加1，n=2时Gray即：011，111，101，001可以看出，Gray码可以用分治策略，递归实现，2n的Gray码可以用2n-1的Gray码构成。
算法描述：void Gray( type a[],int n){ char a[];if (n==1) { a[0]=’0’;a[1]=’1’;}if (n>1){ Gray(a[],n-1);int k=2n-1-1; //Gray码的个数，因为数组下标从0开始int i=k;for (int x=k;x>=0;x--){char y=a[x];a[x]=y+’0’;a[i+1]=y+’1’; i++;}}}3-7 给定由n个英文单词组成的一段文章，……答：设由n 个单词组成的一段文章可以表示为A[1:n]，它的“漂亮打印”方案记为B[1:n]，构成该最优解的最小空格数（最优值）记为m[1][n]（1）分析最优解的结构：A[1:n]的最优解B[1:n]，必然在第k个单词处断开，那么A[1:k]是“漂亮打印”，并且A[k+1:n]也是“漂亮打印”。
与算法有关1． 已知数列{a n }的各项均为正数，观察程序框图，若10,5==k k 时，分别有2110115==S S 和 （1）试求数列{a n }的通项；（2）令m a nb b b b n +++=...,221求的值.解：由框图可知 分，则有是等差数列，设公差为分3.............................................................).........11(11}{2........................................................1.. (111)113221-++-=+++=k k k k n k k a a d a a d a a a a a a a S分4................................................................).........11(1)11....1111(11113221---=-++-+-=∴k k k a a d a a a a a a d S （1）由题意可知，k=5时，211010;115===S k S时， 分故分舍去或问得分9...............................................12)1(8.........................................).........(21215 (2110))11(1115)11(111111161-=-+=⎩⎨⎧-=-=⎩⎨⎧==⎪⎪⎩⎪⎪⎨⎧=-=-∴n d n a a d a d a a a d a a d n （3）由（2）可得：1222-==n an n b分分12..............................................................).........14(3241)41(210................................2...22...123121-=--=+++=+++∴-m m m m b b b2． 根据如图所示的程序框图，将输出的x 、y 值依次分别记为;,,,,,200721x x x x n y 1，y 2，…，y n ，…，y 2007。
1．计算236312222+++++，写出算法的程序.解：s=1n=2i=1WHILE i＜=63s=s+n∧ii=i+1WENDPRINT “1+2+2∧2+2∧3+…+2∧63=”；sEND2．写出已知函数⎪⎩⎪⎨⎧<-=>=).(1),(),(1xxxy输入x的值，求y的值程序.解：INPUT “请输入x的值：”；xIF x>0 THENy=1ELSEIF x=0 THENy=0ELSEy=－1END IFEND IFPRINT “y的值为：”；yEND3．新课标B版数学必修3教材41页第7题：用100元钱买100只鸡，公鸡每只5元，母鸡每只3元，小鸡3只一元，问能买多少公鸡，母鸡和小鸡？程序如下：for x=1:20 for y=1:33 z=100-x-y; if 5*x+3*y+z/3<>100else x y z end end end4．（本小题满分14分）根据下面的要求，求满足1＋2＋3＋…＋n > 500的最小的自然数n。
（1）画出执行该问题的程序框图；（2）以下是解决该问题的一个程序，但有几处错误，请找出错误并予以更正。
解：（1（2）①DO应改为WHILE; 10分②PRINT n+1 应改为PRINT n ； 12分 ③S=1应改为S=0 14分5. 儿童乘坐火车时，若身高不超过1.1 m ，则不需买票；若身高超过1.1 m 但不超过1.4 m ，则需买半票；若身高超过1.4 m ，则需买全票.试设计一个买票的算法，并画出相应的程序框图及程序。
解：程序是：INPUT “请输入身高h （米）：”；hIF h<=1.1 THEN PRINT “免票” ELSEIF h<=1.4 THEN PRINT “买半票” ELSE PRINT “买全票” END IF END IF END6．意大利数学家菲波拉契,在1202年出版的一书里提出了这样的一个问题:一对兔子饲养到第二个月进入成年,第三个月生一对小兔,以后每个月生一对小兔,所生小兔能全部存活并且也是第二个月成年,第三个月生一对小兔,以后每月生一对小兔.问这样下去到年底应有多少对兔子? 试画出解决此问题的程序框图,并编写相应的程序.解: 分析: 根据题意可知,第一个月有1对小兔,第二个月有1对成年兔子,第三个月有两对兔子,从第三个月开始,每个月的兔子对数是前面两个月兔子对数的和,设第N 个月有两F 对兔子,第N －1个月有S 对兔子,第N －2个月有Q 对兔子,则有F=S+Q,一个月后,即第N+1个月时,式中变量S 的新值应变第N 个月兔子的对数(F 的旧值),变量Q 的新值应变为第N －1个月兔子的对数(S 的旧值),这样,用S+Q 求出变量F 的新值就是N+1个月兔子的数,依此类推,可以得到一个数序列,数序列的第12项就是年底应有兔子对数,我们可以先确定前两个月的兔子对数均为1,以此为基准,构造一个循环程序,让表示“第×个月的I 从3逐次增加1,一直变化到12,最后一次循环得到的F ”就是7．设计算法求100991431311211⨯++⨯+⨯+⨯ 的值。
要求画出程序框图，写出用基本语句编写的程序。
解：这是一个累加求和问题，共99项相加，可设计一个计数变量，一个累加变量，用循环结构实现这一算法。
程序框图如图所示：10==k SDO1))1(/(1+=+*+=k k k k S SLOOP UNTIL 99>kPRINTSEND8．求100以内的所有勾股数。
for i=1:100 for j=1:100 for k=2:100 if i*i+j*j<>k*k else i j k end end end end9. 计算 236312222+++++ ，写出算法的程序. 解：s=1n=2 i=1WHILE i ＜=63 s=s+n ∧i i=i+1 WENDPRINT “1+2+2∧2+2∧3+…+2∧63=”；s END10. 写出已知函数⎪⎩⎪⎨⎧<-=>=).0(1),0(0),0(1x x x y 输入x 的值，求y 的值程序. 解：INPUT “请输入x 的值：”；xIF x>0 THEN y=1 ELSEIF x=0 THEN y=0 ELSE y=－1 END IF END IFPRINT “y 的值为：”；y END11. 2000年我国人口为13亿，如果人口每年的自然增长率为7‟，那么多少年 后我国人口将达到15亿？设计一个算法的程序. 解：A=13R=0.007 i=1 DOA=A*（1+R ） i=i+1LOOP UNTIL A ＞=15 i=i －1PRINT “达到或超过15亿人口需要的年数为：”；i END12．1982年我国大陆人口10亿3千万，编程上机计算，若人口增长率r=1％，则哪一年我国人口增长到12亿，若r=O ．5％，r=O ．2％又是何年?INPUT r=O ．01 i=O p=10.3 y=1982 WHILE P ≤12 i=i+1 p=p※(1+ r) y=y+1 WEND PRINT y ，p END13．假定在银行中存款10000元，按11．25％的利率，一年后连本带息将变为11125元，若将此款继续存人银行，试问多长时间就会连本带利翻一番?请用直到型和当型两种语句写出程序． 用直到型INPUT“money =”，10000 x=mOney r=11.25／100 y=OWHILE x≥2r y=y+1 x=x+r*x WEND PRINT y END 用当型 INPUT m=10000 X=m y=Or=11.25／100 Do m<2*x y=y+1x=x + r*x算法语句常见错误解析夏 文 凯人教版必修3第一章《算法初步》是新课程标准中的新增内容，是高考考查的内容。
程序的设计是本章的一个难点和重点，此难点主要体现在语句的选择、语句的使用、语句的衔接三方面。
如果概念不清、运用不当就容易出错，哪怕一个极细小的错误都会导致整个程序无法被计算机运行而宣告失败，所以，我们在设计程序时，一定要时时小心，处处留意，确保准确无误。
为帮助同学们防错、识错、纠错，笔者搜集了教学中一些常见的错误，望同学们加深对它们的理解，引以为戒。
一 输入语句常见错误解析例 判断下列给出的输入语句是否正确，为什么，怎样改正？（1）INPUT a ; b ; c (2) INPUT x = 2 解：（1）错误，变量之间应该用“，”隔开，应改为：INPUT a ，b ，c 备注：输入语句的一般格式是如果是输入一个变量，一般可以写成 INPUT “x=”;x 也可以简写为INPUT x ，如果是两个变量，一般可以写为也可以简写为INPUT a, b 变量中间要用“，”分隔，三个或三个以上的变量以此类推。
（2）错误，输入语句又称“键盘输入语句”，在程序运行过程中，停机等候用户由键盘输入数据，而不需要在写程序时指定，所以INPUT 后面只能是变量，不能是表达式，应改为：INPUT “请输入x 的值”;x 或INPUT x二输出语句常见错误解析例判断下列给出的输出语句是否正确，为什么，怎样改正？(1)PRINT A=3 （2）解：（1）错误，输出语句的格式为PRINT 语句不能用赋值号“=”，应改为：PRINT A（2）错误，输出语句可以输出多个表达式，不同的表达式之间用“，”分隔，不能用“；”分隔。
所以应改为：PRINT A ，B三 赋值语句常见错误解析例 判断下列给出的赋值语句是否正确，为什么，怎样改正？ (1) 3=A (2)x+y+z=0 (3)A=B=4解：(1) 错误，赋值语句的一般格式是 ， 赋值号的左边只能是变量，右边是一个常数或表达式，所以应改为：A=3(2) 错误，赋值语句不能给表达式赋值。
（3例 某同学编了一个交换两个变量A 和B 的值的程序（图一） 解：按照此程序运行,如果输入3，9输出的结果不是 A=B 表示把变量B 的值9赋给变量A, A 的初始值3被“覆盖”， A 的值变为9，变量B 的值保持不变；B=A 表示把刚才变量A 的值9变量B 的值被 “覆盖”，变为9 ，所以最后输出的是 量赋多个不同的值，但是变量的取值总是取最近被赋予的值），所以要交换两个变量的值，必须引如一个 中间变量x,暂时存放变量A 的值，并把其传递给变量B ，所以中间应改为：。
INPUT “a=”;a INPUT “b=”;b（图一）例：编写一个程序，对于函数⎪⎩⎪⎨⎧>+=<+-=)0(1)0(0)0(1x x x x x y 输入x 的值，输出相应的函数的值。
某同学编写了一个程序（图二），正确吗？如果不对，错在哪里？为什么？解析：条件语句的格式有两种，一个是只有一个“分支”的条件语句，它的格式见图三，一个是有两个“分支”的条件语句，它的一般格式见图四，这个同学编写的程序实际上两次运用了两个分支的条件语句，但是第一个条件语句实际上并不完整，少了一个END IF ，所以应在PRINT y 前加一个END IF.例：闰年是指年份能被4整除但是不能被100整除，或者能被400整除的年份，编写一个程序，判断输入的年份是否为闰年。
错解：依题意设计的程序如下：解析：本题是教材上的一道习题，这个错解是教师教学用书给出的答案，错误的原因在于，本程序有两套条件语句，当我们输入一个年份后，要被执行两次判断，结果会输出两次，对有些年份会输出两个相反的结果。
如：输入年份2008，按照第一套条件语句，2008是闰年，但是按照第二套条件语句，2008不是闰年。
正解：依题意设计的程序如图六。
备注：本程序把三个判断的条件集中在一起，对输入的年份只判断一次，便见分晓，有效地避免了错解中自相矛盾的现象，同时本解法还将错解中的赋值语句省略，集中到条件语句中说明是一个十分简捷程序。
（图二） （图三） （图四）（图六）例：分别用WHILE 型语句和UNTIL 型语句设计一个求100131211+⋅⋅⋅+++的值的程序。
错解：设计程序如下：错解分析：在WHILE 型程序里面i=1、sum=1，控制循环的条件为i ≤100，按此算法最后得到的结果应为1001312111+⋅⋅⋅++++，而不是题目要求的100131211+⋅⋅⋅+++，改正的方法是将sum=1改为sum=0；在UNTIL 型程序里面i=1、sum=0，控制条件为100≥i ，按此算法最后得到的结果是99131211+⋅⋅⋅+++，而不是题目要求的100131211+⋅⋅⋅+++，改正的方法是将100≥i 改为100>i 。
