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