計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)考試大綱

2016年浙江大學(xué)研究生入學(xué)考試《計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)》（878）考試大綱I考查目標(biāo)《計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)》（878）綜合考試涵蓋程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)和計(jì)算機(jī)網(wǎng)絡(luò)等學(xué)科專(zhuān)業(yè)基礎(chǔ)課程。要求考生比較系統(tǒng)地掌握上述專(zhuān)業(yè)基礎(chǔ)課程的基本概念、基本原理和基本方法，能夠綜合運(yùn)用所學(xué)的基本原理和基本方法分析、判斷和解決有關(guān)理論問(wèn)題和實(shí)際問(wèn)題。II考試形式和試卷結(jié)構(gòu)一、試卷滿(mǎn)分及考試時(shí)間本試卷滿(mǎn)分為150分，考試時(shí)間為180分鐘二、答題方式答題方式為閉卷、筆試三、試卷內(nèi)容結(jié)構(gòu)程序設(shè)計(jì)基礎(chǔ)（C）30分?jǐn)?shù)據(jù)結(jié)構(gòu)50分操作系統(tǒng)40分計(jì)算機(jī)網(wǎng)絡(luò)30分四、試卷題型結(jié)構(gòu)單項(xiàng)選擇題70分（35小題，每小題2分）綜合應(yīng)用題80分m考查范圍程序設(shè)計(jì)基礎(chǔ)（C）【考查目標(biāo)】理解C程序設(shè)計(jì)語(yǔ)言結(jié)構(gòu)，掌握數(shù)據(jù)表示和輸入輸出的基本方法，掌握流程控制、函數(shù)設(shè)計(jì)與調(diào)用方法；理解模塊化程序設(shè)計(jì)方法，掌握基本的C語(yǔ)言程序設(shè)計(jì)過(guò)程和技巧；掌握初步的算法設(shè)計(jì)及數(shù)據(jù)組織方法，具備基本的問(wèn)題分析和利用：語(yǔ)言進(jìn)行求解問(wèn)題的能力。一、數(shù)據(jù)表達(dá)與組織（一）常量，變量，運(yùn)算與表達(dá)式（二）一維和二維數(shù)組，字符數(shù)組和字符串（三）指針與數(shù)組，結(jié)構(gòu)與數(shù)組（四）指針與結(jié)構(gòu)，單向鏈表二、語(yǔ)句及流程控制（一）復(fù)合語(yǔ)句（二）分支控制（if、switch）（三）循環(huán)控制（for、while、do—while）三、程序結(jié)構(gòu)和函數(shù)（一）C程序結(jié)構(gòu)（二）函數(shù)的定義、參數(shù)傳遞和調(diào)用（三）函數(shù)的遞歸調(diào)用（四）變量的存儲(chǔ)類(lèi)別、作用域，全局變量和局部變量四、輸入/輸出和文件（一）標(biāo)準(zhǔn)輸入和輸出（二）文本文件與二進(jìn)制文件（三）文件打開(kāi)、關(guān)閉、讀寫(xiě)和定位五、編譯預(yù)處理和命令行參數(shù)（一）宏定義和宏函數(shù)（二）命令行參數(shù)和使用六、基本算法設(shè)計(jì)與程序?qū)崿F(xiàn)（一）簡(jiǎn)單排序算法（插入、選擇、冒泡）、二分查找（二）鏈表、文件中查找（三）級(jí)數(shù)求和、進(jìn)制轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)【考查目標(biāo)】掌握數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和基本方法；掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及基本操作的實(shí)現(xiàn)，能夠?qū)λ惴ㄟM(jìn)行基本的時(shí)間復(fù)雜度與空間復(fù)雜度的分析；能應(yīng)用數(shù)據(jù)結(jié)構(gòu)基本原理和方法進(jìn)行問(wèn)題的分析與求解，具備采用（：或C++語(yǔ)言設(shè)計(jì)與實(shí)現(xiàn)算法的能力。一、棧、隊(duì)列和數(shù)組（一）棧和隊(duì)列的基本概念（二）棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)（三）棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（四）棧和隊(duì)列的應(yīng)用二、樹(shù)與二叉樹(shù)（一）樹(shù)的基本概念（二）二叉樹(shù)二叉樹(shù)的定義及其主要特性二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉樹(shù)的遍歷線(xiàn)索二叉樹(shù)的基本概念和構(gòu)造（三）樹(shù)、森林樹(shù)的存儲(chǔ)結(jié)構(gòu)森林與二叉樹(shù)的轉(zhuǎn)換樹(shù)和森林的遍歷（四）樹(shù)與二叉樹(shù)的應(yīng)用二叉排序樹(shù)堆結(jié)構(gòu)哈夫曼（Huffman）樹(shù)和哈夫曼編碼四、圖（一）圖的基本概念（二）圖的存儲(chǔ)及基本操作鄰接矩陣法鄰接表法鄰接多重表、十字鏈表（三）圖的遍歷深度優(yōu)先搜索廣度優(yōu)先搜索（四）圖的基本應(yīng)用最?。ù鷥r(jià)）生成樹(shù)最短路徑拓?fù)渑判蜿P(guān)鍵路徑五、動(dòng)態(tài)查找

（一）平衡二叉樹(shù)（AVL樹(shù)）（二）B樹(shù)及其基本操作、B+樹(shù)的基本概念（三）散列（Hash）表（四）查找算法的分析及應(yīng)用六、排序（一）希爾排序（ShellSort）（二）快速排序（三）堆排序（四）二路歸并排序（MergeSort）（五）基數(shù)排序（六）各種內(nèi)部排序算法的比較（七）排序算法的應(yīng)用操作系統(tǒng)（一）平衡二叉樹(shù)（AVL樹(shù)）【考查目標(biāo)】掌握操作系統(tǒng)的基本概念、基本原理和基本功能，理解操作系統(tǒng)的整體運(yùn)行過(guò)程。掌握操作系統(tǒng)進(jìn)程、內(nèi)存、文件和I/O管理的策略、算法、機(jī)制以及相互關(guān)系。能夠運(yùn)用所學(xué)的操作系統(tǒng)原理、方法與技術(shù)分析問(wèn)題和解決問(wèn)題，并能利用C語(yǔ)言或者C++語(yǔ)言描述相關(guān)算法。一、操作系統(tǒng)概述（一）操作系統(tǒng)的概念、特征、功能和提供的服務(wù)（二）操作系統(tǒng)的發(fā)展與分類(lèi)（三）操作系統(tǒng)的運(yùn)行環(huán)境內(nèi)核態(tài)與用戶(hù)態(tài)中斷、異常系統(tǒng)調(diào)用（四）操作系統(tǒng)體系結(jié)構(gòu)二、進(jìn)程管理（一）進(jìn)程與線(xiàn)程進(jìn)程概念進(jìn)程的狀態(tài)與轉(zhuǎn)換進(jìn)程控制進(jìn)程組織進(jìn)程通信共享存儲(chǔ)系統(tǒng)；消息傳遞系統(tǒng)；管道通信。線(xiàn)程概念與多線(xiàn)程模型（二）處理機(jī)調(diào)度調(diào)度的基本概念調(diào)度時(shí)機(jī)、切換與過(guò)程調(diào)度的基本準(zhǔn)則調(diào)度方式典型調(diào)度算法先來(lái)先服務(wù)調(diào)度算法；短作業(yè)（短進(jìn)程、短線(xiàn)程）優(yōu)先調(diào)度算法；時(shí)間片輪轉(zhuǎn)調(diào)度算法;優(yōu)先級(jí)調(diào)度算法；高響應(yīng)比優(yōu)先調(diào)度算法；多級(jí)反饋隊(duì)列調(diào)度算法。（三）同步與互斥進(jìn)程同步的基本概念實(shí)現(xiàn)臨界區(qū)互斥的基本方法軟件實(shí)現(xiàn)方法；硬件實(shí)現(xiàn)方法。信號(hào)量管程經(jīng)典同步問(wèn)題生產(chǎn)者-消費(fèi)者問(wèn)題；讀者-寫(xiě)者問(wèn)題；哲學(xué)家進(jìn)餐問(wèn)題。（四）死鎖死鎖的概念死鎖處理策略死鎖預(yù)防死鎖避免系統(tǒng)安全狀態(tài)，銀行家算法。5.死鎖檢測(cè)和解除三、內(nèi)存管理（一）內(nèi)存管理基礎(chǔ)內(nèi)存管理概念程序裝入與鏈接；邏輯地址與物理地址空間；內(nèi)存保護(hù)。交換與覆蓋連續(xù)分配管理方式非連續(xù)分配管理方式分頁(yè)管理方式；分段管理方式；段頁(yè)式管理方式。（二）虛擬內(nèi)存管理虛擬內(nèi)存基本概念請(qǐng)求分頁(yè)管理方式頁(yè)面置換算法最佳置換算法（OPT）；先進(jìn)先出置換算法（FIFO）；最近最少使用置換算法（LRU）；時(shí)鐘置換算法（CLOCK）。頁(yè)面分配策略工作集抖動(dòng)四、文件管理（一）文件系統(tǒng)基礎(chǔ)文件概念文件的邏輯結(jié)構(gòu)順序文件；索引文件；索引順序文件。3.目錄結(jié)構(gòu)文件控制塊和索引節(jié)點(diǎn)；單級(jí)目錄結(jié)構(gòu)和兩級(jí)目錄結(jié)構(gòu)；樹(shù)形目錄結(jié)構(gòu)；圖形目錄結(jié)構(gòu)文件共享文件保護(hù)訪問(wèn)類(lèi)型；訪問(wèn)控制。（二）文件系統(tǒng)實(shí)現(xiàn)文件系統(tǒng)層次結(jié)構(gòu)目錄實(shí)現(xiàn)文件實(shí)現(xiàn)（三）磁盤(pán)組織與管理磁盤(pán)的結(jié)構(gòu)磁盤(pán)調(diào)度算法磁盤(pán)的管理五、輸入輸出（I/O）管理（一）I/O管理概述I/O控制方式I/O軟件層次結(jié)構(gòu)（二）I/O核心子系統(tǒng)I/O調(diào)度概念高速緩存與緩沖區(qū)設(shè)備分配與回收假脫機(jī)技術(shù)（SPOOLing）計(jì)算機(jī)網(wǎng)絡(luò)【考查目標(biāo)】掌握計(jì)算機(jī)網(wǎng)絡(luò)的基本概念、基本原理和基本方法。掌握計(jì)算機(jī)網(wǎng)絡(luò)的體系結(jié)構(gòu)和典型網(wǎng)絡(luò)協(xié)議，了解典型網(wǎng)絡(luò)設(shè)備的組成和特點(diǎn)，理解典型網(wǎng)絡(luò)設(shè)備的工作原理。能夠運(yùn)用計(jì)算機(jī)網(wǎng)絡(luò)的基本概念、基本原理和基本方法進(jìn)行網(wǎng)絡(luò)系統(tǒng)的分析、設(shè)計(jì)和應(yīng)用。一、計(jì)算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu)（一）計(jì)算機(jī)網(wǎng)絡(luò)概述計(jì)算機(jī)網(wǎng)絡(luò)的概念、組成與功能計(jì)算機(jī)網(wǎng)絡(luò)的分類(lèi)計(jì)算機(jī)網(wǎng)絡(luò)的標(biāo)準(zhǔn)化工作及相關(guān)組織（二）計(jì)算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu)與參考模型計(jì)算機(jī)網(wǎng)絡(luò)分層結(jié)構(gòu)計(jì)算機(jī)網(wǎng)絡(luò)協(xié)議、接口、服務(wù)等概念3.ISO/OSI參考模型和TCP/IP模型二、物理層（一）通信基礎(chǔ)信道、信號(hào)、寬帶、碼元、波特、速率、信源與信宿等基本概念奈奎斯特定理與香農(nóng)定理編碼與調(diào)制電路交換、分組交換數(shù)據(jù)報(bào)與虛電路（二）傳輸介質(zhì)1.雙絞線(xiàn)、同軸電纜、光纖與無(wú)線(xiàn)傳輸介質(zhì)2,物理層接口的特性（三）物理層設(shè)備1.中繼器2.集線(xiàn)器三、數(shù)據(jù)鏈路層（一）數(shù)據(jù)鏈路層的功能（二）組幀（三）差錯(cuò)控制新增：路由聚集檢錯(cuò)編碼糾錯(cuò)編碼（四）流量控制與可靠傳輸機(jī)制流量控制、可靠傳輸與滑輪窗口機(jī)制停止-等待協(xié)議3.后退1^幀協(xié)議（GBN）選擇重傳協(xié)議（SR）（五）介質(zhì)訪問(wèn)控制信道劃分頻分多路復(fù)用、時(shí)分多路復(fù)用、波分多路復(fù)用、碼分多路復(fù)用的概念和基本原理。隨即訪問(wèn)ALOHA協(xié)議；CSMA協(xié)議；CSMA/CD協(xié)議；CSMA/CA協(xié)議。輪詢(xún)?cè)L問(wèn)：令牌傳遞協(xié)議。（六）局域網(wǎng)1.局域網(wǎng)的基本概念與體系結(jié)構(gòu)2.以太網(wǎng)與IEEE802.3（七）廣域網(wǎng)廣域網(wǎng)的基本概念2.PPP協(xié)議HDLC協(xié)議（八）數(shù)據(jù)鏈路層設(shè)備網(wǎng)橋的概念和基本原理局域網(wǎng)交換機(jī)及其工作原理。四、網(wǎng)絡(luò)層（一）網(wǎng)絡(luò)層的功能異構(gòu)網(wǎng)絡(luò)互聯(lián)路由與轉(zhuǎn)發(fā)擁塞控制（二）路由算法靜態(tài)路由與動(dòng)態(tài)路由距離-向量路由算法鏈路狀態(tài)路由算法層次路由（三）IPv4IPv4分組IPv4地址與NAT子網(wǎng)劃分與子網(wǎng)掩碼、CIDRARP協(xié)議、DHCP協(xié)議與ICMP協(xié)議（四）IPv6IPv6的主要特點(diǎn)IPv6地址（五）路由協(xié)議自治系統(tǒng)域內(nèi)路由與域間路由RIP路由協(xié)議OSPF路由協(xié)議BGP路由協(xié)議（六）IP組播組播的概念I(lǐng)P組播地址（七）網(wǎng)絡(luò)層設(shè)備路由器的組成和功能路由表與路由轉(zhuǎn)發(fā)五、傳輸層（一）傳輸層提供的服務(wù)傳輸層的功能傳輸層尋址與端口無(wú)連接服務(wù)與面向連接服務(wù)（二）UDP協(xié)議UDP數(shù)據(jù)報(bào)UDP校驗(yàn)（三）TCP協(xié)議1.TCP段2.TCP連接管理3.TCP可靠傳輸4.TCP流量控制與擁塞控制六、應(yīng)用層（一）網(wǎng)絡(luò)應(yīng)用模型客戶(hù)/服務(wù)器模型2.P2P模型（二）DNS系統(tǒng)層次域名空間域名服務(wù)器域名解析過(guò)程（三）電子郵件1.電子郵件系統(tǒng)的組成結(jié)構(gòu)2.電子郵件格式與MIME3.SMTP協(xié)議與POP3協(xié)議（四）WWWWWW的概念與組成結(jié)構(gòu)HTTP協(xié)議參考書(shū)：1、C語(yǔ)言程序設(shè)計(jì)（第二版），何欽銘顏暉主編，高等教育出版社，2012年2、DataStructureandAlgorithmAnalysisinC第2版），M.A.Weiss著、陳越改編，人民郵件出版社，20