中南大學2024研究生入學考試大綱：計算機基礎綜合

本考試大綱由計算機學院研教授委員會于2023年7月22日通過。

I.考試性質

《計算機基礎綜合》考試是為中南大學計算機學院招收碩士研究生而設的具有選拔性質的專業(yè)考試科目，其目的是科學、公平、有效地測試學生掌握大學本科階段數(shù)據結構和操作系統(tǒng)基本概念以及運用能力，評價的標準是高等院校本科畢業(yè)生能達到的及格或及格以上水平，以保證被錄取者對數(shù)據結構和操作系統(tǒng)的相關知識有較好的掌握，對錄取者在研究生階段的研究工作的順利展開做好鋪墊。

II.考查目標

計算機基礎綜合考試涵蓋數(shù)據結構、操作系統(tǒng)等高等學校課程。數(shù)據結構考試要求考生：

1、熟悉數(shù)據結構中的基本概念，準確、恰當?shù)厥褂帽緦W科的專業(yè)術語;

2、掌握計算機能處理的數(shù)據結構的特性;

3、能夠為所處理的數(shù)據選擇適當?shù)倪壿嫿Y構、存儲結構;

4、能夠基于數(shù)據結構編寫結構清楚和正確易讀的算法;

5、初步掌握算法的時間分析和空間分析的技術。

操作系統(tǒng)要求考生：

1.理解和掌握操作系統(tǒng)的基本概念、其功能的基本原理及實現(xiàn)技術或算法;

2.掌握設計和實現(xiàn)操作系統(tǒng)的方法，理解操作系統(tǒng)內核;

3.針對操作系統(tǒng)中的設計問題或性能問題，能夠發(fā)現(xiàn)解決問題方案，提出解決思路和方案;

4.能夠將操作系統(tǒng)中的設計技術、算法和安全措施應用到實際問題中;

5.綜合應用操作系統(tǒng)中的方法和技術，培養(yǎng)解決復雜系統(tǒng)問題的創(chuàng)新能力。

Ⅲ.考試形式和試卷結構

1、試卷滿分及考試時間

本試卷滿分為150分，考試時間為180分鐘

2、答題方式

答題方式為閉卷，筆試。

3、試卷內容結構

數(shù)據結構 約50 %

操作系統(tǒng) 約50 %

IV.試卷題型結構

單項選擇題

填空題

名詞解釋

簡答題

計算題

應用題

算法設計與分析題

V.考查內容

一、數(shù)據結構

1.數(shù)據結構有關的概念和術語

1)數(shù)據結構;

2)抽象數(shù)據類型;

3)算法、算法設計的要求、算法效率的度量。

2.鏈表、棧、隊列、串

1)鏈表、靜態(tài)鏈表(單鏈表、雙向鏈表、循環(huán)鏈表)及相關算法;

2)棧及順序棧、鏈棧的進棧、出棧等算法;

3)隊列及順序隊列、鏈隊列的進隊、出隊等算法;

4)棧和隊列的應用。

5)串的概念、存儲、運算及串的模式匹配算法。

3.數(shù)組和廣義表

1)數(shù)組的定義、表示和實現(xiàn);

2)特殊矩陣和稀疏矩陣的存儲及操作;

3)廣義表的定義、存儲結構及相關操作。

4.樹和二叉樹

1)二叉樹的概念、相關術語、性質及存儲結構;

2)二叉樹的遍歷算法及應用;

3)樹(森林)的存儲結構及遍歷方法;

4)哈夫曼(Huffman)樹的構造及應用。

5.圖

1)圖的概念、相關術語及存儲結構;

2)圖的遍歷算法及應用;

3)最小生成樹、最短路徑、拓撲排序、關鍵路徑等算法。

6.查找

1)順序查找、索引順序表查找、二分查找;

2)二叉排序樹的查找、插入及刪除算法;

3)平衡二叉樹及插入時的平衡方法;

4)哈希函數(shù)的構造方法、沖突處理的方法、哈希表的查找及其分析;

5) 查找成功及失敗的平均查找長度。

7.內部排序

直接插入排序、希爾排序、冒泡排序、簡單選擇排序、快速排序、堆排序、歸并排序、基數(shù)排序的算法思想、復雜度分析、穩(wěn)定性以及它們之間的比較。

二、操作系統(tǒng)

1.操作系統(tǒng)基礎知識

1)操作系統(tǒng)概論

操作系統(tǒng)的定義。操作系統(tǒng)的作用和特征。操作系統(tǒng)的分類。操作系統(tǒng)的發(fā)展歷程。

2)操作系統(tǒng)結構

典型操作系統(tǒng)。操作系統(tǒng)的體系結構。中斷和陷入。特權指令和非特權指令。內核態(tài)與用戶態(tài)。操作系統(tǒng)的主要功能。

3)操作系統(tǒng)啟動和引導

一個程序的典型執(zhí)行流程。操作系統(tǒng)設計的主要概念。

2.進程管理

1)進程/線程基本概念

進程的定義與特征。進程狀態(tài)與轉換。進程控制塊和進程創(chuàng)建、撤銷、阻塞、喚醒。進程與程序的區(qū)別與聯(lián)系。線程機制及線程的實現(xiàn)方式。

2)進程/作業(yè)調度

調度算法的設計準則和衡量指標。調度時機和調度過程。典型調度算法。多處理器調度。實時調度。

3)進程同步

進程同步互斥基本概念。臨界資源的基本概念和使用原則。實現(xiàn)同步互斥的軟硬件方法。經典同步問題。信號量機制。管程機制。鎖和條件變量。進程通信。共享內存。消息傳遞。管道通信。RPC。

4)死鎖

死鎖的基本概念。死鎖產生的必要條件。資源分配圖。死鎖的預防。死鎖的避免。死鎖的檢測與解除。

3.內存管理

1)內存基本概念

內存管理的功能。內存地址空間。程序的裝入與鏈接。重定位和交換技術。局部性原理。

連續(xù)分區(qū)管理方案。

固定分區(qū)分配。動態(tài)分區(qū)分配。緊湊。動態(tài)重定位分區(qū)分配?？臻e分區(qū)表和已分分區(qū)表。分區(qū)的分配與回收。

3)離散分區(qū)管理方案。

分頁和請求分頁管理方案。缺頁中斷處理。頁表與頁表項設計。分段和請求分段管理方案。段頁式和請求段頁式管理方案。地址轉換過程。

4)內存管理方案性能設計

有效訪問時間。頁面置換算法。缺頁率。工作集理論。抖動現(xiàn)象和解決抖動的方法。內存的保護和共享。

4.文件系統(tǒng)

1)文件系統(tǒng)基本概念

文件、文件目錄和目錄文件。文件的存儲介質。文件的訪問方法。文件的邏輯結構和物理結構。

2)文件的管理

文件控制塊和索引節(jié)點。文件和目錄的操作。常見目錄結構。目錄查詢技術。

3)磁盤存儲管理

文件讀寫時間。磁盤尋道算法?？臻e空間管理。磁盤容錯技術。

4)文件性能管理

文件訪問一致性。文件訪問速度提高措施。文件的存取控制。文件的共享。文件的保護。文件系統(tǒng)的設計。

5.設備管理

1)I/0設備

輸入/輸出設備的特性。I/0軟件層次結構。設備的分類。設備的控制方式。

2)緩沖管理

單緩沖、雙緩沖、循環(huán)緩沖和緩沖池管理。緩沖引入的原因和性能分析。

3)設備分配及處理技術

設備分配的數(shù)據結構。設備分配過程與回收。設備分配應考慮的問題。設備獨立性/無關性。Spooling技術。設備驅動程序。中斷處理程序。

6.操作系統(tǒng)前沿技術

嵌入式操作系統(tǒng)。虛擬化與容器技術。操作系統(tǒng)安全。操作系統(tǒng)設計。

VI.參考教材和書目

1. 《數(shù)據結構》(C語言版),嚴蔚敏等編著，清華大學出版社，2012.

2.《計算機操作系統(tǒng)教程》(第4版),張堯學等編著，清華大學出版社，2013.10

3.《操作系統(tǒng)概念》,Abraham Silberschatz等著， Higher Education Press,2018.7