2022年電子科技大學(xué)碩士研究生《計算機專業(yè)基礎(chǔ)》初試考試大綱
本科目包括《數(shù)據(jù)結(jié)構(gòu)》和《計算機操作系統(tǒng)》兩門課程，總分150分，兩門課程各占75分
《數(shù)據(jù)結(jié)構(gòu)》
一、總體要求
《數(shù)據(jù)結(jié)構(gòu)》是計算機程序設(shè)計的重要理論技術(shù)基礎(chǔ)，是計算機科學(xué)與技術(shù)學(xué)科的核心課程。要求：
1.理解數(shù)據(jù)結(jié)構(gòu)的基本概念；掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其差異，以及各種基本操作的實現(xiàn)。
2.掌握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠分析算法的時間復(fù)雜度與空間復(fù)雜度。
3.能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和算法策略進行問題求解，具備采用C 或C++或JAVA 語言設(shè)計與實現(xiàn)算法的能力。
二、內(nèi)容
1. 數(shù)據(jù)結(jié)構(gòu)及算法的相關(guān)概念和術(shù)語
?。?） 數(shù)據(jù)結(jié)構(gòu)及算法的概念
?。?） 數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)
?。?） 算法的定義及特性
?。?） 算法時間復(fù)雜度和空間復(fù)雜度的分析方法
2．線性表
（1） 線性表的定義
?。?） 線性表的基本操作及在順序存儲及鏈?zhǔn)酱鎯ι系膶崿F(xiàn)
（3） 各種變形鏈表（循環(huán)鏈表、雙向鏈表、帶頭結(jié)點的鏈表等）的表示和基本操作的實現(xiàn)
?。?） 遞歸過程的特點及實現(xiàn)方法
（5） 棧和隊列的基本概念；棧和隊列的順序存儲結(jié)構(gòu)、鏈?zhǔn)絻Υ娼Y(jié)構(gòu)及其存儲特點
?。?） 棧和隊列的應(yīng)用
（7） 循環(huán)隊列的判滿、判空方法
?。?） 特殊矩陣的壓縮儲存
3．廣義表的基本概念、存儲結(jié)構(gòu)和基本操作
4．樹和二叉樹
?。?） 樹與森林的基本概念
?。?） 樹與森林的存儲結(jié)構(gòu)及遍歷
?。?） 二叉樹的定義及6大性質(zhì)
?。?） 二叉樹的順序儲存與鏈?zhǔn)絻Υ娼Y(jié)構(gòu)
?。?） 二叉樹的先序、中序、后序三種遍歷方式的關(guān)系以及實現(xiàn)；層序遍歷的實現(xiàn)
?。?） 線索二叉樹的基本概念與構(gòu)造方法
?。?） 樹與二叉樹的應(yīng)用：二叉排序樹；二叉平衡樹；哈夫曼樹與哈夫曼編碼
5．圖
?。?） 圖的基本概念和術(shù)語
?。?） 圖的存儲結(jié)構(gòu)：鄰接矩陣、鄰接表、逆鄰接表
?。?） 遍歷算法：深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法
?。?） 應(yīng)用：最小生成樹；最短路徑，拓撲排序和關(guān)鍵路徑
6．查找
?。?） 查找的基本概念；靜態(tài)查找與動態(tài)查找
?。?） 順序查找、折半查找、索引查找
（3） 哈希查找
哈希函數(shù)的基本構(gòu)造方法，解決地址沖突的基本策略
（4） 各種查找算法的時間復(fù)雜度和空間復(fù)雜度
7．排序
?。?） 排序的基本概念
?。?） 插入排序
?。?） 簡單選擇排序
?。?） 希爾排序
?。?） 快速排序
（6） 堆排序
?。?） 歸并排序
?。?） 基數(shù)排序
（9） 排序算法的比較其中算法題分為閱讀、修改和編寫算法三類：
(1)閱讀算法：閱讀指定算法，回答使用的數(shù)據(jù)結(jié)構(gòu)、算法實現(xiàn)的功能或執(zhí)行的結(jié)果；
(2)修改算法：閱讀指定算法，指出算法的錯誤并修正；指出算法的不足并改進；按給定功能填寫算法空缺部分；
(3)編寫算法：根據(jù)算法功能要求，選擇或者設(shè)計合適的數(shù)據(jù)結(jié)構(gòu)，用程序設(shè)計語言編寫算法，實現(xiàn)指定功能。
以上皆可分析給定或者設(shè)計的算法時空復(fù)雜度。
操作系統(tǒng)部分一、總體要求主要考察學(xué)生對操作系統(tǒng)基本概念、原理的理解程度，重點考察操作系統(tǒng)的設(shè)計方法與實現(xiàn)技術(shù)，同時能夠具備運用所學(xué)的操作系統(tǒng)原理、方法與技術(shù)分析問題和解決問題的能力。
二、內(nèi)容
1. 操作系統(tǒng)的基本概念
1) 批處理與多道程序設(shè)計
2) 分時系統(tǒng)與實時系統(tǒng)
3) 操作系統(tǒng)的基本類型與特征
4) 并發(fā)與并行的概念
5) 操作系統(tǒng)的層次結(jié)構(gòu)與功能模塊
6) 程序的并發(fā)執(zhí)行與順序執(zhí)行
2. 進程管理
1) 進程: 進程控制塊、進程的幾種基本狀態(tài)與狀態(tài)轉(zhuǎn)換（進程的創(chuàng)建、進程的終止、進程的阻塞與喚醒、進程的掛起與激活等）
2) 進程的同步與互斥：臨界資源、臨界區(qū)、進程同步與互斥問題、信號量機制以及P、V操作、管程機制
3) 進程間通信：進程通信的類型（直接通信和間接通信方式）、消息傳遞系統(tǒng)中的幾個問題、消息緩沖隊列通信機制
4) 線程與進程的調(diào)度:線程與進程的基本概念，調(diào)度的類型、調(diào)度隊列模型、調(diào)度方式、進程調(diào)度算法（先來先服務(wù)、短進程優(yōu)先、時間片輪轉(zhuǎn)、基于優(yōu)先級的調(diào)度算法等）
5) 死鎖:死鎖的基本概念，死鎖定理、死鎖預(yù)防、死鎖避免與處理死鎖的基本方法、銀行家
算法
6) 綜合應(yīng)用：生產(chǎn)者消費者問題、讀者和寫者問題、哲學(xué)家進餐問題等
3. 內(nèi)存管理
1) 內(nèi)存管理的需求：重定位、內(nèi)存保護、內(nèi)存共享
2) 程序的裝入和鏈接：靜態(tài)裝入和可重定位裝入、靜態(tài)鏈接、動態(tài)鏈接、運行時動態(tài)鏈接。
3) 分區(qū)存儲管理：分區(qū)方式（單一連續(xù)分區(qū)、固定分區(qū)、可變式分區(qū)）、分區(qū)分配算法（首次適應(yīng)算法、循環(huán)首次適應(yīng)算法、最佳適應(yīng)法、最壞適應(yīng)法等）
4) 段式管理與頁式管理：段、頁、碎片等基本概念、段式管理與頁式管理機制
5) 虛擬內(nèi)存：局部性原理、虛擬內(nèi)存概念、請求分段與請求分頁、段頁式管理、段頁式地址結(jié)構(gòu)與地址轉(zhuǎn)換、頁面置換算法（OPT、先進先出、LRU、Clock、改進型Clock置換）、抖動
4. 設(shè)備管理
1) I/O系統(tǒng)的：基本概念、I/O控制方式（程序I/0、中斷、DMA、通道）、相關(guān)數(shù)據(jù)結(jié)構(gòu)、緩沖管理（單緩沖、雙緩沖、循環(huán)緩沖、緩沖池）
2) 磁盤管理與磁盤調(diào)度算法：SSTF算法，SCAN算法，CSCAN算法，N-STEP-SCAN算法，F(xiàn)SCAN 算法
3) 設(shè)備分配、設(shè)備處理、虛擬設(shè)備，Spooling系統(tǒng)
5. 文件系統(tǒng)
1) 基本概念：文件和文件系統(tǒng)、目錄、文件結(jié)構(gòu)的物理結(jié)構(gòu)和邏輯結(jié)構(gòu)（順序文件、索引順
序文件、索引文件、HASH文件）、文件共享（基于索引節(jié)點、基于符號鏈接實現(xiàn)文件共享）
2) 外存分配方法：連續(xù)分配、鏈接分配、索引分配
3) 目錄管理：單級目錄、二級目錄、多級目錄
4) 文件存儲空間的管理技術(shù)：位示圖、空閑鏈表、索引
