算法案例习题(含答案).doc

算法案例 习题（含答案）

一、单选题
1．给出下列命题：
①命题“∃ x0∈R , x02+1>4x0”的否定是“∀x∈R,x2+1≤4x”；
②命题“若x>y，则x>y”的逆命题是真命题；
③把1010(2)化为十进制为11；
④“方程x2k-9+y225-k=1表示椭圆”的充要条件是“9<k<25”．
其中正确命题的个数为（　　）
A． 1 B． 2 C． 3 D． 4
2．用秦九韶算法计算多项式在时的值时,的值为（ ）
A．－307 B．－81 C．19 D．1
3．《周易》历来被人们视作儒家之首，它表现了古代中华民族对万事万物的深刻而不朴素的认识，是中华人文文化的基础，它反映出中国古代的二进制计数的思想方法，我们用近代术语解释为：把阳“—”当作数字“1”，把阴“——”当作数字“0”，则八卦所代表的数表示如下：

依次类推，则六十四卦“屯”卦，符号“”表示的十进制是（ ）
A． B． C． D．
4．在下列各数中,最大的数是(　　)
A． 85(9) B． 210(6)
C． 1000(4) D． 11111(2)
5．二位进制数101化为十位进制数是（ ）
A． 4 B． 5 C． 6 D． 7
6．“结绳计数”是远古时代的人最常用的计数方法，就是用打绳结的办法来计算物体的数量.如图所示的是一位猎人记录自己捕获猎物的个数，在从右向左依次排行的不同绳子上打结，满五进一.根据图示可知，猎人捕获猎物的个数是（ ）

A． 123 B． 86 C． 66 D． 38
7．我国南宋时期的数学家秦九韶是普州（现四川省安岳县）人，秦九韶在所著的《数书九章》中提出的多项式求值的秦九韶算法，至今仍是比较先进的算法，其算法如下：多项式函数f(x)=anxn+an-1xn-1+⋯ +a1x+a0写为f(x)=(anxn-1+an-1xn-2+⋯+a1)+a0=((anxn-2+an-1xn-3+⋯+a2)+a1)x+a0=⋯
=(((anx+an-1)x+an-2)x+⋯+a1)x+a0，即可用如图所示的程序框图来求某多项式的值.若输入a0=1,a1=4,a2=6,a3=4,a4=1及x0，运行程序可以输出16，则x0的值为（ ）

A． -3 B． 1或-3 C． 1 D． 2或-2
8．下列各数中，最大的是（ ）
A． 111111(2) B． 1000(4) C． 210(6) D． 29(10)
9．用秦九韶算法计算多项式= =时, 的值为
A． B． C． 602 D．

二、填空题
10．辗转相除法与更相减损术都是求两个正整数的最大公约数的有效算法，用这两种方法均可求得1254和1881的最大公约数为__________.
11．请将以下用“更相减损术”求两个正整数a,b的最大公约数的程序补充完整:

INPUT　“a,b=”;a,b
WHILE　a<>b
IF　a>b　THEN
a=a-b
ELSE
_________
END　IF
WEND
PRINT　a
END

12．把八进制数转化为三进制数为______________．
13． __________．
14．用秦九韶算法求多项式f(x)=x4-2x3+3x2-7x-5当x=4时的值,给出如下数据:
①0　 ②2　 ③11　 ④37　 ⑤143
其运算过程中(包括最终结果)会出现的数有____(只填序号).
15．二进制数对应的十进制数是__________．
16．把“五进制”数转化为“七进制”数： __________
17．用“秦九韶算法”计算多项式，当时的值的过程中，要经过
____________次乘法运算和_________次加法运算.
18．三个数72,120,168的最大公约数是 　 　　;

三、解答题
19．把110(5)转化为二进制数．
20．（本题满分13分）已知一个5次多项式为f（x）=4x5﹣3x3+2x2+5x+1，用秦九韶算法求这个多项式当x=2时的值
21．某高中男子体育小组的50米跑成绩（单位：）为：，，画出程序框图，从这些成绩中搜索出小于的成绩.
22．试分别用辗转相除法和更相减损术求840与1764、440与556的最大公约数。
23．用辗转相除法求8251与6105的最大公约数
24．用秦九韶算法求多项式f（x）=2x5-5x4-4x3+3x2-6x+7当x=5时的值．
25．若10y1(2)＝x02(3)，求数字x，y的值及与此两数等值的十进制数．
26．新课标要求学生数学模块学分认定由模块成绩决定，模块成绩由模块考试成绩和平时成绩构成，各占50%，若模块成绩大于或等于60分，获得2学分，否则不能获得学分（为0分）.
设计一算法，通过考试成绩和平时成绩计算学分，并画出程序框图.
27．（本小题满分10分）
（1）用辗转相除法求840与1764的最大公约数.
（2）用更相减损术求与的最大公约数

试卷第4页，总4页

参考答案
1．B
【解析】由题意，命题①正确；由x>y⇒x>y,y≥0x>-y,y<0成立，则命题②正确；由1010(2)=1×23+1×2=10，则命题③错；由于当k-9=25-k，即k=17时，该方程表示圆，则命题④错.故选B.
2．C
【解析】由秦九韶算法，从而，故选答案C

考点：算法
3．B
【解析】由题意类推,可知六十四卦中的“屯”卦符合“”表示二进制数的010001，
转化为十进制数的计算为1×20+0×21+0×22+0×23+1×24+0×25=17.
故选：B.
4．B
【解析】试题分析：欲找四个中最小的数，先将它们分别化成十进制数，后再比较它们的大小即可．
解：85（9）=8×9+5=77；
210（6）=2×62+1×6=78；
1000（4）=1×43=64；
11111（2）=24+23+22+21+20=31．
故11111（2）最小，
故选D．
点评：本题考查的知识点是算法的概念，由n进制转化为十进制的方法，我们只要依次累加各位数字上的数×该数位的权重，即可得到结果．
5．B
【解析】分析：利用二进制数转化为十进制数的方法即可得出．
详解：1012=1×22+0×21+1=5
故选：B
点睛：本题考查了二进制数转化为十进制数的方法，属于基础题．
6．D
【解析】由题意满五进一，可得该图示为五进制数，
化为十进制数为 ．
故选B．
7．B
【解析】分析：由题意首先确定流程图的功能，然后结合选项排除错误选项即可求得最终结果.
详解：由题意可知，该流程图的目的是计算S=a4x0+a3x0+a2x0+a1x0+a0的值，
其中a0=1,a1=4,a2=6,a3=4,a4=1，则S=x+4x+6x+4x+1，
结合选项：若x=1，则S=1+4×1+6×1+4×1+1=16，
x=1满足题意，则选项AD错误；
若x=-3，则S=-3+4×-3+6×-3+4×-3+1=16，
x=-3满足题意，则选项C错误；
本题选择B选项.
点睛：本题主要考查流程图的阅读，秦九韶算法的应用等知识，意在考查学生的转化能力和计算求解能力.
8．C
【解析】分析：先把不同的进制都转化为十进制，再统一比较大小。
详解：A、111111(2)=25+24+23+22+21+20=63
B、10000(4)=43=64
C、210(6)=2×62+1×61=78
D、29
所以比较大小，可知210(6)=2×62+1×61=78最大
所以选C
点睛：解决本题的关键是掌握把不同的进制转化为十进制的方法，属于简单题目。
9．A
【解析】=,
因为=,
所以,
.
故选A.
点睛：本题主要考查了秦九韶算法，其特点：通过一次式的反复计算，有规律的推算出下一个值，从而计算高次多项式的值，这种算法也称为“递推法”．对于一个次多项式当最高次项的系数不为1时，需进行次乘法；若各项均不为零，则需进行次加法（或减法）．注意：若多项式函数中间出现空项，要以系数为0补齐此项，即．
10．627
【解析】
由辗转相除法可得，1881=1254×1+627,1254=627×2+0 ，所以1254和1881的最大公约数为627，故答案为627.
11．b=b-a
【解析】阅读程序知，当时，做减法，当时,做减法，因此应填，故答案为.
12．
【解析】,
,
所以.
故答案为： .
13．205
【解析】 =
14．②③④⑤
【解析】将多项式写成，其中， ， ， ， ，由以上可知答案为②③④⑤
点睛：本题主要考查了秦九韶算法，其特点：通过一次式的反复计算，有规律的推算出下一个值，从而计算高次多项式的值，这种算法也称为“递推法”．对于一个次多项式当最高次项的系数不为1时，需进行次乘法；若各项均不为零，则需进行次加法（或减法）．注意：若多项式函数中间出现空项，要以系数为0补齐此项，即．
15．2
【解析】因为 所以对应的十进制数是 ，故答案为.
16．152
【解析】,
把十进制化为七进制:

所以 ,故填152.
17． 5 5
【解析】多项式f（x）=5x5+4x4+3x3+2x2+x+1=（（（（5x+4）x+3）x+2）x+1）x+1不难发现要经过5次乘法5次加法运算．
故答案为：5、5
【点睛】本题主要考查了分类加法计数原理和一元n次多项式问题，属于基础题，“秦九韶算法”的运算法则是解题关键.
18．24
【解析】
试题分析：利用辗转相除法，先求出其中二个数72，120，；120，168的最大公约数，之后我们易求出三个数72，120，168的最大公约数．
解：120=72×1+48
72=48×1+24
48=24×2
∴72，120的最大公约数是24
168=120×1+48
120=48×2+24
48=24×2
故120，168的最大公约数为24
三个数72，120，168的最大公约数24．
故答案为：24．
点评：本题考查的知识点是最大公因数，在求两个正整数的最大公因数时，辗转相除法和更相减损术是常用的方法，要熟练掌握．
19．11110(2)
【解析】解：110(5)＝1×52＋1×51＋0×50＝30，
30＝1×24＋1×23＋1×22＋1×2＋0×20
＝11110(2)，
即110(5)＝11110(2)．
20．123
【解析】
试题分析：将多项式f（x）=4x5﹣3x3+2x2+5x+1改写为f（x）=（（（（4x+0）x﹣3）x+2）x+5）x+1，首先计算最内层括号内一次多项式的值然后由内向外逐层计算一次多项式的值
试题解析：由f（x）=（（（（4x+0）x﹣3）x+2）x+5）x+1 2分
∴v0=4
v1=4×2+0=8
v2=8×2﹣3=13
v3=13×2+2=28
v4=28×2+5=61
v5=61×2+1=123 12分
故这个多项式当x=2时的值为123． 13分
考点：秦九韶算法
21．程序框图见解析.
【解析】
试题分析：由题要求，需先进行数据的判断，由于共有个数据，故循环体次数应执行次.
试题解析：程序框图：

考点：程序框图.
22．840与1764的最大公约数就是84，440与556的最大公约数是4
【解析】(1)辗转相除法:用较大的数字除以较小的数字，得到商和余数，然后再用上一式
中的除数和得到的余数中较大的除以较小的，以此类推，当整除时，就得到要求的最大公约
数．
(2) 用更相减损术求440与556的最大公约数，先用大数减去小数，再用减数和差中较大的
数字减去较小的数字，这样减下去，知道减数和差相同，得到最大公约数．
解：（1）用辗转相除法求840与1764的最大公约数。
1764=8402+84，840=8410+0，
所以840与1764的最大公约数就是84。
(2）用更相减损术求440与556的最大公约数。
556-440=116，440-116=324，324-116=208，208-116=92，116-92=24，92-24=68，
68-24=44，44-24=20，24-20=4，20-4=16，16-4=12，12-4=8，8-4=4。
440与556的最大公约数是4。
23．37
【解析】
试题分析：用辗转相除法求最大公约数的步骤用较大的数字除以较小的数字，得到商和余数，然后再用上一式中的除数和得到的余数中较大的除以较小的，以此类推，当整除时，就得到要求的最大公约数．
试题解析：

所以8251与6105的最大公约数就是37
考点：辗转相除法求最大公约数
24．2 677
【解析】
试题分析：用秦九韶算法

求的值时:

即

则
要求值只需要做n次乘法，n次加
试题解析：f（x）=2x5-5x4-4x3+3x2-6x+7=（（（（2x-5）x-4）x+3）x-6）x+7
v1=2×5-5=5，
v2=5×5-4=21，
v3=21×5+3=108，
v4=108×5-6=534，
v5=534×5+7=2 677．
所以f（5）=2 677．
考点：秦九韶算法
25．x＝y＝1, 十进制数为11
【解析】试题分析：由二进制和三进制可知，∵10y1(2)＝x02(3)，∴1×23＋0×22＋y×2＋1＝x×32＋0×3＋2，将上式整理得9x－2y＝7，由进位制的性质知x=1或2，y=0或1．将二进制和三进制都化成十进制，再根据两数相等及x，y的范围可得x，y的值．
试题解析：
∵10y1(2)＝x02(3)，
∴1×23＋0×22＋y×2＋1＝x×32＋0×3＋2，
将上式整理得9x－2y＝7，
由进位制的性质知，
x∈{1,2}，y∈{0,1}，
当y＝0时，x＝ (舍)，
当y＝1时，x＝1.
∴x＝y＝1，已知数为102(3)＝1011(2)，
与它们相等的十进制数为
1×32＋0×3＋2＝11.
点睛：本题考查的知识点是不同进制之间的转换，其中其它进制转为十进制方法均为累加数字×权重，十进制转换为其它进制均采用除K求余法，另外要注意10y1(2)＝x02(3)由进位制的性质知，x∈{1,2}，y∈{0,1}.
视频
26．见解析
【解析】（1）要注意写算法时，分几个步骤，每个步骤的功能要搞清楚.
(2)画程序框图时，要正确画功能框,不能搞混.
解：（1）算法步骤为：
第一步：输入考试成绩C1和平时成绩C2，…………………………….2分
第二步：计算模块成绩 …………………………….4分
第三步：判断C与60的大小，输出学分F
若，则输出F=2；
若，则输出F=0.…………………………….8分
（2）程序框图：（如图）
否
是
开始
输入C1和C2

输出F
输出F
结束

………………………….14分
27．（1） 84 （2） 51
【解析】略
答案第9页，总9页