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

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

一、考試范圍和要求

(a)導(dǎo)言

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))和存儲結(jié)構(gòu)(順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)、索引存儲結(jié)構(gòu)、哈希存儲結(jié)構(gòu))；數(shù)據(jù)操作。

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

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

(2)線性表

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

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

3.線性表的鏈?zhǔn)酱鎯八惴▽崿F(xiàn):包括線性鏈表、循環(huán)鏈表和雙向鏈表。

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

(3)堆棧和隊列

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

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

3.隊列抽象數(shù)據(jù)類型定義；順序存儲隊列、鏈?zhǔn)疥犃泻脱h(huán)隊列的算法實現(xiàn)。(4)字符串

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

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

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

(5)陣列

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

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

(6)樹和二叉樹

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

2.樹的存儲結(jié)構(gòu)。

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

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

5.遍歷二叉樹。

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

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

(7)圖

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

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

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

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

(八)尋找

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

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

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

(9)內(nèi)部排名

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

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

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

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

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

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

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

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

(三)命題原則

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

(4)試題難度比

試題不超過課本所學(xué)知識，難度與課本相當(dāng)。其中，易題約占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.拓?fù)渑判蚍梢源_定有向圖是否有環(huán)。( )

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

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

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

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

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

#定義空0

typedef int elemtype

typedef結(jié)構(gòu)節(jié)點

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

Struct節(jié)點* next

} linklist

作廢功能(鏈表*表頭)

{ linklist *p，* q；

p = head

while(p！=空)

{ q = p；

q-> next = head；

}

}

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

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

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

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

部分內(nèi)容來源于網(wǎng)絡(luò)轉(zhuǎn)載、學(xué)生投稿，如有侵權(quán)或?qū)Ρ菊居腥魏我庖姟⒔ㄗh或者投訴，請聯(lián)系郵箱（1296178999@qq.com）反饋。 未經(jīng)本站授權(quán)，不得轉(zhuǎn)載、摘編、復(fù)制或者建立鏡像， 如有違反，本站將追究法律責(zé)任！