预赛知识点.doc

一．国标码、区位码、机内码之间的关系
五笔输入法、拼音
国标码：（“国家标准信息交换用汉字编码”（GB2312-80标准））
国标码是一个四位十六进制数，区位码是一个四位的十进制数，每个国标码或区位码都对应着一个唯一的汉字或符号，但因为十六进制数我们很少用到，所以大家常用的是区位码，它的前两位叫做区码，后两位叫做位码
区位码：将GB 2312—80的全部字符集组成一个94×94的方阵，每一行称为一个“区”，编号为0l～94；每一列称为一个“位”，编号为0l～94，这样得到GB 2312—80的区位图，用区位图的位置来表示的汉字编码，称为区位码。
机内码：为了避免ASCII码和国标码同时使用时产生二义性问题，大部分汉字系统都采用将国标码每个字节高位置1作为汉字机内码。这样既解决了汉字机内码与西文机内码之间的二义性，又使汉字机内码与国标码具有极简单的对应关系。
汉字交换码：汉字信息处理系统之间或通信系统之间传输信息时，对每一个汉字所规定的统一编码，我国已指定汉字交换码的国家标准“信息交换用汉字编码字符集——基本集”，代号为GB 2312—80，又称为“国标码”。
中
国标码=区位码+20 20H（或十进制32 32，或二进制00100000 00100000）
机内码=国标码+80 80H（或十进制128 128，或二进制10000000 10000000）
机内码=区位码+A0 A0H（或十进制160 160，或二进制10100000 10100000）
例：“中”字位于区位码表的第54区第48位，它的区位码、国标码、机内码如下表所示
十进制
十六进制
二进制
区位码
国标码
机内码
区位码
国标码
机内码
区位码
国标码
机内码
54 48
86 80
214 208
36 30
56 50
D6 D0
00110110 00110000
01010110 01010000
11010110 11010000
二．十进制、二进制、十六进制、八进制
十进制以D表示(Decimal)，二进制以B表示(Binary)，十六进制以H表示(Hex)，八进制以O表示(Octal)。
1．十进制整数转二进制整数：
法1：除2取余，余数倒着写。
法2：按幂展开，如35=25+21+20，(35)10=(100011)2
2．二进制整数转十进制整数：乘权相加。如(110010)2=1*25+1*24+0*23+0*22+1*21+0*20=50
3．二进制整数与十六进制整数互化：
从最低位开始，每4位二进制化为一位十六进制数；反之每一位十六进制化为4位二进制。
如(10011)2=(0001 0011)2=13H， 4AH=(0100 1010)2=(1001010)2
4．二进制整数与八进制整数互化：
从最低位开始，每3位二进制化为一位八进制数；反之每一位八进制化为3位二进制。
如(10011)2=(010 011)2=(23)8， (236)8=(010 011 110)2=(10011110)2
5．十进制小数转二进制小数：
法1：乘2取余。
法2：按幂展开，如0.375=2-2+2-3，(0.375)10=(0.011)2
显然，有些十进制小数转二进制时，是取不尽的，只能是不精确的。比如0.3，取二进制位数不同时，能得到的不同值如下表所示：
2位
6位
10位
13位
(0.01)2=0.25
(0.010011)2=0.296875
(0.0100110011)2=0.2998046875
(0.0100110011001)2=0.2999267578125
6．二进制小数转十进制小数：乘权相加。如(0.1101)2=1*2-1+1*2-2+0*2-3+1*2-4=0.8125
7．二进制小数与十六进制小数互化：
从小数第1位开始，每4位二进制化为1位十六进制数；反之每1位十六进制化为4位二进制小数。
如(0.10011)2=(0.1001 1000)2=0.98H， 0.4AH=(0.0100 1010)2=(0.0100101)2
8．二进制小数与八进制小数互化：
从小数第1位开始，每3位二进制化为1位八进制数；反之每1位八进制化为3位二进制。
如(0.10011)2=(0.100 110)2=(0.46)8， (0.26)8=(0.010 110)2=(0.01011)2
三．原码、反码和补码 var f:array[1..10000]of longint;
fillchar(f,sizeof(f),$7f);
最高位表示符号，0代表正数，1代表负数。其它位表示数的绝对值。
1．正数的原码=反码=补码。如一个字节8位表示时，9的原、反、补码均为00001001
2．负数的原码：最高位（符号位）为1，其它位值=该数的绝对值的二进制表示。
负数的反码：最高位为1，其它位为原码取反。
负数的补码：反码加1（即最低位加1）。
由负数的补码求原码：符号位为1不变，其它位取反，再在最低位加1。
例：以8位二进制表示，则-3的原码10000011，反码11111100，补码11111101。
计算机中运算过程中都是以补码进行！
not 1 = -2
not 2= -3

3．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
n位二进制,原码、反码只能表示2n-1个数,它们为-(2n-1-1)~2n-1-1。补码能表示2n个数,它们是-2n-1~2n-1-1

4．实数以科学计数法表示。尾数：二进制纯小数；阶码：二进制整数，表示2的次方。
例：一个实数，尾数为以原码表示的011，阶码为以补码表示的1111，求该数以十进制表示的值
尾数值(0.11)2=0.75，阶码值-1（补码取反，再加1得真值）。于是值为0.75*2-1=0.375
四．数据的校验
1．奇偶校验：n位二进制数中，n-1位表示数据，最高位表示校验位。
（1）奇校验：校验位的取值使n位数据有奇数个1。
当n-1位数据有奇数个1时，校验位取0; 当n-1位数据有偶数个1时，校验位取1
（2）偶校验：校验位的取值使n位数据有偶数个1。
当n-1位数据有偶数个1时，校验位取0; 当n-1位数据有奇数个1时，校验位取1
例：数据10111采用奇校验时，得110111，偶校验时得010111。
奇偶校验法能检查出奇数位的错误，不能检查出偶数位的错误。因为2位、4位等同时出错，不会改变数据的奇偶性。奇偶校验法不能知道是哪一位出错。
2．海明码校验（奇或偶）
（1）只能检查出一位出错情况，它能知道是哪一位出错了。不能查出二位及以上的差错。
（2）有m位数据，最少需要的校验位数为r，r为使m+r+1≤2r成立的最小整数。
所有第2k位为校验位，其它为数据位。校验位的值的计算：比如第6位（110）将影响第2位和第4位，第11位（1011）将影响第1、2、8位。
比如有8位数据，需要4位校验位。第1、2、4、8位为校验位，第3、5、6、7、9、10、11、12为数据位。以a[k]表示第k位，采用偶校验时，各校验位的计算如下：(奇校验时，取相反值)
a[1]=a[3] xor a[5] xor a[7] xor a[9] xor a[11] a[2]=a[3] xor a[6] xor a[7] xor a[10] xor a[11]
a[4]=a[5] xor a[6] xor a[7] xor a[12] a[8]=a[9] xor a[10] xor a[11] xor a[12]
例：数据为01001010
位数的二进制表示
1
10
11
100
101
110
111
1000
1001
1010
1011
1100
位数（第几位）
1
2
3
4
5
6
7
8
9
10
11
12
偶校验
1
0
0
0
1
0
1
1
0
0
1
0
奇校验
0
1
0
1
1
0
1
0
0
0
1
0
五．常见运算符及运算次序
1．几种逻辑运算符及常见的表示符号
运算符
非
与
或
异或
常见符号
NOT ~ ┍ ∧
AND ∧ · *
OR ∨ +
XOR +
含义
NOT true得false
NOT false得true
True and true得true
其余情况得false
False or false得false
其余情况得true
相同时得false
不同时得true
注意，我们有时以1表示True，以0表示False。
2．整数的逻辑运算（实数不能作逻辑运算）
将数字转换为二进制补码表示（计算机中，整数是以补码存储的），然后按位作逻辑运算，1作True,0作False，结果为二进制补码。
例：如果数为integer型（16位二进制），则：
not 2=not (00000000 00000010)=(11111111 11111101)补=(10000000 00000011)原=-3
not (-3)=not(10000000 00000011)原=not(11111111 11111101)补=00000000 00000010补=2
57 and (-35)=00000000 00111001 and 11111111 11011101=00000000 00011001补=25
57 or (-35)=00000000 00111001 or 11111111 11011101=11111111 11111101补=-3
57 xor (-35)=00000000 00111001 xor 11111111 11011101=11111111 11100100补=-28
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 1**2得4; 1 xor 2+1得4; 1+2 xor 1得2。
4．几种应该注意的运算：
运算
a\b
3 shL 4
25 shr 3
2**3
a mod b
inc(a)
Inc(s,t)
Dec(s)
Dec(s,t)
a in s
含义
a div b
3左移4位即3*24
得48
25右移3位即25 div 23
得3
23
得8
即a-a div b*b,注意a或b为负数时的情况
a:=a+1
S:=s+t
S:=s-1
S:=s-t
判断元素
a是否在
集合s中
判定元素a不在集合S中，使用not (a in s)，不能使用a not in s(连续两个运算符了，这是英语的说法)
5．集合运算
(1)交集 ∧或∩ (2)并集 ∨或∪ (3)差值：以减号表示，A-B表示从集合A除去集合B中有的元素。

计算机
系统
软件
系统
硬件
系统
运算器
控制器
存储器
输入设备:鼠标、键盘、扫描仪、麦克风(话筒)等
输出设备:显示器、打印机、绘图仪、耳机、音响等
中央处理器
CPU
内存储器
外存储器
RAM,随机存储器,另配的内存条,插在
主板的内存条插槽上,关机后信息丢失
ROM,只读存储器,集成在主板上了,
存储的是如何开机的指令等
硬盘、光盘、U盘、软盘、磁带
系统
软件
应用
软件
除了系统软件外的其它软件
操作系统：如DOS、windows、Linux、Unix、Netware、OS2、Xnix等
编程语言:如C、Pascal、Basic、Fortran等
数据库:如Access、FoxPro、
SQLServer、Oracle等
六．计算机系统的组成

1．各种存储设备的速度
寄存器>高速缓冲存储器>内存>硬盘>光盘U盘>软盘、磁带
CPU中
外存储器

CPU处理的信息都放在寄存器中，寄存器的速度非常快，可以匹配高速的CPU的速度。但是寄存器的价格很高。现在不用的数据，会放在内存中，要用时，向内存中去读取。内存的速度远慢于CPU，于是，在寄存器与内存之间设置了高速缓冲存储器。
2．操作系统的分类
（1）单任务操作系统：DOS，它是基于字符命令的操作系统，没有图形界面。
（2）多任务操作系统：除了DOS以外，均为多任务操作系统。
（3）网络操作系统：比如window NT、windows2000 server（即服务器版）、Linux、Unix、Netware等。
Windows98、windows2000 profession等不是网络操作系统。
3．存储容量换算单位 DreamWaver Flash MacroMedia
1TB=1024GB 1GB=1024MB 1MB=1024KB 1KB=1024B 1B（字节）=8bit（位）
例：下载速度为10kbps,下载一幅大小为96KB的图像文件，需要多少时间？
解：10kbps指每秒10K位，所需时间为96k*8/10k=76.8秒=1.28分
4．N位二进制数，可以表示2n个不同信息。
5．MIPS：指CPU每秒执行百万条指令 Million Instructions Per Second
七．图像、视频、矢量图
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：一幅分辨率为800*600的24位图像，需要多少存储空间？
解：该图像有800*600格，每个小格图像颜色以24位二进制描述，
共需存储空间800*600*24位=800*600*3B=1406.25KB≈1.37MB
（注：该图像每格颜色有224=16777216种色彩，非常接近真实的大自然了。）
例2：一幅分辨率为1024*768的16色图像，需要多少存储空间？
解：该图像有1024*768格，每个小格图像颜色有16种，以4位二进制描述，
共需存储空间1024*768*4位=1024*768/2B=384KB=0.375MB
例3：一幅分辨率为1024*768的黑白单色图像，需要多少存储空间？
解：该图像有1024*768格，每个小格图像颜色有2种，以1位二进制描述，
共需存储空间1024*768*1位=1024*768/8B=96KB
2．视频文件
视频文件的扩展名有avi,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帧，画面为640*480的24位真彩色，问需要多少存储空间？
解：该视频相当于每秒放25幅图片，每幅图片停留0.04秒，利用人的视觉残留，给人以连续的图像感觉。
（1）1幅图片存储空间为：640*480*24/8B=900kB
（2）1秒存储空间为900KB*25=22500KB
（3）1小时存储空间为：22500kB*3600≈79101MB≈77.2GB
由此可见，未经压缩的avi视频文件实在是太大了，不仅需要很大的存储空间，且网上下载也太慢。在的mpeg标准下，压缩比可以达到200:1。MPEG的全名为Moving Pictures Experts Group，中文译名是动态图像专家组。
八．高级语言的执行方式:
1．机器语言：二进制数表示的命令
2．汇编语言：低级的语言，与每台机器密切相关，运行效率比高级语言高。
3．高级语言：与每台机器无关（可移植性好），运行效率不如汇编语言程序.
高级语言的执行方式:最终都要转换成二进制数表示的机器语言(目标程序，扩展名为exe)
编译方式：先形成目标程序，然后再一次性执行，如C,Pascal,Fortran,Visual Basic语言等。
解释方式：逐条解释执行，不形成目标程序，如Qbasic语言。
九．IP地址
每台联网的计算机都会有一个IP地址。现在使用的IP地址系统称为IPV4，使用32位二进制表示。而IPV6使用128位二进制表示。为了方便使用，将IPV4的32位二进制分成4段，每段8位二进制，化成十进制值在0~255之间，每段之间加一个小数点，这叫点分十进制。
网络设备根据IP地址的第一个字节来确定网络类型。
A类网络第一个字节的第一个二进制位为0；00000001~01111111，即十进制1~127。
B类网络第一个字节的前两个二进制位为10；10000000~10111111，即十进制128~191。
C类网络第一个字节的前三位二进制位为110，11000000~11011111，即十进制192~223。
D类网络第一个字节的前四位二进制位为1110，11100000~11101111，即十进制224~239。
其余240及以上为E类地址。
Internet地址授权机构(IANA)控制IP地址分配方案中，留出了三类网络号，给不连到Internet上的专用网用，分别用于A，B和C类IP网，具体如下：
　　A类10.0.0.0～10.255.255.255 　B类172.16.0.0～172.31.255.255 　　C类192.168.0.0～192.168.255.255
　　IANA保证这些网络号不会分配给连到Internet上的任何网络，因此任何人都可以自由的选择这些网络地址作为自己的网络地址。
十．域名
在Internet上的计算机，可以申请一个域名。域名为以小数点分隔的字符，从右至左逐级递减。如：
表示中国(cn)、网络(net)、镇海中学(zhzx)、提供www服务的一台计算机。

美国以外的网络，域名的最后一个字段为国名，比如中国cn，日本jp，英国UK，台湾TW等。
有些英文名的意思是约定俗成的。如下表所示：
英文
com
gov
edu
net
mil
org
含义
商业机构
政府部门
教育机构
网络
军事
其它组织
十一．一些网络名称
名称
www
Internet
Intranet
TCP/IP
HTTP
HTML
含义
万维网
因特网
内部网
传输控制协议/网际协议
Transmission Control Protocol/Internet Protocol
超文本传输协议
Hypertext Transfer Protocol
超文本标记语言HyperTextMark-up
Language

名称
FTP
POP3
SMTP
DNS
含义
文件传输协议File Transfer Protocal
邮局协议,用于接收邮件Post Offic Protocal V3
简单邮件发送协议
Simple Mail Transfer Protocol
域名服务器,将域名翻译为IP地址Domain Name Server

名称
Telnet
BBS
LAN
MAN
WAN
含义
远程登录
电子公告板
Bulletin Board System
局域网
LocalAreaNetwork
城域网
Metropolitan Area Network
广域网
wide area network
十二．各种排序方法 基于元素之间比较的排序方法，时间复杂度不会快于O(nlogn)。

选择排序
插入排序
冒泡排序
快速排序
归并排序
堆排序
希尔排序
时间复杂度
O(n2)
O(n2)
O(n2)
O(nlogn)
O(nlogn)
O(nlogn)
约O(n1.5)
稳定性
稳定
稳定
稳定
不稳定
稳定
不稳定
不稳定
数据有序时
不变
变快
变快
变慢
不变
不变
不变
特殊应用

求第k大数
求逆序对数
优先队列

如果待排序元素值在很小的范围内，则可以使用O(n)时间的基数排序。
十三．线性表
（一）数组和链表
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)时间。
链表的优缺点: 每次查询元素较慢,需要O(n)时间遍历链表; 每次插入和删除时间较快只要O(1)时间。
（二）队列和循环队列
1．先进先出（FIFO），一端（队尾）插入，另一端（队首）删除，可以以数组或链表来模拟。
2．用于宽度优先遍历
3．以n个位置的数组来存储队列时，线性队列中最多可以存储n个元素，循环队列可以存储n-1个元素。
4．循环队列中，如果以head表示队首，tail表示下一个插入位置，则当前已有元素个数为(tail-head+n) mod n
队空:tail=head或(tail-head) mod n=0；队满: (tail-head+n) mod n=n-1或(tail+1)mod n=head
（三）栈
1．后进先出（LIFO），插入和删除都在同一端（栈顶）进行
2．用于:语法检查、计算表达式的值、实现递归过程、函数调用、深度优先遍历(如二叉树中序、前序、后序遍历)
A
B
C
D
H
I
J
M
G
E
F
K
L
十四．树
（一）树
1．结点的度:结点拥有的子树数;
2．树的度(Degree):树内各结点的度的最大值;
3．叶子(Leaf)结点/终端结点:度为0的结点;
4．内部结点/非终端结点/分支结点:度不为0的非根结点;
5．结点的层次:一般根为第1层;孩子结点的层次为双亲结点的层次+1;
也有把根定为第0层的,请看题意。
6．树的深度/高度(Depth):树中结点的最大层次;
7．树有结点数为n，则边数B=n-1
8．一棵m度的树，度为k的结点有nk个，则叶子结点数n0=1+n2+2n3+…+(m-1)nm
9．树的深度优先遍历:遍历根A,深度优先遍历A的第1棵子树, 深度优先遍历A的第2棵子树,…, 深度优先遍历A的最后1棵子树。上图深度优先遍历得ABEKLFCGDHMIJ
10．树的宽度优先遍历:相当于层次遍历,可以借助队列实现。上图宽度优先遍历得ABCDEFGHIJKLM
（二）二叉树
1．二叉树严格区分左子树和右子树
2．满二叉树:每层都充满的二叉树,h层满二叉树有2h-1个结点
3．完全二叉树:最后一层所有结点均尽量向左靠,其它层全部充满。
（1）h层的完全二叉树，结点数在2h-1和2h-1之间。
（2）通过层次遍历顺序（或叫宽度优先遍历），使用数组a存储完全二叉树，则a[k]的左子女为a[2k],右子女为a[2k+1],a[k]的双亲为a[k div 2]。
4．平衡二叉树:任意点的左子树和右子树的高度差不超过1（小于等于1）。
5．哈夫曼树:
（1）结点的带权路径长度:树根到结点的路径长度与结点上权的乘积叫该结点的带权路径长度;
（2）树的带权路径长度:树中所有叶子结点的带权路径长度之和;
（3）哈夫曼树:带权路径长度最小的树称做最优二叉树或哈夫曼树.
（4）构造哈夫曼树
a. 根据给定的n个权值w1,w2,…,wn,构成n棵二叉树的集合F={T1,T2,…,Tn},
其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均为空。
7
2
4
6
5
11
18
b．在F中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。
c．在F中删除这两棵已用过的子树，并将新得到的树加入F中。
d．重复b、c，直至F中只有一棵树止，此时得到的树就是哈夫曼树。
（5）哈夫曼树没有度为1的结点（又称为严格二叉树或正则二叉树）
（6）有n个叶子结点的哈夫曼树中共有2n-1个结点
一颗哈夫曼树
6．二叉树的遍历:除了深度优先和宽度优先遍历外，还有前序、后序和中序。
（1）前序:遍历根,前序遍历左子树,前序遍历右子树;
（2）后序:后序遍历左子树,后序遍历右子树,遍历根;
（3）中序:中序遍历左子树,遍历根,中序遍历右子树;
（4）已知前序和中序，或者已知后序和中序，可以唯一确定一棵二叉树，从而得到第三种遍历顺序
已知前序和后序，不能唯一确定一棵二叉树。
7．堆:（1）最小堆的定义:首先是一棵完全二叉树;其次每个结点均不大于（小于等于）它的子女。
（2）堆的存储:层次遍历存储至数组中。
8．二叉查找树:对于所有的点，均满足：左子树中所有点值≤根的值≤右子树中所有点的值
在以T为根的树中查找值d
p←T;
while p非空 do
if d=p处值 then
break//找到了退出循环
else if d<p处值 then p←p的左子女
else p←p的右子女;
if p非空 then 找到结点p
else 没有找到
中序遍历二叉查找树，得到所有点的升序排列。
在以T为根的树中插入值d
p←T;
while p非空 do begin
q←p;//保存父结点
if d<p处值 then p←p的左子女
else p←p的右子女
end;
产生新结点,值为d,父结点为q
二叉查找树中插入和查找
的原理：如果值比根小，转向
左子树，否则转化右子树！
如果二叉查找树是平衡的, 每
次插入和查找时间为logn, n个点
共O(nlogn)。最坏情况下,所有点
成一条线状,共需比较O(n2)次。
十五．图
（一）图的表示
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)条边。
A
B
C
D
A
A
3．生成树:
B
D
A
C
从A点出发的两棵深度优先生成树
C
B
D
A
C
C
B

B

D
D

原始图
从A点出发的两棵宽度优先生成树