834 計(jì)算機(jī)專業(yè)基礎(chǔ)綜合(數(shù)據(jù)結(jié)構(gòu)、計(jì)算機(jī)網(wǎng)絡(luò))研究生入學(xué)考試大綱
    數(shù)據(jù)結(jié)構(gòu)部分(占60%)
    【考試范圍】
    線性表(包括隊(duì)列、堆棧等特殊線性表)的基本邏輯結(jié)構(gòu)特征理解與應(yīng)用;線性表(包括隊(duì)列、堆棧等特殊線性表)的物理存貯結(jié)構(gòu);特殊矩陣的存貯及應(yīng)用;樹、圖等非線性結(jié)構(gòu)的基本邏輯結(jié)構(gòu)特征理解與應(yīng)用;樹、圖等非線性結(jié)構(gòu)的物理存貯結(jié)構(gòu)。排序與查找算法;一些算法的設(shè)計(jì)與時間復(fù)雜度分析。
    【具體內(nèi)容】
    一 緒論
    1引言
    2 什么是數(shù)據(jù)結(jié)構(gòu)
    3 相關(guān)基本概念和術(shù)語
    4 算法的基本特征
    5 算法分析相關(guān)概念
    二 線性表
    1 線性表的概念，線性表的抽象數(shù)據(jù)類型，基本操作
    2 線性表的順序存儲結(jié)構(gòu)：靜態(tài)分配，動態(tài)分配
    3 順序表的插入刪除算法，移動元素次數(shù)分析
    4 順序存儲結(jié)構(gòu)的優(yōu)缺點(diǎn)，引出單鏈表的結(jié)構(gòu)類型定義
    5 單鏈表的算法：生成先進(jìn)先出單鏈表，后進(jìn)先出單鏈表
    6 單鏈表的算法：生成不帶表頭的遞增有序單鏈表，生成帶表頭的遞增有序單鏈表
    7 單鏈表的算法：在指定位置插入一個新結(jié)點(diǎn);刪除指定值的結(jié)點(diǎn);在指定位置刪除一個結(jié)點(diǎn);
    8 單鏈表的合并：兩個遞增有序的單鏈表合并成一個遞增有序的單鏈表
    9 循環(huán)鏈表的概念，雙向循環(huán)鏈表的概念，插入和刪除結(jié)點(diǎn)
    10 多項(xiàng)式的鏈表表示，算法思想
    三 棧和隊(duì)列
    1 棧的相關(guān)概念與特性
    2 順序棧的基本操作
    3 鏈?zhǔn)綏５幕静僮?BR>    4 棧的應(yīng)用
    5 隊(duì)列的相關(guān)概念
    6 鏈?zhǔn)疥?duì)列的基本操作
    7 順序隊(duì)列的基本操作
    四 數(shù) 組
    1 抽象數(shù)據(jù)類型數(shù)組的說明
    2 數(shù)組的物理結(jié)構(gòu)
    3 特殊矩陣的壓縮存儲: 對稱矩陣與三對角矩陣的壓縮存儲
    4 稀疏矩陣的壓縮存儲：三元組順序表與十字鏈表
    5 稀疏矩陣的運(yùn)算(轉(zhuǎn)置算法)
    6 廣義表的概念：概念、物理結(jié)構(gòu)、遞歸算法
    五 樹與二叉樹
    1 樹的有關(guān)概念
    2 二叉樹的定義與性質(zhì)
    3 二叉樹的存儲結(jié)構(gòu)
    4 二叉樹的遍歷
    5二叉樹遍歷的應(yīng)用
    6 樹的存儲結(jié)構(gòu)
    7 樹與二叉樹的相互轉(zhuǎn)換
    8 樹與森林的遍歷
    9 哈夫曼樹
    10、哈夫曼算法
    六 圖
    1 圖的定義及術(shù)語
    2 圖的物理存貯結(jié)構(gòu)：鄰接矩陣、鄰接表、十字鏈表和鄰接多重表
    3 圖的遍歷：深度優(yōu)先搜索遍歷與廣度優(yōu)先搜索遍歷
    4 圖的連通性問題：DFS與BFS生成樹、強(qiáng)連通分量的求解，最小生成樹
    5 有向無環(huán)圖及應(yīng)用: 拓?fù)渑判?、關(guān)鍵路徑
    6 最短路徑：迪杰斯特拉算法、弗洛伊德算法
    七 查找
    1 查找問題概述
    2 順序查找法
    3 折半查找法
    4 分塊查找法
    5 二叉排序樹查找法
    6 平衡二叉排序樹查找法
    7 B-樹查找法和B+樹查找法
    8 鍵樹查找法
    9 哈希查找法
    八 排序
    1 查找問題概述、插入排序法
    2 交換排序法
    3 選擇排序法
    4 歸并排序法
    5 基數(shù)排序法
    計(jì)算機(jī)網(wǎng)絡(luò)部分(占40%)
    【考試范圍】
    重點(diǎn)考查計(jì)算機(jī)網(wǎng)絡(luò)的構(gòu)成和計(jì)算機(jī)網(wǎng)絡(luò)核心的兩種數(shù)據(jù)交換方法、計(jì)算機(jī)網(wǎng)絡(luò)的層次化體系結(jié)構(gòu)、計(jì)算機(jī)網(wǎng)絡(luò)的性能度量指標(biāo)、四種主流的因特網(wǎng)應(yīng)用的工作原理(萬維網(wǎng)/電子郵件/域名解析/P2P)、數(shù)據(jù)可靠傳輸?shù)幕驹砗头椒?、?shù)據(jù)傳輸中流量控制和擁塞控制的基本原理和方法、計(jì)算機(jī)網(wǎng)絡(luò)中的三種設(shè)備標(biāo)識方式(域名/IP地址/MAC地址)及其映射關(guān)系、端口的概念和TCP/UDP的工作原理、IP協(xié)議和路由協(xié)議、共享信道的協(xié)調(diào)方法和以太網(wǎng)的工作原理、無線局域網(wǎng)的構(gòu)成和基本工作原理等內(nèi)容。
    【具體內(nèi)容】
    一 計(jì)算機(jī)網(wǎng)絡(luò)和因特網(wǎng)
    1 計(jì)算機(jī)網(wǎng)絡(luò)的構(gòu)成和功能
    2 因特網(wǎng)的接入方式
    3 因特網(wǎng)核心的數(shù)據(jù)交換方式
    4 計(jì)算機(jī)網(wǎng)絡(luò)的層次模型及相關(guān)概念
    5 OSI/RM模型和TCP/IP模型
    二 應(yīng)用層
    1 應(yīng)用層協(xié)議的原理及網(wǎng)絡(luò)應(yīng)用模型
    2 Web應(yīng)用和HTTP協(xié)議
    3 因特網(wǎng)中的電子郵件
    4 域名服務(wù)DNS
    5 P2P文件共享
    三 運(yùn)輸層
    1 運(yùn)輸層的工作原理和提供的服務(wù)
    2 多路復(fù)用與多路分解
    3 UDP協(xié)議和TCP協(xié)議的報文結(jié)構(gòu)和工作機(jī)制
    4 可靠數(shù)據(jù)傳輸?shù)幕驹砑捌湓赥CP協(xié)議中的應(yīng)用
    5 擁塞控制的基本原理及其在TCP協(xié)議中的應(yīng)用
    6 流量控制的基本原理及其在TCP協(xié)議中的應(yīng)用
    四 網(wǎng)絡(luò)層
    1 網(wǎng)絡(luò)層的工作原理及其提供的服務(wù)
    2 虛電路和數(shù)據(jù)報網(wǎng)絡(luò)的工作原理及對比
    3 路由器的構(gòu)成和工作原理
    4 IP地址的分類、子網(wǎng)劃分和CIDR的工作原理
    5. IPv4分組結(jié)構(gòu)及轉(zhuǎn)發(fā)機(jī)制
    6 NAT協(xié)議的工作原理和應(yīng)用場景
    7 ARP、DHCP和ICMP協(xié)議
    8 選路算法：RIP、OSPF和BGP-4
    9 IP組播的概念和IP組播地址
    10 IPv6地址、數(shù)據(jù)報格式和鄰居發(fā)現(xiàn)協(xié)議
    五 數(shù)據(jù)鏈路層和以太網(wǎng)
    1 數(shù)據(jù)鏈路層的工作原理及其提供的服務(wù)
    2 差錯檢測和糾錯技術(shù)
    3 多址訪問協(xié)議的分類和工作原理
    4 鏈路層的編址方式
    5 以太網(wǎng)
    6 集線器和交換機(jī)的工作原理
    7 點(diǎn)對點(diǎn)協(xié)議PPP
    8 虛擬局域網(wǎng)
    六 無線網(wǎng)絡(luò)和移動網(wǎng)絡(luò)
    1 無線網(wǎng)絡(luò)的概念、組成、分類和工作原理
    2 無線鏈路和網(wǎng)絡(luò)特征
    3 802.11無線局域網(wǎng)的工作原理
    4 無線局域網(wǎng)中的多址訪問協(xié)議
    5 移動IP