信息学竞赛-实验大纲

《信息学竞赛-实验大纲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《信息学竞赛》实验教学大纲课程总学时：80　学分：5实验学时：32　实验个数：16实验学分：课程性质：选修适用专业：教育技术学教材及参考书：自编教材《信息学竞赛》大纲执笔人：刘洪　大纲审定人：一、实验课的性质与任务本课程是教育技术学专业的选修专业课之一，在学生已有程序设计课程基础上，针对中学信息学奥林匹克联赛开设的课程。信息学奥林匹克竞赛属于智力与应用计算机解题能力的比赛，题目有相当的难度，解决这类问题，需要具备很强的综合能力。首先是观察和分析问题的能力；第二是将实际问题转化为数学模型的能力；第三是灵活地运用各种

2、算法的能力；第四是熟练编写程序并将其调试通过的能力；第五是根据题目的要求，自己设计测试数据，检查自己的解法是否正确，是否完备的能力。通过实验课程的学习，进一步提高学生的自学能力和动手能力，并将在学习过程中结合有关组合数学、图论、基本算法、数据结构、人工智能搜索算法及数学建模等知识，还要学会高级语言和编程技巧，培养很强的上机操作以及程序的调试能力。二、实验课程目的与要求1．实验目的（1）学会分析研究计算机加工的数据结构的特性，提高观察和分析问题的能力，培养数学模型的抽象能力和逻辑思维能力。（2）本课程的学习过程也是

3、复杂程序设计的训练过程，要求学生编写的程序结构清楚、正确易读，符合软件过程的规范。；（3）针对具体问题的要求，设计合适的算法，并采用一门高级语言实现该算法，对不同的算法进行分析（时间和空间复杂性）。2．实验要求（1）熟悉各种基本常用算法的基本思想、适用范围，初步掌握算法分析的基本技巧以及如何根据实际问题设计一个有效的算法。（2）会阅读参考程序，能将算法转变为完整的程序，（3）注重编程思想的培养，实现减少对实际编程语言或工具的依赖，在实际教学中应该以C语言为主，也可采用Java。三、实验项目及内容提要ΧΧΧ实验课程

4、（课程编号）序号实验项目编号实验名称学时必做选做学分数实验类型内容提要基本操作验证综合设计1编程语言基础实验4√√熟悉编程环境，熟悉调试和运行环境。熟练掌握编程语言工具。2程序时空复杂度分析实验2√√验证不同算法的时间复杂度和空间复杂度。3各种排序算法实验2√√验证不同排序算法，包括选择、冒泡、插入、归并、快速、堆、桶、计数4数据结构实验4√√验证线性数据结构（栈和队列）和非线性数据结构（树形数据结构）中的二叉排序树、哈夫曼树和树状数组5递归、分治、回溯算法及其应用10√√验证枚举、递归、分治、回溯算法及其应用6

5、贪心、动态规划算法及其应用6√√7状态空间的搜索算法及其应用4√√四、实验内容安排：实验一编程语言基础实验（验证性实验4学时）1.目的要求以c或者Java为例，熟悉编程环境，会阅读程序，熟悉编译、调试和运行环境。掌握基本语句；掌握函数的使用；熟练掌握数组、文件等的应用。2.实验内容1)阅读课堂示例程序，并运行调试，然后将程序功能进一步完善。2)编程输出一个菱形图案以及空心菱形图案。（巩固循环语句的实用）3)编程输出n阶螺旋方阵。4)编程输出n阶奇魔方。5)利用集合类型实现筛法求素数。3.主要实验仪器设备计算机、c

6、或者Java语言实验二程序时空复杂度分析实验（验证性实验2学时）1.目的要求验证不同算法的时间复杂度和空间复杂度。2.实验内容1)从键盘读入100个正整数，输出其中最大的数2)从输入文件中读入n(n=100)个整数，输出第一个出现数字1的位置。3)输入2个正整数x，y（2<=x<=1000,2<=y<=1000），求出满足下列条件的P、Q的数。a)条件1：PQ是正整数b)PQ以x为最大公约数，以y为最小公倍数。求出满足上述条件的所有正整数个数。3.主要实验仪器设备计算机、c或者Java语言实验三各种排序算法实验（

7、验证性实验2学时）1.目的要求验证不同排序算法，包括选择排序、冒泡排序、插入排序、归并排序、快速排序、堆排序、桶排序、计数排序。2.实验内容1)读入8个整数：76543210，分别采用选择排序、冒泡排序、插入排序、归并排序、快速排序、堆排序、桶排序、计数排序，将它们升序输出3.主要实验仪器设备计算机、c或者Java语言实验四数据结构实验（验证性实验4学时）1.目的要求验证线性数据结构（栈和队列）和非线性数据结构（树形数据结构）中的二叉排序树、哈夫曼树和树状数组。2.实验内容（选作2~3题）1)输入一串字符，以“?

8、”结束，编写一个判断括号配对的程序，如果配对，输出yes，否则输出no。2)设有一个m*n的迷宫，入口在(1,1),出口在（m，n），迷宫的每个格子分别放有0或1,1表示格子是墙，不能通过，0表示通路，可以通过。迷宫中走的规则是上、下、左、右四个方向，且不能回走已经走过的格子。当迷宫地图给定后，求出入口到出口的方案总数。3)奶农有3个容量分别为A、B、C升（1<=A、B、