《信息学奥赛-计算机基础知识》由会员分享，可在线阅读，更多相关《信息学奥赛-计算机基础知识（33页珍藏版）》请在金锄头文库上搜索。
1、第 1 页 共 33 页第一章第一章 计算机基础知识计算机基础知识2 第一节 数制及其转换2 第二节 算术运算和逻辑运算3 第三节 原码、反码和补码5 第四节 浮点数的表示方法6 第五节 奇偶校验7 第六节 ASCII 码表.8 第二章第二章 计算机硬件基础计算机硬件基础9 第一节 中央处理器9 第二节 存储器系统10 第三节 输入输出系统11 第三章第三章 网络基础知识网络基础知识12 第一节 网络的组成与结构12 第二节 网络协议13 第三节 Internet 相关知识.13 第三节 Internet 相关知识.14 第四章第四章 其他相关基础知识其他相关基础知识15 第一节 计算机病毒1
2、5 第二节 数据库系统15 第五章第五章 数据结构之线性结构数据结构之线性结构16 第一节 线性表16 第二节 栈17 第三节 队列18 第六章第六章 数据结构之非线性结构数据结构之非线性结构19 第一节 树的概念19 第二节 树的表示方法和存储结构20 第三节 二叉树的概念22 第四节 二叉树的遍历24 第五节 普通树的遍历27 第六节 根据两种遍历顺序确定树结构28 第七节 二叉排序树29 第八节 最优二叉树(哈夫曼树) .30 AOE 网.32第 2 页 共 33 页第一章第一章 计算机基础知识计算机基础知识第一节 数制及其转换一、二、八、十六进制转十进制的方法：乘权相加法。一、二、八、
3、十六进制转十进制的方法：乘权相加法。 例如： （11010110）2 = 127 + 126 + 025 + 124 + 023 + 122 + 121 + 020 = （214）10 （2365）8 = 283 + 382 + 681 + 580 = （1269）10 （4BF）16 = 4162 + 11161 + 15160 = (1215)10 带小数的情况： （110.011）2 = 122 + 121 + 120 + 02-1 + 12-2 + 12-3 = （6.375）10 （5.76）8 = 580 + 78-1 + 68-2 = （5.96875）10 （D.1C）16 =
4、 13160 + 116-1 + 12*16-2 = （13.109375）10 二、十进制化二进制的方法：整数部分除二取余法，小数部分乘二取整法。二、十进制化二进制的方法：整数部分除二取余法，小数部分乘二取整法。 例一：（例一：（4343）1010 = = （101011101011）2 2例二：（例二：（0.3750.375）1010 = = （0.0110.011）2 2三、二进制转八进制的方法三、二进制转八进制的方法 一位数八进制与二进制对应表一位数八进制与二进制对应表八进制 二进制0000 1001 2010 3011 4100 5101 6110 7111转换方法:对二进制以小数点
5、为分隔，往前往后每三位划为一组， 不足三位补 0，按上表用对应的八进制数字代入即可。例如：(10111011.01100111)= 010,111,011.011,001,110= （273.36）8第 3 页 共 33 页三、二进制转十六进制的方法三、二进制转十六进制的方法 一位数十六进制与二进制对应表一位数十六进制与二进制对应表十六进制二进制00000 10001 20010 30011 40100 50101 60110 70111 81000 91001 A1010 B1011 C1100 D1101 E1110 F1111转换方法:对二进制以小数点为分隔，往前往后每四位划 为一组，不
6、足四位补 0，按上表用对应的十六进 制数字代入即可。例如：(10111011.01100111)= 1011,1011.0110,0111 = （BB.67）16四、进制的英文表示法：四、进制的英文表示法：以上都是用括号加数字的表示方法，另外还有英文表示法，就是以 BIN、OCT、HEX、DEC 分别代表二、八、十六、十进制。或者只写第一个字母。例如 1101B 表示是二进制。有些地方为了避免“O”跟“0”混淆，把 O 写成 Q。第二节第二节 算术运算和逻辑运算算术运算和逻辑运算一、二进制的算术运算一、二进制的算术运算 1、加法运算规则：0+0=0 0+1=1 1+0=1 1+1=10 2、减
7、法运算规则：0-0=0 0-1=1（向高位借 1） 1-0=1 1-1=0 3、乘法运算规则：00=0 01=0 10=0 11=1 二、逻辑运算二、逻辑运算 1、基本运算 逻辑乘，也称“与”运算，运算符为“”或“”00=0 01=0 10=0 11=1使用逻辑变量时，AB 可以写成 AB 逻辑加，也乘“或”运算，运算符为“+”或“”0+0=0 0+1=1 1+0=1 1+1=1第 4 页 共 33 页 逻辑非，也称“反”运算，运算符是在逻辑值或变量符号上加“”= 1 = 0012、常用运算异或运算：AB =AB BA2 2、基本公式、基本公式 0，1 律A0=0A1=AA0=AA1=1 交换
8、律AB=BAAB=BA 结合律ABC =（AB）C = A（BC）ABC =（AB）C = A（BC） 分配律A（BC）= AB AC 重叠律AA.A = AAA.A = A 互补律A + = 1 A = 0 AA 吸收律AAB = A A（AB） = AAB = AB A（B） = AB AA 对合律对一个逻辑变量两次取反仍是它本身 德摩根定理= BA AB= +BAAB三、逻辑代数的应用三、逻辑代数的应用 1、逻辑表达式化简例如： F = AAB ABB=A（B） （利用分配律）ABB=A （利用互补律以及 0，1 律）AB第 5 页 共 33 页= A （利用吸收律） B2、对指定位进行
9、运算，假设变量 A 有八位，内容是 d7d6d5d4d3d2d1d0 将变量 A 的 d5位清零A（11011111）A 将变量 A 的各位置 1A（11111111）A第三节第三节 原码、反码和补码原码、反码和补码计算机中参与运算的数有正负之分，计算机中的数的正负号也是用二进制表示的。 用二进制数表示符号的数称为机器码。常用的机器码有原码、反码和补码。 一、原码一、原码 求原码的方法：设 X；若 X0，则符号位（原码最高位）为 0，X 其余各位取值照抄； 若 X0，则符号位为 1，其余各位照抄。【例 1】X=+1001001 X原原 = 01001001【例 2】X=-1001001 X原原
10、 = 11001001 二、反码二、反码 求反码的方法：设 X；若 X0，则符号位（原码最高位）为 0，X 其余各位取值照抄； 若 X0，则符号位为 1，其余各位按位取反。【例 3】X=+1001001 X反反 = 01001001【例 4】X=-1001001 X反反 = 10110110 三、补码三、补码 求补码的方法：设 X；若 X0，则符号位（原码最高位）为 0，X 其余各位取值照抄； 若 X0，则符号位为 1，其余各位按位取反后，最低位加 1。【例 5】X=+1001001 X补补 = 01001001【例 6】X=-1001001 X补补 = 10110111 四、补码加减法四、补
11、码加减法计算机中实际上只有加法，减法运算转换成加法运算进行，乘法运算转换成加法运 算进行，除法运算转换成减法运算进行。用补码可以很方便的进行这种运算。 1、补码加法X+Y补补 = X补补 + Y补补【例 7】X=+0110011,Y=-0101001，求X+Y补补X补补=00110011 Y补补=11010111第 6 页 共 33 页X+Y补补 = X补补 + Y补补 = 00110011+11010111=00001010注：因为计算机中运算器的位长是固定的，上述运算中产生的最高位进位将丢掉， 所以结果不是100001010，而是 00001010。 2、补码减法X-Y补补 = X补补 -
12、 Y补补 = X补补 + -Y补补其中-Y补补称为负补，求负补的方法是：对补码的每一位（包括符号位）求反，最后末位加“1”。【例 8】X=+0111001,Y=+1001101，求X-Y补补X补补=00111001 Y补补=01001101 -Y补补 = 10110011X-Y补补 = X补补 + -Y补补 = 00111001+10110011=11101100 五、数的表示范围五、数的表示范围通过上面的学习，我们就可以知道计算机如果用一个字节表示一个整数的时候，如果是无符号数，可以表示 0255 共 256 个数（0000000011111111），如果是有符号数则能表示-128127 共
13、 256 个数（1000000001111111）。如果两个字节表示一个整数，则共有 65536 个数可以表示，大部分程序设计语言中整数的范围都是-3276832767 的原因，可以看出这种整数类型是 16 位的有符号数，而且是补码表示的。第四节第四节 浮点数的表示方法浮点数的表示方法一、浮点数表示一、浮点数表示 一个数的浮点形式（设基数是 2）可写成：N = M 2E其中:M 代表尾数,E 代表阶码。 计算机中浮点数只用尾数和阶码表示，其形式如下：阶码尾数符号尾数浮点数的精度由尾数决定，数的表示范围由阶码的位数决定。为了最大限度提高精度，尾数采用规格化形式，既 1/2M 82R102f122
14、z43+63?83S103g12344,6484T104h124|45-65A85U105i12546.66B86V106j12647/67C87W107k 48068D88X108l 49169E89Y109m 50270F90Z110n 51371G91111o 目前使用最广泛的西文字符集及其编码是 ASCII 字符集和 ASCII 码（ ASCII 是 American Standard Code for Information Interchange 的缩写），它同时也被国际标准化组织（ International Organization for Standardization, I
15、SO ）批准为国际标准。 基本的 ASCII 字符集共有 128 个字符，其中有 96 个可打印字符，包括常用的字母、数字、标点符号等，另外还有 32 个控制字符。标准 ASCII 码使用 7 个二进位对字符进行编码，对应的 ISO 标准为 ISO646 标准。下表展示了基本 ASCII 字符集及其编码： 字母和数字的 ASCII 码的记忆是非常简单的。我们只要记住了一个字母或数字的 ASCII 码（例如记住 A 为 65 ， 0 的 ASCII 码为 48 ），知道相应的大小写字母之间差 32 ，就可以推算出其余字母、数字的 ASCII 码。 虽然标准 ASCII 码是 7 位编码，但由于计算机基本处理单位为字节（ 1byte = 8bit ），所以一般仍以一个字节来存放一个 ASCII 字符。每一个字节中多余出来的一位（最高位）在计算机内部通常保持为 0 （在数据传输时可用作奇偶校验位）。 由于标准 ASCII 字符集字符数目有限，在实际应用中往往无法满足要求。为此，国际标准化组织又制定了 ISO202
