上饒師范學院2020年專升本《數(shù)據結構》考試大綱

上饒師范學院普通高校專升本招生統(tǒng)一考試《數(shù)據結構》試題，以上饒師范學院計算機科學與技術專業(yè)《數(shù)據結構》教學大綱和我省相關專業(yè)?？瓶忌膶嶋H為依據，主要考查學生的基本類型數(shù)據結構和各種基于數(shù)據結構的算法，以及運用所學知識組織數(shù)據的能力和算法設計的能力。

本科考試時間為 120 分鐘，總分為 150 分。

一、考試范圍及要求

（一）緒論

1、數(shù)據結構概念；數(shù)據的邏輯結構（線性結構，樹型結構，網狀結構，集合結構），存儲結構（順序存儲結構，鏈式存儲結構，索引存儲結構，散列存儲結構）；數(shù)據的運算。

2、抽象數(shù)據類型的表示與實現(xiàn)。

3、算法描述；時間復雜性；空間復雜性；算法分析方法。

（二）線性表

1、線性表的類型和定義。

2、線性的順序表示和算法實現(xiàn)。

3、線性表的鏈式存儲和算法實現(xiàn)；包括線性鏈表、循環(huán)鏈表、雙向鏈表。

4、一元多項式的表示及數(shù)學運算的實現(xiàn)。

（三）棧和隊列

1、棧的抽象數(shù)據類型定義；順序棧、鏈棧的表示和實現(xiàn)。

2、棧的應用舉例：數(shù)制轉換問題；迷宮問題；表達式求值問題；遞歸算法的實現(xiàn)問題。

3、隊列抽象數(shù)據類型定義；順序存儲隊列、鏈隊列、循環(huán)隊列的算法實現(xiàn)。（四）串

1、串的抽象類型定義及特性。

2、串的表示和實現(xiàn)(串的定長順序存儲表示；堆分配存儲表示；串的塊鏈存儲表示)。

3、串的模式匹配算法（樸素的模式匹配算法，KMP模式匹配算法）及其改進的算法。

(五)數(shù)組

1、數(shù)組的定義，抽象數(shù)據類型。

2、數(shù)組的順序存儲表示和實現(xiàn)。矩陣的壓縮存儲(特殊矩陣的概念；稀疏矩陣的三元組表示法；稀疏矩陣的十字鏈表表示法；稀疏矩陣轉置、加減法等運算的實現(xiàn)）。

(六)、樹和二叉樹

1、樹型結構的基本概念。

2、樹的存儲結構。

3、二叉樹的定義、性質及存儲結構。

4、二叉樹與樹、森林之間的轉換；樹的運算的實現(xiàn)。

5、遍歷二叉樹。

6、線索二叉樹（先序穿線樹；中序穿線樹；后序穿線樹）。

7、哈夫曼樹及其應用，哈夫曼編碼。

（七）圖

1、圖的定義和術語；圖的鄰接矩陣存儲結構、鄰接表存儲結構。

2、圖的兩種遍歷策略：深度優(yōu)先搜索和廣度優(yōu)先搜索。

3、圖的最小生成樹prim算法、Kruskal 算法。

4、拓撲排序算法；單源最短路徑問題的Dijstra 算法。

（八）查找

1、靜態(tài)查找表，順序表的查找；有序表的查找；索引順序表的查找。

2、動態(tài)查找表，二叉排序樹和二叉平衡樹。

3、哈希表的概念，哈希函數(shù)的構造方法，沖突的解決方法。

（九）內部排序

1、插入排序（希爾排序不考）的基本思想、算法特點、排序過程以及它們的時間復雜度分析。

2、交換排序（冒泡排序、快速排序）的基本思想、算法特點、排序過程以及它們的時間復雜度分析。

3、選擇排序的基本思想、算法特點、排序過程以及它們的時間復雜度分析。

4、歸并排序（基數(shù)排序不考）的基本思想、算法特點、排序過程以及它們的時間復雜度分析。

二、考試形式與試卷結構

(一) 考試形式：閉卷筆試。

(二) 試卷結構

試卷為第 I 卷、第 II 卷兩大部分。第 I 卷包括單項選擇題、填空題和判斷題三種題型。第一大題單項選擇題，含15個小題，每小題4分，共60分；第二大題填空題，含10個小題，每小題3分，共30分； 第三大題判斷題，含有5小題，每小題3分，共15分。第 II 卷包括應用題、算法分析題和算法設計題三種題型。第四大題應用題，含2個小題，每小題8分，共16分；第五大題算法分析題，含2個小題，每小題6分，共12分；第六大題算法分析題，含1個小題，每題17分，共17分。試卷總分150分。

(三）命題原則

試題力求覆蓋教材主要內容，知識點分布均勻，保持穩(wěn)定的難易程度。著重考查學生基本知識的掌握程度，是否具備一定的數(shù)據組織能力，對具體問題，能抽象思維，并建立數(shù)學模型，并能獨立地設計算法，解決實際問題。

(四）試題難易比例

試題不超出教材所學知識，難易度與教材相當。其中，較容易題約占 40％，中等難度題約占 50％，較難題約占 10％。

三、樣題示例

一、單項選擇題（每小題4分，15小題共60分）

1．將兩個各有n個元素的有序表歸并成一個有序表，在最好情況下最少的比較次數(shù)是(     )。

A.n           B.2n-1         C.2n         D.n-1

二、填空題（每小題3分，10小題共30分）

16.高度為h的完全二叉樹中最少有________個結點，最多有________個結點。

三、判斷題（每小題3分，5小題共15分，對的打“√”，錯的打“×”）

26.拓樸排序方法可以判斷出一個有向圖是否有環(huán)。  （   ）

四、應用題（每小題8分，2小題共16分）

31.設無向圖G（如圖1所示），請用prim算法算法圖示求最生成樹的過程，并計算最小生成樹各邊上的權值之和。

五、算法分析題（每小題6分，2小題共12分）

33.以下算法是實現(xiàn)將一個不帶頭結點的單鏈表按逆序鏈接，將空白部分補充完整。

#define NULL 0  

    typedef int elemtype;

    typedef struct node

    {  elemtype  data;

       Struct  node *next;

       }linklist;

    Void function( linklist  *head)

    {  linklist  *p,*q;

       p=head;

                        ;

       while(p!=NULL)

         {  q=p;

                            ;

            q->next=head;

                            ;

           }

     }

六、算法設計題（共17分）

35.（本題要求采用C/C++語言描述，寫出以下相應類型定義及算法，不要求寫完整程序。）請用二叉鏈表表示一棵二叉樹的存儲方式；

（1）寫出二叉樹的結點的類型定義。（5分）

（2）寫出統(tǒng)計一棵二叉樹中葉子結點個數(shù)的算法。(12分)

推薦閱讀

上饒師范學院2020年專升本《C語言程序設計》考試大綱