中南大學(xué)2024研究生入學(xué)考試大綱：計(jì)算機(jī)基礎(chǔ)綜合

本考試大綱由計(jì)算機(jī)學(xué)院研教授委員會(huì)于2023年7月22日通過。

I.考試性質(zhì)

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

II.考查目標(biāo)

計(jì)算機(jī)基礎(chǔ)綜合考試涵蓋數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)等高等學(xué)校課程。數(shù)據(jù)結(jié)構(gòu)考試要求考生：

1、熟悉數(shù)據(jù)結(jié)構(gòu)中的基本概念，準(zhǔn)確、恰當(dāng)?shù)厥褂帽緦W(xué)科的專業(yè)術(shù)語;

2、掌握計(jì)算機(jī)能處理的數(shù)據(jù)結(jié)構(gòu)的特性;

3、能夠?yàn)樗幚淼臄?shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu);

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

5、初步掌握算法的時(shí)間分析和空間分析的技術(shù)。

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

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

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

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

4.能夠?qū)⒉僮飨到y(tǒng)中的設(shè)計(jì)技術(shù)、算法和安全措施應(yīng)用到實(shí)際問題中;

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

Ⅲ.考試形式和試卷結(jié)構(gòu)

1、試卷滿分及考試時(shí)間

本試卷滿分為150分，考試時(shí)間為180分鐘

2、答題方式

答題方式為閉卷，筆試。

3、試卷內(nèi)容結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu) 約50 %

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

IV.試卷題型結(jié)構(gòu)

單項(xiàng)選擇題

填空題

名詞解釋

簡(jiǎn)答題

計(jì)算題

應(yīng)用題

算法設(shè)計(jì)與分析題

V.考查內(nèi)容

一、數(shù)據(jù)結(jié)構(gòu)

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

1)數(shù)據(jù)結(jié)構(gòu);

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

3)算法、算法設(shè)計(jì)的要求、算法效率的度量。

2.鏈表、棧、隊(duì)列、串

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

2)棧及順序棧、鏈棧的進(jìn)棧、出棧等算法;

3)隊(duì)列及順序隊(duì)列、鏈隊(duì)列的進(jìn)隊(duì)、出隊(duì)等算法;

4)棧和隊(duì)列的應(yīng)用。

5)串的概念、存儲(chǔ)、運(yùn)算及串的模式匹配算法。

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

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

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

3)廣義表的定義、存儲(chǔ)結(jié)構(gòu)及相關(guān)操作。

4.樹和二叉樹

1)二叉樹的概念、相關(guān)術(shù)語、性質(zhì)及存儲(chǔ)結(jié)構(gòu);

2)二叉樹的遍歷算法及應(yīng)用;

3)樹(森林)的存儲(chǔ)結(jié)構(gòu)及遍歷方法;

4)哈夫曼(Huffman)樹的構(gòu)造及應(yīng)用。

5.圖

1)圖的概念、相關(guān)術(shù)語及存儲(chǔ)結(jié)構(gòu);

2)圖的遍歷算法及應(yīng)用;

3)最小生成樹、最短路徑、拓?fù)渑判?、關(guān)鍵路徑等算法。

6.查找

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

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

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

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

5) 查找成功及失敗的平均查找長(zhǎng)度。

7.內(nèi)部排序

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

二、操作系統(tǒng)

1.操作系統(tǒng)基礎(chǔ)知識(shí)

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

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

2)操作系統(tǒng)結(jié)構(gòu)

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

3)操作系統(tǒng)啟動(dòng)和引導(dǎo)

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

2.進(jìn)程管理

1)進(jìn)程/線程基本概念

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

2)進(jìn)程/作業(yè)調(diào)度

調(diào)度算法的設(shè)計(jì)準(zhǔn)則和衡量指標(biāo)。調(diào)度時(shí)機(jī)和調(diào)度過程。典型調(diào)度算法。多處理器調(diào)度。實(shí)時(shí)調(diào)度。

3)進(jìn)程同步

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

4)死鎖

死鎖的基本概念。死鎖產(chǎn)生的必要條件。資源分配圖。死鎖的預(yù)防。死鎖的避免。死鎖的檢測(cè)與解除。

3.內(nèi)存管理

1)內(nèi)存基本概念

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

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

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

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

分頁和請(qǐng)求分頁管理方案。缺頁中斷處理。頁表與頁表項(xiàng)設(shè)計(jì)。分段和請(qǐng)求分段管理方案。段頁式和請(qǐng)求段頁式管理方案。地址轉(zhuǎn)換過程。

4)內(nèi)存管理方案性能設(shè)計(jì)

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

4.文件系統(tǒng)

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

文件、文件目錄和目錄文件。文件的存儲(chǔ)介質(zhì)。文件的訪問方法。文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。

2)文件的管理

文件控制塊和索引節(jié)點(diǎn)。文件和目錄的操作。常見目錄結(jié)構(gòu)。目錄查詢技術(shù)。

3)磁盤存儲(chǔ)管理

文件讀寫時(shí)間。磁盤尋道算法?？臻e空間管理。磁盤容錯(cuò)技術(shù)。

4)文件性能管理

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

5.設(shè)備管理

1)I/0設(shè)備

輸入/輸出設(shè)備的特性。I/0軟件層次結(jié)構(gòu)。設(shè)備的分類。設(shè)備的控制方式。

2)緩沖管理

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

3)設(shè)備分配及處理技術(shù)

設(shè)備分配的數(shù)據(jù)結(jié)構(gòu)。設(shè)備分配過程與回收。設(shè)備分配應(yīng)考慮的問題。設(shè)備獨(dú)立性/無關(guān)性。Spooling技術(shù)。設(shè)備驅(qū)動(dòng)程序。中斷處理程序。

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

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

VI.參考教材和書目

1. 《數(shù)據(jù)結(jié)構(gòu)》(C語言版),嚴(yán)蔚敏等編著，清華大學(xué)出版社，2012.

2.《計(jì)算機(jī)操作系統(tǒng)教程》(第4版),張堯?qū)W等編著，清華大學(xué)出版社，2013.10

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