蘭州理工大學(xué)技術(shù)工程學(xué)院2020年專升本計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程考試大綱

一、考試目的

蘭州理工大學(xué)技術(shù)工程學(xué)院專升本招生計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)課為《數(shù)據(jù)結(jié)構(gòu)》?？荚嚹康氖菣z查學(xué)生是否牢固掌握《數(shù)據(jù)結(jié)構(gòu)》課程相關(guān)知識(shí)的一次水平測(cè)定，全面考核普通高校計(jì)算機(jī)類專業(yè)?？?/span>(含高職)應(yīng)屆畢業(yè)生對(duì)專業(yè)核心課程《數(shù)據(jù)結(jié)構(gòu)》的掌握程度，要求學(xué)生比較系統(tǒng)的理解數(shù)據(jù)結(jié)構(gòu)的基本概念和基本理論。

二、考試內(nèi)容 

(一)基本概念

1.數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ)(數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu));

2.算法的特性和算法分析。

(二)順序表

1.線性表的定義;

2.線性表的順序存儲(chǔ)結(jié)構(gòu)(順序表的查找、插入、刪除操作);

3.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(單鏈表的插入、刪除操作)。

(三)棧和隊(duì)列

1.棧和隊(duì)列的定義;

2.順序棧的入棧和出棧操作;

3.鏈隊(duì)列的入隊(duì)和出隊(duì)操作。

(四)數(shù)組和廣義表

1.數(shù)組的定義;

2.數(shù)組的順序存儲(chǔ)結(jié)構(gòu)(分別以行序和列序?yàn)橹鳎?jì)算一維數(shù)組和二維數(shù)組元素的地址);

3.廣義表的定義(計(jì)算廣義表的長(zhǎng)度)。

(五)樹和二叉樹

1.樹和二叉樹的定義;

2.二叉樹的性質(zhì)和存儲(chǔ)結(jié)構(gòu)(順序、鏈?zhǔn)?;

3.二叉樹的遍歷(先序、中序和后序)，線索二叉樹的構(gòu)造;

4.樹、森林與二叉樹的相互轉(zhuǎn)換;

5.樹的遍歷(先根、后根)，森林的遍歷(先序、中序);

6.最優(yōu)二叉樹(WPL值的計(jì)算)，應(yīng)用赫夫曼樹構(gòu)造赫夫曼編碼。

(六)圖

1.圖的定義和基本術(shù)語(yǔ);

2.圖的存儲(chǔ)結(jié)構(gòu)：鄰接矩陣和鄰接表;

3.圖的遍歷：深度優(yōu)先搜索和廣度優(yōu)先搜索;

4.最小生成樹的構(gòu)造(普里姆算法和克魯斯卡爾算法);

5.Dijkstra算法求解最短路徑的過(guò)程。

(七)查找

1.順序查找、折半查找和分塊查找的過(guò)程、算法實(shí)現(xiàn)和算法分析;

2.二叉排序樹的查找、插入和刪除操作算法。

(八)內(nèi)部排序

1.直接插入排序、希爾排序、快速排序、簡(jiǎn)單選擇排序等;

2.各種排序的算法實(shí)現(xiàn)和性能分析。

三、試題難易程度

1.較容易題：約40%;

2.中等難度題：約50%;

3.較難題：約10%。

四、考試形式及試卷結(jié)構(gòu)

考試形式為閉卷筆試，時(shí)間為120分鐘，試卷滿分200分，試卷長(zhǎng)度為A4紙8-10版。

試卷結(jié)構(gòu)如下：

1.選擇題 約20%;

2.填空題 約20%;

3.簡(jiǎn)答題 約40%;

4.算法設(shè)計(jì)題 約20%。

五、參考書目

《數(shù)據(jù)結(jié)構(gòu)》(C語(yǔ)言版).嚴(yán)蔚敏編著.清華大學(xué)出版社,2011年。

推薦閱讀

蘭州理工大學(xué)技術(shù)工程學(xué)院2020年專升本測(cè)繪工程專業(yè)考試大綱