计算机：硬件和软件 各种存储设备的速度 寄存器>高速缓冲存储器>内存>硬盘>光盘U盘>软盘、磁带

触摸屏既是输入设备又是输出设备

冯．诺依曼机思想的核心内容——“存储程序”。

（1） 主存容量：主存容量是指一个主存储器所能存储的全部信息量。主存容量的基本单位是字节，还可用KB、MB（兆字节）、GB（吉字节）、TB（太字节）和PB（皮字节）来衡量。它们之间的关系如表1-3所示。 表1-3 K、M、G、T、P的定义 单位 通常意义 实际意义 K（Kilo） 103 210=1024 M（Mega兆） 106 220=1024KB=1,048,576 G（Giga吉） 109 230=1024MB=1,073,741,824 T（Tera太） 1012 240=1024GB =1,099,511,627,776 P（Peta皮） 1015 250=1024TB =1,125,899,906,842,624 通常，计算机的主存容量越大，存放的信息就越多，处理问题的能力就越强。

1. (ASCII) 美国标准信息交换代码( American Standard Code for Information Interchange, ASCII )是由美国国家标准学会(American National Standard Institute , ANSI ) 二、网络部分 、网络的分类： （1）按照地理范围分类：局域网 (Local Area Network, LAN) 城域网 (Metropolitan Area Network, MAN) 广域网 (Wide Area Network, WAN)
   1、什么是IP地址：IP地址是TCP/IP网络中的主机(或称为节 点)的惟一地址。IP地址是网络层的逻辑地址。 2、为什么要使用IP地址：方便管理和使用，弥补了MAC（48位，用十六进制表示）地址的离散。 3、IP地址的格式： IP地址是一组32位长的二进制数字，用点分十进制表示。分IPV4（32位）和IPV6（128位）；例如172.168.1.1.（每个数字不超过255） A类地址：10.0.0.0/8（10.0.0.0~10.255.255.255） B类地址：172.16.0.0/12（172.16.0.0~172.31.255.255） C类地址：192.168.0.0/16 （192.168.0.0~192.168.255.255） 公网IP(供Internet使用)：要申请并付一定的费用才能使用或动态分配

三．软件部分（软件主要分为应用软件和系统软件，这里主要讲应用软件） 1.系统软件 常见的系统软件分为：各种驱动软件、操作系统、编程语言、各种数据库； 操作系统（非网络操作系统）：windows2000、windows2000 prefassional winxp windows vista Mac OS。 Linux、Unix、Netware、OS2、Xnix
2.应用软件 （一）图像、视频、适量图 1．图像文件 图像文件扩展名为bmp、jpg、gif等。其中bmp图像为windows自带的“画图”软件默认格式。它把一幅图像分为一个个很小很小的矩形，逐个描述每个小矩形的颜色。如果有x点，每点颜色会有y种可能性，这y种可能性需要z 位二进制表示，则该幅图像需要xz位(bit)，即xz/8字节(B)。 可以将bmp图像文件压缩为扩展名为jpg或gif的图像文件。其中jpg为有损压缩。它使用JPEG标准来压缩图像。JPEG是Joint Photographic Experts Group(联合图像专家组)的缩写。 例1：一幅分辨率为800600的24位图像，需要多少存储空间？ 解：该图像有800600格，每个小格图像颜色以24位二进制描述， 共需存储空间80060024位=8006003B=1406.25KB≈1.37MB （注：该图像每格颜色有224=16777216种色彩，非常接近真实的大自然了。） 例2：一幅分辨率为1024768的16色图像，需要多少存储空间？ 解：该图像有1024768格，每个小格图像颜色有16种，以4位二进制描述， 共需存储空间10247684位=1024768/2B=384KB=0.375MB 例3：一幅分辨率为1024768的黑白单色图像，需要多少存储空间？ 解：该图像有1024768格，每个小格图像颜色有2种，以1位二进制描述， 共需存储空间10247681位=1024768/8B=96KB 2．视频文件 视频文件的扩展名有avi,rmvb,mpg,dat,wmv,asf,rm等，其中mpg,dat,wmv,asf,rm为压缩过的视频文件。dat为VCD格式，wmv,asf,rm三者为流媒体文件，支持在网上边下载边播放。Wmf和asf为微软的windows media player能播放，rm需要使用real player或real one软件播放。 未压缩过的视频文件大小的计算： 例：一段1小时的视频，每秒播放25帧，画面为640480的24位真彩色，问需要多少存储空间？ 解：该视频相当于每秒放25幅图片，每幅图片停留0.04秒，利用人的视觉残留，给人以连续的图像感觉。 （1）1幅图片存储空间为：64048024/8B=900kB （2）1秒存储空间为900KB25=22500KB （3）1小时存储空间为：22500kB*3600≈79101MB≈77.2GB 由此可见，未经压缩的avi视频文件实在是太大了，不仅需要很大的存储空间，且网上下载也太慢。在的mpeg标准下，压缩比可以达到200:1。MPEG的全名为Moving Pictures Experts Group，中文译名是动态图像专家组。 （三）十进制、二进制、十六进制、八进制 十进制以D表示(Decimal)，二进制以B表示(Binary)，十六进制以H表示(Hex)，八进制以O表示(Octal)。

1. 十进制整数转二进制整数：方法：按幂展开，如35=25+21+20，(35)10=(100011)2

2. 二进制整数转十进制整数：乘权相加。 如(110010)2=125+124+023+022+121+020=50

3. 如(10011)2=(010 011)2=(23)8， (236)8=(010 011 110)2=(10011110)2

4. 二进制小数转十进制小数：乘权相加。 如：(0.1101)2=12-1+12-2+02-3+12-4=0.8125 (四)原码、反码和补码

5. 最高位表示符号，0代表正数，1代表负数。其它位表示数的绝对值。

6. 正数的原码=反码=补码。如一个字节8位表示时，9的原、反、补码均为00001001

7. 负数的原码：最高位（符号位）为1，其它位值=该数的绝对值的二进制表示。

8. 负数的反码：最高位为1，其它位为原码取反。

9. 负数的补码：反码加1（即最低位加1）。 例：以8位二进制表示，则-3的原码10000011，反码11111100，补码11111101。 例如： 3位二进制，原码、反码只能表示7个数，它们为-3~3。补码能表示8个数，它们是-4~3。 其中原码和反码0的表示有两种，如下表所示。 数值 -4 -3 -2 -1 -0 0 1 2 3 原码 无 111 110 101 100 000 001 010 011 反码 无 100 101 110 111 000 001 010 011 补码 100 101 110 111 无 000 001 010 011 （五）定点数表示法

10. 定点数表示法通常把小数点固定在数值部分的最高位之前，或把小数点固定在数值部分的最后面。前者用来表示纯小数，而后者则用于表示整数。如图1所示。

11. 在计算机中，图1所示的小数点“．”实际上是不表示出来的，是事先约定好固定在那里的。对于一台计算机来说，一旦确定了一种小数点的位置，整个系统就不再改变。

12. 只能处理定点数的计算机称为定点计算机。在这种计算机中机器指令访问的所有操作数都是定点数。因此，在定点计算机中，必须把参加运算的操作数变成约定的定点数形式方能处理，故在编程时需要设定一个比例因子，把原始的数缩小成定点小数或扩大成定点整数后进行处理，得到的运算结果还需要根据比例因子还原成实际的数值。选择合适的比例因子是很重要的，其值必须保证参加运算的初始数据、中间结果和最后结果都在定点数的表示范围之内，否则就会产生“溢出”。 （六）浮点数表示法

13. 在科学计算中，人们常常会遇到非常大和非常小的数值，若用相同的比例因子来处理的话，很难兼顾数值范围和运算精度的要求。为了协调这两方面的关系，让小数点的位置视需要而浮动，这就是浮点数。例如： N＝rE•M 式中，r为浮点数阶码的底，与尾数的基数相同，通常r＝2。E和M都是带符号的定点数，其中E叫数N的阶码（Exponent），M为数N的有效数字，称为尾数（Mantissa）。在大多数计算机中，尾数为纯小数，常用原码或补码表示；阶码为纯整数，常用移码或补码表示。即浮点数是用尾数和阶码来表示的。 实数以科学计数法表示。尾数：二进制纯小数；阶码：二进制整数，表示2的次方。 例如： 一个实数，尾数为以原码表示的011，阶码为以补码表示的1111，求该数以十进制表示的值 尾数值(0.11)2=0.75，阶码值-1（补码取反，再加1得真值）。于是值为0.75*2-1=0.375

14. 在计算机中，通常用约定的4部分来表示一个浮点数：

阶符± 阶码e 数符± 尾数m

(七)常见运算符及运算次序

1. 逻辑运算符及常见的表示符号 运算符 非 与 或 异或 常见符号 NOT ~ ┍ ∧ AND ∧ • * OR ∨ + XOR +

含义 NOT true得false NOT false得true True and true得true 其余情况得false False or false得false 其余情况得true 相同时得false 不同时得true 逻辑运算符有4个，它们分别是： ！（逻辑非）、 ｜｜（逻辑或）、＆＆（逻辑与） ＾（异或） 注意，我们有时以1表示True，以0表示False。 2. 整数的逻辑运算（实数不能作逻辑运算） 将数字转换为二进制补码表示（计算机中，整数是以补码存储的），然后按位作逻辑运算，1作True,0作False，结果为二进制补码。 例如： 57 and (-35)=00000000 00111001 and 11111111 11011101=(00000000 00011001) 57 or (-35)=00000000 00111001 or 11111111 11011101=(11111111 11111101) 57 xor (-35)=00000000 00111001 xor 11111111 11011101=(11111111 11100100) 3. 运算符的级别： （1）括号内运算先运算； （2）级别较高的优先于级别较低的先运算； （3）同级运算从左至右运算； 如下表所示，1级为最高，2级次之，3级再次之，5级为最低级。 级别 1 2 3 4 5 运算符 NOT（非） （乘方） * / div mod and Xor + - or in = < > >= <= <> 例：15 xor 3 or 10得14; 10 or 3 xor 15得4; not 12得4; 1 xor 2+1得4; 1+2 xor 1得2。 （八）各种排序方法
基于元素之间比较的排序方法，时间复杂度不会快于O(nlogn)。 选择排序 插入排序 冒泡排序 快速排序 归并排序 堆排序 希尔排序 时间复杂度 O(n2) O(n2) O(n2) O(nlogn) O(nlogn) O(nlogn) 约O(n1.5) 稳定性 不稳定 稳定 稳定 不稳定 稳定 不稳定 不稳定 数据有序时 不变 变快 变快 变慢 不变 不变 不变 特殊应用 求第k大数 求逆序对数 优先队列 1. （九）线性表

1. 数组和链表 （1）已知二维数组的首元素地址，每个元素所占存储空间，求其它元素存储地址 （2）下三角矩阵：n行n列的数组，沿主对角线对称时，只要存储下三角即可。 n行n列的数组，将下三角按行存储至一维数组中，a[j,k]（j>=k）对应一维数据中第(j-1)j/2+k n行n列的数组，将下三角按列存储至一维数组中，a[j,k]（j>=k）对应第(2n-k+2)(k-1)/2+j-k+1 （3）数组的优缺点:每次查询较快,只要O(1)时间;每次插入和删除较慢,会造成大量元素的移动, 需要O(n)时间。 (4) 链表的优缺点: 每次查询元素较慢,需要O(n)时间遍历链表; 每次插入和删除时间较快只要O(1)时间。

2. 队列和循环队列 (1) 先进先出（FIFO），一端（队尾）插入，另一端（队首）删除，可以以数组或链表来模拟。 (2) 用于宽度优先遍历 (3) 以n个位置的数组来存储队列时，线性队列中最多可以存储n个元素，循环队列可以存储n-1个元素。 (4) 循环队列中，如果以head表示队首，tail表示下一个插入位置，则当前已有元素个数为(tail-head+n) mod n (5) 队空:tail=head或(tail-head) mod n=0；队满: (tail-head+n) mod n=n-1或(tail+1)mod n=head

3. 栈 (1) 后进先出（LIFO），插入和删除都在同一端（栈顶）进行 (2) 用于:语法检查、计算表达式的值、实现递归过程、函数调用、深度优先遍历(如二叉树中序、前序、后序遍历) (十) 树

4. 树 （1） 结点的度:结点拥有的子树数; （2） 树的度(Degree):树内各结点的度的最大值; （3） 叶子(Leaf)结点/终端结点:度为0的结点; （4） 内部结点/非终端结点/分支结点:度不为0的非根结点; （5） 结点的层次:一般根为第1层;孩子结点的层次为双亲结点的层次+1; （6） 也有把根定为第0层的,请看题意。 （7） 树的深度/高度(Depth):树中结点的最大层次; （8） 树有结点数为n，则边数B=n-1 （9） 一棵m度的树，度为k的结点有nk个，则叶子结点数n0=1+n2+2n3+…+(m-1)nm （10） 树的深度优先遍历:遍历根A,深度优先遍历A的第1棵子树, 深度优先遍历A的第2棵子树,…, 深度优先遍历A的最后1棵子树。上图深度优先遍历得ABEKLFCGDHMIJ （11） 树的宽度优先遍历:相当于层次遍历,可以借助队列实现。上图宽度优先遍历得ABCDEFGHIJKLM

5. 二叉树 （1） 二叉树严格区分左子树和右子树 （2） 满二叉树:每层都充满的二叉树,h层满二叉树有2h-1个结点 （3） 完全二叉树:最后一层所有结点均尽量向左靠,其它层全部充满。  h层的完全二叉树，结点数在（2h-1和2h-1]。  通过层次遍历顺序（或叫宽度优先遍历），使用数组a存储完全二叉树，则a[k]的左子女为a[2k],右子女为a[2k+1],a[k]的双亲为a[k div 2]。 （4） 平衡二叉树:任意点的左子树和右子树的高度差不超过1（小于等于1）。 （5） 二叉树的遍历:除了深度优先和宽度优先遍历外，还有前序、后序和中序。  前序:遍历根,前序遍历左子树,前序遍历右子树;  后序:后序遍历左子树,后序遍历右子树,遍历根;  中序:中序遍历左子树,遍历根,中序遍历右子树;  已知前序和中序，或者已知后序和中序，可以唯一确定一棵二叉树，从而得到第三种遍历顺序先根遍历是 1 2 3 4 5 6（数字为结点的编号，以下同），后根遍历是 3 2 5 6 4 1，中根遍历是：3 2 1 5 4 6  已知前序和后序，不能唯一确定一棵二叉树。先根遍历是 1 2 3 4 5 6（数字为结点的编号，以下同），后根遍历是3 2 1 5 4 6 或者 2 3 1 5 4 6  3 2 5 6 4 1，则该二叉树的可能的中根遍历是 （6） 二叉查找树:对于所有的点，均满足：左子树中所有点值≤根的值≤右子树中所有点的值 中序遍历二叉查找树，得到所有点的升序排列。 (十一)．图 （一）图的表示 1．邻接矩阵表示法: （1）以a[j,k]=0表示点j至点k没有边;以a[j,k]≠0表示点j至点k有边相连。 （2）如果边上没有权值,则有边时a[j,k]=1，如果边上有值，则让a[j,k]等于该值。 （3）邻接矩阵需要n2的数组空间，与图中的边数是无关的。 2．邻接表（邻接链表）表示法: 链表存储每一点出发有多少条边相连。存储空间与边数有关。当边数较少时，可以节省存储空间，提高算法效率。 3．关联矩阵:存储第k条边与哪二个点相连。 （二）图中相关概念 1．无向图中结点的度:与结点相连的边数 n个结点的无向图中，如果结点没有指向自己的边（即无自环），则图中最多有n(n-1)/2条边。 有n(n-1)/2条边的无向图叫完全图。 2．有向图中，结点的出度为从该结点出发的边数;结点的入度为指向该结点的边数。 有向图中，所有结点的入度之和等于所有结点的出度之和。有向完全图共有n(n-1)条边。 3．生成树:

6. 图的遍历最短路径计算方法（即生成最小生成树）：Kruskal算法的基本思路：

G(1,3) G(4,6) G(2,5) G(3,6) G(1,4) G(3,4) G(2,3) G(1,2) G(3,5) G(5,6) 1 2 3 4 5 5 5 6 6 6

（十二）。前缀、后缀表达式 将表达式转换为表达式树。后缀是其后续遍历，前缀是其先序遍历。依据这样的思想，就可以用栈转换了。提示一点：运算符永远是子数的根节点。例如a+bc的后缀是abc+则+是根节点，他的右子树的根节点是*，即后缀中紧挨他的符号，而紧挨的是c，那他一定是的右子树，而b紧挨c，不是符号，所以它只能是的左子树……如此继续下去就可以了。 举例：中缀表达式：+a+bcd(e+f) ；前缀表达式：+*a+bcd+ef 后缀表达式：abc+d+ef+