一、考試基本要求及適用范圍概述

本《數據結構（C語言版）》考試大綱適用于山東工程職業技術大學2023年專升本專業測試考試。

《數據結構》課程是計算機科學與技術專業的必修專業基礎課。這門課程的主要特點是實踐性很強,不僅要學習基本理論知識,更要注重實踐能力,通過實踐驗證算法的正確性,掌握和鞏固所學理論知識。設立本門課程的目的是通過學習，使學生學會分析研究數據結構的特性，以便為應用涉及的數據選擇適當的邏輯結構、存儲結構及相應的算法，并初步了解對算法的時間分析和空間分析技術。另一方面，通過對本課程算法設計和實踐的訓練，還應培養學生的數據抽象能力和程序設計的能力，為后續課程，特別是軟件開發設計課程打下堅實的知識基礎。

二、考試方法和考試時間

專升本專業測試《數據結構（C語言）》考試為閉卷，線上考試，試卷滿分100分，考試時間為60分鐘。

三、考試內容和考試要求

1．數據結構與算法的概述

考試內容

數據結構中常用的基本概念和術語以及學習數據結構的意義。

數據的抽象類型定義。

算法在實際問題中的應用。重點掌握各種基本概念和術語、算法描述和分析的方法

考核要求：

識記：運算的概念、存儲結構和運算實現、算法分析

掌握：數據、數據元素、數據項、數據類型、數據結構、抽象數據類型

應用：算法及其描述

2.線性表

考試內容

線性表的邏輯結構和各種存儲表示方法，以及定義在邏輯結構上的各種基本運算及其在存儲結構上如何實現這些基本運算。

要求在熟悉這些內容的基礎上，能夠針對具體應用問題的要求和性質，選擇合適的存儲結構設計出相應的有效算法，解決與線性表相關的實際問題。

考核要求：

識記：線性結構的概念、線性表的概念

掌握：線性表的鏈式存儲結構、順序表與鏈表的比較

應用：線性表的順序存儲結構，插入、刪除和定位運算在單鏈表上的實現

3.棧和隊列

考試內容

棧和隊列的邏輯結構定義及在兩種存儲結構上如何實現棧和隊列的基本運算。

棧和隊列的特點的基礎上，懂得在什么樣的情況下使用棧或隊列。

考核要求：

識記：棧的定義、隊列的定義

掌握：棧的順序實現、棧的鏈接實現、隊列的順序實現

應用：循環隊的組織方法及在其上進行人隊、出隊運算的方法和隊滿、隊空的條件。

4.串

考試內容

串的邏輯結構、存儲結構及其串上的基本運算。

串的基本概念和三種表示方法。

考核要求：

識記：串的定義

掌握：串的定長順序實現

5.數組

考試內容

多維數組的邏輯結構特征及其存儲方式，特殊矩陣和稀疏矩陣的壓縮存儲方法的概念。

考核要求：

識記：數組元素地址的計算

掌握：特殊矩陣的壓縮存儲

6.樹和二叉樹

考試內容

二叉樹的定義、性質、存儲結構、遍歷、線索化，樹的定義、存儲結構、遍歷、樹和森林的轉換及赫夫曼樹及其赫夫曼編碼等內容。

考核要求：

識記：樹形結構的基本概念和術語、樹和森林、二叉樹的定義、二叉樹的順序存儲結構

掌握：二叉樹的鏈式存儲結構、哈夫曼樹的概念、構造哈夫曼樹的方法

應用：二叉樹的遍歷

7.圖

考試內容

圖的基本概念、兩種常用的存儲結構、兩種遍歷方法以及圖的應用算法。

圖的兩種存儲結構上實現的遍歷算法。

最小生成樹，求最短路徑以及拓撲排序。

考核要求：

識記：樹形結構的基本概念和術語、樹和森林

掌握：圖的遍歷，拓撲排序、關鍵路徑、圖的概念、圖的存儲結構最小生成樹

應用：Prime算法、迪杰斯特拉方法的基本思想

8.查找

考試內容

線性表、樹和哈希表的查找方法、算法實現以及各種查找方法的時間性能（平均查找長度）分析。

順序查找、折半查找、二叉排序樹和哈希表查找的基本思想和算法實現。

考核要求：

識記：查找表的基本概念

掌握：靜態查找表的實現、二叉排序樹的查找算法及其基本思想

應用：哈希表、在開散列表上實現查找、插入和刪除運算的思想和算法

9.排序

考試內容

五類內部排序方法的基本思想、排序過程、算法實現、時間和空間性能的分析以及各種排序方法的比較和選擇。

考核要求：

識記：排序的基本概念、歸并排序

掌握：堆的定義、堆的調整方法和“篩選”過程，建堆的方法、冒泡排序算法、直接選擇排序基本思想

應用：直接插入排序的算法和性能、折半插入排序算法、快速排序的算法和性能

四、主要參考教材

1.《數據結構》 湯莊園  東北師范大學出版社  2020.01

2.《數據結構（C語言版）》 嚴蔚敏  清華大學出版社  2022.10