鄭州大學遠程教育學院數(shù)據(jù)結構試題及答案

1、鄭州大學現(xiàn)代遠程教育數(shù)據(jù)結構課程（本科）學習指導書郭純一編.課程內容與基本要求“數(shù)據(jù)結構” 在計算機科學中是一門綜合性的專業(yè)基礎課。 本課程將主要介紹數(shù)據(jù)結構的基本概念和術語、 非數(shù)值計算中常用的數(shù)據(jù)結構 （線性表、 棧和隊列、串、樹和圖）和基本技術（查找和排序方法）三大部分。本課程要求學生在掌握線性表、棧和隊列、串、樹和二叉樹、圖等基本數(shù)據(jù)類型的基礎上， 會分析各種數(shù)據(jù)結構的特性， 會根據(jù)應用需求為所涉及的數(shù)據(jù)合理選擇適當?shù)倪壿嫿Y構和存儲結構， 并能據(jù)此設計實現(xiàn)問題的算法； 還應初步掌握算法的時間和空間效率的分析方法。課程學習進度與指導章節(jié)課程內容學時分配學習指導（均以課件學習為主）第一章緒

2、論4 學時重點掌握基本概念和時間復雜度的計算方法重點掌握順序結構和鏈式結構表示線性第二章 *線性表10 學時表的方法和操作的實現(xiàn)；結合具體例子理解編程實現(xiàn)一個問題的 2 種方法重點掌握棧和隊列的特點以及它們各自第三章棧和隊列8 學時的存儲表示，尤其是順序棧和循環(huán)隊列的實現(xiàn)；結合具體例子理解棧和隊列的應用第四章串2 學時重點掌握串的術語、串操作結果和不同存儲結構的特點重點掌握二叉樹的定義、存儲、性質、遍第七章 *樹和二叉樹10 學時歷算法（遞歸）及應用、線索化；掌握樹和森林與二叉樹的轉換以及 Huffman 樹和Huffman 編碼的構造方法重點掌握圖的術語、存儲、遍歷算法及應第八章圖8 學時用

3、；掌握最小生成樹的 2 種構造方法及特點、會求拓撲排序序列和單源最短路徑重點掌握各種動態(tài)查找表的構造過程、性第九章 *查找8 學時能分析、插入 / 刪除方法；掌握靜態(tài)查找表的順序、折半和分塊查找及 ASL求法掌握關于排序的術語及分類方法；重點掌第十章 *排序8 學時握插入排序、交換排序、選擇排序等內排序方法及其性能分析方法.第一章緒論一、章節(jié)學習目標與要求1、理解數(shù)據(jù)抽象和信息隱蔽原則2、掌握所有的基本概念和術語、掌握時間復雜度的計算方法、會用 C 語言描述抽象數(shù)據(jù)類型和算法；能夠熟練使用 C 語言編寫程序二、本章重點、難點重點：基本概念和術語， C 語言描述算法的方式， 簡單程序的時間復雜度

4、的求法。難點：時間復雜度的計算方法和原則。三、章節(jié)練習（一）選擇題：1 具有線性結構的數(shù)據(jù)結構是_。A.圖B.樹C.集合D.棧2 計算機算法是指 _。A. 計算方法和運算結果B.調度方法C. 解決某一問題的有限運算系列D.排序方法3 線性結構中，最后一個結點有_個后繼結點。A.0B.1C.任意多4. 算法分析的目的是 _。A. 找出數(shù)據(jù)結構的合理性B.研究算法中輸入和輸出的關系C. 分析算法的效率以求改進D.分析算法的可讀性和可行性5. 具有非線性結構的數(shù)據(jù)結構是 _。A.圖B.線性表C.串D.棧6算法具有 5 個特性： _、_、 _、輸入和輸出。A. 穩(wěn)定性、確定性、可行性B.有窮性、確定性

5、、可行性C. 有窮性、安全性、可行性D.有窮性、確定性、可移植性7設 n 為正整數(shù)。則下面程序段的時間復雜度為_。i=1; k=0;while(i=n-1) k+=10*i;.i+;A.O(1)B. O(n)C. O(nlogn)D. O(n2)8設 n 為正整數(shù)。則下面程序段的時間復雜度為_。k=0;for(i=1;i=n;i+)for(j=i;jnext=NULL; B. p=NULL; C. p-next=head; D. p=head;4若在線性表的任何位置上插入元素的概率是相等的，那么在長度為n 的順序表中插入一個元素時需平均移動_個元素。A. nB. (n-1)/2C.n/2D.

6、(n+1)/25在帶頭結點的非空單鏈表中，頭結點的位置由_指示，首元結點的存儲位置由 _指示，除首元結點外，其它任一元素結點的存儲位置由_指示。A. 頭指針B.頭結點的指針域的指針C.前驅結點的指針域的指針6. 單鏈表的頭指針為 p，若有頭結點，則表空的判斷條件是 _；若不帶頭結點，則表空的判斷條件是 _。A. p=NULLB. p-next=NULLC. p-next-next=NULL（二）判斷題：1在單鏈表中插入或刪除元素時是以結點的指針變化來反映邏輯關系的變化，因此不需要移動元素。（ ）2 順序表能夠以元素在計算機內的物理位置的相鄰性來表示線性表中元素之間的邏輯關系。（ ）3. 在不帶

7、頭結點的非空單鏈表中， 首元結點的存儲位置由頭指針指示， 除首元結點外，其它任一元素結點的存儲位置由前驅結點的指針域的指針指示。（ ）（三）問答題：1若線性表要求以最快的速度存取而表中元素變動不大，則應采取什么存儲結構（順序或鏈式結構）？為什么？2若線性表經(jīng)常做插入/ 刪除操作，則應采取什么存儲結構？為什么？3. 在單鏈表中設置頭結點有什么作用？（四）算法題：1. 設帶頭結點的單鏈表 (L 為頭指針 ) 中的數(shù)據(jù)元素遞增有序。設計算法，將x 插入到鏈表的適當位置上，并仍保持該表的有序性。.2. 設順序表 va 中的數(shù)據(jù)元素遞增有序。設計算法，將x 插入到順序表的適當位置上，并仍保持該表的有序性

8、。3. 設計算 法， 實現(xiàn) 單鏈 表的 就地逆 置，即利用 原表的 存儲 空間將 線性表（ a1,a 2, ,a n）逆置為（ an ,a n-1 , ,a 1）。第三章棧和隊列一、 章節(jié)學習目標與要求1、理解用棧和隊列解決實際問題的方法。2、掌握棧和隊列的定義以及特性、它們的2 種不同的存儲表示方法（特別是順序棧和循環(huán)隊列） 以及各種常見操作 （如入、出操作）在不同表示方式上的實現(xiàn)。二、本章重點、難點重點：棧和隊列的定義、各種表示和實現(xiàn)方法，加深對線性結構的理解難點：循環(huán)隊列的表示及為解決循環(huán)隊列隊空、 隊滿判斷條件相同而使用的不同實現(xiàn)方式；能在具體問題中靈活運用棧和隊列結構。三、章節(jié)練習（

9、一）選擇題：1一個棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是_。A. edcba B.decba C.dceab D.abcde 2棧和隊列的共同點是 _。A. 都是后進先出B.都是先進先出C. 都是只允許在端點處插入和刪除元素D.無共同點3一個隊列的入隊序列是1,2,3,4,則隊列的輸出序列是 _。A. 4321B. 1234C. 1432D. 32414棧的入棧序列是 1，2， ，n，輸出序列為 p1,p2,pn, 若 p1=n, 則 pi 為 _。A. iB. n-iC. n-i+1D.不確定5隊列是限定在 _進行插入，在 _進行刪除的線性表。A. 隊頭B.隊尾C.任意位

10、置6循環(huán)隊列中，設隊列元素依次存放在Q0.m 中， f 、 r 分別指示隊頭元素位置和隊尾元素的下一個位置， 約定存儲 m個元素時為隊滿。 則隊列空的判定方法是 _, 隊列滿的判定方法是 _。.A.f=rB. (f+1)%(m+1)=rC. (r+1)%(m+1)=fD. (r+1)% m=f（二）判斷題：1若用戶無法估計所用隊列的最大長度，則最好采用鏈隊列。（ ）2在鏈隊列上刪除隊頭元素時， 只需修改頭結點中的指針， 不必修改尾指針。 （ ）3.棧是限定僅在棧頂進行插入或刪除操作的線性表。（ ）4.隊列是限定在隊尾插入元素，在隊頭刪除元素的線性表。（ ）（三）問答與算法題：1對于一個棧，若輸

11、入序列依次為A,B,C,試給出所有可能的輸出序列。2假設將循環(huán)隊列定義為：以整型域變量front和 length 分別指示循環(huán)隊列中隊頭元素位置和隊列中元素個數(shù)， 指針 elem 指示存放隊列元素的連續(xù)空間的首地址，寫出相應的入隊列和出隊列的算法。第四章串一、 章節(jié)學習目標與要求1、理解串的抽象數(shù)據(jù)類型的定義以及相關術語、理解串在文本編輯中的作用。2、掌握字符串的定義及各種基本操作的運算結果以及串的各種存儲表示的特點。二、本章重點、難點重點：串的基本運算、串的各種存儲表示和特點。繼續(xù)加深對線性結構的理解難點：串的不同存儲結構，區(qū)分它們和高級語言中串的存儲方式的不同。三、章節(jié)練習（一）選擇題：1

12、設串 s=I AM A STUDENT, 則其串長是 _。A. 13B. 14C. 15D. 162.設 s =HE IS A WORKER,t=WORKER。則 StrIndex(s,t,5)的返回值是 _。A.4B.5C.6D.9E.103. 串是一種特殊的線性表，其特殊性體現(xiàn)在 _。A. 可以順序存儲B.數(shù)據(jù)元素是一個字符C. 可以鏈接存儲D.數(shù)據(jù)元素可以是多個字符4. 已知串 s=ABCDEFGH, 則 s 的所有不同子串的個數(shù)為_。A.8B.9C.36D.37.5. 設串 s=I ama teacher. , 則 s 的第 8 個字符起、長度為 7 的子串為 _。 A. teache

13、r. B. teacher C. a teacher D. teacher6.設串 s=student.,t=“good ,則執(zhí)行 StrInsert(s,1,t)后， s 為_。A. good student.B. good studentC. goodstudentD. good teacher（二）判斷題：1空串和空格串是相同的。（）2. 如果兩個串含有相同的字符，則它們是相同的。 （ ）3. 串的基本操作和線性表的一樣， 都是以“單個元素” 作為操作對象的。 （ ）4.在串的鏈式存儲結構中，結點大小與存儲密度之間沒有關系。（）第七章樹和二叉樹一、章節(jié)學習目標與要求1、理解樹、二叉樹和森

14、林的概念，理解線索化二叉樹的特性、創(chuàng)建方法及在線索二叉樹上尋找某結點的前驅和后繼的方法；理解樹與森林的存儲方法。2、掌握二叉樹的性質及表示；掌握二叉樹的各種遍歷方法 （尤其是遞歸形式的）以及遍歷在實際問題中的應用；掌握樹及森林與二叉樹的轉換及遍歷方式的對應；掌握 Huffman 樹的構造方法以及構造 Huffman 編碼的方法。二、本章重點、難點重點：二叉樹的性質（及證明） 、存儲結構及各種遍歷算法，二叉樹的線索化過程，樹和森林與二叉樹的轉換關系， Huffman 樹及 Huffman 編碼的構造方法難點：各種遍歷算法的遞歸實現(xiàn)以及在具體問題中能靈活運用遍歷思想解題三、章節(jié)練習（一）選擇題：1

15、下列關于二叉樹的說法中，正確的有_。A. 二叉樹的度為 2 B. 二叉樹的度可以小于 2C.二叉樹中至少有一個結點的度為 2 D. 二叉樹中任一個結點的度都為 2 2任何一棵二叉樹的葉子結點在先、 中、后序遍歷序列中的相對次序 _。A.不發(fā)生改變B.發(fā)生改變C.不能確定D.以上都不對3下面幾個符號串編碼集合中，不是前綴編碼的是_。.A. 0 ，10，110， 1111B. 11，10，001，101，0001C. 00 ， 010， 0110， 1000D. b,c,aa,ac,aba,abb,abc4二叉樹按某種順序線索化后，任意結點均有指向其前驅和后繼的線索，這種說法 _。A.正確B.不正

16、確C.無法確定（二）判斷題：1.哈夫曼樹是帶權葉子數(shù)目固定的二叉樹中帶權路徑長度最小的。（）2.根據(jù)二叉樹的定義，具有 3 個結點的二叉樹有5 種不同的形態(tài)。（）3.深度為 k 的完全二叉樹至少有 2k-1 個結點，至多有 2k1 個結點。（）4.具有 n 個結點的滿二叉樹，其葉子結點個數(shù)為n 1 個。（）25.在哈夫曼樹中，通常權值較大的結點離根較遠。（）（三）問答題：1下圖所示森林轉化為相應的二叉樹，并在其上標出中序全線索。2證明：深度為 k 的二叉樹上至多有2k-1 個結點（ k1）。3. 證明：任何一棵滿二叉樹中的分支數(shù) B滿足 B=2(n01) ，其中 n0 為葉子結點個數(shù)。4. 以

17、數(shù)據(jù)集 15 ，3， 14，2，6，9，16，17 為葉子的權值構造 Huffman 樹，畫出此樹并計算其帶權路徑長度。（四）算法題：1. 假設二叉排序樹（ t 為指向根結點的指針）中各元素值均不相同，設計一個遞歸算法按遞增順序輸出樹上各元素值。2編寫遞歸算法 ,交換二叉鏈表存儲的二叉樹中每個結點的左、右子樹。.3. 編寫遞歸算法，求以二叉鏈表存儲的二叉樹的深度。4. 設計遞歸算法計算以二叉鏈表存儲的二叉樹的葉子結點數(shù)目。第八章圖一、章節(jié)學習目標與要求1、理解圖的基本概念和術語。2、掌握圖的鄰接矩陣和鄰接表2 種表示方法；掌握圖的兩種遍歷算法及其求解連通性問題的方法；掌握用Prim 算法和 K

18、ruskal 算法構造最小生成樹的過程和性能分析；掌握 AOV網(wǎng)的拓撲排序方法( 不要求算法 ) ，掌握用 Dijkstra方法求解單源最短路徑問題的方法( 不要求算法 ) 。二、本章重點、難點重點：圖的數(shù)組表示法和鄰接表表示法存儲結構以及圖的兩種遍歷方式，求最小生成樹的兩種方法， AOV網(wǎng)的拓撲排序方法，掌握單源最短路徑的求法難點：圖的兩種遍歷算法的實現(xiàn)以及在圖的連通性問題中的應用三、章節(jié)練習（一）選擇題：1. 4 個頂點的無向完全圖有 _條邊。A.6B.12C.16D.202無向圖的鄰接矩陣是一個_。A. 對稱矩陣B.零矩陣C.對角矩陣D.上三角矩陣3圖的廣度優(yōu)先遍歷算法類似于二叉樹的_，

19、圖的深度優(yōu)先遍歷算法類似于二叉樹的 _。A. 先序遍歷B.中序遍歷C.后序遍歷D.層序遍歷4. 對 _，用 Prim 算法求最小生成樹較為合適， 而 Kruskal 算法適于構造_圖的最小生成樹。A. 完全圖B.連通圖C.稀疏圖D.稠密圖5. 對于含 n 個頂點、 e 條邊的無向連通圖，利用 Prim 算法構造最小生成樹的時間復雜度 _，用 Kruskal 算法構造最小生成樹的時間復雜度為_。A. O(n) B. O(n2) C. O(e) D. O(eloge) F. O(e2).（二）判斷題：1. 若從無向圖的一個頂點出發(fā)進行廣度優(yōu)先遍歷可訪問到圖中所有頂點，則該圖一定是連通圖。（）2.

20、若從無向圖的一個頂點出發(fā)進行深度優(yōu)先遍歷可訪問到圖中所有頂點，則該圖一定是連通圖。（）3. 任何有向圖的頂點都可以排成拓撲有序序列， 而且拓撲序列不唯一。 （ ）4.有 n 個頂點和 n-1 條邊的無向圖一定是生成樹。（）5.一棵有 n 個頂點的生成樹有且僅有 n-1 條邊。（）6. 連通分量是無向圖的極大連通子圖， 而生成樹是無向圖的極小連通子圖。（ ）（三）問答及算法題：0101. 一個圖的鄰接矩陣 G.arcs= 1 0 1 ，該圖有多少個頂點？如果是有0 1 1向圖，該圖共有多少條?。咳绻菬o向圖，該圖共有多少條邊?2. 已知如右圖所示的有向圖，寫出該圖的 :(1) 鄰接矩陣 (2 ）

21、一個可能的拓撲有序序列 （ 3）寫出從 1 出發(fā)的深度優(yōu)先遍歷序列（4）寫出從 5 出發(fā)的廣度優(yōu)先遍歷序列。3. 假設有 5 項活動 C1C5，每項活動要求的前驅活動如下：C1：無； C2：C1， C3； C3 ：C1； C4 ：C3，C5C5 ：C2；試根據(jù)上述關系，畫出相應的有向圖，再寫出一個拓撲排序序列。4. 基于圖的深度優(yōu)先遍歷策略寫一算法，判斷以鄰接表方式存儲的無向圖中連通分量的個數(shù)。第九章查找一、章節(jié)學習目標與要求1、理解各種查找表的定義、 各種查找方法的思想以及構造查找表所依據(jù)的原則。2、掌握線性表表示的靜態(tài)查找表的順序查找和折半查找算法及其性能分析方法；掌握二叉排序樹的創(chuàng)建、查

22、找、插入、刪除算法及其性能分析方法；掌握AVL樹的平衡化旋轉方法及其性能分析；掌握B- 樹的插入和刪除時結點的分裂和合.并方法；掌握 Hash 法的查找、構造方法平均查找長度的計算方法。二、本章重點、難點重點：各種樹結構表示的動態(tài)查找表和Hash 表的構造方法難點：二叉排序樹的刪除、AVL 樹的旋轉處理、 B-樹的插入和刪除、 Hash 法的構造以及各種查找表的平均查找長度的計算方法三、章節(jié)練習（一）選擇題：1. _ 二叉排序樹可得到一個關鍵字的有序序列。A. 先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 層序遍歷2用鏈地址法處理沖突構造的散列表中，每個地址單元所鏈接的同義詞表中結點的 _相

23、同。A.關鍵字B.元素值C.散列地址D.含義3利用折半查找方法在長度為n 的有序表中查找一個元素的平均查找長度是_。A.O(n 2)B.O(nlogn)C.O(n)D. O(logn)4散列表的裝填因子越大，則發(fā)生沖突的可能性就_。A.越小B.越大C.不確定5線性表中共有 256 個元素，采用分塊查找，若查找每個元素的概率相等，用順序查找確定結點所在的塊，每塊有_個元素時查找效率最佳。A. 16B. 20C. 25D. 2566用折半查找對長度為7 的有序表進行查找，則等概率下查找成功時的平均查找長度為 _。A. 15/7B. 17/7C. 18/7D. 19/77有序表（ 1，32，41，

24、45，62， 75，77，82，95，100），使用折半查找關鍵字為 95 的元素時，需要經(jīng)過 _次比較后才能查找成功。A.2B.3C.4D.5（二）判斷題：1.折半查找和二叉排序樹的查找時間性能一樣。（）2. 在任意一棵非空的二叉排序樹中，刪除某結點后又將其插入，則所得的二叉.排序樹與刪除前的二叉排序樹形態(tài)相同。（）3. 根據(jù) B-樹的定義，在 9 階 B- 樹中，除根以外的任何一個非葉子結點中的關鍵字數(shù)目均在 59 之間。（）4. 折半查找時，要求線性表必須是有序的且以順序結構存儲。（）（三）問答題：1. 設有一組關鍵字序列 19 ，1，23，14， 55，20，84，27，68， 11，

25、40 ，（ 1） 按表中元素順序構造一棵二叉排序樹，畫出這棵樹，并求其在等概率情 況下查找成功時的平均查找長度。（ 2）從空樹開始，按表中元素順序構造一棵2_3 樹(3 階 B_樹) ，若此后再刪除55，84，畫出每一步執(zhí)行后2_3 樹的狀態(tài)。2. 設散列函數(shù) H(key)=key MOD 7, 用線性探測再散列法解決沖突。對關鍵字序列 13 ，28，72，5，16，8，7，11 在地址空間為 0-10 的散列區(qū)中建散列表，畫出此表，并求等概率情況下查找成功時的平均查找長度。3. 關鍵字序列： 13， 28，72，5，16，18， 7，11， 24，h (key) = key mod 11,表

26、長為 11，用線性探測再散列處理沖突， 試填寫下表并計算每個關鍵字的比較次數(shù)和等概率情況下查找成功時的平均查找長度。0哈希表比較次數(shù)ASL=4. 在地址空間為 0-16 的散列區(qū)中，對以下關鍵字序列 (Jan,Feb,Mar,Apr,May, June,July,Aug,Sep,Oct,Nov,Dec) 按鏈地址法處理沖突構造散列表， 設散列函數(shù)H(x)=i/2,其中 i 為關鍵字中第一個字母在字母表中的序號。畫出該散列表并求在等概率情況下查找成功時的平均查找長度。第十章排序一、章節(jié)學習目標與要求1、理解排序相關的定義以及排序方法的各種分類，理解各種排序方法的基本思想和依據(jù)原則。2、掌握內部排

27、序的基本概念和性能分析方法；掌握插入排序、交換排序、選擇排序等內排序的方法及其性能分析方法。.二、本章重點、難點重點：各類內部排序方法所依據(jù)的原則、特點及典型算法。難點：希爾排序、快速排序、堆排序三、章節(jié)練習（一）選擇題：1. 下列方法中， _是穩(wěn)定的排序方法。A堆排序 B. 希爾排序 C. 快速排序 D. 折半插入排序2. 設有 1000 個無序的元素，希望用最快的速度選出其中前 20 個最大的元素，最好用 _排序方法。A. 冒泡排序B.快速排序C.堆排序D.希爾排序3下列序列中， _是堆。A. 12 ， 35，20， 60，40，30B. 100，85，120， 38，10，9，36C.

28、1 ，5，6，24，7，3，4 D. 38，24，15，20，30， 464在待排序的元素序列基本有序時，效率最高的排序方法是_ _ 。A. 插入排序B.選擇排序C.快速排序D.歸并排序5在下列排序方法中，某一趟結束后未必能選出一個元素放在其最終位置上的是 _。A. 堆排序B.起泡排序C.快速排序D.直接插入排序6 對序 列 22,86,19,49,12,30,65,35,18進行 一趟 排 序后 得到 的結 果為18,12,19,22,49,30,65,35,86，則其使用的排序方法為_。A. 插入排序B.選擇排序C.快速排序D.起泡排序7. 下列方法中， _算法的時間復雜度為 O(n2 )

29、 。A.堆排序B.希爾排序C.快速排序D.直接插入排序8.對 n 個記錄的序列進行堆排序，最壞情況下的時間復雜度為_。A. O(logn)B. O(nlogn)C. O(n)D.O(n2)（二）判斷題：1. 快速排序的速度在所有排序方法中是最快的， 而且所需的附加空間也最少。（ ）2. 對一個堆按層次遍歷，不一定能得到一個有序序列。（）3. 由于希爾排序的最后一趟與直接插入排序過程相同，所以前者一定比后者花費.的時間多。（）4. 快速排序算法在待排序數(shù)據(jù)有序時最不利于發(fā)揮其長處。（）（三）問答題：1. 在快速排序過程中，通常取序列中的第 1 個記錄作為樞軸，以它為“分界線”重排其余記錄。 但當

30、初始記錄序列按關鍵字有序或基本有序時， 快速排序將蛻化為起泡排序，為改進之，應如何選取樞軸記錄？2. 判斷以下序列是否是堆，若不是，把它調整為堆（要求記錄交換次數(shù)最少） ，寫出調整后的序列。1） 5 ， 26，20，60，80，35， 53，70 2） 26 ，33，35，29，19， 12，22 3. 已知關鍵字序列 70 ，83， 100，65， 10， 9，7，32 ，寫出直接插入排序和快速排序每一趟結束時的關鍵字狀態(tài)。4. 設關鍵字集合為 10 ，2，14， 8， 12，13 ，(1) 寫出用希爾排序方法對序列排序時每一趟結束時的關鍵字狀態(tài)。(2) 用堆排序方法對其從小到大排序，畫出堆

31、排序的初態(tài)、建堆和排序過程中重建堆的過程?？荚嚹M題客觀題部分一、單項選擇題：（每空 2 分，共 20 分）1. 單鏈表是線性表的一種 _的存儲結構。A.順序存取 B. 隨機存取 C. 索引存取2. 棧和隊列的共同點是 _。A. 都是后進先出 B. 都是先進先出C. 都是只允許在端點處插入和刪除元素D. 無共同點3. 設 s=HE IS A WORKER,t=WORKER。則index(s,t,5)的返回值是 _。A.4B.5C.6D.9E.104.串是一種特殊的線性表，其特殊性體現(xiàn)在_。.A. 可以順序存儲B.數(shù)據(jù)元素是一個字符C.可以鏈接存儲D.數(shù)據(jù)元素可以是多個字符5樹最適合用來表示 _

32、。A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C元素之間具有分支層次關系的數(shù)據(jù)D.元素之間無關聯(lián)的數(shù)據(jù)6 4 個頂點的無向完全圖有 _條邊。A. 6B. 12C. 16 D. 207散列表的裝填因子越大，則發(fā)生沖突的可能性就 _。A. 越小B.越大C.不確定8.在長度為 n 的有序表中折半查找一個元素的平均查找長度是 _。A.O(n2)B.O(nlogn)C.O(n)D. O(logn)9. 下列方法中， _是不穩(wěn)定的排序方法。A. 折半插入排序 B. 直接插入排序 C. 冒泡排序 D. 堆排序10_二叉排序樹可得到一個關鍵字的有序序列。A. 先序遍歷 B. 中序遍歷 C.后序遍歷 D.層序遍歷二、是非題

33、：（每題 1 分，共 10 分）（說明：正確的選“ A” , 錯誤選“ B” ）1 線性表的順序存儲結構優(yōu)于鏈式存儲結構。（）2 空串和空格串是相同的。（）3 圖結構中，每個結點的前驅和后續(xù)都可以有任意多個。（）4 快速排序算法在待排序數(shù)據(jù)有序時最不利于發(fā)揮其長處。（）5 連通網(wǎng)的最小生成樹是唯一的。（）6 棧是 FIFO 的線性表。（）7 由二叉樹的先序和后序遍歷序列不能唯一確定這棵二叉樹。（）8 若從無向圖的一個頂點出發(fā)進行廣度優(yōu)先遍歷可訪問到圖中的所有頂點，則該圖一定是連通圖。（）9 折半查找方法要求查找表必須是關鍵字的有序表，但是對存儲結構沒有限制。（）10 在一棵非空二叉樹的中序遍歷

34、序列中，根結點的右邊只有其右子樹上的所有結點。（）.主觀題部分一、簡答題：（ 50 分）1. 若線性表要求以最快的速度存取而表中元素變動不大，則應采取什么存儲結構（順序或鏈式結構）？為什么？（ 10 分）2. 將下圖所示森林轉化為二叉樹并在其上標出中序全線索。 （ 10 分）3. 已知如右圖所示的有向圖，寫出該圖的 :(1) 鄰接矩陣 (2 ）一個可能的拓撲有序序列。 （10 分）4設散列函數(shù) H(key)=key MOD 7, 用線性探測再散列法解決沖突。對關鍵字序列 13，28，72， 5， 16，8，7，9，11， 29 在地址空間為 0-10 的散列區(qū)中建散列表，畫出此表，并求等概率情

35、況下查找成功時的平均查找長度。（10 分）5對于序列 26 ， 33，35， 29，19，12， 22 ，（ 1）判斷它是否是堆，若是，寫出其是大頂堆還是小頂堆；若不是，把它調整為堆，寫出調整的過程和調整后的序列。（5 分）（ 2）寫出對該序列進行直接插入排序每一趟結束時的關鍵字狀態(tài)。（ 5 分）二、算法設計題：（20 分）1、編寫遞歸算法，計算二叉鏈表存儲的二叉樹的結點數(shù)目。（ 10 分）2、基于圖的深度優(yōu)先遍歷策略寫一算法，判斷以鄰接表方式存儲的無向圖中連通分量的個數(shù)。（10 分）.附：答案或答案要點第一章章節(jié)練習答案（一）選擇題：1D2C3A4C5A6B7B8D（二）判斷題：123.4第

36、二章章節(jié)練習答案（一）選擇題： 1B, A2C3C4C5A, B, C 6.B, A（二）判斷題： 123（三）問答題：1應采用順序結構。因為順序表是隨機存取的存儲結構，在順序表中存取任何元素所花的時間都一樣。而鏈表是順序存取的存儲結構。2應采用鏈式結構。 因為在鏈表中是以結點的指針變化來反映邏輯關系的變化，因此不需要移動元素，效率高。3頭結點在位置上可視為首元結點的前驅，則做插入/ 輸出操作時， i=1 （即插入或刪除的位置是1）時不需要做特別處理，否則i=1 時需要修改頭指針。（四）算法題：1status insert_L (LinkList L, ElemType x)/* 帶頭結點 *

37、/LinkList p,s;for (p=L; p-next & p-next-datanext); s=(LinkList )malloc(sizeof(LNode); if (!s) return OVERFLOW;s-data=x;s-next=p-next;p-next=s;return OK;2status insert_Sq(SqList *va,ElemType x)int i;if( va-length=va-listsize) exit OVERFLOW;.for( i=va-length-1;i=0 & va-elemix;-i)va-elemi+1= va-elemi;v

38、a-elemi+1=x; va-length+;return OK;3void reverse(LinkList L)/* 帶頭結點 */LinkList p;p=L-next;L-next=NULL;for(; p; p=p-next)q=p-next;p-next=L-next;L-next=p;第三章章節(jié)練習答案（一）選擇題： 1. C2.C 3. B4.C5. B,A6. A，C（二）判斷題： 1234（三）問答與算法題：1所有可能的輸出序列有：ABC、ACB、BAC、BCA、CBA2算法：#define MAXQSIZE 100typedef struct ElemType *ele

39、m;intfront;intlength;CycQueue;statusEnQueue(CycQueue *Q, ElemType e).if (Q-length=MAXQSIZE) return ERROR;Q-elem(Q-front+Q-length) % MAXQSIZE=e;Q-length+;return OK;status DeQueue(CycQueue *Q, ElemType *e)if (Q-length=0) return ERROR;*e= Q-elemQ-front;Q-length - -;return OK;第四章章節(jié)練習答案（一）選擇題： 1.B2.D3.B4

40、.D5.B6.A（二）判斷題： 1. 2. 3. 4.第七章章節(jié)練習答案（一）選擇題： 1. B2.A 3.B4. B（二）判斷題： 1. 2. 3. 4. 5.（三）問答題：1.2證明：由于深度為 k 的二叉樹的最大結點數(shù)為二叉樹上每一層的最大結點數(shù)之和，而二叉樹上第 i 層的最大結點數(shù)為 2i-1。則kk(第 i層的最大結點數(shù) )2i-12 k1i 1i 13. 證明：設 n0 為葉子結點個數(shù)， n2 為度為 2 的結點個數(shù)，則由二叉樹的性質 2 可知： n2= n0 1又：滿二叉樹中只有度為 2 的結點和葉子結點，所以滿二叉樹中的結點總數(shù)n= n2+ n0 =2 n01又：二叉樹中的分支數(shù) B=n1所以： B=2 n0 1=2(n01)14.wpl=(16+17)*2+(9+14+15)*3+6*4+(2+3)*5=229（四）算法題：1void output(BiTree t)if (t)output(t-lchild);printf(t-data);output(t-rchild);.2.voidexchange(BiTree t)BiTree temp;if (t)temp=t-lchild;