2021年全國碩士研究生入學考試

湖北師范大學自命題考試科目考試大綱

（科目名稱：計算機軟件技術基礎      科目代碼:826）

一、考查目標

計算機軟件技術基礎科目考試內容包括C語言程序設計和數據結構兩個部分，它們是計算機各個專業的基礎。其中，C語言程序設計要求考生系統掌握程序設計的基本數據類型、程序的基本結構、函數、數組、指針和結構體的基本概念和使用方法；數據結構部分要求考生掌握各種基本類型的概念、特征、操作、存儲表示和基本應用，各種基本查找表的概念、特征以及查找方法，基本的排序方法；注重考查考生運用相關理論和方法分析、解決實際問題的能力。

二、考試形式與試卷結構

（一）試卷成績及考試時間

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

（二）答題方式

答題方式為閉卷、筆試。

（三）試卷題型結構

C語言程序設計（90分）

選擇題：10小題，每小題3分，共30分

填空題：10小題，每小題2分，共20分

閱讀程序題：5小題，每小題4分，共20分

編程題：2小題，每小題10分，共20分

數據結構（60分）

選擇題：10小題，每小題3分，共30分

分析題：2小題，每小題10分，共20分

算法設計題：1小題，每小題10分，共10分

（四）主要參考書目

1.《C程序設計》（第五版），譚浩強著，清華大學出版社，2017

2.《數據結構（C語言版）》（第2版），嚴蔚敏等編著，人民郵電出版社出版社，2015

三、考查范圍

（一）考查目標

C語言程序設計：

1、C語言程序科目要求考生比較系統地掌握C語言的基礎理論和基本知識。

2、熟練掌握C語言的基本語法，熟悉結構化程序設計的編程思想，能運用C語言設計應用程序以解決實際問題。

數據結構：

1、理解數據的基本概念；掌握數據的邏輯結構、存儲及其差異，以及各種基本操作的實現。

2、掌握基本的數據處理原來和方法的基礎上，能夠簡單設計算法，并對其進行基本的時間復雜度與空間復雜度的分析。

3、能夠選擇合適的數據結構和算法進行問題求解，具備采用C語言設計與實現算法的能力。

（二）考試內容

C語言程序設計：

1、程序設計概述：了解程序和程序設計語言的基本概念，掌握C語言程序的基本結構。

2、數據類型、運算符與表達式：掌握C語言中各種基本數據類型；理解常量、變量的概念；掌握標識符的命名規則；掌握符號常量的定義；掌握變量定義和初始化；掌握算術運算符，關系運算符、邏輯運算符、賦值運算符和逗號運算符的含義及優先級與結合性；掌握各種表達式的求值；掌握不同類型數據間的轉換與運算；掌握關系表達式和邏輯表達式及各種混合表達式的求值。

3、順序程序設計：掌握C語言語句的種類；掌握賦值語句的功能和表達方法；掌握數據輸入、輸出的格式控制；掌握字符的輸入輸出函數。

4、程序的控制結構：理解結構化程序設計的基本思想，掌握程序的三種基本結構；掌握if語句的三種基本形式和嵌套使用；理解條件運算符的功能和作用；掌握用switch語句實現多分支選擇結構；掌握for 、while 、do-while語句格式，并能用它們實現循環及循環嵌套，掌握三種循環的區別和聯系；掌握break與continue語句的使用。

5、函數：理解函數的概念；掌握函數的定義和調用；理解函數的類型和返回值；熟練使用函數編程；掌握函數的形式參數與實際參數的區別；理解函數的參數傳遞；掌握函數的嵌套調用和函數遞歸調用；理解局部變量和全局變量及變量的存儲類別、變量的作用域和生存期；理解內部函數、外部函數的概念。

6、數組：掌握數組的定義和引用并能夠靈活運用；掌握數組作為函數參數的函數的定義和調用；掌握字符數組的定義和使用；掌握使用字符數組來處理字符串；掌握字符串處理函數的使用。

7、指針：理解指針的概念；掌握指針變量的定義和使用；掌握指向簡單變量的指針和指向數組的指針使用；掌握指針變量和簡單變量作為函數參數的區別；掌握指針數組；掌握指向字符串的指針變量的定義和使用。了解指向函數的指針。

8、結構體與共用體：掌握結構體類型的定義、結構體類型變量的定義、初始化及引用方法；掌握結構體數組的定義和使用；掌握結構體變量、結構體數組和結構體指針作為函數參數；掌握關鍵字typedef的使用；了解結構體類型和共用體類型的變量占用內存情況；了解鏈表的意義和實現。

9、文件：了解文件的概念；掌握文件類型指針、掌握文件的打開與關閉；理解文件的讀寫。

數據結構：

1、緒論：掌握數據、數據元素、數據對象、數據結構、存儲結構和數據類型的概念和術語的含義；理解算法五要素的確切含義；掌握算法設計的基本要求以及計算語句頻度和估算算法時間復雜度的方法。

2、線性表：掌握線性表的邏輯結構特性是數據元素之間存在著的線性關系；熟練掌握線性表的順序存儲結構和鏈式存儲結構的描述方法，頭結點，頭指針和首元結點的區別及循環鏈表，雙向鏈表的特點；熟練掌握線性表在順序存儲結構和各種鏈表結構上的查找、插入和刪除的算法；能夠從時間和空間復雜度的角度綜合比較兩種存儲結構的不同特點及其適用的場合。

3、棧和隊列：熟練掌握棧和隊列的結構特性；熟練掌握棧類型在兩種存儲結構表示時的基本操作實現方法；熟練掌握循環隊列和鏈式隊列的基本操作實現算法；熟練掌握棧和隊列的滿和空的條件和它們的描述方法；熟悉棧和隊列的典型應用。

4、串：掌握串的結構特性----數據元素為字符的線性表；熟悉串的基本操作；掌握串匹配的KMP算法，熟悉next函數的定義，學會手工計算next函數值。

5、數組：掌握數組存儲表示方法存儲結構中的地址計算；掌握對特殊矩陣進行壓縮存儲時的下標變換公式；了解稀疏矩陣的三元組壓縮存儲表示方法及適用范圍。

6、樹和二叉樹：熟悉樹的基本定義及其相關的術語的含義；熟練掌握二叉樹的結構特性，了解相應的證明方法，理解常見的二叉樹有關理論結論；熟悉二叉樹的二叉鏈和線索二叉樹存儲結構特點及適用范圍；熟悉三種遍歷二叉樹的遞歸算法；掌握二叉樹線索化的實質及線索化的過程；掌握樹和森林與二叉樹的轉換，及其各自遍歷的對應關系；了解實現樹的各種操作的算法；掌握最優樹的特性，掌握Huffman樹及其應用。

7、圖：掌握圖的定義和術語；掌握圖的兩種存儲結構：數組表示法、鄰接表，了解實際問題的求解效率與采取何種存儲結構和算法有密切關系；掌握圖的兩種遍歷策略；圖的遍歷和樹的遍歷之間的類似與差異；熟悉圖的最小生成樹的生成方法；AOE有向無環網的關鍵路徑，關鍵活動的計算思路；掌握網絡頂點之間的最短距離的計算思想。

8、查找：熟練掌握順序表和有序表的查找方法；掌握查找效率的計算方法；. 熟練掌握二叉排序樹的構造和查找方法；掌握平衡二叉樹的維護平衡的方法。

9、內部排序：掌握排序的定義和各種排序方法的基本思想及其特點；了解各種排序方法的排序過程及其依據的原則，基于“關鍵字間的比較”進行排序的方法；熟練掌握快速排序和堆排序等方法的實例排序過程；能夠進行各種排序方法的時間復雜性(平均情況與最壞情況)估計或分析；一般了解排序方法“穩定”的含義。