計算機學科專業(yè)基礎878考試大綱

1、2015年浙江大學研究生入學考試計算機學科專業(yè)基礎（878）考試大綱考查目標 計算機專業(yè)基礎（878）綜合考試涵蓋程序設計、數據結構、操作系統和計算機網絡等學科專業(yè)基礎課程。要求考生比較系統地掌握上述專業(yè)基礎課程的基本概念、基本原理和基本方法，能夠綜合運用所學的基本原理和基本方法分析、判斷和解決有關理論問題和實際問題。考試形式和試卷結構一、試卷滿分及考試時間本試卷滿分為150分，考試時間為180分鐘二、答題方式答題方式為閉卷、筆試三、試卷內容結構程序設計基礎（C）30分數據結構50分操作系統40分計算機網絡30分四、試卷題型結構單項選擇題70分（35小題，每小題2分）綜合應用題80分考查范圍程

2、序設計基礎（C）【考查目標】1理解C程序設計語言結構，掌握數據表示和輸入輸出的基本方法，掌握流程控制、函數設計與調用方法；2理解模塊化程序設計方法，掌握基本的C語言程序設計過程和技巧；3掌握初步的算法設計及數據組織方法，具備基本的問題分析和利用C語言進行求解問題的能力。數據表達與組織（一）常量，變量，運算與表達式（二）一維和二維數組，字符數組和字符串（三）指針與數組，結構與數組（四）指針與結構，單向鏈表語句及流程控制（一）復合語句（二）分支控制(if、switch)（三）循環(huán)控制(for、while、dowhile)程序結構和函數（一）C程序結構（二）函數的定義、參數傳遞和調用（三）函數的遞歸

3、調用（四）變量的存儲類別、作用域，全局變量和局部變量輸入/輸出和文件（一）標準輸入和輸出（二）文本文件與二進制文件（三）文件打開、關閉、讀寫和定位編譯預處理和命令行參數（一）宏定義和宏函數（二）命令行參數和使用基本算法設計與程序實現（一）簡單排序算法（插入、選擇、冒泡）、二分查找（二）鏈表、文件中查找（三）級數求和、進制轉換數據結構【考查目標】1掌握數據結構的基本概念、基本原理和基本方法；2掌握數據的邏輯結構、存儲結構及基本操作的實現，能夠對算法進行基本的時間復雜度與空間復雜度的分析；3能應用數據結構基本原理和方法進行問題的分析與求解，具備采用C或C+語言設計與實現算法的能力。一、棧、隊列和數

4、組（一）棧和隊列的基本概念（二）棧和隊列的順序存儲結構（三）棧和隊列的鏈式存儲結構（四）棧和隊列的應用二、樹與二叉樹（一）樹的基本概念（二）二叉樹1. 二叉樹的定義及其主要特性2.二叉樹的順序存儲結構和鏈式存儲結構3.二叉樹的遍歷4.線索二叉樹的基本概念和構造（三）樹、森林1.樹的存儲結構2.森林與二叉樹的轉換3.樹和森林的遍歷（四）樹與二叉樹的應用1.二叉排序樹2.堆結構3.哈夫曼（Huffman）樹和哈夫曼編碼四、圖（一）圖的基本概念（二）圖的存儲及基本操作1. 鄰接矩陣法2. 鄰接表法3鄰接多重表、十字鏈表（三）圖的遍歷1. 深度優(yōu)先搜索2. 廣度優(yōu)先搜索（四）圖的基本應用1. 最小（代

5、價）生成樹2. 最短路徑3. 拓撲排序4. 關鍵路徑五、動態(tài)查找（一）平衡二叉樹(AVL樹)（二）B樹及其基本操作、B+樹的基本概念（三）散列（Hash）表（四）查找算法的分析及應用六、排序（一）希爾排序（Shell Sort）（二）快速排序（三）堆排序（四）二路歸并排序（Merge Sort）（五）基數排序（六）各種內部排序算法的比較（七）排序算法的應用操作系統【考查目標】1. 掌握操作系統的基本概念、基本原理和基本功能，理解操作系統的整體運行過程。2. 掌握操作系統進程、內存、文件和I/O管理的策略、算法、機制以及相互關系。3. 能夠運用所學的操作系統原理、方法與技術分析問題和解決問題，并

6、能利用C語言或者C+語言描述相關算法。一、操作系統概述（一）操作系統的概念、特征、功能和提供的服務（二）操作系統的發(fā)展與分類（三）操作系統的運行環(huán)境1.內核態(tài)與用戶態(tài)2.中斷、異常3.系統調用（四）操作系統體系結構二、進程管理（一）進程與線程1. 進程概念2. 進程的狀態(tài)與轉換3. 進程控制4. 進程組織5. 進程通信共享存儲系統；消息傳遞系統；管道通信。6.線程概念與多線程模型（二）處理機調度1. 調度的基本概念2.調度時機、切換與過程3.調度的基本準則4.調度方式5.典型調度算法先來先服務調度算法；短作業(yè)（短進程、短線程）優(yōu)先調度算法；時間片輪轉調度算法；優(yōu)先級調度算法；高響應比優(yōu)先調度算

7、法；多級反饋隊列調度算法。（三）同步與互斥1. 進程同步的基本概念2. 實現臨界區(qū)互斥的基本方法軟件實現方法；硬件實現方法。3. 信號量4. 管程5. 經典同步問題生產者-消費者問題；讀者-寫者問題；哲學家進餐問題。（四）死鎖1. 死鎖的概念2. 死鎖處理策略3. 死鎖預防4. 死鎖避免系統安全狀態(tài)，銀行家算法。5. 死鎖檢測和解除三、內存管理（一）內存管理基礎1. 內存管理概念程序裝入與鏈接；邏輯地址與物理地址空間；內存保護。2. 交換與覆蓋3. 連續(xù)分配管理方式4. 非連續(xù)分配管理方式分頁管理方式；分段管理方式；段頁式管理方式。（二）虛擬內存管理1. 虛擬內存基本概念2. 請求分頁管理方式

8、3. 頁面置換算法最佳置換算法（OPT）；先進先出置換算法（FIFO）；最近最少使用置換算法（LRU）；時鐘置換算法（CLOCK）。4. 頁面分配策略5.工作集6. 抖動四、文件管理（一）文件系統基礎1. 文件概念2. 文件的邏輯結構順序文件；索引文件；索引順序文件。3. 目錄結構文件控制塊和索引節(jié)點；單級目錄結構和兩級目錄結構；樹形目錄結構；圖形目錄結構。4. 文件共享5. 文件保護訪問類型；訪問控制。（二）文件系統實現1. 文件系統層次結構2. 目錄實現3. 文件實現（三）磁盤組織與管理1. 磁盤的結構2. 磁盤調度算法3. 磁盤的管理五、輸入輸出（I/O）管理（一）I/O管理概述1. I

9、/O控制方式2. I/O軟件層次結構（二）I/O核心子系統1. I/O調度概念2. 高速緩存與緩沖區(qū)3. 設備分配與回收4. 假脫機技術（SPOOLing）計算機網絡【考查目標】1. 掌握計算機網絡的基本概念、基本原理和基本方法。2. 掌握計算機網絡的體系結構和典型網絡協議，了解典型網絡設備的組成和特點，理解典型網絡設備的工作原理。3. 能夠運用計算機網絡的基本概念、基本原理和基本方法進行網絡系統的分析、設計和應用。一、計算機網絡體系結構（一）計算機網絡概述1. 計算機網絡的概念、組成與功能2. 計算機網絡的分類4. 計算機網絡的標準化工作及相關組織（二）計算機網絡體系結構與參考模型1. 計算

10、機網絡分層結構2. 計算機網絡協議、接口、服務等概念3. ISO/OSI參考模型和TCP/IP模型二、物理層（一）通信基礎1. 信道、信號、寬帶、碼元、波特、速率、信源與信宿等基本概念2. 奈奎斯特定理與香農定理3. 編碼與調制4. 電路交換、分組交換5. 數據報與虛電路（二）傳輸介質1. 雙絞線、同軸電纜、光纖與無線傳輸介質2. 物理層接口的特性（三）物理層設備1. 中繼器2. 集線器三、數據鏈路層（一）數據鏈路層的功能（二）組幀（三）差錯控制新增：路由聚集1. 檢錯編碼2. 糾錯編碼（四）流量控制與可靠傳輸機制1. 流量控制、可靠傳輸與滑輪窗口機制2. 停止-等待協議3. 后退N幀協議（G

11、BN）4. 選擇重傳協議（SR）（五）介質訪問控制1. 信道劃分頻分多路復用、時分多路復用、波分多路復用、碼分多路復用的概念和基本原理。2. 隨即訪問ALOHA協議；CSMA協議；CSMA/CD協議；CSMA/CA協議。3. 輪詢訪問：令牌傳遞協議。（六）局域網1. 局域網的基本概念與體系結構2. 以太網與IEEE 802.3 （七）廣域網1. 廣域網的基本概念2. PPP協議3. HDLC協議（八）數據鏈路層設備1. 網橋的概念和基本原理2. 局域網交換機及其工作原理。四、網絡層（一）網絡層的功能1. 異構網絡互聯2. 路由與轉發(fā)3. 擁塞控制（二）路由算法1. 靜態(tài)路由與動態(tài)路由2. 距離

12、-向量路由算法3. 鏈路狀態(tài)路由算法4. 層次路由（三）IPv4 1. IPv4分組2. IPv4地址與NAT 3. 子網劃分與子網掩碼、CIDR 4. ARP協議、DHCP協議與ICMP協議（四）IPv6 1. IPv6的主要特點2. IPv6地址（五）路由協議1. 自治系統2. 域內路由與域間路由3. RIP路由協議4. OSPF路由協議5. BGP路由協議（六）IP組播1. 組播的概念2. IP組播地址（七）網絡層設備1. 路由器的組成和功能2. 路由表與路由轉發(fā)五、傳輸層（一）傳輸層提供的服務1. 傳輸層的功能2. 傳輸層尋址與端口3. 無連接服務與面向連接服務（二）UDP協議1. U

13、DP數據報2. UDP校驗（三）TCP協議1. TCP段2. TCP連接管理3. TCP可靠傳輸4. TCP流量控制與擁塞控制六、應用層（一）網絡應用模型1. 客戶/服務器模型2. P2P模型（二）DNS系統1. 層次域名空間2. 域名服務器3. 域名解析過程（三）電子郵件1. 電子郵件系統的組成結構2. 電子郵件格式與MIME 3. SMTP協議與POP3協議（四）WWW 1. WWW的概念與組成結構2. HTTP協議參考書：C語言程序設計（第二版），何欽銘顏暉主編，高等教育出版社，2012年2、Data Structure and Algorithm Analysis in C(第2版)，M.A.Weiss著、陳越改編，人民郵件出版社，2005年3、數據結構，陳越 主編，高等教育出版社，2012年4、操作系統概念(第7版)(翻譯版)，西爾伯查茨(Abraham Silberschatz)等著，鄭扣根譯高等教育出版社，2010年5. 計算機網絡(英文版第5版)，Andrew S.Tane