计算机奥赛基础知识资料

《计算机奥赛基础知识资料》由会员分享，可在线阅读，更多相关《计算机奥赛基础知识资料（16页珍藏版）》请在金锄头文库上搜索。

1、兄弟培训内部教学资料 第 1 页 第一章第一章 计算机基础知识计算机基础知识 一、1946 年 2 月世界上第一台计算机 ENIAC 诞生在美国。 二、计算机的发展分为 4 个阶段：1、电子管时代 2、晶体管时代 3、中小规 模集成电路时代 4、大规模和超大规模集成电路时代 三、主存容量： 1024 个字节为 1K，1024K 为 1M，1024M 为 1G 四、数据在计算机内都是用二进制编码形式表示的。 五、四种常用数制 1、十进制：即逢十进位。含有十个数字符号：09。形式表示：D 2、二进制：即逢二进位。含有两个数字符号：0、1。形式表示：B 3、八进制：即逢八进位。含有八个数字符号：07

2、。形式表示：O 4、十六进制：即逢十六进位。含有十六个数字符号： 09、A、B、C、D、E、F。形式表示：H 六、进制转换： 1、R 进制数转换为十进制数 基数为 R 的数字，只要将各位数字与它的位权相乘的积相加，和数就是十 进制。 例 1：（1101101.0101）B =126+125+024+123+122+021+120+02-1+12-2+02- 3+12-4 =（109.3125）D 例 2：（12321.2）O =（5329.25）D 2、十进制数转换成 R 进制数 将整数与小数两部分分别转换。整数部分转换方法：除 R 倒取余。小数部 分转换方法：乘 R 正取整法。 例：（100

3、.345）D（1100100.01011）B 八进制与二进制、十六进制与二进制的关系 八进制对应二进制十六进制对应二进制十六进制对应二进制 00000000081000 10011000191001 201020010A1010 301130011B1011 410040100C1100 510150101D1101 611060110E1110 711170111F1111 七、原码、反码和补码 1、正数的反码、补码与其原码相同。 2、负数的反码：除符号位外，各位依次取反。 负数的补码：为其反码加 1。 八、计算机系统 一台完整的计算机系统是由硬件系统和软件系统两部分组成的。 1、计算机的硬

4、件系统：其基本结构属于冯诺依曼型计算机，它的主要特 点： 兄弟培训内部教学资料 第 2 页 1）计算机由五个基本部分组成：运算器、控制器、存储器、输入设备和输 出设备。 2）程序和数据以同等地位存放在存储器中，并要按地址寻访。 3）程序和数据以二进制表示。 2、CPU：称为中央处理单元，又称微处理器。 3、存储器 存储器的主要功能是存放程序和数据。 存储器通常分为内存储器和外存储器。 内存的存取速度直接影响计算机的运算速度。 内部存储器按其功能特征分为三类：1）随机存储器 RAM（一旦关机断电， RAM 中的信息将全部消失。 ） 2）只读存储器 ROM 3）高速缓冲存储器 Cache 4、计算

5、机软件系统 软件分为系统软件和应用软件两大类。 九、计算机病毒 计算机病毒是一组人为设计的程序。这种特殊的程序隐藏在计算机中，在系 统运行过程中能把自身准确复制或有修改地复制到其他程序体内，从而给计 算机系统造成一定的损害甚至严重破坏。 计算机病毒的特性： 1）传染性 2）潜伏性 3）隐蔽性 4）破坏性 5）寄生性 十、计算机网络 1、计算机网络的类型 1）广域网（WAN）和局域网（LAN） 2）专用网和公共网 2、计算机网络协议 1）TCP/IP 传输控制协议和网际协议 规范了网络上所有通信设备之间的数据传输格式及传送方法，以保证数 据安全可靠地到达指定的目的地。 2）FTP 文件传送协议

6、3）TELNET 远程登录协议 4）SMTP 简单邮件传送协议 5）PPP 点-点协议 6）HTTP 超文本传输协议 3、WWW ：全称是 World Wide Web，有时也简称 Web 或 3W。 4、URL 统一资源定位标识 任何一个信息文档、图形图像、视频或音频都被看作是资源。为了引用资源， 在 WWW 上，每一信息资源都有统一的且在网上唯一的地址，该地址就叫 URL。 第二章第二章 数据结构与算法数据结构与算法 1、算法：问题处理方案的正确而完整的描述。 2、算法的 4 个特性：确定性，可行性，有穷性，拥有足够的情报。 3、算法的复杂度包括：时间复杂度和空间复杂度。 4、算法的时间复

7、杂度是指：算法执行过程中所需要的基本运算次数。 CPU 兄弟培训内部教学资料 第 3 页 5、算法的空间复杂度是指：算法执行过程中所需要的存储空间。 6、一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二 是算法的控制结构。 7、算法的 3 种基本控制结构：顺序、选择、循环。 8、算法设计的基本方法：列举法、归纳法、递推、递归和减半递推技术。 9、数据的存储结构：是指数据的逻辑结构在计算机存储空间中的存放形式。 10、数据处理：是指对数据集合中的各元素以各种方式进行运算。 11、数据结构：是指相互有关联的数据元素的集合。 12、数据元素之间的任何关系都可以用前驱和后继关系来描述。

8、13、常用的存储结构有顺序、链接、索引等存储结构。 14、采用不同的存储结构，数据处理的效率不同。 15、数据结构分为逻辑结构和存储结构，循环队列属于存储结构。 16、在数据结构中，没有前驱的结点称为根结点；没有后继的结点称为叶子 结点。 17、数据结构按逻辑关系的不同，通常可分为线性结构和非线性结构两类。 18、在稍微复杂的线性表中，一个数据元素可以由若干个数据项组成，在这 种情况下，常把数据元素称为记录，含有大量记录的线性表就称作文件。 19、在计算机中存放线性表，一种最简单的方法是顺序存储。 20、在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空 间。 21、栈：栈是一种只

9、允许在一端进行插入与删除的线性表。 22、栈的特点：1）先进后出（或后进先出） 2）栈具有记忆作用 3）对 栈的操作中，不需要改变栈底指针 23、栈的基本运算有三种：入栈、退栈与读栈顶元素。 24、队列：队列是一种允许在一端进行插入、而在另一端进行删除的线性表。 允许插入的一端称为队尾，允许删除的一端称为队头。 25、队列的特点：先进先出（或后进后出） 26、循环队列主要有两种基本运算：入队运算与退队运算。每进行一次入队 运算，队尾指针就进一。 27、递归算法一般需要利用栈实现。 28、对长度为 n 的线性表进行插入一个新元素或删除一个元素时，在最坏情 况下所需要的比较次数为 n 。在平均情况

10、下，需要比较次数为 n/2 。 29、线性链表属于链式存储结构，在链式存储结构中，存储空间可以不连续， 各元素的存储顺序是任意的。 30、在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据 元素值，称为数据域；另一部分用于存放指针，称为指针域。 31、在线性单链表中，每一个结点只有一个指针域，由这个指针只能找到后 继结点，但不能找到前驱结点。 兄弟培训内部教学资料 第 4 页 32、与单向链表相比，双向链表更容易访问相邻结点。 33、在实际应用中，带链的栈可以用来收集计算机存储空间中所有空闲的存 储结点，这种带链的栈称为可利用栈。 34、在线性链表中删除一个元素，只需要改变被删除元

11、素所在结点的前一个 结点的指针域即可。 35、在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访 问到表中其他所有的结点。在对循环链表进行插入和删除的过程中，实现了 空表与非空表的运算统一。 36、二叉树的遍历：是指不重复地访问二叉树中的所有结点。 37、二叉树的遍历有三种：前序遍历、中序遍历、后序遍历。 1）前序遍历：访问根结点； 前序遍历左子树； 前序遍历右子树。 2）中序遍历：中序遍历左子树； 访问根结点； 中序遍历右子树。 3）后序遍历：后序遍历左子树； 后序遍历右子树； 访问根结点。 38、满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。 39、二叉树的性质：

12、1）在二叉树的第 k 层上，最多有 2k-1个结点。 2）深度为 m 的二叉树，最多有 2m-1 个结点。 3）在任意一棵二叉树中，度为 0 的结点（即叶子结点）总是比度为 2 的结 点多一个。 40、完全二叉树：除最后一层外，每一层上的所有结点都有两个子结点，在 最后一层上缺少右边的若干结点。 41、对于长度为 n 的有序线性表，在最坏情况下，二分法查找需要比较 log2n 次，而顺序查找需要比较 n 次。 42、二分法查找只适用于顺序存储的有序线性表。 43、顺序查找一般是指在线性表中查找指定的元素。 44、交换类排序：快速排序法和冒泡排序法。 插入类排序：简单插入排序法和希尔排序法。 选

13、择类排序：简单选择排序法和堆排序法。 45、对于长度为 n 的线性表，在最坏情况下，各种排序法的比较次数： 冒泡排序：n(n-1)/2 快速排序：n(n-1)/2 简单插入排序：n(n-1)/2 简单选择排序：n(n-1)/2 希尔排序：n1.5 堆排序：nlog2n 46、在最坏情况下，堆排序的时间复杂度最小。 47、快速排序法可以实现通过一次交换而消除多个逆序。 48、快速排序法的关键是对线性表进行分割。 第三章第三章 程序设计基础程序设计基础 1、程序设计风格：清晰第一，效率第二。 兄弟培训内部教学资料 第 5 页 2、源程序文档化时程序应加注释。注释一般分为序言性注释和功能性注释。 3

14、、在编写程序时，需要注意数据说明的风格，以便使程序中的数据说明更 易于理解和维护。 4、程序应该简单易懂，语句构造应该简单直接，不应该为提高效率而把语 句复杂化。 5、当程序设计语言对输入格式有严格要求时，应保持输入格式与输入语句 的一致性。 6、结构化程序设计的主要特点是： 1）程序易于理解、使用和维护。 2）提高了编程工作的效率，降低了软件开发成本。 3）每个控制结构只允许有一个入口和一个出口。 7、结构化程序设计的三种基本逻辑结构为顺序、选择和循环。 8、结构化程序设计的主要原则：自顶向下、逐步求精、模块化、限制使用 GOTO 语句。 9、结构化程序设计的一种基本方法是逐步求精法。 10

15、、在模块化程序设计中，按功能划分模块的原则是：各模块的功能尽量单 一，且各模块之间的联系尽量少。 11、在面向对象方法中，信息隐蔽是通过对象的封装性来实现的。封装是一 种信息隐蔽技术。 12、在面向对象方法中，类的实例称为对象。 13、在面向对象方法中，类之间共享属性和操作的机制称为继承。 不是所有的对象都有继承性。 14、在面向对象方法中，一个对象请求另一对象为其服务的方式是通过发送 消息。 15、信息隐蔽的概念与模块独立性直接有关。耦合是指模块之间联系的紧密 程度。耦合度越高则模块的独立性越差。 16、在面向对象方法学中，直接反映了用户对目标系统的要求的模型是功能 模型。 17、面向对象技

16、术中，对象是类的实例。对象有三种成分：标识、属性和方 法。 18、多态性：是指同一个操作作用于不同的对象可以有不同的解释，产生不 同的执行结果。 第四章第四章 软件工程基础软件工程基础 1、软件工程研究的内容主要包括：软件开发技术和软件工程管理。 2、软件是程序、数据与相关文档的集合。 3、软件工程的主要思想是强调在软件开发过程中需要应用工程化原则。 4、软件的生命周期：是从软件产品提出、实现、使用维护到停止使用退役 的过程。 软件交付后还要进行维护。 兄弟培训内部教学资料 第 6 页 5、在软件生命周期中，能准确地确定软件系统必须做什么和必须具备哪些 功能的阶段是：需求分析。 6、软件工程的三要素是方法、工具和过程。 7、软件开发环境是全面支持软件开发全过程的软件工具集合。 8、软件工程过程是把输入转化为输出的一组彼此相关的资源和活动。 9、软件生命周期一般包括可行性研究与需求分析、设计、实现、测试、交 付使用以及维护等活动。 10、软件工程的原则包括抽象、信息隐蔽、模块化、局部化、确定性、一致 性、完备性和可验证性。 11、结构化方法的核心和基