碩士研究生入學(xué)考試計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)綜合考試大綱

1、<p>　　碩士研究生入學(xué)考試《計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)綜合》考試大綱</p><p>　　考察模塊一《數(shù)據(jù)結(jié)構(gòu)》</p><p><b>　　一、考試要求</b></p><p>　　《數(shù)據(jù)結(jié)構(gòu)》是一門(mén)專(zhuān)業(yè)基礎(chǔ)課，要求考生能夠理解數(shù)據(jù)結(jié)構(gòu)的基本概念;掌握數(shù)據(jù)結(jié)構(gòu)中邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)的基本概念和差異，以及各種基本操作的實(shí)現(xiàn)；在掌握基本的數(shù)據(jù)處理

2、原理和方法的基礎(chǔ)上，能夠?qū)λ惴ㄟM(jìn)行設(shè)計(jì)與分析；能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進(jìn)行問(wèn)題求解；能夠針對(duì)具體問(wèn)題設(shè)計(jì)正確的數(shù)據(jù)結(jié)構(gòu)加以應(yīng)用；具備采用類(lèi)c或c++或JAVA語(yǔ)言設(shè)計(jì)與實(shí)現(xiàn)算法的能力。</p><p>　　本課程包括：算法的基本概念、分析和設(shè)計(jì)方法；軟件開(kāi)發(fā)中常用的各類(lèi)結(jié)構(gòu)，包括線性結(jié)構(gòu)、樹(shù)結(jié)構(gòu)、圖結(jié)構(gòu)；查找、排序等各類(lèi)常用算法。主要考察學(xué)生對(duì)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識(shí)的理解、是否具備對(duì)現(xiàn)有常用結(jié)構(gòu)和算法的應(yīng)用能力、是

3、否具備針對(duì)具體應(yīng)用設(shè)計(jì)合適數(shù)據(jù)結(jié)構(gòu)的能力。</p><p>　　二、考試題型及權(quán)重（共75分）</p><p><b>　　⑴選擇: 30分；</b></p><p><b>　　⑶簡(jiǎn)答題:15分；</b></p><p>　?、人惴☉?yīng)用題:20分；</p><p>　?、伤?/p>

4、法設(shè)計(jì)題:10分。</p><p><b>　　三、考查范圍</b></p><p>　?。?）基本概念和算法分析</p><p>　　本部分的目的是介紹數(shù)據(jù)結(jié)構(gòu)中常用的基本概念和術(shù)語(yǔ)以及學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義。重點(diǎn)要求理解數(shù)據(jù)結(jié)構(gòu)的基本概念、算法的基本要素和基本要求。掌握簡(jiǎn)單的算法時(shí)間/空間復(fù)雜度分析方法。理解抽象數(shù)據(jù)結(jié)構(gòu)的定義，理解最好、最壞和

5、平均復(fù)雜度的分析和計(jì)算方法。</p><p><b>　?。?）線性表</b></p><p>　　本部分的目的是介紹線性表的邏輯結(jié)構(gòu)和各種存儲(chǔ)表示方法，以及定義在邏輯結(jié)構(gòu)上的各種基本運(yùn)算及其在存儲(chǔ)結(jié)構(gòu)上如何實(shí)現(xiàn)這些基本運(yùn)算。重點(diǎn)要求熟練掌握線性表的定義和基本操作，能夠熟練掌握線性表的兩種實(shí)現(xiàn)方法（順序存儲(chǔ)和隨機(jī)存儲(chǔ)），熟知線性表的應(yīng)用范圍。理解線性表的各種存儲(chǔ)結(jié)構(gòu)、

6、操作實(shí)現(xiàn)的異同點(diǎn)，優(yōu)缺點(diǎn)。</p><p><b>　?。?）棧和隊(duì)列</b></p><p>　　本部分的目的是介紹棧和隊(duì)列的邏輯結(jié)構(gòu)定義及在兩種存儲(chǔ)結(jié)構(gòu)上如何實(shí)現(xiàn)棧和隊(duì)列的基本運(yùn)算。重點(diǎn)要求熟練掌握棧和隊(duì)列的基本概念，以及棧和隊(duì)列的兩種實(shí)現(xiàn)方法（順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)）及其操作的實(shí)現(xiàn)。能夠掌握棧和隊(duì)列的基本應(yīng)用。</p><p>

7、;<b>　　（4）樹(shù)和二叉樹(shù)</b></p><p>　　本部分的目的是介紹二叉樹(shù)的定義、性質(zhì)、存儲(chǔ)結(jié)構(gòu)、遍歷、線索化；樹(shù)的定義、存儲(chǔ)結(jié)構(gòu)、遍歷、樹(shù)和森林的轉(zhuǎn)換及赫夫曼樹(shù)及其赫夫曼編碼等內(nèi)容。重點(diǎn)要求熟練掌握樹(shù)的基本概念、基本性質(zhì)。熟練掌握二叉樹(shù)的定義及其主要特征、二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、二叉樹(shù)的遍歷操作；掌握線索二叉樹(shù)的基本概念和構(gòu)造；掌握基于二叉樹(shù)遍歷操作所衍生出的各類(lèi)操作

8、，例如二叉樹(shù)的構(gòu)造、二叉樹(shù)葉子節(jié)點(diǎn)的統(tǒng)計(jì)、求二叉樹(shù)深度操作等。理解樹(shù)的存儲(chǔ)結(jié)構(gòu)，掌握森林和二叉樹(shù)的相互轉(zhuǎn)換，樹(shù)和森林的遍歷操作。理解二叉排序樹(shù)的基本原理和算法，掌握平衡二叉樹(shù)的各種操作；掌握哈夫曼(Huffman)樹(shù)和哈夫曼編碼，并能夠在實(shí)際的問(wèn)題中加以應(yīng)用。</p><p><b>　?。?）圖</b></p><p>　　本部分的目的是介紹圖的基本概念、兩種常用的

9、存儲(chǔ)結(jié)構(gòu)、兩種遍歷方法以及圖的應(yīng)用算法。重點(diǎn)要求掌握?qǐng)D的基本概念，基本性質(zhì)。掌握?qǐng)D的存儲(chǔ)方法，掌握?qǐng)D存儲(chǔ)的鄰接矩陣法和鄰接表法。掌握?qǐng)D的兩種遍歷方法：深度優(yōu)先遍歷、廣度優(yōu)先遍歷。理解基于圖的最小(代價(jià))生成樹(shù)算法、最短路徑算法、拓?fù)渑判蛩惴āＡ私怅P(guān)鍵路徑算法。</p><p><b>　?。?）查找</b></p><p>　　本部分的目的是介紹線性表、樹(shù)和哈希表的查

10、找方法、算法實(shí)現(xiàn)以及各種查找方法的時(shí)間性能（平均查找長(zhǎng)度）分析。重點(diǎn)要求掌握順序查找、折半查找、二叉排序樹(shù)和哈希表查找的基本思想和算法實(shí)現(xiàn)。了解平衡二叉樹(shù)、B-樹(shù)的基本概念及基本操作、B+樹(shù)的基本概念。能夠理解各種不同查找算法的適用情況，以及不同算法的性能分析。</p><p><b>　?。?）內(nèi)部排序</b></p><p>　　內(nèi)部排序部分的目的是介紹五大類(lèi)內(nèi)部

11、排序方法的基本思想、排序過(guò)程、算法實(shí)現(xiàn)、時(shí)間和空間性能的分析；并且對(duì)各種排序方法進(jìn)行比較。重點(diǎn)要求掌握直接插入排序、快速排序、堆排序和歸并排序的基本思想和排序過(guò)程。理解基數(shù)排序、折半插入排序等排序方法的基本思想和排序過(guò)程。掌握各類(lèi)排序方法的性質(zhì)、效率對(duì)比。</p><p>　　考察模塊二《計(jì)算機(jī)網(wǎng)絡(luò)》</p><p><b>　　一、考試要求</b></p>

12、;<p>　　1. 掌握計(jì)算機(jī)網(wǎng)絡(luò)的基本概念、原理和方法。</p><p>　　2. 理解TCP/IP協(xié)議。</p><p>　　二、考試題型及權(quán)重（共75分）</p><p>　　1. 選擇題: 20題，40分； </p><p>　　2. 簡(jiǎn)答題: 2題，10分；</p><p>　　4. 綜合應(yīng)用:

13、 2題，25分；</p><p><b>　　三、考查范圍</b></p><p>　　1. 第一章 計(jì)算機(jī)網(wǎng)絡(luò)概述</p><p>　　（1）因特網(wǎng)的邏輯組成與端到端設(shè)計(jì)原則；</p><p>　　（2）計(jì)算機(jī)網(wǎng)絡(luò)的主要分類(lèi)方法；</p><p>　?。?）電路交換、報(bào)文交換與分組交換的區(qū)別；&

14、lt;/p><p>　?。?）計(jì)算機(jī)網(wǎng)絡(luò)協(xié)議的分層方法；</p><p>　?。?）OSI模型與TCP/IP模型；</p><p>　　2. 第二章 物理層</p><p>　?。?）數(shù)據(jù)傳輸?shù)幕靖拍睿ǎ簲?shù)據(jù)與信號(hào)的關(guān)系、通信方式和傳輸介質(zhì)；</p><p>　?。?）常見(jiàn)編碼方式與基本帶通調(diào)制技術(shù)；</p&g

15、t;<p>　?。?）信道的極限容量，包括：奈奎斯特定理與香農(nóng)定理；</p><p>　?。?）多路復(fù)用技術(shù)；</p><p>　　3. 第三章 數(shù)據(jù)鏈路層</p><p>　?。?）數(shù)據(jù)鏈路層的基本概念，包括：鏈路協(xié)議分類(lèi)、幀的概念和鏈路層的三個(gè)基本問(wèn)題；</p><p>　?。?）常見(jiàn)的組幀技術(shù)；</p>&l

16、t;p>　?。?）CRC檢錯(cuò)編碼方法；</p><p>　　（4）PPP協(xié)議的主要內(nèi)容，包括：協(xié)議特點(diǎn)，基本組成和幀格式；</p><p>　?。?）以太網(wǎng)的主要內(nèi)容：CSMA/CD協(xié)議、MAC地址和幀格式；</p><p>　　（6）網(wǎng)橋與交換機(jī)的工作原理；</p><p>　　（7）VLAN的工作原理；</p><

17、;p>　　4. 第四章 網(wǎng)絡(luò)層</p><p>　?。?）網(wǎng)絡(luò)層的基本概念，包括：異構(gòu)互連問(wèn)題、網(wǎng)絡(luò)層服務(wù)模型和設(shè)計(jì)思想；</p><p>　?。?）IP協(xié)議的基本概念，包括：主要特點(diǎn)和協(xié)議組成；</p><p>　?。?）IP編址方法，包括：分類(lèi)的IP地址、帶掩碼的IP地址、CIDR編址；</p><p>　?。?）NAT地址轉(zhuǎn)換技

18、術(shù)的工作原理；</p><p>　?。?）ARP協(xié)議的工作原理；</p><p>　?。?）IP分組的封裝格式，包括：TTL字段的作用、IP分片方法；</p><p>　?。?）ICMP協(xié)議的作用；</p><p>　?。?）RIP路由協(xié)議的工作原理和特點(diǎn)；</p><p>　?。?）OSPF 路由協(xié)議的特點(diǎn)和工作原理

19、；</p><p>　　5. 第五章 傳輸層</p><p>　?。?）進(jìn)程間的通信與端口的概念；</p><p>　?。?）兩種運(yùn)輸層協(xié)議TCP和UDP的區(qū)別；</p><p>　?。?）UDP協(xié)議，包括：報(bào)文格式和主要特點(diǎn)；</p><p>　?。?）TCP報(bào)文段的分段與首部格式；</p><p

20、>　　（5）TCP的滑動(dòng)窗口機(jī)制和確認(rèn)號(hào)；</p><p>　?。?）TCP的可靠傳輸機(jī)制，包括流量控制方法和擁塞控制方法；</p><p>　?。?）TCP的連接管理；</p><p>　　6. 第6章 應(yīng)用層</p><p>　　（1）兩種網(wǎng)絡(luò)應(yīng)用模型的主要特點(diǎn)，包括：客戶/服務(wù)器模型和P2P模型；</p><