碩士研究生入學(xué)考試《數(shù)據(jù)結(jié)構(gòu)》考試大綱
一、考試要求
《數(shù)據(jù)結(jié)構(gòu)》是一門專業(yè)基礎(chǔ)課,要求考生能夠理解數(shù)據(jù)結(jié)構(gòu)的基本概念;掌握數(shù)據(jù)結(jié)構(gòu)中邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)的基本概念和差異,以及各種基本操作的實現(xiàn);在掌握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上,能夠?qū)λ惴ㄟM(jìn)行設(shè)計與分析;能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進(jìn)行問題求解;能夠針對具體問題設(shè)計正確的數(shù)據(jù)結(jié)構(gòu)加以應(yīng)用;具備采用類c或c++或JAVA語言設(shè)計與實現(xiàn)算法的能力。
本課程包括:算法的基本概念、分析和設(shè)計方法;軟件開發(fā)中常用的各類結(jié)構(gòu),包括線性結(jié)構(gòu)、樹結(jié)構(gòu)、圖結(jié)構(gòu);查找、排序等各類常用算法。主要考察學(xué)生對數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識的理解、是否具備對現(xiàn)有常用結(jié)構(gòu)和算法的應(yīng)用能力、是否具備針對具體應(yīng)用設(shè)計合適數(shù)據(jù)結(jié)構(gòu)的能力。
二、考試題型及權(quán)重(共75分)
⑴選擇: 30分;
⑶簡答題:15分;
⑷算法應(yīng)用題:20分;
⑸算法設(shè)計題:10分。
三、考查范圍
(1)基本概念和算法分析
本部分的目的是介紹數(shù)據(jù)結(jié)構(gòu)中常用的基本概念和術(shù)語以及學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義。重點要求理解數(shù)據(jù)結(jié)構(gòu)的基本概念、算法的基本要素和基本要求。掌握簡單的算法時間/空間復(fù)雜度分析方法。理解抽象數(shù)據(jù)結(jié)構(gòu)的定義,理解最好、最壞和平均復(fù)雜度的分析和計算方法。
(2)線性表
本部分的目的是介紹線性表的邏輯結(jié)構(gòu)和各種存儲表示方法,以及定義在邏輯結(jié)構(gòu)上的各種基本運(yùn)算及其在存儲結(jié)構(gòu)上如何實現(xiàn)這些基本運(yùn)算。重點要求熟練掌握線性表的定義和基本操作,能夠熟練掌握線性表的兩種實現(xiàn)方法(順序存儲和隨機(jī)存儲),熟知線性表的應(yīng)用范圍。理解線性表的各種存儲結(jié)構(gòu)、操作實現(xiàn)的異同點,優(yōu)缺點。
(3)棧和隊列
本部分的目的是介紹棧和隊列的邏輯結(jié)構(gòu)定義及在兩種存儲結(jié)構(gòu)上如何實現(xiàn)棧和隊列的基本運(yùn)算。重點要求熟練掌握棧和隊列的基本概念,以及棧和隊列的兩種實現(xiàn)方法(順序存儲結(jié)構(gòu)實現(xiàn)和鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn))及其操作的實現(xiàn)。能夠掌握棧和隊列的基本應(yīng)用。
(4)樹和二叉樹
本部分的目的是介紹二叉樹的定義、性質(zhì)、存儲結(jié)構(gòu)、遍歷、線索化;樹的定義、存儲結(jié)構(gòu)、遍歷、樹和森林的轉(zhuǎn)換及赫夫曼樹及其赫夫曼編碼等內(nèi)容。重點要求熟練掌握樹的基本概念、基本性質(zhì)。熟練掌握二叉樹的定義及其主要特征、二叉樹的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)、二叉樹的遍歷操作;掌握線索二叉樹的基本概念和構(gòu)造;掌握基于二叉樹遍歷操作所衍生出的各類操作,例如二叉樹的構(gòu)造、二叉樹葉子節(jié)點的統(tǒng)計、求二叉樹深度操作等。理解樹的存儲結(jié)構(gòu),掌握森林和二叉樹的相互轉(zhuǎn)換,樹和森林的遍歷操作。理解二叉排序樹的基本原理和算法,掌握平衡二叉樹的各種操作;掌握哈夫曼(Huffman)樹和哈夫曼編碼,并能夠在實際的問題中加以應(yīng)用。
(5)圖
本部分的目的是介紹圖的基本概念、兩種常用的存儲結(jié)構(gòu)、兩種遍歷方法以及圖的應(yīng)用算法。重點要求掌握圖的基本概念,基本性質(zhì)。掌握圖的存儲方法,掌握圖存儲的鄰接矩陣法和鄰接表法。掌握圖的兩種遍歷方法:深度優(yōu)先遍歷、廣度優(yōu)先遍歷。理解基于圖的最小(代價)生成樹算法、最短路徑算法、拓?fù)渑判蛩惴?。了解關(guān)鍵路徑算法。
(6)查找
本部分的目的是介紹線性表、樹和哈希表的查找方法、算法實現(xiàn)以及各種查找方法的時間性能(平均查找長度)分析。重點要求掌握順序查找、折半查找、二叉排序樹和哈希表查找的基本思想和算法實現(xiàn)。了解平衡二叉樹、B-樹的基本概念及基本操作、B+樹的基本概念。能夠理解各種不同查找算法的適用情況,以及不同算法的性能分析。
(7)內(nèi)部排序
內(nèi)部排序部分的目的是介紹五大類內(nèi)部排序方法的基本思想、排序過程、算法實現(xiàn)、時間和空間性能的分析;并且對各種排序方法進(jìn)行比較。重點要求掌握直接插入排序、快速排序、堆排序和歸并排序的基本思想和排序過程。理解基數(shù)排序、折半插入排序等排序方法的基本思想和排序過程。掌握各類排序方法的性質(zhì)、效率對比。
碩士研究生入學(xué)考試《計算機(jī)網(wǎng)絡(luò)》考試大綱
一、考試要求
1. 掌握計算機(jī)網(wǎng)絡(luò)的基本概念、原理和方法。
2. 理解TCP/IP協(xié)議。
二、考試題型及權(quán)重(共75分)
1. 選擇題: 20題,40分;
2. 簡答題: 2題,10分;
4. 綜合應(yīng)用: 2題,25分;
三、考查范圍
1. 第一章 計算機(jī)網(wǎng)絡(luò)概述
(1)因特網(wǎng)的邏輯組成與端到端設(shè)計原則;
(2)計算機(jī)網(wǎng)絡(luò)的主要分類方法;
(3)電路交換、報文交換與分組交換的區(qū)別;
(4)計算機(jī)網(wǎng)絡(luò)協(xié)議的分層方法;
(5)OSI模型與TCP/IP模型;
2. 第二章 物理層
(1)數(shù)據(jù)傳輸?shù)幕靖拍?,包括:?shù)據(jù)與信號的關(guān)系、通信方式和傳輸介質(zhì);
(2)常見編碼方式與基本帶通調(diào)制技術(shù);
(3)信道的極限容量,包括:奈奎斯特定理與香農(nóng)定理;
(4)多路復(fù)用技術(shù);
3. 第三章 數(shù)據(jù)鏈路層
(1)數(shù)據(jù)鏈路層的基本概念,包括:鏈路協(xié)議分類、幀的概念和鏈路層的三個基本問題;
(2)常見的組幀技術(shù);
(3)CRC檢錯編碼方法;
(4)PPP協(xié)議的主要內(nèi)容,包括:協(xié)議特點,基本組成和幀格式;
(5)以太網(wǎng)的主要內(nèi)容:CSMA/CD協(xié)議、MAC地址和幀格式;
(6)網(wǎng)橋與交換機(jī)的工作原理;
(7)VLAN的工作原理;
4. 第四章 網(wǎng)絡(luò)層
(1)網(wǎng)絡(luò)層的基本概念,包括:異構(gòu)互連問題、網(wǎng)絡(luò)層服務(wù)模型和設(shè)計思想;
(2)IP協(xié)議的基本概念,包括:主要特點和協(xié)議組成;
(3)IP編址方法,包括:分類的IP地址、帶掩碼的IP地址、CIDR編址;
(4)NAT地址轉(zhuǎn)換技術(shù)的工作原理;
(5)ARP協(xié)議的工作原理;
(6)IP分組的封裝格式,包括:TTL字段的作用、IP分片方法;
(7)ICMP協(xié)議的作用;
(8)RIP路由協(xié)議的工作原理和特點;
(9)OSPF 路由協(xié)議的特點和工作原理;
5. 第五章 傳輸層
(1)進(jìn)程間的通信與端口的概念;
(2)兩種運(yùn)輸層協(xié)議TCP和UDP的區(qū)別;
(3)UDP協(xié)議,包括:報文格式和主要特點;
(4)TCP報文段的分段與首部格式;
(5)TCP的滑動窗口機(jī)制和確認(rèn)號;
(6)TCP的可靠傳輸機(jī)制,包括流量控制方法和擁塞控制方法;
(7)TCP的連接管理;
6. 第6章 應(yīng)用層
(1) 兩種網(wǎng)絡(luò)應(yīng)用模型的主要特點,包括:客戶/服務(wù)器模型和P2P模型;
(2) DNS系統(tǒng)工作原理;
(3)DHCP協(xié)議的作用;
(4) 電子郵件的基本概念,包括SMTP協(xié)議和pop3協(xié)議;
(5)WWW服務(wù)和HTTP協(xié)議的基本概念;