算法综合

（数学3必修）第一章 算法初步 [综合训练B 组] 一、选择题1 用“辗转相除法”求得459和357的最大公约数是（ ）A 3B 9C 17D 51 2 当x )A 173 利用“直接插入排序法”给8,1,2,3,5,7按从大到小的顺序排序，当插入第四个数3时，实际是插入哪两个数之间 （ ） A 8与1 B 8与2 C 5与2 D 5与1 4 对赋值语句的描述正确的是 （ ）①可以给变量提供初值 ②将表达式的值赋给变量 ③可以给一个变量重复赋值 ④不能给同一变量重复赋值 A ①②③ B ①② C ②③④ D ①②④ 5 在repeat 语句的一般形式中有“until A ”,其中A 是 ( )A 循环变量B 循环体C 终止条件D 终止条件为真6 用冒泡排序法从小到大排列数据 13,5,9,10,7,4需要经过（ ）趟排序才能完成 A 4 B 5 C 6 D 7二、填空题1 根据条件把流程图补充完整，求11000→内所有奇数的和；(1) 处填(2) 处填2 图中所示的是一个算法的流程图，已知31=a ，输出的7b =,则2a 的值是____________3 下列各数)9(85 、 )6(210 、 )4(1000 、 )2(111111中最小的数是____________4 右图给出的是计算201614121++++ 的值的一个流程图，其中判断框内应填入的条件是____________5 用直接插入排序时对:7,1,3,12,8,4,9,10进行从小到大排序时,第四步得到的一组数为: ___________________________________三、解答题1 以下是计算1234...100+++++程序框图,请写出对应的程序i:=1,S:=02 函数⎪⎩⎪⎨⎧≤<-≤<≤≤=128),12(284,840,2x x x x x y ，写出求函数的函数值的程序3 用辗转相除法或者更相减损术求三个数324,243,135的最大公约数4 意大利数学家菲波拉契,在1202年出版的一书里提出了这样的一个问题:一对兔子饲养到第二个月进入成年,第三个月生一对小兔,以后每个月生一对小兔,所生小兔能全部存活并且也是第二个月成年,第三个月生一对小兔,以后每月生一对小兔 问这样下去到年底应有多少对兔子? 试画出解决此问题的程序框图,并编写相应的程序数学3（必修）第一章 算法初步 [综合训练B 组]参考答案一、选择题1 D 4593571102,357102351,102512=⨯+=⨯+=⨯51是102和51的最大公约数，也就是459和357的最大公约数 2 C 0211,1213,3217,72115⨯+=⨯+=⨯+=⨯+=3 B 先比较8与1，得8,1；把2插入到8,1，得8,2,1；把3插入到8,2,1，得8,3,2,1；4 A 见课本赋值语句相关部分5 D Until 标志着直到型循环，直到终止条件成就为止6 B 经过第一趟得5,9,10,7,4,13；经过第二趟得5,9,7,4,10,13；经过第三趟得5,7,4,9,10,13；经过第四趟得5,4,7,9,10,13；经过第五趟得4,5,7,9,10,13；二、填空题1 （1）s s i =+（2）2i i =+2 111227,112a a a +== 3 )2(111111 (9)8589577=⨯+= 、 2(6)2102616078=⨯+⨯+= 、3(4)10001464=⨯= 、 5432(2)1111111212121212163=⨯+⨯+⨯+⨯+⨯+= 4 10i >5 1,3,7,8,12,4,9,10 1,7,3,12,8,4,9,10①; 1,3,7,12,8,4,9,10②;1,3,7,12,8,4,9,10③;1,3,7,8,12,4,9,10④三、解答题 1 解： i=1sum=0WHILE i<=100 sum=sum+i i=i+1 WEND PRINT sum END2 解：INPUT “x=”;xIF x>=0 and x<=4 THEN y=2*xELSE IF x<=8 THENy=8ELSE y=2*(12-x)END IFEND IFPRINT yEND3解：324=243×1＋81243=81×3＋0则 324与 243的最大公约数为 81又 135=81×1＋5481=54×1＋2754=27×2＋0则 81 与 135的最大公约数为27所以,三个数 324、243、135的最大公约数为 27-=-=-=另法32424381,24381162,1628181;1358154,815427,542727-=-=-=∴为所求274解: 根据题意可知,第一个月有1对小兔,第二个月有1对成年兔子,第三个月有两对兔子,从第三个月开始,每个月的兔子对数是前面两个月兔子对数的和,设第N个月有F对兔子,第N+个N-个月有Q对兔子,则有F S Q1N-个月有S对兔子,第2=+,一个月后,即第1月时,式中变量S的新值应变第N个月兔子的对数(F的旧值),变量Q的新值应变为第N+个月兔子的1N-个月兔子的对数(S的旧值),这样,用S Q+求出变量F的新值就是1数,依此类推,可以得到一个数序列,数序列的第12项就是年底应有兔子对数,我们可以先确定前两个月的兔子对数均为1,以此为基准,构造一个循环程序,让表示“第×个月的I从3逐次增加1,一直变化到12,最后一次循环得到的F就是所求结果流程图和程序如下:。

算法设计综合实训题目0．逆序数字（借助栈）编写一个函数，接收一个4位整数值，返回这个数中数字逆序后的结果值。

例如，给定数7631，函数返回1367.输入：第一行一个正整数T（T<=10），表示有T组测试数据; 以下T行，每行一个非负的整数N。

输出：共T行，对于每组输入数据输出一行，即数字逆序后的结果值。

样本输入：3763110185158样本输出：1367810185151．人见人爱A+B这个题目的A和B不是简单的整数，而是两个时间，A和B 都是由3个整数组成，分别表示时分秒，比如，假设A为34 45 56，就表示A所表示的时间是34小时 45分钟 56秒。

输入：输入数据有多行组成，首先是一个整数N，表示测试实例的个数，然后是N行数据，每行有6个整数AH,AM,AS,BH,BM,BS，分别表示时间A和B所对应的时分秒。

题目保证所有的数据合法。

输出：对于每个测试实例，输出A+B，每个输出结果也是由时分秒3部分组成，同时也要满足时间的规则（即：分和秒的取值范围在0-59），每个输出占一行，并且所有的部分都可以用32位整数表示。

样本输入：21 2 3 4 5 634 45 56 12 23 34样本输出：5 7 947 9 302．敲七【问题描述】输出7和7的倍数，还有包含7的数字例如（17，27，37...70，71，72，73...）【要求】【数据输入】一个整数N。

(N不大于30000)【数据输出】从小到大排列的不大于N的与7有关的数字，每行一个。

【样例输入】20【样例输出】714173．统计同成绩学生人数问题【问题描述】读入N名学生的成绩，将获得某一给定分数的学生人数输出。

【要求】【数据输入】测试输入包含若干测试用例，每个测试用例的格式为第1行：N第2行：N名学生的成绩，相邻两数字用一个空格间隔。

第3行：给定分数当读到N=0时输入结束。

其中N不超过1000，成绩分数为（包含）0到100之间的一个整数。

综合指数算法
综合指数算法是通过对多个指标进行评估、加权和聚合来综合评判某个事物或对象的
综合表现的算法。

以下是一种常见的综合指数算法，包括四个基本步骤：
1. 指标选择：根据具体问题从一系列指标中选择适合的评价指标，如A、B、C等。

2. 数据归一化：将各个指标的取值范围统一到相同的尺度，常用的方法有最小-最大
归一化和标准化等。

对于指标A，假设其取值范围为[a, b]，则将其归一化为[0, 1]的范围。

3. 指标加权：对每个指标进行加权处理，根据指标的重要程度决定其权重。

权重可
以通过专家评判、统计分析或基于经验的方法得到。

对于指标A、B、C，分别赋予权重w1、w2、w3，使得w1 + w2 + w3 = 1。

4. 综合评估：通过将归一化后的指标按照相应权重进行加权求和，得到综合指数。

对于指标A、B、C的归一化值分别为xa、xb、xc，综合指数可以计算为：综合指数 = w1 * xa + w2 * xb + w3 * xc。

综合指数算法根据实际需求进行灵活调整，可以根据不同指标的重要性进行权重的分配、选择不同的归一化方法等。

综合指数算法也可以通过对比不同对象的综合指数来进行
排序和排名，以支持决策和评估分析。

综合试题一、选择题1. _________不是算法的基本特征。

A. 可行性B. 长度有限C. 在规定的时间内完成D. 确定性2．在数据结构中，从逻辑上可以把数据结构分成( )A．动态结构和静态结构 B．线性结构和非线性结构C．内部结构和外部结构 D．紧凑结构和非紧凑结构3．计算机算法必须具备（）这三个特性。

A．可执行性、可移植性、可扩充性 B. 确定性、有穷性、稳定性C. 可执行性、确定性、有穷性D. 易读性、稳定性、安全性４．下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

5．在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（）。

A. s->next=p;p->next=s;B. s->next=p->next;p->next=s;C. s->next=p->next;p=s;D. p->next=s;s->next=p6．3个结点可构成( )个不同形态的二叉树A.2B.3C.4D.57．先根序列和中根序列相同的非空二叉树是( )A.任一结点均无右子树的非空二叉树B.根结点无右子树的非空二叉树C.任一结点均无左子树的非空二叉树D.根结点无左子树的非空二叉树8.假设p是指向线性表中第i个数据元素结点的指针，则p->next 是指向第i+1个数据元素结点的指针，若p->data=ai, 则p->next->data=ai+1，那么p->next->next指向的是第（）个结点A. iB. i+1C. i+2D. i+39．设栈S的初始状态为空，现有5个元素组成的序列{1，2，3，4，5}，对该序列在S栈上依次进行如下操作(从序列中的1开始，出栈后不再进栈)：进栈、进栈、进栈、出栈、进栈、出栈、进栈。

算法初步本章达标测评(总分:150分;时间:120分钟)一、选择题(本大题共12小题,每小题5分,共60分,在每小题给出的四个选项中,只有一项是符合题目要求的)1.下面对算法的描述正确的一项是( )A.算法只能用自然语言来描述B.算法只能用图形语言来表示C.同一问题可以有不同的算法D.同一问题的算法不同,结果必然不同2.执行如图所示的框图,输入N=5,则输出S的值为( )A.54B.45C.65D.563.下面一段程序执行后的结果是( )A.6B.4C.8D.104.算式1 010(2)+10(2)的值是( )A.1 011(2)B.1 100(2)C.1 101(2)D.1 000(2)5.执行如图所示的程序框图,当输入的值为3时,输出的结果是( )A.3B.8C.12D.206.若如图所示的程序框图的功能是计算1×12×13×14×15的结果,则在空白的执行框中应该填入( )A.T=T·(i+1)B.T=T·iC.T=T·1i+1D.T=T·1i7.已知7 163=209×34+57,209=57×3+38,57=38×1+19,38=19×2.根据上述一系列等式,可确定7 163和209的最大公约数是( )A.57B.3C.19D.348.已知44(k)=36,则把67(k)转化成十进制数为( )A.8B.55C.56D.629.执行如图所示的程序框图,若输出的k=5,则输入的整数p的最大值为( )A.7B.15C.31D.6310.用秦九韶算法求多项式f(x)=12+35x-8x2+79x3+6x4+5x5+3x6在x=-4时的值时,其中v4的值为( )A.-57B.124C.-845D.22011.某程序框图如图所示,若该程序运行后输出的值是9,则( )5A.a=4B.a=5C.a=6D.a=712.执行如图所示的程序框图,则输出的n的值是( )A.29B.31C.61D.63二、填空题(本大题共4小题,每小题4分,共16分,把正确答案填在题中横线上)13.输入8,则下列程序运行后输出的结果是.化成十进制数,结果为,再将该结果化成七进制数,结14.将二进制数110 101(2)果为.15.执行如图所示的程序框图,则输出结果S= .16.阅读下面程序,当输入x的值为3时,输出y的值为.(其中e为自然对数的底数)三、解答题(本大题共6小题,共74分,解答应写出文字说明,证明过程或演算步骤)17.(12分)下面给出一个用循环语句编写的程序:(1)指出程序所用的是何种循环语句,并指出该程序的算法功能;(2)请用另一种循环语句的形式把该程序写出来.18.(12分)输入10个数,找出其中最大的数并输出,画出程序框图,并写出程序.19.(12分)如图所示,在边长为4的正方形ABCD的边上有一点P,沿着折线BCDA由点B(起点)向点A(终点)运动(不与A、B重合).设点P运动的路程为x,△APB的面积为y,求y与x之间的函数关系式,画出程序框图,写出程序.20.(12分)把区间[0,1]10等分,求函数y=√2x+1+|x-2|在各分点(包括区间端点)的函数值,写出程序.21.(12分)设计一个程序求11×4+13×6+15×8+…+199×102的值.22.(14分)“角谷猜想”是由日本学者角谷静夫首先提出的,所以称为“角谷猜想”.猜想的内容是:对于任意一个大于1的整数n,如果n 为偶数就除以2,如果n 是奇数,就将其乘3再加1,然后将得到的结果再进行以上处理,则最后结果总是1.试设计一个算法的程序框图,对任意输入的整数n(n≥2)进行检验,要求输出每一步的结果,直到结果为1时结束.附加题1.(2015河北石家庄一模,★★☆)执行下面的程序框图,如果输入的依次是1,2,4,8,则输出的S 为( )A.2B.2√2C.4D.62.(2015山西四校联考三,★★☆)执行如图的程序框图,则输出S 的值为( )D.-1 A.2 016 B.2 C.12一、选择题1.C 算法可以用自然语言、图形语言和程序语言来描述;同一个问题可以有不同的算法,但算法的结果相同.2.D 第一次循环,S=0+11×2=12,k=2;第二次循环,S=12+12×3=23,k=3;第三次循环,S=23+13×4=34,k=4;第四次循环,S=34+14×5=45,k=5;第五次循环,S=45+15×6=56,此时k=5不满足判断框内的条件,跳出循环,输出S=56,选D.3.A 由程序知a=2,2×2=4,4+2=6,故最后输出a 的值为6,故选A.4.B 1 010(2)+10(2)=(1×23+0×22+1×21+0×20)+(1×21+0×20)=12=1 100(2).5.B 3<5,执行y=x 2-1,所以输出结果为8.故选B.6.C 程序框图的功能是计算1×12×13×14×15的结果,依次验证选项可得选项C 正确. 7.C 由辗转相除法的思想可得结果. 8.B 由题意得,36=4×k 1+4×k 0,所以k=8. 则67(k)=67(8)=6×81+7×80=55.9.B 由程序框图可知:①S=0,k=1;②S=1,k=2;③S=3,k=3;④S=7,k=4;⑤S=15,k=5,输出k,此时S=15≥p,则p 的最大值为15,故选B. 10.D由已知,得a 0=12,a 1=35,a 2=-8,a 3=79,a 4=6,a 5=5,a 6=3,所以v 0=3,v 1=3×(-4)+5=-7,v 2=(-7)×(-4)+6=34,v 3=34×(-4)+79=-57,v 4=(-57)×(-4)-8=220.11.A 此程序框图的作用是计算S=1+11×2+12×3+…+1a (a+1)的值,由已知得S=95,即S=1+1-12+12-13+…+1a -1a+1=2-1a+1=95,解得a=4.12.D 开始:p=5,n=1;p=9,n=3;p=15,n=7;p=23,n=15;p=31,n=31;p=31,n=63,此时log 3163>1,结束循环,输出n=63. 二、填空题 13.答案 0.7解析 这是一个用条件语句编写的程序,由于输入的数据为8,8<-4不成立,所以c=0.2+0.1×(8-3)=0.7. 14.答案 53;104(7)解析 110 101(2)=1×25+1×24+0×23+1×22+0×21+1×20=53,然后用除7取余法得53=104.(7)15.答案 1 007解析根据程序框图知,S=(-1+2)+(-3+4)+…+(-2 013+2 014)=1 007,故输出的S的值为1 007.16.答案 1.5解析当输入x=3时,由于3>e,故执行y=0.5x,即y=0.5×3=1.5.三、解答题17.解析(1)本程序所用的循环语句是WHILE循环语句,其功能是计算12+22+32+…+92的值.(2)用UNTIL语句改写程序如下:18.解析程序框图如图.程序:19.解析 函数关系式为 y={2x (0<x ≤4),8(4<x ≤8),2(12-x )(8<x <12).程序框图如图所示:程序:20.解析把区间[0,1]10等分,故步长为0.1,∴用“x=x+0.1”表达,y=√2x+1+|x-2|,用“y=SQR(2*x+1)+ABS(x-2)”表达,循环控制条件x≤1.程序如下:21.解析程序:22.解析程序框图如图:附加题1.B 由程序框图可知,S=1,i=1;S=1,i=2;S=√2,i=3;S=2,i=4;S=2√2,i=5,此时跳出循环,输出S=2√2.故选B.2.B 循环前S=2,k=0,第一次循环,得S=11-2=-1,k=1;第二次循环,得S=11-(-1)=12,k=2;第三次循环,得S=11-12=2,k=3;……,由此可知S 的值的变化周期为3,又2 016=672×3,所以输出S 的值为2,故选B.。

算法与分析综合试卷一、选择题1．算法分析是（）。

A．将算法用某种程序设计语言恰当地表示出来B．在抽象数据集合上执行程序，以确定是否会产生错误的结果C．对算法需要多少计算时间和存储空间作定量分析D．证明算法对所有可能的合法输入都能算出正确的答案2．算法确认是（）。

A．将算法用某种程序设计语言恰当地表示出来B．证明算法对所有可能的合法输入都能算出正确的答案C．对算法需要多少计算时间和存储空间作定量分析D．在抽象数据集合上执行程序，以确定是否会产生错误的结果3．算法与程序的区别在于算法具有（）。

A．能行性B．确定性C．有穷性D．输入和输出4．设A[1..60]={11,12,…,70}。

算法BINARYSEARCH在A上搜索x=33、7、70、77时执行的元素比较次数分别为a、b、c、d，则（）。

A．a<b<c<d B．a>b=c=d C．a<b=c=d D．a<c<b=d5．算法INSERTIONSORT 在A[1..8]={45,33,24,45,12,12,24,12}上运行时执行的元素比较次数为（）。

A．14 B．28 C．7 D．226．当A[1..n]中元素取值在范围（）时，算法RADIXSORT 的时间复杂度为T(nlogn)。

A．A．[1..n] B．[n..2n] C．[1..n2] D．[1.. 2n]7．设待排序的序列A[1..n]中元素取值于[1..n!]，则下列哪一个算法最坏情况下排序更慢?A．SELECTIONSORT B．INSERTIONSORTC．RADIXSORT D．BUBBLESORT8．一个排序算法如果能够使得序列中相同元素的位置次序在排序前后保持一致，则称之为稳定的排序算法。

下列几种排序算法中哪一种不是稳定的？A．SELECTIONSORT B．RADIXSORTC．BUBBLEBSORT D．BOTTOMUPSORT9．使用算法EXP来计算下列哪一个整数次幂所花费的乘法次数最多？A．35B．36C．37D．3810．算法MAJORITY在下列哪一个输入上执行时最后j=n，count=1，且c是主元素？A．{5,7,5,4,5} B．{5,7,5,4,8} C．{2,4,1,4,4,4,6,4} D．{1,2,3,4,5} 11．用贪心法设计算法的关键是（）。

C语言排序算法大全综合排序利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。

基本要求：（1) 至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。

并把排序后的结果保存在不同的文件中。

（2) 统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。

问题补充：要纯C语言版，不含C++语言/*================================================================相关知识介绍（所有定义只为帮助理解相关概念，并非严格定义）：1、稳定排序和非稳定排序简单地说就是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，我们就说这种排序方法是稳定的。

反之，就是非稳定的。

比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为a1,a2,a4,a3,a5，则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。

假如变成a1,a4,a2,a3,a5就不是稳定的了。

2、内排序和外排序在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序；在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。

3、算法的时间复杂度和空间复杂度所谓算法的时间复杂度，是指执行算法所需要的计算工作量。

一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。

==================================================================*/ /*================================================================== 功能：选择排序输入：数组名称（也就是数组首地址）、数组中元素个数==================================================================*/ /*================================================================== 算法思想简单描述：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

实验五程序设计常用算法5.1实验要求与目的1．熟悉和掌握算法以及算法的特性2．熟练掌握结构化程序设计的三种基本结构3. 掌握常用的数值算法（求最大公约数，迭代法、牛顿迭代法和二分法等）4. 培养解决实际问题的能力5.2实验指导算法（Algorithm）是计算机解题的基本思想方法和步骤，算法被称为程序设计的灵魂，也是学习编程的必备知识。

学习和掌握算法，必须要十分清楚，输入什么数据，输出什么结果，采用什么结构以及如何合理安排语句等。

通常使用自然语言、结构化流程图、伪代码等来描述算法。

利用计算机解决问题，首先要设计出适合计算机执行的算法，此算法包含的步骤必须是有限的，每一步都必须是明确的，最终能被计算机执行，而得到结果。

算法可分为两类：1.数值运算算法。

对问题求数值解，通过运算得出一个具体值，如求方程的根等，此类算法一般有现成的模型，算法较成熟。

2.非数值运算算法。

如用于事务管理领域，图书检索等。

根据实际问题设计算法时，还要尽量考虑用重复的步骤去实现，使算法简明扼要，通用性强，不仅能减少编写程序的时间，减少上机输入和调试程序的时间，还能减少程序本身所占用的内存空间。

算法应具有以下的特性：1.有穷性：一个算法应包含有限的操作步骤而不能是无限的。

2.确定性：算法中每一个步骤应当是确定的，而不能具有二义性。

3.有零个或多个输入：通常，处理的数据对象需要从外界通过输入来获得数据。

4.有一个或多个输出：算法的目的就是得到结果，将其结果输出。

没有输出的算法是无意义的。

5.有效性：算法中每一个步骤应当能有效地执行，并得到确定的结果。

【5.1】编程实现，求两个正整数的最大公约数和最小公倍数。

程序文件名ex5_1.c。

分析：利用欧几里德辗转相除法求最大公约数。

算法思想，假定两个整数m,n（m>n），用较小的数n（除数）除较大的数m（被除数），得到余数r1；若余数r1不为零，则除数作为被除数，余数r1作为除数，相除得到余数r2；若余数r2还不为零，仍是将除数作为被除数，余数r2作为除数，相除得到余数r3，这样辗转相除，直到余数是零为止。

综合排序算法
综合排序算法是指一类能够处理多种类型数据，并兼顾多种排序标准的排序方法。

这类算法常用于解决多字段排序的问题，例如在数据库查询或复杂列表排序时，不仅需要根据一个字段排序，还要考虑其他字段的次序规则。

基本思想是先按第一优先级字段排序，遇到相同值时再比较第二优先级字段，以此类推。

常见的实现方式有：
1. 多关键字排序：设置多个排序键，依次对每个键进行排序。

2. 权重排序：给每个字段赋予不同的权重，通过计算加权值进行排序。

3. 复合排序：在编程语言中，利用sort函数提供的自定义比较函数，根据多个字段组合成复合条件进行排序。

综合排序算法可以灵活适应复杂的数据排序需求，提高数据处理的实用性与便利性。