2009.1算法设计与分析课程期末试卷-A卷(自测-)

华南农业大学期末考试试卷（A卷）

2008学年第一学期考试科目：算法分析与设计

考试类型：（闭卷）考试时间：120分钟

学号姓名年级专业

一、选择题（20分，每题2分）

1.下述表达不正确的是。

A．n2/2 + 2n的渐进表达式上界函数是O(2n)

B．n2/2 + 2n的渐进表达式下界函数是Ω(2n)

C．logn3的渐进表达式上界函数是O(logn)

D．logn3的渐进表达式下界函数是Ω(n3)

2.当输入规模为n时，算法增长率最大的是。

A．5n B．20log2n C．2n2D．3nlog3n

3.T（n）表示当输入规模为n时的算法效率，以下算法效率最优的是。A．T（n）= T（n – 1）+1，T（1）=1 B．T（n）= 2n2

C．T（n）= T（n/2）+1，T（1）=1 D．T（n）= 3nlog2n

4.在棋盘覆盖问题中，对于2k×2k的特殊棋盘（有一个特殊方块），所需的L型骨

牌的个数是。

A．（4k– 1）/3 B．2k /3 C．4k D．2k

5.在寻找n个元素中第k小元素问题中，若使用快速排序算法思想，运用分治算法

对n个元素进行划分，应如何选择划分基准？下面答案解释最合理。A．随机选择一个元素作为划分基准

B．取子序列的第一个元素作为划分基准

C．用中位数的中位数方法寻找划分基准

D．以上皆可行。但不同方法，算法复杂度上界可能不同

6.

现在要盖一所邮局为这9个村庄服务，请问邮局应该盖在 才能使到邮局到这9个村庄的总距离和最短。 A ．（4.5，0） B ．（4.5，4.5） C ．（5，5） D ．（5，0）

7. n 个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水，

水流恒定。如下 说法不正确？

A ．让水桶大的人先打水，可以使得每个人排队时间之和最小

B ．让水桶小的人先打水，可以使得每个人排队时间之和最小

C ．让水桶小的人先打水，在某个确定的时间t 内，可以让尽可能多的人打上水

D ．若要在尽可能短的时间内，n 个人都打完水，按照什么顺序其实都一样

8. 分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分

别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题 。

A ．问题规模相同，问题性质相同

B ．问题规模相同，问题性质不同

C ．问题规模不同，问题性质相同

D ．问题规模不同，问题性质不同

9. 对布线问题，以下 是不正确描述。 A ．布线问题的解空间是一个图

B ．可以对方格阵列四周设置围墙，即增设标记的附加方格的预处理，使得算法简化对边界的判定

C ．采用广度优先的标号法找到从起点到终点的布线方案（这个方案如果存在的话）不一定是最短的

D ．采用先入先出的队列作为活结点表，以终点b 为扩展结点或活结点队列为空作为算法结束条件

10. 对于含有n 个元素的子集树问题，最坏情况下其解空间的叶结点数目为 。 A ．n!

B ．2n

C ．2n+1-1

D ．

∑=n

i i n 1

!/!

答案：DACAD CACCB

二、填空题（10分，每题2分）

1、一个算法复杂性的高低体现在计算机运行该算法所需的时间和存储器资源上，因此算法的复杂性有 时间 复杂性和空间复杂性之分。

2、出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致 相同 。

3、使用二分搜索算法在n 个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复杂性为O （ 1 ），在最坏情况下，搜索的时间复杂性为O （ logn ）。

4、已知一个分治算法耗费的计算时间T(n)，T(n)满足如下递归方程：

?

?

?≥+<=22221n n O n T n O n T )()/()

()( 解得此递归方可得T(n)= O （ nlogn ）。

5、动态规划算法有一个变形方法 备忘录方法 。这种方法不同于动态规划算法“自底

向上”的填充方向，而是“自顶向下”的递归方向，为每个解过的子问题建立了备忘录以备需要时查看，同样也可避免相同子问题的重复求解。

参考解答：1、时间 2、相同 3、1 logn 4、log n n 5、备忘录方法

三、简答题（40分，每题8分）

1、（8分）写出下列复杂性函数的偏序关系（即按照渐进阶从低到高排序）：

2323log !log 10n

n

n n n n n

n n

参考解答：3

210

log log 23!n n n n n n n n n p p p p p p p

2、（8分）现在有8位运动员要进行网球循环赛，要设计一个满足以下要求的比赛日程表：

（1）每个选手必须与其他选手各赛一次；

（2）每个选手一天只能赛一次；

（3）循环赛一共进行n – 1天。

请利用分治法的思想，给这8位运动员设计一个合理的比赛日程。

参考解答：

3、（8分）某体育馆有一羽毛球场出租，现在总共有10位客户申请租用此羽毛球场，每个客户所租用的时间单元如下表所示，s(i)表示开始租用时刻，f(i)表示结束租用时

同一时刻，该羽毛球场只能租借给一位客户，请设计一个租用安排方案，在这10位客户里面，使得体育馆能尽可能满足多位客户的需求，并算出针对上表的10个客户申请，最多可以安排几位客户申请。

1）选择申请1（1,4）

2）依次检查后续客户申请，只要与已选择的申请相容不冲突，则选择该申请。直到所有申请检查完毕。申请4（5,7）、申请8（8,11）、申请10（11,13）

3）最后，可以满足：申请1（1,4）、申请4（5,7）、申请8（8,11）、申请10（11,13）共4个客户申请。这已经是可以满足的最大客户人数。

4、（8分）对于矩阵连乘所需最少数乘次数问题，其递归关系式为：

1i k j

0[,]min{[,][1,]}i k j i j m i j m i k m k j p p p i j -≤<=??

=?+++

其中m[i ，j]为计算矩阵连乘Ai …Aj 所需的最少数乘次数，p i-1为矩阵Ai 的行，i p 为矩阵Ai 的列。现有四个矩阵，其中各矩阵维数分别为：

请根据以上的递归关系，计算出矩阵连乘积A 1A 2A 3A 4所需要的最少数乘次数。

参考解答：

014024034[1][1][2][4]080005010510500[1][4]min [1][2][3][4]2000060005040536000

[1][3][4][4]270000503053450010500

m m p p p m m m p p p m m p p p ++=++??=??

=++=++??=??++=++??=?

=

5、（8分）有这样一类特殊0-1背包问题：可选物品重量越轻的物品价值越高。

n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。

其中n 为物品个数，c 为背包载重量，P 表示物品的价值，W 表示物品的重量。请问对于此0-1背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大，能获得的最大总价值多少？

参考解答：因为该0－1背包问题比较特殊，恰好重量越轻的物品价值越高，所以优先取重量轻的物品放进背包。最终可以把重量分别为2，3，4，5的三个物品放进背包，得到的价值和为15 + 8 + 6 + 4 = 33，为最大值。

四、算法设计题（30分，前三题每题8分，最后一题6分）

1、【最优服务次序问题】（8分）—— 提示：此题可采用贪心算法实现

问题描述：设有n 个顾客同时等待一项服务，顾客i 需要的服务时间为ti ，1<=i<=n 。

应该如何安排n 个顾客的服务次序才能使平均等待时间达到最小？（平均等待时间是n 个顾客等待服务时间的总和除以n ）。

参考解答：贪心策略：最短服务时间优先。

将n 个顾客的服务时间ti 按照由小到大排序，n 个顾客的服务调度方案即为排序后的顺序，即可使得平均等待时间最小。

评分准则：

1) 答到使用贪心算法，并且说明贪心的策略是短服务优先，本题即可得满分； 2) 仅说明使用贪心算法，但未说明贪心策略，答题不完整，扣2分以上； 3) 其它情况酌情考虑。

2、【Gray 码构造问题】（8分）—— 提示：此题可采用分治递归算法实现 问题描述：“格雷码”是一个长度为n 2的序列，满足：

（a ）每个元素都是长度为n 比特的串

（b ）序列中无相同元素

（c ）连续的两个元素恰好只有1个比特不同 例如：n=2时，格雷码为{00，01，11，10}。

Gray 码是一种编码，这种编码可以避免在读取时，因各数据位时序上的差异造成的误读。格雷码在工程上有广泛应用。但格雷码不便于运算，请你设计一种构造方法，输入长度序列n ，输出格雷码（你只要做出一种构造方案即可，格雷码并不唯一）。

参考解答： 此题可用分治法解决。 当n ＝1时，输出格雷码{0, 1}

当n>1时，格雷码的长度为n

2，即共有n

2个码序列。此时，将问题一分为二，即上半部分和下半部分。上半部分最高位设为0，下半部分最高位设为1。剩下n-1位的格雷码的构造采用递归的思路。

评分准则：

1) 答到使用分治算法，并且推导出分治算法的过程，边界设定清晰（即当仅输

出1位的格雷码如何处理），本题即可得满分； 2) 说明使用分治算法，但漏边界条件，扣2分以上； 3) 其它情况酌情考虑。

3、【最长上升子序列问题】（8分）—— 提示：此题可采用动态规划算法实现

对于给定的一个序列12(,,,)N a a a L ，11000N ≤≤。我们可以得到一些递增上升的子序列12(,,,)i i iK a a a L ，这里121K i i i N ≤<<<≤L 。比如，对于序列(1, 7, 3, 5,

9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，

比如子序列(1, 3, 5, 8)。你的任务：就是对于给定的序列，求出最长上升子序列的长度。要求写出你设计的算法思想及递推函数的公式表达。

参考解答：设()f i 表示：从左向右扫描过来直到以[]a i 元素结尾的序列，获得的最长上升子序列的长度，且子序列包含[]a i 元素（1i n ≤≤）。

11()max{()1:[][];1}111;(1)[][]i f i f j a i a j j i i i j j i a i a j =?

?

=+>≤<>??>?≤<<=?

当,都有

即，()f i 是从(1)f ，(2)f ……到(1)f i -中找最大的一个值，再加1。或者就是1。主要是看a[i]这个元素能否加入到之前已经获得的最长上升子序列，如果能加入，是之前已获得的最长上升子序列长度加一；如果不能加入，就取这最后一个元素作为一个单独子序列，长度为1。

最后，所要求的整个序列的最长公共子序列长度为max{f(i): 1<=i<=n}

评分准则：

1) 答到使用动态规划算法，并且推导出动态规划算法的递推函数公式表达，边

界设定清晰，本题即可得满分；（阅卷时仔细看递推公式表达，公式表达含义正确即可，因其表达形式可能不唯一）

2) 说明使用动态规划算法，但对递推函数表达错误或含糊，扣2分以上； 3) 其它情况酌情考虑。

4、【骑士问题】（6分）—— 提示：此题可采用广度优先搜索算法实现

在一个标准8×8的国际象棋棋盘上，棋盘中有些格子是可能有障碍物的。已知骑士的初始位置和目标位置，你的任务是计算出骑士最少需要多少步可以从初始位置到达目标位置，若无法到达目标位置，输出“not reachable ”。请用文字或伪代码说明你的算法。

注意：骑士只能进行“日”字行对角跳，棋盘上有障碍物的格子不能到达。

图（a）：骑士能进行的“日”字行对角跳，n为骑士当前位置，x为骑士下一步可以跳到的格子

图（b）：骑士从初始位置n到目标位置N，最小需要7步的实例。b为棋盘障碍

参考解答：这也是一个搜索的题目，非常类似于书上的“布线问题”，可参考书上此例。

用一个二维数组board[12][12]来记录棋盘的状况。

为何大小是12*12呢？棋盘大小8*8，为了减少对周围边界的判断，在上下左右四边各加上2行2列做“围墙”（障碍），因此board棋盘的大小12*12。

有如下几个步骤需要解决：

1)障碍格子：将输入的障碍格子填写到board当中对应格上，设置为-1；

2)起始格子和结束格子：将起始点start和结束点end，这两个点记录下来，

在board中这两个格子设置为0；

3)围墙：在8*8的棋盘外面，上下左右各加2行2列做围墙，围墙和障碍一样，

设置为-1；

4)除障碍围墙起始结束格子这些格子特殊对待输入之外，其余格子全部初始化

为0；

5)队列初始为空。队列是用来在骑士做“日字型”对角跳的时候，候选位置放

入队列中的一个辅助的数据结构，以便于“广度优先搜索”。

6)从起点开始，将这个位置所能跳的周围8个位置都检查一下：只要未标记，

就标记为前一个位置值加1，并将该格子位置加入队列；如果不能标记（比如障碍或围墙等），就跳过，继续检查下一个位置，一共骑士所能跳的8个位置。

7)取出队列首个位置结点，又继续检查这个结点周围的8个位置，类同上一步，

直到找到对终点标记位置。

8)最后，输出终点所标记的数值（正数），就是骑士所需的最少移动步数，若为

0表示终点无法标记到，输出：“not reachable”这样的信息。

评分准则：

1)答到使用搜索算法，并且说明采用广度优先的搜索策略，算法描述清晰准确，

本题即可得满分；

2)算法表达含糊或不准确，扣2分以上；

3)其它情况酌情考虑。

课程与教学论期末试题

课程与教学论期末考试题2 专业：教育管理(本) / 课程与教学论人气指数：185 中央广播电视大学2007—2008学年度第一学期“开放本科”期末考试(半开卷) 小学教育等专业课程与教学论试题 一、填空(每空1分，共10分) 1．典型的课程与教学论的研究方法包括——、观察研究法、————、人种学研究法。 2．课程资源是教学内容的直接来源，它包括——和————。 3．所谓教学手段，是指师生为实现预期的教学目的，开展教学活动、相互传递信息的 ——、——或设备。 4．一般情况下，课堂气氛可以分为积极的、消极的和——三种类型。 5．一个完整的教学模式应包含理论基础、——、实现条件、活动程序和评价等五个要素。 6．在课堂教学中，教师的非言语表达艺术是非常丰富的，它一般要通过一一——、手 势、面部表情、——和体态等来表达。 二、判断题(每小题2分，共10分。在每小题后面的括号内，根据自己的判断填上“正”或“误”) 1．生成性目标在英国著名课程论专家泰勒的理论中得到了发展和传播。( ) 2．杜威是最早为分科课程提供心理学理论基础的人。( ) 3．比较典型的实行中央集权型课程管理模式的国家为法国。( ) 4．教学过程就是一个认识的过程。( ) 5．教学评价不是教育行政主管部门的职责。( ) 三、简答题(每小题10分，共40分) 1．什么是隐性课程? 2．综合实践活动的含义与内容是什么？ 3．简述教学过程的基本阶段。 4．简述教学艺术的特征。 四、论述题(每小题20分，共40分) 1．试举例分析影响课程实施的因素。 2．试述课程与教学内容选择的依据。

试卷代号：1155 中央广播电视大学2007—2008学年度第一学期“开放本科”期末考试[半开卷) 小学教育等专业课程与教学论试题答案及评分标准 (供参考) 2008年1月 一、填空题(共6小题，共lo分) 1．调查研究法实验研究法 2．素材性资源条件性资源 3．工具媒体 4．对抗 5．功能目标 6．副语言眼神 二、判断题(共5小题，共10分) 1．错 2．错 3．对 4．错 5．错 三、简答题(共4小题，共40分) 1．隐性课程：隐性课程也叫隐蔽课程、无形课程等，是指学生在学习环境(包括物质环境、社会环境和文化体系)中所学习到的非预期或非汁划性的知识、价值观念、规范和态度，是计划表上看不到的课程。 2．综合实践活动的含义与内容 综合实践活动：主要指以学生的兴趣和直接经验为基础，以与学生学习生活和社会生活密切相关的各类现实性、综合性、实践性问题为内容，以研究性学习为主导的学习方式，以培养学生的创新精神、实践能力及体现对知识的综合运用为主要目的的一类新型课程。包括：信息技术教育，研究性学习，社区眼务与社会实践，劳动与技术教育。 3．教学过程的基本阶段 心理准备阶段；感知知识阶段；理解知识阶段；巩固知识阶段；运用知识阶段；检查与评价学习效果阶段。 4．教学艺术的特征 (1)教学艺术的创造性。(2)教学艺术的形象性。(3)教学艺术的情感性。(4)教学艺术

学校校本课程开发与实施实施方案

学校校本课程开发与实施方案

————————————————————————————————作者：————————————————————————————————日期： 2

天水市枣园巷小学学校课程开发与实施方案 校本课程是学校自主开发的一门课程，由学生自主参加，以学生活动为主，它与必修课程一起构成学校课程体系。但它与必修课程在内容、要求的深广程度和活动形式的灵活程度等方面又不尽相同。校本课程更突出学生的自主性、自愿性和灵活性。按照中共中央国务院关于深化教育改革全面推进素质教育的决定》和《国家基础教育课程改革纲要》的要求，学校开发校本课程将对培养学生的兴趣特长、创新思维习惯和实践能力，培养学生分析和解决问题的能力以及团结协作和社会活动的能力，全面提高学生的素质，发现和培养人才具有重要意义。 一、培养目标 1．培养学生的兴趣、爱好，发展个性特长。 2．拓展学生的知识领域，培养创新精神和实践能力。 3．提高学生的思想品德修养和审美能力，陶冶情操、增进身心健康。 4。培养学生的科学态度和精神，学习和掌握科学的基本知识、基本技能和方法。 5．培养学生的团结协作和社会活动能力，使学生热爱学校生活，适应社会。 二、校本课程开发和实施

1，建立领导机构。成立由校长、教师、课程专家、家长共同组成的学校课程开发和实施领导小组，由校长任组长，具体负责校本课程的开发和实施。领导机构的职能是：（1）为校本课程开发和实施提供组织保障和领导保障，组织教师积极参与学校课程开发；（2）负责对校本课程的审议；（3）负责确定学校课程开发内容，审议教师的课程纲要或活页材料；（4）负责协调学校课程开发工作，使校本课程开发具有合理性、创新性。 2、培训师资 （1）对教师进行课程理论的培训。让教师初步掌握课程的一些基本原理，明确课程目标、课程内容、课程实施、课程常识、课程探究等基本原理，为课程开发提供理论依据。（2）对教师进行专业知识培训，不断拓宽知识。 3、课程的开发和实施程序 （1）前期论证 既对所开发的校本课程进行前期论证。论证主要从两个方面：一是将开发的目的、意义、项目报市课程开发项目领导小组，经领导小组讨论认定；二是将开发的课程拿到学生中去征求意见，看所开课程学生是否喜欢，是否需要。 （2）确定题目，搜集资料 校本课程的开发首先需要明确主题、范围与领域。主题的确立首先考虑以下因素：一是学生的内在需要。检验任何一类课程是否成功的标志很多，但学生的需要必须放在首要

中科院陈玉福计算机算法设计与分析期末简答题答案

1. 贪心算法和动态规划算法有什么共同点和区别？它们都有那些优势和劣势？ 共通点：动态规划和贪心算法都是一种递推算法，均有局部最优解来推导全局最优解 区别：贪心算法中，作出的每步贪心决策都无法改变，每一步的最优解一定包含上一步的 最优解，而上一部之前的最优解则不作保留。 动态优化算法，全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解 动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率。但它需要计算之前所有情况花费，更加耗费空间。 贪心算法所作的选择依赖于以往所作过的选择,但决不依赖于将来的选择,这使得算法在编 码和执行过程中都有一定的速度优势。贪心算法是只是找局部最优解，不一定是全局最优解。 2. 试比较回溯法与分枝限界算法，分别谈谈这两个算法比较适合的问题？ 二者都是在解空间树里搜索问题的可靠解或最优解，但是搜索的方式不同，回溯法采用深 度优先的方式，直到达到问题的一个可行解，或经判断沿此路径不会达到问题的可行解或最优解时，停止向前搜索，并沿原路返回到该路径上最后一个还可扩展的节点，然后，从该节点出发朝新的方向纵深搜索。分枝限界法采用的是宽度优先的方式，它将活节点存放在一个特殊的表中，其策略是，在扩展节点处，首先生成其所有的儿子节点，将那些导致不可行解或导致非最优解的儿子节点舍弃，其余儿子节点加入活节点表中，然后，从活节点中取出一个节点作为当前扩展节点，重复上述节点中扩展过程。可以看出，回溯法一般用于求问题的一个可行解，而分枝限界可以用于求出问题的所有可行解。 3. 何谓最优化原理？采用动态规划算法必须满足的条件是什么？动态规划算法是通过什 么问题的什么特性提高效率的？ 一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。最优子结构性质，子问题重叠性质是计算模型采用动态规划算法求解的两个基本要素。 动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率 4. 什么是多项式时间算法？ 若存在一个常数C，使得对于所有n>=0，都有|f(n)| <= C*|g(n)|，则称函数f(n)是O(g(n))。时间复杂度是O(p(n))的算法称为多项式时间算法，这里p(n)是关于n的多项式。 时间复杂度为O(nlog(n))、O(n^3)的算法都是多项式时间算法，时间复杂度为O(n^log(n))、O(n!)、O(2^n)的算法是指数时间算法。 一个优化问题如果已经找到了多项式时间算法，则称该问题为多项式时间可解问题，并 将这类问题的集合记为P，因此多项式时间可解问题就称为P类问题。。

算法设计与分析实验报告贪心算法

算法设计与分析实验报告 贪心算法 班级：2013156 学号：201315614 姓名：张春阳哈夫曼编码 代码 #include float small1,small2; int flag1,flag2,count; typedefstructHuffmanTree { float weight; intlchild,rchild,parent; }huffman; huffmanhuffmantree[100]; void CreatHuffmanTree(intn,int m) { inti; void select(); printf("请输入%d个节点的权值:",n); for(i=0;i

printf("\n"); for(i=0;i

小学六年级下册综合实践期末试题

小学六年级综合实践试题 一、填空（每空2分，共10分） 1、常用的收集资料的方法有（）、（）、（）。 2、综合实践活动课程是以（）为主要形式展开的。 3、综合实践活动课程是由教师和（）合作开发与实施的课。 4、按照国家课程规定，小学综合实践活动课程平均每周( )课时。 5、对于不同年级的小学生实施综合实践活动课程，教师的指导应该有不同，即年级越低，指导的力度应越（）。 二、选择（每题1分，共10分） 1、实施一项研究的一般步骤有哪些？（） A、确立研究主题，制定研究方案和计划； B、实施研究过程； C、汇报交流研究成果； D、体味反思研究中的问题。 E、以上都是。 2、采访访问有哪些常见形式？（） A对话式B、座谈会C、问卷式D、问答式E、以上都是 3、实施研究过程一般有哪些研究方法？（） A、收集整理资料 B、采访访问 C、社会调查 D、以上都是 4、下列哪一项不属于综合实践活动课程特点（） A、综合性 B、实践性 C、知识性 D、自主性 E、生成性 F、开

放性 5、下列说法中，不正确的是（） A.综合实践活动课程是一种经验性课程 B.综合实践活动课程是一种实践性课程 C.综合实践活动课程是一种向学生生活领域延伸的综合性课程 D.综合实践活动课程是校本课程 6、综合实践活动课程主题选择不应该遵循的原则是（）。 A、尊重每个学生兴趣、爱好和特长； B、反映学校所在地区特色； C、有利于体现教师的教学特色； D、引导学生从日常生活中选取探究课题或问题； 7、下列哪一项不属于综合实践活动课程指定领域包括的内容（）。 A、研究性学习； B、社区服务和社会实践； C、劳动和劳动技术教育； D、语文综合性学习活动； E、信息技术教育； 8、下列哪项不符合综合实践活动课程评价基本理念的是（） A、整体覌 B、多元化 C、过程性 D、知识性

落实国家课程开发校本课程实施方案

落实国家课程开发校本课程 ——课程建设方案 学校课程建设是学校提升综合办学能力的一项重要工作。学校要树立“无处不课程、无事不课程、无时不课程”的大课程观。教育部副部长陈小娅在《努力成长为新时代的人民教育家》一文中曾提到：“一定要把学校的一切工作都变为教育的机会和手段，让教师的一言一行，让学校的一砖一石、一草一木、一角一景都体现着教育。……”。为了学生的健康成长，学校课程建设不可或缺。根据党的教育方针，以及《山东省中小学课程建设方案》、莘县教育局（2010）29号等文件精神，从学校实际情况与办学特色出发，贯彻“三个着眼于”，即着眼于促进学生全面而有个性发展、着眼于促进教师教学实践能力的提高、着眼于促进学校课程整体育人功能的提升，制定《实验小学课程建设方案》，全面推进以创新精神与实践能力为核心的素质教育。 一、指导思想 坚持邓小平理论和“三个代表”的重要思想，以科学发展观指导学校课程建设。面向全体师生，以师生的可持续发展与幸福成长为课程建设之宗旨。加强校本研训，提高教师素养，探索国家课程校本化实施，开发校本课程，以合格课程建设为基础，打造学校精品课程。追求学校特色，提升办学品位，推进素质教育的全面开展。 二、课程建设目标 （一）总目标 通过国家课程的校本化实施与校本课程的开发：提供丰富而适性的课程，使学校课程结构更合理，学校特色更鲜明；使教师的教学理念进一步更新、教学手段进一步优化，跟上时代发展的步伐；使每一位独具个性的学生在道德、身体、智力、情感等方面得到充分发展，为在多样化社会中做一个终身学习者和负责任的公民作好准备。 （二）学生培养目标 以“让每一个孩子插上创造的翅膀”为办学理念，让学生在学习活动中“学会做人、学会学习、学会合作、学会创造”，使学生的文化知识、学习习惯、学习技能、意志品质、创造能力等方面得到进一步的提升。

算法设计与分析试卷(2010)

算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： B 、D A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ C 、D A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： ABCD A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： C A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T

算法设计与分析课程设计报告样本

课程设计报告 课程设计名称: 算法设计与分析 系 : 三系 学生姓名: 吴阳 班级: 12软件(2)班 学号: 0311232 成绩: 指导教师: 秦川 开课时间: 年一学期 一、问题描述 1．普通背包问题

给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。选择装入的背包的物品, 使得装入背包中的物品的总价值最大, 在选择物品i装入背包时, 能够选择物品i的一部分, 而不一定要全部装入背包, 1≤i≤n。 2．0/1背包问题 给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。选择装入的背包的物品, 使得装入背包中的物品的总价值最大, 在选择物品i装入背包时, 对于每种物品i只有两种选择, 即装入背包或者不装入背包, 不能将物品装入背包多次, 也不能只装入部分的物品i。 3．棋盘覆盖问题 在一个2k x 2k个方格组成的棋盘中恰有一个方格与其它的不同称为特殊方格, 想要求利用四种L型骨牌( 每个骨牌可覆盖三个方格) 不相互重叠覆盖的将除了特殊方格外的其它方格覆盖。 二、问题分析

1．普通背包问题 对于背包问题, 若它的一个最优解包含物品j, 则从该最优解中拿出所含的物品j的那部分重量Ｗ, 剩余的将是n-1个原重物品1, 2, ······, j-1, j+1, ·····, n以及重为Ｗi－Ｗ的物品j 中可装入容量为C－Ｗ的背包且具有最大价值的物品。 2．0/1背包问题 如果当前背包中的物品的总容量是cw, 前面的k-1件物品都已经决定好是否要放入包中, 那么第k件物品是否放入包中取决于不等式 cw + wk <= M (其中, wk为第k件物品的容量, M为背包的容量)( 此即约束条件) 然后我们再寻找限界函数, 这个问题比较麻烦, 我们能够回忆一下背包问题的贪心算法, 即物品按照物品的价值/物品的体积来从大到小排列, 然后最优解为( 1, 1, 1......., 1, t, 0, 0, ......) , 其中0<=t<=1; 因此, 我们在确定第k个物品到底要不要放入的时候(在前k-1个物品已经确定的情况下), 我们能够考虑我们能够达到的最大的价值, 即我们能够经过计算只放入一部分的k物品来计算最大的价值。我们要确保当前选择的路径的最大的价值要大于我们已经选择的路径的价值。这就是该问题的限界条件。经过该条件, 能够减去很多的枝条, 大大节省运行时间。 3．棋盘覆盖问题 每次都对分割后的四个小方块进行判断, 判断特殊方格是否

校本课程实施方案

校本课程实施方案 导读：范文校本课程实施方案 【篇一：校本课程实施方案】 一、指导思想： 以新一轮课程改革“一切为了学生，一切为了学生的发展”的教育理念为指导，从学校的实际状况和学生的实际需要出发，构建学校办学特色，打造“个性化”学校形象，发展学生特长，促进学生全面发展，以适应社会进步，科教发展，教育改革的客观要求。 二、实施目标： 1、校本课程要体现基础性： 基础教育要重视基础，校本课程将立足于打好学生文化基础、品德基础、身心基础为目标。全面发展学生的能力，促进学生对学科知识的综合和运用。 2、校本课程要体现发展性：

根据学校实际状况，兼顾到每个学生的发展需要，树立着眼于学生发展的教育价值观，把为学生的发展服务当作校本课程的基本价值取向。 3、校本课程要体现现实性： 校本课程是根据学校的实际情况而开设了课程，在开发过程中主要依靠学校的自身力量来完成，所以要充分考虑本校老师队伍的整体实力，科研水平及学生的发展情况，还有学校的设备资金等因素，目标不能远离实际。 4、校本课程要体现主体性： 校本课程的主体性体现在课程的开发和实施需要，教师的充分参与，在课程的开发和实施中要重视教师的主动精神，要发扬团结协作的精神，使校本课程得到更大的开发。同时，还要充分了解和反映学生的实际，重视学生参与，注意学生的反馈信息，不断根据学生的需要完善优化校本课程。 三、实施内容： 、建立健全校本课程开发体系

校本开发不是一两个人能完成的，是由校长、课程专家、教师、学生家长等共同参与的。学校要形成开发校本课程的组织网络，形成领导小组——教研组——教师——学生的开发网络，通力合作，共同创建“学习化校园”。 1、成立课程开发领导小组 组长：蒋志敏 副组长：乔磊、赵春丽 组员：班主任、自然、社会、综合实践课程等相关教师 2、成立课程开发研究小组 组长：蒋志敏 副组长：乔磊赵春丽 组员：班主任、自然、社会、综合实践课程等相关教师

计算机算法设计与分析期末考试复习题

1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 5. 回溯法解TSP问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、实现最长公共子序列利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解14．广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．背包问题的贪心算法所需的计算时间为（ B ）。

六年级上学期综合实践活动期末试题及答案

六年级上学期综合实践活动期末试题及答案 一．填空 1、综合实践活动课程是由教师和（）合作开发与实施的课。 2. 沙包的缝制过程包括：裁剪布片，缝合，翻面，（），封口。 3、不同年级的小学生实施综合实践活动课程，教师的指导应该有不同，即年级越低， 指导的力度应越（）。 4、综合实践活动课程是以（）为主要形式展开的。 5、在寿司课上我们制作寿司需要准备的材料包括：熟米饭、寿司醋、黄瓜、胡萝卜、 盐、醋、香肠、寿司帘、（）。 二、选择题。 1．你认为综合实践活动会让你：（） A．学会更多知识，开拓视野，锻炼能力B．学不到什么东西 2、口语表达的要求与技巧是（） A语言要做到清晰、流畅、响亮。 B用自己的语言表达，态度亲切、自然。 C通过加大音量、音节拖长、停顿和连接，增强表达的效果 D注意节奏的变化，控制好语气。 E适当运用眼神、手势，身体等作为表达的辅助手段。 F以上都是

3、研究报告的基本形式包括（） A研究题目B参加人员C研究过程D研究结论E以上都是 4、撰写研究报告时要注意的方面是：（） A一是内容要详略得当、主题鲜明；B二是对研究过程作适当分析； C三是组织材料要条理分明D、以上都是 5、下列说法中，不正确的是（） A.综合实践活动课程是一种经验性课程 B.综合实践活动课程是一种实践性课程 C.综合实践活动课程是一种向学生生活领域延伸的综合性课程 D.综合实践活动课程就是校本课程 三：判断题 1、低碳生活是一种生活方式，更是一种生活态度，我们应该提倡。（） 2、低碳的解释是：较低或更低的温室气体（二氧化碳为主）的排放。（） 3、沙包的正确缝制步骤是：翻面，装填充物，裁剪布片，缝合，封口。（） 4、综合实践课就是美术课。（） 5、综合实践活动强调学生的亲身经历。（）四：连线题（综合实践活动课程作为必修课，其内容范围包括：“研究性学习”、“社区服务与社会实践”、“劳动与技术教育”、“信息技术教育”，请结合你的学习知识和生活经验答题）

小学校本课程开发方案

小学校本课程《山水古诗文赏读》开发方案 一、开发的目的 在中国五千年的悠久文化中,山水古诗文不仅映射着中国文化的文学之美,而且能使孩子们渐渐懂得“人伦之道”的“做人”道理,懂得“生存之道”的“生活”艺术,懂得人生进入“文学”化的境界。 基于以上认识,学校将构建具有个性化的、本土化的校本课程:《走进山水古诗文》,并努力将古诗文教育与培养学生良好习惯、高尚情操、优秀品格的人文教育有机地融合,着力培养一代“腹有诗书气自华”的少年君子。具体目标: 1、激发学生学习语文、运用语言的兴趣; 2、培养学生良好的诵读习惯; 3、提高学生的言语感知与领悟能力; 4、激发学生的想象力与创造力; 5、培养学生对祖国语言文字的热爱; 6、培养学生的道德情感。 二、课程开发过程 校本教材内容既选取课程标准规定的必背篇目,也选取大量外籍名人诗篇。学生们不仅能读到《送孟浩然之广陵》、《望庐山瀑布》这样流传千古的经典诗篇,还能读到许多虽不知名的优美的诗篇。 我校古诗文教育的宗旨就就是“以人为本”,根据“学生的兴趣与需要”来制定校本课程,创建具有学校特色的教材体系。因此在总结平时开展的实践活动的基础之上,可以在每篇诗文之后,根据教材内容,提供一个个个性鲜明的实践活动方案,如安排“请您画一画”、“请您填一填”等。这些精心设计的实践活动方案,可以极大地调动学生诵读诗文的兴趣,提高诵读的效果。 三、课程内容框架

为适合学生阅读,根据学生年龄的特点,共编写低、中、高三册教材,在内容编排上也体现一定的层次性,采取按年级、按内容分单元编排,努力做到循序渐进。 1、具体内容 1、《黄河》【宋】王安石 派出昆仑五色流,一支黄浊贯中州。吹沙走浪几千里,转侧屋闾无处求。 2、《浪淘沙》【唐】刘禹锡 九曲黄河万里沙,浪淘风簸自天涯。如今直上银河去,同到牵牛织女家。 3、《黄河二首》【唐】杜甫 黄河北岸海西军,椎鼓鸣钟天下闻。铁马长鸣不知数,胡人高鼻动成群。 黄河西岸就是吾蜀,欲须供给家无粟。愿驱众庶戴君王,混一车书弃金玉。 4、《咏史诗·黄河》【唐】胡曾 博望沉埋不复旋,黄河依旧水茫然。沿流欲共牛郎语,只得灵槎送上天。 5、《望岳》【唐】杜甫 岱宗夫如何？齐鲁青未了。造化钟神秀,阴阳割昏晓。 荡胸生层云,决眦入归鸟。会当凌绝顶,一览众山小。 6、《泰山吟》【南朝】谢灵运 泰宗秀维岳,崔崒刺云天。岞崿既崄巘,触石辄迁绵。 登封瘗崇坛,降禅藏肃然。石闻何吨蔼,明堂秘灵篇。 7、《望天门山》【唐】李白 天门中断楚江开,碧水东流至此回。两岸青山相对出,孤帆一片日边来。 8、《早发白帝城》【唐】李白 早辞白帝彩云间,千里江陵一日还。两岸猿声啼不住,轻舟已过万重山。 9、《黄鹤楼送孟浩然之广陵》【唐】李白 故人西辞黄鹤楼,烟花三月下扬州。孤帆远影碧空尽,唯见长江天际流。 10、《题天柱峰》【唐】白居易 太微星斗拱琼台,圣祖琳宫镇九垓。天柱一峰擎日月,洞门千仞锁云雷。 玉光白橘相争秀,金翠佳莲蕊斗开。时访左慈高隐处,紫清仙鹤认巢来。 11、《望洞庭》【唐】刘禹锡 湖光秋月两相知,潭面无风镜未磨。遥望洞庭山水翠,白银盘里一青螺。 12、《使至塞上》【唐】王维 单车欲问边,属国过居延。征蓬出汉塞,归雁入胡天。 大漠孤烟直,长河落日圆。萧关逢候骑,都护在燕然。

算法设计与分析课程设计报告

压缩软件课程设计书 一、问题描述： 建立一个文本文件，统计该文件中各字符频率，对各字符进行Huffman编码，将该文件至翻译成Huffman编码文件，再将Huffman编码文件翻译成原文件。 二、算法分析及思路： 对于该问题，我们做如下分析： （1）首先得构造出哈弗曼树，我们用函数HuffmanTree(int w[],int s[],int n)设计；（2）在构建哈弗曼树的基础上，进一步实现哈弗曼编码问题，我们用函数Huffmancode(char wen[])设计； （3）实现哈弗曼编码后再进一步实现哈弗曼译码问题，我们用函数Huffmandecode()设计； （4）其中编码问题中，得进一步统计出各个字符在文件中的频率，并进行一些必要的标记，我们用函数runhuffman(char wen[])设计； （5）在译码过程中，还有必要的一步是比较原文件与译码后的文件是否相同，我们用函数compare(char wen[])设计； （6）其中的文件输入我们用到类”fstream.h”中的输入输出流，并在运行的文件夹中建立一个文件名为逍遥游的文本文件，且在逍遥游文件中输入需要编码的数据。 三、主要解决的设计问题： 1.写一个对txt文件压缩和解压的程序，使用动态编码。 2.使用Huffman编码压缩和解压时，Huffman树的存储可以直接存储树结构，也可以存储所有字符的频度或权值，然后读取时建立Huffman树； 3.使用Huffman编码压缩和解压时，注意定义压缩码的结束标记，可以使用一个特殊的字符作为结束标记，也可以在压缩码之前存储其比特长度；如果使用一个特殊字符作为结束标记，则其频度为1，需要在建立Huffman树时把它看作一个独立的字符进行建树。 4.使用Huffman编码压缩和解压时，在一个缓冲区里面收集压缩码比特流，每当收集的比特数满8时，可以把这8比特通过位操作合并成一个字节写入文件（当然也可以收集满一定数目的字节后再写入文件）。写入文件的最小信息单位为字节。 四、程序设计的流程图：

(3)--《课程与教学论》期末试卷A卷及参考答案

河南大学《课程与教学论》试卷（A卷） 一、单项选择题（每题1分，共15分） 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．科学主义 6、提出最近发展区理论假设的教育家是（ ） A．巴班斯基B．维果茨基C．凯洛夫D．列昂节夫 7、范例教学的三个基本特性是( ) A．全员性、基本性、范例性 B．基本性、全面性、范例性

C．个体性、基础性、范例性 D．基本性、基础性、范例性 8、在课程开发或课程实施过程中时所采用的评价是（ ） A． 内在评价 B．总结性评价 C．诊断性评价 D．形成性评价 9、在非指导性教学中，教师是作为( )存在的。 A．先知者 B．管理者 C．促进者 D．指导者 10、 文纳特卡制的创立者是（ ） A．巴班斯基 B．布鲁姆 C．华虚朋 D．瓦根舍因 11、浪漫自然主义经验课程的代表人物是（ ） A．杜威 B．卢梭 C．斯宾塞 D．夸美纽斯 12、在课程开发与教学设计中，体现教育价值的是（ ） A．教育目的 B．教育目标 C．课程与教学目标 D．课时目标 13、以学习小组为教学活动的基本单位，通过小组内成员的分工协作去达成小组共同目标，并以小组活动的整体效果为教学评价主要指标的教学策略是（） A．合作学习策略 B.活动性策略 C.生活性策略 D.教学互动策略 14、有意识地运用两种或两种以上学科的知识观和方法论去考察和探究一个中心主题或问题。具有这种课程取向的课程类型称为（ ）

学校校本课程设计方案

长葛市第十四中学校本课程课程 开发方案 为了切实推进课程改革,贯彻落实《义务教育地方课程与学校课程设置指导意见》文件精神,结合我校实际,建立校本课程与地方课程相结合得课程体系,特制订本方案,具体内容如下: 一．课程目标: 1、充分利用学校得课程资源与人力资源,加强课程与地方经济、社会、学生生活得联系。 2、拓展学生得知识领域,提高学生得科学精神与人文素养、创新精神与实践能力,形成良好得审美情趣。 3、激发学生热爱家乡得情感,增强对地方与社会发展得责任感、使命感。 4、促进教师队伍建设,增强教师得课程意识,鼓励教师组合校本课程开发团队。 5、通过教师培训,提高课程开发与实施得能力,打造系统得校园文化,进而形成学校办学特色。 二、组织保障: 1、成立校本课程改革工作领导小组,全面负责对新课程作出正确决策与部署,在经费投入、政策支持、办学条件、制度建设、师资培训、舆论宣传等方面提供保障,对实验过程予以指导与调控。 2、成立校本课程领导小组,全面负责开发与实施具有地域特色、适应学校特点得地方课程与校本课程,促进学校办学特色。并对教师所实施得校本课程进行督导与评价,适时给出指导性意见。

3、成立课程指导委员会,负责对各年级得课程计划形成建议并组织反馈;优化整合现有资源,开发建设新型课程资源。 4、学校有完善得教研组、备课组制度,定期交流研讨,全面落实学校各级教学任务。 三、课程设置?校本课程: (一)开发原则: 1、实效性原则。严格执行国家得课程政策,遵循课程开发得规律。 2、互补性原则。要充分体现出对国家课程得补充作用,发挥其自身优势,使国家课程与校本课程能相互协调地发挥整体育人功能。 3、针对性原则。校本课程得开发要从我校得实际与学生得需要出发,强调有利于形成学校得特色,发展学生得个性特长与需要。 (二)开发目标: 1、与国家课程、地方课程相互整合与补充,以加强课程结构得综合性与多样性。 2、通过校本课程得开发,凸现学校办学特色。 3、培养一批复合型、科研型得教师。 4、全面实施素质教育、倡导学生主动参与、交流、合作、探究等多种学习活动,改进学习方式,拓展学生得知识领域,培养创新精神与实践能力,使学生真正成为学习得主人。 5、培养学生得团结、合作意识,提高学生得思想品德修养与审美能力,陶冶情操、增进学生身心健康,使学生热爱学校生活,适应社会环境。 (三)开发得内容类别:

算法设计与分析期末试题答案解析

1、用计算机求解问题的步骤： 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制 2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程 3、算法的三要素 1、操作 2、控制结构 3、数据结构 算法具有以下5个属性： 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口 可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。 输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。 输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。 算法设计的质量指标： 正确性：算法应满足具体问题的需求； 可读性：算法应该好读，以有利于读者对程序的理解；

健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。 经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法 迭代法 基本思想：迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。 解题步骤：1、确定迭代模型。根据问题描述，分析得出前一个（或几个）值与其下一个值的迭代关系数学模型。 2、建立迭代关系式。迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式，存储新值的变量称为迭代变量 3、对迭代过程进行控制。确定在什么时候结束迭代过程，这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一

算法设计与分析课程报告

算法设计与分析课程报告 第一章 算法问题求解基础 1、算法的概念：算法是指解决问题的一种方法或过程，是由若干条指令组成的有穷序列。 2、算法的特性 ① 有穷性：一个算法必须保证执行有限步之后结束; ② 确切性：算法的每一步骤必须有确切的定义; ③ 输入： 一个算法有 0 个或多个输入， 法 本身定除了初始条件; ④ 输出： 一个算法有一个或多个输出， 是毫无意义的; ⑤可行性：算法原则上能够精确地运行, 而且人们用笔和纸做有限次运算后即可完成 3、算法与程序的关系： 区别：程序可以不一定满足可终止性。但算法必须在有限时间内结束; 程序可以没有输出 ,而算法则必须有输出; 算法是面向问题求解的过程描述，程序则是算法的实现。 联系：程序是算法用某种程序设计语言的具体实现; 程序可以不满足算法的有限性性质。 4、算法描述方式：自然语言，流程图，伪代码，高级语言。 第二章 算法分析基础 1、算法复杂性分析： 算法复杂性的高低体现运行该算法所需计算机资源（时间，空间）的多少。 算法复杂性度量： 期望反映算法本身性能，与环境无关。 理论上不能用算法在机器上真正的运行开销作为标准（硬件性能、代码质量影响） 般是针对问题选择基本运算和基本存储单位，用算法针对基本运算与基本存储单 以刻画运算对象的初始情况， 所谓 0 个输入是指算 以反映对输入数据加工后的结果。 没有输出的算法

位的开销作为标准。算法复杂性C依赖于问题规模N、算法输入I和算法本身A。即C=F（N, I,A）。 第五章分治法 1、递归算法：直接或间接地调用自身的算法。 用函数自身给出定义的函数称为递归函数。 注：边界条件与递归方程是递归函数的二个要素。 实例：①阶乘函数; ② Fibonacci 数列；③ Ackerman 函数; ④排列问题; ⑤整数划分问题; ⑥ Hanoi 塔问题 优缺点：①优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性, 因此它为设计算法、调试程序带来很大方便。 ②缺点：递归算法的运行效率低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 2、分治法的设计思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。（将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解） 分治法所能解决的问题一般具有以下几个特征： ①该问题的规模缩小到一定的程度就可以容易地解决; ②该问题可以分为若干个规模更小的相同问题，即该问题具有最有子结构性质; ③利用该问题分解出的子问题的解可以合并为该问题的解; ④该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 第六章贪心法 1、贪心算法的思想：

小学校本课程实施方案

小学校本课程实施方案 校本课程是学校自主开发的一门课程，由学生自主参加，以学生活动为主，它与必修课程一起构成学校课程体系。但它与必修程在内容、要求的深广程度和活动形式的修灵活程度等方面又不尽相同。校本课程更突出学生的自主性、自愿性和灵活性。按照中共中央国务院关于深化教育改革全面推进素质教育的决定》和《国家基础教育课程改革纲要》的要求，学校开发的校本课程将对培养学生的兴趣特长、创新思维习惯和实践能力，培养学生分析和解决问题的能力以及团结协作和社会活动的能力，全面提高学生的素质，发现和培养人才具有重要意义。 一、培养目标 1、培养学生的兴趣、爱好，发展个性特长。 2、拓展学生的知识领域，培养创新精神和实践能力。 3、提高学生的思想品德修养和审美能力，陶冶情操、增进身心健康。 4、培养学生的科学态度和精神，学习和掌握科学的基本知识、基本技能和方法。 5、培养学生的团结协作和社会活动能力，使学生热爱学校生活，适应社会。 二、教学原则 校本课程与其他课程一样．都是由学生全员参加的学校教育活动，在遵循一般教学原则的同时，还要考虑到其自身的特点和规律。

在教学上还应注意以下原则： 1、自主性原则：尊重学生的主体地位，以学生自主活动为主，教师讲授、指导少而精，尽量让学生多炼、多动，多给学生以尽可能多的时间与想象、创造空间。 2、自愿性原则：学生在"自选"科目时，教师应尊重学生的意愿，报名后按各自选择编组活动，充分发挥学生的个性特长。 3、灵活性原则：教学内容、方法应以学生的实际情况而定，教师应从学生的能力、效果等差异出发、因材施教，灵活的作内容形式上的调整，使全体学生都得到发展。 4、开放性原则：体现在目标的多元化、内容的宽泛性、即时性，时间空间的广域性、可变性，评价的主体性、差异性。 三、教学形式 作为一门以学生实践为主的课程，它的教育方式势必要打破固有的教学模式，教师要尽可能给学生更大的自主活动余地以及更多的相互交流的机会。在教学上主要应采用集体活动式：如班团队活动、社会实践等。 四、课时安排 校本课程每周2课时，安排在下午。 五、教学内容 根据学校实际情况，学校目前安排如下教学内容：《民俗》、《农历》 六、教学评价

算法设计与分析试卷及答案.doc

湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型： C 卷 考试时量： 120 分钟 题号 一 二 三 四 五 总分 统分人 得 分 阅卷人 一、填空题（每小题 3 分，共计 30 分） 1. 用 O 、Ω和θ表示函数 f 与 g 之间的关系 ______________________________ 。 f n n lo g n g n log n 1, n 1 2. 算法的时间复杂性为 f (n) n ，则算法的时间复杂性的阶 8 f (3n / 7) n, 2 为__________________________ 。 3. 快速排序算法的性能取决于 ______________________________ 。 4. 算法是 _______________________________________________________ 。 5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的 是_________________________ 。 6. 在算法的三种情况下的复杂性中， 可操作性最好且最有实际价值的是 _____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限，这个下限的阶越 ___________，结果就越有价值。 。 8. ____________________________ 是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指 ________________________________________________________ ____________________________________________________________ 。