下载文档原格式
第九章算法初步、统计与统计案例[深研高考·备考导航]为教师备课、授课提供丰富教学资源[五年考情]考点算法、算法框图、基本算法语句全国卷Ⅰ·T9全国卷Ⅱ·T8全国卷Ⅲ·T7全国卷Ⅰ·T9全国卷Ⅱ·T8全国卷Ⅰ·T7全国卷Ⅱ·T7全国卷Ⅰ·T5全国卷Ⅱ·T6全国卷·T6随机抽样———全国卷Ⅰ·T3—用样本估计总体全国卷Ⅱ·T10全国卷Ⅲ·T4全国卷Ⅱ·T18全国卷Ⅰ·T18全国卷Ⅱ·T19全国卷·T18变量间的相关关系与统计案例全国卷Ⅲ·T18全国卷Ⅰ·T19全国卷Ⅱ·T19——综合近5年全国卷高考试题，我们发现高考命题在本章呈现以下规律：1．从考查题型看：一般有1个客观题，1个解答题；从考查分值看，在17分左右．基础题主要考查对基础知识和基本方法的掌握，中档题主要考查数据的处理能力和综合应用能力．2．从考查知识点看：主要考查算法框图、简单随机抽样、用样本估计总体、变量间的相关关系与统计案例．突出对数形结合思想、转化与化归思想、分类讨论思想以及探究、创新能力的考查．3．从命题思路上看：(1)求算法框图的执行结果．(2)确定选择结构中的条件与循环结构中的循环变量，完善算法框图．(3)随机抽样中的系统抽样与分层抽样．(4)样本的平均数、频率、中位数、众数、方差；频率分布直方图、茎叶图；变量间的相关关系中的线性回归分析及独立性检验的基本思想及其初步应用．[导学心语]1．深刻理解并掌握以下概念算法中三种结构的功能，抽样方法的操作步骤，数字特征的含义及计算，频率分布直方图和茎叶图的画法，回归分析中线性回归方程的含义及求法和独立性检验的基本思想．2．突出重点、控制难度本章命题背景新颖、重点内容突出：如算法框图的执行结果与条件判断、统计图表与样本数字特征等，但题目难度不超过中等程度，复习时注意新材料、新背景的题目，重基础，控制好难度．3．注重交汇，突出统计思想强化统计思想方法的应用，注重知识的交汇渗透，如算法框图与数列、统计与函数、统计图表与概率．复习时善于把握命题新动向，抓住命题的增长点，强化规范性训练，力争不失分、得满分．第一节算法与算法框图[考纲传真] 1.了解算法的含义，了解算法的思想.2.理解算法框图的三种基本逻辑结构：顺序、条件分支、循环.3.理解几种基本算法语句——输入语句、输出语句、赋值语句、条件语句、循环语句的含义．1．算法的含义算法是解决某类问题的一系列步骤或程序，只要按照这些步骤执行，都能使问题得到解决．2．算法框图在算法设计中，算法框图(也叫程序框图)可以准确、清晰、直观地表达解决问题的思想和步骤，算法框图的三种基本结构：顺序结构、选择结构、循环结构．3．三种基本逻辑结构(1)顺序结构：按照步骤依次执行的一个算法，称为具有“顺序结构”的算法，或者称为算法的顺序结构．其结构形式为图911(2)选择结构：需要进行判断，判断的结果决定后面的步骤，像这样的结构通常称作选择结构．其结构形式为图912(3)循环结构：指从某处开始，按照一定条件反复执行某些步骤的情况．反复执行的处理步骤称为循环体．其基本模式为图9134．基本算法语句任何一种程序设计语言中都包含五种基本的算法语句，它们分别是：输入语句、输出语句、赋值语句、条件语句和循环语句．5．赋值语句(1)一般形式：变量＝表达式．(2)作用：将表达式所代表的值赋给变量．6．条件语句(1)If—Then—Else语句的一般格式为：(2)If—Then语句的一般格式是：7．循环语句(1)For语句的一般格式：(2)Do Loop语句的一般格式：1．(思考辨析)判断下列结论的正误．(正确的打“√”，错误的打“×”)(1)算法框图中的图形符号可以由个人来确定．()(2)一个算法框图一定包含顺序结构，但不一定包含选择结构和循环结构．()(3)选择结构的出口有两个，但在执行时，只有一个出口是有效的．()(4)在算法语句中，X＝X＋1是错误的．()[答案](1)×(2)√(3)√(4)×2．(教材改编)根据给出的算法框图，计算f(－1)＋f(2)＝()图914A．0B．1 C．2 D．4A[f(－1)＝4×(－1)＝－4，f(2)＝22＝4，∴f(－1)＋f(2)＝－4＋4＝0.]3．(·贵阳调研)执行如图915所示的算法框图，输出S的值为()图915A．－32B．32C．－12D．12D[按照算法框图依次循环运算，当k＝5时，停止循环，当k＝5时，S＝sin 5π6＝12.]4．(·全国卷Ⅱ)中国古代有计算多项式值的秦九韶算法，如图916是实现该算法的算法框图．执行该算法框图，若输入的x＝2，n＝2，依次输入的a为2,2,5，则输出的s＝()图916A．7B．12C．17D．34C[输入x＝2，n＝2.第一次，a＝2，s＝2，k＝1，不满足k>n；第二次，a＝2，s＝2×2＋2＝6，k＝2，不满足k>n；第三次，a＝5，s＝6×2＋5＝17，k＝3，满足k>n，输出s＝17.]5．执行算法框图917，若输入的x的值为1，则输出的y的值是________.【导学号：57962430】图91713[当x＝1时，1＜2，则x＝1＋1＝2，当x＝2时，不满足x＜2，则y＝3×22＋1＝13.]算法框图的基本结构若输入x 的值为1，则输出y 的值为( )图918A ．2B ．7C ．8D ．128(2)(·北京高考)执行如图919所示的算法框图，若输入的a 值为1，则输出的k 值为( )图919A ．1B ．2C ．3D ．4(1)C (2)B [(1)由算法框图知，y ＝⎩⎨⎧2x ，x ≥2，9－x ，x ＜2.∵输入x 的值为1，比2小，∴执行的程序要实现的功能为9－1＝8，故输出y 的值为8.(2)初始值k＝0，a＝1，b＝1.第一次循环a＝－12，k＝1；第二次循环，a＝－2，k＝2；第三次循环，a＝1，此时a＝b＝1，输出k＝2.][规律方法] 1.(1)利用选择结构解决算法问题时，要根据题目的要求引入一个或多个判断框．(2)判断框内的条件不同，对应的下一图框中的内容和操作要相应地进行变化，故要逐个分析判断框内的条件．2．解决循环结构问题时，要弄清程序中的循环变量，并弄清循环变量和终止条件之间的对应关系，避免出现循环次数与条件不对应的错误．[变式训练1](1)根据如图9110所示算法框图，当输入x为6时，输出的y＝()图9110A．1B．2C．5D．10(2)我国古代数学典籍《九章算术》“盈不足”中有一道两鼠穿墙问题：“今有垣厚十尺，两鼠对穿，初日各一尺，大鼠日自倍，小鼠日自半，问几何日相逢？”现用算法框图描述，如图9111所示，则输出结果n＝()【导学号：57962431】图9111A．4B．5C．2D．3(1)D(2)A[(1)当x＝6时，x＝6－3＝3，此时x＝3≥0；当x＝3时，x＝3－3＝0，此时x＝0≥0；当x＝0时，x＝0－3＝－3，此时x＝－3＜0，则y＝(－3)2＋1＝10.(2)该算法框图运行4次，第1次循环，a＝1，A＝1，S＝2，n＝1；第2次循环，a＝12，A＝2，S＝92，n＝2；第3次循环，a＝14，A＝4，S＝354，n＝3；第4次循环，a＝18，A＝8，S＝1358，n＝4，此时循环结束，则输出的n＝4，故选A.]算法框图的识别与完善(·全国卷Ⅰ)执行下面的算法框图，如果输入的x＝0，y＝1，n＝1，则输出x，y的值满足()图9112 A．y＝2x B．y＝3xC．y＝4x D．y＝5xC[输入x＝0，y＝1，n＝1，运行第一次，x＝0，y＝1，不满足x2＋y2≥36；运行第二次，x＝12，y＝2，不满足x2＋y2≥36；运行第三次，x＝32，y＝6，满足x2＋y2≥36，输出x＝32，y＝6.由于点⎝⎛⎭⎪⎫32，6在直线y＝4x上，故选C.]☞角度2完善算法框图执行如图9113所示的算法框图，若输出k的值为8，则判断框内可填入的条件是()图9113A．s≤34B．s≤56C．s≤1112D．s≤2524C[执行第1次循环，则k＝2，s＝12，满足条件．执行第2次循环，则k＝4，s＝12＋14＝34，满足条件．执行第3次循环，则k＝6，s＝34＋16＝1112，满足条件．执行第4次循环，k＝8，s＝1112＋18＝2524，不满足条件，输出k＝8，因此条件判断框应填s≤11 12.][规律方法] 1.(1)第1题的关键在于理解算法框图的功能；(2)第2题要明确何时进入或退出循环体，以及累加变量的变化．2．解答此类题目：(1)要明确算法框图的顺序结构、选择结构和循环结构；(2)理解算法框图的功能；(3)要按框图中的条件运行程序，按照题目的要求完成解答. 基本算法语句A ．25B ．30C ．31D ．61C [由题知，算法语句是一个分段函数y ＝f (x )＝⎩⎨⎧0.5x ，x ≤50，25＋0.6(x －50)，x ＞50，∴y ＝f (60)＝25＋0.6×(60－50)＝31.][规律方法] 1.本题主要考查条件语句，输入、输出语句与赋值语句，要注意赋值语句一般格式中的“＝”不同于等式中的“＝”，其实质是计算“＝”右边表达式的值，并将该值赋给“＝”左边的变量．2．解决此类问题关键要理解各语句的含义，以及基本算法语句与算法结构的对应关系．[变式训练2] 按照如下程序运行，则输出k 的值是________．3 [第一次循环，x ＝7，k ＝1；第二次循环，x ＝15，k ＝2；第三次循环，x ＝31，k ＝3.终止循环，输出k 的值是3.][思想与方法]1．每个算法结构都含有顺序结构，循环结构中必定包含一个选择结构，用于确定何时终止循环体，循环结构和选择结构都含有顺序结构．2．在画算法框图时首先要进行结构的选择．若所要解决的问题不需要分情况讨论，只用顺序结构就能解决；若所要解决的问题要分若干种情况讨论时，就必须引入选择结构；若所要解决的问题要进行许多重复的步骤，且这些步骤之间又有相同的规律时，就必须应用循环结构．[易错与防范]1．赋值号左边只能是变量(不是表达式)，在一个赋值语句中只能给一个变量赋值．2．注意选择结构与循环结构的联系：循环结构有重复性，选择结构具有选择性没有重复性，并且循环结构中必定包含一个选择结构，用于确定何时终止循环体．。
《算法及其分析》课后选择题答案及详解第1 章——概论1.下列关于算法的说法中正确的有（）。
Ⅰ.求解某一类问题的算法是唯一的Ⅱ.算法必须在有限步操作之后停止Ⅲ.算法的每一步操作必须是明确的，不能有歧义或含义模糊Ⅳ.算法执行后一定产生确定的结果A.1个B.2个C.3个D.4个2.T(n)表示当输入规模为n时的算法效率，以下算法效率最优的是（）。
A.T(n)=T(n-1)+1，T(1)=1B.T(n)=2nC.T(n)= T(n/2)+1，T(1)=1D.T(n)=3nlog2n答案解析：1.答：由于算法具有有穷性、确定性和输出性，因而Ⅱ、Ⅲ、Ⅳ正确，而解决某一类问题的算法不一定是唯一的。
答案为C。
2.答：选项A的时间复杂度为O(n)。
选项B的时间复杂度为O(n)。
选项C 的时间复杂度为O(log2n)。
选项D的时间复杂度为O(nlog2n)。
答案为C。
第3 章─分治法1.分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。
这要求原问题和子问题（）。
A.问题规模相同，问题性质相同B.问题规模相同，问题性质不同C.问题规模不同，问题性质相同D.问题规模不同，问题性质不同2.在寻找n个元素中第k小元素问题中，如快速排序算法思想，运用分治算法对n个元素进行划分，如何选择划分基准？下面（）答案解释最合理。
A.随机选择一个元素作为划分基准B.取子序列的第一个元素作为划分基准C.用中位数的中位数方法寻找划分基准D.以上皆可行。
但不同方法，算法复杂度上界可能不同3.对于下列二分查找算法，以下正确的是（）。
A.intbinarySearch(inta[],intn,int x){intlow=0,high=n-1;while(low<=high){intmid=(low+high)/2;if(x==a[mid])returnmid;if(x>a[mid])low=mid;elsehigh=mid;}return –1;}B.intbinarySearch(inta[],intn,int x) { intlow=0,high=n-1;while(low+1!=high){intmid=(low+high)/2;if(x>=a[mid])low=mid;elsehigh=mid;}if(x==a[low])returnlow;elsereturn –1;}C.intbinarySearch(inta[],intn,intx) { intlow=0,high=n-1;while(low<high-1){intmid=(low+high)/2;if(x<a[mid])high=mid;elselow=mid;}if(x==a[low])returnlow;elsereturn –1;}D.intbinarySearch(inta[],intn,int x) {if(n>0&&x>=a[0]){intlow= 0,high=n-1;while(low<high){intmid=(low+high+1)/2;if(x<a[mid])high=mid-1;elselow=mid;}if(x==a[low])returnlow;}return –1;}答案解析：1.答：C。
第九章查找：习题习题一、选择题1．散列表查找中k个关键字具有同一散列值，若用线性探测法将这k个关键字对应的记录存入散列表中，至少要进行( )次探测。
A. k B。
k+l C. k(k+l）／2 D. l+k （k+l)/22．下述命题( )是不成立的。
A。
m阶B-树中的每一个结点的子树个数都小于或等于mB。
m阶B-树中的每一个结点的子树个数都大于或等于『m/2-1C。
m阶B-树中的每一个结点的子树高度都相等D。
m阶B—树具有k个子树的非叶子结点含有(k-l）个关键字3．如果要求一个基本线性表既能较快地查找，又能适应动态变化的要求，可以采用( ）查找方法.A。
分块 B. 顺序 C. 二分 D.散列4．设有100个元素，用折半查找法进行查找时，最大比较次数是( ),最小比较次数是( ）.A。
7，1 B.6，l C.5，1 D. 8，15．散列表长m=15，散列表函数H(key）=key％13。
表中已有4个结点：addr（18)=5；addr(32）=6; addr(59)=7；addr(73)=8;其余地址为空，如果用二次探测再散列处理冲突，关键字为109的结点的地址是( )。
A. 8 B。
3 C. 5 D。
46．用分块查找时，若线性表中共有729个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分( )个结点最佳。
A。
15 B. 27 C。
25 D。
307．散列函数有一个共同性质，即函数值应当以( )取其值域的每个值。
A.同等概率B。
最大概率C。
最小概率D。
平均概率8．设散列地址空间为O.。
m—1，k为关键字，假定散列函数为h(k)=k％p，为了减少冲突，一般应取p为( )。
A.小于m的最大奇数B. 小于m的最大素数C.小于m的最大偶数D.小于m的最大合数9．当向一棵m阶的B-树做插入操作时，若使一个结点中的关键字个数等于( )，则必须分裂成两个结点。
A。
m B。
m-l C.m+l D。
第9课体验算法控制教学设计一、引言在当今信息时代，计算机科学和编程教育受到越来越多的重视。
而作为计算机科学中基础且重要的一环，算法控制更是备受瞩目。
本文将围绕第9课体验算法控制这一教学设计主题展开深入探讨，旨在为读者提供一些有益的思考和启发。
二、算法控制的概念解析算法控制是计算机科学中的一个重要概念，它指的是通过编程语言对计算机进行指令控制，使之按照预定的算法执行特定的任务。
在教学中，体验算法控制旨在让学生了解并掌握如何利用代码编写算法，实现对计算机的控制和指导。
三、深度和广度分析1. 算法控制的基本原理在教学中，需要首先向学生介绍算法控制的基本原理，包括顺序执行、条件执行和循环执行等概念。
通过实际案例和代码演示，让学生深入理解这些基本原理，并能够灵活运用于实际编程中。
2. 不同编程语言的算法控制应用在教学设计中，可以引导学生了解和比较不同编程语言在算法控制上的应用。
Python、Java和C语言等，它们在算法控制方面的特点和应用场景各有不同，通过比较分析可以帮助学生更全面地理解算法控制的本质。
3. 算法控制在实际问题中的应用通过实际问题的案例分析，可以帮助学生将算法控制理论与实际应用相结合。
通过模拟生活中的问题情境，教学设计可以让学生编写代码实现解决问题的算法控制，从而培养他们的实际应用能力和创新思维。
4. 算法控制的发展趋势和挑战教学设计还可涉及到算法控制的发展趋势和未来挑战。
随着人工智能、大数据等新技术的发展，算法控制所面临的挑战和应对策略也将成为教学的一部分，帮助学生更好地把握行业动态。
四、总结与展望通过对第9课体验算法控制这一教学设计主题的深度和广度分析，我们不仅将理论知识传授给学生，更重要的是培养他们的逻辑思维、创新能力和问题解决能力。
我们也应该关注教学设计的创新和改进，结合学生的实际情况和学习特点，不断完善教学内容和方法。
希望学生们能够在体验算法控制的过程中，感受到计算机科学的魅力，并为未来的发展奠定坚实的基础。
