当前位置:首页 >> 学科竞赛 >> 信息学奥赛NOIP初赛复习知识点+基本函数

信息学奥赛NOIP初赛复习知识点+基本函数


信息学奥赛 NOIP 初赛复习知识点+基本函数
1 被西方人誉为“计算机之父”的美籍匈牙利科学家、 数学家 冯 · 诺依曼 于 1945 年发表了一个全新的 " 存储程序通用电子计算机方案 "— EDVAC 。 EDVAC 方案提出了著名的“ 冯· 诺依曼体系结构”理论: (1)采用二进制形式表示数据和指令(2)采用存储程序方式(3) 由运算器、存储

器、控制器、输入设备和输出设备五大部件组成计算机系统 2 “图灵机”与“冯· 诺伊曼机”齐名,被永远载入计算机的发展史中。1950 年 10 月,图灵又发表了另一篇题为“机器能思考吗”的论文,成为划 时代之作。也正是这篇文章,为图灵赢得了“人工智能之父”的桂冠。与计算机有关的最高奖项“图灵奖”。 3 常见的操作系统有:DOS、WIN32、WIN95、WIN98、WIN2000、WINXP、WIN2003、LINUX、 4 断电后能保存信息的有:ROM(只读存储器)、硬盘、软盘、光盘、U 盘、MP3、MP4 等;不能保存的主要是 RAM(读写存储器)。 5CPU 又名中央处理器,它可以分成运算器、控制器和寄存器 6Smalltalk 被认为是第一个真正面向对象的语言 7 第一代语言: 机器语言 (0101001) ; 第二代语言: 20 世纪 50 年代, 汇编语言, 第三代语言: 高级语言、 算法语言, 如 BASIC, FORTRAN, COBOL,PASCAL,C;高级语言的特点是可读性强,编程方便;第四代语言:非过程化语言;SQL;第五代语言:智能性语言,PROLOG (代表);还有:LISP,APL,SNOBOL,SIMULA。 8 编程时读入一个很大的二维数组,按行读和按列读相比,输入效率上(取决于数组的存储方式)。 9 希尔排序是一种不稳定的排序 快速排序是冒泡排序的改进,是速度最快的排序方法

排序方法
简单排序 (采用比较为主要 操作的算法)

时间复杂 度 O(n^2) O(n^2) O(n^2) O(nlogn)

最好时间复杂 度 O(n) O(n^2) O(n) O(nlogn)

最坏时间复杂 度 O(n^2) O(n^2) O(n^2) O(n^2)

是否稳定 稳定 不稳定 稳定 不稳定

空间复杂 度 O(1) O(1) O(1) O(logn)

插入排序 选择排序 冒泡排序 快速排序

①n 比较小的时候,适合插入排序和选择排序;②基本有序的时候,适合直接插入排序和冒泡排序;④n 很大的时候,适合快速排序、堆 排序 、归并排序;⑤无序的时候,适合快速排序; ⑥稳定的排序:冒泡排序、插入排序、归并排序、基数排序;⑦复杂度是 O(nlogn):快速排序、堆排序、归并排序; ⑧辅助空间(大 次大):归并排序、快速排序;⑨好坏情况一样:简单选择排序(n^2),堆排序(nlogn),归并排序(nlogn); ⑩最好是 O(n)的:插入排序、冒泡排序。 10PASCAL 语言中,表达式(21 XOR 2)的值是(23) 11PASCAL 语言,判断 a 不等于 0 且 b 不等于 0 的正确的条件表达式是(a<>0)and(b<>0) 12 高度为 N 的均衡的二叉树是:如果去掉叶结点及相应的树枝,它应该是高度为 N-1 的满二叉树。在这里,树高等于叶结点的最大深度, 根结点的深度为 0,如果某个均衡的二叉树共有 2381 个结点,则该树的树高为(11)。

13 结点的度:一个结点的子树数目称为该结点的度树的度:所有结点中最大的度称为该树的度(宽度)。(3)树的深度(高度) :树是分
层次的。结点所在的层次是从根算起的。根结点在第一层,根的儿子在第二层,其余各层依次类推。树中最大的层次称为树的深度,亦称 高度。 14 满二叉树: 若深度为 K 的二叉树,共有 2K-1 个结点,即第 I 层有 2I-1 的结点,称为满二叉树。 15 完全二叉树:如果一棵二叉树最多只有最下面两层结点度数可以小于 2,并且最下面一层的结点都集中在该层最左边的若干位 置上,则称此二叉树为完全二叉树 16 二叉树的三个主要性质: 性质 1:在二叉树的第 i(≥1)层上,最多有 2i-1 个结点 性质 2:在深度为 k(k≥1)的二叉树中最多有 2k-1 个结点。 性质 3:在任何二叉树中,叶子结点数总比度为 2 的结点多 1。n0=n2+1 17 数的表示:为了表达方便起见,常在数字后加一缩写字母后缀作为不同进制数的标识。各种进制数的后缀字母分别为: B:二进制数。Q:八进制数。D:十进制数。H:十六进制数。对于十进制数通常不加后缀,也即十进制数后的字母 D 可省略 18 广度优先需要用到的是 队列,深度优先需要 的是栈 19 回溯法(探索与回溯法)是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达 不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法。动态规划把多阶段过程转化为一系列单阶段问题,利用 1 1

各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法——动态规划。贪心算法(又称贪婪算法)是指,在对问题 求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。 一、数学函数: Inc(i) 使 I:=I+1; Inc(I,b) 使 I:=I+b; Abs(x) 求 x 的绝对值 例:abs(-3)=3 Chr(x) 求编号 x 对应的字符。例:Chr(65)=?A? chr(97)=?a? chr(48)=?0? Ord(x) 求字符 x 对应的编号。 例:ord(?A?)=65 ord(?a?)=97 另 外:ord(false)=0 ord(true)=1 Sqr(x) 求 x 的平方。 例:sqr(4)=16 Sqrt(x)求 x 的开方. 例:sqrt(16)=4 round(x) 求 x 的四舍五入 例:round(4.5)=5 trunc(x) 求 x 的整数部分 例:trunc(5.6)=5 结果是 integer 型 int(x) 求 x 的整数部分 例 int(5.6)=5.0 frac (x)求 x 的小数部分 例 frac(5.6)=0.6 pred(x) 求 求 x 的 前 导 的 后 继 pred(?b?)=?a? succ(?b?)=?c? pred(5)=4 succ(5)=6

个位置 例:s:=abc;insert(?12?,s,2);结果 s:=?a12bc? 5. 求字符串长度 length(s) 例:length(?12abc?)=5 6. 搜索子串的位置 pos(s1,s2) 如果 s1 是 s2 的子串 ,则 返回 s1 的第一个字符在 s2 中的位置,若不是子串,则返 回 0. 例:pos(?ab?,?12abcd?)=3 7. 字符的大写转换。Upcase(ch) 求字符 ch 的大写体。 例:upcase(?a?)=?A? 8. 数值转换为数串。 过程 Str(x,s) 把数值 x 化为数串 s. 例:str(12345,s); 结果 s=?12345? 9. 数串转换为数值。过程 val(s,x,i) 把数串 s 转化为数值 x, 如果成功则 i=0,不成功则 i 为无效字符的序数 例:val(?1234?,x,I);结果 x:=1234 xor :异或运算 shr:位运算 相当于/2 shl:位运算 相当于*2,但是比*运算快的多的多 int : 求一个实型数的整数部分 arc tan:反正切函数 xor:异或运算,就是把两个数转换成二进制数,然后每位 对应,如果相同(都是 0 或 1)就得 1,如果不同就得 0 shl:左位移(左位移一位=*2,左位移两位=*2^2……a shl b=a*2^b) shr:右位移(右位移一位=/2,右位移两位=/2^2……a shl b=a/2^b) 取整函数 int(x) 注意:X 是实型数,返回值也是实型的;返 回的是 X 的整数部分,也就是说,X 被截尾了(而不是四舍 五入)

pred(true)=false succ(x) x

succ(false)=true odd(x) 判断 x 是否为奇数。 如果是值为 true, 反之值为 false. Odd(2)=false odd(5)=true power(a,n) 求 a 的 n 次方 power(2,3)=8 exp(b*ln(a)) a 的 b 次方 random 取 0~1 之间的随机数(不能取到 1) randomize 随机数的种子函数,在每次设置随机数时都要把 这个函数放在最前面. Fillchar(a,size(a),0) 数组初始化,即把数组 a 的值全部置 为0 二、字符串函数 1. 连接运算 concat(s1,s2,s3…sn) 相当于 s1+s2+s3+…+ sn. 例:concat(?11?,?aa?)=?11aa?; 2. 求子串。 Copy(s,i,L) 从字符串 s 中截取第 i 个字符开始 后的长度为 L 的子串。 例:copy(?abdag?,2,3)=?bda? 3. 删除子串。过程 Delete(s,i,L) 从字符串 s 中删除第 i 个 字符开始后的长度为 L 的子串。例:s:=?abcde?;delete(s,2, 3);结果 s:=?ae? 4. 插入子串。 过程 Insert(s1,s2,I) 把 s1 插入到 s2 的第 I 2

2


更多相关文档:

信息学奥赛NOIP初赛复习知识点+基本函数

信息学奥赛 NOIP 初赛复习知识点+基本函数 1 被西方人誉为“计算机之父”的美籍匈牙利科学家、 数学家 冯· 诺依曼 于 1945 年发表了一个全新的 " 存储程序...

信息学奥赛NOIP初赛复习知识点

信息学奥赛NOIP初赛复习知识点_其它课程_高中教育_教育专区。信息学奥赛 NOIP ...函数或表达式: A:PASCAL 语言中,表达式(21 XOR 2)的值是(23) B:PASCAL ...

信息学奥赛NOIP初赛复习知识点

信息学奥赛 NOIP 初赛复习知识点 1、计算机相关科学家: A:被西方人誉为“...函数或表达式: A:PASCAL 语言中,表达式(21 XOR 2)的值是(23) B:PASCAL ...

信息学奥赛NOIP初赛复习知识点

信息学奥赛 NOIP 初赛复习知识点 1、计算机相关科学家: A: :被西方人誉为“...函数或表达式: A:PASCAL 语言中,表达式(21 XOR 2)的值是(23) : B:PASCAL...

信息学奥赛NOIP初赛复习

信息学奥赛NOIP初赛复习_学科竞赛_高中教育_教育专区。分区联赛初赛复习初赛考的知识点就是计算机基本常识、 基本操作和程序设计基础知识。 其中选择题考查 的是知识...

noip初赛复习资料(全)

noip初赛复习资料(全)_学科竞赛_高中教育_教育专区...分区联赛初赛复习初赛考的知识点就是计算机基本常识、...(0~12),Hash 函数是:H(key)=key % 13,其中%...

NOIP初赛相关知识点及参考答案

NOIP初赛相关知识点及参考答案_学科竞赛_高中教育_...108 用户在网上最常用信息查询工具叫搜索引擎。 ...NOIP初赛知识点复习总结 86页 1下载券 NOIP2010普及...

信息学奥赛初赛复习题

信息学奥赛初赛复习题_学科竞赛_高中教育_教育专区。...输入:aabbccwwabcabc 6 四、函数与过程 [要点]...NOIP2010信息学奥赛初赛... 8页 1下载券 第十四...

2016NOIP初赛复习资料

2016NOIP初赛复习资料_其它考试_资格考试/认证_教育...全国分区联赛初赛复习初赛考的知识点就是计算机基本...(0~12),Hash 函数是:H(key)=key % 13,其中%...

信息学奥赛初赛复习2012-16K

信息学奥赛初赛复习2012-16K_学科竞赛_小学教育_教育...中国信息学联赛 答案:A (NOIP 分区联赛 IOI 国际)...函数与过程 [要点]参数,前面加 VAR 的参数,在函数...
更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com