全国青少年信息学奥林匹克联赛大纲微信扫一扫.docx
- 文档编号:10058540
- 上传时间:2023-05-23
- 格式:DOCX
- 页数:159
- 大小:312.68KB
全国青少年信息学奥林匹克联赛大纲微信扫一扫.docx
《全国青少年信息学奥林匹克联赛大纲微信扫一扫.docx》由会员分享,可在线阅读,更多相关《全国青少年信息学奥林匹克联赛大纲微信扫一扫.docx(159页珍藏版)》请在冰点文库上搜索。
全国青少年信息学奥林匹克联赛大纲微信扫一扫
第1章全国青少年信息学奥林匹克联赛大纲
1.1竞赛形式和成绩评定
联赛分两个等级组:
普及组和提高组。
每组竞赛分两轮:
初试和复试。
初试形式为笔试,侧重考察学生的计算机基础知识和编程的基本能力,并对知识面的广度进行测试。
初试为资格测试,各省初试成绩在本赛区前15%的学生进入复赛。
复试形式为上机,着重考查学生对问题的分析理解能力,数学抽象能力,驾驭编程语言的能力和编程技巧、想象力和创造性等。
各省联赛的等第奖在复试的优胜者中产生。
比赛中使用的程序设计语言是:
PASCAL或C/C++。
每年复赛结束后,各省必须在指定时间内将本省一等奖候选人的有关情况、源程序和可执行程序报送科学委员会。
经复审确认后,由中国计算机学会报送中国科协和教育部备案。
中国计算机学会对各省获NOIP二等奖和三等奖的分数线或比例提出指导性意见,各省可按照成绩确定获奖名单。
1.2试题形式
每次联赛的试题分四组:
普及组初赛题Al、普及组复赛题A2、提高组初赛题Bl和提高组复赛题82。
其中,Al和Bl类型相同,A2和B2类型相同,但题目不完全相同,提高组难度高于普及组。
1.初赛
初赛全部为笔试,满分l00分。
试题由四部分组成。
(1)选择题:
共20题,每题l.5分,共计30分。
每题有5个备迭答案,前10题为单选题(即每题有且只有一个正确答案,选对得分),后l0题为不定项选择题(即每题有l~5个正确答案,只有全部选对才得分)。
(2)问题求解题:
共2题,每题5分,共计l0分。
试题给出一个叙述较为简单的问题,要求学生对问题进行分析,找到合适的算法,并推算出问题的解。
考生给出的答案与标准答案相同,则得分;否则不得分。
(3)程序阅读理解题:
共4题,每题8分,共计32分。
题目给出一段程序(不一定有关于程序功能的说明),考生通过阅读理解该段程序给出程序的输出。
输出与标准答案一致,则得分;否则不得分。
(4)程序完善题:
共2题,每题l4分,共计28分。
题目给出一段关于程序功能的文字说明,然后给出一段程序代码,代码中略去了若干个语句或语句的一部分并在这些位置给出空格,要求考生根据程序的功能说明和代码的上下文填出省略的语句。
填对则得分;否则不得分。
2.复赛
复赛的题型和考试形式与全国青少年程序设计竞赛类似,全部为上机编程题,但难度比NOI低。
题目包括4道题,每题100分,共计400分。
每一试题包括:
题目、问题描述、输入输出要求、样例描述及相关说明。
测试时,测试程序为每道题提供了5或10组测试数据,考生所编程序每答对一组得10或20分,累计分即为该道题的得分。
1.3试题的知识范围
1.3.1初赛内容与要求
1.计算机的基本常识
(1)计算机和信息社会(信息社会的主要特征、计算机的主要特征、数字通信网络的主要特征、数字化)。
(2)信息输入输出基本原理(信息交换环境、文字图形多媒体信息的输入输出方式)。
(3)信息的表示与处理(信息编码、微处理部件MPU、内存储结构、指令、程序、存储程序原理和程序的三种基本控制结构)。
(4)信息的存储、组织与管理(存储介质、存储器结构、文件管理、数据库管理)。
(5)信息系统组成及互联网的基本知识(计算机构成原理、槽和端口的部件间可扩展互联方式、层次式的互联结构、互联网络、TCP/IP协议、HTTP协议、Web应用的主要方式和特点)。
(6)人机交互界面的基本概念(窗口系统、人和计算机交流信息的途径(文本及交互操作))。
(7)信息技术的新发展、新特点、新应用等。
2.计算机的基本操作
(1)Windows和LINUX的基本操作知识。
(2)互联网的基本使用常识(网上浏览、搜索和查询等)。
(3)常用的工具软件使用(文字编辑、电子邮件收发等)。
3.程序设计的基本知识
(1)数据结构。
程序语言中基本数据类型(字符、整数、长整数、浮点)。
浮点运算中的精度和数值比较。
一维数组(串)与线性表。
记录类型(PASCAL)/结构类型(C)。
(2)程序设计。
结构化程序设计的基本概念。
阅读理解程序的基本能力。
具有将简单问题抽象成适合计算机解决的模型的基本能力。
具有针对模型设计简单算法的基本能力。
程序流程描述(自然语言/伪码/NS图/其他)。
程序设计语言(PASCAL/C/C++)。
(3)基本算法处理。
初等算法(计数、统计、数学运算等)。
排序算法(冒泡法、插入排序、合并排序、快速排序)。
查找(顺序查找、二分法)。
回溯算法。
1.3.2复赛内容与要求
在初赛的内容上增加以下内容。
1.数据结构
(1)指针类型。
(2)多维数组。
(3)单链表及循环链表。
(4)二叉树。
(5)文件操作(从文本文件中读人数据,并输出到文本文件中)。
2.程序设计
(1)算法的实现能力。
(2)程序调试基本能力。
(3)设计测试数据的基本能力。
(4)程序的时间复杂度和空间复杂度的估计。
3.算法处理:
(1)离散数学知识的应用(如排列组合、简单图论、数理逻辑)。
(2)分治思想。
(3)模拟法。
(4)贪心法。
(5)简单搜索算法(深度优先、广度优先)搜索中的剪枝。
(6)动态规划的思想及基本算法。
第2章计算机相关理论知识
2.1计算机和信息技术的发展
1.信息与信息技术
(1)信息。
信息是以适合于通信、存储或处理的形式来表示的知识或消息。
(2)信息的特性。
①可识别性。
信息是可以识别的,识别又可分为直接识别和间接识别:
直接识别是指通过感官的识别;间接识别是指通过各种测试手段的识别。
不同的信息源有不同的识别方法。
②可存储性。
信息是可以通过各种方法存储的。
③可扩充性。
信息随着时间的变化将不断扩充。
④可压缩性。
人们对信息进行加工、整理、概括、归纳就可使之精练,从而浓缩。
⑤可传递性。
信息的可传递性是信息的本质特征。
⑥可转换性。
信息可以由一种形态转换成另一种形态。
⑦特定范围有效性。
信息在特定的范围内有效,否则无效。
这是信息区别于物质和能量的特性。
(3)信息技术。
信息技术(InformationTechnology,IT)是主要用于管理和处理信息所采用的各种技术的总称,主要指应用计算机科学和通信技术来设计、开发、安装和实施信息系统及应用软件。
2.计算机的数学模型
现代计算机的基础是抽象的图灵机(TuringMachine),英国数学家A.M.Turing于1936年提出的一种理想的计算机器的数学模型。
1936年,图灵发表了著名的《论应用于决定问题的可计算数字》一文,提出思考实验原理的计算机概念。
他把人在计算时所做的工作分解成简单的规定动作,这样就把人的工作机械化了,这种理想中的机器被称为“图灵机”。
3.计算机的基本结构和工作方式
1944年,美籍匈牙利数学家冯·诺依曼提出计算机基本结构和工作方式的设想,为计算机的诞生和发展提供了理论基础。
时至今日,尽管计算机软硬件技术飞速发展,但计算机本身的体系结构并没有明显的突破。
冯·诺依曼理论的要点如下。
(1)计算机硬件设备由存储器、中央处理器、控制器、输入设备和输出设备五部分组成。
(2)存储程序思想:
把计算过程描述为由许多命令按一定顺序组成的程序,然后把程序和数据一起输入计算机,计算机对已存人的程序和数据处理后,输出结果。
4.第一台计算机
人们公认的世界上第一台电子计算机是1946年2月问世的埃尼阿克(TheElectronicNumericalIntegratorandCalculator,ENIAC,电子数值积分计算机)。
它是美国宾夕法尼亚大学莫尔学院的莫奇莱教授和他的学生埃克特博士等人为计算弹道轨迹而研制成功的。
5.计算机的发展阶段
从1946年2月诞生至今,计算机的系统结构不断变化,应用领域不断拓展。
人们根据计算机所用的电子器件的种类,习惯上将计算机的发展划为四个阶段(即四代):
电子管、晶体管、中小规模集成电路、大规模/超大规模集成电路。
1971年,由于大规模和超大规模集成电路的出现,计算机的核心部分可集成在一块或几块芯片上,从而出现微型计算机。
6.计算机的发展趋势
计算机的运算速度越来越快,体积越来越小,能源消耗越来越少,生产成本越来越低,但计算机的功能则越来越强,使用越来越方便。
计算机的发展趋势可以归纳为微型化、巨型化、智能化、多媒体和网络化的方向。
计算机人工智能的研究建立在现代科学基础之上。
智能化是计算机发展的一个重要方向,新一代计算机将可以模拟人的感觉行为和思维过程的机理,进行“看”、“听”、“说”、“想”、“做”等动作,具有逻辑推理、学习与证明的能力。
计算机是否可以完全替代人的大脑的问题一直是理论界讨论的焦点,至今还未有定论。
正在研制的第五代计算机是一种非冯·诺依曼型计算机,它完全采用新的工作原理和体系结构。
7.计算机的主要特点
电子计算机是一种以高速进行操作、具有内部存储能力、有程序控制操作过程的自动电子装置。
它运算速度快、精确度高,具有“记忆”和逻辑判断的能力,内部的操作运算都是自动控制运行的。
其中,计算机的主要功能是可以实现高速运算。
8.计算机的应用领域
计算机的应用已渗透到社会的各行各业,正在改变传统的工作、学习和生活方式,推动社会的发展。
计算机的主要应用领域有:
科学计算(或数值计算)、数据处理、过程控制、辅助工程(办公自动化、生产自动化、数据库应用、网络应用、计算机模拟、计算机辅助教育)、人工智能(机器人、专家系统、模式识别、智能检索)。
9.计算机在中国的发展
我国计算机的发展可以归纳为以下几个典型阶段。
①1956年开始计算机的科研和教学工作;②l960年第一台自行设计的通用电子计算机l07机诞生;③1964年研制成功大型通用电子计算机ll9机;④1983年,每秒运行一亿次的“银河”巨型计算机在国防科技大学诞生;⑤l992年研制成功了每秒运行10亿次的“银河Ⅱ”巨型计算机;⑥1997年又研制成功了每秒运行130亿次的“银河IIl”巨型计算机。
国家智能机中心与曙光公司于1997——1999年先后在市场上推出具有机群结构的曙光1000A,曙光2000—I,曙光2000—II超级服务器,峰值计算速度已突破每秒1000亿次浮点运算,机器规模已超过l60个处理机,2000年推出每秒浮点运算速度3000亿次的曙光3000超级服务器。
2004年上半年推出每秒浮点运算速度l万亿次的曙光4000超级服务器。
2008年8月26日,由中国科学院计算技术研究所、曙光信息产业有限公司自主研发制造的百万亿次超级计算机“曙光5000”近日研制成功。
这标志着中国成为继美国之后第二个能制造和应用超百万亿次商用高性能计算机的国家,也表明我国生产、应用、维护高性能计算机的能力达到了世界先进水平。
“曙光5000”系统峰值运算速度达到每秒230万亿次浮点运算,LINPACK运算速度超过每秒l60万亿次浮点运算,是目前国内速度最快的商用高性能计算机系统。
除了超强计算能力,它还拥有全自主、超高密度、超高性价比、超低功耗以及超广泛应用等特点。
1993年7月,国家提出了“三金工程”,即“金桥”、“金卡”、“金关”工程。
“金桥”工程又称经济信息通信网工程,它是建设国家公用经济信息通信网、实现国民经济信息化的基础设施。
这项工程的建设,对于提高我国宏观经济调控和决策水平以及提供信息资源共享、推动信息服务业的发展,都具有十分重要的意义。
“金卡”工程又称为海关网工程,其目标是推广电子数据交换(EDI)技术,以实现货物通关自动化、国际贸易无纸化。
“金关”工程又称电子货币工程,它是借以实现金融电子化和商业流通现代化的必要手段。
10.计算机发展史上的重要人物
(1)布莱士·帕斯卡(BlaisePascal,1623—1662年)。
法国科学家,被公认为是制造出机械计算机的第一人。
帕斯卡加法器是由齿轮组成的装置,靠发条驱动,用专用的铁笔来拨动转轮以输入数字。
(2)莱布尼茨(G.Leibnitz,1646—1716年)。
德国数学家,他发明了“乘法器”,该机器由一系列齿轮组成,基本原理继承于帕斯卡,但多了一个“步进轮”装置。
它能够连续重复地做加法减法,从而实现了乘除运算。
(3)巴贝奇(C.Babbage,1792—1871年)。
英国剑桥大学科学家,他设计的“分析机”有齿轮式“存贮仓库”(Store)和“运算室”即“作坊”(Mill)、“控制器”、输入和输出部件。
首次提出了类似于现代计算机五大部件的逻辑结构。
(4)阿达·奥古斯塔(AugustaAdaLovelaee,1815—1851年)——第一个写软件的人。
英国数学家,拜伦的女儿,穿孔机程序创始人,建立了循环和子程序概念,为计算程序拟定“算法”。
l860年她尝试为机械式计算机写软件。
尽管努力失败了,但她的名字永远载人了计算机发展的史册,被认为“第一个给计算机写程序的人”。
(5)香农(C.Shannon,1916—2001年)。
美国数学家,1938年撰写了《继电器和开关电路的分析》,创立了开关电路理论。
把二进制0和1与运用以脉冲方式处理信息的继电器开关相对应,从理论到技术改变了数字电路的设计方向,在现代数字计算机史上具有划时代的意义。
(6)华罗庚(1910一1985年)和我国第一个计算机科研小组。
华罗庚教授是我国计算技术的奠基人和最主要的开拓者之一。
当冯·诺依曼开创性地提出并着手设计存储程序通用电子计算机EDVAC时,正在美国Princeton大学工作的华罗庚教授参观过他的实验室,并经常与他讨论有关学术问题。
华罗庚教授l950年回国,l952年在全国大学院系调整时,他从清华大学电机系物色了闵乃大、夏培肃和王传英三位科研人员在他任所长的中国科学院数学所内建立了中国第一个电子计算机科研小组。
l956年筹建中科院计算技术研究所时,华罗庚教授担任筹备委员会主任。
(7)慈云桂(1917—1990年)——中国巨型机之父。
l983年12月22日,中国第一台每秒钟运算达l亿次以上的计算机——“银河”在长沙研制成功,其设计主持人为两院院士慈云桂教授。
慈云桂教授也被称为中国巨型机之父。
(8)王选(1937--2006年)。
中国科学院院士、中国工程院院士、第三世界科学院院士。
是汉字激光照排系统的创始人,他所领导的科研集体研制出的汉字激光照排系统为新闻、出版全过程的计算机化奠定了基础,被誉为“汉字印刷术的第二次发明”。
l987年获得我国首次设立的印刷界个人最高荣誉奖——毕昇奖,被誉为“当代毕昇”。
(9)姚期智(AndrewChi—ChihYa0,1946一)。
世界著名计算机学家,2000年图灵奖得主,美国科学院院士,美国科学与艺术学院院士,中国科学院外籍院士,清华大学高等研究中心教授。
1967年获得台湾大学物理学士学位,1972年获得美国哈佛大学物理博士学位,1975年获得美国伊利诺依大学计算机科学博士学位。
1975--1986年曾先后在美国麻省理工学院数学系、斯坦福大学计算机系、加利福尼亚大学伯克利分校计算机系任助教授、教授。
l986--2004年在普林斯顿大学计算机科学系担任WilliamandEdnaMacaleer工程与应用科学教授。
2004年起在清华大学任全职教授。
2.2计算机硬件知识
1.计算机系统组成
完整的计算机系统由硬件系统和软件系统组成,只有两者相互配合,计算机才能正常工作。
计算机硬件系统是计算机工作的物质基础。
计算机软件系统包括系统软件和应用软件。
2.计算机硬件系统
计算机硬件系统包括中央处理器、存储器、输入设备(键盘、鼠标等)和输出设备(显示器、打印机等)。
从理论上讲,中央处理器(即CPU,包括运算器、控制器)和主存(内存储器)组成主机。
主机是计算机硬件系统中最基本的部分。
存储器有内存储器和外存储器之分,内存储器包括只读存储器(ROM)和随机存储器(RAM)等;外存储器包括软盘存储器(现在基本不用)、硬盘存储器、磁带存储器、光盘存储器、U盘等一系列移动存储设备等。
输入设备包括键盘、鼠标、扫描仪、麦克风、手写笔、摄像头等。
输出设备包括显示器、打印机和绘图仪、音响等。
3.信息编码及其运算
(1)ASCIl码。
通常,大部分信息是用字符的组合来表示的,在这里,字符可以是字母、数字和其他一些符号。
例如,26个英文字母、l0个阿拉伯数字、运算符(+、一、*、/)、关系符码(>、<、=)等都是字符。
在计算机中,所有信息都用二进制代码表示,字符在计算机中一般要用若干位二进制代码表示。
n位二进制代码能表示2n个不同的字符。
ASCII(AmericanStandardCodeforInformationInterchange,美国标准信息交换码)码是目前微型计算机中使用最广泛的一种字符编码。
ASCIl码用7位二进制数来编码(占一个字节),可表示l28个字符,最高位为“0”或作奇偶校验用。
若将原来的高三位扩展为4位后,0000000001111111的编码与原来的编码相同,l0000000--11111111增加了l28个字符,如“α”、“β”、“γ”等。
例如,大写字母A的ASCIl码值为01000001,即十进制数65,小写字母a的ASCIl码值为1100001,即十进制数97。
(2)汉字编码。
在我国,汉字是我们常用的信息符号,国家标准GB2312—80中规定,以ASCII码中的94个字符为基础,由任意两个ASCIl码组成一个汉字编码(即一个汉字由两个字节组成),第一个字节称为“区”,第二个字节称为“位”,则国标码最多可表示94×94(共8836)个汉字符号。
在国标码中,实际收录各种字符7445个,其中汉字6763个,而其中一级汉字3755个,二级汉字3008个;同时收录了包括拉丁字母、希腊字母、日文平假名及片假名字母、俄语西里尔字母在内的682个字符。
为了避免国标码和ASCIl码的两重定义,在计算机内部存储时,将汉字的各个字节的最高位都置为l,这时的汉字编码称为机内码。
(3)机内代码及其运算。
在计算机中,参加运算的数有正与负之分,数的符号也是用二进制来表示的。
用二进制表示带符号的数称为机器码。
通常规定,带符号数使用最高二进制位作为符号位,常用的机器码有原码、反码、补码。
(4)原码。
求原码的简单方法:
设X,若为正数,则符号位为0,X的其余各位取值不变;若X为负数,则符号位为l,X的其余各位取值不变。
例如:
如果X=+1110001则[X]原=01110001
如果X=-lll0001则[X]原=llll0001
(5)反码。
求反码的简单方法:
设X,若为正数,则符号位为0,X的其余各位取值不变;若X为负数,则符号位为l,X的其余各位取值求反。
例如:
如果X=+1110001则[X]反=01110001
如果X=-1110001则[X]反=l0001110
(6)补码。
求补码的简单方法:
设X,若为正数,则符号位为0,X的其余各位取值不变;若X为负数,则符号位为l,X的其余各位取值求反,且最低位加1。
例如:
如果X=+1110001则[X]补=01110001
如果X=-1110001则[X]补=l0001111
(7)补码加、减运算。
在计算机中,实际上只有加法运算,减法运算要转换成加法运算进行;同样,乘法运算也转换成加法运算进行,除法运算转换成减法运算。
在计算机内部,对任意一个带有符号的二进制数来说,都是按其补码的形式来进行存储和处理的,所以在计算机中的运算用补码进行加减运算。
在用补码进行加减运算时,连同符号位一起参加运算。
(8)补码加法运算。
公式[X+Y]补=[X]补+[Y]补。
例如:
已知X=+0110011,Y=-0101001,求[X+Y]补。
求解过程如下:
[X]补=00110011,[Y]补=11010111
[X+Y]补=[X]补+[Y]补=00110011+11010111=00001010。
因为计算机中运算器的位长是固定的,上述运算中最高位产生的进位被丢掉,所以运算结果不是l00001010,而是00001010。
(9)补码减法运算。
公式[X—Y]补=[X]补—[Y]补=[X]补+[一Y]补,公式中的[一Y]补称为负补。
做补码减运算之前,应该先求出减数的负补。
求负补的方法是:
对补码(包括符号位)的每一位求反,且最低位加1。
例如:
已知X=+1001101,Y=+0111001,求[X—Y]补。
求解过程如下:
[X]补=01001101,[Y]补=00111001,[一Y]补=ll000111
[X-Y]补=[X]补+[一Y]补=01001101+11000111-=00010100
(10)计算机中数值存放形式。
数值在计算机中的存储形式主要有:
位(bit)、字节(Byte)、字(Word)、双字(Dword)、四字(Oword)、字符串(String)。
位由单一的一位二进制数所构成。
位是数的最小表示形式,每一位代表一种状态,而这种状态只能是0或1。
字节由8位连续的二进制位组成。
字节是存储单元的最基本单位。
字由两个连续字节组成,即字由16个二进制位所组成。
另外,在特定计算机中,字是其用来一次性处理事务的一个固定长度的位组。
一个字的位数(即字长)是计算机系统结构中的一个重要特性。
双字由两个连续存放的相邻的字组成。
四字由四个连续存放的相邻的字组成。
字符串又称串,它是用单引号引起来的能表示多个字节数据的完整数据。
数值单位称谓及其换算方式如下:
1Byte=8bit,1KB=210B=1024B,1MB=210KB=1024KB,1GB=210MB=1024MB,1TB=210GB=1024GB。
(11)定点数和浮点数。
定点数是指数据中小数点的位置固定不变。
小数点定点位置有两种:
①小数点固定在最低位右边,这种定点数称为整数;②小数点固定在符号位与有效位之间,即S.XXXXXXX形式。
由于受字长表示范围的限制,定点数所能表示的范围有限,在计算过程中容易出现计算结果超出字长表示范围的情况,即溢出。
浮点数表示一个数的形式(设基数为2)可以写成N=M×2E。
其中M代表尾数,E代表阶码。
计算机中浮点数只能用尾数M和阶码E表示,其形式如图2.1所示。
阶码
尾数符号尾数
图2.1浮点数表示
浮点数的精度由尾数的位数决定,数的表示范围由阶码的位数决定。
为了最大限度地使用计算机的精度,充分利用尾数表示有效数据,浮点数采用规格化形式。
规格化形式对尾数提出的限制是l/2≤|M|<1。
例如:
设X=23×0.0110,用规格化浮点数形式表示如下。
①用浮点数表示:
用补码、浮点数形式表示阶码Xj=011,尾数为X=0.0110。
此时X尾数中小数点后第一位的真值是“0”而不是l,所以该数不是一个规范化的数,需要进行规格化处理。
②做规格化处理:
进行规格化处理时,先把尾数左移一位,尾数X=0.1100,再把阶码减l,Xj=011。
这时尾数1/2<|X|=0.1100<1,所以该数是一个规格化数。
4.数据校验方法
计算机系统运行时,在各个部件之间经常需要进行数据交换,为了保证数据在传送过程中的正确无误,不仅需要设计高可靠的硬件电路,同时还必须引入差错检查机制,对数据信息进行校验以检测是否有数据传送错误。
常用的校验码有奇偶校验码、海明码和循环冗余码(CRC)。
5.中央处理器
中央处理器(CentralProcessingUnit,CPU)负责完成大部分的信息处理操作,是计算机的核心部件,是执行各种运算的中心,是控制调度全机工作的中心。
CPU一般认为由运算器和控制器组成。
运算器完成指令所规定的运算和操作;控制器控制运算器和寄存器组正确地完成某一操作。
其实,寄存器组也是CPU的重要组成部分,它用于在指令执行过程中存放操作数和
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 全国青少年 信息学 奥林匹克 联赛 大纲 微信扫一扫