國(guó)防科技大學(xué)

2022年研究生入學(xué)考試自命題科目考試大綱

科目代碼：903 科目名稱：計(jì)算機(jī)綜合

一、參考書(shū)目

1.《數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)第二版》嚴(yán)蔚敏主編，人民郵電出版社,2015;

2.《計(jì)算機(jī)網(wǎng)絡(luò)》(第7版)，謝希仁，電子工業(yè)出版社，2017;

3.《Computer Networking: A Top Down Approach》, James F. Kurose and Keith W. Rose(陳鳴譯), 機(jī)械工業(yè)出版社, 2017。

二、考試內(nèi)容及要求

(一)數(shù)據(jù)結(jié)構(gòu)

1.緒論

考試內(nèi)容：數(shù)據(jù)結(jié)構(gòu)，抽象數(shù)據(jù)類型，時(shí)間復(fù)雜度，空間復(fù)雜度。

考試要求：

了解《數(shù)據(jù)結(jié)構(gòu)》的研究?jī)?nèi)容，數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ)，熟悉抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)，掌握算法的時(shí)間復(fù)雜度的計(jì)算方法。

2.線性表

考試內(nèi)容：線性表的類型定義、順序表示和實(shí)現(xiàn)、鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)，線性表在一元多項(xiàng)式相加中的應(yīng)用。

考試要求：

(1)了解線性表的邏輯結(jié)構(gòu)特性，線性表的兩種存儲(chǔ)實(shí)現(xiàn)方式和描述方法。

(2)掌握順序表的定義與實(shí)現(xiàn)，包括查找、插入、刪除算法的實(shí)現(xiàn)。

(3)掌握在各種鏈?zhǔn)浇Y(jié)構(gòu)中實(shí)現(xiàn)線性表操作的基本方法，能在實(shí)際應(yīng)用中選用適當(dāng)?shù)逆湵斫Y(jié)構(gòu)。

(4)能夠從時(shí)間和空間復(fù)雜度的角度綜合比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合。

(5)了解線性表在一元多項(xiàng)式相加中的應(yīng)用。

3.棧和隊(duì)列

考試內(nèi)容：棧的定義、表示和實(shí)現(xiàn)，隊(duì)列的定義、表示和實(shí)現(xiàn)，棧的應(yīng)用，棧與遞歸的實(shí)現(xiàn)。

考試要求：

(1)了解棧和隊(duì)列的定義、特性，并能正確應(yīng)用它們解決實(shí)際問(wèn)題。

(2)掌握棧的順序表示、鏈?zhǔn)奖硎疽约跋鄳?yīng)操作的實(shí)現(xiàn)。注意�？蘸蜅�滿的條件。

(3)掌握隊(duì)列的順序表示、鏈?zhǔn)奖硎疽约跋鄳?yīng)操作的實(shí)現(xiàn)。注意循環(huán)隊(duì)列中隊(duì)頭與隊(duì)尾指針的變化情況。

(4)了解棧與遞歸的實(shí)現(xiàn)。

4.串

考試內(nèi)容：串的類型定義，串的表示和實(shí)現(xiàn)，串的模式匹配算法。

考試要求：

(1)了解串的定義、基本操作。

(2)掌握順序存儲(chǔ)結(jié)構(gòu)上串各種操作的方法。

(3)掌握KMP算法。

5.數(shù)組與廣義表

考試內(nèi)容：數(shù)組，稀疏矩陣，數(shù)組的順序表示，壓縮存儲(chǔ)，廣義表。

考試要求：

(1)了解數(shù)組的定義，掌握數(shù)組的順序表示和實(shí)現(xiàn)。

(2)掌握特殊矩陣、稀疏矩陣壓縮存儲(chǔ)方式。

(3)了解廣義表的概念、表示及存儲(chǔ)結(jié)構(gòu)。

6.樹(shù)和二叉樹(shù)

考試內(nèi)容：二叉樹(shù)與樹(shù)，二叉樹(shù)性質(zhì)，二叉樹(shù)與樹(shù)的存儲(chǔ)結(jié)構(gòu)，二叉樹(shù)的遍歷和線索化，森林與二叉樹(shù)的轉(zhuǎn)換，赫夫曼樹(shù)及其應(yīng)用。

考試要求：

(1)了解樹(shù)和二叉樹(shù)的定義和性質(zhì)。

(2)掌握二叉樹(shù)的結(jié)構(gòu)特性、存儲(chǔ)結(jié)構(gòu)及適用范圍、遍歷算法。

(3)掌握樹(shù)存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)、樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換方法。

(4)掌握建立赫夫曼樹(shù)和赫夫曼編碼的方法及帶權(quán)路徑長(zhǎng)度的計(jì)算。

7.圖

考試內(nèi)容：圖的定義和存儲(chǔ)結(jié)構(gòu)、圖的遍歷、圖的連通性問(wèn)題、拓?fù)渑判颉㈥P(guān)鍵路徑、最短路徑。

考試要求：

(1)理解圖的基本概念，熟悉圖的各種存儲(chǔ)結(jié)構(gòu)及其構(gòu)造算法。

(2)掌握?qǐng)D的深度優(yōu)先和廣度優(yōu)先兩種路徑遍歷算法。

(3)了解AOV網(wǎng)絡(luò)、AOE網(wǎng)絡(luò)。

(4)掌握拓?fù)渑判蚝完P(guān)鍵路徑算法。

(5)掌握kruskul和prim算法構(gòu)造最小生成樹(shù)算法。

(6)掌握Dijkstra算法求解單源最短路徑，理解floyd算法求多源頂點(diǎn)間最短路徑問(wèn)題。

7.查找

考試內(nèi)容：順序表、有序表的查找，二叉排序樹(shù)和平衡二叉樹(shù)，哈希表的構(gòu)造方法和處理沖突的方法。

考試要求：

(1)掌握順序表和有序表的查找算法及其性能分析方法。

(2)掌握二叉排序樹(shù)的構(gòu)造和查找算法及其性能分析方法。

(3)理解AVL樹(shù)的維護(hù)平衡方法。

(4)理解B_樹(shù)、B+的特點(diǎn)、查找及構(gòu)造方法。

(5)掌握哈希函數(shù)的構(gòu)造及解決沖突的方法。

8.查找

考試內(nèi)容：插入排序，快速排序，選擇排序，歸并排序，基數(shù)排序。

考試要求：

(1)掌握排序的基本概念和各種排序方法的特點(diǎn)，并能加以靈活應(yīng)用。

(2)掌握插入排序、交換排序、選擇排序、歸并排序的方法及其性能分析方法。

(3)了解基數(shù)排序方法及其性能分析方法。

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

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

考試內(nèi)容：計(jì)算機(jī)網(wǎng)絡(luò)的概念、組成與功能，計(jì)算機(jī)網(wǎng)絡(luò)的分類，因特網(wǎng)的組成，計(jì)算機(jī)網(wǎng)絡(luò)的性能，計(jì)算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu)與參考模型。

考試要求：

(1)掌握計(jì)算機(jī)網(wǎng)絡(luò)的基本概念、組成和基本功能;掌握因特網(wǎng)邊緣和電路交換、報(bào)文交換與分組交換等因特網(wǎng)核心的基本概念;掌握衡量網(wǎng)絡(luò)性能的速率、帶寬、時(shí)延、時(shí)延帶寬積、往返時(shí)間RTT、吞吐量等概念;掌握網(wǎng)絡(luò)協(xié)議分層的基本原理和方法，計(jì)算機(jī)網(wǎng)絡(luò)協(xié)議、實(shí)體、接口和服務(wù)等概念;掌握TCP/IP協(xié)議的體系結(jié)構(gòu);掌握客戶/服務(wù)器、P2P等典型的網(wǎng)絡(luò)應(yīng)用模型。

(2)理解計(jì)算機(jī)網(wǎng)絡(luò)的分類方法和標(biāo)準(zhǔn);理解計(jì)算機(jī)網(wǎng)絡(luò)的標(biāo)準(zhǔn)化工作及相關(guān)組織機(jī)構(gòu)的特點(diǎn)和職能范圍;理解因特網(wǎng)的標(biāo)準(zhǔn)化工作過(guò)程。

(3)了解計(jì)算機(jī)網(wǎng)絡(luò)與因特網(wǎng)的發(fā)展歷程和發(fā)展趨勢(shì);了解網(wǎng)絡(luò)協(xié)議的ISO/OSI參考模型。

2.物理層

考試內(nèi)容：數(shù)據(jù)通信的基礎(chǔ)知識(shí)，物理層下面的傳輸媒體，信道復(fù)用技術(shù)，數(shù)字傳輸系統(tǒng)，寬帶接入技術(shù)。

考試要求：

(1)掌握物理層的基本概念、數(shù)據(jù)通信系統(tǒng)模型、信道和信道容量等基礎(chǔ)知識(shí);掌握頻分復(fù)用、時(shí)分復(fù)用、碼分復(fù)用等信道復(fù)用技術(shù)的基本原理;掌握ADSL、HFC和FTTx等寬帶接入技術(shù)的基本原理和實(shí)現(xiàn)方法。

(2)理解導(dǎo)引型和非導(dǎo)引型各類傳輸媒體的特點(diǎn)和應(yīng)用場(chǎng)合;理解奈奎斯特定理與香農(nóng)定理的基本內(nèi)容;理解信道編碼與調(diào)制的基本概念;理解統(tǒng)計(jì)時(shí)分復(fù)用的原理和基本實(shí)現(xiàn)方法;理解中繼器、集線器等典型物理層設(shè)備的工作原理和應(yīng)用場(chǎng)合。

(3)了解光的波分復(fù)用技術(shù);了解SDH和SONET等數(shù)字傳輸系統(tǒng)。

3.數(shù)據(jù)鏈路層

考試內(nèi)容：使用點(diǎn)對(duì)點(diǎn)信道的數(shù)據(jù)鏈路層和點(diǎn)對(duì)點(diǎn)協(xié)議PPP，使用廣播信道的數(shù)據(jù)鏈路層，以太網(wǎng)和CSMA/CD協(xié)議，無(wú)線局域網(wǎng)WLAN協(xié)議，高速以太網(wǎng)。

考試要求：

(1)掌握數(shù)據(jù)鏈路和幀的基本概念，數(shù)據(jù)鏈路層要解決的封裝成幀、透明傳輸、差錯(cuò)檢測(cè)三個(gè)基本問(wèn)題;掌握PPP協(xié)議的特點(diǎn)、幀格式和工作狀態(tài);掌握CSMA/CD協(xié)議的基本內(nèi)容和使用方式;掌握在物理層和鏈路層擴(kuò)展以太網(wǎng)的原理和方法;掌握局域網(wǎng)交換機(jī)的工作原理和使用方法。

(2)理解以太網(wǎng)MAC層的基本內(nèi)涵;理解網(wǎng)橋的概念和基本原理;理解無(wú)線局域網(wǎng)WLAN協(xié)議IEEE 802.11的工作原理和實(shí)現(xiàn)方法;理解100BASE-T、吉比特和10吉比特以太網(wǎng)的實(shí)現(xiàn)原理和方法;理解使用以太網(wǎng)進(jìn)行寬帶接入的方法。

(3)了解以太網(wǎng)信道利用率的分析和計(jì)算方法。

4.網(wǎng)絡(luò)層

考試內(nèi)容：網(wǎng)絡(luò)層提供的服務(wù)，IP地址與IP協(xié)議，劃分子網(wǎng)和構(gòu)造超網(wǎng)，網(wǎng)際控制報(bào)文協(xié)議ICMP協(xié)議，因特網(wǎng)的路由選擇協(xié)議;IP多播，虛擬專用網(wǎng)VPN和網(wǎng)絡(luò)地址轉(zhuǎn)換NAT。

考試要求：

(1)掌握網(wǎng)絡(luò)層提供的虛電路和數(shù)據(jù)報(bào)服務(wù)的基本原理和方法，虛擬互連網(wǎng)絡(luò)的概念;掌握IP地址、物理地址的概念，地址解析協(xié)議ARP作用、工作原理和實(shí)現(xiàn)方法;掌握IP層轉(zhuǎn)發(fā)分組的基本流程;掌握子網(wǎng)掩碼的概念和劃分子網(wǎng)的方法、使用子網(wǎng)時(shí)分組轉(zhuǎn)發(fā)的方法、使用無(wú)分類編址CIDR構(gòu)造超網(wǎng)的原理和方法;掌握網(wǎng)際控制報(bào)文協(xié)議ICMP的作用、報(bào)文的種類和應(yīng)用場(chǎng)合;掌握靜態(tài)路由與動(dòng)態(tài)路由的基本概念，內(nèi)部網(wǎng)關(guān)協(xié)議RIP、OSPF和外部網(wǎng)關(guān)協(xié)議BGP等典型因特網(wǎng)路由選擇協(xié)議的工作原理和應(yīng)用場(chǎng)合，自治系統(tǒng)的基本概念;掌握虛擬專用網(wǎng)VPN和網(wǎng)絡(luò)地址轉(zhuǎn)換NAT的基本原理和實(shí)現(xiàn)方法。

(2)理解IP數(shù)據(jù)報(bào)的格式及各協(xié)議字段的含義;理解地址聚合的概念和作用;理解典型路由器的基本構(gòu)成部件;理解IP多播的概念、在局域網(wǎng)上進(jìn)行硬件多播的實(shí)現(xiàn)方法、網(wǎng)際組管理協(xié)議IGMP和多播路由選擇協(xié)議的工作原理和實(shí)現(xiàn)方法。

(3)了解IPv6的主要特點(diǎn)和各協(xié)議字段的含義;了解移動(dòng)IP的概念和移動(dòng)IP的通信過(guò)程。

5.運(yùn)輸層

考試內(nèi)容：運(yùn)輸層協(xié)議的概念，用戶數(shù)據(jù)報(bào)協(xié)議UDP，可靠傳輸?shù)墓ぷ髟�理，傳輸控制協(xié)議TCP的特點(diǎn)、TCP報(bào)文段的首部格式和TCP可靠傳輸?shù)膶?shí)現(xiàn)方法，TCP的流量控制和擁塞控制，TCP的運(yùn)輸連接管理。

考試要求：

(1)掌握進(jìn)程間通信的概念、運(yùn)輸層端口的作用和意義;掌握UDP協(xié)議的特點(diǎn)、首部格式和應(yīng)用場(chǎng)合;掌握TCP協(xié)議的特點(diǎn)和TCP連接的概念，停止等待協(xié)議、連續(xù)ARQ協(xié)議等可靠傳輸協(xié)議的工作原理;掌握TCP報(bào)文段首部各字段的含義和作用，TCP協(xié)議實(shí)現(xiàn)可靠傳輸?shù)幕瑒?dòng)窗口、字節(jié)編號(hào)、確認(rèn)、超時(shí)重傳等基本機(jī)制;掌握擁塞控制的一般原理、TCP協(xié)議實(shí)現(xiàn)擁塞控制的方法。

(2)理解選擇確認(rèn)SACK的實(shí)現(xiàn)方法;理解TCP協(xié)議實(shí)現(xiàn)流量控制的方法;理解利用隨機(jī)早期檢測(cè)RED實(shí)現(xiàn)TCP擁塞控制的原理;理解TCP連接的建立、釋放等TCP運(yùn)輸連接管理的實(shí)現(xiàn)方法。

(3)了解影響TCP效率和TCP連接吞吐量的各類因素和TCP連接吞吐量的基本計(jì)算方法;了解TCP協(xié)議有限狀態(tài)機(jī)。

6.應(yīng)用層

考試內(nèi)容：域名系統(tǒng)DNS，文件傳輸協(xié)議FTP，遠(yuǎn)程終端協(xié)議TELNET，萬(wàn)維網(wǎng)WWW，電子郵件，動(dòng)態(tài)主機(jī)配置協(xié)議DHCP，簡(jiǎn)單網(wǎng)絡(luò)管理協(xié)議SNMP，應(yīng)用進(jìn)程跨越網(wǎng)絡(luò)的通信。

考試要求：

(1)掌握域名系統(tǒng)的基本概念、因特網(wǎng)的域名結(jié)構(gòu)、域名服務(wù)器概念和作用、域名查詢的過(guò)程;掌握FTP協(xié)議的概念和FTP的基本工作原理;掌握萬(wàn)維網(wǎng)的基本概念，統(tǒng)一資源定位符URL的作用，超文本傳送協(xié)議HTTP的工作原理和實(shí)現(xiàn)方法，萬(wàn)維網(wǎng)文檔、信息檢索系統(tǒng)和微博的概念;掌握電子郵件的概念，簡(jiǎn)單郵件傳送協(xié)議SMTP的工作原理，電子郵件的信息格式，郵件讀取協(xié)議POP3和IMAP的作用和工作原理，基于萬(wàn)維網(wǎng)實(shí)現(xiàn)電子郵件的方法，通用因特網(wǎng)郵件擴(kuò)充MIME的實(shí)現(xiàn)方法;掌握DHCP協(xié)議的作用和工作原理;掌握網(wǎng)絡(luò)管理的基本概念和SNMP協(xié)議的實(shí)現(xiàn)方法。

(2)理解簡(jiǎn)單文件傳送協(xié)議TFTP的工作原理;理解系統(tǒng)調(diào)用和應(yīng)用編程接口的概念。

(3)了解TELNET協(xié)議的作用和基本工作原理;了解SNMP的協(xié)議數(shù)據(jù)單元和報(bào)文;了解常用的系統(tǒng)調(diào)用。

三、試卷結(jié)構(gòu)(滿分150分，時(shí)間180分鐘)

按題型：

內(nèi)  容	選擇題	填空題	簡(jiǎn)答題	計(jì)算題	綜合題
數(shù)據(jù)結(jié)構(gòu)	20分		20分	0分	35分
計(jì)算機(jī)網(wǎng)絡(luò)	40分			35分

按章節(jié)內(nèi)容，數(shù)據(jù)結(jié)構(gòu)75分，計(jì)算機(jī)網(wǎng)絡(luò)75分，具體如下：

內(nèi)       容		分　值
數(shù)據(jù) 結(jié)構(gòu)	緒論	5
	線性表、棧、隊(duì)列	20
	串、數(shù)組、廣義表	10
	樹(shù)和二叉樹(shù)	15
	圖	15
	查找與排序	10
計(jì)算機(jī)網(wǎng)絡(luò)	計(jì)算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu)	5
	物理層	5
	數(shù)據(jù)鏈路層	10
	網(wǎng)絡(luò)層	25
	運(yùn)輸層	20
	應(yīng)用層	10