2023年中國石油大學(北京)計算機科學與技術考研856考試大綱

考試大綱的內容一般包括當年全國研究生入學考試相應科目的考試范圍、考試要求、考試形式、試卷結構等信息，對考生備考至關重要。希賽網(wǎng)整理了2023年中國石油大學(北京)計算機科學與技術（081200）考研856數(shù)據(jù)結構與計算機網(wǎng)絡考試大綱信息，希望對考生備考有所幫助。

相關閱讀推薦>>>2021-2022年全國考研復試線丨2023年全國考試科目匯總丨2023年全國研究方向匯總

（注：以下信息來自學院官網(wǎng)，僅供參考，具體內容以院校發(fā)布為準）

856 數(shù)據(jù)結構與計算機網(wǎng)絡一初試考試大綱

第一部分 考試說明

一、考試性質

數(shù)據(jù)結構和計算機網(wǎng)絡是計算機專業(yè)的專業(yè)基礎課。此次綜合考試是為招收計算機學科的碩士研究生而設置的具有選拔性質的聯(lián)考科目，其目的是科學、公平、有效地測試考生掌握計算機科學與技術學科大學本科階段專業(yè)知識、基本理論、基本方法的水平和分析問題、解決問題的能力，評價的標準是高等院校計算機科學與技術學科優(yōu)秀本科畢業(yè)生所能達到的及格或及格以上水平，以利于計算機各專業(yè)的導師擇優(yōu)選拔碩士研究生，確保碩士研究生的招生質量。

二、考試要求

此次考試涵蓋數(shù)據(jù)結構和計算機網(wǎng)絡兩門專業(yè)基礎課程。要求考生比較系統(tǒng)地掌握上述基礎課程的基本概念、基本原理和基本方法，能夠綜合運用所學的基本原理和基本方法分析、判斷和解決有關理論問題和實際問題。

三、考試形式和試卷結構

1.試卷滿分及考試時間

本試卷滿分為150分，考試時間為180分鐘。

2.答題方式

答題方式為閉卷、筆試。

3.試卷內容結構

數(shù)據(jù)結構 75分

計算機網(wǎng)絡 75分

四、主要參考書目

《數(shù)據(jù)結構》(C語言版)，嚴蔚敏、吳偉民編著,清華大學出版社,2012

《計算機網(wǎng)絡(第7版)》，謝希仁，電子工業(yè)出版社，2017.1

五、考查內容

I.數(shù)據(jù)結構

【考查目標】

1.掌握數(shù)據(jù)結構的基本概念、基本原理和基本方法。

2.掌握數(shù)據(jù)的邏輯結構、存儲結構及基本操作的實現(xiàn)，能夠對算法進行基本的時間復雜度與空間復雜度的分析。

3.能夠運用數(shù)據(jù)結構基本原理和方法進行問題的分析與求解，具備采用C或C++語言設計與實現(xiàn)算法的能力。

【考查內容】

1.數(shù)據(jù)結構和算法

數(shù)據(jù)結構、存儲結構的概念;數(shù)據(jù)類型與抽象數(shù)據(jù)類型;算法的概念,用C/C++描述算法和程序設計,算法分析初步。

2.線性表

線性表的定義和基本操作;線性表的抽象數(shù)據(jù)類型;線性表的順序存儲結構，應用舉例;線性表的鏈式存儲結構(單鏈表,雙鏈表,循環(huán)鏈表),應用舉例。

3.棧

棧的定義和基本操作;棧的抽象數(shù)據(jù)類型;順序棧，鏈式棧;棧和遞歸算法, 算術表達式求值,其它應用。

4.隊列

隊列的定義和基本操作;隊列的抽象數(shù)據(jù)類型;順序隊列，鏈式隊列;雙端隊列的定義和基本操作;應用舉例。

5.數(shù)組和字符串

數(shù)組的定義和基本操作;數(shù)組的順序存儲結構，應用舉例;特殊矩陣和稀疏矩陣的壓縮存儲。 字符串的定義和基本操作,字符串的存儲結構,字符串操作的實現(xiàn)舉例,字符串和模式匹配。

6.樹和二叉樹

(1)樹的基本概念和基本操作,樹的抽象數(shù)據(jù)類型;

(2)二叉樹的概念和性質,特殊二叉樹;二叉樹的存儲結構;

(3)二叉樹的生成與建立;

(4)遍歷二叉樹：前序遍歷,中序遍歷,后序遍歷,層次遍歷;

(5)二叉樹其它操作實現(xiàn)舉例;

(6)線索二叉樹的概念和存儲結構,二叉樹的線索化,線索二叉樹的遍歷;

(7)樹的存儲結構,樹與二叉樹之間的轉換,森林與二叉樹之間的轉換,樹和森林的遍歷;

(8)樹的路徑長度和帶權路徑長度,哈夫曼樹(Huffman)的概念,哈夫曼算法, 哈夫曼編碼樹;

(9)二叉排序樹的的概念和基本操作,二叉排序樹的建立,二叉排序樹其它操作實現(xiàn)舉例。

7.圖

(1)圖的基本概念和基本操作，圖的抽象數(shù)據(jù)類型;

(2)圖的存儲結構：數(shù)組表示法(鄰接矩陣);鄰接表，逆鄰接表，十字鏈表;鄰接多重表;

(3)圖的遍歷：深度優(yōu)先搜索法, 寬度優(yōu)先搜索法, 求圖的連通分量;

(4)生成樹、最小生成樹的概念;克魯斯卡爾(Kruskal)算法,普里姆(Prim)算法;

(5)從一個頂點到其余各頂點的最短路徑,每對頂點之間的最短路徑;

(6)拓撲排序和關鍵路徑。

8.查找

(1)查找的概念,關鍵字比較次數(shù),平均查找長度;

(2)順序表的查找:順序查找,折半查找,分塊查找;

(3)樹表的查找:二叉排序樹,平衡二叉樹。

(4)哈希(Hash)表的查找:哈希表的概念,哈希函數(shù)構造方法,哈希表的建立和查找,沖突處理方法。

9.排序

(1)排序的概念;排序的穩(wěn)定性;比較關鍵字次數(shù),移動記錄次數(shù);

(2)內排序方法與算法：

1) 交換排序:冒泡排序,快速排序;

2) 插入排序:直接插入排序,2路插入排序,折半插入排序,希爾排序;

3) 接選擇排序,錦標賽排序,堆排序;

4) 歸并排序;

5) 基數(shù)排序;

(3)各種排序算法的評價和應用。

II.計算機網(wǎng)絡

【考查目標】

1.掌握計算機網(wǎng)絡的基本概念、基本原理和基本方法。

2.掌握計算機網(wǎng)絡的體系結構和典型網(wǎng)絡協(xié)議，了解典型網(wǎng)絡的組成和特點，理解典型網(wǎng)絡設備的工作原理。

3.能夠運用計算機網(wǎng)絡的基本概念、基本原理和基本方法進行網(wǎng)絡系統(tǒng)的分析、設計和應用。

【考查內容】

1.計算機網(wǎng)絡體系結構

(1)計算機網(wǎng)絡概述：計算機網(wǎng)絡的概念、計算機網(wǎng)絡組成與功能、計算機網(wǎng)絡的分類、計算機網(wǎng)絡的標準化工作及相關組織、計算機網(wǎng)絡的性能。

(2)計算機網(wǎng)絡體系結構與參考模型：計算機網(wǎng)絡分層結構、計算機網(wǎng)絡協(xié)議、計算機接口和服務等概念、ISO/OSI參考模型、TCP/IP模型和五層協(xié)議體系結構。

2.物理層

(1)通信基礎:通信的基本概念(信道、信號、寬帶、碼元、波特、速率、信源與信宿等)、

奈奎斯特定理與香農定理、編碼與調制、電路交換和分組交換、數(shù)據(jù)報與虛電路;

(2)傳輸介質:有線傳輸介質(雙絞線、同軸電纜、光纖)與無線傳輸介質、物理層接口的特性、物理層設備(中繼器和集線器)。

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

(1)數(shù)據(jù)鏈路層的功能;

(2)組幀;

(3)差錯控制;

(4)介質訪問控制:信道劃分(頻分多路復用、時分多路復用、波分多路復用、碼分多路復用的概念和基本原理)、隨機訪問(CSMA/CD協(xié)議、CSMA/CA協(xié)議)、輪詢訪問(令牌傳遞協(xié)議);

(5)局域網(wǎng):局域網(wǎng)的基本概念與體系結構、以太網(wǎng)與IEEE802.3、IEEE802.11、虛擬局域網(wǎng);

(6)廣域網(wǎng):廣域網(wǎng)的基本概念、PPP協(xié)議;

(7)數(shù)據(jù)鏈路層設備:網(wǎng)橋的概念及其基本原理、局域網(wǎng)交換機及其工作原理。

4.網(wǎng)絡層

(1)網(wǎng)絡層的功能:異構網(wǎng)絡互連、路由與轉發(fā)、擁塞控制;

(2)路由算法:靜態(tài)路由與動態(tài)路由、距離-向量路由算法、鏈路狀態(tài)路由算法、層次路由;

(3)IPv4:IPv4分組、IPv4地址與NAT、子網(wǎng)劃分、路由聚集、子網(wǎng)掩碼與CIDR、ARP協(xié)議和ICMP協(xié)議;

(4)IPv6:IPv6的主要特點、IPv6地址;

(5)路由協(xié)議:自治系統(tǒng)、域內路由與域間路由、RIP路由協(xié)議、OSPF路由協(xié)議、BGP路由協(xié)議;

(6)IP組播:組播的概念、IP組播地址;

(7)網(wǎng)絡層設備:路由器的組成和功能、路由表與路由轉發(fā)。

5.傳輸層

(1)傳輸層提供的服務:傳輸層的功能、傳輸層尋址與端口、無連接服務與面向連接服務;

(2)UDP協(xié)議:UDP數(shù)據(jù)報、UDP校驗;

(3)TCP協(xié)議:TCP報文段、TCP連接管理、TCP可靠傳輸(停止等待協(xié)議、后退N幀協(xié)議GBN、選擇重傳協(xié)議SR);

(4)TCP流量控制與擁塞控制。

6.應用層

(1)網(wǎng)絡應用模型:客戶/服務器模型、P2P模型;

(2)DNS系統(tǒng):層次域名空間、域名服務器、域名解析過程;

(3)FTP:FTP協(xié)議的工作原理、控制連接與數(shù)據(jù)連接;

(4)電子郵件:電子郵件系統(tǒng)的組成結構、電子郵件格式與MIME、SMTP協(xié)議與POP3協(xié)議;

(5)WWW:WWW的概念與組成結構、HTTP協(xié)議。

7.DHCP協(xié)議

8.簡單網(wǎng)絡管理協(xié)議SNMP(網(wǎng)絡管理的基本概念、SNMP協(xié)議數(shù)據(jù)單元和報文)。

數(shù)據(jù)來源：中國石油大學(北京)碩士研究生入學考試