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 運行相同的自治系統間選路協議。