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

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

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

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

(2)線性表

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

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

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

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

(3)堆棧和隊(duì)列

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

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

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

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

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

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

(5)陣列

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

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

(6)樹和二叉樹

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

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

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

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

5.遍歷二叉樹。

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

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

(7)圖

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)查找表，二進(jìn)制排序樹，二進(jìn)制平衡樹。

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

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

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

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

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

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

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

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

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

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

(三)命題原則

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

(4)試題難度比

試題不超過課本所學(xué)知識(shí)，難度與課本相當(dāng)。其中，易題約占40%，中難度約占50%，難題約占10%。

第三，樣題

一、單項(xiàng)選擇題(每個(gè)小題4分，15個(gè)小題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.拓?fù)渑判蚍梢源_定有向圖是否有環(huán)。( )

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

31.設(shè)無向圖G(如圖1所示)，請(qǐng)用prim算法舉例說明尋找最大生成樹的過程，并計(jì)算最小生成樹每邊的權(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é)點(diǎn)的單個(gè)鏈表反向鏈接，完成空的白色部分。

#定義空0

typedef int elemtype

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

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

Struct節(jié)點(diǎn)* next

} linklist

作廢功能(鏈表*表頭)

{ linklist *p，* q；

p = head

while(p！=空)

{ q = p；

q-> next = head；

}

}

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

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

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

(2)寫一個(gè)計(jì)算二叉樹葉節(jié)點(diǎn)數(shù)的算法。(12分)

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