没有合适的资源?快使用搜索试试~ 我知道了~
信奥初赛基础知识pdf文档(高中noip校队內部教材)
需积分: 5 2 下载量 182 浏览量
2023-12-16
18:46:11
上传
评论 1
收藏 1.07MB PDF 举报
温馨提示
![preview](https://dl-preview.csdnimg.cn/88635484/0001-74755d54637343e72fb88c868303265c_thumbnail.jpeg)
![preview-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/scale.ab9e0183.png)
试读
25页
以前搞noip的时候用的,内容涵盖初赛大部分内容
资源推荐
资源详情
资源评论
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/release/download_crawler_static/88635484/bg1.jpg)
信奥初赛基础知识
点学习资料
![](https://csdnimg.cn/release/download_crawler_static/88635484/bg2.jpg)
前言:NOIP 简介
(1) NOIP 时间和题型
NOIP 分普及组和提高组,前者是初中的,后者是高中的。二者题目不完全相同,提
高组难度高于普及组。
1. 初赛
初赛在 10 月份第三个星期六的 14:30~16:30 进行,时间为 2 小时,内容全部为笔
试,满分 100 分。
试题由四部分组成:
① 选择题(共 20 题,每题 1.5 分,共计 30 分):提高组的前 10 道题为单选题,
后 10 道题为不定项选择题(只有全部选对才得分,否则不得分);普及组的前 20 道题都
是单选题。
② 问题求解题(共 2 题,每题 5 分,共计 10 分):试题给出一个叙述较为简单的问
题,要求学生对问题进行分析,找到一个合适的算法,并推算出问题的解。考生给出的答
案与标准答案相同,则得分;否则不得分。
③ 程序阅读理解题(共 4 题,每题 8 分,共计 32 分):题目给出一段程序(不一定
有关于程序功能的说明),考生通过阅读理解该段程序给出程序的输出。输出与标准答案
一致,则得分;否则不得分。
④ 程序完善题(共 2 题,共计 28 分):题目给出一段关于程序功能的文字说明,然
后给出一段程序代码,在代码中略去了若干个语句或语句的一部分并在这些位置给出空
格,要求考生根据程序的功能说明和代码的上下文,填出被略去的语句。填对则得分;否
则不得分。
2. 复赛
复赛在 11 月份第三个星期六和星期日的上午 8:30~11:30 进行。
复赛的题型和考试形式与 NOI 类似,全部为上机编程题,但难度比 NOI 低。
普及组的复赛时间为 3 小时,共 4 道题,每题 100 分,共计 400 分。
提高组的复赛包括一试和二试,分两天进行。每次测试时间为 3 小时,有 3 道题,每
题 100 分。选手的总分为两次测试的分数的总和,最高 600 分。
2010 年及以前提高组只有一试,共 4 道题,满分 400 分。
每一试题包括:题目、问题描述、输入输出要求、样例数据(部分题目有样例的说
明)。测试时,测试程序为每道题提供了 10-20 组测试数据,考生程序每答对一组得 5
-10 分,累计分即为该道题的得分。
NOIP 的程序将在 NOI Linux 1.3(Ubuntu 系统)的环境下测评,G++编译器版本
为 4.4.5,评测系统为 Arbiter。2011 年测评器 CPU 为 P4 3.0GHz,内存大小为
1GB。
![](https://csdnimg.cn/release/download_crawler_static/88635484/bg3.jpg)
(2) 初赛内容与要求
计
基
算
本
机
常
的
识
1.计算机和信息社会(信息社会的主要特征、计算机的主要特征、数字通信网络
的主要特征、数字化)
2.信息输入输出基本原理(信息交换环境、文字图形多媒体信息的输入输出方
式)
3.信息的表示与处理(信息编码、微处理部件 MPU、内存储结构、指令,程序,
和存储程序原理、程序的三种基本控制结构)
4.信息的存储、组织与管理(存储介质、存储器结构、文件管理、数据库管理)
5.信息系统组成及互连网的基本知识(计算机构成原理、槽和端口的部件间可扩
展互连方式、层次式的互连结构、互联网络、TCP/IP 协议、HTTP 协议、WEB 应
用的主要方式和特点)
6.人机交互界面的基本概念(窗口系统、人和计算机交流信息的途径(文本及交
互操作))
7.信息技术的新发展、新特点、新应用等。
计
基
算
本
机
操
的
作
1.Windows 和 LINUX 的基本操作知识
2.互联网的基本使用常识(网上浏览、搜索和查询等)
3.常用的工具软件使用(文字编辑、电子邮件收发等)
程
序
设
计
的
基
本
知
识
数据结构
1.程序语言中基本数据类型(字符、整数、长整、浮点)
2.浮点运算中的精度和数值比较
3.一维数组(串)、线性表、队列与栈
4.记录类型(PASCAL)/结构类型(C/C++)
程序设计
1.结构化程序设计的基本概念
2.阅读理解程序的基本能力
3.具有将简单问题抽象成适合计算机解决的模型的基本能力
4.具有针对模型设计简单算法的基本能力
5.程序流程描述(自然语言/伪码/NS 图/其他)
6.程序设计语言(PASCAL/C/C++)
基本算法处理
1.初等算法(计数、统计、数学运算等)
2.排序算法(冒泡法、插入排序、合并排序、快速排序)
3.查找(顺序查找、二分法)
4.简单搜索
5.字符串处理
5.回溯算法
6.递归算法
![](https://csdnimg.cn/release/download_crawler_static/88635484/bg4.jpg)
(3) 复赛内容与要求
在初赛内容的基础上增加以下内容(*表示普及组不涉及):
计算机
软件
1.操作系统的使用
2.编程语言的使用
数据
结构
1.指针类型
2.多维数组
3.单链表及循环链表
4.二叉树
5.文件操作(从文本文件中读入数据,并输出到文本文件中)
6.图*
程序
设计
1.算法的实现能力
2.程序调试基本能力
3.设计测试数据的基本能力
4.程序的时间复杂度和空间复杂度的估计*
算法
处理
1.离散数学知识的应用(如排列组合、简单图论、数理逻辑)
2.分治思想
3.模拟法
4.贪心法
5.简单搜索算法(深度优先、广度优先)、搜索中的剪枝
6.动态规划的思想及基本算法
.1 常用语
1. 竞赛简称
OI:信息学奥林匹克竞赛
NOIP:National Olympiad in Informatics in Provinces,联赛,分
为普及组(初中生参加)和提高组(高中生参加)。
NOIP 初赛相当于其他竞赛科目的省级联赛,NOIP 复赛相当于其他竞赛科目的全
国初赛。
NOI:National Olympiad in Informatics,全国竞赛。先进省队然后才
能参加。
CTSC:Chinese Team Selection Contest,中国国家队选拔赛,选拨选手
参加 IOI。CTSC 的题难度最大,甚至比 IOI 大。
IOI:International Olympiad in Informatics,国际信息学奥林匹克
竞赛
WC:Winter Camp,冬令营
APIO:Asia-Pacific Informatics Olympiad,亚洲与太平洋地区信息学
奥林匹克(不属于 NOI 系列活动,有 NOIP 一等奖即可参加)
ACM/ICPC:ACM International Collegiate Programming
Contest,ACM 主办的大学生程序设计竞赛(不属于 NOI 系列活动,以团体的形
式组队参加)
2. 选手
OIer:学信息学奥赛的人。
![](https://csdnimg.cn/release/download_crawler_static/88635484/bg5.jpg)
P 党:指用 Pascal 语言编程的 OIer。
C 党:指用 C 或 C++语言编程的 OIer。
菜鸡:新手
大牛、神犇:高手
3. 题目
水题:特别简单的题——有编程基础的就能做上——只要认真审题,基本上就能
得满分。
水过:做完了一道水题。
暴 0:一个题目一个测试点也没过,得 0 分。
被虐:被题目虐杀,自己完全做不出,或者对自己的表现很不满意。
一眼题:题目内容较为明显,一眼就可以看出做法。
4. 评测
AC:Accepted,测试点全部正确。
AK:把一次比赛的所有的题目全都做对,得满分。
WA:Wrong Answer,答案错误,也可能是输出格式错误。
CE:Compile Error,编译错误,出现了某些语法错误,错误引用头文件,或
者忘记引用头文件,还可能是忘记 using namespace std 而直接使用 std 的
成员。
RE:Runtime Error,运行错误。可能是算法中数组下标越界,可能是因文件
错误而引发的下标越界,也可能是爆栈。
TLE:Time Limit Error,超时。可能是算法太慢、发生死循环。
MLE:Memory Limit Error,超过空间限制。在 NOIP 中一般不会出现此类问
题。尽管如此,做题之前仍然需要仔细阅读试题第一页的“内存限制”。
5. 算法与数据结构:
DFS:Depth First Search,深度优先搜索,简称“深搜”,搜索过程叫
“一条道走到黑”,一般用递归实现。
BFS:Breadth First Search,广度优先搜索,简称“广搜”、“宽搜”,
搜索过程和扩散现象比较像。实现时需要队列。
DP:Dynamic Programming,动态规划,简称“动规”
DAG:Directed Acyclic Graph,有向无环图
SPFA:Shortest Path Faster Algorithm,使用队列的 Bellman-Ford
算法。这是一个比较常用的算法。
BST:Binary Search Tree,二叉排序树
MST:Minimum-cost Spanning Tree,最小生成树
SCC:Strong Connected Component,强连通分量
LIFO:Last In & First Out,后进先出表,栈属于这种结构。
FIFO:First In & First Out,先进先出表,队列属于这种结构。
STL:Standard Template Library,标准模板库,是 C++自带的“现成的
程序”。STL 的头文件与其他头文件不同,是开源的。
ADT:Abstract Data Type,抽象数据类型,在软件开发中很常见。
6. 1..10:Pascal 语言里的用法,翻译成英语就是“1 to 10”。
7. IDE:Integrated Development Environment,集成开发环境
8. 难题:
非确定性计算机:一种神奇的计算机(目前还不存在),能够猜测答案,并且一
剩余24页未读,继续阅读
资源评论
![avatar-default](https://csdnimg.cn/release/downloadcmsfe/public/img/lazyLogo2.1882d7f4.png)
![avatar](https://profile-avatar.csdnimg.cn/a50d5a8d01ba4a3a9032eeaa3639d08c_qq_51471030.jpg!1)
![avatar-vip](https://csdnimg.cn/release/downloadcmsfe/public/img/user-vip.1c89f3c5.png)
黑暗骚年
- 粉丝: 17
- 资源: 3
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![voice](https://csdnimg.cn/release/downloadcmsfe/public/img/voice.245cc511.png)
![center-task](https://csdnimg.cn/release/downloadcmsfe/public/img/center-task.c2eda91a.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![dialog-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/green-success.6a4acb44.png)