当前位置:首页 >> 其它课程 >>

NOIP初赛知识点复习总结


NOIP2014初赛指导

初赛的目的
? 进入复赛(本赛区前15%) ? 考察计算机基础知识和编程的基本能力,并对知识面的广 度进行测试 ? 复赛排名重要依据

初赛试题形式
●初赛:初赛全部为笔试,满分100分。试题由四部分组成: 1、选择题:共20题,每题1.5分,共计30分。提高组每题有5个备选答案, 前10

个题为单选题(即每题有且只有一个正确答案,选对得分 ),后10题为不定项选 择题(即每题有1至5个正确答案,只有全部选对才得分 )。普及组4个备选答案,全为 单选题。 2、问题求解题:共2题,每题5分,共计10分。试题给出一个叙述较为简单的 问题,要求学生对问题进行分析,找到一个合适的算法,并推算出问题的解。考生 给出的答案与标准答案相同,则得分:否则不得分。 3、程序阅读理解题:共4题,每题8分,共计32分。题目给出一段程序(不一 定有关于程序功能的说明),考生通过阅读理解该段程序给出程序的输出。输出与标 准答案一致,则得分;否则不得分。 4、程序完善题:共2题,每题14分,共计28分。题目给出一段关于程序功能 的文字说明,然后给出一段程序代码,在代码中略去了若干个语句或语句的一部分 并在这些位置给出空格,要求考生根据程序的功能说明和代码的上下文,填出被略 去的语句。填对则得分;否则不得分。

知识范围
内容与要求 1、计算机的基本常识 ●计算机和信息社会(信息社会的主要特征、计算机的主要特征、数 字通信网络的主要特征、数字化) ●信息输入输出基本原理(信息交换环境、文字图形多媒体信息的输 入输出方式) ●信息的表示与处理(信息编码、微处理部件MPU、内存储结构、指 令,程序,和存储程序原理、程序的三种基本控制结构) ●信息的存储、组织与管理(存储介质、存储器结构、文件管理、数 据库管理) ●信息系统组成及互连网的基本知识(计算机构成原理、槽和端口的 部件间可扩展互连方式、层次式的互连结构、互联网络、TCP/IP协议、 HTTP协议、WEB应用的主要方式和特点) ●人机交互界面的基本概念(窗口系统、人和计算机交流信息的途径 (文本及交互操作)) ●信息技术的新发展、新特点、新应用等。

2、计算机的基本操作 ●WINDOWS和LINUX的基本操作知识 ●联网的基本使用常识 (网上浏览、搜索和查询等) ●常用的工具软件使用(文字编辑、电子邮件收发等) 3、程序设计的基本知识 数据结构 ●程序语言中基本数据类型(字符、整数、长整数、浮点) ●浮点运算中的精度和数值比较 ●一维数组(串)与线性表 ●记录类型(PASCAL)/结构类型(C) 程序设计 ●结构化程序设计的基本概念 ●阅读理解程序的基本能力 ●具有将简单问题抽象成适合计算机解决的模型的基本能力 ●具有针对模型设计简单算法的基本能力 ●程序流程描述(自然语言/伪码/NS图/其他) ●程序设计语言(PASCAL/C/C++,) 基本算法处理 ●初等算法(计数、统计、数学运算等) ●排序算法(冒泡法、插入排序、合并排序、快速排序 ) ●查找(顺序查找、二分法) ●回溯算法

课程大纲
NOIP初赛情况的简单分析 基础知识 二叉树 图 排列组合 程序阅读题 程序填空题 总结

初赛试卷题型分析
(提高组)单项选择 15分 (提高组) 不定项选择 15分(多选少选均不得分) 问题求解 10分 阅读程序 32分 完善程序 28分

初赛试卷题型分析
初赛考的知识点,大纲说:计算机基本常 识,基本操作和程序设计基本知识。选择 题考查的是知识,而问题解决题、填空更 加重视能力的考查。 一般说来,选择题是不需要单独准备 的 ,也无从准备。只要多用心积累就可以 了。到是问题解决题目比较固定,大家应 当多做以前的题目。写运行结果需要多做 题目,培养良好的程序阅读和分析能力, 而完善程序最好总结一下以前题目常常要 你填出来的语句类型。

初赛试卷题型分析
1.选择题 一般它们是比较容易得分的,一共30分,不可 错过! 近几年来,初赛的考查范围有了很大的变化,越来 越紧跟潮流,需要大家有比较广泛的知识,包括计算机 硬件,软件,网络,数据结构(例如栈,队列,排序算 法),程序设计语言以及一些基本的数学知识和技巧 (例如排列组合等)。
2.填空、问题解决 这部分题目对数学要求要高一点,往往考查的是代数 变形、集合论、数列(一般是考递推),也考查 一些算 法和数据结构知识。建议大家多花一点时间做,尽量做 对。

初赛试卷题型分析
3. 阅读程序写出运行结果 占的分数多,但得分率却不高,较易失分,一 旦结果不正确,将丢失全分。 这种题型主要考察选手: ① 程序设计语言的掌握能力 ② 数学运算能力 ③ 耐心、细心的心理品质一般做这类题目的 关键在于能够分析程序的结构及程序段的功能, 找出程序目的,即这个程序想干什么。

初赛试卷题型分析
完成这类题目的一般方法和步骤是: ① 从头到尾通读程序,大致掌握程序的算法; ② 通过给程序分段,清理程序的结构和层次,达到读懂程序 的目的;

③ 阅读程序中特别注意跟踪主要变量值的变化,也可以用列 表的方法,了解变量变化和程序运行的结果,要注意发现规律。 迄今为止考过的题目还没有―乱写‖的,总有一点―写作目的‖ 的。抓住了它,得出答案就变得很容易了,而且对结果也会有信 心。写程序运行结果大纲规定是必考的。试卷中给出的程序并不 复杂,语句的含义容易明白,因此悟性好的选手总是很快就能体 会到程序的设计思路并得出正确的答案,而机械模仿计算机硬算 出结果的同学往往做得慢的多,而且容易失误。

初赛试卷题型分析
4.完善程序 这部分题目得分率似乎不高。 尽量把一些简单的填好就行了。 建议大家把以前的初赛题目都做一下。 常常让大家填的是: ①初始化 ②一些明显的动作: a.结果没有储存在需要的地方。 b.累加器没有做加法 c.输出 ③关键动作。 在算法描述中出现的比较关键的步骤。例如交换 排序程序的―交换‖操作等很明显需要完成的操作。 分析方法和写运行结果类似,注意分析变量和 程序结构,理解变量和模块的作用是解题的关键。

进制转换
1.二进制与十进制间的相互转换: (1)二进制转十进制 方法:―按权展开求和‖ 例: (1011.01)2 =(1×23+0×22+1×21+1×20+0×2-1+1×2-2)10 =(8+0+2+1+0+0.25)10 =(11.25)10 规律:个位上的数字的次数是0,十位上的数字的次数是 1,......,依次递增,而十 分位的数字的次数是-1,百分位上数字的次数是2,......,依次递减。 注意:不是任何一个十进制小数都能转换成有限位的二进 制数。

进制转换

进制转换
1.二进制与十进制间的相互转换: (1)二进制转十进制 方法:―按权展开求和‖ 例: (1011.01)2 =(1×23+0×22+1×21+1×20+0×2-1+1×2-2)10 =(8+0+2+1+0+0.25)10 =(11.25)10 规律:个位上的数字的次数是0,十位上的数字的次数是 1,......,依奖递增,而十分位的数字的次数是-1,百分 位上数字的次数是-2,......,依次递减。 注意:不是任何一个十进制小数都能转换成有限位的二进 制数。

进制转换
以下二进制数与十进制数23.456最接近的 是() A 10111.0101 B 11011.1111 C 11011.0111 D 10111.0111 E.10111.1111

D 把下面的数转换为10进制数再进行比较

位运算
位运算主要有: 按位与( & ),按位或( | ),按位异或( ^ ), 取反~ 运算法则: 1、先将两边的数转化为二进制,右边第 一位对齐,对于每一位进行按位运算。 2、只有1&1为真,其余情况为假 3、只有0|0为假,其余为真 4、只有1^0和0^1为真,其余为假 5、优先级~>& > ^ > | 6、~(00001001)2=(11110110)2

切记:2^5不是25而是2异或5

位运算
补充:负数在计算机内的表示是取对应正 数的补码。 补码 = 反码 + 1 如1表示为(0001)2,那么-1就表示为: (1111)2。 10表示为(1010)2,那么-10就表示为 (0110)2。

位运算
比如,计算21^2 先转换为二进制 21 = (10101)2 2 = (10)2 ^

10101 10 10111

(10111)2=23

位运算
练习题: 23|2^5的值是多少?

23
23|2^5 = 23|7 = 23
这个内容比较重要,至少会占1 分,请大家务必学透!

逻辑
设A = true,B = false,C = false,D = true, 以下逻辑运算表达式值为真的有( CDE )。 A. (A∧B)∨(C∧D) B. ((A∧B)∨C)∧D C. A∧((B∨C)∨D) D. (A∧(B∨C)) ∨D E. (A∨B)∧(C∨D) 真真假假很容易判断的,总之复赛前要看一 下!需要结合C语言的逻辑判断!

逻辑
6.在 C语言中,判断整数a 等于 0 或b等于 0或 c等于0 的正确的条件表达式是( B )

A. ! ((a!=0) || (b!=0) || (c!=0)) B. ! ((a!=0) && (b!=0) && (c!=0)) C. ! ((a==0) && (b==0)) || (c==0) D.(a==0) && (b==0) && (c==0) E. ! ((a==0) || (b==0) || (c==0))

逻辑
12. 命题―P→Q‖可读做P蕴含Q, 其中 P、Q是两个独立的命题. 只有当命题P成 立而命题Q不成立时, 命题"P→Q"的值为 false, 其它情况均为true. 与命题"P→Q" 等价的逻辑关系式是( AD)。 A. ﹁ P∨Q B. P∧Q C. ﹁ (P∨Q) D. ﹁(﹁Q∧P )

需要注意优先级

逻辑
P→Q
q=true q=false p=true true false p=false true true

﹁P∨Q

p=true true false

p=false true true

q=true q=false

P∧Q q=true q=false

p=true true false

p=false false false

﹁(﹁Q∧P)

p=true true false

p=false true true

q=true q=false

集合论
集合我们刚刚学过,但是我们学的东西还 是少了点。另外,注意信息学竞赛中的一 些符号和数学书上略有不同。 需要学会的运算: 交集,并集,补集,差集

集合论
集合我们刚刚学过,但是我们学的东西还 是少了点。另外,注意信息学竞赛中的一 些符号和数学书上略有不同。 需要学会的运算: 交集,并集,补集,差集 建议学会 ―鸽巢原理‖ 差集符号:- (就是减号) A — B 就相当于去掉A中(A∩B)的元素。

集合论
设全集I = {a, b, c, d, e, f, g, h},集合B ∪A = {a, b, c, d, e, f}, C∩A= {c, d, e}, ~B ∩A= {a, d},那么集合C∩B∩A为 ( A)。 A. {c, e} B. {d, e} C. {e} D. {c, d, e} E. {d, f}

集合论
设全集I = {a, b, c, d, e, f, g},集合A = {a, b, c},B = {b, d, e},C = {e, f, g},那么集 合(A — B)∪(~C∩B)为( A)。 A. {a, b, c, d} B. {a, b, d, e} C. {b, d, e} D. {b, c, d, e} E. {d, f, g}

储存单位的计算
bit 位 Byte 比特,字节 KB 千字节 MB,兆字节 其它单位:GB TB
速率单位(声音,视频,网络): bps <=> bit per second <=> bit/s Kbps <=> Kbit per second <=> Kbit/s Mbps <=> Mbit per second <=> Mbit/s

储存单位的计算
1 Byte = 8 bit 1 KB = 1024 Byte 1 MB = 1024 KB = 10242Byte = 8*10243 bit 1 GB = 1024 MB = 10242 KB = 10243 Byte =... ...自己去推了

1Mbps = 1024 Kbps = 10242bps
Attention,大B小b有区别的,一个是bit,一个是Byte, 所以KB和Kb是不一样的,比如说“ADSL宽带512Kb” 当然,现在很多人都混着用了……但是考试还是要严格点。

储存单位的计算
声音文件的大小等于: 速率*长度(注意单位) 下载时间与网络速度的关系: 下载时间 = 文件大小 / 下载速率 注意下载速率的基本单位是bit/s,而文件大小的 单位是Byte,所以要乘以8。 公式不用死记,用物理的量纲理论就可以了。由 单位确定公式。 (bit/s) * (s) = bit 下载速率*时间 = 文件大小

储存单位的计算
例题:一个音乐爱好者收藏有100首MP3 格式的音乐,这些音乐的编码率都是 192Kbps,平均每首音乐的时长为3min, 他要通过网络将这些音乐传送给另一个 人,假设网络速度恒定为512KB/s,则他 传送这些音乐大概需要( )。 A. 72s B. 843s C. 112.5min D. 3h48min16s E. 超过24小时
100 * 192Kb/s * 3min / (512KB/s) = 843.75s 切记要换算单位!!!

储存单位的计算
10. 一位艺术史学家有20000 幅1024 * 768 的真彩色图像,如果将这些图像以位 图形式保存在CD 光盘上(一张CD 光盘 的容量按600M计算),大约需要( C)张 CD光盘。

A. 1 B. 10 C. 100 D. 1000 E. 10000
Hint:真彩色通常指每像素32位的图形

1024*768*20000*32bit/600MB = 100

栈和队列
类比火车站。一个是这样的——

另一个是这样的——

栈和队列
某个车站呈狭长形,宽度只能容下一台车,并且 只有一个出入口。已知某时刻该车站状态为空, 从 这一时刻开始的出入记录为:―进,出, 进,进,进,出,出,进,进,进,出,出‖。 假设车辆入站的 顺序为 1,2,3,……,则车 辆出站的顺序为( C )。

A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 D. 1, 4, 3, 7, 2 E. 1, 4, 3, 7, 5

C. 1, 4, 3, 7, 6

排序
n个数排序,最少需要比较多少次? for(i=1; i<=n; i++)

for(j=1; j<=n-i; j++) if(a[j] > a[j+1]) //这就是比较 .... ┏ 公式: 最少比较次数 = 2

log n !



10.将 5 个数的序列排序,不论原先的顺 序如何,最少都可以通过( B)次比较, 完成从小到大的排序。

A. 6

B. 7

C. 8

D. 9

E. 10

排序
思考:最坏情况下最少需要交换多少次?

n-1
1. 将数组{32, 74, 25, 53, 28, 43, 86, 47} 中的元素按从小到大的顺序排列,每 次可以交换任意两个元素,最少需要 5 次。 交换_____

排序
稳定排序包括: 插入排序、冒泡排序 不稳定排序包括: 选择排序、希尔排序、快速排序、堆排序 时间复杂度: 冒泡排序O(n2),选择排序O(n2),快速排 序O(nlog2n),堆排序O(nlog2n)

二叉树
定义:n个结点的有限集,每个结点至多 只有两棵子树,子树也是二叉树。每个结 点可以有左孩子和右孩子,顺序不可颠倒。 概念: 度:某个结点孩子的个数 叶子:度为0的结点 深度:二叉树的层数 满二叉树:深度为n且结点数为2n-1的二叉 树 完全二叉树:深度为k,1~k-1层为满二叉 树,第k层叶子节点集中在左边的二叉树

二叉树
二叉树的遍历:先根,中根,后根遍历以 及深度优先遍历和广度优先遍历,具体方 法参看资料。 根据前根中根或中根后根遍历确定一颗二 叉树的形态以及另一种遍历。

二叉树知识点补充
n个结点所组成的不同形态的二叉树数目 为:

C(2n,n)/(n+1)

二叉树
二叉树T,已知其前序遍历序列为1 2 4 3 5 7 6,中序遍历序列为4 2 1 5 7 3 6,则 其后序遍历序列为( B )。

A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1 C. 4 2 7 5 3 6 1 D. 4 7 2 3 5 6 1 E. 4 5 2 6 3 7 1

二叉树
已知7个节点的二叉树的先根遍历是1 2 4 5 6 3 7(数字为结点的编号,以下同), 后 根遍历是4 6 5 2 7 3 1, 则该二叉树的可 能的中根遍历是(ABD) A. 4 2 6 5 1 7 3 B. 4 2 5 6 1 3 7 C. 4 2 3 1 5 4 7 D. 4 2 5 6 1 7 3
只知道前根遍历和后根遍历是无法确定一棵二叉树的, 所以这题采用反推验证

二叉树
4. 完全二叉树的结点个数为4 * N + 3,则 它的叶结点个数为( E )。 A. 2 * N B. 2 * N - 1 C. 2 * N + 1 D. 2 * N - 2 E. 2 * N + 2
4n+3=2*2(n+1) - 1,熟悉的公式 2*叶子结点数-1,这不是满二叉树的结点数 吗?

二叉树
8.高度为 n 的均衡的二叉树是指:如果 去掉叶结点及相应的树枝,它应该是高度 为 n-1 的满二叉树。在这里,树高等于叶 结点的最大深度,根结点的深度为 0,如 果某个均衡的二叉树共有 2381 个结点, 则该树的树高为( B )。 A. 10 B. 11 C. 12 D. 13 E. 210 – 1

211<2381<212

二叉树
5. 一个高度为h 的二叉树最小元素数目是 ( B )。 C) 2h-1 A) 2h+1 B) h D) 2h E) 2h-1

此时二叉树退化成一条链


图是由顶点和边所组成的数据结构。分为 有向图和无向图。
带权图:权的含义,不加权的图也可以认为所 有边上的权都是1。 阶和度:一个图的阶是指图中顶点的个数 如果顶点A和B之间有一条边相连,则称A和B是 关联的 顶点的度:与该顶点相关联的边的数目,有奇点、 偶点之分 对于有向图:有入度和出度之分


大家记住定义,然后就见招拆招了。图论 的题目考得比较少,而且大家知道定义, 运用各种方法应该不难得到答案。 下面就简单地讲一下几道出现过的题目。


假设我们用d=(a1,a2,...,a5),表示无向图G 的5个顶点的度数,下面给出的哪(些) 组d 值合理( BE )。 A){5,4,4,3,1} B){4,2,2,1,1} C){3,3,3,2,2} D){5,4,3,2,1} E){2,2,2,2,2}


9. 欧拉图G是指可以构成一个闭回路的 图,且图G的每一条边恰好在这个闭回路 上出现一次(即一笔画成)。在以下各个 描述中, 不一定是欧拉图的是:( )。 A. 图G中没有度为奇数的顶点 B. 包括欧拉环游的图(欧拉环游是指通过 图中每边恰好一次的闭路径) C. 包括欧拉闭迹的图(欧拉迹是指通过途 中每边恰好一次的路径) D. 存在一条回路, 通过每个顶点恰好一次 E. 本身为闭迹的图
D 解释:闭迹,一条路径,起点和终点是一个点


5. 平面上有五个点A(5, 3), B(3, 5), C(2, 1), D(3, 3), E(5, 1)。以这五点作为完全图G 的 顶点,每两点之间的直线距离是图G 中对应 边的权值。图G 的最小生成树中的所有边的 权值和为( D ) A.8 B.7+ 5 C.9 D.6+ 5 E.4+2 2+ 5

讲解:最小生成树算法


1. 无向图G有16条边,有3个4度顶点、4 个3度顶点,其余顶点的度均小于3,则G 11 个顶点。 至少_______

排列组合
前置知识:乘法原理,加法原理,排列组 合公式C(n,r),A(n,r)的计算方法以及基本 定理和推论。

排列组合
公式: 1、不可重复的n个元素取r个的排列数为: A(n,r) 2、可重复的n个元素取r个的排列数为: nr 3、不可重复的n个元素取r个的组合数为: C(n,r) 4、可重复的n个元素取r个的组合数为: C(n+r-1,r)

排列组合
练习: 1.有五个不同颜色的球,从中依次拿出三 个,可能的排列有多少种 2.有五种不同颜色的球,从中依次拿出三 个,可能的排列有多少种 3.有五个不同颜色的球,从中拿出三个, 可能的组合有多少种 4.有五种不同颜色的球,从中拿出三个, 可能的组合有多少种

排列组合
由3个a,5个b和2个c构成的所有字符串 中,包含子串―abc‖的共有( D )个。 A. 40320 B. 39600 C. 840 D. 780 E. 60
C(8,1) * C(7,2) *C(5,4) * C(1,1) - C(6,2) * C(4,1) *C(3,3) 取出 出abc,变成2个a,4个b和1个c和"abc"构成字符串的 数目。一共有 有2+5+1+1=8个位置,任取1个给"abc",方 法数是C(8,1),剩下7个取2个给a,方法数C(7,2),剩下5 个取4个放b,以此类推。但是要考虑abcabc出现两次重 复计算的情况,所以要减去,怎么减大家自己思考一下。

排列组合
练习字符串"success"重新排列,包括其本 身,共可以组成多少个不同的字符串?

C(7,2)*C(5,2)*A(3,3) = 1260

问题求解
75名儿童到游乐场去玩。他们可以骑旋转 木马,坐滑行铁道,乘宇宙飞船。已知其 中20人这三种东西都玩过,55人至少玩过 其中的两种。若每样乘坐一次的费用是5 元,游乐场总共收入700,可知有___ 10 名儿 童没有玩过其中任何一种。 集合类问题,通常可以运用数学方法解决

已知a, b, c, d, e, f, g七个人中,a会讲英语;b会讲英语 和汉语;c会讲英语、意大利语和俄语;d会讲汉语和日 语;e会讲意大利语和德语;f会讲俄语、日语和法语;g 会讲德语和法语。能否将他们的座位安排在圆桌旁,使 得每个人都能与他身边的人交谈?如果可以,请以―a b‖ abdfgc 开头写出你的安排方案:______ 。




O











a b c d e f g

O O O O O O O O

O

O O O O O

2. 取火柴游戏的规则如下:一堆火柴有N 根,A、B两人轮流取出。每人每次可以取 1 根或2 根,最先没有火柴可取的人为败 方,另一方为胜方。如果先取者有必胜策 略则记为1,先取者没有必胜策略记为0。 当N 分别为100,200,300,400,500 时,先取者有无必胜策略的标记顺序为 (回答应为一个由0 或1 组成的字符串)。 11011,简单的博弈论,小学奥数题

(取石子游戏) 现有 5 堆石子,石子数依 次为 3,5,7,19,50,甲乙两人轮流从 任一堆中任取(每次只能取自一堆,不能 不取), 取最后一颗石子的一方获胜。甲 先取,问甲有没有获胜策略(即无论 乙怎 样取,甲只要不失误,都能获胜)? 第一次在第五堆里面取32枚石子。

T=3^5^7^19^50=32,取掉32后T=0,面对 T=0的状态时,先取者必败
普及组的题目。

1.将 2006 个人分成若干不相交的子集, 每个子集至少有 3 个人,并且: (1)在每个子集中,没有人认识该子集 的所有人。 (2)同一子集的任何 3 个人中,至少 有 2 个人互不认识。 (3)对同一子集中任何 2 个不相识的 人,在该子集中恰好只有 1 个人认识这两 个人。 则满足上述条件的子集最多能有 _______个?
401,主要方法是根据(1),(2),(3)进行假设, 发现至少需要5个人才能同时满足(1),(2),(3), 于是……2006/5,一个6人,其余5人

2.将边长为 n 的正三角形每 边 n 等分,过每个分点分别 做另外两边的平行线,得到若 干个正三角形, 我们称为小 三角形。正三角形的一条通路 是一条连续的折线,起点是最 上面的一个小三角形,终点是 最 下面一行位于中间的小三 角形。在通路中,只允许由一 个小三角形走到另一个与其有 公共边的且位于同 一行或下 一行的小三角形,并且每个小 三角形不能经过两次或两次以 上(图中是 n=5 时一条通路 的例 子)。设 n=10,则该正 三角形的不同的通路的总数为 _______。

362880 严格证明挺复杂,找规律 可以知道总数为(n-1)!

1.给定n个有标号的球,标号依次为1, 2,…,n。将这n个球放入r个相同的盒子 里,不允许有空盒,其不同放置方法的总 数记为S(n,r)。例如,S(4,2)=7,这7种不 同的放置方法依次为{(1) , (234)} , {(2) , (134)} , {(3) , (124)} , {(4) , (123)} , {(12) , (34)} , {(13) , (24)} , {(14) , (23)}。当 n=7,r=4时,S(7,4)=_____。
289 S(n,r)=S(n-1,r-1)+r*S(n-1,r) 边界条件自己找。 难题,递推类问题

下面介绍一个简单的递推问题,好让大家 初步认识递推。 小明上楼,一步可以上一级,也可以上两 级,请问上n级有多少种上法?例如,上2 级可以有1+1,也可以一次上2级。上3级 可以是1+1+1,2+1,1+2三种。
设f(n)表示上n级需要的步数,显然只能够从n-1级或n2级上到第n级,所以方法总数适用加法原理, f(n)=f(n-1)+f(n-2),斐波那契数列! 其中f(1)=1,f(2)=2,后面的都可以根据这两个初 始条件推出来

2.N个人在操场里围成一圈,将这N个人 按顺时针方向从1到N编号,然后从第一个 人起,每隔一个人让下一个人离开操场, 显然,第一轮过后,具有偶数编号的人都 离开了操场。依次做下去,直到操场只剩 下一个人,记这个人的编号为J(N),例 如,J(5)=3,J(10)=5,等等。 则J(400)= _______。 (提示:对J(N)=2m+r进行分析,其中 0≤r<2m)。
289,找规律,数学好的智商分数的比较占优势

N J(n)
m

1 1
0

2 1
1

3 3
1

4 1
2

5 3
2

6 5
2

7 7
2

8 1
3

9 3
3

10 11 12 13 14 15 16 17 5
3

7
3

9
3

11 13 15
3 3 3

1
4

3
4

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

r
2r+1

0
1

0
1

1
3

0
1

1
3

2
5

3
7

0
1

1
3

2
5

3
7

4
9

5

6

7

0
1

1
3

11 13 15

非常容易看出:J(N)=J(2m+r)=2r+1 J(400)=J(28+144)=2*144+1=289

问题求解总结
1、要耐心地寻找规律 2、要冷静的分析问题 3、不到万不得已决不轻言放弃 4、不懂就蒙一个!

阅读程序
1、认真计算 2、耐心分析 3、分析不下去就函数(语句作用) 4、千万记得第一个阅读程序要检查 5、多多练习,熟能生巧 6、列出变量变化表

程序填空
这种题与编程经验和算法学习的程度有 关,拿得一分是一分。不过对于编程经验 不足和算法练习少的人来说也不是没分可 拿。比如说——

程序填空总结
1、分析语句是干什么的,回到开头讲的内容: ①初始化 ②一些明显的动作: a.结果没有储存在需要的地方。 b.累加器没有做加法 c.输出 ③关键动作。 2、不懂就根据上下文猜 3、不写白不写,蒙一下总是好的。 4、千万注意开头和结尾,常常有送分题目!

几个小问题
20. 近20年来, 许多计算机专家都大力推崇 递归算法,认为它是解决较复杂问题的强有 力的工具. 在下列关于递归的说法中, 正确 的是( AC )。 A. 在1977年前后形成标准的计算机高级语言 "FORTRAN77"禁止在程序使用递归, 原因 之一是该方法可能会占用更多的内存空间. B. 和非递归算法相比, 解决同一个问题, 递归算法一般运行得更快一些 C. 对于较复杂的问题, 用递归方式编程往往 比非递归方式更容易一些 D. 对于已定义好的标准数学函数sin(x), 应 用程序中的语句―y=sin(sin(x));‖就是一种 递归调用

16.在下列各软件中,属于 NOIP 竞赛(复 赛)推荐使用的语言环境有( ABD )。

A. gcc/g++ C. Turbo C

B. Turbo Pascal D. free pascal

18. 在下列关于计算机语言的说法中,正 确的有( AB )。 A. Pascal和C都是编译执行的高级语言 B. 高级语言程序比汇编语言程序更容易从 一种计算机移植到另一种计算机上 C. C++是历史上的第一个支持面向对象的 计算机语言 D. 高级语言比汇编语言更高级,是因为它 的程序的运行效率更高

3.在下面各世界顶级的奖项中,为计算机 科学与技术领域作出杰出贡献的科学家设 立的奖项是( D )。 C. 菲尔 B. 诺贝尔奖 A. 沃尔夫奖 兹奖 D. 图灵奖 E. 南丁格尔奖

2. 在关系数据库中, 存放在数据库中的数 据的逻辑结构以( )为主。 C. 哈希表 B. 多叉树 A. 二叉树 D. B+树 E. 二维表

E 数据库有层次型数据库、关系型数据库、 网状数据库 层次是树,关系是二维表,网状是链接指针

19. 在下列关于计算机算法的说法 中,正确的有( BD)。 A. 一个正确的算法至少要有一个输入 B. 算法的改进,在很大程度上推动了 计算机科学与技术的进步由 C. 判断一个算法的好坏,主要依据它 在某台计算机上具体实现时的运行时 间 D. 目前仍然存在许多涉及到国计民生 的重大课题,还没有找到能够在计算 机上实施的有效算法

19. 下列活动中属于信息学奥赛系列活动 的是( )。 A. NOIP B. NOI C. IOI D. 冬令营 E. 国家队选拔赛

ABCDE

16. 处理器A 每秒处理的指令数是处理器B 的2 倍。某一特定程序P 分别编译为处理器A 和处理器B 的指令,编译结果处理器A 的指令数 是处理器B 的4 倍。已知程序P 的算 法时间复杂度为O(n2),如果处理器A执行程序P 时能在一小时内完成的输入规模为n, 则处理器B执行程序P时能在一小时内完成的输 入规模为( )。 A. 4 * n B. 2 * n C. n D. n / 2 E. n / 4 B

彩色显示器所显示的五彩斑斓的色彩,是 由哪三色混合而成的( )。 A. 红 B. 白 C. 蓝 D. 绿 E. 橙 ACD

美籍匈牙利数学家冯· 诺依曼对计算机科学发展 所做出的贡献包括( )。 A提出理想计算机的数学模型,成为计算机科学 的理论基础。 B提出存储程序工作原理,对现代电子计算机的 发展产生深远影响。 C设计出第一台具有存储程序功能的计算机 EDVAC。 D采用集成电路作为计算机的主要功能部件。 E指出计算机性能将以每两年翻一番的速度向前 发展。

AB

下列哪个(些)是64位处理器( )。 A. Intel Itanium B. Intel Pentium III C. AMD Athlon64 D. AMD Opteron E. IBM Power 5 ACDE补充: 双核处理器: AMD速龙(althon)系列,奔腾D,酷睿 系列

幽默一下
20. 在下列关于青少年信息学竞赛的说法中,你赞成的 是( )

A. 举行信息学竞赛的目的,是为了带动广大青少年学科 学、爱科学,为造就一大批优秀的计算机科学 与技术人 才奠定良好的基础 B. 如果竞赛优胜者不能直接保送上大学,我今后就不再 参与这项活动了 C. 准备竞赛无非要靠题海战术,为了取得好成绩,就得 拼时间、拼体力 D. 为了取得好成绩,不光要看智力因素,还要看非智力 因素。优秀选手应该有坚韧不拔的意志,有严谨求实的 作风,既要努力奋进,又要胜不骄败不馁

不是空着就得分

预祝大家初赛取得好成绩!


相关文章:
NOIP初赛知识点复习总结
NOIP初赛知识点复习总结_学科竞赛_高中教育_教育专区。NOIP初赛知识点复习总结 NOIP2011初赛指导 课程大纲 NOIP初赛情况的简单分析 基础知识 二叉树 图 排列组合 程序...
NOIP初赛理论知识复习资料要点摘录
NOIP初赛理论知识复习资料要点摘录_学科竞赛_高中教育_教育专区。要点摘录 ?计算机的诞生与发展 ?微型机的主要技术指标 ?计算机的工作原理 ?总线与接口 ?计算机中数...
信息学奥赛NOIP初赛复习知识点
信息学奥赛 NOIP 初赛复习知识点 1、计算机相关科学家: A: 被西方人誉为“计算机之父”的美籍匈牙利科学家、 数学家 冯· 诺依曼 于 1945 年发表了一个 全新...
noip初赛复习资料(全)
noip初赛复习资料(全)_学科竞赛_高中教育_教育专区。noip初赛复习资料(全) 分区联赛初赛复习初赛考的知识点就是计算机基本常识、 基本操作和程序设计基础知识。 其中...
信息学奥赛NOIP初赛复习知识点+基本函数
信息学奥赛 NOIP 初赛复习知识点+基本函数 1 被西方人誉为“计算机之父”的美籍匈牙利科学家、 数学家 冯· 诺依曼 于 1945 年发表了一个全新的 " 存储程序...
NOIP初赛相关知识点及参考答案
相关知识点与参考答案一.单项选择题 1、操作系统是系统软件的核心,是有效利用...noip2002初赛试题及答案 7页 免费 NOIP初赛知识点复习总结 86页 1下载券 NOIP...
信息学奥赛NOIP初赛复习知识点
信息学奥赛 NOIP 初赛复习知识点 1、计算机相关科学家: A:被西方人誉为“计算机之父”的美籍匈牙利科学家、 数学家 冯 ·诺依曼 于 1945 年发表了一个 全新的...
信息学奥赛NOIP初赛复习知识点
信息学奥赛 NOIP 初赛复习知识点 1、计算机相关科学家: A: :被西方人誉为“计算机之父”的美籍匈牙利科学家、 数学家 冯· 诺依曼 于 1945 年发表了一个 ...
普及组NOIP初赛复习——基础知识STU
普及组NOIP初赛复习——基础知识STU_其它课程_高中教育_教育专区。分区联赛初赛复习 初赛考的知识点就是计算机基本常识、基本操作和程序设计基础知识。其中 选择题考...
NOIP初赛知识汇总
13. 14. NOIP 初赛知识汇总 现代计算机的结构是由美籍匈牙利数学家“冯.诺依曼”提出来的“程序存储”结构,它包 括“运算器”“控制器”“存储器”“输入设备”...
更多相关标签: