上饒師范學(xué)院2020年專升本《數(shù)據(jù)結(jié)構(gòu)》考試大綱

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

本科考試時(shí)間為 120 分鐘，總分為 150 分。

一、考試范圍及要求

（一）緒論

1、數(shù)據(jù)結(jié)構(gòu)概念；數(shù)據(jù)的邏輯結(jié)構(gòu)（線性結(jié)構(gòu)，樹型結(jié)構(gòu)，網(wǎng)狀結(jié)構(gòu)，集合結(jié)構(gòu)），存儲(chǔ)結(jié)構(gòu)（順序存儲(chǔ)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，索引存儲(chǔ)結(jié)構(gòu)，散列存儲(chǔ)結(jié)構(gòu)）；數(shù)據(jù)的運(yùn)算。

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

3、算法描述；時(shí)間復(fù)雜性；空間復(fù)雜性；算法分析方法。

（二）線性表

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

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

3、線性表的鏈?zhǔn)酱鎯?chǔ)和算法實(shí)現(xiàn)；包括線性鏈表、循環(huán)鏈表、雙向鏈表。

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

（三）棧和隊(duì)列

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

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

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

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

2、串的表示和實(shí)現(xiàn)(串的定長(zhǎng)順序存儲(chǔ)表示；堆分配存儲(chǔ)表示；串的塊鏈存儲(chǔ)表示)。

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

(五)數(shù)組

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

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

(六)、樹和二叉樹

1、樹型結(jié)構(gòu)的基本概念。

2、樹的存儲(chǔ)結(jié)構(gòu)。

3、二叉樹的定義、性質(zhì)及存儲(chǔ)結(jié)構(gòu)。

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

5、遍歷二叉樹。

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

7、哈夫曼樹及其應(yīng)用，哈夫曼編碼。

（七）圖

1、圖的定義和術(shù)語；圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)、鄰接表存儲(chǔ)結(jié)構(gòu)。

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

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

4、拓?fù)渑判蛩惴ǎ粏卧醋疃搪窂絾栴}的Dijstra 算法。

（八）查找

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

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

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

（九）內(nèi)部排序

1、插入排序（希爾排序不考）的基本思想、算法特點(diǎn)、排序過程以及它們的時(shí)間復(fù)雜度分析。

2、交換排序（冒泡排序、快速排序）的基本思想、算法特點(diǎn)、排序過程以及它們的時(shí)間復(fù)雜度分析。

3、選擇排序的基本思想、算法特點(diǎn)、排序過程以及它們的時(shí)間復(fù)雜度分析。

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

二、考試形式與試卷結(jié)構(gòu)

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

(二) 試卷結(jié)構(gòu)

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

(三）命題原則

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

(四）試題難易比例

試題不超出教材所學(xué)知識(shí)，難易度與教材相當(dāng)。其中，較容易題約占 40％，中等難度題約占 50％，較難題約占 10％。

三、樣題示例

一、單項(xiàng)選擇題（每小題4分，15小題共60分）

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

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

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

16.高度為h的完全二叉樹中最少有________個(gè)結(jié)點(diǎn)，最多有________個(gè)結(jié)點(diǎn)。

三、判斷題（每小題3分，5小題共15分，對(duì)的打“√”，錯(cuò)的打“×”）

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

四、應(yīng)用題（每小題8分，2小題共16分）

31.設(shè)無向圖G（如圖1所示），請(qǐng)用prim算法算法圖示求最生成樹的過程，并計(jì)算最小生成樹各邊上的權(quán)值之和。

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

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

#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;

                            ;

           }

     }

六、算法設(shè)計(jì)題（共17分）

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

（1）寫出二叉樹的結(jié)點(diǎn)的類型定義。（5分）

（2）寫出統(tǒng)計(jì)一棵二叉樹中葉子結(jié)點(diǎn)個(gè)數(shù)的算法。(12分)

推薦閱讀

上饒師范學(xué)院2020年專升本《C語言程序設(shè)計(jì)》考試大綱