2021中國石油大學(xué)（北京）數(shù)據(jù)結(jié)構(gòu)與計(jì)算機(jī)網(wǎng)絡(luò)研究生考試大綱 正文

中國石油大學(xué)（北京）碩士研究生入學(xué)考試
《數(shù)據(jù)結(jié)構(gòu)與計(jì)算機(jī)網(wǎng)絡(luò)》考試大綱
第一部分 考試說明
一、考試性質(zhì)
數(shù)據(jù)結(jié)構(gòu)和計(jì)算機(jī)網(wǎng)絡(luò)是計(jì)算機(jī)專業(yè)的專業(yè)基礎(chǔ)課。此次綜合考試是為招收計(jì)算機(jī)學(xué)科的碩士研究生而設(shè)置的具有選拔性質(zhì)的聯(lián)考科目，其目的是科學(xué)、公平、有效地測試考生掌握計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科大學(xué)本科階段專業(yè)知識(shí)、基本理論、基本方法的水平和分析問題、解決問題的能力，評(píng)價(jià)的標(biāo)準(zhǔn)是高等院校計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科優(yōu)秀本科畢業(yè)生所能達(dá)到的及格或及格以上水平，以利于計(jì)算機(jī)各專業(yè)的導(dǎo)師擇優(yōu)選拔碩士研究生，確保碩士研究生的招生質(zhì)量。
二、考試要求
此次考試涵蓋數(shù)據(jù)結(jié)構(gòu)和計(jì)算機(jī)網(wǎng)絡(luò)兩門專業(yè)基礎(chǔ)課程。要求考生比較系統(tǒng)地掌握上述基礎(chǔ)課程的基本概念、基本原理和基本方法，能夠綜合運(yùn)用所學(xué)的基本原理和基本方法分析、判斷和解決有關(guān)理論問題和實(shí)際問題。
三、考試形式和試卷結(jié)構(gòu)
1.試卷滿分及考試時(shí)間
本試卷滿分為150分，考試時(shí)間為180分鐘。
2.答題方式
答題方式為閉卷、筆試。
3.試卷內(nèi)容結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)   75分
計(jì)算機(jī)網(wǎng)絡(luò) 75分
四、主要參考書目
《數(shù)據(jù)結(jié)構(gòu)》(C語言版)，嚴(yán)蔚敏、吳偉民編著,清華大學(xué)出版社,1997.4
《數(shù)據(jù)結(jié)構(gòu)（AR）》，連遠(yuǎn)鋒、吳雙元、朱丹丹編著，清華大學(xué)出版社，2019.10
《計(jì)算機(jī)網(wǎng)絡(luò)（第7版）》，謝希仁，電子工業(yè)出版社，2017.1
五、考查內(nèi)容
I.數(shù)據(jù)結(jié)構(gòu)
【考查目標(biāo)】
1.掌握數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和基本方法。
2.掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及基本操作的實(shí)現(xiàn)，能夠?qū)λ惴ㄟM(jìn)行基本的時(shí)間復(fù)雜度與空間復(fù)雜度的分析。
3.能夠運(yùn)用數(shù)據(jù)結(jié)構(gòu)基本原理和方法進(jìn)行問題的分析與求解，具備采用C或C++語言設(shè)計(jì)與實(shí)現(xiàn)算法的能力。
【考查內(nèi)容】
    1.數(shù)據(jù)結(jié)構(gòu)和算法
    數(shù)據(jù)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)的概念；數(shù)據(jù)類型與抽象數(shù)據(jù)類型；算法的概念,用C/C++描述算法和程序設(shè)計(jì),算法分析初步。
    2.線性表
    線性表的定義和基本操作；線性表的抽象數(shù)據(jù)類型；線性表的順序存儲(chǔ)結(jié)構(gòu)，應(yīng)用舉例；線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(單鏈表,雙鏈表,循環(huán)鏈表),應(yīng)用舉例。
3.棧
    棧的定義和基本操作；棧的抽象數(shù)據(jù)類型；順序棧，鏈?zhǔn)綏?；棧和遞歸算法, 算術(shù)表達(dá)式求值,其它應(yīng)用。
    4．隊(duì)列
    隊(duì)列的定義和基本操作；隊(duì)列的抽象數(shù)據(jù)類型；順序隊(duì)列，鏈?zhǔn)疥?duì)列；雙端隊(duì)列的定義和基本操作；應(yīng)用舉例。
    5.數(shù)組和字符串
    數(shù)組的定義和基本操作；數(shù)組的順序存儲(chǔ)結(jié)構(gòu)，應(yīng)用舉例；特殊矩陣和稀疏矩陣的壓縮存儲(chǔ)。    字符串的定義和基本操作,字符串的存儲(chǔ)結(jié)構(gòu),字符串操作的實(shí)現(xiàn)舉例,字符串和模式匹配。
    6.樹和二叉樹
(1)樹的基本概念和基本操作,樹的抽象數(shù)據(jù)類型；
(2)二叉樹的概念和性質(zhì),特殊二叉樹；二叉樹的存儲(chǔ)結(jié)構(gòu)；
(3)二叉樹的生成與建立；
    (4)遍歷二叉樹：前序遍歷,中序遍歷,后序遍歷,層次遍歷；
    (5)二叉樹其它操作實(shí)現(xiàn)舉例；
    (6)線索二叉樹的概念和存儲(chǔ)結(jié)構(gòu),二叉樹的線索化,線索二叉樹的遍歷；
    (7)樹的存儲(chǔ)結(jié)構(gòu),樹與二叉樹之間的轉(zhuǎn)換,森林與二叉樹之間的轉(zhuǎn)換,樹和森林的遍歷；
    (8)樹的路徑長度和帶權(quán)路徑長度,哈夫曼樹(Huffman)的概念,哈夫曼算法, 哈夫曼編碼樹；
    (9)二叉排序樹的的概念和基本操作,二叉排序樹的建立,二叉排序樹其它操作實(shí)現(xiàn)舉例。
    7.圖
    (1)圖的基本概念和基本操作，圖的抽象數(shù)據(jù)類型；
    (2)圖的存儲(chǔ)結(jié)構(gòu)：數(shù)組表示法(鄰接矩陣)；鄰接表，逆鄰接表，十字鏈表；鄰接多重表；
    (3)圖的遍歷：深度優(yōu)先搜索法, 寬度優(yōu)先搜索法, 求圖的連通分量；
(4)生成樹、最小生成樹的概念；克魯斯卡爾(Kruskal)算法,普里姆(Prim)算法；
(5)從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑,每對(duì)頂點(diǎn)之間的最短路徑；
(6)拓?fù)渑判蚝完P(guān)鍵路徑。
    8.查找
    (1)查找的概念,關(guān)鍵字比較次數(shù),平均查找長度；
    (2)順序表的查找:順序查找,折半查找,分塊查找；
    (3)樹表的查找:二叉排序樹,平衡二叉樹。
    (4)哈希(Hash)表的查找:哈希表的概念,哈希函數(shù)構(gòu)造方法,哈希表的建立和查找,沖突處理方法。
    9.排序
(1)排序的概念；排序的穩(wěn)定性；比較關(guān)鍵字次數(shù),移動(dòng)記錄次數(shù)；
(2)內(nèi)排序方法與算法：
1) 交換排序:冒泡排序,快速排序；
2) 插入排序:直接插入排序,2路插入排序,折半插入排序,希爾排序；
3) 接選擇排序,錦標(biāo)賽排序,堆排序；
4) 歸并排序；
5) 基數(shù)排序；
(3)各種排序算法的評(píng)價(jià)和應(yīng)用。
II.計(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ò)的組成和特點(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)用。
【考查內(nèi)容】
1.計(jì)算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu)
(1)計(jì)算機(jī)網(wǎng)絡(luò)概述：計(jì)算機(jī)網(wǎng)絡(luò)的概念、計(jì)算機(jī)網(wǎng)絡(luò)組成與功能、計(jì)算機(jī)網(wǎng)絡(luò)的分類、計(jì)算機(jī)網(wǎng)絡(luò)的標(biāo)準(zhǔn)化工作及相關(guān)組織、計(jì)算機(jī)網(wǎng)絡(luò)的性能。
(2)計(jì)算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu)與參考模型：計(jì)算機(jī)網(wǎng)絡(luò)分層結(jié)構(gòu)、計(jì)算機(jī)網(wǎng)絡(luò)協(xié)議、計(jì)算機(jī)接口和服務(wù)等概念、ISO/OSI參考模型、TCP/IP模型和五層協(xié)議體系結(jié)構(gòu)。
2.物理層
(1)通信基礎(chǔ):通信的基本概念（信道、信號(hào)、寬帶、碼元、波特、速率、信源與信宿等）、
奈奎斯特定理與香農(nóng)定理、編碼與調(diào)制、電路交換和分組交換、數(shù)據(jù)報(bào)與虛電路;
(2)傳輸介質(zhì):有線傳輸介質(zhì)（雙絞線、同軸電纜、光纖）與無線傳輸介質(zhì)、物理層接口的特性、物理層設(shè)備（中繼器和集線器）。
3.數(shù)據(jù)鏈路層
(1)數(shù)據(jù)鏈路層的功能；
(2)組幀；
(3)差錯(cuò)控制；
(4)介質(zhì)訪問控制:信道劃分（頻分多路復(fù)用、時(shí)分多路復(fù)用、波分多路復(fù)用、碼分多路復(fù)用的概念和基本原理）、隨機(jī)訪問（CSMA/CD協(xié)議、CSMA/CA協(xié)議）、輪詢?cè)L問（令牌傳遞協(xié)議）；
(5)局域網(wǎng):局域網(wǎng)的基本概念與體系結(jié)構(gòu)、以太網(wǎng)與IEEE802.3、IEEE802.11、虛擬局域網(wǎng)；
     (6)廣域網(wǎng):廣域網(wǎng)的基本概念、PPP協(xié)議；
 (7)數(shù)據(jù)鏈路層設(shè)備:網(wǎng)橋的概念及其基本原理、局域網(wǎng)交換機(jī)及其工作原理。
4.網(wǎng)絡(luò)層
(1)網(wǎng)絡(luò)層的功能:異構(gòu)網(wǎng)絡(luò)互連、路由與轉(zhuǎn)發(fā)、擁塞控制；
(2)路由算法:靜態(tài)路由與動(dòng)態(tài)路由、距離-向量路由算法、鏈路狀態(tài)路由算法、層次路由；
(3)IPv4:IPv4分組、IPv4地址與NAT、子網(wǎng)劃分、路由聚集、子網(wǎng)掩碼與CIDR、ARP協(xié)議和ICMP協(xié)議；
(4)IPv6:IPv6的主要特點(diǎn)、IPv6地址；
(5)路由協(xié)議:自治系統(tǒng)、域內(nèi)路由與域間路由、RIP路由協(xié)議、OSPF路由協(xié)議、BGP路由協(xié)議；
(6)IP組播:組播的概念、IP組播地址；
 (7)網(wǎng)絡(luò)層設(shè)備:路由器的組成和功能、路由表與路由轉(zhuǎn)發(fā)。
5.傳輸層
(1)傳輸層提供的服務(wù):傳輸層的功能、傳輸層尋址與端口、無連接服務(wù)與面向連接服務(wù)；
(2)UDP協(xié)議:UDP數(shù)據(jù)報(bào)、UDP校驗(yàn)；
(3)TCP協(xié)議:TCP報(bào)文段、TCP連接管理、TCP可靠傳輸（停止等待協(xié)議、后退N幀協(xié)議GBN、選擇重傳協(xié)議SR）；
(4)TCP流量控制與擁塞控制。
6.應(yīng)用層
(1)網(wǎng)絡(luò)應(yīng)用模型:客戶/服務(wù)器模型、P2P模型；
(2)DNS系統(tǒng):層次域名空間、域名服務(wù)器、域名解析過程；
(3)FTP:FTP協(xié)議的工作原理、控制連接與數(shù)據(jù)連接；
(4)電子郵件:電子郵件系統(tǒng)的組成結(jié)構(gòu)、電子郵件格式與MIME、SMTP協(xié)議與POP3協(xié)議；
(5)WWW:WWW的概念與組成結(jié)構(gòu)、HTTP協(xié)議。
7.DHCP協(xié)議
8.簡單網(wǎng)絡(luò)管理協(xié)議SNMP（網(wǎng)絡(luò)管理的基本概念、SNMP協(xié)議數(shù)據(jù)單元和報(bào)文）。
 

中國石油大學(xué)(北京)

本文來源：http://alternativeofficeassistance.com/zhongguoshiyouda/cankaoshumu_390348.html