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

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

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

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

5、、安全性、可行性D. 有窮性、確定性、可移植性7設n為正整數。則下面程序段的時間復雜度為_。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為正整數。則下面程序段的時間復雜度為_。k=0; for(i=1;i<=n;i+) for(j=i;j<=n;j+) k+; A.O(1) B. O(n) C. O(nlogn) D. O(n2)（二）判斷題：1在數據結構中，從邏輯上可以把數據結構分為動態結構和靜態結構兩大類。（ ）2任何一個算法的設計取決于數據的邏輯結構，而算法的實現則

6、依賴于所采用的存儲結構。 （ ）3. 數據元素是數據的不可分割的最小單位。 （ ）4. 算法分析的兩個主要方面是時間復雜度和空間復雜度。 （ ）第二章 線性表一、 章節學習目標與要求1、理解線性表的邏輯結構特性、順序表和鏈表表示線性表的優缺點、循環鏈表和雙向鏈表的特點。2、 掌握線性表的兩種存儲方式及其實現：熟練掌握順序表和鏈表的創建、插入元素、刪除元素以及定位等常用操作的實現算法并會求相應算法的時間復雜度。二、本章重點、難點重點：線性表的特點、兩種表示方式及它們的運算實現，會求算法的時間復雜度。難點：單鏈表結構、特點及其實現三、章節練習（一）選擇題：1順序表是一種_的存儲結構，單鏈表是_的存

7、儲結構。A. 順序存取 B. 隨機存取 C. 索引存取2順序表中第一個元素的起始存儲地址為100，每個元素的長度為4，則第五個元素的起始地址是_。A. 105 B. 110 C. 116 D. 1203非空循環單鏈表(head為頭指針)的尾結點（由指針p所指示）應滿足_。A. p->next=NULL; B. p=NULL; C. p->next=head; D. p=head;4若在線性表的任何位置上插入元素的概率是相等的，那么在長度為n的順序表中插入一個元素時需平均移動_個元素。A. n B. (n-1)/2 C.n/2 D. (n+1)/25在帶頭結點的非空單鏈表中，頭結點的

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

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

10、的存儲空間將線性表（a1,a2,an）逆置為（an ,an-1,a1）。第三章 棧和隊列一、 章節學習目標與要求1、理解用棧和隊列解決實際問題的方法。2、掌握棧和隊列的定義以及特性、它們的2種不同的存儲表示方法（特別是順序棧和循環隊列）以及各種常見操作（如入、出操作）在不同表示方式上的實現。二、本章重點、難點重點：棧和隊列的定義、各種表示和實現方法，加深對線性結構的理解難點：循環隊列的表示及為解決循環隊列隊空、隊滿判斷條件相同而使用的不同實現方式；能在具體問題中靈活運用棧和隊列結構。三、章節練習（一）選擇題：1一個棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是_。A. edcba

11、B.decba C.dceab D.abcde2棧和隊列的共同點是_。 A. 都是后進先出 B. 都是先進先出 C. 都是只允許在端點處插入和刪除元素 D.無共同點3一個隊列的入隊序列是1,2,3,4,則隊列的輸出序列是_。A. 4321 B. 1234 C. 1432 D. 32414棧的入棧序列是1，2，n，輸出序列為p1,p2,pn,若p1=n, 則pi為_。A. i B. n-i C. n-i+1 D. 不確定5隊列是限定在_進行插入，在_進行刪除的線性表。A. 隊頭 B. 隊尾 C. 任意位置6循環隊列中，設隊列元素依次存放在Q0.m中，f、r分別指示隊頭元素位置和隊尾元素的下一個位

12、置，約定存儲m個元素時為隊滿。則隊列空的判定方法是_,隊列滿的判定方法是_。A.f=r B. (f+1)%(m+1)=r C. (r+1)%(m+1)=f D. (r+1)%m=f（二）判斷題：1若用戶無法估計所用隊列的最大長度，則最好采用鏈隊列。 （ ）2在鏈隊列上刪除隊頭元素時，只需修改頭結點中的指針，不必修改尾指針。 （ ）3. 棧是限定僅在棧頂進行插入或刪除操作的線性表。 （ ）4. 隊列是限定在隊尾插入元素，在隊頭刪除元素的線性表。 （ ）（三）問答與算法題：1對于一個棧，若輸入序列依次為A,B,C, 試給出所有可能的輸出序列。2假設將循環隊列定義為：以整型域變量front和leng

13、th分別指示循環隊列中隊頭元素位置和隊列中元素個數，指針elem指示存放隊列元素的連續空間的首地址，寫出相應的入隊列和出隊列的算法。第四章 串一、 章節學習目標與要求1、理解串的抽象數據類型的定義以及相關術語、理解串在文本編輯中的作用。2、掌握字符串的定義及各種基本操作的運算結果以及串的各種存儲表示的特點。二、本章重點、難點重點：串的基本運算、串的各種存儲表示和特點。繼續加深對線性結構的理解難點：串的不同存儲結構，區分它們和高級語言中串的存儲方式的不同。三、章節練習（一）選擇題：1設串s="I AM A STUDENT", 則其串長是_。 A. 13 B. 14 C. 15

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

15、" B."teacher" C. "a teacher" D." teacher"6.設串s="student.",t=“good ",則執行StrInsert(s,1,t)后，s為_。A. "good student." B."good student"C. "goodstudent" D." good teacher"（二）判斷題：1空串和空格串是相同的。 （ ）2. 如果兩個串含有相同的字符，則它們是相同的。（

16、 ）3. 串的基本操作和線性表的一樣，都是以“單個元素”作為操作對象的。 （ ）4. 在串的鏈式存儲結構中，結點大小與存儲密度之間沒有關系。 （ ）第七章 樹和二叉樹一、章節學習目標與要求1、理解樹、二叉樹和森林的概念，理解線索化二叉樹的特性、創建方法及在線索二叉樹上尋找某結點的前驅和后繼的方法；理解樹與森林的存儲方法。2、掌握二叉樹的性質及表示；掌握二叉樹的各種遍歷方法（尤其是遞歸形式的）以及遍歷在實際問題中的應用；掌握樹及森林與二叉樹的轉換及遍歷方式的對應；掌握Huffman樹的構造方法以及構造Huffman編碼的方法。二、本章重點、難點重點：二叉樹的性質（及證明）、存儲結構及各種遍歷算法

17、，二叉樹的線索化過程，樹和森林與二叉樹的轉換關系，Huffman樹及Huffman編碼的構造方法難點：各種遍歷算法的遞歸實現以及在具體問題中能靈活運用遍歷思想解題三、章節練習（一）選擇題：1下列關于二叉樹的說法中，正確的有_。A. 二叉樹的度為2 B. 二叉樹的度可以小于2 C.二叉樹中至少有一個結點的度為2 D. 二叉樹中任一個結點的度都為22任何一棵二叉樹的葉子結點在先、中、后序遍歷序列中的相對次序_。A. 不發生改變 B. 發生改變 C. 不能確定 D. 以上都不對3下面幾個符號串編碼集合中，不是前綴編碼的是_。A. 0，10，110，1111 B. 11，10，001，101，0001

18、C. 00，010，0110，1000 D. b,c,aa,ac,aba,abb,abc4二叉樹按某種順序線索化后，任意結點均有指向其前驅和后繼的線索，這種說法_。A. 正確 B. 不正確 C. 無法確定（二）判斷題：1.哈夫曼樹是帶權葉子數目固定的二叉樹中帶權路徑長度最小的。 （ ）2.根據二叉樹的定義，具有3個結點的二叉樹有5種不同的形態。 （ ）3.深度為k的完全二叉樹至少有2k-1個結點，至多有2k1個結點。 （ ）4. 具有n個結點的滿二叉樹，其葉子結點個數為個。 （ ）5. 在哈夫曼樹中，通常權值較大的結點離根較遠。 （ ）（三）問答題：1下圖所示森林轉化為相應的二叉樹，并在其上標

19、出中序全線索。2證明：深度為k的二叉樹上至多有2k-1個結點（k1）。3.證明：任何一棵滿二叉樹中的分支數B滿足B=2(n01)，其中n0為葉子結點個數。4. 以數據集15，3，14，2，6，9，16，17為葉子的權值構造Huffman樹，畫出此樹并計算其帶權路徑長度。（四）算法題：1. 假設二叉排序樹（t為指向根結點的指針）中各元素值均不相同，設計一個遞歸算法按遞增順序輸出樹上各元素值。2編寫遞歸算法, 交換二叉鏈表存儲的二叉樹中每個結點的左、右子樹。3. 編寫遞歸算法，求以二叉鏈表存儲的二叉樹的深度。4. 設計遞歸算法計算以二叉鏈表存儲的二叉樹的葉子結點數目。第八章 圖一、章節學習目標與要

20、求1、理解圖的基本概念和術語。2、掌握圖的鄰接矩陣和鄰接表2種表示方法；掌握圖的兩種遍歷算法及其求解連通性問題的方法；掌握用Prim算法和Kruskal算法構造最小生成樹的過程和性能分析；掌握AOV網的拓撲排序方法 (不要求算法)，掌握用Dijkstra方法求解單源最短路徑問題的方法(不要求算法)。二、本章重點、難點重點：圖的數組表示法和鄰接表表示法存儲結構以及圖的兩種遍歷方式，求最小生成樹的兩種方法，AOV網的拓撲排序方法，掌握單源最短路徑的求法難點：圖的兩種遍歷算法的實現以及在圖的連通性問題中的應用三、章節練習（一）選擇題：1. 4個頂點的無向完全圖有_條邊。A. 6 B. 12 C. 1

21、6 D. 202無向圖的鄰接矩陣是一個_。A. 對稱矩陣 B. 零矩陣 C. 對角矩陣 D. 上三角矩陣3圖的廣度優先遍歷算法類似于二叉樹的_，圖的深度優先遍歷算法類似于二叉樹的_。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

22、) F. O(e2)（二）判斷題：1.若從無向圖的一個頂點出發進行廣度優先遍歷可訪問到圖中所有頂點，則該圖一定是連通圖。 （ ）2. 若從無向圖的一個頂點出發進行深度優先遍歷可訪問到圖中所有頂點，則該圖一定是連通圖。 （ ）3.任何有向圖的頂點都可以排成拓撲有序序列，而且拓撲序列不唯一。（ ）4.有n個頂點和n-1條邊的無向圖一定是生成樹。 （ ）5. 一棵有n個頂點的生成樹有且僅有n-1條邊。 （ ）6.連通分量是無向圖的極大連通子圖，而生成樹是無向圖的極小連通子圖。（ ）（三）問答及算法題：1.一個圖的鄰接矩陣G.arcs=，該圖有多少個頂點.如果是有向圖，該圖共有多少條弧.如果是無向圖，

23、該圖共有多少條邊"2.已知如右圖所示的有向圖，寫出該圖的: (1)鄰接矩陣(2）一個可能的拓撲有序序列 （3）寫出從1出發的深度優先遍歷序列（4）寫出從5出發的廣度優先遍歷序列。3. 假設有5項活動C1C5，每項活動要求的前驅活動如下： C1：無； C2：C1，C3； C3：C1； C4：C3，C5 C5：C2； 試根據上述關系，畫出相應的有向圖，再寫出一個拓撲排序序列。4. 基于圖的深度優先遍歷策略寫一算法，判斷以鄰接表方式存儲的無向圖中連通分量的個數。 第九章 查找一、章節學習目標與要求1、理解各種查找表的定義、各種查找方法的思想以及構造查找表所依據的原則。2、掌握線性表表示的靜

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

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

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

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

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

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

30、，38，10，9，36 C. 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. 下列方法中，_

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

32、樞軸，以它為“分界線”重排其余記錄。但當初始記錄序列按關鍵字有序或基本有序時，快速排序將蛻化為起泡排序，為改進之，應如何選取樞軸記錄.2.判斷以下序列是否是堆，若不是，把它調整為堆（要求記錄交換次數最少），寫出調整后的序列。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，寫出直接插入排序和快速排序每一趟結束時的關鍵字狀態。4.設關鍵字集合為10，2，14，8，12，13，(1)寫出用希爾排序方法對序列排序時每一趟結束時的關鍵字狀態。(2)用堆排序方法對其從小到大排序，畫出堆排序的

33、初態、建堆和排序過程中重建堆的過程?？荚嚹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. 4 B. 5 C. 6 D. 9 E. 104. 串是一種特殊的線性表，其特殊性體現在_。A. 可以順序存儲 B. 數據元素是一個字符 C. 可

34、以鏈接存儲 D. 數據元素可以是多個字符5 樹最適合用來表示_。A. 有序數據元素 B. 無序數據元素 C 元素之間具有分支層次關系的數據 D. 元素之間無關聯的數據6 4個頂點的無向完全圖有_條邊。 A. 6 B. 12 C. 16 D. 207 散列表的裝填因子越大，則發生沖突的可能性就_。A. 越小 B. 越大 C. 不確定 8. 在長度為n的有序表中折半查找一個元素的平均查找長度是_。A.O(n2) B.O(nlogn) C.O(n) D. O(logn)9. 下列方法中，_是不穩定的排序方法。A. 折半插入排序 B. 直接插入排序 C. 冒泡排序 D. 堆排序10_二叉排序樹可得到一

35、個關鍵字的有序序列。A. 先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 層序遍歷二、是非題：（每題1分，共10分）（說明：正確的選“A”,錯誤選“B” ）1 線性表的順序存儲結構優于鏈式存儲結構。 （ ） 2 空串和空格串是相同的。 （ ）3 圖結構中，每個結點的前驅和后續都可以有任意多個。 （ ）4 快速排序算法在待排序數據有序時最不利于發揮其長處。（ ）5 連通網的最小生成樹是唯一的。 （ ）6 棧是FIFO的線性表。 （ ）7 由二叉樹的先序和后序遍歷序列不能唯一確定這棵二叉樹。（ ）8 若從無向圖的一個頂點出發進行廣度優先遍歷可訪問到圖中的所有頂點，則該圖一定是連通圖。 （ ）9 折

36、半查找方法要求查找表必須是關鍵字的有序表，但是對存儲結構沒有限制。 （ ）10 在一棵非空二叉樹的中序遍歷序列中，根結點的右邊只有其右子樹上的所有結點。（ ）主觀題部分一、簡答題：（50分）1. 若線性表要求以最快的速度存取而表中元素變動不大，則應采取什么存儲結構（順序或鏈式結構）.為什么.（10分）2.將下圖所示森林轉化為二叉樹并在其上標出中序全線索。（10分）3.已知如右圖所示的有向圖，寫出該圖的:(1)鄰接矩陣 (2）一個可能的拓撲有序序列。 （10分）4設散列函數H(key)=key MOD 7,用線性探測再散列法解決沖突。對關鍵字序列 13，28，72，5，16，8，7，9，11，2

37、9 在地址空間為0-10的散列區中建散列表，畫出此表，并求等概率情況下查找成功時的平均查找長度。（10分）5對于序列 26，33，35，29，19，12，22 ，（1）判斷它是否是堆，若是，寫出其是大頂堆還是小頂堆；若不是，把它調整為堆，寫出調整的過程和調整后的序列。（5分）（2）寫出對該序列進行直接插入排序每一趟結束時的關鍵字狀態。（5分）二、算法設計題：（20分）1、編寫遞歸算法，計算二叉鏈表存儲的二叉樹的結點數目。（10分）2、基于圖的深度優先遍歷策略寫一算法，判斷以鄰接表方式存儲的無向圖中連通分量的個數。 （10分）附：答案或答案要點第一章章節練習答案（一）選擇題： 1D 2C 3A

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

39、status insert_L (LinkList L, ElemType x)/*帶頭結點*/ LinkList p,s; for (p=L; p->next && p->next->data<x；p=p->next); 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) in

40、t i;if( va->length=va->listsize) exit OVERFLOW;for( i=va->length-1;i>=0 && va->elemi>x;-i) va->elemi+1= va->elemi; va->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->nex

41、t; p->next=L->next;L->next=p; 第三章章節練習答案（一）選擇題：1.C 2.C 3. B 4.C 5. B, A 6. A，C（二）判斷題：1 2× 3 4（三）問答與算法題：1 所有可能的輸出序列有：ABC、ACB、BAC、BCA、CBA2算法：*define MAXQSIZE 100typedef struct ElemType *elem; int front; int length; CycQueue; status EnQueue(CycQueue *Q, ElemType e) if (Q->length=MAXQSIZ

42、E) 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; 第四章章節練習答案（一）選擇題：1.B 2. D 3. B 4. D 5. B 6. A（二）判斷題：1.×2.× 3.× 4

43、.×第七章章節練習答案（一）選擇題：1. B 2. A 3. B 4. B（二）判斷題：1. 2. 3.4. 5. ×（三）問答題：2證明：由于深度為k的二叉樹的最大結點數為二叉樹上每一層的最大結點數之和，而二叉樹上第i層的最大結點數為2i-1。則3. 證明：設n0為葉子結點個數，n2為度為2的結點個數，則由二叉樹的性質2可知： n2= n01又：滿二叉樹中只有度為2的結點和葉子結點，所以滿二叉樹中的結點總數n= n2+ n0=2 n01又：二叉樹中的分支數B=n1所以：B=2 n011=2(n01)4.wpl=(16+17)*2+(9+14+15)*3+6*4+(2+3)

44、*5=229（四）算法題：1 void output(BiTree t) if (t) output(t->lchild); printf(t->data); output(t->rchild); 2. void exchange(BiTree t) BiTree temp; if (t) temp=t->lchild; t->lchild= t->rchild; t->rchild=temp; exchange (t-> lchild); exchange (t->rchild); 3. intdepth(BiTree t) int l,

45、r; if (!t) return 0;l= depth (t->lchild); r= depth (t->rchild); return (l>=r"l:r)+1; 4. void leaf(BiTree t) if (!t) return 0; if (!t->lchild && !t->rchild) return 1; return leaf(t->lchild)+leaf(t->rchild); 第八章章節練習答案（一）選擇題：1.A 2.A 3.D, A 4.D, C 5.B, D（二）判斷題: 1. 2. 3.

46、× 4. × 5. 6. （三）問答及算法題：1. 圖中共有3個頂點，如果是有向圖，該圖共有5條??；如果是無向圖，該圖共有3條邊。2.（1）鄰接矩陣： （2）可能的拓撲序列為：156234 （注意4一定是最后一個，2一定在1和5后）（3）123456（4）5624313. 一個拓撲排序序列：C1 C3 C2 C5 C4 4算法： int count (AlGraph G) for (i=0; i<G.vexnum; i+) visitedi=false; sum=0; for (i=0; i< G.vexnum; i+) if (!visitedi) sum+;

47、 dfs (G, i); return sum; void dfs (AlGraph G, int i) visitedi=true; for (p=G.verticesi.firstarc; p; p=p->nextarc) k=p->adjvex; if (!visitedk) dfs(G, k);第九章章節練習答案（一）選擇題：1.B 2.C 3.D 4.B 5.A 6. B 7. B（二）判斷題：1.× 2. × 3. × 4. 1.（1）ASL=(1+2*2+3*3+3*4+2*5)/11=36/11 (2) 2_3樹:（三）問答題：(3) 刪除55: 刪除84:2ASL=(1+1+1+2+5+1+1+4)/8=16/8=23. 3、012345678910哈希表1113245287216187比較次數112112434 ASL=（1+1+2+1+1+2+4+3+4）/9=19/94. 用鏈地址法處理沖突:（注意鏈表的有序性）ASL=(7