文章目录
展开摘抄自《CCF CSP第一轮认证一本通》丁向民编著，仅供学习交流，请勿侵权传播。
平时需要自己看的内容：
1.1 基本常识
1.2 系统结构
1.3 软件系统
1.5 信息编码
1.6 网络基础（选看，难度较大）
2.1 计算机语言与算法（可以先不做习题，等学完算法再做）
2.2 C++语言基础
怎么看？
因为全部是常识性内容（说白了就是不需要理解的背诵内容），要求就是大概熟悉，不要求一字不落的掌握，考试的时候遇到尽量能得分就可以（不要求一定全部掌握）。典型习题解析里也有一些知识点，也可以阅读。
有不理解的可以在群里问，我会告诉你如何更好地理解记忆 or 压根不用记忆。
其他内容怎么办？
讲初赛知识点时会统一讲，建议提前阅读预习，上课会讲基础知识介绍和典型习题解析里的部分习题，剩余题目要求理解内容后自行做题并查缺补漏。（部分习题涉及的知识点没讲过可以先跳过）（建议铅笔做题，明年可能还能再做一遍）
讲课后需要自己看的内容
主要看第5,6,7章
次要看课上章节没有讲的内容（讲过的也要看，做复习）
2.0 计算机基础知识
2.0.0 基本常识
2.0.1 系统结构
计算机体系结构：冯诺依曼结构。
计算机应该具有五大部件：存储器、运算器、控制器、输入设备和输出设备。其中，控制器和运算器又称CPU，是冯诺依曼计算机体系结构的核心，其它部件都是通过CPU进行通信的。这类计算机的主要体系结构如下图所示。
2.0.2 软件系统
2.0.3 数据表示与计算
（1）计算机的存储单位
计算机存储数据的最小单位是位（b, bit），一个二进制位要么是0，要么是1，只有这两种状态。
字节（B, Byte）是计算机数据处理的基本单位，1字节为8位，即1B=8b。一般情况下，一个ASCII码字符占用1字节，一个汉字国际码字符占用2字节。
字（word）通常由一个或若干个字节组成。字是计算机进行数据处理时一次存取、加工和传送的数据长度。由于字长是计算机一次所能处理信息的实际位数，所以它决定了计算机数据处理的速度，是衡量计算机性能的一个重要指标，字长越长，计算机的性能越好。
计算机中数据的换算都以字节为基本单位，以 2^{10}=1024 为进率。常见的数据单位及其换算关系如下表所示。
（2）计算机的进制
计算机通常使用的记数制有十进制、二进制、八进制和十六进制。为了能够区别书写的数字是哪个进制的数，通常在数字后面加上一个字母，十进制数加D或者不加（默认为十进制），二进制数加B，八进制数加Q，十六进制数加H。
各个进制之间的换算关系非常重要，下表列出了数字0~15的所有十进制、二进制、八进制和十六进制之间的换算关系。
补充说明如果数值中有小数该如何处理：
X进制转十进制：按位权法，此时注意小数点后第一位为-1次方，以此类推。
如 (101.010)_ 2=(5.25)_{10} ，计算式子为：1\times2^2+0\times2^1+1\times2^0+0\times2^{-1}+1\times2^{-2}+0\times2^{-3}=5.25 。
十进制转X进制：整数部分除X取余，小数部分乘X取整。
如 题目5 (13.375)_{10}=(1101.011)_2 ，计算过程如下：
（3）二进制运算
二进制数运算包括算术运算和逻辑运算。
· 二进制数的算术运算（没什么用，真出了二进制数运算就先转成十进制数运算后再转回二进制数，习题中的解法看看即可）
二进制数的算术运算包括加法、减法、乘法和除法运算。
二进制数加法运算法则是：0+0=0，0+1=1+0=1，1+1=10（向高位进位）。
二进制数减法运算法则是：0-0=1-1=0，1-0=1，0-1=1（借1当2）。
二进制数乘法运算法则是：0×0=0，0×0=1×0=0，1×1=1。
二进制数除法运算法则是：0÷0=0，0÷1=0（1÷0无意义），1÷1=1。
在计算机内部，二进制的加法是基本运算，利用加法可以实现二进制数的减法、乘法和除法运算。在计算机的运算过程中，应用了“补码”进行运算。
· 二进制数的逻辑运算
在逻辑运算中，用1或0表示“真”或“假”。逻辑运算主要包括：逻辑加（又称“或”运算，符号为∨）、逻辑乘（又称“与运算”，符号为∧）、逻辑“非”（符号为-X）和逻辑“异或”（符号为⊕）。各个逻辑运算的运算法则如下表所示。
当两个变量之间进行逻辑运算时，只在对应位之间按上述规律进行逻辑运算，不同位之间没有任何关系，当然也就不存在算术运算中的进位或借位问题。
（4）数值数据的表示
· 机器数和真值
一个数在计算机中的表示形式称为机器数。机器数所对应的原来的数值称为真值。机器数的最高位一般为符号位，0表示正数，1表示负数。
整数机器数的表示法可用图说明，下图是一个用8位二进制数表示的有符号整数，其代表的数为-28。数符为1代表机器数为负数，即-0011100，换算为十进制数-28。
为了便于计算机的运算，机器数采用了不同的编码方法，称为码制。常见的码制有原码、反码、补码和移码。
· 原码
一个数X的原码表示为：符号位用0表示正，用1表示负；数值部分为X的绝对值的二进制形式，记X的原码为 [X]_ 原 。例如，当X=+1100001时，[X]_ 原=01100001；当X=-1110101时，[X]_ 原=11110101。0在原码中有两种表示方式：00000000和10000000，即+0和-0。（这里都是以8位二进制数举例）
原码的特点是容易与真值相转换，但做加减运算不太方便。比如-1+1=10000001+00000001=00000000，无法通过二进制的算术运算来表示计算。
· 反码
一个数X的反码表示为：若X为正数，则其反码和原码相同；若X为负数，则在原码的基础上符号位保持不变，数值位按位取反，记X的反码为 [X]_ 反 。例如，当X=+1100001时，[X]_ 反=01100001；当X=-1100001时，[X]_ 反=10011110。0在反码中也有两种表示形式：00000000和11111111。
反码弥补了原码做加减运算的不足。例如，若 X_1=97,X_2=-97 ，则 X_1+X_2=0 。利用二进制原码运算为：若 [X_1]_ 原=01100001， [X_2]_ 原=11100001，则 [X_1]_ 原+[X_2]_ 原 为
注：虚框内为溢出码。
结果转换为十进制数为66，显然不对。
若利用反码进行运算，则 [X_1]_ 反=01100001，[X_2]_ 反=10011110，则 [X_1]_ 反+[X_2]_ 反 为
该结果为负数，将此负数由反码转换成原码，其结果为10000000，即为-0。
虽然反码解决了加减运算问题，但由于并没有解决0的两种表示方法的不足，因此现在已经较少使用了。
· 补码
一个数X的补码表示方式为：当X为正数时，X的补码与X的原码相同；当X为负数时，X的补码的符号位与原码相同，其数值位取反加1。记X的补码表示为 [X]_ 补 。例如，X=+1110001，[X]_ 补=01110001；X=-1110001，[X]_ 补=10001111。0在补码中的表示是唯一的，即00000000，而10000000表示-128的补码、11111111表示-1的补码。
补码不仅解决了加减运算问题，而且0的表示也是唯一的。接着上述反码的例子，如果利用补码进行运算，[X_1]_ 补=01100001，[X_2]_ 补=10011111，则 [X_1]_ 补+[X_2]_ 补 为
该结果为0，并且没有+0和-0之分。
关于溢出：
正数+负数的溢出是正常现象，不会导致计算错误。但正数+正数或负数+负数的溢出都会导致结果错误。比如-128+(-1)等价于
10000000
+11111111
1 01111111
即结果为127。
进一步考虑，可以认为数值是在-128~127内循环，-128-1没有数值，循环回127。属于是物极必反的典型了。
补码比原码、反码所能表示的范围略宽，1字节（8位）的有符号整数能表示的范围为-128\~127，而原码和补码都只能表示-127\~127，所以补码目前被广泛应用于计算机的数制表示中。
典型习题解析
题目4 在8位二进制补码中，10101011表示的数是十进制下的（）。
A. 43 B. -85 C. -43 D. -84
题目7 与二进制小数0.1相等的八进制数是（）。
A. 0.8 B. 0.4 C. 0.2 D. 0.1
题目11 1TB代表的字节数量是（）。
A. 2的10次方 B. 2的20次方 C. 2的30次方 D. 2的40次方
题目13 下列各无符号十进制整数中，能用8位二进制表示的数中最大的是（）。（题目有问题）
A. 296 B. 133 C. 256 D.199
题目23 一个自然数在十进制下有n位，则它在二进制下的位数与（）最接近。
A. 5n B. nlog_210 C. 10log_2n D. 10nlog_2n
2.0.4 信息编码
信息的范畴很广泛，除了上一节介绍的数值型数据外，还有很多非数值型数据，主要包括字符、汉字、图形图像、声音、音频、视频等。这些类型的数据由于格式不同，其信息表示的方式也大相径庭。
- 英文字符数据的表示
英文字符编码方案的国际标准为ASCII码。ASCII码利用7位二进制数表示，共有128个元素。1字节（8位）是计算机中的常用单位，ASCII码字符将字节中多余的最高位取0。如下表所示为7位ASCII码字符的编码表。
-
汉字的存储与编码
-
图像数据的表示
图像数据的表示方法与声音相似，都需要先将图像数据数字化。
目前，图像的数字化途径主要有两类：一类是利用扫描设备对各类图像资料进行扫描，通过扫描仪实现数字化；另一类是通过数码相机直接对景物进行拍摄，数码相机直接将拍摄到的景物数字化。不论哪种途径，数字化过程大体都分为采样、量化和编码三步。下图演示了灰度图像的数字化过程。
采样：将连续的图像划分成M×N个像素点
量化：将每个像素点的颜色/灰度由连续的区间划分成间断的数值。
编码：把离散的像素矩阵按一定方式编制成二进制编码组，并将所得到的图像数据按某种图像格式记录在图像文件中。
影响图像质量的两个重要参数就是图像分辨率和颜色深度，图像分辨率越高，颜色深度越深，则数字化后的图像效果就越逼真，图像数据量就越大。
对于一幅图像，其分辨率为M×N，其颜色深度为D，图像的数据量可利用以下公式计算：图像数据量=M×N×D/8（Byte）。
例如，一幅1024×768像素的32位彩色图像，其文件大小的计算过程如下：1024×768×32/8=3145728B=3MB。 -
声音数据的表示
补充霍夫曼/哈夫曼编码：
霍夫曼编码（Huffman Coding）是可变字长编码的一种，由霍夫曼于1952年提出，该方法完全依据字符的出现概率构造异字头的平均长度最短的码字，有时称为最佳编码。
霍夫曼编码的算法步骤如下：
（1）初始化，将信号源的符号按照出现概率递减的顺序排列；
（2）计算，将两个最小的出现概率进行合并相加，将得到的结果作为新符号的出现概率；
（3）重复步骤（1）和（2）直到概率相加的结果等于1;
（4）分配码字，为所有出现的符号分配码字，概率大的符号用编码0表示，概率小的符号用编码1表示（当然也可以倒过来）;
（5）记录编码，记录概率为1处到当前信号源符号之间的0，1序列，从而得到每个符号的编码。
讲到数据结构-树时可以更好理解。
此编码方式的优点是：给定一段连续的编码，可以唯一确定一个字符序列，且理论占用长度较小。
典型习题解析
题目6 现有一段文言文，要通过二进制哈夫曼编码进行压缩。为简单起见，假设这段文言文只由4个汉字“之”“呼”“者”“也”组成，它们出现的次数分别为700、600、300、200那么，“也”字的编码长度是（）。
本题编码过程如下图所示：
利用霍夫曼编码最后得到“也”字的编码为 (001)_2，编码长度为3。
2.0.5 网络基础
2.1 程序设计基础
2.1.0 计算机语言与算法
2.1.1 C++语言基础
- 常量还有一种声明方式：
#define pi 3.14159，此方式又叫宏定义，会将程序中所有出现pi的地方替换为3.14159，又如#define int long long可将程序中所有int替换为long long，当可能出现溢出时可以采用此方法+void main()的方式。另：只有单独出现int的地方会被替换，假如有个变量叫intt，则其不会被替换为long longt。 -
指针运算符和取地址运算符：C/C++语言有一个非常大的优势是其可以通过指针直接访问内存。我们知道数据是存储在内存中的，每一块空间都有一个地址。绘图举例。
12345678int a=10; //声明一个变量叫a，将值10赋给它int *p; //声明一个指针叫p，其用来存int型数据的地址，声明指针的方式为：数据类型 *指针变量名p=&a; //通过取地址符将a的地址取出并赋给指针变量pcout<<p<<endl; //输出记录在指针变量p中变量a的地址*p=1000; //在一个已经声明的指针变量p前加*表示对其解引用，相当于访问p存的地址。cout<<a<<endl; //因为p中存的是a的地址，所以*p修改的是a的地址存放的内容，因此会修改a的值详细了解（如指针和数组、函数结合）可以参考：黑马程序员|C++教程从0到1入门编程(P56-P63)
-
求字节运算符sizeof：可以计算任何数据占用的字节数，方法为将该变量放入括号中。
123456789101112char c;int a;string s="123456";struct node{int a,b,c;double t[100];}stu;cout<<sizeof(c)<<endl;cout<<sizeof(a)<<endl;cout<<sizeof(s)<<endl;cout<<sizeof(stu)<<endl; - goto语句，表示跳转到指定位置。
1234567891011121314cout<<"1"<<endl;goto FLAG;cout<<"2"<<endl;cout<<"3"<<endl;FLAG:cout<<"4"<<endl;cout<<"5"<<endl;/*输出如下：145*/
2.2 基本数据结构
数据结构是指相互之间存在一种或多种特定关系的数据元素集合，即数据结构=元素+关系。
数据结构的形式定义为：数据结构是一个二元组Data_Structure=(D, R)。其中，D是数据元素的有限集，R是D上关系的有限集。
数据结构的定义是对操作对象的一种数学描述，结构中定义的“关系”描述的是数据元素之间的逻辑关系，因此称为数据的逻辑结构。存储结构（又称物理结构）是逻辑结构在计算机中的存储映像，是逻辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。
逻辑结构和存储结构的关系为：存储结构是逻辑关系的映像和元素本身的映像。
逻辑结构是抽象，存储结构是实现，两者综合起来建立了数据元素之间的结构关系。
根据数据元素之间关系的不同特性，通常有以下4类基本的数据结构。
- 集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其他关系。
- 线性结构：结构中的数据元素之间存在一对一的线性关系。
- 树状结构：结构中的数据元素之间存在一对多的层次关系。
- 图状结构或网状结构：结构中的数据元素之间存在多对多的任意关系。
数据元素之间的关系在计算机中有两种不同的表示方法：顺序存储结构和链式存储结构。
2.2.0 线性表
线性表（Linear List）是由 n(n\geq0) 个类型相同的数据元素 a_1,a_2,…,a_n 组成的有限序列，记为 (a_1,a_2,…,a_{i-1},a_i,a_{i+1},…,a_n) 。这里的数据元素 a_i(1\leq i\leq n) 只是一个抽象的符号，其具体含义在不同情况下也不同，既可以是原子类型，也可以是结构类型，但同一线性表中的数据元素必须属于同一数据对象。此外，线性表中相邻数据元素之间存在序偶关系，即对于非空的线性表，表中 a_{i-1} 领先于 a_i ，称 a_{i-1} 是 a_i 的直接前驱，而称 a_i 是 a_{i-1} 的直接后继。除了第一个元素 a_1 外，每个元素 a_i 有且仅有一个被称为直接前驱的节点 a_{i-1} ，除了最后一个元素 a_n 外，每个元素 a_i 有且仅有一个被称为直接后继的节点 a_{i+1} 。线性表中元素的个数 n 被定义为线性表的长度， n=0 时称为空表。
线性表的特点可概括如下：
- 同一性：线性表由同类数据元素组成，每个 a_i 必须属于统一数据对象。
- 有穷性：线性表由有限个数据元素组成，表的长度就是表中数据元素的个数。
- 有序性：线性表中相邻数据元素之间存在序偶关系 <a_i, a_{i+1}> 。
由此可以看出，线性表是一种最简单的数据结构，因为数据元素之间是由“一前驱一后继”的直观有序的关系确定的；线性表也是一种常见的数据结构，因为矩阵、数组、字符串、栈、队列等都符合线性条件。
线性表根据数据存储的不同分为顺序表和链表。
顺序表指用一组地址连续的存储单元依此存储线性表的数据元素，称为线性表的顺序存储结构或顺序映像（Sequential Mapping），它以“物理位置相邻”表示线性表中数据元素之间的逻辑关系，可以随机存取表中任一元素。下图表示一个具体的顺序表的例子。
在使用链表结构表示数据元素 a_i 时，除了存储 a_i 本身的信息之外，还需要一个存储指示其后继元素的存储位置，这两个部分组成了 a_i 的存储映像，通常称为节点（node）。
其中，data域为数据域，用来存储节点的值；next域为指针域，用来存储节点的直接后继的存储地址（位置）。n个节点组成了一个链表，即线性表 (a_1,a_2,…,a_n) 的链式存储结构，其抽象表示如下图所示。
补充知识：
- 题目1 字符串（String）是由数字、字母、下划线等组成的一串字符。一般记为 s=a_1,a_2,…,a_n(n\geq0) ，它是编程语言中表示文本的数据类型。在程序设计中，字符串为符号或数值的一个连续序列。字符串是一种特殊的线性表，串的长度可以为0，即空串。
-
题目2 链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起的。如果要访问链表中的一个元素，则需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表结构就非常简单了，只要修改元素中的指针就可以了。
-
题目4 哈希表是根据关键码值（key vaule）而直接进行访问的，它通过把关键码映射到表中的一个位置访问记录，以加快查找的速度，这个映射函数称为哈希函数。
-
题目5 双向链表中有两个指针域llink和rlink，分别指向该节点的前驱及后继。
-
题目6 二分查找也称折半查找（Binary Search），每次查找都会去除一半的数据，是一种高效的查找方法，但该算法有两个先决条件：必须采用顺序存储结构；必须按关键字大小有序排列。
二分查找法每次将表中间位置记录的关键字与查找关键字进行比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直至找到满足条件的记录，使查找成功或子表不存在为止。
二分查找法的最大比较次数是 log_2n 向上取整数。
2.2.1 栈和队列
栈（stack）是限定在表的一端进行插入和删除运算的线性表，通常将插入、删除的一段称为栈顶（top），将另一端称为栈底（bottom），将不含元素的空表称为空栈。
假设栈 S=(a_1,a_2,…,a_n) ，若栈中元素按 a_1,a_2,…,a_n 的顺序进栈，其中 a_1 为栈底元素， a_n 为栈顶元素，那么退栈的顺序就是 a_n,a_{n-1},…,a_1 。也就是说，栈的修改是按后进先出（先进后出）的原则进行的。因此，栈又称后进先出（Last In First Out/First In Last Out）的线性表，简称LIFO/FILO表，如下图所示。
队列（queue）也是一种受限的线性表，它只允许在表的一端进行元素的插入，而在另一端进行元素的删除。允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。
在队列中，通常把元素的插入称为入队，把元素的删除称为出队。队列的概念与现实生活中的排队相似，新来的成员总是排在队尾，排在队列最前面的成员总是最先离开队列，即先进先出，因此又称队列为先进先出（First In First Out，FIFO）表。
假设有队列 q=(a_1, a_2,…,a_n) ，在空队列的情况下，依次加入元素 a_1,a_2,…,a_n) 之后，a_1 就是队头元素，a_n 则是队尾元素。退出队列也是按此顺序进行的，也就是说，只有在a_1,a_2,…,a_{n-1} 都出队之后，a_n 才能出队。队列的示意图如下图所示。
补充知识：
- 题目2 四则运算表达式共有前缀表达式、中缀表达式和后缀表达式三种形式，用来进行表达式求值。
中缀表达式就是常见的运算表达式，如 (3+4)* 5-6 。
前缀表达式又称波兰表达式，前缀表达式的运算符位于操作数之前，如 -* +3456 。
后缀表达式又称逆波兰表达式，与前缀表达式相似，只是运算符位于操作数之后，如 34+5* 6-。
中缀表达式对于计算机自动计算表达式结果不太方便，转换成前缀表达式和后缀表达式后，非常方便计算，所以表达式转换是常见操作。转换方法主要有两种：一是手工转换，二是计算机转换。
典型题目解析
题目3 题目4 题目5 题目10 题目13
2.2.2 树
树是一类重要的非线性数据结构，树中的节点之间具有明确的层次关系，并且节点之间有分支。非常类似于真正的树。树状结构在客观世界中大量存在，如行政组织机构和人类社会的家谱等都可用树状结构形象地表示。
树是 n(n\geq0) 个节点的有限集 T 。 T 要么是空集（空树），要么是非空集。对于一棵非空树，有且仅有一个特定的称为根（root）的节点，其余节点可分为 m(m>0) 个互不相交的有限集 T_1, T_2,…,T_m ，其中每个集合本身又是一棵树，并称为根的子树。例如下图表示的是一个有9个节点的树，其中A是根节点，其余节点分成3棵互不相交的子集： T_1={B,E,F,G},T_2={C},T_3={D,H,I} ，T_1, T_2,T_3 都是根A的子树，且本身也是一棵树。
一个节点拥有的子树数称为该节点的度（degree）。一棵树中节点的最大度数称为该树的度。在下图所示的某大学的行政组织结构树中，文学院节点的度为3，是所有节点中度最大的，也作为该树的度。（树的度就是树中所有节点的度中最大的）
树中节点的最大层数称为树的深度（depth）或高度。节点层数（level）从根开始算起，根为第1层，其余节点的层次等于其双亲节点的层数加1。
度数为0的节点称为叶子（leaf）节点，度数不为0的节点称为非终端节点。
森林（forest）是 m(m\geq0) 棵互不相交的树的集合。若将一棵树的根节点删除，则得到该树的子树所构成的森林，将森林中所有树作为子树用一个根节点连起来，森林就变成了一棵树。
二叉树（binary tree）是一种特殊的树，其每个节点的度都不大于2，并且每个节点的孩子节点的次序不能任意颠倒。由此可知，一个二叉树中的每个节点只能含有0、1或2个孩子，并且每个孩子有左右之分。通常把位于左边的孩子称为左子树，把位于右边的孩子称为右子树。二叉树的基本形态有以下5种。
补充知识：
- 题目1 满K叉树，即每个节点度数要么为K要么为0。
- 题目5 二叉树的遍历根据遍历根节点、左子树和右子树的顺序的不同而分为前序遍历中序遍历和后序遍历三种，这三种遍历方法是根据遍历根节点的先后顺序区分的。先遍历根节点的称为前序遍历，中间遍历根节点的称为中序遍历，最后遍历根节点的称为后序遍历。左子树和右子树的遍历都是先遍历左子树，后遍历右子树。（练习题知识点巩固的第10题）
- 题目15 完全二叉树的顺序存储方案是指将完全二叉树的节点从上至下、从左至右依次存放到一个顺序结构的数组中。
2.2.3 图
图是一种复杂的非线性结构。图结构与表结构和树结构的不同之处表现在节点之间的关系上，线性表中节点之间的关系是一对一的，即每个节点仅有一个直接前驱和直接后继（若存在前驱和后继）；树是按分层关系组织的结构，树结构中节点之间的关系是一对多的，即一个双亲可以有多个孩子，每个孩子节点仅有一个双亲；对于图结构，图中节点之间的关系可以是多对多的，即一个节点和其它节点的关系的任意的，可以有关，也可以无关。由此可见，图G \subset 树T \subset 表L。
图（Graph）是一种网状数据结构，其形式化定义如下：
Graph=(V,\ R)
V={X|X\in DataObject}
R={VR}
VR={<x,y>|P(x,y)∧ (x,y\in V)}
DataObject为一个集合，该集合中的所有元素均具有相同的特性。V中的数据元素通常称为顶点（vertex），VR是两个顶点之间的关系的集合。P(x, y)表示x和y之间有特定的关系属性P。
若 <x,y>\in VR ， <x,y> 表示从顶点x到顶点y的一条弧（arc），并称x为弧尾（tail）或起始点，称y为弧头（head）或终端点，此时图中的边是有方向的，这样的图称为有向图。
若 <x,y>\in VR 则必有 <y,x>\in VR ，即VR是对称关系，这时以无序对 (x,y) 代替两个有序对，表示x和y之间的一条边（edge），此时的图称为无向图。
图的遍历搜索算法主要有两种：深度优先搜索（Depth First Search， DFS）遍历和广度优先搜索（Breadth First Search， BFS）遍历。
深度优先搜索遍历类似树的前序（先根）遍历。假设初始状态是图中所有顶点都未曾访问过的，则在图中任选一顶点v作为初始出发点，首先访问出发点v，并将其标记为已访问过，然后依此从v出发搜索v的每个邻接点w，若w未曾访问过，则以w作为新的出发点出发，继续进行深度优先遍历，直到图中的所有顶点都被访问为止。
广度优先搜索遍历类似树的按层次遍历，其基本思想是：首先访问出发点 v_1 ，接着依此访问 v_1 的所有未被访问的邻接点 v_{i1},v_{i2},…,v_{it} ，并均标记为已访问过，然后按照 v_{i1},v_{i2},…,v_{it} 的次序访问每一个顶点的所有未曾访问过的邻接点，并均标记为已访问过，以此类推，直到图中所有和初始出发点 v_1 路径相通的顶点都被访问为止。需要使用队列，详见栈和队列题目9。
2.2.4 排序
排序算法大体可以分为以下两种：
第一种是比较排序，时间复杂度为 O(nlogn)\sim O(n^2) ，主要有冒泡排序、选择排序、插入排序、堆排序、归并排序、快速排序等。
第二种是非比较排序，时间复杂度可以达到 O(n) ，主要有计数排序、基数排序等。
下表给出了常见排序算法的性能指标。
稳定排序算法对于稳定性的简单形式化定义为：如果 A_i=A_j ，排序前 A_i 在 A_j 之前，排序后 A_i 还在 A_j 之前，则称这种排序算法是稳定的，即保证排序前后两个相等的数的相对顺序不变。对于不稳定的排序算法，只要举出一个实例，即可说明它的不稳定性；而对于稳定的排序算法，必须对算法进行分析以得到稳定的特性。
排序算法是否为稳定的是由具体算法决定的，不稳定的算法在某些条件下可以变为稳定的算法，而稳定的算法在某些条件下也可以变为不稳定的算法。例如，冒泡排序原本是稳定的排序算法，如果将记录交换的条件改成 A[i]>=A[i+1]，则两个相等的记录就会交换位置，从而变成不稳定的排序算法。
排序算法具有稳定性的好处是：排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，则前一个键排序的结果可以为后一个键排序所用。比如先按键A从小到大排序，再按键B从小到大排序，如果算法稳定的话，键B中相等的对象其顺序是按照键A从小到大的。基数排序就是这样先按低位排序，逐次按高位排序，低位排序后元素的顺序在高位相同时是不会改变的。