信息学奥赛-计算机基础知识

.

第一章 计算机基础知识 ........................................................... 2

第一节 数制及其转换 ......................................................... 2 第二节 算术运算和逻辑运算 ................................................... 4 第三节 原码、反码和补码 ..................................................... 7 第四节 浮点数的表示方法 ..................................................... 9 第五节 奇偶校验 ............................................................ 10 第六节 ASCII码表 ........................................................... 12 第二章 计算机硬件基础 .......................................................... 13

第一节 中央处理器 .......................................................... 13 第二节 存储器系统 .......................................................... 15 第三节 输入输出系统 ........................................................ 17 第三章 网络基础知识 ............................................................ 19

第一节 网络的组成与结构 .................................................... 19 第二节 网络协议 ............................................................ 20 第三节 Internet相关知识 .................................................... 20 第三节 Internet相关知识 .................................................... 21 第四章 其他相关基础知识 ........................................................ 23

第一节 计算机病毒 .......................................................... 23 第二节 数据库系统 .......................................................... 23 第五章 数据结构之线性结构 ...................................................... 25

第一节 线性表 .............................................................. 25 第二节 栈 .................................................................. 27 第三节 队列 ................................................................ 29 第六章 数据结构之非线性结构 .................................................... 31

第一节 树的概念 ............................................................ 31 第二节 树的表示方法和存储结构 .............................................. 33 第三节 二叉树的概念 ........................................................ 36 第四节 二叉树的遍历 ........................................................ 40 第五节 普通树的遍历 ........................................................ 44 第六节 根据两种遍历顺序确定树结构 .......................................... 46 第七节 二叉排序树 .......................................................... 47 第八节 最优二叉树(哈夫曼树) ................................................ 48 AOE网 ...................................................................... 50

.

.

第一章 计算机基础知识

第一节 数制及其转换

一、二、八、十六进制转十进制的方法：乘权相加法。 例如：

（11010110）2 = 1×27 + 1×26 + 0×25 + 1×24 + 0×23 + 1×22 + 1×21 + 0×20

= （214）10

（2365）8 = 2×83 + 3×82 + 6×81 + 5×80 = （1269）10 （4BF）16 = 4×162 + 11×161 + 15×160 = (1215)10 带小数的情况：

（110.011）2 = 1×22 + 1×21 + 1×20 + 0×2-1 + 1×2-2 + 1×2-3 = （6.375）10 （5.76）8 = 5×80 + 7×8-1 + 6×8-2 = （5.96875）10

（D.1C）16 = 13×16 + 1×16+ 12*16 = （13.109375）10

二、十进制化二进制的方法：整数部分除二取余法，小数部分乘二取整法。 例一：（43）10 = （101011）2

例二：（0.375）10 = （0.011）2

0

-1

-2

.

.

三、二进制转八进制的方法 一位数八进制与二进制对应表

八进制 二进制 转换方法:对二进制以小数点为分隔，往前往后每三位划为一组， 0 1 2 3 4 5 6 7 000 不足三位补0，按上表用对应的八进制数字代入即可。 001 例如：(10111011.01100111) 010 011 100 101 110 111 = 010,111,011.011,001,110 = （273.36）8 三、二进制转十六进制的方法 一位数十六进制与二进制对应表 十六进制 0 1 2 3 4 5 6 二进制 转换方法:对二进制以小数点为分隔，往前往后每四位划 0000 0001 0010 0011 0100 0101 0110 为一组，不足四位补0，按上表用对应的十六进 制数字代入即可。 例如：(10111011.01100111) = 1011,1011.0110,0111 = （BB.67）16 .