2024年電子科技大學非全日制研究生招生考試《計算機專業(yè)基礎(chǔ)》考試大綱

　　本科目包括《數(shù)據(jù)結(jié)構(gòu)》和《計算機操作系統(tǒng)》兩門課程，總分 150 分，兩門課程各占 75 分

　　《數(shù)據(jù)結(jié)構(gòu)》

　　一、總體要求

　　《數(shù)據(jù)結(jié)構(gòu)》是計算機程序設計的重要理論技術(shù)基礎(chǔ)，是計算機科學與技術(shù)學科的核心課程要求：

　　1. 理解數(shù)據(jù)結(jié)構(gòu)的基本概念;掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其差異，以及各種基本操作的實現(xiàn)。

　　2. 掌握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠分析算法的時間復雜度與空間復雜度。

　　3. 能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和算法策略進行問題求解，具備采用 C 或 C++或 JAVA 語言設計與實現(xiàn)算法的能力。

　　二、內(nèi)容

　　1. 數(shù)據(jù)結(jié)構(gòu)及算法的相關(guān)概念和術(shù)語

　　(1) 數(shù)據(jù)結(jié)構(gòu)及算法的概念

　　(2) 數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)

　　(3) 算法的定義及特性

　　(4) 算法時間復雜度和空間復雜度的分析方法2.線性表

　　(1) 線性表的定義

　　(2) 線性表的基本操作及在順序存儲及鏈式存儲上的實現(xiàn)

　　(3) 各種變形鏈表(循環(huán)鏈表、雙向鏈表、帶頭結(jié)點的鏈表等)的表示和基本操作的實現(xiàn)

　　(4) 遞歸過程的特點及實現(xiàn)方法

　　(5) 棧和隊列的基本概念;棧和隊列的順序存儲結(jié)構(gòu)、鏈式儲存結(jié)構(gòu)及其存儲特點

　　(6) 棧和隊列的應用

　　(7) 循環(huán)隊列的判滿、判空方法

　　(8) 特殊矩陣的壓縮儲存

　　3. 廣義表的基本概念、存儲結(jié)構(gòu)和基本操作

　　4. 樹和二叉樹

　　(1) 樹與森林的基本概念

　　(2) 樹與森林的存儲結(jié)構(gòu)及遍歷

　　(3) 二叉樹的定義及 6 大性質(zhì)

　　(4) 二叉樹的順序儲存與鏈式儲存結(jié)構(gòu)

　　(5) 二叉樹的先序、中序、后序三種遍歷方式的關(guān)系以及實現(xiàn);層序遍歷的實現(xiàn)

　　(6) 線索二叉樹的基本概念與構(gòu)造方法

　　(7) 樹與二叉樹的應用：二叉排序樹;二叉平衡樹;哈夫曼樹與哈夫曼編碼 5.圖

　　(1) 圖的基本概念和術(shù)語

　　(2) 圖的存儲結(jié)構(gòu)：鄰接矩陣、鄰接表、逆鄰接表

　　(3) 遍歷算法：深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法

　　(4) 應用：最小生成樹;最短路徑，拓撲排序和關(guān)鍵路徑6.查找

　　(1) 查找的基本概念;靜態(tài)查找與動態(tài)查找

　　(2) 順序查找、折半查找、索引查找

　　(3) 哈希查找

　　哈希函數(shù)的基本構(gòu)造方法，解決地址沖突的基本策略

　　(4) 各種查找算法的時間復雜度和空間復雜度7.排序

　　(1) 排序的基本概念

　　(2) 插入排序

　　(3) 簡單選擇排序

　　(4) 希爾排序

　　(5) 快速排序

　　(6) 堆排序

　　(7) 歸并排序

　　(8) 基數(shù)排序

　　(9) 排序算法的比較

　　其中算法題分為閱讀、修改和編寫算法三類：

　　(1) 閱讀算法：閱讀指定算法，回答使用的數(shù)據(jù)結(jié)構(gòu)、算法實現(xiàn)的功能或執(zhí)行的結(jié)果;

　　(2) 修改算法：閱讀指定算法，指出算法的錯誤并修正;指出算法的不足并改進;按給定功能填寫 算法空缺部分;

　　(3) 編寫算法：根據(jù)算法功能要求，選擇或者設計合適的數(shù)據(jù)結(jié)構(gòu)，用程序設計語言編寫算法，實 現(xiàn)指定功能。

　　以上皆可分析給定或者設計的算法時空復雜度。

　　操作系統(tǒng)部分

　　一、總體要求

　　主要考察學生對操作系統(tǒng)基本概念、原理的理解程度，重點考察操作系統(tǒng)的設計方法與實現(xiàn)技術(shù)，

　　同時能夠具備運用所學的操作系統(tǒng)原理、方法與技術(shù)分析問題和解決問題的能力。 二、內(nèi)容

　　1. 操作系統(tǒng)的基本概念

　　1) 批處理與多道程序設計

　　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)度算法(先來先服務、短進程優(yōu)先、時間片輪轉(zhuǎn)、基于優(yōu)先級的調(diào)度算法等)

　　5) 死鎖:死鎖的基本概念，死鎖定理、死鎖預防、死鎖避免與處理死鎖的基本方法、銀行家

　　算法

　　6) 綜合應用：生產(chǎn)者消費者問題、讀者和寫者問題、哲學家進餐問題等

　　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ū)分配算法(首 次適應算法、循環(huán)首次適應算法、最佳適應法、最壞適應法等)

　　4) 段式管理與頁式管理：段、頁、碎片等基本概念、段式管理與頁式管理機制

　　5) 虛擬內(nèi)存：局部性原理、虛擬內(nèi)存概念、請求分段與請求分頁、段頁式管理、段頁式地址 結(jié)構(gòu)與地址轉(zhuǎn)換、頁面置換算法(OPT、先進先出、LRU、Clock、改進型 Clock 置換)、抖動

　　4. 設備管理

　　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) 設備分配、設備處理、虛擬設備，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ù)：位示圖、空閑鏈表、索引