算法练习题-分章节-带答案
算法练习题---算法概述
一、选择题
1、下面关于算法的描述，正确的是（）
A、一个算法只能有一个输入
B、算法只能用框图来表示
C、一个算法的执行步骤可以是无限的
D、一个完整的算法，不管用什么方法来表示，都至少有一个输出结果
2、一位爱好程序设计的同学，想通过程序设计解决“韩信点兵”的问题，他制定的如下工作过程中，更恰当的是（）
A、设计算法，编写程序，提出问题，运行程序，得到答案
B、分析问题，编写程序，设计算法，运行程序，得到答案
C、分析问题，设计算法，编写程序，运行程序，得到答案
D、设计算法，提出问题，编写程序，运行程序，得到答案
3、下面说法正确的是（）
A、算法+数据结构=程序
B、算法就是程序
C、数据结构就是程序
D、算法包括数据结构
4、衡量一个算法好坏的标准是（）。
A、运行速度快
B、占用空间少
C、时间复杂度低
D、代码短
5、解决一个问题通常有多种方法。若说一个算法“有效”是指( )。
A、这个算法能在一定的时间和空间资源限制内将问题解决
B、这个算法能在人的反应时间内将问题解决
C、这个算法比其他已知算法都更快地将问题解决
D、A和C
6、算法分析中，记号O表示（），记号Ω表示（）。
A.渐进下界
B.渐进上界
C.非紧上界
D.非紧下界
7、以下关于渐进记号的性质是正确的有：（）
A.f(n)(g(n)),g(n)(h(n))f(n)(h(n))
=Θ=Θ?=Θ
B.f(n)O(g(n)),g(n)O(h(n))h(n)O(f(n))
==?=
C. O(f(n))+O(g(n)) = O(min{f(n),g(n)})
D.f(n)O(g(n))g(n)O(f(n))
=?=
8、记号O的定义正确的是（）。
A. O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤f(n) ≤cg(n) }；
B. O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤cg(n) ≤f(n) }；
C. O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n≥n0有0 ≤f(n) D. O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n≥n0有：0 ≤cg(n) < f(n) }； 9、记号Ω的定义正确的是（）。 A. O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤f(n) ≤cg(n) }； B．O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤cg(n) ≤f(n) }； C．O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n≥n0有： 0 ≤f(n) D．O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n≥n0有： 0 ≤cg(n) < f(n) }； 二、填空题 1、算法的性质包括输入、输出、、、有限性。 4、算法的复杂性是的度量，是评价算法优劣的重要依据。 6、计算机的资源最重要的是时间和空间资源。因而，算法的复杂性有和之分。 7、算法复杂度依赖于三方面：、和算法本身。 8、程序是用某种程序设计语言的具体实现。 9、算法是指解决问题的或步骤的描述。 11、计算一个算法时间复杂度通常可以计算、或计算步。16、任何可用计算机求解的问题所需的时间都与其有关。 算法练习题---递归与分治策略 一、选择题 10、Hanoi塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为：（） 11、二分搜索算法是利用（ ）实现的算法。 A 、分治策略 B 、动态规划法 C 、贪心法 D 、回溯法 12、以下不可以使用分治法求解的是（） 。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 13、实现循环赛日程表利用的算法是（ ）。 A 、分治策略 B 、动态规划法 C 、贪心法 D 、回溯法 14、实现棋盘覆盖算法利用的算法是（ ）。 A 、分治法 B 、动态规划法 C 、贪心法 D 、回溯法 15、Strassen 矩阵乘法是利用（ ）实现的算法。 A 、分治策略 B 、动态规划法 C 、贪心法 D 、回溯法 16、使用分治法求解不需要满足的条件是（）。 A 子问题必须是一样的 B 子问题不能够重复 C 子问题的解可以合并 D 原问题和子问题使用相同的方法解 17、实现合并排序利用的算法是（ ）。 A 、分治策略 B 、动态规划法 C 、贪心法 D 、回溯法 18、实现大整数的乘法是利用的算法（ ）。 A 、贪心法 B 、动态规划法 C 、分治策略 D 、回溯法 二、填空题 5、分治法的基本思想是将一个规模为n 的问题分解为k 个规模较小的子问题，这些子问题互相 且与原问题相同。 10、从分治法的一般设计模式可以看出，用它设计出的程序一般是 。 14、快速排序算法是基于 的一种排序算法。 17、快速排序算法的性能取决于 三、简答题 3、分治法所能解决的问题一般具有的几个特征是： 答：（1）该问题的规模缩小到一定的程度就可以容易地解决； （2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质; （3）利用该问题分解出的子问题的解可以合并为该问题的解； （4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 4、分治法与动态规划法的异同。 答：相同点：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 不同点：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。而用分治法求解的问题，经分解得到的子问题往往是互相独立的。 8、老板有一袋金块（共n块，n是2的幂（n>=2）），最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重的金块。 答：n≤2 ，识别出最重和最轻的金块，一次比较就足够了。 n＞2， 第一步，把这袋金块平分成两个小袋A和B。 第二步，分别找出在A和B中最重和最轻的金块。设A中最重和最轻的金块分别为HA与LA，以此类推，B中最重和最轻的金块分别为HB和LB。 第三步，通过比较HA和HB，可以找到所有金块中最重的；通过比较LA和LB，可以找到所有金块中最轻的。在第二步中，若n＞2，则递归地应用分而治之方法。 9、Tom很顽皮。一天，他把假币投到储钱罐里。之后，他担心爸爸揍它，想从N个钱币里找出那个假币。他知道假币的重量比其他钱币轻，但不知道如何找到它，于是禁不住哭了。也许你能帮他。请描述一个通过使用天平找到假币的算法，并分析你算法的运行时间。 11、对下面的递归算法，写出调用f(4)的执行结果。 void f(int k) { if(k>0) { printf("%d\n ",k); f(k-1); f(k-1); } } 四、算法填空 5.快速排序 void QuickSort (int a[], int p, int r) { if (p { int q=Partition(a,p,r); ; //对左半段排序 ; //对右半段排序 } } 6.排列问题 void perm(int list[], int k, int m ) { //产生[list[k:m]的所有排列 if() { //只剩下一个元素 for (int i=0;i<=m;i++) cout< cout< } else //还有多个元素待排列，递归产生排列 for () { swap(list[k]，list[i]); ; swap(list[k],list[i]); } } 五、算法题 1. 给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x，返回其在数组中的位置，如果未找到返回-1。写出二分搜索的算法，并分析其时间复杂度。template intBinarySearch(Type a[], const Type& x, int n) {//在a[0:n]中搜索x，找到x时返回其在数组中的位置，否则返回-1 Int left=0; int right=n-1; While (left<=right) {int middle=(left+right)/2; if (x==a[middle]) return middle; if (x>a[middle]) left=middle+1; else right=middle-1; } Return -1; } 时间复杂性为O(logn) 2. 利用分治算法写出合并排序的算法，并分析其时间复杂度 voidMergeSort(Type a[], int left, int right) { if (left { int i=(left+right)/2; //取中点 mergeSort(a, left, i); mergeSort(a, i+1, right); merge(a, b, left, i, right); //合并到数组b copy(a, b, left, right); //复制回数组a } } 算法在最坏情况下的时间复杂度为O(nlogn)。 算法练习题---动态规划 一、选择题 19、下列不是动态规划算法基本步骤的是（）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 20、最长公共子序列算法利用的算法是（）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 21、动态规划算法的基本要素为（） A. 最优子结构性质与贪心选择性质B．重叠子问题性质与贪心选择性质C．最优子结构性质与重叠子问题性质 D. 预排序与递归调用 22、矩阵连乘问题的算法可由（）设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D.分治法 23、下列算法中通常以自底向上的方式求解最优解的是（）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 24、应用Johnson法则的流水作业调度采用的算法是（） A. 贪心算法 B. 分支限界法 C.分治法 D. 动态规划算法 25、下列不是动态规划算法基本步骤的是（）。题目不好 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 二、填空题 2、动态规划算法的基本思想就将待求问题、先求解子问题，然后从这些子问题的解得到原问题的解。 3、设计动态规划算法的4个步骤：（1）＿，并刻画其结构特征。 （2）。（3）。（4）根据计算最优值得到的信息，。 12、解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是，需要排序的是，。 18、下面程序段的所需要的计算时间为。 intMaxSum(int n, int *a, int&besti, int&bestj) { int sum=0; for(int i=1;i<=n;i++) { intthissum=0; for(int j=i;j<=n;j++) {thissum+=a[j]; if(thissum>sum) { sum=thissum;besti=i; bestj=j;} } } return sum; } 21、所谓最优子结构性质是指。 三、简答题 1、请叙述动态规划算法与贪心算法的异同。 答：共同点：都需要最优子结构性质， 不同点： （1）动态规划：每一步作一个选择—依赖于子问题的解。 贪心方法：每一步作一个选择—不依赖于子问题的解。 （2）动态规划方法的条件：子问题的重叠性质。 贪心方法的条件：最优子结构性质；贪心选择性质。 （3）动态规划：自底向上求解； 贪心方法：自顶向下求解。 2、设计动态规划算法的主要步骤为： 答：（1）找出最优解的性质，并刻划其结构特征。（2）递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造最优解。 4、分治法与动态规划法的异同。 答：相同点：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 不同点：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。而用分治法求解的问题，经分解得到的子问题往往是互相独立的。 四、算法填空 2.最大子段和: 动态规划算法 intMaxSum(int n, int a[]) { int sum=0, b=0； //sum存储当前最大的b[j], b存储b[j] for(int j=1； j<=n； j++) { if (b>0) b+= a[j] ； else； //一旦某个区段和为负，则从下一个位置累和 if(b>sum) sum=b; } return sum； } 算法练习题---贪心算法 一、选择题 26、能采用贪心算法求最优解的问题，一般具有的重要性质为：（） A. 最优子结构性质与贪心选择性质B．重叠子问题性质与贪心选择性质 C．最优子结构性质与重叠子问题性质 D. 预排序与递归调用 27、贪心算法与动态规划算法的共同点是（）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 28、贪心算法与动态规划算法的主要区别是（）。 A、最优子结构 B、贪心选择性质 C、构造最优解 D、定义最优解 29、哈弗曼编码的贪心算法所需的计算时间为（）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 30、下面是贪心算法的基本要素的是（）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 31、下面问题（B）不能使用贪心法解决。 A 单源最短路径问题 B N 皇后问题 C 最小花费生成树问题 D 背包问题 32、背包问题的贪心算法所需的计算时间为（ ） A 、O （n2n ） B 、O （nlogn ） C 、O （2n ） D 、O （n ） 45、下列算法中不能解决0/1背包问题的是（） A 贪心法 B 动态规划 C 回溯法 D 分支限界法 二、填空题 19、有11个待安排的活动，它们具有下表所示的开始时间与结束时间，如果以贪心算法求解 这些活动的最优安排（即为活动安排问题：在所给的活动集合中选出最大的相容活动子集合），得到的最大相容活动子集合为活动。 20、所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。 21、所谓最优子结构性质是指问题的最优解包含了其子问题的最优解。 四、算法填空 1.背包问题的贪心算法 void Knapsack(intn,floatM,float v[],float w[],float x[]) { Sort(n,v,w); int i;float c=M; for (i=1;i<=n;i++) x[i]=0; for (i=1;i<=n;i++) {if (w[i]>c) break; x[i]=1; ; } ; } 3.贪心算法求装载问题 14 13 12 11 10 9 8 7 6 5 4 f[i] 12 2 8 8 6 5 3 5 0 3 1 S[i] 11 10 9 8 7 6 5 4 3 2 1 i void Loading(int x[], int w[], int c, int n) { int *t = new int [n+1]; ; for (int i = 1; i <= n; i++) x[i] = 0; for (int i = 1; i <= n && w[t[i]] <= c; i++) {x[t[i]] = 1; ; } } 4.贪心算法求活动安排问题 template void GreedySelector(int n, Type s[], Type f[], bool A[]) { ; int j=1; for (int i=2;i<=n;i++) {if (s[i]>=f[j]) { ;; } else A[i]=false; } } 五、算法题 5、试用贪心算法求解下列问题：将正整数n分解为若干个互不相同的自然数之和，使这些自然数的乘积最大。 voiddicomp(intn,int a[]) { k=1; if(n<3) { a[1]=0; return; } if(n<5) { a[k]=1; a[++k]=n-1; return;} a[1]=2; n-=2; while(n>a[k]) { k++; a[k]=a[k-1]+1; n-=a[k]; } if(n==a[k]) { a[k]++; n--;} for(int i=0;i } 算法练习题—回溯法 一、选择题 33、回溯法在问题的解空间树中，按（）策略，从根结点出发搜索解空间树。 A.广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先 34、下面哪种函数是回溯法中为避免无效搜索采取的策略（） A．递归函数 B.剪枝函数C。随机数函数 D.搜索函数 35、回溯法的效率不依赖于以下哪一个因素？（） A. 产生x[k]的时间； B.满足显式约束的x[k]值的个数； C. 问题的解空间的形式； D.计算上界函数bound的时间； 36、回溯法的效率不依赖于下列哪些因素（） A.满足显约束的值的个数 B. 计算约束函数的时间 C. 计算限界函数的时间 D. 确定解空间的时间 37、下列算法中通常以深度优先方式系统搜索问题解的是（）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 38、回溯法搜索状态空间树是按照（）的顺序。 A 中序遍历 B 广度优先遍历 C 深度优先遍历 D 层次优先遍历 39、程序块（）是回溯法中遍历排列树的算法框架程序。 二、填空题 12、解决0/1 背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是，需要排序的是，。 13、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是，只使用约束条件进行裁剪的是。 15、回溯法是一种既带有又带有的搜索算法。 22、回溯法是指。 23、用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为。 24、回溯法的算法框架按照问题的解空间一般分为算法框架与算法框架。 25、用回溯法解0/1背包问题时，该问题的解空间结构为结构。 26、用回溯法解批处理作业调度问题时，该问题的解空间结构为结构。 27、旅行售货员问题的解空间树是。 28、用回溯法解图的m着色问题时，使用下面的函数OK检查当前扩展结点的每一个儿子所相应的颜色的可用性，则需耗时（渐进时间上限）。 Bool Color::OK(int k) { for(int j=1;j<=n;j++) if((a[k][j]= =1)&&(x[j]= =x[k])) return false; return true; } 三、简答题 5、分支限界法与回溯法的异同 答：相同点：都是一种在问题的解空间树T中搜索问题解的算法。 不同点：（1）求解目标不同；（2）搜索方式不同； （3）对扩展结点的扩展方式不同；（4）存储空间的要求不同。 四、算法填空 10.用回溯法解0/1背包问题时，计算结点的上界的函数如下所示，请在空格中填入合适的内容：Typep Knap { Typew cleft = c - cw; // 剩余容量 Typep b = cp; // 结点的上界 // 以物品单位重量价值递减序装入物品 while (i <= n && w[i] <= cleft) {; ; ; } // 装满背包 if (i <= n) return b; } 五、算法题 3.N皇后回溯法 bool Queen::Place(int k) //检查x[k]位置是否合法 { for (int j=1;j if ((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) return false; return true; } void Queen::Backtrack(int t) { if (t>n) sum++; else for (int i=1;i<=n;i++) { x[t]=i; if ( 约束函数 ) Backtrack(t+1); } } 4. 请写出用回溯法解装载问题的函数。 装载问题：有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i 的重量为wi，且 12 1 n i i w c c = ≤+ ∑ 。装载问题要求确定是否有一个合理的装载方案可将这n个 集装箱装上这2艘轮船。如果有，找出一种装载方案。void backtrack (int i)// 搜索第i层结点 {if (i > n) // 到达叶结点 if(cw>bestw) //更新最优解bestx,bestw;return; { for(j=1;j<=n;j++) bestx[j]=x[j]; Bestw=cw; } r -= w[i]; if (cw + w[i] <= c) // 搜索左子树 {x[i] = 1; cw += w[i]; backtrack(i + 1); cw -= w[i]; } if (cw + r >bestw) // 搜索右子树 { x[i] = 0; backtrack(i + 1); } r += w[i]; } 算法练习题---分支限界法 一、选择题 40、常见的两种分支限界法为（） A. 广度优先分支限界法与深度优先分支限界法； B. 队列式（FIFO）分支限界法与堆栈式分支限界法； C. 排列树法与子集树法； D. 队列式（FIFO）分支限界法与优先队列式分支限界法； 41、分支限界法在问题的解空间树中，按（）策略，从根结点出发搜索解空间树。 A．广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先 42、下面不是分支界限法搜索方式的是（）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 43、分支限界法解旅行售货员问题时，活结点表的组织形式是（）。 A、最小堆 B、最大堆 C、栈 D、数组 44、优先队列式分支限界法选取扩展结点的原则是（）。 A、先进先出 B、后进先出 C、结点的优先级 D、随机 45、下列算法中不能解决0/1背包问题的是（） A 贪心法 B 动态规划 C 回溯法 D 分支限界法 二、填空题 12、解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是，需要排序的是，。 三、简答题 5、分支限界法与回溯法的异同 答：相同点：都是一种在问题的解空间树T中搜索问题解的算法。 不同点：（1）求解目标不同；（2）搜索方式不同； （3）对扩展结点的扩展方式不同；（4）存储空间的要求不同。 6、用分支限界法设计算法的步骤是： 答：(1)针对所给问题，定义问题的解空间（对解进行编码）；分 (2)确定易于搜索的解空间结构（按树或图组织解）； (3)以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪 枝函数避免无效搜索。 7、常见的两种分支限界法的算法框架 答：（1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 10、用分支限界法解装载问题时，对算法进行了一些改进，下面的程序段给出了改进部分；试说明斜线部分完成什么功能，以及这样做的原因，即采用这样的方式，算法在执行上有什么不 同。 答：斜线标识的部分完成的功能为：提前更新bestw值； 这样做可以尽早的进行对右子树的剪枝。具体为：算法Maxloading初始时将bestw设置为0，直到搜索到第一个叶结点时才更新bestw。因此在算法搜索到第一个叶子结点之前，总有bestw=0，r>0 故Ew+r>bestw总是成立。也就是说，此时右子树测试不起作用。 为了使上述右子树测试尽早生效，应提早更新bestw。又知算法最终找到的最优值是所求问题的子集树中所有可行结点相应重量的最大值。而结点所相应得重量仅在搜索进入左子树是增加，因此，可以在算法每一次进入左子树时更新bestw的值。 《数值计算方法》复习试题 一、填空题： 1、????? ?????----=410141014A ，则A 的LU 分解为 A ??? ?????????=? ?????????? ?。 答案： ?? ????????--??????????--=1556141501 4115401411A 2、已知3.1)3(,2.1)2(,0.1)1(===f f f ，则用辛普生（辛卜生）公式计算求得 ?≈3 1 _________ )(dx x f ,用三点式求得≈')1(f 。 答案：， 3、1)3(,2)2(,1)1(==-=f f f ，则过这三点的二次插值多项式中2 x 的系数为 ， 拉格朗日插值多项式为 。 答案：-1， )2)(1(21 )3)(1(2)3)(2(21)(2--------= x x x x x x x L 4、近似值*0.231x =关于真值229.0=x 有( 2 )位有效数字； 5、设)(x f 可微,求方程)(x f x =的牛顿迭代格式是( )； （ 答案 )(1)(1n n n n n x f x f x x x '--- =+ 6、对1)(3 ++=x x x f ,差商=]3,2,1,0[f ( 1 ),=]4,3,2,1,0[f ( 0 )； 7、计算方法主要研究( 截断 )误差和( 舍入 )误差； 8、用二分法求非线性方程 f (x )=0在区间(a ,b )内的根时，二分n 次后的误差限为 ( 1 2+-n a b )； 9、求解一阶常微分方程初值问题y '= f (x ,y )，y (x 0)=y 0的改进的欧拉公式为 ( )] ,(),([2111+++++=n n n n n n y x f y x f h y y )； 10、已知f (1)＝2，f (2)＝3，f (4)＝，则二次Newton 插值多项式中x 2系数为( )； 11、 两点式高斯型求积公式?1 d )(x x f ≈( ?++-≈1 )] 321 3()3213([21d )(f f x x f )，代数精 度为( 5 )； 12、 解线性方程组A x =b 的高斯顺序消元法满足的充要条件为(A 的各阶顺序主子式均 不为零)。 13、 为了使计算 32)1(6 )1(41310-- -+-+ =x x x y 的乘除法次数尽量地少，应将该表 达式改写为 11 ,))64(3(10-= -++=x t t t t y ，为了减少舍入误差，应将表达式 19992001-改写为 199920012 + 。 14、 用二分法求方程01)(3 =-+=x x x f 在区间[0,1]内的根,进行一步后根的所在区间 为 ，1 ,进行两步后根的所在区间为 ， 。 15、 、 16、 计算积分?1 5 .0d x x ,取4位有效数字。用梯形公式计算求得的近似值为 ，用辛卜 生公式计算求得的近似值为 ，梯形公式的代数精度为 1 ，辛卜生公式的代数精度为 3 。 17、 求解方程组?? ?=+=+042.01532121x x x x 的高斯—塞德尔迭代格式为 ?????-=-=+++20/3/)51()1(1)1(2)(2)1(1 k k k k x x x x ，该迭 代格式的迭代矩阵的谱半径)(M ρ= 121 。 18、 设46)2(,16)1(,0)0(===f f f ,则=)(1x l )2()(1--=x x x l ，)(x f 的二次牛顿 插值多项式为 )1(716)(2-+=x x x x N 。 19、 求积公式 ?∑=≈b a k n k k x f A x x f )(d )(0 的代数精度以( 高斯型 )求积公式为最高，具 有( 12+n )次代数精度。 一、单项选择题（共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。 算法初步练习题 一、选择题： 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题 练习题与答案 练习题一 练习题二 练习题三 练习题四 练习题五 练习题六 练习题七 练习题八 练习题答案 练习题一 一、是非题 1.–作为x的近似值一定具有6位有效数字，且其误差限。() 2.对两个不同数的近似数，误差越小，有效数位越多。() 3.一个近似数的有效数位愈多，其相对误差限愈小。() 4.用近似表示cos x产生舍入误差。 ( ) 5.和作为的近似值有效数字位数相同。 ( ) 二、填空题 1.为了使计算的乘除法次数尽量少，应将该表达式改写 为； 2.–是x舍入得到的近似值，它有位有效数字，误差限 为，相对误差限为； 3.误差的来源是； 4.截断误差 为； 5.设计算法应遵循的原则 是。 三、选择题 1．–作为x的近似值，它的有效数字位数为( ) 。 (A) 7； (B) 3； (C) 不能确定 (D) 5. 2．舍入误差是( )产生的误差。 (A) 只取有限位数 (B) 模型准确值与用数值方法求得的准确值 (C) 观察与测量 (D) 数学模型准确值与实际值 3．用 1+x近似表示e x所产生的误差是( )误差。 (A). 模型 (B). 观测 (C). 截断 (D). 舍入 4．用s*=g t2表示自由落体运动距离与时间的关系式 (g为重力加速度)，s t是在时间t内的实际距离，则s t s*是（）误差。 (A). 舍入 (B). 观测 (C). 模型 (D). 截断 5．作为的近似值，有( )位有效数字。 (A) 3； (B) 4； (C) 5； (D) 6。 四、计算题 1．，，分别作为的近似值，各有几位有效数字？ 2．设计算球体积允许的相对误差限为1%，问测量球直径的相对误差限最大为多少？ 3．利用等价变换使下列表达式的计算结果比较精确： (1)， (2) (3) ， (4) 4．真空中自由落体运动距离s与时间t的关系式是s=g t2，g为重力加速度。现设g是精确的，而对t有秒的测量误差，证明：当t增加时，距离的绝对误差增加，而相对误差却减少。 5*. 采用迭代法计算，取 k=0,1,…, 若是的具有n位有效数字的近似值，求证是的具有2n位有效数字的近似值。 练习题二 一、是非题 1.单点割线法的收敛阶比双点割线法低。 ( ) 2.牛顿法是二阶收敛的。 ( ) 3.求方程在区间[1, 2]内根的迭代法总是收敛的。( ) 4.迭代法的敛散性与迭代初值的选取无关。 ( ) 5.求非线性方程f (x)=0根的方法均是单步法。 ( ) 二、填空题 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 若b 5．计算机执行下面的程序段后，输出的结果是（） 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按从大到小排列 《计算方法》练习题一 练习题第1套参考答案 一、填空题 1．Λ14159.3=π的近似值3.1428，准确数位是（ 210- ）。 2．满足d b f c a f ==)(,)(的插值余项=)(x R （ ))((!2) (b x a x f --''ξ ） 。 3．设)}({x P k 为勒让德多项式，则=))(),((22x P x P （5 2 ）。 4．乘幂法是求实方阵（按模最大 ）特征值与特征向量的迭代法。 5．欧拉法的绝对稳定实区间是（ ]0,2[-）。 二、单选题 1．已知近似数,,b a 的误差限)(),(b a εε，则=)(ab ε（Ｃ ）。 A ．)()(b a εε Ｂ．)()(b a εε+ Ｃ．)()(b b a a εε+ Ｄ．)()(a b b a εε+ 2．设x x x f +=2)(，则=]3,2,1[f （ Ａ ）。 Ａ．１ Ｂ．２ Ｃ．３ Ｄ．４ 3．设Ａ＝? ? ????3113，则化Ａ为对角阵的平面旋转=θ（ Ｃ ）． Ａ． 2π Ｂ．3π Ｃ．4π Ｄ．6 π 4．若双点弦法收敛，则双点弦法具有（Ｂ ）敛速． Ａ．线性 Ｂ．超线性 Ｃ．平方 Ｄ．三次 5．改进欧拉法的局部截断误差阶是（ Ｃ ）. A ．)(h o Ｂ．)(2h o Ｃ．)(3h o Ｄ．)(4h o 三、计算题 1．求矛盾方程组：??? ??=-=+=+2 42321 2121x x x x x x 的最小二乘解。 22122122121)2()42()3(),(--+-++-+=x x x x x x x x ?， 由0,021=??=??x x ? ?得：???=+=+96292321 21x x x x ， 高二数学算法初步单元 测试题及答案 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）题 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? 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、已知3.1)3(,2.1)2(,0.1)1(===f f f ，则用辛普生（辛卜生）公式计算求得 ?≈3 1 _________ )(dx x f ,用三点式求得≈')1(f 。 答案：2.367，0.25 2、1)3(,2)2(,1)1(==-=f f f ，则过这三点的二次插值多项式中2 x 的系数为 ，拉 格朗日插值多项式为 。 答案：-1， )2)(1(21 )3)(1(2)3)(2(21)(2--------= x x x x x x x L 3、近似值*0.231x =关于真值229.0=x 有( 2 )位有效数字； 4、设)(x f 可微,求方程)(x f x =的牛顿迭代格式是( )； 答案 )(1)(1n n n n n x f x f x x x '--- =+ 5、对1)(3 ++=x x x f ,差商=]3,2,1,0[f ( 1 ),=]4,3,2,1,0[f ( 0 )； 6、计算方法主要研究( 截断 )误差和( 舍入 )误差； 7、用二分法求非线性方程 f (x )=0在区间(a ,b )内的根时，二分n 次后的误差限为 ( 1 2+-n a b )； 8、已知f (1)＝2，f (2)＝3，f (4)＝5.9，则二次Newton 插值多项式中x 2系数为( 0.15 )； 11、 两点式高斯型求积公式?1 d )(x x f ≈( ?++-≈1 )] 321 3()3213([21d )(f f x x f )，代数精度 为( 5 )； 12、 为了使计算 32)1(6 )1(41310-- -+-+ =x x x y 的乘除法次数尽量地少，应将该表达 式改写为 11 ,))64(3(10-= -++=x t t t t y ，为了减少舍入误差，应将表达式1999 2001- 六年级数学简便计算专项练习题（附答案＋计算方法汇总） 小学阶段（高年级）的简便运算，在一定程度上突破了算式原来的运算顺序，根据运算定律、性质重组运算顺序。如果学生没真正理解运算定律、性质，他只能照葫芦画瓢。在实际解题的过程当中，学生的思路不清晰，常出现这样或那样的错误。因此，培养学生思维的灵活性就显得尤为重要。 下面，为大家整理了8种简便运算的方法，希望同学们在理解的基础上灵活运用，不提倡死记硬背哟！ 1.提取公因式 这个方法实际上是运用了乘法分配律，将相同因数提取出来，考试中往往剩下的项相加减，会出现一个整数。 注意相同因数的提取。 例如： 0.92×1.41＋0.92×8.59 =0.92×（1.41+8.59） 2.借来借去法 看到名字，就知道这个方法的含义。用此方法时，需要注意观察，发现规律。还要注意还哦,有借有还，再借不难。 考试中，看到有类似998、999或者1.98等接近一个非常好计算的整数的时候，往往使用借来借去法。 例如： 9999+999+99+9 =9999+1+999+1+99+1+9+1－4 3.拆分法 顾名思义，拆分法就是为了方便计算把一个数拆成几个数。这需要掌握一些“好朋友”，如：2和5，4和5，2和2.5，4和2.5，8和1.25等。分拆还要注意不要改变数的大小哦。 例如： 3.2×12.5×25 =8×0.4×12.5×25 =8×12.5×0.4×25 4.加法结合律 注意对加法结合律 (a＋b)＋c=a＋(b＋c) 的运用，通过改变加数的位置来获得更简便的运算。 例如： 5.76＋13.67＋4.24＋ 6.33 =（5.76＋4.24）＋(13.67＋6.33) 5.拆分法和乘法分配律结合 这种方法要灵活掌握拆分法和乘法分配律，在考卷上看到99、101、9.8等接近一个整数的时候，要首先考虑拆分。 例如： 34×9.9 = 34×(10－0.1) 案例再现：57×101=？ 6.利用基准数 在一系列数种找出一个比较折中的数字来代表这一系列的数字，当然要记得这个数字的选取不能偏离这一系列数字太远。 例如： 2072+2052+2062+2042+2083 算法初步单元测试题 一、选择题()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组基础练(建议用时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≤r 6.用秦九韶算法求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. 《计算方法》练习题一 练习题第1套参考答案 一、填空题 1． 14159.3=π的近似值3.1428，准确数位是（ 2 10- ）。 2．满足d b f c a f ==)(,)(的插值余项=)(x R （ ))((!2) (b x a x f --''ξ ） 。 3．设)}({x P k 为勒让德多项式，则=))(),((22x P x P （5 2 ）。 4．乘幂法是求实方阵（按模最大 ）特征值与特征向量的迭代法。 5．欧拉法的绝对稳定实区间是（ ]0,2[-）。 二、单选题 1．已知近似数,,b a 的误差限)(),(b a εε，则=)(ab ε（Ｃ ）。 A ．)()(b a εε Ｂ．)()(b a εε+ Ｃ．)()(b b a a εε+ Ｄ．)()(a b b a εε+ 2．设x x x f +=2 )(，则=]3,2,1[f （ Ａ ）。 Ａ．１ Ｂ．２ Ｃ．３ Ｄ．４ 3．设Ａ＝?? ? ? ??3113，则化Ａ为对角阵的平面旋转=θ（ Ｃ ） ． Ａ． 2π Ｂ．3π Ｃ．4π Ｄ．6 π 4．若双点弦法收敛，则双点弦法具有（Ｂ ）敛速． Ａ．线性 Ｂ．超线性 Ｃ．平方 Ｄ．三次 5．改进欧拉法的局部截断误差阶是（ Ｃ ）. A ．)(h o Ｂ．)(2 h o Ｃ．)(3 h o Ｄ．)(4 h o 三、计算题 1．求矛盾方程组：??? ??=-=+=+2 42321 2121x x x x x x 的最小二乘解。 2 212 212 2121)2()42()3(),(--+-++-+=x x x x x x x x ?， 由 0,021=??=??x x ? ?得：???=+=+9 629232121x x x x ， 解得14 9 ,71821== x x 。 数学必修三《算法初步》单元测试 一、选择题 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题 《数值计算方法》复习试题 一、填空题: 1、????? ?????----=410141014A ，则A 的ＬU 分解为 A ??? ?????????=? ?????????? ?。 答案： ?? ????????--??????????--=1556141501 4115401411A 3、1)3(,2)2(,1)1(==-=f f f ,则过这三点的二次插值多项式中2 x 的系数 为 ，拉格朗日插值多项式为 。 答案:-1， )2)(1(21 )3)(1(2)3)(2(21)(2--------= x x x x x x x L 4、近似值*0.231x =关于真值229.0=x 有( 2 )位有效数字； ５、设)(x f 可微,求方程)(x f x =的牛顿迭代格式是( ）； 答案 )(1)(1n n n n n x f x f x x x '--- =+ ６、对1)(3 ++=x x x f ,差商=]3,2,1,0[f ( 1 )，=]4,3,2,1,0[f ( ０ )； 7、计算方法主要研究（ 截断 ）误差和( 舍入 )误差; 8、用二分法求非线性方程 f (x )=0在区间(a ,b )内的根时,二分n 次后的误差限为 （ 1 2+-n a b ); １０、已知f （１）＝2,f (2)=３,ｆ(４)＝5.９，则二次Ne ｗton 插值多项式中x 2系数为 ( ０.15 )； 11、 解线性方程组A x =b 的高斯顺序消元法满足的充要条件为（A 的各阶顺序主子式均 不为零)。 12、 为了使计算 32)1(6 )1(41310-- -+-+ =x x x y 的乘除法次数尽量地少，应将该 第一章算法初步 (时间：120分钟满分：150分) 一、选择题(本大题共12小题，每小题5分，共60分) 1．将两个数a＝8，b＝17交换，使a＝17，b＝8，下面语句正确一组是() 2．运行如下的程序，输出结果为() A．32 B．33 C．61 D．63 3．表达算法的基本逻辑结构不包括() A．顺序结构 B．条件结构 C．循环结构 D．计算结构 4．设计一个计算1×2×3×…×10的值的算法时，下面说法正确的是() A．只需一个累乘变量和一个计数变量 B．累乘变量初始值设为0 C．计数变量的值不能为1 D．画程序框图只需循环结构即可 5．阅读下边的程序框图，运行相应的程序，则输出s的值为() A．－1 B．0 C．1 D．3 6，输出的结果是() a=1 b=3 a=a+b b=a-b PRINT a,b A C．0,0 D．6,0 7．给出30个数：1,2,4,7,11，…，其规律是第一个数是1，第二个数比第一个数大1，第三个数比第二个数大2，第四个数比第三个数大3，……依此类推，要计算这30个数的和，现已知给出了该问题的程序框图如图所示．那么框图中判断框①处和执行框②处应分别填入() A．i≤30？；p＝p＋i－1 B．i≤29？；p＝p＋i－1 C．i≤31？；p＝p＋i D．i≤30？；p＝p＋i 8．当x＝5，y＝－20时，下面程序运行后输出的结果为() A．22，－22 B．22,22 C．12，－12 D．－12,12 9．阅读如图所示的程序框图，运行相应的程序，输出的结果是() A．2 B．4 C．8 D．16 10． INPUT x IF x>0THEN y＝SQR(x) ELSE y＝(0.5)^x－1 END IF PRINT y END 时，则输入的x值的取值范围是() A．(－∞，－1) B．(1，＋∞) C．(－∞，－1)∪(1，＋∞) D．(－∞，0)∪(0，＋∞) 11．用“辗转相除法”求得459和357的最大公约数是() A．3 B．9 C．17 D．51 12．以下给出了一个程序框图，其作用是输入x的值，输出相应的y的值，若要使输入的x的值与输出的y的值相等，则这样的x的值有() A．1个 B．2个 题号123456789101112答案 13．读程序 计算方法模拟试题 一、 单项选择题（每小题3分，共15分） 1．近似值210450.0?的误差限为（ ）。 A ． 0.5 B. 0.05 C ． 0.005 D. 0.0005. 2. 求积公式)2(3 1 )1(34)0(31)(2 0f f f dx x f ++≈ ?的代数精确度为（ ）。 A. 1 B. 2 C. 3 D. 4 3. 若实方阵A 满足（ ）时，则存在唯一单位下三角阵L 和上三角阵R ，使LR A =。 A. 0det ≠A B. 某个0 det ≠k A C. )1,1(0det -=≠n k A k D. ),,1(0det n k A k =≠ 4.已知?? ?? ? ?????=531221112A ，则=∞A （ ）。 A. 4 B. 5 C. 6 D 9 5.当实方阵A 满足)2(,221>>-=i i λλλλ，则乘幂法计算公式1e =（ ）。 A. 1+k x B. k k x x 11λ++ C. k x D. k k x x 11λ-+ 二、填空题（每小题3分，共15分） 1. 14159.3=π，具有4位有效数字的近似值为 。 2. 已知近似值21,x x ，则=-?)(21x x 。 3．已知1)(2-=x x f ，则差商=]3,2,1[f 。 4．雅可比法是求实对称阵 的一种变换方法。 5．改进欧拉法的公式为 。 三、计算题（每小题12分 ，共60分） 1. 求矛盾方程组； ??? ??=-=+=+2 42321 2121x x x x x x 的最小二乘解。 2．用列主元法解方程组 ??? ??=++=++=++4 26453426352321 321321x x x x x x x x x 3．已知方程组 ???? ? ?????=????????????????????----131********x x x a a a a （1） 写出雅可比法迭代公式； （2） 证明2 高一数学单元形成性测试题（十三） （数学三第一章） 一：选择题： 1． 下列语句正确的是（ ） A .x+3=y-2 B .d=d+2 C .0=x D .x-y=5 2: 将二进制数10101（2）化为十进制为（ ） A ．21 B. 20 C.19 D. 18 3：将十进制数111化为五进制数是（ ） A ．421（5） B. 521（5） C.423（5） D. 332（5） 4: 用程序框图表示“判断以任意给定的3个正实数为边长的三角形是否存在”将用到（ ） A 、顺序结构 B 、顺序结构和条件结构 C 、顺序结构和循环结构 D 、三种基本逻辑结构 5：用二分法求方程2 20x -=的近似根的算法中要用那种算法结构（ ） A ．顺序结构 B.条件结构 C. 循环结构 D. 以上都用 6：对赋值语句描述正确的是（ ） ①可以给变量提供初值 ②将表达式的值赋给变量 ③可以给一个变量重复赋值 ④不能给同一个变量重复赋值 A .①②③ B.①② C .②③④ D.①②④ 7: 阅读右面的流程图，若输入的a 、b 、c 分别是21、32、75， 则输出的a 、b 、c 分别是：（ ） )(A 75、21、32 )(B 21、32、75 )(C 32、21、75 )(D 75、32、21 8:将两个数8,17a b ==交换,使17,8a b ==,下面语句正确一组是 ( ) 二：填空题 9.算法的基本结构是：__________________ 10．各种程序设计语言中都包含的基本算法语句是______________ 11．程序框图（如图1 12.下列程序如图2运行的结果是 N=15 SUM=0 I=1 WHILE I ≦N SUM=SUM+I I=I+2 WEND PRINT “SUM=”;SUM END （2） 三．解答题 13.已知一个三角形的三条边长分别为2，3，4，画出一个求三角形面积的框图。 14. 画出一个“求满足10003212 222>++++n 的n 最小值”的框图。《数值计算方法》试题集及答案
高一数学必修三《算法初步》单元测试题
算法初步练习题(附详细答案).doc
计算方法练习题与答案
1.4算法初步单元测试
计算方法习题
高二数学算法初步单元测试题及答案
2018届人教A版算法初步单元测试13
高中数学必修三《算法初步》练习题(内含答案)[1]
数值计算方法》试题集及答案
六年级数学简便计算专项练习题(附答案+计算方法汇总)
算法初步单元测试题
人教A版高中数学必修三练习：第一章算法初步分层训练进阶冲关1.3算法案例Word版含答案
计算方法习题
新课改高中数学数学必修三《算法初步》单元测试[技巧]
算法初步练习题(附详细答案)好
《数值计算方法》试题集及答案
算法初步单元测试题(含详细答案)
计算方法模拟试题及答案
中山市直属学校算法初步单元测试题