專(zhuān)升本數(shù)據(jù)結(jié)構(gòu)考試題1（還有好多哦大家進(jìn)我的賬號(hào)下載）

本文格式為Word版，下載可任意編輯——專(zhuān)升本數(shù)據(jù)結(jié)構(gòu)考試題1（還有好多哦，大家進(jìn)我的賬號(hào)下載）大綱

一、考試性質(zhì)

本考試是為在計(jì)算機(jī)專(zhuān)科生中招收本科生而實(shí)施的具有選拔功能的水平考試，其指導(dǎo)思想是既要有利于國(guó)家對(duì)高層次人材的選拔，又要有利于促進(jìn)高等學(xué)校各類(lèi)課程教學(xué)質(zhì)量的提高，考試對(duì)象為2023年參與專(zhuān)升本考試的考生。二、考試的基本要求

要求學(xué)生比較系統(tǒng)地理解數(shù)據(jù)結(jié)構(gòu)的基本概念和基本知識(shí)，把握表、棧、隊(duì)列、樹(shù)和圖等數(shù)據(jù)結(jié)構(gòu)的基本特征和在計(jì)算機(jī)上實(shí)現(xiàn)的方法，要求考生具有抽象思維能力、規(guī)律推理能力、綜合運(yùn)用所學(xué)的知識(shí)分析問(wèn)題和解決問(wèn)題的能力，以及軟件設(shè)計(jì)和編程能力。三、考試方法和考試時(shí)間

考試方法為閉卷筆試，考試時(shí)間為120分鐘。四、考試內(nèi)容和要求

1、緒論

考試內(nèi)容:數(shù)據(jù)結(jié)構(gòu)基本概念和術(shù)語(yǔ)，算法、算法的描述和算法分析。考試要求

（1）了解非數(shù)值問(wèn)題的數(shù)學(xué)模型不是數(shù)學(xué)方程，而是表、樹(shù)和圖之類(lèi)的數(shù)據(jù)結(jié)構(gòu)。（2）理解數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類(lèi)型等的定義。（3）把握數(shù)據(jù)的規(guī)律結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)及其種類(lèi)；算法的重要特征等。（4）會(huì)根據(jù)語(yǔ)句的最大頻度計(jì)算算法的時(shí)間繁雜度的方法。

2、線性表

考試內(nèi)容:線性表的定義、線性表的規(guī)律結(jié)構(gòu)、線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，單向鏈表、循環(huán)鏈表和雙向鏈表，一元多項(xiàng)式的表示及相加?？荚囈?/p>

（1）了解線性表的定義和線性結(jié)構(gòu)的特點(diǎn)。

（2）理解線性表的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)，理解數(shù)組與單鏈表表示表的優(yōu)缺點(diǎn)。

（3）把握線性順序表中數(shù)據(jù)元素的存儲(chǔ)位置的計(jì)算，順序表、單向鏈表、循環(huán)鏈表和雙向鏈

表的插入、刪除等有關(guān)操作。

（4）會(huì)用單鏈表編寫(xiě)插入、刪除等有關(guān)算法。

（5）能夠從時(shí)間和空間繁雜度的角度綜合比較兩存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用場(chǎng)合。

3、棧和隊(duì)列

考試內(nèi)容:棧的定義、棧的表示和實(shí)現(xiàn)；隊(duì)列的定義、隊(duì)列的表示和實(shí)現(xiàn)，鏈隊(duì)列、循環(huán)隊(duì)列?？荚囈?/p>

（1）了解棧和隊(duì)列的定義。

（2）理解線性表、棧和隊(duì)列特點(diǎn)及區(qū)別，棧對(duì)實(shí)現(xiàn)遞歸過(guò)程的作用。

（3）把握順序棧、鏈棧的入棧和出棧操作，順序隊(duì)列、鏈隊(duì)列的入隊(duì)和出隊(duì)操作，循環(huán)隊(duì)列

的隊(duì)空和隊(duì)滿(mǎn)的判斷。

（4）會(huì)編寫(xiě)入棧和出棧，入隊(duì)和出隊(duì)的有關(guān)算法。

4、串

考試內(nèi)容:串的有關(guān)定義、串的規(guī)律結(jié)構(gòu)、靜態(tài)存儲(chǔ)結(jié)構(gòu)、動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)和串的基本操作?？荚囈?/p>

（1）了解串的有關(guān)定義。

（2）理解串的規(guī)律結(jié)構(gòu)和物理存儲(chǔ)結(jié)構(gòu)。（3）把握串的模式匹配傳統(tǒng)方法。（4）理解串的模式匹配的KMP算法。

5、數(shù)組和廣義表

1

考試內(nèi)容:數(shù)組的定義和運(yùn)算、數(shù)組的順序存儲(chǔ)結(jié)構(gòu)，特別矩陣、稀疏矩陣的定義、矩陣的壓縮存儲(chǔ)，廣義表的定義、廣義表的存儲(chǔ)結(jié)構(gòu)?？荚囈?/p>

（1）了解數(shù)組、特別矩陣和稀疏矩陣的定義，廣義表的概念和鏈表表示。（2）理解矩陣的壓縮存儲(chǔ)的概念。

（3）把握矩陣的壓縮存儲(chǔ)的有關(guān)計(jì)算方法。（4）把握一種廣義表的鏈?zhǔn)絻?chǔ)方法。

（5）學(xué)習(xí)利用分治法的算法設(shè)計(jì)思想編寫(xiě)遞歸算法。

6、樹(shù)和二叉樹(shù)

考試內(nèi)容:樹(shù)的結(jié)構(gòu)定義和基本操作、二叉樹(shù)的定義、二叉樹(shù)的性質(zhì)、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)、遍歷二叉樹(shù)和線索二叉樹(shù)，樹(shù)和森林、樹(shù)的存儲(chǔ)結(jié)構(gòu)、森林與二叉樹(shù)的轉(zhuǎn)換、樹(shù)的遍歷，最優(yōu)二叉樹(shù)和哈夫曼編碼?？荚囈?/p>

（1）了解樹(shù)的定義和二叉樹(shù)的定義。

（2）理解二叉樹(shù)的性質(zhì)、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)。

（3）把握遍歷二叉樹(shù)的方法、線索二叉樹(shù)的構(gòu)造，森林與二叉樹(shù)的轉(zhuǎn)換，最優(yōu)二叉樹(shù)和哈夫曼編碼。

（4）會(huì)利用二叉樹(shù)的先根、中根和后根遍歷解決有關(guān)二叉樹(shù)的應(yīng)用問(wèn)題，會(huì)編寫(xiě)與二叉樹(shù)有關(guān)的算法。

7、圖

考試內(nèi)容:圖的定義和術(shù)語(yǔ)、圖的存儲(chǔ)結(jié)構(gòu)：鄰接矩陣和鄰接表，圖的遍歷：深度優(yōu)先探尋和廣度優(yōu)先探尋，無(wú)向圖的連通分量和生成樹(shù)、最小生成樹(shù)，拓?fù)渑判?。考試要?/p>

（1）了解圖的定義和術(shù)語(yǔ)，生成樹(shù)和最小生成樹(shù)的概念。（2）理解鄰接矩陣中元素的含義和鄰接表中結(jié)點(diǎn)的含義。（3）把握深度優(yōu)先探尋和廣度優(yōu)先探尋算法。

（4）會(huì)用Prim算法和Kruskal算法構(gòu)造最小生成樹(shù)，會(huì)找出圖中頂點(diǎn)的拓?fù)湫蛄械取?/p>

8、查找

考試內(nèi)容:靜態(tài)查找表：順序查找、二分查找和分塊查找，動(dòng)態(tài)查找表：二叉排序樹(shù)和平衡二叉樹(shù)，哈希查找、哈希函數(shù)的構(gòu)造方法和處理沖突的方法?？荚囈?/p>

（1）了解順序查找、二分查找和分塊查找的概念，二叉排序樹(shù)和平衡二叉樹(shù)、哈希查找等的概念。

（2）理解順序查找、二分查找和分塊查找算法，二叉排序樹(shù)的性質(zhì)。（3）把握哈希函數(shù)的構(gòu)造方法和處理沖突的方法，平衡二叉樹(shù)的查找、插入和刪除操作算法，

相關(guān)查找方法的ASL。

（4）會(huì)用哈希函數(shù)、開(kāi)放地址法或拉鏈法建立散列表。

9、內(nèi)部排序

考試內(nèi)容:直接插入排序、希爾排序、快速排序、簡(jiǎn)單項(xiàng)選擇擇排序、堆排序、歸并排序和基數(shù)排序。各種內(nèi)部排序方法的比較。考試要求

（1）了解排序算法的穩(wěn)定性問(wèn)題。

（2）理解直接插入排序、希爾排序、快速排序、簡(jiǎn)單項(xiàng)選擇擇排序、堆排序、歸并排序和基數(shù)排

序的基本思想。

（3）把握直接插入排序、希爾排序、快速排序、簡(jiǎn)單項(xiàng)選擇擇排序、堆排序、歸并排序的算法和時(shí)間分析。

2

（4）會(huì)用希爾排序、快速排序、堆排序、二路歸并排序方法寫(xiě)出每趟排序的結(jié)果，會(huì)編寫(xiě)與

直接插入排序和簡(jiǎn)單項(xiàng)選擇擇排序有關(guān)的算法。五、考試題型及大致比例

判斷題10%、選擇題20%、填空題20%、應(yīng)用題30%、編程題20%。

六、考試內(nèi)容大致比例：

內(nèi)容線性表樹(shù)和二叉樹(shù)圖排序棧和隊(duì)查找其它比例20%20%20%15%10%10%5%七、參考教材[1]《數(shù)據(jù)結(jié)構(gòu)》（C語(yǔ)言版）嚴(yán)蔚敏清華大學(xué)出版社

[2]《數(shù)據(jù)結(jié)構(gòu)》江濤中央廣播電視大學(xué)出版社[2]《數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)指導(dǎo)》胡學(xué)鋼清華大學(xué)出版社

3

襄樊學(xué)院專(zhuān)升本《數(shù)據(jù)結(jié)構(gòu)》考試樣卷

一、以下表達(dá)中，你認(rèn)為正確的小題題號(hào)有：（10*1`）。

1、順序循環(huán)隊(duì)列Q滿(mǎn)的條件是：Q.front+1==Q.rear2、哈夫曼樹(shù)中沒(méi)有度為1的結(jié)點(diǎn)。

3、兩分法插入排序所需比較次數(shù)與待排序記錄的初始排列狀態(tài)有關(guān)。4、當(dāng)待排序記錄已經(jīng)基本有序時(shí)，快速排序的執(zhí)行時(shí)間最省。

5、在等概率查找狀況下，分塊查找平均查找長(zhǎng)度不僅與表中元素個(gè)數(shù)有關(guān)，而且與每塊

中元素個(gè)數(shù)有關(guān)。

6、用樹(shù)的前序遍歷和中序遍歷結(jié)果可以導(dǎo)出樹(shù)的后序遍歷；7、樹(shù)中所有結(jié)點(diǎn)的層數(shù)之和稱(chēng)為樹(shù)的高度（深度）。8、三元組表是稀疏矩陣的一種順序存儲(chǔ)結(jié)構(gòu)。

9、直接插入排序是一種就地排序，它需要的輔助空間是O（n）

10、C=((x,(a,b)),y)是一個(gè)長(zhǎng)度為3的廣義表。

二、以下各小題提供的選項(xiàng)中，只有一個(gè)是正確的，請(qǐng)將你認(rèn)為正確代碼填入以下表格中（14*1.5`）題1234567891011121314號(hào)選擇1、若哈夫曼樹(shù)中其葉結(jié)點(diǎn)個(gè)數(shù)為n,則非葉結(jié)點(diǎn)的個(gè)數(shù)為。An-1BnCn+1Dlog2n

2、最優(yōu)查找樹(shù)為平均查找路徑長(zhǎng)度w1h1+w2h2+……+wnhn最小的樹(shù),其中n表示。A樹(shù)中葉結(jié)點(diǎn)數(shù)B樹(shù)中的全部結(jié)點(diǎn)數(shù)C所有非葉結(jié)點(diǎn)數(shù)D查找成功的結(jié)點(diǎn)數(shù)3、一個(gè)棧的輸入序列為1，2，3，4，下面哪一個(gè)序列不可能是這個(gè)棧的輸出序列？

A.1，3，2，42，3，4，14，3，1，23，4，2，14、以下排序方法中，哪一種方法的比較次數(shù)與記錄的初始排列狀態(tài)無(wú)關(guān)？

A.直接插入排序.起泡排序.快速排序直接選擇排序5、若一棵二叉樹(shù)具有10個(gè)度為2的結(jié)點(diǎn)，則該二叉樹(shù)葉結(jié)點(diǎn)個(gè)數(shù)是

A.91112不確定

6、在順序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找關(guān)鍵碼12需做次關(guān)鍵字比較。

A、2B、3C、4D、5

7、對(duì)包含N個(gè)元素的散列表進(jìn)行檢索，平均檢索長(zhǎng)度為。

A、為o(log2N)B、為o(N)C、不直接依靠于ND、上述三者都不是

8、假定有k個(gè)關(guān)鍵字互為同義詞（發(fā)生沖突）,若用線性探測(cè)法把這k個(gè)關(guān)鍵字存入散列表中,至少要進(jìn)行次探測(cè)。

Ak-1BkCk+1Dk(k+1)/2

9、給定一個(gè)整數(shù)集合{3，5，6，9，12}，以下二叉樹(shù)是該整數(shù)集合對(duì)應(yīng)的哈夫曼（Huffman）樹(shù)。

4

10、若需要在O(nlog2(n))的時(shí)間內(nèi)完成對(duì)數(shù)組的排序,且要求排序是穩(wěn)定的,則可選擇的排

序方法是

A快速排序B堆排序C歸并排序D直接插入排序

11、將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表,其最少的比較次數(shù)是

AnB2n-1C（n+1）/2Dn-1

12、以下方法可以用來(lái)判斷出一個(gè)有向圖中是否有環(huán)（回路）

A深度優(yōu)先遍歷B拓樸排序C求最短路徑D求關(guān)鍵路徑

13、假設(shè)有兩個(gè)串A和B，求B在A中首次出現(xiàn)的位置的操作，我們稱(chēng)為。

A連接B.模式匹配C求子串D求串長(zhǎng)

14、假使待排序的記錄的規(guī)模很大，則在下面的排序方式中，我們最好不要選擇使

用。

A快速排序B.直接插入排序C.堆排序D.歸并排序

三、你認(rèn)為正確的表達(dá)填在各題的下劃線上（10*2`）。

1、串的主要存貯方式有：定長(zhǎng)順序存貯、和塊鏈存貯。2、堆的存儲(chǔ)表示是（順序的，還是鏈接的）。

3、在n個(gè)記錄的哈希表中進(jìn)行查找，最少的比較次數(shù)是。

4、n個(gè)頂點(diǎn)的連通圖用鄰接矩陣表示時(shí),該矩陣至少有個(gè)非零元素.5、評(píng)價(jià)一個(gè)算法好壞的主要標(biāo)準(zhǔn)有。

6、若壓縮存貯下三角矩陣Am*n的首地址為a,每個(gè)元素占空間為b字節(jié),則元素aij的地址為。

7、棧和隊(duì)列都是線性表，其中隊(duì)列的特點(diǎn)是。

8、若順序二叉樹(shù)中編號(hào)為n的結(jié)點(diǎn)的父結(jié)點(diǎn)和右兒子是存在的，則它們的編號(hào)應(yīng)當(dāng)分別是

9、若一數(shù)組的記錄數(shù)為400,采用分塊查找，塊長(zhǎng)最好取。10、就排序算法的穩(wěn)定性而言，希爾排序和快速排序分別是。

四、應(yīng)用題（5*6`）

1、假設(shè)字符a,b,c,d,e,f的使用頻度分別是0.07,0.09,0.12,0.22,0.23,0.27，寫(xiě)出a,b,c,d,e,f的Huffman（哈夫曼）編碼。

2、圖1是用鄰接表存儲(chǔ)的圖，畫(huà)出此圖，并寫(xiě)出從C點(diǎn)開(kāi)始按深度(廣度)優(yōu)先遍歷該圖的結(jié)果，。

3、試求按關(guān)鍵字序列（12，1，4，3，7，8，10，2）插入生成的二叉排序樹(shù)和平衡二叉樹(shù)。

4、哈希函數(shù)為：H(key)=3*keymod11,開(kāi)放定址的di=i*(7*keymod10+1),在

5

區(qū)間[0，10]上構(gòu)造關(guān)鍵字（22，41，53，46，30，13，01，67）的哈希表，并計(jì)算其平均查找長(zhǎng)