考試科目：軟件工程專業(yè)基礎

科目代碼：807

一、考試的總體要求

本科目考試內容涵蓋C語言程序設計、數據結構兩部分內容。

（一）C語言程序設計部分

要求掌握C語言的基本內容及程序設計的基本方法、常用算法與編程技巧，掌握結構化程序設計思想。選擇適當的數據類型表示實際問題，能使用函數進行模塊化程序設計，掌握應用計算機解決和處理實際問題的思維方法與基本能力。

（二）數據結構

理解數據結構的基本概念；掌握數據的邏輯結構、存儲結構及其差異，以及各種基本操作的實現；熟練掌握經典算法的演化過程；具備選擇合適的數據結構和方法進行問題求解的能力；能夠對算法性能進行簡單分析。

二、考試的內容及比例

（一）C語言程序設計部分

1. C語言基礎 (約10%)

（1）C語言程序基本結構特點；

（2）基本數據類型，整數、實數、字符和字符串常量的表示方法，變量定義和初始化，能選擇正確的數據類型處理實際問題；

（3）基本運算的實現（包括算術運算、關系運算、邏輯運算、條件運算、賦值運算），各類數值型數據間的混合運算；

（4）數據輸入輸出的概念及在Ｃ語言中的實現，包括字符數據的輸入輸出、格式輸入與輸出。

2.程序控制結構（約10%）

（1）用if、switch實現分支結構的程序設計；

（2）用while語句、do while語句和for語句實現循環(huán)結構的程序設計，循環(huán)嵌套的實現方法；

（3）用循環(huán)實現迭代、枚舉、遞歸等常用算法。

3、數組 (約20%)

（1）一維數組、二維數組的定義和引用方法；

（2）字符數組和字符串處理函數的使用；

（3）能應用數組處理實際問題，如字符串處理、數列計算、矩陣運算等。

4、函數 (約30%)

（1）函數定義的一般形式，函數參數和函數返回值，包括數組、指針作為函數的參數，指針作為函數的返回值；

（2）函數調用的一般形式、函數的嵌套和遞歸調用；

（3）變量的存儲類別、局部變量和全局變量的使用；

（4）通過函數定義、函數調用實現模塊化程序設計。

5、指針 (約15%)

（1）地址和指針的概念，指針變量的定義；

（2）通過指針變量引用各類指向實體（包括普通變量、數組、結構體和指針）；

（3）指針數組和命令行參數（argc、argv）的意義和實現。

6、結構體 (約10%）

（1）結構體類型變量的定義、成員引用、初始化的方法；

（2）結構體數組的使用；

（3）結構體嵌套的定義、成員引用、初始化的方法。

7、文件 （約5%）

（1）文件有關的基本概念、文件類型指針；

（2）文件打開與關閉、文件讀寫，文件定位操作的實現。

（二）數據結構部分

1、緒論（約5%）

（1）數據結構的基本概念，數據的邏輯結構、存儲結構；

（2）算法的定義、算法的基本特性以及算法分析的基本概念。

2、線性表（約20%）

（1）線性表的定義和基本操作；

（2）線性表的實現：順序存儲結構與鏈式存儲結構(包括單鏈表、循環(huán)鏈表和雙向鏈表)；線性表的應用——表的建立、插入與刪除、檢索等操作對應的算法設計(含遞歸算法的設計)。

3、棧、隊列和稀疏矩陣（約15%）

（1）棧與隊列的基本概念、基本操作；

（2）棧與隊列的順序存儲結構與鏈式存儲結構的構造原理；

（3）在不同存儲結構的基礎上對棧與隊列實施插入與刪除等基本操作對應的算法設計；

（4）棧與隊列的應用。

（5）對稱矩陣和稀疏矩陣的壓縮存儲；

4、樹與二叉樹(約20%)

（1）樹的定義和性質；

（2）二叉樹的概念、性質和實現；

（3）二叉樹的順序存儲結構和鏈式存儲結構；

（4）遍歷二叉樹和線索二叉樹；

（5）樹和森林；

（6）赫夫曼樹及其應用。

5、圖(約10%)

（1）圖的基本概念和常用名詞術語；

（2）圖的鄰接矩陣存儲方法、鄰接表存儲方法的構造原理；

（3）圖的遍歷操作及連通性問題；

（4）最小生成樹，最短路徑，AOV網與拓撲排序，關鍵路徑。

6、查找(約10%)

（1）查找的基本概念；

（2）順序表的順序查找方法、有序順序表的折半查找方法；

（3）二叉排序樹、平衡二叉樹和B樹；

（4）哈希表的構造及其查找；

（5）查找算法的分析及應用。

7、內排序(約20%)

（1）排序的基本概念，排序方法的分類；

（2）各種排序方法排序的原理、規(guī)律和特點，包括：插入排序法(含折半插入排序法和希爾排序)、選擇排序法（含堆排序）、冒泡排序法、快速排序法、歸并排序、基數排序；

（3）排序算法性能的簡單分析（時空復雜度）。

三、考試題型及比例

（一）C語言程序設計部分

考試滿分75分，其中：

1、客觀題（選擇、判斷） 20分

2、程序完善題 15分

3、編程題 40分

（二）數據結構部分

考試滿分75分，其中：

1、客觀題（選擇、判斷） 15分

2、算法設計題 30分

3、綜合題 30分

四、考試形式及時間

考試形式為筆試，考試時間為 3 小時。

更多學歷考試信息請查看學歷考試網