2021中國石油大學（北京）數據結構與計算機網絡研究生考試大綱 正文

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

中國石油大學(北京)

本文來源：http://www.qiang-kai.com/zhongguoshiyouda/cankaoshumu_390348.html