2023年中國(guó)石油大學(xué)(北京)計(jì)算機(jī)技術(shù)考研856考試大綱

考研考試大綱一般是由各個(gè)院校自行發(fā)布，內(nèi)容包含考試科目的考試范圍、試卷結(jié)構(gòu)、考試形式和主要參考資料等等?？荚嚧缶V對(duì)考生來說至關(guān)重要，以下是希賽網(wǎng)小編為大家整理的2023年中國(guó)石油大學(xué)(北京)計(jì)算機(jī)技術(shù)（085404）考研初試856數(shù)據(jù)結(jié)構(gòu)與計(jì)算機(jī)網(wǎng)絡(luò)考試大綱，僅供大家參考。

相關(guān)推薦：2021-2022年分?jǐn)?shù)線 | 研究方向一覽表 | 考試科目 | 學(xué)費(fèi)匯總 | 招生人數(shù) | 歷年真題

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

856數(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é)、公平、有效地測(cè)試考生掌握計(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ǔ)言版)，嚴(yán)蔚敏、吳偉民編著,清華大學(xué)出版社,2012

《計(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++語(yǔ)言設(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)樹的路徑長(zhǎng)度和帶權(quán)路徑長(zhǎng)度,哈夫曼樹(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ù),平均查找長(zhǎng)度;

(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ì)(雙絞線、同軸電纜、光纖)與無(wú)線傳輸介質(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ù)與面向連接服務(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.簡(jiǎn)單網(wǎng)絡(luò)管理協(xié)議SNMP(網(wǎng)絡(luò)管理的基本概念、SNMP協(xié)議數(shù)據(jù)單元和報(bào)文)。

資料來源：

中國(guó)石油大學(xué)(北京)信息科學(xué)與工程學(xué)院2023年碩士研究生入學(xué)考試大綱