北大計(jì)算機(jī)招簡三_跨考網(wǎng)

　　計(jì)算機(jī)網(wǎng)絡(luò)

　　【考查目標(biāo)】

　　1.掌握計(jì)算機(jī)網(wǎng)絡(luò)的基本概念、基本原理和基本方法。

　　2.掌握計(jì)算機(jī)網(wǎng)絡(luò)的體系結(jié)構(gòu)和典型網(wǎng)絡(luò)協(xié)議，了解典型網(wǎng)絡(luò)設(shè)備的組成和特點(diǎn)，理解典型網(wǎng)絡(luò)設(shè)備的工作原理

　　3.能夠運(yùn)用計(jì)算機(jī)網(wǎng)絡(luò)的基本概念、基本原理和基本方法進(jìn)行網(wǎng)絡(luò)系統(tǒng)的分析、設(shè)計(jì)和應(yīng)用

　　一、計(jì)算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu)

　?。ㄒ唬┯?jì)算機(jī)網(wǎng)絡(luò)概述

　　1.計(jì)算機(jī)網(wǎng)絡(luò)的概念、組成與功能

　　2.計(jì)算機(jī)網(wǎng)絡(luò)的分類

　　3.計(jì)算機(jī)網(wǎng)絡(luò)與互聯(lián)網(wǎng)的發(fā)展歷史

　　4.計(jì)算機(jī)網(wǎng)絡(luò)的標(biāo)準(zhǔn)化工作及相關(guān)組織

　　（二）計(jì)算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu)與參考模型

　　1.計(jì)算機(jī)網(wǎng)絡(luò)分層結(jié)構(gòu)

　　2.計(jì)算機(jī)網(wǎng)絡(luò)協(xié)議、接口、服務(wù)等概念

　　3.ISO/OSI參考模型和TCP/IP模型

　　二、物理層

　　（一）通信基礎(chǔ)

　　1.信道、信號、寬帶、碼元、波特、速率等基本概念

　　2.奈奎斯特定理與香農(nóng)定理

　　3.信源與信宿

　　4.編碼與調(diào)制

　　5.電路交換、報文交換與分組交換

　　6.數(shù)據(jù)報與虛電路

　　（二）傳輸介質(zhì)

　　1.雙絞線、同軸電纜、光纖與無線傳輸介質(zhì)

　　2.物理層接口的特性

　　（三）物理層設(shè)備

　　1.中繼器

　　2.集線器

　　三、數(shù)據(jù)鏈路層

　　（一）數(shù)據(jù)鏈路層的功能

　?。ǘ┙M幀

　　（三）差錯控制

　　1.檢錯編碼

　　2.糾錯編碼

　?。ㄋ模┝髁靠刂婆c可靠傳輸機(jī)制

　　1.流量控制、可靠傳輸與滑輪窗口機(jī)制

　　2.單幀滑動窗口與停止-等待協(xié)議

　　3.多幀滑動窗口與后退N幀協(xié)議（GBN）

　　4.多幀滑動窗口與選擇重傳協(xié)議（SR）

　?。ㄎ澹┙橘|(zhì)訪問控制

　　1.信道劃分介質(zhì)訪問控制

　　頻分多路復(fù)用、時分多路復(fù)用、波分多路復(fù)用、碼分多路復(fù)用的概念和基本原理。

　　2.隨即訪問介質(zhì)訪問控制

　　ALOHA協(xié)議；CSMA協(xié)議；CSMA/CD協(xié)議；CSMA/CA協(xié)議。

　　3.輪詢訪問介質(zhì)訪問控制：令牌傳遞協(xié)議

　?。┚钟蚓W(wǎng)

　　1.局域網(wǎng)的基本概念與體系結(jié)構(gòu)

　　2.以太網(wǎng)與IEEE802.3

　　3.IEEE802.11

　　4.令牌環(huán)網(wǎng)的基本原理

　?。ㄆ撸V域網(wǎng)

　　1.廣域網(wǎng)的基本概念

　　2.PPP協(xié)議

　　3.HDLC協(xié)議

　　4.ATM網(wǎng)絡(luò)基本原理

　?。ò耍?shù)據(jù)鏈路層設(shè)備

　　1.網(wǎng)橋

　　網(wǎng)橋的概念；透明網(wǎng)橋與生成樹算飯；源選徑網(wǎng)橋與源選徑算法。

　　2.局域網(wǎng)交換機(jī)及其工作原理。

　　四、網(wǎng)絡(luò)層

　?。ㄒ唬┚W(wǎng)絡(luò)層的功能

　　1.異構(gòu)網(wǎng)絡(luò)互聯(lián)

　　2.路由與轉(zhuǎn)發(fā)

　　3.擁塞控制

　　（二）路由算法

　　1.靜態(tài)路由與動態(tài)路由

　　2.距離-向量路由算法

　　3.鏈路狀態(tài)路由算法

　　4.層次路由

　?。ㄈ㊣Pv4

　　1.IPv4分組

　　2.IPv4地址與NAT

　　3.子網(wǎng)劃分與子網(wǎng)掩碼、CIDR

　　4.ARP協(xié)議、DHCP協(xié)議與ICMP協(xié)議

　?。ㄋ模㊣Pv6

　　1.IPv6的主要特點(diǎn)

　　2.IPv6地址

　?。ㄎ澹┞酚蓞f(xié)議

　　1.自治系統(tǒng)

　　2.域內(nèi)路由與域間路由

　　3.RIP路由協(xié)議

　　4.OSPF路由協(xié)議

　　5.BGP路由協(xié)議

　?。㊣P組播

　　1.組播的概念

　　2.IP組播地址

　　3.組播路由算法

　?。ㄆ撸┮苿覫P

　　1.移動IP的概念

　　2.移動IP的通信過程

　　（八）網(wǎng)絡(luò)層設(shè)備

　　1.路由器的組成和功能

　　2.路由表與路由轉(zhuǎn)發(fā)

　　五、傳輸層

　?。ㄒ唬﹤鬏攲犹峁┑姆?wù)

　　1.傳輸層的功能

　　2.傳輸層尋址與端口

　　3.無連接服務(wù)與面向連接服務(wù)

　　（二）UDP協(xié)議

　　1.UDP數(shù)據(jù)報

　　2.UDP校驗(yàn)

　?。ㄈ㏕CP協(xié)議

　　1.TCP段

　　2.TCP連接管理

　　3.TCP可靠傳輸

　　4.TCP流量控制與擁塞控制

　　六、應(yīng)用層

　?。ㄋ模┚W(wǎng)絡(luò)應(yīng)用模型

　　1.客戶/服務(wù)器模型

　　2.P2P模型

　?。ㄎ澹〥NS系統(tǒng)

　　1.層次域名空間

　　2.域名服務(wù)器

　　3.域名解析過程

　?。〧TP

　　1.FTP協(xié)議的工作原理

　　2.控制連接與數(shù)據(jù)連接

　　（七）電子郵件

　　1.電子郵件系統(tǒng)的組成結(jié)構(gòu)

　　2.電子郵件格式與MIME

　　3.SMTP協(xié)議與POP3協(xié)議

　?。ò耍￤WW

　　1.WWW的概念與組成結(jié)構(gòu)

　　2.HTTP協(xié)議

　?、簟Ｔ囶}示例

　　一、單項(xiàng)選擇題：1～40小題，每小題2分，共80分。在每小題給出的四個選項(xiàng)中，請選出一項(xiàng)最符合題目要求的。

　　1.下列排序算法中，時間復(fù)雜度為0（nlog：n）且占用額外空間最少的是

　　A.堆排序 B.起泡排序

　　C.快速排序 D.希爾排序

　　2.下列序列中，滿足堆定義的是

　　A.（100，86，48，73，35，39，42，57，66，21）

　　B.（12，70，33，65，24，56，48，92，86，33）

　　C.（103，97，56，38，66，23，42，12，30，52，6，26）

　　D.（5，56，20，23，40，38，29，6l，35，76，28，100）

　　3.程序計(jì)數(shù)器Pc用來存放指令地址，其位數(shù)和下列哪個寄存器相同？

　　A.指令寄存器IR B.主存數(shù)據(jù)寄存器MDR

　　C.程序狀態(tài)字寄存器PSWR D.主存地址寄存器MAR

　　4.假定一個十進(jìn)制數(shù)為一66，按補(bǔ)碼形式存放在一個8位寄存器中，該寄存器的內(nèi)容用十六進(jìn)制表示為

　　A.C2H B.BEH C.BDH D.42H

　　5.下列進(jìn)程狀態(tài)轉(zhuǎn)換中，不可能發(fā)生的轉(zhuǎn)換是

　　A.運(yùn)行一就緒 B.運(yùn)行一等待

　　C.等待一運(yùn)行 D.等待_÷就緒

　　6.設(shè)某系統(tǒng)中有3個并發(fā)進(jìn)程都需要4個同類資源，該系統(tǒng)不會發(fā)生死鎖的最少資源數(shù)是

　　A.9 B.10 C.1 D 12

　　7.根據(jù)csMA／cD協(xié)議的工作原理，下列情形中需要提高最短幀長度的是

　　A.網(wǎng)絡(luò)傳輸速率不變，沖突域的最大距離變短

　　B.沖突域的最大距離不變，網(wǎng)絡(luò)傳輸速率提高

　　c.上層協(xié)議使用TcP的概率增加

　　D.在沖突域不變的情況下減少線路中的中繼器數(shù)量

　　8.在選擇重傳協(xié)議（sR）中，當(dāng)幀的序號字段為3比特，且接收窗口與發(fā)送窗口尺寸相同時，發(fā)送窗口的最大尺寸為

　　A.2 B.4 C. 6 D. 8

　　二、綜合應(yīng)用題：41～47小題，共70分。

　　試題示例

　　41.（10分）設(shè)無向圖G=（y，E），其中y={l，2，3，4，5}，E= {（1，2，4），（2，5，5），（1，3，2），（2，4，4），（3，4，1），（4，5，3）， （1，5，8）}，每條邊由一個三元組表示，三元組中前兩個元素為與該邊關(guān)聯(lián)的頂點(diǎn)，第三個元素為該邊的權(quán)。請寫出圖G中從頂點(diǎn)1到其余各點(diǎn)的最短路徑的求解過程。要求列出最 短路徑上的各頂點(diǎn)，并計(jì)算路徑長度。

　　42.（15分）已知一棵二叉樹采用二叉鏈表存儲，結(jié)點(diǎn)構(gòu)造為：

　　lLeft（：h訂d i Data}Right（：hildI，root指向根結(jié)點(diǎn)。現(xiàn)定義二叉樹中結(jié)點(diǎn)x。的根路徑為從根結(jié)點(diǎn)到x。結(jié)點(diǎn)的一條路徑，請編寫算法輸出該二叉樹中最長的根路徑（多條最長根路徑中只輸出一條即可。算法可使用c或c++或JAVA語言實(shí)現(xiàn)）。

　　43.（11分）某計(jì)算機(jī)的主存地址位數(shù)為32位，按字節(jié)編址。假定數(shù)據(jù)（~ache中最多存放128個主存塊，采用4路組相聯(lián)方式，塊大小為64 Byte，每塊設(shè)置了l位有效位。采用一次性寫回（write Back）策略，為此每塊設(shè)置了1位“臟（Diny）”位。

　　要求：

　?。?）分別指出主存地址中標(biāo)記（Tag）、組號（Inclex）和塊內(nèi)地址（c）ffset）三部分的位置和位數(shù)。

　　（2）計(jì)算該數(shù)據(jù)cache的總位數(shù)（請給出詳細(xì)計(jì)算過程）。

　　44.（10分）下圖是一個簡化的CPu與主存連接結(jié)構(gòu)示意圖（圖中省略了所有多路選擇器）。其中有一個累加寄存器Ac、一個狀態(tài)寄存器和其他四個寄存器：主存地址寄存器MAR、 主存數(shù)據(jù)寄存器MDR、程序計(jì)數(shù)器Pc和指令寄存器IR，各部件及其之間的連線表示數(shù)據(jù)通路，箭頭表示信息傳送方向。

　　一個簡化的cPU與主存連接結(jié)構(gòu)示意圖要求：

　　（1）請寫出圖中a、b、c、d四個寄存器的名稱。

　　（2）簡述圖中指令從主存取到控制器的過程。

　　（3）說明數(shù)據(jù)從主存取出、運(yùn)算、寫回主存所經(jīng)過的數(shù)據(jù)通路（假定數(shù)據(jù)地址已在MAR中）。

　　45.（6分）設(shè)頁引用序列：，（1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6），物理塊（Page frame）數(shù)為3，且所有的塊初始時為空。當(dāng)分別采用最近最少使用置換（LRu）、先進(jìn)先出置換（FIFO）和最佳置換（0PT）的頁面置換算法時，各會發(fā)生多少次缺頁？要求給出求解過程。

　　46.（9分）理發(fā)師問題描述如下：理發(fā)店包含一間接待室和一間工作室，接待室內(nèi)有n（n≥1）把椅子，而工作室只有l(wèi)把椅子。如果沒有顧客，理發(fā)師就去睡覺；如果顧客來時所有的椅子都有人，那么顧客離去；如果理發(fā)師在忙且接待室有空閑的椅子，那么此顧客會坐在其中1把空閑的椅子上等待；如果理發(fā)師在睡覺，則顧客會喚醒他。請采用信號量機(jī)制解決該理發(fā)師問題（可用偽代碼描述）。

　　47.（9分）考慮某路由器具有下列路由表項(xiàng)：

　　網(wǎng)絡(luò)前綴 下一跳

　　142.150.64.O／24 A

　　142.150.71.128／28B

　　142.150.71.128／30C

　　142.150.0.0／16 D

　　（1）假設(shè)路由器接收到一個目的地址為142.150.71.132的 IP分組，請確定該路由器為該IP分組選擇的下一跳，并解釋說明。

　　（2）在上面的路由表中增加一條路由表項(xiàng)，該路由表項(xiàng)使以142.150.71.132為目的地址的IP分組選擇“A”作為下一跳，而不影響其他目的地址的IP分組轉(zhuǎn)發(fā)。

　?。?）在上面的路由表中增加一條路由表項(xiàng)，使所有目的地址與該路由表中任何路由表項(xiàng)都不匹配的IP分組被轉(zhuǎn)發(fā)到下一跳“E”。

　?。?）將142.150.64.0／24劃分為4個規(guī)模盡可能大的等長子網(wǎng)，給出子網(wǎng)掩碼及每個子網(wǎng)的可分配地址范圍。