1. 初二微机考试题
一、选择题
1． 中国的第一枚高性能通用CPU芯片是（ ）。
A 至强 B 毒龙 C 龙芯 D 龙珠
2． 计算机最主要的工作特点是（ ）。
A存储程序与自动控制 B高速度与高精度 C可靠性与可用性 D有记忆能力
3． 在微机中，用来表示信息的最小单位是（ ）。
A位 B 字节 C 字 D 双字
4． 下列操作中能在各种中文输入法之间切换的是（ ）。
A Ctrl＋Space B Ctrl＋Shift C Alt + Space D Alt + Enter
5． 在网络的各个节点上,为了顺利实现OSI模型中同一层次的功能,必须共同遵守的规则,叫做（ ）。
A TCP/IP B 协议 C INTERNET D 以太
6． Word具有分栏功能，下列关于分栏的说法中正确的是（ ）。
A各栏不同的间距是固定的 B 最多可以设4栏
C各栏的宽度必须相同 D 各栏的宽度可以不同
7． 在微型计算机内存储器中，不能用指令修改其存储内容的部分是（ ）。
A RAM B DRAM C ROM D SRAM
8． 排序的方法有许多种,_______法从未排序列中依次取出元素,与已排序列(初始时为空) 中的元素作比较,将其放入已排序列的正确位置上
A快速排序 B 插入排序 C 冒泡排序 D 选择排序
9． 在计算机领域中通常用MIPS来描述（ ）。
A 计算机的运算速度 B 计算机的可靠性 C 计算机的可运行性 D 计算机的可扩充性
10． I/O接口位于（ ）
A 总线和I/O设备之间 B CPU和I/O设备之间 C 主机和总线之间 D CPU和主存储器之间
11． 下列四条关于计算机基础知识的叙述中，正确的一条是（ ）。
A微型计算机是指体积微小的计算机
B 存储器必须在电源电压正常时才能存取信息
C 字长32位的计算机是指能计算最大为32位十制数的计算机
D 防止软盘感染计算机病毒的方法是定期对软盘格式化
12． 微型计算机的CPU与（）构成主机．
A控制器 B 输入输出设备 C 运算器 D 内存储器
13． 在计算机应用中，“计算机辅助设计”的英文缩写为（ ）。
A. CAD B. CAM C. CAE D. CAT
14． 在Windows的画图程序中，用鼠标右键作一长方形，则下列说法中下确的是（ ）。
A 以前景色作边框，以背景色填充
B 以前景色作边框，以前景填充
C 以背景色作边框，以前景色填充
D 以背景色作边框，以背景填充
15． 程序的三种基本控制结构是 。
A FOR、WHILE、REPEAT B 顺序、循环、选择
C FOR、WHILE、TF…THEN D 赋值、数组、文件
16． 在下列几种存储器中,访问速度最快的是( )。
A 硬盘存储器 B Cache C 光盘存储器 D 内存储器
17． 设栈S的初始状态为空,现对序列{1,2,3,4,5}在栈S上,依次进行如下操作(从元素1开始,出栈后不再进栈):进栈,出栈,进栈,进栈,出栈,出栈。试问出栈的元素序列是( )。
A {1,2,3} B {1,3,2} C {3,2,1} D {2,3,1}
18． 一般来说16位二进制数能表示非负整数的范围是（ ）。
A 0---2的16次方 B 0---16的平方-1 C 0---16的平方 D 0--2的16次方-1
19． 下列四个不同进制表示的数中，最大的是（）．
A 1011001（2） B 132（8） C 92（10） D 5B（16）
20． 下面哪家公司（单位）可以称为ICP？
A 中国铁通
B CNNIC
C 网易
D 英特尔
Answer
1
2
3
4
5
6
7
8
9
C
A
A
B
B
D
C
B
A
A
10
11
12
13
14
15
16
17
18
19
20
B
D
A
C
B
B
B
D
C
C
以上为一些简单的初中题，下面是和高中有关的题，因为我是搞微机竞赛的...
第一部分 高中计算机基础题
高中计算机自测题（一）
单项选择题
1、1MB等于（ ）
A、1000字节 B、1024字节
C、1000×1000字节 D、1024×1024字节
2、一个完整的计算机系统包括（ ）
A、计算机及其外部设备
B、主机、键盘、显示器
C、系统软件与应用软件
D、硬件系统与软件系统
3、计算机的软件系统包括（ ）
A、程序与数据 B、系统软件与应用软件
C、操作系统与语言处理程序
D、程序、数据与文档
4、以下哪种方式属于微机的冷启动方式？（ ）
A、按CTRL+ALT+DEL键 B、按CTRL+BREAK键
C、按RESET键 D、打开电源开关启动
5、在PC机中，80386、80486，PENTIUM（奔腾）等是指（ ）
A、生产厂家名称 B、硬盘的型号
C、CPU的型号 D、显示器的型号
6、某计算机的型号为486/33，其中33的含义是（ ）
A、CPU的序号 B、内存的容量
C、CPU的速率 D、时钟频率
7、下列关于操作系统的叙述中，正确的是（ ）A、操作系统是软件和硬件之间的接口
B、操作系统是源程序和目标程序之间的接口
C、操作系统是用户和计算机之间的接口
D、操作系统是外设和主机之间的接口
8、操作系统的作用是（ ）
A、把源程序译成目标程序
B、便于进行数据管理
C、控制和管理系统资源
D、实现硬件之间的连接
9、WPS是一种集编辑与打印为一体的（ ）
A、工具软件 B、字处理软件
C、管理软件 D、系统软件
10、在DOS提示符下不能执行的是以（ ）为扩展名的文件。
A、BAT B、、BAK C、EXE D、COM
11、检查磁盘剩余空间可用命令：（ ）
A、TIME B、COPY C、DIR D、REN
12、下列命令中MD、CD、RD、DIR有（ ）个是有关目录操作的命令：（ ）
A、1 B、2 C、3 D、4
13、在DOS提示符下，列出当前目录中所有第二、第三字符为DS的文件名清单，应使用的命令：（ ）
A、DIR DS*.* B、DIR ?DS*.*
C、DIR ?DS*.* D、DIR ?DS?.*
14、下列关于DEL命令的四条叙述中正确的是（ ）
A、一次只能删除一个文件
B、一次可以删除一个或多个文件
C、可以删除隐含文件 D、可以删除只读文件
15、一张5.25英寸软盘片的外套上标有“DS，HD”，则该软盘的容量为（ ）
A、360KB B、720KB C、1.2MB D、1.44MB
16、断电时计算机（ ）中的信息会丢失。
A、软盘 B、硬盘 C、RAM D、ROM
17、下列各无符号十进制整数中，能用八位进制表示的是（ ）
A、296 B、333 C、256 D、199
18、进入WPS对一个原有的文件MINE.WPS进行编辑，一直没有存盘操作，突然机器断电则（ ）
A、MINE.WPS文件的内容（原有的和刚编辑的）全部丢失 B、原有的MINE.WPS文件内容仍保留，刚编辑的内容全部丢失 C、原有的MINE.WPS文件内容保留在MINE.BAK文件中，刚编辑的内容丢失 D、原有的文件保留在MINE.BAK文件中，刚编辑的内容保留在MINE.WPS文件中
19、计算机病毒是指（ ）
A、能传染给用户的磁盘病毒 B、已感染病毒的磁盘 C、具有破坏性的特制程序 D、已感染病毒的程序
20、（ ）是计算机感染病毒的途径。
A、从键盘输入命令 B、运行外来程序
C、软盘已发霉 D、将内存数据拷贝到磁盘
21、对计算机软件正确的认识应该是（ ）
A、计算机软件受法律保护是多余的
B、正版软件太贵，软件能复制不必购买
C、受法律保护的计算机软件不能随便复制
D、正版软件只要能解密就能用
答案：1、D 2、D 3、B 4、D 5、C 6、D
7、C 8、C 9、B 10、B 11、C 12、D
13、B 14、B 15、B 16、C 17、D 18、B
19、C 20、B 21、C
（注：本试题原载于《学生计算机世界》报1998年3月9日第9期）
高中计算机自测题（二）
单项选择题
1、计算机的两大任务是（ ）
A、表示数据和输出数据 B、输入数据和输出数据 C、搜集数据和处理数据 D、表示数据和处理数据
2、流程图是描述（ ）的常用工具。
A、程序 B、算法 C、数据结构 D、计算规则
3、把计算机语言程序转换为机器代码，必须由（ ）来完成。
A、编译程序 B、解释程序
C、操作系统 D、应用软件
4、计算机科学常用（ ）表达方式来表示极其复杂的数据对象。
A、数据分类 B、关系类型
C、逻辑类型 D、分层次
5、数据和程序是以（ ）形式存储在磁盘上的。
A、集合 B、文件 C、目录 D、记录
6、在树型目录中，确定一个文件或子目录时，要指明相应的（ ）
A、路径 B、目录名 C、文件名 D、根目录
7、对文件的存取方式主要有（ ）
A、顺序和随机 B、索引和随机
C、顺序和索引 D、随机和读写
8、数据库的数据模型应用最广泛的是（ ）
A、层次模型 B、网络模型
C、关系模型 D、对象模型
9、（ ）是CPU能同时处理的二进制位数，位数越多，表明CPU处理的功能越强。
A、字 B、字节 C、字长 D、字段
10、486DX/33比86SL/25的功能要（ ），速度要（ ）
A、强、慢 B、强，快 C、差、慢D、差、快
11、显示器通过（ ）与主机板连接。
A、功能卡 B、打印卡 C、解压卡 D、适配卡
12、Cache的存取速度比主存储器速度（ ）
A、快 B、慢 C、稍慢 D、稍快
13、以下是软盘使用的情况，错误的说法是（ ）
A、不要触摸读写孔等裸露部分
B、驱动器指示灯灭时，可取出磁盘
C、封上写保护口，可保护软盘免受破坏
D、在电视机、稳压器等附近可放置磁盘
14、各种应用软件都必须在（ ）的支持下运动。
A、编程程序 B、计算机语言程序
C、字处理程序 D、操作系统
15、（ ）是指计算机对特定的输入结果，能在规定的时间内处理完毕，并作出反应。
A、单道批处理系统 B、多道批处理系统
C、分时系统 D、实时系统
16、DOS的功能就是管理（ ）
A、设备与文件 B、数据与通信
C、软件资源 D、硬件资源
17、VESA是PC机的（ ）
A、显示卡类型 B、功能卡类型
C、总线类型 D、声卡类型
18、对插入B驱动器（5.25英寸高密）中的360KB软盘进行格式化工作，相应的操作命令是（ ）
A、FORMAT B: B、FORMAT B:/S
C、FORMAT B:/V D、FORMAT B:/4
答案：
1、D 2、B 3、A 4、D 5、B 6、A 7、A
8、C 9、C 10、B 11、D 12、A 13、D
14、D 15、D 16、A 17、C 18、D
（注：本试题原载于《学生计算机世界》报1998年3月16日第10期）
高中计算机自测题（三）
单项选择题
1、将C盘子目录WPS下的文件目录从打印机上输出。命令为（ ）
A、C:\>DIR C:\WPS<回车>
B、C:\>DIR C:\WPS>DATA.DAT<回车>
C、C:\>DIR C:\WPS>CON<回车>
D、C:\>DIR C:\WPS>PRN<回车>
2、下列命令中，DATE、FORMAT、CHKDSK、DEL、REN中，属于内部命令的有（ ）
A、1 B、2 C、3 D、4
3、命令PATH C:\DOS有何作用（ ）
A、标记C盘DOS子目录
B、将C盘DOS子目录置为当前目录
C、指明C:\DOS为当前路径
D、搜寻C盘DOS子目录下的可执行文件
4、若PROMPT命令后没有参数，它的功能是（ ）
A、显示当前路径 B、显示根目录
C、显示当前目录 D、显示DOS提示符
5、若在启动操作系统，屏幕上出现如下提示：BAD OR MISSING COMMAND INTERPRETER。正确的解决方法是（ ）
A、取出启动盘，重新再试一次
B、重新安装DOS系统
C、将系统盘重新格式化
D、更新DOS系统盘
6、执行DOS命令后，下列说法中正确的是（ ）
A、一定列出根目录中的文件
B、一定列出当前当前目录下的文件清单
C、列出的不是根目录下的文件清单
D、一定列出子目录下的文件清单
7、使用DOS命令REN对文件进行改名操作时，正确的命令是（ ）
A、REN ABC.* ABC.* B、REN A:ABC.* B:*.*
C、REN ABC.* BAC.* D、REN A:ABC.* A:ABC.*
8、内存储器RAM中的信息是（ ）
A、生产厂家预先写入的
B、计算机工作时随机写入的
C、在计算机掉电时，其中的信息也不会丢失
D、任何时间，其中存放的信息都是一样的
9、用COPY命令创建文件时（ ）
A、只能创建批处理文件（扩展名为.BAT）
B、只能创建系统文件（扩展名为.SYS）
C、只能创建文本文件（扩展名为.TXT）
D、可创建以ASCⅡ码或汉字代码为内容的文件
10、批处理文件是（ ）
A、几条DOS命令存放在一个文件中
B、任何命令存放在一个文件中
C、不要存放任何命令的文件
D、若干个DOS命令及有关信息组合成一个以.BAT为扩展的文件
11、某用户在C驱动器下，想用DEL命令删除A盘上所有文件，他键入命令
C:\A:
C:\>del *.*
Are you sure(Y/N)?Y
用户将会（ ）
A、将A盘上所有文件都删去
B、将A盘根目录下的所有文件都删去
C、将C盘上所有文件都删去
D、将C盘根目录下的所有文件都删去
12、EDI意为电子数据交换，应用于（ ）
A、通信 B、邮电 C、交通 D、商业
答案：
1、D 2、D 3、D 4、B 5、D 6、B 7、C 8、B 9、D 10、D 11、D 12、D
（注：本试题原载于《学生计算机世界》报1998年3月23日第11期）
高中计算机自测题（四）
多项选择题
1、文件的基本操作有（ ）
A、读操作 B、写操作
C、重写操作 D、删除操作
2、程序的基本控制结构有（ ）
A、顺序结构 B、分支结构
C、重复结构 D、数据结构
3、下列哪些情况属于计算机犯罪现象？（ ）
A、破坏计算机系统程序或数据 B、由于操作错误造成信息资源的丢失 C、窃取计算机信息资源 D、盗用计算机机时
4、计算机病毒都具有的共同特点是（ ）
A、破坏性 B、复制性 C、感染性 D、隐藏性
5、预防计算机病毒的主要做法有（ ）
A、不使用外来软件 B、定期进行病毒检查
C、复制数据文件副本 D、当病毒侵害计算机系统时，应停止使用，须进行清除病毒
6、显示器的技术标准有（ ）
A、分辨率 B、点锐度
C、隔行/逐行扫描 D、颜色明亮
7、PC机的基本输入设备有（ ）
A、鼠标器 B、显示器 C、软盘 D、键盘
8、按计算机系统的结构模式，可分为（ ）
A、集中式系统 B、网络系统
C、分散式系统 D、互连系统
9、计算机网络，其重要作用为（ ）
A、实现计算机系统之间的通信互连
B、实现资源共享 C、实现计算机之间的连接
D、使网上的计算机成为工作站
10、PC DOS的隐含系统文件是（ ）模块组成。
A、IBMIO.SYS B、IBMDOS.COM C.BOOT
D.COMMAND.COM
11、启动计算机的“热启动”的方式是指（ ）
A、开机状态下，按CTRL+ALT+DEL键
B、开机状态下，按RESET键
C、打开显示电源，再开主机电源
D、先关主机电源，后关显示器电源
12、在MSDOS的根目录中，有如下文件：TIME.TXT、TIME.COM、TIME.BAT，则C:\TIME<回车>执行的是（ ）
A、TIME.EXE B、TIME.COM
C、TIME.BAT D、内部命令
13、（ ）是不能完成预期目标的。
A、DISKCOPY A: A: B、COPY A:X1.TXT A:C.REN
C、REN A:X1.TXT C:X1.TXT D、FORMAT A:/S
14、WINDOWS的主要特点是（ ）
A、具有全新的图形界面 B、功能强大的应用程序 C、强大的并行处理能力 D、强大的串行处理能力
15、下列程序项，（ ）属于程序管理器中的“附件”程序组。
A、记事本 B、日历 C、游戏 D、文件管理
16、下列软件中，（ ）是文字处理类软件。
A、WPS B、CCED C、WORDSTAR D、WORD
17、（ ）是计算机病毒感染的途径。
A、软盘表面不清洁 B、运行外来软件
C、使用盗版软件 D、在网上下载软件
18、在输入DOS命令时，各成分之间要用（ ）键分隔，命令的最后以（ ）结尾。
A、换档键 B、空格键 C、回车键 D、控制键
19、在以下（ ）情况下，系统将有如下显示：C:\>DIR A:General failure error reading drive A: abort,Retry,fail?
A、软盘和驱动器类型不匹配 B、软盘未经格式化 C、软盘中的软件中只能使用不能读出（因加密等技术） D、驱动器中没有放入软盘
答案：
1、ABCD 2、ABC 3、ACD 4、ACD 5、BCD
6、ABC 7、AD 8、AB 9、AB 10、ABC
11、AB 12、D 13、BC 14、ABC 15、AB 16、ABCD 17、BCD 18、B，C 19、ABCD
（注：本试题原载于《学生计算机世界》报1998年3月30日第12期）
第二部分 高中计算机基础综合题
高中计算机综合题（一）
单项选择题
1、电子计算机最重要的特征是（ ）
A、高速度 B、高精度
C、记忆力强 D、存储程序自动控制
2、你认为，以下说法中最能准确反映计算机主要功能的是（ ）
A、计算机可以高速度运算 B、计算机能代替人的脑力劳动C、计算机可以存储大量信息 D、计算机是一种信息处理机
3、计算机之所以称为“电脑”，是因为（ ）
A、计算机是人类大脑功能的延伸 B、计算机具有逻辑判断功能C、计算机有强大的记忆能力 D、计算机有自我控制功能
4、在计算机行业中，MIS是指（ ）
A、管理信息系统 B、数学教学系统
C、多指令系统 D、查询信息系统
5、CAI是指（ ）
A、系统软件 B、计算机辅助教学软件C、计算机辅助管理软件 D、计算机辅助设计软件
6、所谓媒体是指（ ）
A、表示和传播信息的载体 B、字处理软件
C、计算机输入与输出信息 D、计算机屏幕显示的信息
7、多媒体计算机是指（ ）
A、具有多种功能的计算机 B、具有多种外设的计算机 C、能处理多种媒体的计算机 D、能借助多种媒体操作的计算机
8、计算机与计算器的最大区别是（ ）
A、计算机比计算器的运算速度快
B、计算机比计算器大 C、计算机比计算机贵
D、计算机能够存放并执行复杂的程序
9、目前计算机的应用领域可大致分为三个方面，指出下列答案中哪个正确。（ ）
A、计算机辅助教学 专家系统 人工智能
B、数值处理 人工智能 操作系统
C、实时控制 科学计算 数据处理
D、工程计算 数据结构 文字处理
10、下列说法正确的是（ ）
A、在微机性能中，CPU的主频越高，其运算速度越快 B、存储器具有记忆能力，其中的信息任何时候都不会丢失 C、点阵打印机的针数越多，则能打印的汉字字体就越多 D、两个显示器屏幕尺寸相同，则它们的分辨率必定相同
11、既是输入设备又是输出设备的是（ ）
A、磁盘驱动器 B、显示器 C、键盘 D、鼠标器
12、当运行某个程序时，发现存储容量不够。解决的办法是（ ）
A、把磁盘换成光盘 B、把软盘换成硬盘
C、使用高容量磁盘 D、扩充内存
13、JAVA是一种新的（ ）
A、编程语言 B、数据库 C、应用程序
D、信息管理系统
14、计算机网络最突出的优点是（ ）
A、传送信息速度高 B、共享资源
C、内存容量大 D、交互性好
15、信息高速公路传送的是（ ）
A、二进制数据 B、多媒体信息
C、程序数据 D、各种数字信息
16、以下列举INTERNET的各种功能中，错误的是（ ）
A、编译程序 B、传送电子邮件
C、查询信息 D、数据库检索
答案:
1、D 2、D 3、A 4、A 5、B 6、A 7、D 8、D 9、C 10、A 11、A 12、D 13、A 14、B 15、B 16、A
（注：本试题原载于《学生计算机世界》报1998年6月8日第22期，发表时有删节。）
一、单项选择题
1、与二进制数101101.11等值的十进制数是（ ）
A、 2D/B B、 2D.C C、 2B.C D、 2B.B
2、已知在某位进制计数下，2＊4＝11，根据这个运算规则，5＊16的结果是（ ）
A、80 B、61 C、122 D、212
3、将十进制数0.7309375转换成二进制数（ ）
A、0.1011001 B、0.100111 C、0.1011101 D、0.1010011
4、在计算机内部，一切信息的存取、处理和传送的形式是（ ）
A、ASCII码 B、BCD码 C、二进制
D、十六进制
5、如果按字长来分的话，个人计算机可分为8位机、16位机、32位机和64位机。所谓32位机是指该计算机（ ）
A、CPU同时能处理32位二进制数
B、只能处理32位二进制浮点数
C、具有32位的寄存器 D、有32个寄存器
6、以下哪两个软件是系统软件？（ ）
A、WPS和XENIX B、DOS和MIS
C、DOS和XENIX D、XENIX和MIS
7、内存地址的最重要特点是（ ）
A、唯一性 B、随机性 C、顺序性 D、连续性
8、计算机的运算速度可以用MIPS来描述，它的含义是（ ）
A、每秒执行百万条指令 B、每秒处理百万个字符 B、每秒执行千万条指令 D、每秒处理百千个字符
9、直接通过总线与CPU连接的部件是（ ）
A、显示器 B、内存储器 C、磁盘驱动器
D、键盘
10、下列存储器中，存取速度最快的是（ ）
A、软盘 B、硬盘 C、光盘 D、内存
11、24针打印机的分辨率约180dpi。dpi数越大，打印精度越高。其中单位dpi是指（ ）
A、印点／英寸 B、印点／厘米
C、印点／毫米 D、印点／寸
12、DOS能直接管理的640K RAM叫做[1]，把在640K至1024K之间的384K RAM叫做[2] ， 把1024K以上的叫做[3]，[2][3]不能为DOS直接利用，必须在5.0以上版本的DOS 系统并运行适当软件才能使用。（ ）
A、扩展内存（XMS） B、上位内存（UMB）
C、基本内存（Base Memory）
D、常规内存（IMB）
13、计算机病毒发作一般包括这样几个环节，即初始引导、触发、传播和破坏。其中初始引导部完成病毒的[1][2]工作；触发部分由一些触发条件构成，一旦触发条件成熟，病毒就开始作用，即[2]；传染部分主要是将病毒[4]，传染到健康的文件上；破坏部分是[5] 的具体表现。[1][2][3][4][5]的选择分别是（ ）
A、病毒 B、自我复制 C、传染和破坏
D、初始化参数 E、装入内存
14、文件型病毒传染的主要对象是（ ）
A、文本文件 B、系统文件
C、可执行文件 D、.EXE和.COM文件
二、多项选择题
15、电子计算机有三种接口可与其它外设连接，它们是：串行口（COM1）、并行口（COM2、LPT）和游戏杆接口（GAME）。串行口和并行口的区别在于（ ）
A、在传送信息时，串行口每步动作只传送1个Bit（即一位一位地传送） B、并行口每步动作则同时传送8个Bit（即一个字节一个字节地传送） C、串行口而传送信息速度慢，但传送的距离较远 D、并行口传送信息速度快，但传送的距离一般只有几十厘米
16、下列设备文件名中，（ ）既可作为输入设备，也可作为输出设备。
A、CON B、PRN C、NUL D、LPT2
E、AUX F、COM2
答案：
一、单项选择题：1、B 2、C 3、B 4、C 5、A 6、C 7、A 8、A 9、B 10、D
11、A 12、[1]C [2]B [3]A
13、[1]E [2]D [3]C [4]B [5]A 14、D
二、多项选择题：15、ABCD 16、ACEF
2. 计算机网络自学笔记：选路算法
网络层必须确定从发送方到接收方分组所经过的路径。选路就是在网络中的路由瞎物器里的给某个数据报确定好路径(即路由)。
一 台主机通常直接与一台路由器相连接，该路由器即为该主机的默认路由器，又称为该主机的默认网关。 每当某主机向外部网络发送一个分组时，该分组都被传送给它的默认网关。
如果将源主机的默认网关称为源路由器,把目的主机的默认网关称为目的路由器。为一个分组从源主机到目的主机选路的问题于 是可归结为从源路由器到目的路由器的选路问题。
选路算法的目标很简单:给定一组路由器以及连接路由器的链路，选路算法要找到一条从源路由器到目的路由器的最好路径，通常一条好路径是指具有最低费用的路径。
图 G=(N，E)是一个 N 个节点和 E 条边的集合，其中每条边是来自 N 的一对节点。在网 络选路的环境中，节点表示路由器，这是做出分组转发决定的节点，连接节点的边表示路由 器之间的物理链路。
一条边有一个值表示它的费用。通常一条边的费用可反映出对应链路的物理长度、链路速度或与该链路相关的费用。
对于 E 中的任一条边(xy)可以用 c(xy )表示节点 x 和 y 间边的费用。一般考虑的都是无向 图，因此边(xy)与边(y x)是相同的并且开销相等。节点 y 也被称为节点 x 的邻居。
在图中为各条边指派了费用后，选路算法的目标自然是找出从源到目的间的最低费用路径。图 G=(N，E)中的一条路径(Path)是一个节点的序列，使得每一对以(x1,x2)， (x2,x3)，…，是 E 中的边。路径的费用是沿着路径所有边费用的总和。
从广义上来说，我们对 选路算法分类的一种方法就是根据该算法是全局性还是分布式来区分的。
.全局选路算法： 用完整的、全局性的网络信息来计算从源到目的之间的最低费用路径。
实际上， 具有全局状态信息裂歼的算法常被称作链路状态 LS 算法， 因为该算法必须知道网络中每条链路的费用。
.分布式选路算法： 以迭代的、分布式的方式计算出最低费用路径。通过迭代计算并与相邻节点交换信息，逐渐计算出到达某目的节点或一组目的节点的最低费用路径。
DV 算法是分布式选路算法， 因为每个节点维护到网络中的所有其他节点的费用(距离)估计的矢量。
选路算法的第二种广义分类方法是根据算法是静态的还是动态的来分类。
一： 链路状态选路算法 LS
在链路状态算法中，通过让每个节点向所有其他路由器广播链路状态分组， 每个链路状态分组包含它所连接的链路的特征和费用， 从而网络中每个节点都建立了关于整个网络的拓扑。
Dijkstra 算法计算从源节点到网络中所有其他节点的最低费用路径.
Dijkstra 算法是磨源液迭代算法，经算法的第 k 次迭代后，可知道到 k 个目的节点的最低费用路径。
定义下列记号:
D(V)随着算法进行本次迭代，从源节点到目的节点的最低费用路径的费用。
P(v)从源节点到目的节点 v 沿着当前最低费用路径的前一节点(，的邻居)。
N`节点子集；如果从源节点到目的节点 v 的最低费用路径已找到，那么 v 在 N`中。
Dijkstra 全局选路算法由一个初始化步骤和循环组成。循环执行的次数与网络中的节点个数相同。在结束时，算法会计算出从源节点 u 到网络中每个其他节点的最短路径。
考虑图中的网络，计算从 u 到所有可能目的地的最低费用路径。
.在初始化阶段 ，从 u 到与其直接相连的邻居 v、x、w 的当前已知最低费用路径分别初始化为 2，1 和 5。到 y 与 z 的费用被设为无穷大，因为它们不直接与 u 连接。
.在第一次迭代时， 需要检查那些还未加到集合 N`中的节点，找出在前一次迭代结束时具有最低费用的节点。那个节点是 x 其费用是 1，因此 x 被加到集合 N`中。然后更新所有节点的 D(v)，产生下表中第 2 行(步骤)所示的结果。到 v 的路径费用未变。经过节点 x 到 w 的 路径的费用被确定为 4。因此沿从 u 开始的最短路径到 w 的前一个节点被设为 x。类似地， 到 y 经过 x 的费用被计算为 2，且该表项也被更新。
.在第二次迭代时 ，节点 v 与 y 被发现具有最低费用路径 2。任意选择将 y 加到集合 N` 中，使得 N’中含有 u、x 和 y。通过更新，产生如表中第 3 行所示的结果。
.以此类推…
当 LS 算法结束时，对于每个节点都得到从源节点沿着它的最低费用路径的前继节点， 对于每个前继节点，又有它的前继节点，按照此方式可以构建从源节点到所有目的节点的完 整路径。
根据从 u 出发的最短路径，可以构建一个节点(如节点 u)的转发表。
二 距离矢量选路算法 DV
LS 算法是一种使用全局信息的算法，而距离矢量算法是一种迭代的、异步的和分布式的算法。
Bellman-Ford 方程：
设 dx(y)是从节点 x 到节点 y 的最低费用路径的费用，则有 dx(y) = min {c(x,v) + dv(y) }
PS： 方程中的 min，是指取遍 x 的所有邻居。
Bellman-Ford 方程含义相当直观，意思是从 x 节点出发到 y 的最低费用路径肯定经过 x 的某个邻居，而且 x 到这个邻居的费用加上这个邻居到达目的节点 y 费用之和在所有路径 中其总费用是最小的。 实际上，从 x 到 v 遍历之后，如果取从 v 到 y 的最低费用路径，该路 径费用将是 c(x,v)+ dv(y)。因此必须从遍历某些邻居 v 开始，从 x 到 y 的最低费用是对所有邻 居的 c(x,v)+dv(y)的最小值。
在该 DV 算法中，当节点 x 看到它的直接相连的链路费用变化，或从某个邻居接收到一 个距离矢量的更新时，就根据 Bellman-Ford 方程更新其距离矢量表。
三 LS 与 DV 选路算法的比较
DV 和 LS 算法采用不同的方法来解决计算选路问题。
在 DV 算法中，每个节点仅与它的直接相连邻居交换信息，但它为它的邻居提供了从其 自己到网络中(它所知道的)所有其他节点的最低费用估计。
在 LS 算法中，每个节点(经广播)与所有其他节点交换信息，但它仅告诉它们与它直接 相连链路的费用。
·报文复杂性：
LS 算法要求每个节点都知道网络中每条链路的费用，需要发送 O(nE)个消息。
DV 算法要求在每次迭代时，在两个直接相连邻居之间交换报文，算法收敛所需的时间 依赖于许多因素。当链路费用改变时，DV 算法仅当在会导致该节点的最低费用路径发生改 变时，才传播已改变的链路费用。
·收效速度：
DV算法收敛较慢，且在收敛时会遇到选路环路。DV算法还会遭受到计数到无穷的问题。
•健壮性： 在 LS 算法中，如果一台路由器发生故障、或受到破坏，路由器会向其连接的链路广播 不正确费用，导致整个网络的错误。
在 Dv 算法下， 每次迭代时，其中一个节点的计算结果会传递给它的邻居，然后在下次迭代时再间接地传递给邻居的邻居。在这种情况下，DV 算法中一个不正确的计算结果也会扩散到整个网络。
四.层次选路
两个原因导致层次的选路策略：
•规模： 随着路由器数目增长，选路信息的计算、存储及通信的开销逐渐增高。
•管理自治： 一般来说，一个单位都会要求按自己的意愿运行路由器(如运行其选择的某 种选路算法)，或对外部隐藏其内部网络的细节。
层次的选路策略是通过将路由器划分成自治系统 AS 来实施的。
每个 AS 由一组通常在相同管理控制下的路由器组成(例如由相同的 ISP 运营或属于相同 的公司网络)。在相同的 AS 内的路由器都全部运行同样的选路算法。
在一个自治系统内运行的选路算法叫做自治系统内部选路协议。 在一个 AS 边缘的一台 或多台路由器，来负责向本 AS 之外的目的地转发分组，这些路由器被称为网关路由器
在各 AS 之间，AS 运行相同的自治系统间选路协议。