全国信息学奥林匹克实验大纲(四)

扫码手机阅读
用圣才电子书APP或微信扫一扫,在手机上阅读本文,也可分享给你的朋友。
评论(0


  实验内容安排

 

  实验一  编程语言基础实验

 

  (验证性实验  4学时)

 

  1.目的要求

 

  以c或者Java为例,熟悉编程环境,会阅读程序,熟悉编译、调试和运行环境。掌握基本语句;掌握函数的使用;熟练掌握数组、文件等的应用。

 

  2.实验内容

 

  1)阅读课堂示例程序,并运行调试,然后将程序功能进一步完善。

 

  2)编程输出一个菱形图案以及空心菱形图案。(巩固循环语句的实用)

 

  3)编程输出n阶螺旋方阵。

 

  4)编程输出n阶奇魔方。

 

  5)利用集合类型实现筛法求素数。

 

  3.主要实验仪器设备

 

  计算机、c或者Java语言

 

  实验二  程序时空复杂度分析实验

 

  (验证性实验  2学时)

 

  1.目的要求

 

  验证不同算法的时间复杂度和空间复杂度。

 

  2.实验内容

 

  1)从键盘读入100个正整数,输出其中最大的数

 

  2)从输入文件中读入nn100)个整数,输出第一个出现数字1的位置。

 

  3)输入2个正整数xy2<x<1000 2<y<1000),求出满足下列条件的PQ的数。

 

  a)条件1PQ是正整数

 

  bPQx为最大公约数,以y为最小公倍数。

 

  求出满足上述条件的所有正整数个数。

 

  3.主要实验仪器设备

 

  计算机、c或者Java语言

 

  实验三  各种排序算法实验

 

  (验证性实验  2学时)

 

  1.目的要求

 

  验证不同排序算法,包括选择排序、冒泡排序、插入排序、归并排序、快速排序、堆排序、桶排序、计数排序。

 

  2.实验内容

 

  1)读入8个整数:76543210,分别采用选择排序、冒泡排序、插入排序、归并排序、快速排序、堆排序、桶排序、计数排序,将它们升序输出

 

  3.主要实验仪器设备

 

  计算机、c或者Java语言

 

  实验四  数据结构实验

 

  (验证性实验  4学时)

 

  1.目的要求

 

  验证线性数据结构(栈和队列)和非线性数据结构(树形数据结构)中的二叉排序树、哈夫曼树和树状数组。

 

  2.实验内容(选作23题)

 

  1)输入一串字符,以“?”结束,编写一个判断括号配对的程序,如果配对,输出yes,否则输出no

 

  2)设有一个m*n的迷宫,入口在(11),出口在(mn),迷宫的每个格子分别放有011表示格子是墙,不能通过,0表示通路,可以通过。迷宫中走的规则是上、下、左、右四个方向,且不能回走已经走过的格子。

 

  当迷宫地图给定后,求出入口到出口的方案总数。

 

  3)奶农有3个容量分别为ABC升(1<ABC<20)的桶,ABC分别是120的整数。最初AB桶都是空,C桶装满牛奶。奶农把牛奶从一个桶倒到另一个桶中,直到灌满或原桶空,每一次灌注都是完全的,容器上不会沾上牛奶。

 

  写一个程序帮助奶农找出当A桶是空的时候,C桶中牛奶所剩量的所有可能性(从小到大输出)

 

  输入文件:3个整数,表示ABC

 

  输出文件:只有1行,所有的可能性。

 

  4)给定一张N个顶点、E条边的无向图,请用BFS从顶点l遍历这张图。

 

  输入文件:第1行为NE,以下为E行每行2个整数代表顶点编号,表示他们之间有边连接。

 

  输出文件:从顶点l广搜的顶点编号,用空格分隔

 

  5)给定一个长度为nn<100000),初始值都为0的序列,xx<10000)次的修改某些位置上的数字,每次加上一个数,然后提出yy<10000)个问题,求每段区间的和。时间限制为1s

 

  6)有一颗N个结点的树,一开始每个结点上都有一个苹果,每次有两种操作:

 

  Cx:如果x结点上有苹果,那么摘下苹果,否则x结点会再长出一个苹果

 

  Qx:询问以x结点为根的子树中苹果的个数。

 

  你要对于每个Q操作,输出对应的答案。

 

  输入文件:第1N,表示数的结点个数,接下来的N-1行,每行两个数uv,表示一条树边。然后一行是一个数m,表示操作数目,接下来m行为m个操作,格式如题所示。

 

  输出文件:对于每个Q操作,输出对应的答案,一个操作一行。

 

  3.主要实验仪器设备

 

  计算机、c或者Java语言

 

  实验五  枚举、递归、分治、回溯算法及其应用

 

  (验证性实验  10学时)

 

  1.目的要求

 

  验证枚举、递归、分治、回溯算法及其应用

 

  2.实验内容

 

  1)枚举法的简单应用:对一个数字三角形,寻找从顶到底的最短路线和最长路线,并输出。

 

  2)递归和分治法及其应用:实现残缺棋盘的覆盖;

 

  3)回溯法及其应用(选作23题)

 

  a)求解排列组合问题;

 

  b)编程实现地图的填色问题;

 

  c)编程实现n皇后问题;

 

  d)编程实现棋盘覆盖问题;

 

  e)控制方格棋盘问题;

 

  f)填数游戏等。

 

  3.主要实验仪器设备

 

  计算机、c或者Java语言

 

  实验六  贪心、动态规划算法及其应用

 

  (验证性实验  6学时)

 

  1.目的要求

 

  掌握贪心法和动态规划法的基本思想,并应用贪心法和动态规划法解决一些实际问题。

 

  2.实验内容

 

  1)编程实现活动安排问题;

 

  2)编程实现背包问题;

 

  3)编程实现删数问题;

 

  4)编程实现0/1背包问题。

 

  5)编程实现数塔问题(塔的层高<200)。

 

  3.主要实验仪器设备

 

  计算机、c或者Java语言

 

  实验七  状态空间的搜索算法及其应用

 

  (验证性实验  4学时)

 

  1.目的要求

 

  理解搜索算法的基本思想。掌握深度优先搜索算法的基本思想、算法过程;以栈结构的应用和实现为重点。掌握广度优先搜索算法的基本思想、算法过程;以队列结构的应用和实现为重点认真阅读和掌握本实验的参考程序。

 

  2.实验内容

 

  1)编程实现工作安排问题。

 

  2)应用DFSBFS两种搜索算法,编程实现8数码难题,并比较两个程序的优缺点。

 

  3.主要实验仪器设备

 

  计算机、c或者Java语言  

 

  编辑推荐:

 

  欢迎扫以下二维码,扫码后分享到朋友圈并下载APP,登录即可领取现金红包。

 

  


学科竞赛类电子书(题库)

查看全部>>

小编工资已与此挂钩!一一分钱!求打赏↓ ↓ ↓

如果你喜欢本文章,请赐赏:

已赐赏的人
最新评论(共0条)评论一句