NOIP普及组初赛单项选择题

NOIP普及组初赛单项选择题 NOIP 普及组初赛单项选择复习资料 整理者:马鞍山市二中实验学校 陆华，授课:陈中 计算机结构与组成原理 一、计算机发展及应用 1、第一台电子计算机的诞生: ENIAC 1946年，世界上第一台数字式电于计算机是由美固宾夕法尼亚大学的物理学家约翰?莫克利(John Mauchly)和 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 师普雷斯伯?埃克特(J.hesper.Eckert)领导研制的取名为ENIAC(Elecotmnic Nurnerical Integrator And Calculator)的计算杌。 2、第一台具有存储程序功能的计算机:EDVAC。 1903年，冯?诺伊曼(Neumann，John von)出生于匈牙利的布达佩斯。冯?诺依曼依据存储程序的工作原理设计. 运算器、控制器、存储器、输人设备和输出设备这五部分组成，同ENIAC相比，EDVAC 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 有两个重大改进:(1):采用了二进制;(2):提出了“存储程序”。 3、图灵机和图灵奖 艾伦?麦席森?图灵(Alan Mathison Turing，1912年6月23日 - 1954年6月7日)，英国数学家。 图灵机由三部分组成，包括一条 带子、一个读写头和一个控制装置。 图灵对于人工智能的发展有诸多贡献，例如:图灵曾写过一篇名为《机器会思考吗,》(Can Machine Think?)的论文，其中提出了一种用于判定机器是否具有智能的试验方法，即图灵试验。 图灵奖是美国计算机协会于1966年设立的，又叫"A.M.图灵奖"，专门奖励那些对计算机事业作出重要贡献的个人。其名称取自计算机科学的先驱、英国科学家艾伦?图灵，这个奖设立目的之一是纪念这位科学家。 4、世界上第一位软件工程师 英国著名诗人拜伦的女儿Ada Lovelace(爱达).由于她在程序设计上的开创性工作，Ada Lovelace被称为世界上”第一位程序员”。“世界上第一位软件工程师”。 5、微型计算机的问世 第四代 1972——至今 超大规模集成电路的微星计算机个人PC 应用到了各个领域。 二、硬件系统的组成: 1、冯?诺伊曼体系 其思想是，在计算机中设置存储器，将符号化的计算步骤存放在存储器中，然后依次取出存储的内容，由一个被称之为控制器的部件进行译码，译码结果在一个被称为运算器的部件中进行计算，从而实现计算机工作的自动化(运算器和控制器统称为CPU)。 五个基本部分组成:(1)运算器，(2)控制器，(3)存储器，(4)输人设备，(5) - 1 - 输出设备 计算机的整个工作过程及基本硬件结构如图2-8所示: 图2-8 计算机系统的基本硬件组成及工作原理 2、计算机的三总线结构 总线是一组导线、是公共通路，微型计算机中各个组成部件之间的信息传输都是通过它们来实现的 地址总线(AB)是单向总线，用以传送CPU向外设或存储器发出的地址信息。 数据总线(DB)是双向总线，用以CPU与内存或接口之间传输数据信息。 控制总线(CB)是双向总线，有的作为输出，有的作为输入，用以CPU与内存或I/O接口之间传送控制信息。 分别传送地址信号、数据信号和控制信号。 软件系统 1、系统软件: (,)操作系统软件: DOS, OS/2 ，Windows 9x,Windows 2000, Windows XP, Windows Vista, Win7 Netware，Windows NT, Windows Server 200x，Unix, Linux，iOS4，Android 3.0 (,)计算机语言: 机器语言 汇编语言 高级语言:Logo, Basic, Pascal, c, c++, Viscal Basic, Java, Go等。 2、应用软件: Wps，Office (word, powerpoint, excel),3dmax, flash, photoshop等. - 2 - 3、面向对象编程语言 面向对象语言(Object-Oriented Language)是一类以对象作为基本程序结构单位的程序设计语言，它之前呢,是面向过程。而现在呢,面向切面(AOP)。 一种是纯面向对象语言，如Smalltalk、EIFFEL等 。 混合型面向对象语言，即在过程式语言及其它语言中加入类、继承等成分，如C++、Objective-C等。Visual Basic, Java 面向切面(AOP)与面向对象(OOP)，MM和OO的故事。 计算机中数字 数值信息在计算机内的 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示方法就是用二进制数来表示。 一般说来，如果数制只采用R个基本符号，则称为基R数值，R称为数制的基数，而数制中每一固定位置对应的单位值称为权。 进位计数制的编码符合“逢R进位”的规则，各位的权是以R为底的幂，一个数可按权展开成为多项式。例如，一个十进制数256.47可按权展开为 21-1-2256.47=2×10，5×10，6×10?十4×10，7×10 1、R进制转换为十进制 基数为R的数字，只要将各位数字与它的权相乘，其积相加,和数就是十进制数 例: 3506.2 8123-1=6×8?+0×8+5×8+3×8+2×8 =1862.25 例: 0.2A 16-1-2=2×16+10×16 =0.1640625 2、十进制转换为R进制 十进制整数转换成R进制的整数: 除R取余法。 例: (89) ,(1011001) 102 2 89 2 44 „„1 2 22 „„0 2 11 „„0 2 5 „„1 2 2 „„1 2 1 „„0 0 „„1 十进制小数转换成R进制时: 乘R取整. - 3 - 例: (0(625)= (0(101) 102 0(625 X 2 1(25 1 X 2 0(5 0 X 2 1(0 1 3、二、八、十六进制的相互转换 每位八进制数相当于三位二进制数，每位十六进制数相当于四位二进制数。在转换时， 位组划分是以小数点为中心向左右两边延伸，中间的0不能省略，两头不够时可以补0。尤 其是小数后末尾的0 例如:将1011010.1转换成八进制和十六进制数 2 001 011 010. 100 1011010.1,132.4 28 1 3 2. 4 0101 1010. 1000 1011010.1=5A.8 216 5 A . 8 例如:将十六进制数F7.28变为二进制数 F 7 . 2 8 F7.28=11110111.00101 1621111 0111.0010 1000 二、在计算机中带符号数的表示法 1、原码: 在用二进制原码表示的数中，符号位为0表示正数，符号位为1表示负数，其余各位表 示数值部分。 如:10000010，00000010 2、反码: 反码的定义如下: ?对于正数，它的反码表示与原码相同。即[x]反=[x]原 ?对于负数，则除符号位仍为“1”外，其余各位“1”换成”0”，”0”换成1”，即得 到反码[X]反。例如[-1101001] 反=10010110。 ?对于0，它的反码有两种表示:[+0] 反=00„0 [-0] 反=11„1 3、补码: 正数的补码就是该正数本身。 [01100100]补 ,01000100 对于负数:两头的1不变，中间取反。 [10100100]补 ,11011100 [+0]补,[-0]补,00„0。 4、BCD码(8421码) BCD码就是用二进制代码表示的十进制数，也称BCD数。它是用4位二进制代码 0000—1001来表示十进制数0---9。如:39的BCD码为00111001。 四、ASCII码 American Standard Code for Information Interchange) 美国标准信息交换代码 将每个字符用7位的二进制数来表示，共有128种状态 大小字母、0„9、其它符号、控制符 - 4 - ‘ 0 ’ ―― 48 ‘ A ’ ―― 65 ‘ a ’ ―― 97 五、信息存储单位 ?位(bit，缩写为b):度量数据的最小单位，表示一位二进制信息。 ?字节(byte，缩写为B):一个字节由八位二进制数字组成(l byte,8bit)。字节是信息存储中最常用的基本单位。 计算机存储器(包括内存与外存)通常也是以多少字节来表示它的容量。常用的单位有: KB 1K=1024 MB 1M=1024K GB 1G=1024M TB 1T=1024G 3、机器字(word):字是位的组合，并作为一个独立的信息单位处理。字又称为计算机字，它取决于机器的类型、字长以及使用者的要求。常用的固定字长有8位、16位、32位等。 计算机网络的基本概念 一、 计算机网络分类 计算机网络的分类方式有很多种,可以按地理范围、拓扑结构、传输速率和传输介质等分类。 地理范围分类: ?局域网LAN(Local Area Network)，?城域网MAN(Metropolitan Area Network)?广 域网WAN(Wide Area Network)，广域网地理范围一般在几千公里左右,属于大范围连网。 如几个城市,一个或几个国家,是网络系统中的最大型的网络,能实现大范围的资源共享, 如国际性的Internet 网络。 按传输介质分类 传输介质是指数据传输系统中发送装置和接受装置间的物理媒体,按其物理形态可以划分为有线和无线两大类。 ?有线网，光纤和双绞线，10M/100M/1000M ?无线网，802.a b c n 协议 离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载 。 二、计算机网络体系结构的核心是OSI模型 国际标准化组织(ISO)提出的开放系统互联参考模型(OSI)已成为网络体系结构的标准 ?网络协议 常见的网络协议有IPX/SPX, TCP/IP等。 ?网络互联模型 国际标准化组织ISO( International Standardization Organization)于1981年推出“开放系统互联结构模型”即OSI(OpenSystem Interconnection)标准。OSI不是一个实际的物理模型,而是一个将网络协议规范化了的逻辑参考模型。图1.6.3是OSI 七层模型图。 - 5 - 图 1.6.3 OSI 七层参考模型 通常把计算机网络分成通信子网和资源子网两大部分。OSI 参考模型的低三层:物理层、数据链路层和网络层归于通信子网的范畴;高三层:会话层、表示层和应用层归于资源子网的范畴。传输层起着承上启下的作用。 三、Internet 网络地址 (IP地址) 现在的Internet最早起源于60 年代末期美国国防部的ARPAnet(阿帕网)。 通常一个IPv4地址共有32 位，分为4 段，每段8 位(也即1 个字节)。它的表示方法如下:xxx，xxx，xxx，xxx，其中每段的取值范围为0,255。IP地址是Internet上主机的一种数字标识，它由两部分组成，一部分是网络标识(netid)，另一部分是主机标识(hostid)。 第一段取值在1,127之间，表示主机所在的网络属于大型网(A类网)，其_____值就是网络的网络号，后三段数字表示该主机号; 第一段数字取值在128,191 之间，表示主机所在网络为中型网(B 类网)，第一段和第二段的数字联合表示该网络的网络号，第三段数字则表示子网号，第四段则是该主机号; 第一段数字取值为192,223 的，表示该主机所在的网络为小型网(C 类网)，第一、二、三段数字的组合表示该网络的网络号，第四段是主机号。网站的IP地址就是203.207.226.84，则表示它的主机是属于C 类网，203.207.226是它所在网络的网络号，其主机号为84。 什么是IPv6、保留地址和域名, 逻辑运算 ? 运算:与或非，异或 ? 运算的优先级:非,与,或 1、“与” 运算( “?”， “?” ，and) 在逻辑问题中，如果决定某一事件发生的多个条件必须同时具备，事件才能发生，则这种因果关系称之“与”逻辑(并且)。 “与”运算又称为逻辑乘，其运算符号为“?”，有时也用“?”表示。 F = A?B 或者 F = A?B 0?0 = 0 1?0 = 0 0?1 = 0 1?1 = 1 结论:若A、B均为1，则F为1;否则，F为0 推广:A?0=0 A?1=A 2、“或”运算( “+”， “?” ,or 在逻辑问题的描述中，如果决定某一事件是否发生的多个条件中，只要有一个或一个以上条件成立，事件便可发生，则这种因果关系称之为“或”逻辑。 “或”运算又称逻辑加， - 6 - 其运算符号为“+”，有时也用“?”表示。两变量“或”运算的关系可表示为 F = A + B 或者 F = A ? B 0 + 0 = 0 1 + 0 = 1 0 + 1 = 1 1 + 1 = 1 结论:仅当A、B均为0时，F才为0 推广:A+0=A A+1=1 3.“非”运算 ? 在逻辑问题中，如果某一事件的发生取决于条件的否定，即事件与事件发生的条件之间构成矛盾，则这种因果关系称为“非”逻辑。“非”运算也叫求反运算或者逻辑否定。其运算符号为“-”，有时也用“?”表示。 “非”运算的逻辑关系可表示为 F= 或者 F = ?A “非”运算的运算法则为 =1 =0 字符串和表达式 一、在C++语言中逻辑运算 && and 与 || or 或 ! not 非 二、字符串 NOI2009、NOIP2009竞赛环境说明 分类 软件 版本 说明 内核 - 2.6.24 系统软件 NOI Linux 操作系统 NOILinux – 1.2 Gcc 4.1.2 C编译器 G++ 4.1.2 C++编译器 编译器 Freepascal 2.0.4 Pascal编译器 Gdb 6.6 命令行启动 调试器 Ddd 3.3.11 命令行启动 单文件程序IDEGUIDE 1.0.0 (C/C++/Pascal) 集成开发环境 Anjuta 1.2.4 C/C++ IDE Lazarus 0.9.22 Pascal IDE 从参考资料来看:市面上大部分关于NOI的辅导、参考资料都是基于Free pascal的;当然新版本的辅导、参考资料也有用C/C++写的，特别是比较有名的教练写的新书或参考资 - 7 - 料、大牛们写的解题 报告 软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载 也多数都采用了C/C++。 集合的运算 算法 一、递归 递归在计算机中的实现计算机执行递归算法时，是通过栈来实现的。 数据结构入门 一、复杂度: 算法分析，就是复杂度的问题。复杂度只算“最要命的”，比如，执行n^2的算法前来个快排根本不拖速度，n^2多的都豁出去了不在乎区区一个nlogn。书里对复杂度进行了严格的定义，包括O()、o()、Θ()、Ω()四种符号。简单地说，O(n^2)就是顶破天了搞个n^2次;o(n^2)就是天花板不到n^2，比n^2矮一点(比如希尔排序就是o(n^2)，因为它再倒霉也达不到n^2);Ω(n^2)就是说某个算法随便怎么至少都要耗费n^2，比如所有基于比较的排序都是Ω(nlogn);Θ(n^2)就是说它即是O(n^2)又是Ω(n^2)，被天花板和水泥地夹在中间了，动不了了，就是它了。这里面有一个经典的例子，就是最大子序列(找数列中连续一段数之和最大)的四种算法，复杂度分别为O(n^3)、O(n^2)、O(nlogn)和O (n)。这书一个特色在于，对每种数据结构都有严格的算法复杂度证明，这往往是看上去最头痛的部分。 二、表、栈和队列: 表、栈和队列是三个基本的数据结构。说穿了表就是把数据找起来排排坐吃果果，找什么东西都来把整个队伍找一遍。 栈就是一个桶，后放进去的先拿出来，它下面本来有的东西要等它出来之后才能出来，就好像你看到了一个丑人不可能今天的中饭还没吐出来就先把早饭吐出来了。栈是拿来模拟多个过程的调用的(比如递归)，实际点的用途就是表达式计算。 队列好比堵车，先进去的先出来。先进队先买票，不能插队。常拿来实现广搜。(BaihowFF注:广搜就是一般说的广度优先搜索,即BPS) - 8 - 二叉树 一、二叉树定义: 是另一种树形结构，他的特点是每个节点至多只有两棵子树，并且，二叉树的子树有左右之分，其次序不能任意颠倒。 二、二叉树的性质: i-1性质1:在二叉树的第i层上至多有2 个结点。(i?1) k性质2:深度为k的二叉树上至多含2-1个结点(k?1) 性质3:对任何一棵二叉树，若它含有n个叶子结点、n个度为2的结点，则必存在关系02 式:n = n+1。通俗点说:即叶子节点比二叉节点(分支节点)数多一个。 02 满二叉树:叶结点个数为N，则它的结点总数为2 * N – 1。 完全二叉树:在满二叉树的最底层自右向左依次去掉若干个节点得到的二叉树。 性质4:n层完全二叉树，深度为N，节点数为(2^N)-1，叶子节点为2^(N-1)，2^N表示2的N次方。 三、二叉树的遍历: 三种遍历的顺序分别是这样的: ? 前序遍历:根-左-右 ? 中序遍历:左-根-右 ? 后序遍历:左-右-根 四、经典问题: 若某二叉树的前遍历访问顺序是序abdgcefh,中序遍历顺序是dgbaechf,则后序遍历的访问顺序是什么。 解答:此题的解答过程如下: (1)由前序遍历结果我们可知a为根结点，再看中序遍历结果，因为中序遍历顺序是左子树、根、右子树，因此由“中序遍历顺序是dgbaechf”可断定，dgb为该二叉树的左子树中序遍历结果，echf为右子树中序遍历结果。 (2)由前序遍历结果可知，左子树的前序遍历结果是bdg,右子树的前序遍历结果是cefh;因此，和第一步分析类似，可知b为左子树的根，再由“dgb为该二叉树的左子树中序遍历结果”可知，dg为该左子树的左子树的中序遍历结果，再由dg在前序遍历结果中排列顺序dg可知，d为根，因此由“dg为该左子树的左子树的中序遍历结果”可推出g为d的右孩子。 到此为止，可以完全推断出该二叉树的左子树的结构了。 按照同样方法，可以推断出该二叉树的右子树的结构，因此整个二叉树的结构图如下: 据此图，不难看出该二叉树的后序遍历结果是:gdbehfca. - 9 - 五、按层次遍历二叉树 自然表达式转换为前/中/后缀表达式，其实是很简单的。首先将自然表达式按照优先级顺序，构造出与表达式相对应的二叉树，然后对二叉树进行前/中/后缀遍历，即得到前/中/后缀表达式。 举例说明将自然表达式转换成二叉树: a×(b+c)-d ? 根据表达式的优先级顺序，首先计算(b+c)，形成二叉树 ?然后是a×(b+c)，在写时注意左右的位置关系 ?最后在右边加上-d 所以还是以刚才的这个例子，在最终二叉树的基础上可以得出: 前缀表达式:-*a+bcd 中缀表达式:a*b+c-d 后缀表达式:abc+*d- 排序与查找 一、各排序算法时间复杂度比较 (1)冒泡排序;冒泡排序算法时间复杂度是O(n^2)。 (2)选择排序;选择排序算法复杂度是O(n^2)。 (3)插入排序;插入排序算法时间复杂度是O(n^2) (4)快速排序;最理想情况算法时间复杂度O(nlog2n)，最坏O(n^2)。快速排序快速排序是不稳定的。 (5)堆排序;堆排序算法时间复杂度O(nlogn)。 (6)归并排序;归并排序的时间复杂度是O(nlog2n)。 (2)选择排序 首先在未排序序列中找到最小元素，存放(交换任意两个元素)到排序序列的起始位置， - 10 - 然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。要经过n-1趟。 二、非比较排序算法 计数排序, 基数排序, 桶排序等非比较排序算法,平均时间复杂度都是O(n). 这些排序因为其待排序元素本身就含有了定位特征,因而不需要比较就可以确定其前后位置,从而可以突破比较排序算法时间复杂度O(nlgn)的理论下限. 三、查找 (1)二分查找算法 二分查找算法先比较位于集合中间位置的元素与键的大小，有三种情况(假设集合是从小到大排列的): 键小于中间位置的元素，则匹配元素必在左边(如果有的话)，于是对左边的区域应用二分搜索。 键等于中间位置的元素，所以元素找到。 键大于中间位置的元素，则匹配元素必在右边(如果有的话)，于是对右边的区域应用二分搜索。 注:比较次数n次，可查找元素个数2^n-1个。 信息技术的新发展 虚拟化技术:服务器虚拟化，存储与客户端虚拟化。 云计算:“云计算”提供数据存储和平台测试等网络服务。 客户端变革:虚拟化技术的流行，将为客户端计算机技术带来新的变革。 移动应用程序竞争:目前，苹果i-Phone应用程序，谷歌Android明年将推出大量新机型，移动应用程序市场的竞争将进一步加剧。 实时搜索(Real-Time Search):Amit Singhal正在Google领导着一个团队挖掘社会化网络的信息，提供与传统Web搜索相同质量和价值的信息。 其他 图论 排列组合题目特难只能放弃，每次考试大约1题。 整理日期:2010-09-15 联系方式 陆华 EMAIL: 54422138@qq.com 陈中 EMAIL: rickchen@163.com - 11 -