还剩21页未读，继续阅读
本资源只提供10页预览，全部文档请下载后查看！喜欢就下载吧，查找使用更方便
文本内容:
普与组初赛单项选择复习资料NOIP整理者马鞍山市二中试验学校，授课计算机结构与组成原理
一、计算机发展与应用、第一台电子计算机的诞生1ENIAC年，世界上第一台数字式电于计算机是由美固宾夕法尼亚高校的物1946理学家约翰•莫克利和工程师普雷斯伯-埃克特John Mauchly领导研制的取名为J.hesper.Eckert ENIAC ElecotmnicNumerical的计算机Integrator AndCalculator、第一台具有存储程序功能的计算机2EDVACo年，冯•诺伊曼诞生于匈牙利的布达佩斯1903Neumann,John von冯・诺依曼依据存储程序的工作原理设计.运算器、限制器、存储器、输人设备和输出设备这五部分组成，同ENIAC相比，方案有两个重大改进接受了二进制；提出了“存储EDVAC1:2:程序”、图灵机和图灵奖3艾伦•麦席森•图灵年月日・Alan MathisonTuring,1912623年月日，英国数学家195467图灵机由三部分组成，包括一条带子、一个读写头和一个限制装置图灵对于人工智能的发展有诸多贡献，例如图灵曾写过一篇名为
二、计算机网络体系结构的核心是模型OSI国际标准化组织（）提出的开放系统互联参考模型（）已成为网ISO OSI络体系结构的标准⑴网络协议常见的网络协议有等IPX/SPX,TCP/IP⑵网络互联模型国际标准化组织（）ISO InternationalStandardization Organization于年推出“开放系统互联结构模型”即（1981OSI OpenSystem）标准不是一个实际的物理模型,而是一个将网络协Interconnection OSI议规范化了的逻辑参考模型图是七层模型图OSI应用层______表示层______会话层传输层网络层数据链路层物理层图七层参考模型
1.
6.3OSI通常把计算机网络分成通信子网和资源子网两大部分参考模型的低OSI三层物理层、数据链路层和网络层归于通信子网的范畴;高三层会话层、表示层和应用层归于资源子网的范畴传输层起着承上启下的作用
三、网络地址（地址）Internet IP现在的最早起源于年头末期美国国防部的（阿帕Internet60ARPAnet网）通常一个地址共有位，分为段，每段位（也即个字节）IPv432481它的表示方法如下其中每段的取值范围为XXX,XXX,XXX,XXX,〜255o地址是上主机的一种数字标识，它由两部分组成，一部分是网络IP Intemet标识（）另一部分是主机标识（）netid,hostido第一段取值在1〜127之间，表示主机所在的网络属于大型网（A类网），其_____值就是网络的网络号，后三段数字表示该主机号；第一段数字取值在128〜191之间，表示主机所在网络为中型网（B类网），第一段和其次段的数字联合表示该网络的网络号，第三段数字则表示子网号，第四段则是该主机号；第一段数字取值为192〜223的，表示该主机所在的网络为小型网（类网），第
一、
二、三段数字的组合表示该网络的网络号，第四段是主C机号网站的地址就是则表示它的主机是属于类网，IP
203.
207.
226.84,C是它所在网络的网络号，其主机号为84什么是、保留地址和域名？IPv6逻辑运算运算与或非，异或♦运算的优先级非＞与＞或♦、“与”运算（・，）1““A”,and在逻辑问题中，假如确定某一事务发生的多个条件必需同时具备，事务才能发生，则这种因果关系称之“与”逻辑（并且）“与”运算又称为逻辑乘，其运算符号为“・”，有时也用“八”表示两变量“与”运算关系可表示为或者F=A-B F=AAB“与”运算的运算法则为0-0=01-0=00-1=01-1=1结论:若、均为则为否则，为A B1,F1;F推广A♦0=0A•1=A、“或”运算（“+”，）2“V”,or在逻辑问题的描述中，假如确定某一事务是否发生的多个条件中，只要有一个或一个以上条件成立，事务便可发生，则这种因果关系称之为“或”逻辑“或”运算又称逻辑加，其运算符号为“+”，有时也用表示两变量“或”“V”运算的关系可表示为或者F=A+B F=AVB“或”运算的运算法则为0+0=01+0=10+1=11+1=1结论仅当、均为时，才为A BF0推广A+0=A A+l=l“非”运算「
3.-NOT在逻辑问题中，假如某一事务的发生取决于条件的否定，即事务与事务发生的条件之间构成冲突，则这种因果关系称为“非”逻辑“非”运算也叫求反运算或者逻辑否定其运算符号为、”，有时也用表示“非”运算的逻辑关系可表示为或者F=A F=nA0=11=0“非”运算的运算法则为字符串和表达式
一、在语言中逻辑运算C++与and或II or非!not
二、字符串、竞赛环境说明NOI2023NOIP2023分类软件版本说明内核-系统软件操作系统NOI LinuxNOILinux-
1.2编译器Gcc C编译器编译器G++C++编译器Free PascalPascal叮嘱行启动Gdb
6.6调试器叮嘱行启动Ddd集成开发环单文件程序GUIDE IDE境C/C++/PascalAnjuta C/C++IDELazarus PascalIDE从参考资料来看市面上大部分关于的辅导、参考资料都是基于NOI Free当然新版本的辅导、参考资料也有用写的，特别是比较出名pascal ftj;C/C++的教练写的新书或参考资料、大牛们写的解题报告也多数都接受了C/C++、集合的运算并、交、林、差1并g u交，c-补,-或成〜集合的运算AAUR ACR算法
一、递归递归在计算机中的实现计算机执行递归算法时，是通过栈来实现的数据结构入门
一、困难度算法分析，就是困难度的问题困难度只算“最要命的”，比如，执行门八的算法前来个快排根本不拖速度，八多的都豁出去了不在乎区区一个2n2书里对困难度进行了严格的定义，包括（）、（）、（）、（）nlogn0四种符号简洁地说，
（八）就是顶破天了搞个八次；
（八）O n2n2o n2就是天花板不到八比八矮一点（比如希尔排序就是
（八）因为n2,n2o n2,它再倒霉也达不到八）
（八）就是说某个算法随意怎么至少都要耗n2;Q n2费八比如全部基于比较的排序都是（）刨八僦是说它即是n2,Q nlogn;n2O
（八）又是（A）被天花板和水泥地夹在中间了，动不了了，就是它了n2Q n2,这里面有一个经典的例子，就是最大子序列（找数列中连续一段数之和最大）的四种算法，困难度分别为
（八）、
（八）、（）和（）O n3O n2O nlognO no附希腊字母读音“大欧”、“小欧”、“西塔”、“欧米咖”O oO Q
二、表、栈和队列表、栈和队列是三个基本的数据结构说穿了表就是把数据找起来排排坐吃果果，找什么东西都来把整个队伍找一遍栈就是一个桶，后放进去的先拿出来，它下面原来有的东西要等它出来之后才能出来，就好像你看到了一个丑人不行能今日的中饭还没吐出来就先把早饭吐出来了栈是拿来模拟多个过程的调用的（比如递归），实际点的用途就是表达式计算队列好比堵车，先进去的先出来先进队先买票，不能插队常拿来实现广搜（注:广搜就是一般说的广度优先搜寻，即）BaihowFF BPS二叉树
一、二叉树定义是另一种树形结构，他的特点是每个节点至多只有两棵子树，并且,二叉树的子树有左右之分，其次序不能随意颠倒
二、二叉树的性质性质在二叉树的第层上至多有一个结点1i2il性质深度为的二叉树上至多含匕个结点2:k21kl性质对任何一棵二叉树，若它含有个叶子结点、出个度为的结点，3:n02则必存在关系式通俗点说即叶子节点比二叉节点分支节点数多n=n+l02o一个满二叉树叶结点个数为则它的结点总数为N,2*N-lo完全二叉树在满二叉树的最底层自右向左依次去掉若干个节点得到的二叉树性质层完全二叉树，深度为节点数为八叶子节点为A4:n N,2N-l,2N-1,八表示的次方2N2N
三、二叉树的遍历三种遍历的依次分别是这样的
①前序遍历根-左-右
②中序遍历左-根-右
③后序遍历左-右-根
四、经典问题若某二叉树的前遍历访问依次是序中序遍历依次是则abdgcefh,dgbaechf,后序遍历的访问依次是什么解答此题的解答过程如下由前序遍历结果我们可知为根结点，再看中序遍历结果，因为中序遍1a历依次是左子树、根、右子树，因此由“中序遍历依次是可断定，dgbaechf”dgb为该二叉树的左子树中序遍历结果，为右子树中序遍历结果echf由前序遍历结果可知，左子树的前序遍历结果是右子树的前序遍2bdg,历结果是因此，和第一步分析类似，可知为左子树的根，再由为该cefh;b“dgb二叉树的左子树中序遍历结果”可知，为该左子树的左子树的中序遍历结果，dg再由在前序遍历结果中排列依次可知，为根，因此由为该左子树dg dg d“dg的左子树的中序遍历结果”可推出为的右孩子gd到此为止，可以完全推断出该二叉树的左子树的结构了依据同样方法，可以推断出该二叉树的右子树的结构，因此整个二叉树的结构图如下据此图，不难看出该二叉树的后序遍历结果是gdbehfca.
五、按层次遍历二叉树自然表达式转换为前/中/后缀表达式，其实是很简洁的首先将自然表达式依据优先级依次，构造出与表达式相对应的二叉树，然后对二叉树进行前/中/后缀遍历，即得到前/中/后缀表达式举例说明将自然表达式转换成二叉树axb+c-d
①依据表达式的优先级依次，首先计算形成二叉树b+c,A
②然后是在写时留意左右的位置关系axb+c,;
③最终在右边加上-d/As所以还是以刚才的这个例子，在最终二叉树的基础上可以得出:前缀表达式，a+bcd中缀表达式:a*b+c-d后缀表达式:abc+*d-排序与查找
一、各排序算法时间困难度比较算法名称时间困难度一句话描述冒泡排序八交换相邻位置的元素，每次把最大或最小元素换On2到最右边，每次范围减一选择排序A在未排序序列中找到最小元素，存放交换随意两On2个元素到排序序列的起始位置，再从剩余未排序元素中接着找寻最小元素，放到已排序序列末尾耍经过趟不稳定插入排序A把第个元素插入前有序的数组中，从后往前On2N N-1扫描，不符合条件的元素往后移，符合条件就将第个元素放入当前位置N快速排序最Onlog2n,找到一个参考元素，将比它小的元素放到其左边，坏八On2比它大的元素放到其右边，参考元素就在最终的位置，再对左右进行排序不稳定，优化方案略堆排序略Onlogn归并排序略Onlog2n
二、非比较排序算法计数排序，基数排序，桶排序等非比较排序算法，平均时间困难度都是On.这些排序因为其待排序元素本身就含有了定位特征，因而不须要比较就可以确定其前后位置，从而可以突破比较排序算法时间困难度的理论下限.Onlogn
三、查找二分查找算法1二分查找算法先比较位于集合中间位置的元素与键的大小，有三种状《机器会思索吗？》（）的论文，其中提出了一种用于判Can MachineThink定机器是否具有智能的试验方法，即图灵试验图灵奖是美国计算机协会于年设立的，又叫图灵奖”，特地1966“A.M.嘉奖那些对计算机事业作出重要贡献的个人其名称取自计算机科学的先驱、英国科学家艾伦・图灵，这个奖设立目的之一是纪念这位科学家、世界上第一位4软件工程师英国著名诗人拜伦的女儿（爱达）.由于她在程序设计上的Ada Lovelace开创性工作，被称为世界上”第一位程序员，“世界上第一位软Ada Lovelace件工程师，、微型计算机的问世5第四代至今超大规模集成电路的微星计算机个人应用到了各个领1972——PC域
二、硬件系统的组成、冯・诺伊曼体系1其思想是，在计算机中设置存储器，将符号化的计算步骤存放在存储器中，然后依次取出存储的内容，由一个被称之为限制器的部件进行译码,译码结果在一个被称为运算器的部件中进行计算，从而实现计算机工作的自动化（运算器和限制器统称为）CPU五个基本部分组成（）运算器，（）限制器，（）存储器，（）输1234人设备，（）输出设备5计算机的整个工作过程与基本硬件结构如图所示:2-8况（假设集合是从小到大排列的）键小于中间位置的元素，则匹配元素必在左边（假如有的话），于是对左边的区域应用二分搜寻键等于中间位置的元素，所以元素找到键大于中间位置的元素，则匹配元素必在右边（假如有的话），于是对右边的区域应用二分搜寻注比较次数次，可查找元素个数八・个n2n l信息技术的新发展虚拟化技术服务器虚拟化，存储与客户端虚拟化云计算“云计算”供应数据存储和平台测试等网络服务客户端变革虚拟化技术的流行，将为客户端计算机技术带来新的变革移动应用程序竞争目前，苹果应用程序，谷歌明年将iPhone Android推出大量新机型，移动应用程序市场的竞争将进一步加剧实时搜寻（）正在领导着一Real-Time SearchAmit SinghalGoogle个团队挖掘社会化网络的信息，供应与传统搜寻相同质量和价值的信息Web其他图论排列组合题目特难只能放弃，每次考试大约题1整理日期2023-07-26联系方式陆华EMAIL:陈中EMAIL:附录
一、初赛内容与要求计算机和信息社会（信息社会的主要特征、计算机的主要特征、
1.数字通信网络的主要特征、数字化）；.信息输入输出基本原理（信息交换环境、文字图形多媒体信息2的输入输出方式）；信息的表示与处理（信息编码、微处理部件、内存储结
3.MPU构、指令，程序，和存储程序原理、程序的三种基本限制结构）；计算机的.信息的存储、组织与管理（存储介质、存储器结构、文件4基本学问管理、数据库管理）；.信息系统组成与互连网的基本学问（计算机构成原理、槽和端5口的部件间可扩展互连方式、层次式的互连结构、互联网络、协议、协议、应用的主要方式和特点）；TCP/IP HTTPWEB人机交互界面的基本概念（窗口系统、人和计算机沟通信息的
6.途径（文本与交互操作））；信息技术的新发展、新特点、新应用等
7.和的基本操作学问；
1.Windows LINUX计算机的.互联网的基本运用常识（网上阅读、搜寻和查询等）；2基本操作.常用的工具软件运用（文字编辑、电子邮件收发等）3程序语言中基本数据类型（字符、整数、长整
1.数、浮点）；程序设计数据结构浮点运算中的精度和数值比较；
2.基本学问的类型一维数组（串）与线性表；
3.记录类型（）/结构类型（）
4.PASCAL Co结构化程序设计的基本概念；
1.阅读理解程序的基本实力；
2.具有将简洁问题抽象成适合计算机解决的模
3.型的基本实力；程序设计具有针对模型设计简洁算法的基本实力；
4.程序流程描述（自然语言/伪码图/其
5./NS他）；初等算法（计数、统计、数学运算等）；
1.排序算法（冒泡法、插入排序、合并排序、
2.基本算法处快速排序）;理查找（依次查找、二分法）；
3.回溯算法
4.运算器图计算机系统的基本硬件组成与工作原理2-8存储器简洁分类寄存器和高速缓存；和软盘和硬盘RAM ROM;内部、外部存储器、计算机的三总线结构2总线是一组导线、是公共通路，微型计算机中各个组成部件之间的信息传输都是通过它们来实现的地址总线是单向总线，用以传送向外设或存储器发出的地址信息AB CPU数据总线是双向总线，用以与内存或接口之间传输数据信息限制总DB CPU线是双向总线，有的作为输出，有的作为输入，用以与内存或接CB CPUI/O口之间传送限制信息分别传送地址信号、数据信号和限制信号软件系统、系统软件1操作系统软件1DOS,OS/2,Windows9x,Windows2000,Windows XP,WindowsVista,Win7Netware,Windows NT,Windows Server200x,Unix,Linux,iOS4,Android
3.0文件的后缀名
0.
1143.6,
8.9六法制189aBeDE1进位计数制的编码符合“逢进位”的规则，各位的权是以为底的常，R R一个数可按权绽开成为多项式例如，一个十进制数可按权绽开为
256.47】+十
256.47=2X+5X106X10°4X101+7x10%、进制转换为十进制1R基数为的数字，只要将各位数字与它的权相乘，其积相加，和数就是十进制数R例
3506.28」=6X8°+0X81+5X82+3X83+2X8=
1862.25例
0.2A
16、十进制转换为进制=2x16-1+10x16-2=
0.16406252R十进制整数转换成进制的整数除取余法R R例89=10110012102|892442|22……02I11——021~~5……12|2……1~6~……0……1十进制小数转换成进制时乘取整.RR例
0.625=
0.
1011020.625X2；
1.251X2;
0.50X2▼
1.
01、
二、
八、十六进制的相互转换3每位八进制数相当于三位二进制数，每位十六进制数相当于四位二进制数在转换时，位组划分是以小数点为中心向左右两边延长，中间的不能省略，两头不够时可以补尤其是小数后末尾的例如将转换成八进制和十六进制数
1011010.
12001011010.
1001011010.1=
132.
428132.
401011010.
10001011010.1=5A.82165A.8例如将十六进制数变为二进制数F
7.28F
7.28F
7.28=
11110111.00101162mi oiu.ooio woo
二、在计算机中带符号数的表示法、原码1在用二进制原码表示的数中，符号位为表示正数，符号位为表示负数，1其余各位表示数值部分如，、反码2反码的定义如下⑴对于正数，它的反码表示与原码相同即因反=因原⑵对于负数，则除符号位仍为夕卜，其余各位换成“换成“1”T0,”0”，即得到反码［］反例如［］反1X-1101001=10010110⑶对于，它的反码有两种表示:［］反［］反+0=00…0-0=11…
1、补码3正数的补码就是该正数本身［］01100100#=01000100对于负数:两头的不变，中间取反（负数取反加一）1
[10100100]#=11011100补=补[+0][-0]=00…
00、码（码）4BCD8421码就是用二进制代码表示的十进制数，也称数它是用BCD BCD4位二进制代码来表示十进制数如:的码为
三、0000—10010—939BCD整数和浮点数、整数1整型值可以用十进制，十六进制或八进制符号指定，前面可以加上可选的符号（-或者+）、浮点数2浮点数，在计算机中用以近似表示随意某个实数具体来说，这个实数由一个整数或定点数（即尾数）乘以某个基数（计算机中通常是）的整数次幕2得到,这种表示方法类似于基数为的科学记数法用（）来表示指数部10E e分如或
123.456123e-2
四、码ASCII）美国标准信息American StandardCode forInformation Interchange交换代码将每个字符用位的二进制数来表示，共有种状态7128大小字母、…、其它符号、限制符90——48A——65，a97
五、信息存储单位⑴位（缩写为）度量数据的最小单位，表示一位二进制信息、bit,b⑵字节（缩写为）一个字节由八位二进制数字组成（）byte,B1byte=8bit字节是信息存储中最常用的基本单位o计算机存储器（包括内存与外存）通常也是以多少字节来表示它的容量常用的单位有KB1K=1O24MB1M=1O24KGB1G=1O24M TB1T=1O24G、机器字（）字是位的组合，并作为一个独立的信息单位处理字又3word:称为计算机字，它取决于机器的类型、字长以与运用者的要求常用的固定字长有位、位、位等81632计算机网络的基本概念
一、计算机网络分类计算机网络的分类方式有很多种，可以按地理范围、拓扑结构、传输速率和传输介质等分类地理范围分类
①局域网
②城域网
③广域网广域网地理范围一般在几千LAN,MAN,WAN,公里左右，属于大范围连网如几个城市，一个或几个国家,是网络系统中的最大型的网络，能实现大范围的资源共享，如国际性的网络Internet按传输介质分类传输介质是指数据传输系统中发送装置和接受装置间的物理媒体，按其物理形态可以划分为有线和无线两大类
①有线网，光纤和双绞线，10M/100M/1000M
②无线网，协议8O
2.abcn。
个人认证
优秀文档
获得点赞 0
