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

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

I.考試性質(zhì)

《計(jì)算機(jī)基礎(chǔ)綜合》考試是為中南大學(xué)計(jì)算機(jī)學(xué)院招收碩士研究生而設(shè)的具有選拔性質(zhì)的專(zhuān)業(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ì)錄取者在研究生階段的研究工作的順利展開(kāi)做好鋪墊。

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é)科的專(zhuān)業(yè)術(shù)語(yǔ);

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)編寫(xiě)結(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ì)問(wèn)題或性能問(wèn)題，能夠發(fā)現(xiàn)解決問(wèn)題方案，提出解決思路和方案;

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

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

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

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

本試卷滿(mǎn)分為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ù)語(yǔ)

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

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

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.樹(shù)和二叉樹(shù)

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

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

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

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

5.圖

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

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

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

6.查找

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

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

3)平衡二叉樹(shù)及插入時(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)的分類(lèi)。操作系統(tǒng)的發(fā)展歷程。

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

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

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

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

2.進(jìn)程管理

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

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

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

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

3)進(jìn)程同步

進(jìn)程同步互斥基本概念。臨界資源的基本概念和使用原則。實(shí)現(xiàn)同步互斥的軟硬件方法。經(jīng)典同步問(wèn)題。信號(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ū)管理方案。

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

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

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

4.文件系統(tǒng)

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

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

2)文件的管理

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

3)磁盤(pán)存儲(chǔ)管理

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

4)文件性能管理

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

5.設(shè)備管理

1)I/0設(shè)備

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

2)緩沖管理

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

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

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

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

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

VI.參考教材和書(shū)目

1. 《數(shù)據(jù)結(jié)構(gòu)》(C語(yǔ)言版),嚴(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