1
2
3
4
一、考試基本要求及適用范圍概述
計算機基礎理論考試主要包括數據結構和操作系統兩部分。
數據結構部分要求考生掌握數據結構的基本概念和術語;掌握 包括線性表、棧和隊列、 串、數組和特殊矩陣、樹和二叉樹以及圖 在內的各種數據結構的基本概念、邏輯結構與存儲結構， 以及在這 些結構的基礎上的相關算法實現;能夠針對具體問題選擇合適的數 據結構抽象建模，設計合適的存儲結構，并采用 C/C++、Java、Python 或類 C 語言描述等程序設計語言基本運算的算法實現;掌握各種查 找、排序算法;能夠對基本算法進行復雜度分析。
操作系統部分主要考察學生對操作系統基本概念、結構、策略， 以及一些基本的算法、處理過程的理解與掌握;對構成系統的進程 管理、存儲管理、設備管理、文件系統等各模塊的工作機理及設計 方法的掌握。重點考察操作系統的設計方法與實現技術，要求學生 能夠運用操作系統原理、方法與技術分析問題和解決問題。
本考試大綱適用于計算機科學與技術、農業信息化技術專業。
二、考試形式 閉卷 筆試
三、考試內容和要求
數據結構和操作系統各占約50%，具體考試內容和要求如下：
第一部分 數據結構
1. 數據結構概述
l 掌握數據結構的基本概念和術語，包括數據、數據元素、數
據項、數據對象、數據結構、數據的邏輯結構、數據的存儲 結構、數據類型、抽象數據類型;
l 掌握算法特性、算法的時間復雜度分析、算法的空間復雜度 分析。
2.線性表
l 理解線性表的基本概念;
l 掌握線性表的順序存儲結構及其算法實現;
l 掌握線性表的鏈式存儲結構及其算法實現，包括單鏈表、雙 向鏈表、循環鏈表。
3.棧和隊列
l 掌握棧及其特性，理解棧的抽象數據類型;
l 掌握順序棧及其基本算法實現、鏈棧及其基本算法實現;
l 理解函數調用、遞歸的實現過程、能夠利用棧解決表達式求 值、括號匹配等問題;
l 掌握隊列及其特性，理解隊列的抽象數據類型;
l 掌握循環隊列及其基本運算實現、鏈隊列及其基本運算實現;
l 能夠利用隊列解決銀行排隊、二叉樹層序遍歷、圖的廣度優 先遍歷等問題。
4.串、數組和廣義表
l 掌握串的基本概念及操作、 串的定長順序存儲及基本運算;
l 掌握數組的定義及操作、數組的順序存儲、特殊矩陣的壓縮 存儲、隨機稀疏矩陣的壓縮存儲;
l 理解廣義表的基本概念
5.樹和二叉樹
l 掌握樹的定義及基本術語;
l 掌握二叉樹的定義、二叉樹的性質以及二叉樹的存儲結構;
l 掌握二叉樹遍歷方法，包括二叉樹的遞歸遍歷、二叉樹的非 遞歸遍歷，并能夠應用二叉樹遍歷算法解決問題;
l 掌握線索二叉樹的定義和存儲結構、二叉樹的線索化、線索 二叉樹中結點的前驅和后繼查找方法。
l 掌握樹的存儲、森林的存儲結構、樹和森林的遍歷、樹、森 林和二叉樹的相互轉換;
l 掌握哈夫曼樹的定義及特性，并能應用哈夫曼樹解決實際問 題。
6.圖
l 掌握圖的基本概念，包括圖、無向圖、有向圖、完全圖、圖 的連通性等;
l 掌握圖的鄰接矩陣和鄰接表等存儲結構;
l 掌握圖的深度優先和圖的廣度優先搜索遍歷算法;
l 掌握最小生成樹算法(Kruskal 算法和Prim 算法)、求某個頂 點(單源點)到其余各頂點的最短路徑(Dijkstra 算法)、拓 撲排序、關鍵路徑。
7.排序
l 理解排序的基本概念;
l 掌握插入排序(包括直接插入排序、希爾排序)、交換排序(包 冒泡排序、快速排序)、選擇排序(包括簡單選擇排序、堆排
序)、歸并排序、基數排序等基本排序算法及其復雜度分析。
8. 查找
l 理解查找的基本概念、查找成功和查找失敗的平均查找長度;
l 掌握順序表的查找、有序表的折半查找;
l 掌握二叉排序樹(包括二次排序樹的定義和特點、二叉排序 樹的創建、插入、刪除結點)，掌握平衡二叉樹的定義;
l 掌握哈希函數的確定方法、處理沖突的方法。
第二部分 操作系統
1.操作系統概述
l 掌握操作系統的計算機體系中的地位和作用;
l 計算機的發展過程中出現的各種不同類型的操作系統以及它 們的特點， 了解常用的操作系統以及操作系統的現狀;
l 掌握操作系統的并發、共享、虛擬、異步等基本特征以及在 操作系統中的一些重要的概念，如并行、并發、時間片等;
l 掌握操作系統為用戶和應用程序所提供的各種服務、接口和 系統調用等功能;
l 掌握操作系統結構設計以及它們的特征和優缺點。 2.進程的描述與控制
l 掌握進程的基本概念，包括進程的結構特征、PCB、作業、任 務等，掌握進程的狀態以及轉換時機;
l 掌握進程控制的機制，包括創建、終止、阻塞、喚醒等;
l 掌握進程同步的意義、概念和方法;掌握臨界區的概念以及 進程同步的四個準則;
l 掌握生產者-消費者問題、哲學家進餐問題、讀者-寫者問題 等經典進程同步問題以及用信號量機制來解決進程同步問題 的方法，能熟練應用同步信號量和互斥信號量;
l 理解管程機制;
l 掌握進程通信的方法，包括共享存儲系統、消息傳遞系統、 管道;
l 掌握線程的概念以及線程和進程的區別;掌握用戶和內核線 程的定義、區別;掌握多線程模式下用戶和內核線程的關系。
3.處理機調度與死鎖
l 掌握處理機調度的基本類型、基本概念以及調度準則、衡量 調度算法的指標;
l 掌握先來先服務、短作業(進程)優先、高響應比優先、時 間片輪轉等基本的調度算法以及搶占式調度和非搶占式調度 的區別;
l 理解多級隊列調度和多級反饋隊列調度的算法。
l 掌握死鎖的產生原因、定義和四個必要條件;
l 掌握處理死鎖的基本方法;掌握用銀行家算法來避免死鎖; 理解資源分配圖以及死鎖的檢測和解除機制。
4.存儲器管理
l 理解存儲管理中的基本概念，包括存儲器的層次結構、地址 綁定、邏輯與物理地址空間、動態重定位、動態裝入、動態 鏈接、交換、碎片等;
l 掌握存儲管理的三種主要的方法：連續分配、分頁和分段存...更多見官網
原標題：關于調整我校部分專業2025年碩士研究生招生考試初試科目的公告
文章來源：https://yanjiusheng.hebau.edu.cn/info/1110/4305.htm
