根據(jù)上饒師范學院計算機科學與技術專業(yè)數(shù)據(jù)結構教學大綱和我省相關專業(yè)院校考生的實際情況，上饒師范學院專升本統(tǒng)考數(shù)據(jù)結構試題主要考查學生數(shù)據(jù)結構的基本類型和基于數(shù)據(jù)結構的各種算法，以及用自己的知識組織數(shù)據(jù)和設計算法的能力。

本科考試120分鐘，總分150分。

一、考試范圍和要求

(a)導言

1.數(shù)據(jù)結構的概念；數(shù)據(jù)的邏輯結構(線性結構、樹形結構、網(wǎng)狀結構、集合結構)和存儲結構(順序存儲結構、鏈式存儲結構、索引存儲結構、哈希存儲結構)；數(shù)據(jù)操作。

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

3.算法描述；時間復雜度；空之間的復雜度；算法分析方法。

(2)線性表

1.線性表格的類型和定義。

2.線性序列表示及算法實現(xiàn)。

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

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

(3)堆棧和隊列

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

2.棧的應用實例:數(shù)制轉換問題；迷宮問題；表情評價問題；遞歸算法的實現(xiàn)。

3.隊列抽象數(shù)據(jù)類型定義；順序存儲隊列、鏈式隊列和循環(huán)隊列的算法實現(xiàn)。(4)字符串

1.字符串的抽象類型定義和特征。

2.字符串的表示和實現(xiàn)(字符串的定長順序存儲表示；堆分配存儲表示；字符串的區(qū)塊鏈存儲表示)。

3.字符串模式匹配算法(樸素模式匹配算法、KMP模式匹配算法)及其改進算法。

(5)陣列

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

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

(6)樹和二叉樹

1.樹形結構的基本概念。

2.樹的存儲結構。

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

4.二叉樹與樹和森林之間的轉換；樹操作的實現(xiàn)。

5.遍歷二叉樹。

6、線索二叉樹(靠前線程樹；中間穿線樹；穿線樹后)。

7.霍夫曼樹及其應用，霍夫曼編碼。

(7)圖

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

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

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

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

(八)尋找

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

2.動態(tài)查找表，二進制排序樹，二進制平衡樹。

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

(9)內部排名

1.插入排序的基本思想、算法特點、排序過程及其時間復雜度分析(Hill排序不做測試)。

2.交換排序(冒泡排序、快速排序)的基本思想、算法特點、排序過程和時間復雜度分析。

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

4.合并排序的基本思想、算法特點、排序過程及其時間復雜度分析(基數(shù)排序不做測試)。

二、考試形式和試卷結構

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

(二)試卷結構

試卷由靠前卷和第二卷兩部分組成?？壳熬戆▎雾椷x擇題、填空題空題和判斷題三種題型?？壳暗绬雾椷x擇題，包括15道小題，每道4分，共60分；填寫第二個大題空，包括10個小題，每題3分，共30分；第三個大題，真假，包含5個小題，每題3分，共15分。第二卷包括三類問題:應用問題、算法分析問題和算法設計問題。第四大應用題，包括2道小題，每道小題8分，共16分；第五大題算法分析題，包括2個小題，每個小題6分，共12分；第六大題，算法分析，一個小項目組成，每個項目17分，共17分。試卷總分150。

(三)命題原則

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

(4)試題難度比

試題不超過課本所學知識，難度與課本相當。其中，易題約占40%，中難度約占50%，難題約占10%。

第三，樣題

一、單項選擇題(每個小題4分，15個小題60分)

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

a . n . b . 2n-1 c . 2n d . n-1

二、填空題(每道小題3分，10道小題30分)

16.高度為h的完整二叉樹至少有_ _ _ _ _ _個節(jié)點，最多有_ _ _ _ _ _個節(jié)點。

三、真假題(每道小題3分，5道小題15分，對的打√，錯的打×)

26.拓撲排序法可以確定有向圖是否有環(huán)。( )

四、應用題(每道小題8分，2道小題16分)

31.設無向圖G(如圖1所示)，請用prim算法舉例說明尋找最大生成樹的過程，并計算最小生成樹每邊的權重之和。

專升本數(shù)據(jù)結構考試大綱題型" alt="2020上饒師范學院專升本數(shù)據(jù)結構考試大綱題型" width="147" height="186" border="0" vspace="0" style="width: 147px; height: 186px;"/>

第五，算法分析題(每道小題6分，2道小題12分)

33.下面的算法是將沒有前導節(jié)點的單個鏈表反向鏈接，完成空的白色部分。

#定義空0

typedef int elemtype

typedef結構節(jié)點

{ elemtype數(shù)據(jù)；

Struct節(jié)點* next

} linklist

作廢功能(鏈表*表頭)

{ linklist *p，* q；

p = head

while(p！=空)

{ q = p；

q-> next = head；

}

}

六、算法設計題(共17分)

35.(本題目要求用C/C++語言來描述，寫出下面相應的類型定義和算法，不要求完整的程序。請用二進制鏈表來表示一個二叉樹的存儲方式；

(1)寫出二叉樹節(jié)點類型的定義。(5分)

(2)寫一個計算二叉樹葉節(jié)點數(shù)的算法。(12分)

部分內容來源于網(wǎng)絡轉載、學生投稿，如有侵權或對本站有任何意見、建議或者投訴，請聯(lián)系郵箱（1296178999@qq.com）反饋。 未經(jīng)本站授權，不得轉載、摘編、復制或者建立鏡像， 如有違反，本站將追究法律責任！