算法初步简单练习题

1. The O-notation provides an asymptotic upper bound. The -notation provides an asymptotic

lower bound. The Θ-notation asymptotically a function form above and below.

O型符号提供一个渐近的上限。Θ符号提供一个渐近下界。 Θ-符号渐近函数形式的上方和下方。

2. To represent a heap as an array，the root of tree is A[1], and given the index i of a node, the

indices of its parent Parent(i) { return i/2; }，left child, Left(i) { return 2*i; }，right child,

right(i) { return 2*i + 1; }.

代表一个堆中的一个数组，树的根节点是A[1]，并且给出一个节点i，那么该节点的父节点是 左孩子

右孩子

3. Because the heap of n elements is a binary tree, the height of any node is at most (lg n).

因为n个元素的堆是一个二叉树，任意节点的树高最多是

4. In optimization problems , there can be many possible solutions. Each solution has a value, and

we wish to find a solution with the optimal (minimum or maximum) value. We

1 / 11 算 法

算法是高中数学课程中的新增内容，是中国数学课程内容的一个新特色．“算法”过程是指机械式地按照某种确定的步骤行事，通过一系列小的简单计算操作完成复杂计算的过程．算法的学习内容大致可分为三个步骤：用自然语言描述算法；精确刻画算法(程序框图)；计算机实现执行算法(程序语言的描述过程)．算法思想贯穿高中数学课程的相关部分．

【知识要点】

1．算法：算法可以理解为由基本运算及规定的运算顺序所构成的完整的解题步骤，或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤或序列能够解决一类问题．现代意义上的“算法”通常是指可以用计算机来解决的某一类问题的程序或步骤．

2．程序框图

程序框图：用一些通用的符号构成一张图来表示算法，这种图称为程序框图(程序框图又称流程图，是一种用程序框、流程线及文字说明来表示算法的图形)．

用框图表示算法步骤的一些常用的图形符号：

程序框 名称 功能

终端框(起止框) 表示一个算法的起始和结束

输入、输出框 表示一个算法输入和输出的信息

处理框(执行框) 赋值、计算

判断框 判断某一条件是否成立，成立时在出口处标明“是”，不成立时标明“否”

↓→ 流程线(指向线) 指引流程图的方向

连接点 连接另一页或另一部分的框图

程序框图的三种基本逻辑结构：

顺序结构：描述的是最简单的算法结构，语句与语句之间、框与框之间按从上到下的顺序进行(如图9－1)．

图9－1

条件分支结构：依据指定条件选择执行不同指令的控制结构(如图9－2)． 2 / 11

图9－2

循环结构：根据指定条件决定是否重复执行一条或多条指令的控制结构(如图9－3)．

图9－3

3．几种基本算法语句

任何一个程序设计语言中，都包含五种基本的算法语句，即输入语句、输出语句、赋值语句、条件语句、循环语句．

输入语句和输出语句分别用来实现算法的输入信息、输出结果的功能；赋值语句是用来表明赋给某一个变量一个具体的确定值的语句；条件语句是处理条件分支逻辑结构的算法语句；循环语句是用来处理算法中的循环结构的语句．

高一数学算法初步试题答案及解析

1. 我国《算经十书》之一《孙子算经》中有这样一个问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二.问物几何？答曰：二十三.”你能用程序解决这个问题吗？

【答案】见解析。

【解析】设物共m个，被3，5，7除所得的商分别为x、y、z，则这个问题相当于求不定方程

的正整数解.

m应同时满足下列三个条件：（1）m MOD 3=2；（2）m MOD 5=3；

（3）m MOD 7=2.因此，可以让m从2开始检验，若3个条件中有任何一个不成立，则m递增1，一直到m同时满足三个条件为止.

程序：m=2

f=0

WHILE f=0

IF m MOD 3=2 AND m MOD 5=3

AND m MOD 7=2 THEN

PRINT “物体的个数为：”；m

f=1

ELSE

m=m+1

END IF

WEND

END

【考点】本题主要考查算法的基本概念及算法的程序语言。

点评：经典题目。在理解解方程组算理的基础上，首先用语言表示算法，再写出程序语言。

2. 下面程序的运行结果不为4的

【答案】C

【解析】本题考查的是简单程序语言的运行。

A考查的是条件语句，由a←3，b←5得b＞a，应执行c←， Print c所以运行结果为4。B考查的也是条件语句，由a←3，b←4得，应执行a←a+1，Print a所以运行结果为4。C考查的是条件语句，由a←3，b←4得a≤b，应执行c←a+b，Print c运行结果为7。故应选C。

【考点】程序中条件语句，赋值语句的运行。

点评：解决此类问题，先根据变量的初始值判断条件是否成立，然后再根据“是”和“否”分别执行的语句来计算运行结果。

3. 设计一个解关于x的方程：ax+b=0的程序．图中给出了程序的一部分，请在横线上填上适当的语句，使程序完整

．

【答案】①：x= -；②：“方程无解”；③：“解为一切实数”

1 第一章 算法初步 测试题

一、选择题

1．看下面的四段话，其中是解决问题的算法的是( ).

A．把高一5班的同学分成两组，高个子参加篮球赛，矮个子参加拔河比赛

B．把高一5班的同学分成两组，身高达到170 cm的参加篮球赛，不足170 cm的参加拔河比赛

C．把a，b的值代入x＝ab，求方程ax＝b的解

D．从2开始写起，后一个数为前一个数与2的和，不断地写，写出所有偶数

2．任何一个算法都必须有的基本结构是( ).

A．顺序结构 B．条件结构

C．循环结构 D．三个都有

3．右边的程序框图(如图所示)，能判断任意输入的整数x的奇偶性：其中判断框内的条件是( ).

A．m＝0 B．x＝0 C．x＝1 D．m＝1

4．给出以下一个算法的程序框图(如图所示)，该程序框图的功能是( ).

A．求输出a，b，c三数的最大数

B．求输出a，b，c三数的最小数

C．将a，b，c按从小到大排列

D．将a，b，c按从大到小排列

5．右图给出的是计算21＋41＋61＋ „ ＋201的值的

一个程序框图，其中判断框内应填入的条件是( ).

A．i＞10 B．i＜10 C．i＞20 D．i＜20

6．直到型循环结构为( ). 2

A

B

C D

7．下列给出的赋值语句中正确的是( ).

A．4＝M B．M＝－M C．2B＝A－3

D．x＋y＝0

8．右边程序执行后输出的结果是( ).

A．－1 B．0 C．1 D．2

9．我国古代数学发展曾曾经处于世界领先水平，特别是宋、元时期的“算法”，其中可以同欧几里德辗转相除法相媲美的是( ).