【845 計算機基礎綜合】

一、簡要說明

《計算機學科專業基礎綜合》涵蓋了計算機類專業的主要基礎課程，包括數據結構、操作系統等專業課程。要求考生比較系統地掌握上述專業課程的基本概念、基本原理和基本方法，能綜合運用所學的基本原理和基本方法分析、判斷和解決有關理論問題及實際問題。

二、考試題型

數據結構：填空題、選擇題、算法應用題、算法設計題

操作系統：填空題、簡答題、綜合題

三、考試內容詳細說明

【數據結構部分（75分）】

掌握數據結構的基本概念、基本原理和基本方法；掌握數據的邏輯結構、存儲結構及基本操作的實現，能夠對算法進行基本的時間及空間復雜度的分析；能夠運用數據結構的基本原理和方法進行問題的分析與求解，具備采用C、C++或相關語言設計與實現算法的能力。

主要內容：

（一）線性表

1. 線性表的定義和基本操作

2. 單鏈表、循環鏈表和雙向鏈表的定義及實現

3. 線性表的應用

（二）堆棧、隊列

1. 堆棧和隊列的基本概念

2. 堆棧和隊列的存儲結構、基本操作及實現

3. 堆棧和隊列的典型應用

（三）數組和串

1. 數組及串的定義

2. 數組的存儲結構及特殊矩陣的壓縮存儲

3. 串的存儲結構及模式匹配算法

（四）樹與二叉樹

1. 樹的基本概念、表示及存儲結構

2. 二叉樹

（1）二叉樹的定義及主要特性

（2）二叉樹的順存儲結構、基本操作及實現

（3）二叉樹的遍歷

（4）線索二叉樹的基本概念和構造

3. 二叉樹、樹和森林之間的相關轉換

4. 樹及二叉樹的應用

（1）哈夫曼樹的定義、構造及哈夫曼編碼

（五）圖

1. 圖的基本概念

2. 圖的存儲及基本操作

（1）鄰接矩陣

（2）鄰接表

3. 圖的遍歷

（1）深度優先搜索

（2）廣度優先搜索

4. 圖的基本應用

（1）最小生成樹

（2）最短路徑

（3）拓撲排序

（4）關鍵路徑

（六）查找

1. 查找的基本概念

2. 順序表、有序表和索引順序表的查找

3. 二叉查找樹、平衡二叉樹

4. 哈希表

（七）排序

1. 排序的基本概念

2. 插入排序

3. 希爾排序

4. 選擇排序

5. 堆排序

6. 冒泡排序

7. 快速排序

8. 歸并排序

9. 基數排序

10. 各種排序算法的性能

【操作系統部分（75分）】

了解操作系統在計算機系統中的作用、地位、發展和特點；理解操作系統的基本概念、原理，掌握操作系統設計方法與實現技術；能夠運用所學的操作系統原理、方法與技術分析問題和解決問題。

主要內容：

（一）操作系統概述

1. 操作系統的概念、特征、功能和提供的服務

2. 操作系統的發展與分類

（二）進程管理

1. 進程與線程的基本概念

2. 進程調度的基本概念、調度方式、調度算法

3. 進程同步的基本概念、臨界區、信號量、經典同步問題

4. 死鎖的基本概念、處理策略、死鎖預防和死鎖避免的算法、死鎖檢測

（三）內存管理

1. 內存管理基本概念

2. 內存交換及分頁、分段、段頁式內存分配管理

3. 虛擬內存

（1）虛擬內存的基本概念

（2）頁面置換算法

（3）頁面分配策略

（四）文件管理

1. 文件系統基礎

（1）文件概念

（2）文件的邏輯結構：順序文件、索引文件和索引順序文件

（3）目錄結構

（4）文件的訪問類型及訪問控制

2. 文件系統實現

（1）文件系統層次結構

（2）目錄實現

（3）文件實現

3. 磁盤組織與管理

（1）磁盤的結構

（2）磁盤的調度算法

（五）輸入輸出（I/O）管理

1. I/O管理概述

（1）I/O設備

（2）I/O管理功能

（3）I/O應用接口

（4）I/O控制方式

2. I/O調度

（1）I/O調度基本概念

（2）高速緩存與緩沖區

（3）設備分配與回收

四、主要參考書目

主要教材

[1] 數據結構，吳海燕等，浙江大學出版社，最新版

[2] 操作系統概念（第七版），A. Silbershatz等，高等教育出版社，最新版

參考書

[1] 數據結構 (C語言版)，嚴蔚敏，清華大學出版社，最新版

[2] 計算機操作系統，湯子瀛，西安電子科技大學，最新版

【845 計算機基礎綜合】

相關課程推薦