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

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

一、考試性質(zhì)

本考試是為在計算機?？粕姓惺毡究粕鴮嵤┑木哂羞x拔功能的水平考試，其指導(dǎo)思想是既要有利于國家對高層次人材的選拔，又要有利于促進高等學(xué)校各類課程教學(xué)質(zhì)量的提高，考試對象為2023年參與專升本考試的考生。二、考試的基本要求

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

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

1、緒論

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

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

2、線性表

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

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

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

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

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

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

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

3、棧和隊列

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

（1）了解棧和隊列的定義。

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

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

的隊空和隊滿的判斷。

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

4、串

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

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

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

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

1

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

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

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

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

6、樹和二叉樹

考試內(nèi)容:樹的結(jié)構(gòu)定義和基本操作、二叉樹的定義、二叉樹的性質(zhì)、二叉樹的存儲結(jié)構(gòu)、遍歷二叉樹和線索二叉樹，樹和森林、樹的存儲結(jié)構(gòu)、森林與二叉樹的轉(zhuǎn)換、樹的遍歷，最優(yōu)二叉樹和哈夫曼編碼。考試要求

（1）了解樹的定義和二叉樹的定義。

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

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

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

7、圖

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

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

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

8、查找

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

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

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

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

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

9、內(nèi)部排序

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

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

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

序的基本思想。

（3）把握直接插入排序、希爾排序、快速排序、簡單項選擇擇排序、堆排序、歸并排序的算法和時間分析。

2

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

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

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

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

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

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

3

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

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

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

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

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

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

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

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

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

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

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

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

A.直接插入排序.起泡排序.快速排序直接選擇排序5、若一棵二叉樹具有10個度為2的結(jié)點，則該二叉樹葉結(jié)點個數(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、對包含N個元素的散列表進行檢索，平均檢索長度為。

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

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

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

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

4

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

序方法是

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

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

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

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

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

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

A連接B.模式匹配C求子串D求串長

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

用。

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

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

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

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

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

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

7、棧和隊列都是線性表，其中隊列的特點是。

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

9、若一數(shù)組的記錄數(shù)為400,采用分塊查找，塊長最好取。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，寫出a,b,c,d,e,f的Huffman（哈夫曼）編碼。

2、圖1是用鄰接表存儲的圖，畫出此圖，并寫出從C點開始按深度(廣度)優(yōu)先遍歷該圖的結(jié)果，。

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

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

5

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