數(shù)據(jù)結(jié)構(gòu)練習題--2011級--參考答案講解

1、第1章選擇題：1.1 數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的表示是指：A 數(shù)據(jù)的存儲結(jié)構(gòu)B.數(shù)據(jù)結(jié)構(gòu)C數(shù)據(jù)的邏輯結(jié)構(gòu)D.數(shù)據(jù)元素之間的關(guān)系1.2 數(shù)據(jù)的邏輯結(jié)構(gòu)是指：A. 數(shù)據(jù)所占的存儲空間量B各數(shù)據(jù)元素之間的邏輯關(guān)系C. 數(shù)據(jù)在計算機中順序或鏈接的存儲方式D. 存儲在內(nèi)存或外存中的數(shù)據(jù)1.3 在下列的敘述中，正確的是：A數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關(guān)系。B數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機內(nèi)的實際存儲形式。C在順序存儲結(jié)構(gòu)中，數(shù)據(jù)元素之間的關(guān)系是顯示體現(xiàn)的。D鏈接存儲結(jié)構(gòu)是通過結(jié)點的存儲位置相鄰來體現(xiàn)數(shù)據(jù)元素之間的關(guān)系填空題：1.4數(shù)據(jù)結(jié)構(gòu)主要研究 數(shù)據(jù)的邏輯結(jié)構(gòu)， 數(shù)據(jù)的存儲結(jié)構(gòu) ， 數(shù)據(jù)的運

2、算三個方面的內(nèi)容。1.5鏈接存儲的特點是通過附加指針域來表示數(shù)據(jù)元素之間的邏輯關(guān)系。1.6數(shù)據(jù)結(jié)構(gòu)中討論的三種經(jīng)典結(jié)構(gòu)包括：線性表 ， 樹 ， 圖 。1.7數(shù)據(jù)結(jié)構(gòu)中常用的存儲方法有：順序， 鏈接 ， 索引 ， 散列 。1.8順序存儲結(jié)構(gòu)可以通過位置隱含 表示關(guān)系，鏈接存儲結(jié)構(gòu)通過附加指針來 顯示表示關(guān)系。1.9算法的特性包括 有窮性， 確定性， 可行性 ，輸入和輸出。1.10算法性能分析的兩個主要定量評價指標是時間復雜度 和 空間復雜度 。簡答題：1.11 數(shù)據(jù)結(jié)構(gòu)研究的三方面內(nèi)容之間有什么聯(lián)系和區(qū)別？ 數(shù)據(jù)結(jié)構(gòu)研究的三方面內(nèi)容包括 : 數(shù)據(jù)的邏輯結(jié)構(gòu)、 存儲結(jié)構(gòu)和運算。 數(shù)據(jù)的邏輯結(jié)構(gòu) 是

3、數(shù)學模型，存儲結(jié)構(gòu)是指邏輯結(jié)構(gòu)到存儲區(qū)域的映射，運算是定義在邏輯結(jié)構(gòu)上， 實現(xiàn)在存儲結(jié)構(gòu)上。1.12 簡述數(shù)據(jù)結(jié)構(gòu)中討論的三種經(jīng)典結(jié)構(gòu)的邏輯特征是什么？三種經(jīng)典結(jié)構(gòu)：線性表、樹和圖。邏輯特征分別為：（ 1）線性表：一對一。有且僅有一個開始結(jié)點和一個終端結(jié)點，其余的內(nèi)部結(jié)點都有 且僅有一個前趨結(jié)點和一個后繼結(jié)點。（ 2）樹：一對多。有且僅有一個開始結(jié)點，可有若干個終端結(jié)點，其余的內(nèi)部結(jié)點都 有且僅有一個前趨結(jié)點，可以有若干個后繼結(jié)點。（3）圖：多對多?？捎腥舾蓚€開始結(jié)點和終端結(jié)點，其余的內(nèi)部結(jié)點可以有若干個前 趨結(jié)點和若干個后繼結(jié)點。1.13 簡述各種常用存儲方法的基本思想。 各種方法的基本思想

4、： 順序存儲：邏輯上相鄰的數(shù)據(jù)元素存儲在物理位置上相鄰的存儲單元里。 鏈接存儲：通過附加指針域表示數(shù)據(jù)元素之間的關(guān)系。索引存儲：除了存儲數(shù)據(jù)元素，還要建立附加的索引表來標識數(shù)據(jù)元素的地址。 散列存儲：根據(jù)關(guān)鍵字直接計算出該結(jié)點的存儲地址，通常稱為關(guān)鍵字地址轉(zhuǎn)換法。第2章選擇題：2.1 線性表 L= (a1，a2， an)，下列說法正確的是：A. 每個元素都有一個直接前驅(qū)和一個直接后繼。B. 線性表中至少有一個元素。C. 表中元素的排列順序必須是由小到大或由大到小。D. 除第一個和最后一個元素外，其余每個元素都有且僅有一個直接前驅(qū)和一個直接后繼。2.2 下面關(guān)于線性表的敘述中，錯誤的是：A線性表

5、若采用順序存儲，必須占用一片連續(xù)的存儲單元B線性表若采用順序存儲，便于進行插入和刪除操作C線性表若采用鏈接存儲，不必占用一片連續(xù)的存儲單元 D線性表若采用鏈接存儲，便于插入和刪除操作2.3 在長度為 n 的順序表的第 i(1 i n+1)個位置上插入一個元素，元素的移動次數(shù)為： A .n-i+1B .n-iC .iD .i-12.4 刪除長度為 n 的順序表中的第 i(1 in)個位置上的元素，元素的移動次數(shù)為：A. n-i+1B. n-iC. iD. i-12.5 已知一個帶頭結(jié)點單鏈表L，在表頭元素前插入新結(jié)點*s 的語句為：A. L=s; s-next=L;C. s=L; s-next=

6、L;B. s-next=L-next; L-next=s;D. s-next=L; s=L;2.6 已知一個不帶頭結(jié)點單鏈表的頭指針為 L，則在表頭元素之前插入一個新結(jié)點 *s 的語句為： A. L=s; s-next=L; B. s-next=L; L=s;C. s=L; s-next=L; D. s-next=L; s=L;2.7 已知單鏈表上一結(jié)點的指針為 p，則在該結(jié)點之后插入新結(jié)點 *s 的正確操作語句為： A p-next=s; s-next=p-next;B s-next=p-next; p-next=s;C p-next=s; p-next=s-next;D p-next=s-

7、next; p-next=s;2.8 已知單鏈表上一結(jié)點的指針為 p，則刪除該結(jié)點后繼的正確操作語句是：A s= p-next; p=p-next; free(s);B p=p-next; free(p);C s= p-next; p-next=s-next; free(s);D p=p-next; free(p-next);2.9 設(shè)一個鏈表最常用的操作是在表尾插入結(jié)點和在表頭刪除結(jié)點， 則選用下列哪種存儲結(jié)構(gòu)效率最高？A. 單鏈表 B. 雙鏈表 C. 單循環(huán)鏈表 D. 帶尾指針的單循環(huán)鏈表2.10 線性表的鏈接存儲結(jié)構(gòu)是一種(A. 隨機存取 B. 順序存取2.11 鏈表不具備的特點是：A.

8、 插入刪除不需要移動元素C. 可隨機訪問任一結(jié)點)存儲結(jié)構(gòu)。C. 索引存取 D. 散列存取B. 不必事先估計存儲空間D. 所需空間與其長度成正比填空題： 2.1 在單鏈表 L 中，指針 p 所指結(jié)點有后繼結(jié)點的條件是 p-next!=NULL 。2.2 判斷帶頭結(jié)點的單鏈表 L 為空的條件 L-next=NULL 。2.12 順序表和鏈表中能實現(xiàn)隨機存取的是 順序表 ，插入、刪除操作效率高的是 鏈表 。2.13 對于一個具有 n 個結(jié)點的單鏈表，已知一個結(jié)點的指針p，在其后插入一個新結(jié)點的時間復雜度為O(1) ；若已知一個結(jié)點的值為 x，在其后插入一個新結(jié)點的時間復雜度為O( n) 。2.14

9、 順序表的存儲密度 大 ，鏈表的存儲密度 小 。簡答題：2.15 比較順序表和鏈表這兩種線性表不同存儲結(jié)構(gòu)的特點順序表存儲密度大存儲空間連續(xù)靜態(tài)分配隨機存取插、刪效率低鏈表存儲密度大存儲空間可不連續(xù)動態(tài)分配順序存取插、刪效率高2.16 簡述頭結(jié)點的作用。 頭結(jié)點的作用是使得單鏈表在表頭位置的插、刪操作同中間位置的插、刪操作完全相 同。即使“空表”與“非空表”的操作統(tǒng)一，也使“表頭結(jié)點”與其他位置結(jié)點的操 作完全一致，無須特殊處理。2.17 寫出單鏈表存儲結(jié)構(gòu)的 C 語言描述。typedef int DataType;typedef struct Node DataType data;struc

10、t Node *next;LinkList;完善程序題：2.18 設(shè)計一個算法，其功能為：向一個帶頭結(jié)點的有序單鏈表(從小到大有序)中插入一個元素x，使插入后鏈表仍然有序。請將代碼補充完整。typedef int DataType;typedef struct Node DataType data; /* 定義指向該結(jié)構(gòu)類型的指針變量 next*/Linklist;void insert(Linklist *L,DataType x) Linklist *s,*p=L;while(p-next & p-next-datadata=x; ; /* 將 *s 結(jié)點插入到 *p 結(jié)點的后面 */st

11、ruct Node * next;2.19 設(shè)計一個函數(shù)功能為：在帶頭結(jié)點的單鏈表中刪除值最小的元素。請將代碼補充完整。 typedef int DataType;typedef Node/* 定義結(jié)構(gòu)體類型 */ DataType data;struct Node * next;LinkList;void deleteMin(LinkList *L) LinkList *p=L-next,*q;/* 首先查找值最小的元素，指針 q 指向最小元素結(jié)點 */q=p;while(p) if( p-data data)q=p; /* p 指針后移一步，比較單鏈表中的每一個結(jié)點 */if(!q) re

12、turn; /* 不存在最小結(jié)點(空表)時，直接退出 */p=L; /*若存在最小結(jié)點，則先找到最小結(jié)點的前驅(qū)，即 *q 的前驅(qū) */ while( ) p=p-next; /* 從單鏈表中刪除最小元素結(jié)點(指針 q 所指結(jié)點) */; /* 釋放指針 q 所指結(jié)點的空間 */structp=p-next;p-next!=qp-next=q-next;free(q);算法設(shè)計題：2.20 已知長度為 n 的線性表 A 中的元素是整數(shù)，寫算法求線性表中值大于 item 的元素個數(shù)。分兩種情況 編寫函數(shù)：( 1)線性表采用順序存儲； ( 2)線性表采用單鏈表存儲。(1)線性表采用順序存儲#defi

13、ne MAX 1024typedef int DataType;typedef struct DataType dataMAX;int last; SeqList;int LocateElem (SeqList *L, DataTypeitem) int i,j=0;for(i=0;ilast ;i+)if( L-datai item ) j+;return j;(2)線性表采用單鏈表存儲typedef int DataType;typedef struct Node DataType data;struct Node *next;LinkList;int locateElem(LinkLis

14、t *L, DataTypeitem )LinkList *p=L-next;int i=0; while ( p )if( p-data item) i+; return i ;2.21 試寫一算法實現(xiàn)對不帶頭結(jié)點的單鏈表 H 進行就地（不額外增加空間）逆置typedef int DataType;typedef struct Node DataType data; struct Node *next;LinkList;LinkList * Reverse(LinkList * L) LinkList *p,*q;if (!L) return;p=H-next; q=H-next; L-ne

15、xt=NULL; while(q)q=q-next; p-next= L; L=p; p=q; return L;第3章選擇題：3.1 設(shè)一個棧的輸入序列是 1，2， 3，4，5，則下列序列中，是棧的合法輸出序列的是：A. 5 1 2 3 4B. 4 5 1 3 2C. 4 3 2 1 5D. 3 5 2 4 13.2 設(shè)有一順序棧，元素 1，2，3，4，5 依次進棧，如果出棧順序是 2，4，3，5，1 則棧的容量至少是：A .1 B. 2 C. 3D. 43.3 若用一個大小為 6 的數(shù)組來實現(xiàn)循環(huán)隊列，且當前 rear 和 front 的值分別為 0 和 3，當入隊一個元素， 再出隊兩個元

16、素后， rear 和 front 的值分別為：A. 1 和 5 B. 2 和 4 C. 4 和 2D. 5 和 1填空題：3.4 棧和隊列都是操作受限的線性表，棧的運算特點是 LIFO ，隊列的運算特點是 FIFO 。3.5 若序列 a、b、c、d、e 按順序入棧， 假設(shè) P 表示入棧操作， S表示出棧操作， 則操作序列 PSPPSPSPSS 后得到的輸出序列為 acdeb 。3.6 已知一個順序棧 *s，棧頂指針是 top ，它的容量為 MAXSIZE ，則判斷?？盏臈l件為 s-top=-1 ， 棧滿的條件是 s-top=MAXSIZE-1 。3.7 對于隊列來說，允許進行刪除的一端稱為 隊

17、頭 ，允許進行插入的一端稱為 隊尾 。3.8 某循環(huán)隊列的容量 MAXSIZE =6，隊頭指針 front=3 ，隊尾指針 rear=0，則該隊列有 _3_個元素。 簡答題：3.9 棧上的基本運算有哪些？ 棧的基本運算有： （ 1）初始化棧 initStack （ s）：構(gòu)造了一個空棧 s。 （2）判?？?empty（s）：若棧 s為空棧，返回值為“真” （1），否則返回值為“假” （0）。3）入棧 push（s，x）：在棧 s的頂部插入一個新元素 x， x 成為新的棧頂元素。4）出棧 pop（ s）：刪除棧 s 的棧頂元素。5）讀棧頂元素 top（ s）：棧頂元素作為結(jié)果返回，不改變棧的狀態(tài)

18、。循環(huán)順序隊列圖示：front3.10 循環(huán)順序隊列的存儲結(jié)構(gòu)圖示及 C 語言描述？ C 語言描述：#define MAXSIZE 1024typedef int DataType;typedef struct DataType dataMAXSIZE;int rear , front;SeQueue;SeQueue *sq;3.11 簡述棧和隊列有哪些聯(lián)系與區(qū)別？ 棧和隊列都是運算運算受限的線性表，邏輯結(jié)構(gòu)相同；都可以順序存儲和鏈接存儲， 存儲結(jié)構(gòu)也相同；插入和刪除運算都限制在線性表的表端完成，且不需要查找運算。 二者差別主要體現(xiàn)在運算的限制不同：棧是后進先出（LIFO ）的線性表，限制它的

19、插入和刪除操作僅在表的一端進行。隊列是先進先出（FIFO ）的線性表，只允許在表的一端進行插入，而在表的另一端進行刪除。算法設(shè)計題：3.12 通常稱正讀和反讀都相同的字符序列為 “回文 ”，例如， “ abcdeedcba、”“ abcdcba是”回文。若字符序列 存儲在一個單鏈表中，編寫算法判斷此字符序列是否為回文。 （提示：將一半字符先依次進棧） #define maxsize 100 typedef char datatype1;typedef struct datatype1 datamaxsize;int top; seqstack;typedef int datatype;type

20、def struct node datatype data;struct node *next; Linklist;Duichen（Linklist *head） int i=1;Linklist *p;seqstack *s;s=initSeqStack（）;p= head-next;n=0;while（p）n+; p=p-next;p=head-next;while(idata); i+; if (n%2!=0) p=p-next;while(p&p-data=pop(s) p=p-next;if (p) return 0 else return 1;選擇題：5.1 設(shè)數(shù)據(jù)結(jié)構(gòu) D-S 可

21、以用二元組表示為 D-S=（D ，S），rS，其中： D=A ，B，C，D ，r=A ，B，A，C，B，D，則數(shù)據(jù)結(jié)構(gòu) D-S 是：A 線性結(jié)構(gòu)B樹形結(jié)構(gòu)C5.2 樹最適合用來表示： A有序數(shù)據(jù)元素 C元素之間具有分支層次關(guān)系的數(shù)據(jù)5.3 有關(guān)二叉樹下列說法正確的是：A 二叉樹是度為 2 的有序樹C二叉樹中至少有一個結(jié)點的度為 2圖形結(jié)構(gòu)D集合B.無序數(shù)據(jù)元素D.元素之間無聯(lián)系的數(shù)據(jù)B 二叉樹中結(jié)點的度可以小于 2D 二叉樹中任何一個結(jié)點的度都為 25.4 深度為 10的完全二叉樹，第 3 層上的的結(jié)點數(shù)是：A .15 B .16 C . 4 D .325.5 設(shè)一棵樹的度為 4，其中度為 1

22、、2、3、4 的結(jié)點個數(shù)分別為 6、3、2、1，則這棵樹中葉子結(jié)點的個 數(shù)為：A .8 B. 9 C. 10 D. 115.6 對于二叉樹來說，第 i 層上最多包含的結(jié)點個數(shù)為：A2i - 1B. 2i + 1C2iD.2i5.7 樹的后根遍歷序列等同于與該樹對應的二叉樹的哪種序列？A. 前序序列 B. 中序序列 C. 后序序列 D. 層序序列5.8 設(shè)森林 F 中有三棵樹，第一，第二，第三棵樹的結(jié)點個數(shù)分別為M1，M2和 M 3。與森林 F 對應的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是：A M1BM1+M 2CM3DM2+M 3填空題：5.9 二叉樹具有 10個度為 2的結(jié)點， 5個度為 1的結(jié)

23、點，則度為 0的結(jié)點個數(shù)是 115.10 包含 n個結(jié)點的二叉樹，高度最大為n ，高度最小為 log2 n 1。5.11 某完全二叉樹共有 200 個結(jié)點，則該二叉樹中有 1 個度為 1 的結(jié)點。5.12 一棵高度為 10 的滿二叉樹中的結(jié)點總數(shù)為210-1 個，其中葉子結(jié)點數(shù)為 29 。5.13 某完全二叉樹結(jié)點按層順序編號（根結(jié)點的編號是1），若 21 號結(jié)點有左孩子結(jié)點，則它的左孩子結(jié)點的編號為 _42_。k-1 k5.14 深度為 k 的完全二叉樹至少有2k-1 個結(jié)點，至多有 2k-1 個結(jié)點。5.15 n 個結(jié)點的線索二叉樹上含有 n+1 條線索。簡答題：5.16 畫出包含三個結(jié)點

24、的樹和二叉樹的所有不同形態(tài)。5.17 找出滿足下面條件的二叉樹：（ 1）前序遍歷與中序遍歷結(jié)果相同： 只有右分支的單分支二叉樹（ 2）前序遍歷和后序遍歷結(jié)果相同： 只有一個根結(jié)點的二叉樹（ 3）中序遍歷和后序遍歷結(jié)果相同： 只有左分支的單分支二叉樹5.18 一棵二叉樹的中序、后序遍歷序列分別為：G L D H B E I A C J F K 和 L G H D I E B J K F C A ，請回答：1）畫出二叉樹邏輯結(jié)構(gòu)的圖示。2）畫出此二叉樹的二叉鏈表存儲結(jié)構(gòu)的圖示并給出C 語言描述。3）畫出上題中二叉樹的中序線索二叉樹。4）畫出中序線索二叉鏈表存儲結(jié)構(gòu)圖示并給出C 語言描述。1）二叉樹

25、的邏輯結(jié)構(gòu)圖示：2）二叉鏈表存儲結(jié)構(gòu)的圖示及 C 語言描述：rootAEBDGHILFJKtypedef char DataType; typedef struct Node DataType data;struct Node *lchild,*rchild; BiTree;3）中序線索二叉樹：NULL4 ）中序線索二叉鏈表的圖示及 C 語言描述：typedef char DataType; typedef struct Node DataType data;struct Node *lchild,*rchild; int ltag,rtag;BiThrTree;5.19 設(shè)有森林如圖 5.3

26、1 所示，請回答：1）畫出與該森林對應的二叉樹的邏輯結(jié)構(gòu)圖示2）寫出該二叉樹的前序、中序、后序遍歷序列3）畫出該二叉樹的中序線索二叉鏈表的圖示并給出C 語言描述。CEG圖 5.311）二叉樹的邏輯結(jié)構(gòu)圖示：2）前序遍歷序列： ABCDFGEH ，中序遍歷序列： ADGFCBHE后序遍歷序列： GFDCHEBA3 ）中序線索二叉鏈表的圖示及 C 語言描述：1A00B0typedef char DataType; typedef struct Node DataType data;struct Node *lchild,*rchild; int ltag,rtag;BiThrTree;0E11H1

27、0F115.20 設(shè)有森林 B=(D,S),D=A,B,C,D,E,F,G ,H,I,J, r S r=, 請回答：1）畫出與森林對應的二叉樹的邏輯結(jié)構(gòu)圖示。2）寫出此二叉樹的前序、中序、后序遍歷序列3）畫出此二叉樹的二叉鏈表存儲結(jié)構(gòu)的圖示并給出C 語言描述。1）與森林對應的二叉樹的邏輯結(jié)構(gòu)圖示：3）二叉鏈表存儲結(jié)構(gòu)的圖示及C 語言描述：roottypedef char DataType; typedef struct Node DataType data;struct Node *lchild,*rchild; BiTree;5.21 請畫出 5.32 中的各二叉樹對應的森林。BCHa）（

28、b）c）d）2）前序遍歷序列： ABECFDGHIJ ， 中序遍歷序列： EBFCDAHJIG 后序遍歷序列： EFDCBJIHGA圖 5.32FIa ）（ b ）（c ）105.22 假設(shè)用于通信的電文由字符集 a，b，c，d，e，f，g，h中的字母構(gòu)成，這 8 個字母在電文中出現(xiàn)的 概率分別為 0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10，試為這 8 個字母進行哈夫曼編碼。請 回答：1）畫出哈夫曼樹（按根點權(quán)值左小右大的原則）2）寫出依此哈夫曼樹對各個字母的哈夫曼編碼。1）哈夫曼樹：107 a6 d01132 e10h3）求出此哈夫曼樹的帶權(quán)路徑長度WPL

29、2)各字母的哈夫曼編碼： a:1010 b:00 c:10000 d:1001 e:11 f:10001 g:01 h:10113）哈夫曼樹的帶權(quán)路徑長度WPL ：nWPLwilii1=0.07 4+0.19 2+0.02 5+0.06 4+0.32 2+0.03 5+0.21 2+0.10 4=2.61 完善程序題：5.23 設(shè)計一個算法，其功能為：利用中序線索求結(jié)點的中序后繼。請將代碼補充完整。 typedef char DataType;typedef struct Node DataType data;struct Node *lchild, ;int ltag,rtag;BiThrT

30、ree;BiThrTree * InOrderNext(BiThrTree *p)/* 求中序后繼 */ if( ) p=p-rchild;/* 若結(jié)點 *p 無右孩子 */else/* 若結(jié)點 *p 有右孩子 */while(p-ltag=0)return ;*rchildp-rtag=1p=p-rchildp=p-lchildp11第6章選擇題：6.1 n 個頂點的有向圖中有向邊的數(shù)目最多為：C n(n-1)/26.2 下面哪一方法可以判斷出一個有向圖是否有環(huán)(回路) C. 拓撲排序A n-1B nD n(n-1)A 深度優(yōu)先遍歷B. 求最短路徑填空題：某無向圖的鄰接矩陣如下所示，則該圖中

31、有6.3A=0101011010110100011000110101001111006.46.5D. 廣度優(yōu)先遍歷9 條邊，有6 個頂點。在無向圖的鄰接矩陣存儲結(jié)構(gòu)中，第 i 列上非零元素的個數(shù)是頂點 vi 的 矩陣中，第 i 列上非零元素的個數(shù)是頂點 vi的 入度 。度 ，而在有向圖的鄰接頂點 的個數(shù)有關(guān)。6.6簡答題：若無向圖采用鄰接矩陣存儲，則存儲空間的大小只與圖中對于一個具有 n 個頂點和 e 條邊的連通圖，其生成樹中的頂點數(shù)和邊數(shù)分別為n 和 n-1 。6.7 設(shè)一個有向圖為 G=(V,E)，其中 V= v 1,v2,v3,v4 ， 答下列各問： 畫出該有向圖，求出每個頂點的入度和出

32、度。 畫出該圖的鄰接矩陣存儲結(jié)構(gòu)圖示。 對( 2)中的鄰接矩陣，給出從頂點 對( 2)中的鄰接矩陣，給出從頂點 1)有向圖：E=, ，請回1)2)3)4)v2 出發(fā)的v2 出發(fā)的DFS 序列和BFS 序列和DFS 生成樹。BFS 生成樹。頂點 頂點 頂點 頂點v1 的入度是v2 的入度是v3 的入度是v4 的入度是2，1出度是 出度是 出度是 出度是1；2；0；2。2)鄰接矩陣存儲結(jié)構(gòu)圖示：數(shù)組r10v1v2v3v43) DFS 序列：生成樹：A 1=v2, v1,v4,v34)BFS 序列： v2, v1,v3,v4 生成樹：v112v46.8 對圖 6.44 所示的無向圖，依次輸入各邊：

33、(v1,v2)、(v1,v4)、(v 2,v 3)、 (v 3,v 4) 、 (v 3,v5)，請回答下列各問：(1) 寫出該無向圖的二元組表示。(2) 畫出該圖的鄰接表(頭插法建表)存儲結(jié)構(gòu)圖示。(3) 對(2)中的鄰接表，給出從頂點 v1出發(fā)的 DFS 序列和 DFS生成樹。(4) 對(2)中的鄰接表，給出從頂點 v1出發(fā)的 BFS序列和 BFS 生成樹。(1)無向圖的二元組表示： 設(shè) G=(V,E) ，V 為頂點集， E 為邊集，則 V=v1,v2,v3,v4, v5E=(v1,v2)、 (v1,v4)、 (v2,v3)、(v3,v4)、(v3,v5) (2)圖的鄰接表(頭插法建表)存儲

34、結(jié)構(gòu)圖示：vertex link012345頂點表邊表3) 從頂點 v1 出發(fā)：DFS 序列： v1,v4,v3,v5,v24) 從頂點 v1 出發(fā)：BFS 序列： v1,v4,v2,v3,v5圖 6.45畫出圖 6.45 中所有可能的最小生成樹。圖 6.446.1 圖 6.45 的所有可能的最小生成樹：v52132第7章選擇題：7.1 在對 n 個元素進行起泡排序的過程中，最好情況下的時間復雜度為： 32A O(n3)B O(n2)C O(n)D O(1)7.2 堆排序?qū)儆谙铝心念惻判?？A. 插入B. 交換C. 歸并D. 選擇7.3 下列哪組序列是堆：A (79,40,46,56,38,84

35、)B. (84,56,79,46,38,40)C (40,38,46,56,79,84)D. (84,38,46,40,56,79)7.4 下列排序算法中，哪種排序方法在一趟結(jié)束后不一定能選出一個元素放在其最終位置上。A. 簡單選擇排序 B. 冒泡排序 C. 歸并排序 D. 堆排序7.5 就平均性能而言，目前最好的內(nèi)排序方法是：C. 交換D. 快速O(n2)且是不穩(wěn)定的排序方法為：C. 直接選擇排序D. 起泡排序A. 冒泡 B. 希爾插入7.6 在下面的排序方法中，平均時間復雜度為A. 快速排序 B. 直接插入排序填空題：7.7 每次從無序子表中取出一個元素， 把它插入到有序子表中的適當位置，

36、 此種排序方法叫做 插入 排序。7.8 快速排序的平均時間復雜度是O( nlog2n) ，平均空間復雜度是 O(log 2n) 。7.9 設(shè)記錄的排序碼序列為： ( 49，38，65，97，76，13，27)，若采用快速排序，則第一趟劃分的結(jié)果為 27,38,134976,97,65 。7.10 快速排序、堆排序和歸并排序的平均時間復雜度都是O( nlog2n)，但其中穩(wěn)定的排序方法只有歸并7.11 在直接插入排序、希爾排序、起泡排序、快速排序中穩(wěn)定的排序方法有直接插入 和 起泡 。7.12 在堆排序、快速排序和歸并排序中，若只從存儲空間考慮，則首先應選取 堆排序 方法，其次選取快 速排序方法

37、。7.13 直接插入排序和簡單選擇排序兩種排序算法中，關(guān)鍵字的比較次數(shù)與初始序列無關(guān)的是 簡單選擇 。簡答題：7.14 常用的實現(xiàn)排序的方法有幾大類？它們的實現(xiàn)思想是什么？ 插入排序的基本思想是： 將一個待排序記錄按照排序碼的大小插入到一個有序序列的適當位置， 使得插入后的序列仍然有序，直到所有記錄全部插入到有序序列中。交換排序的基本思想是：兩兩比較待排序記錄的排序碼， 不符合排列順序則交換記錄， 直到所有記錄的排序 碼都符合排序要求。選擇排序的基本思想是： 每一次從待排序記錄序列中選取一個排序碼最小 (或最大) 的記錄， 放在待排序記 錄序列的最前面(或最后面) ，重復此過程，直到所有的記錄

38、按排序碼排好序。歸并排序的基本思想是： 利用“歸并”技術(shù)實現(xiàn)的排序方法。所謂歸并就是將兩個或多個有序表合并成一 個有序表的過程。 如果是將兩個有序表合并成一個有序表稱為二路歸并， 二路歸并是最 簡單和最常用的。基數(shù)排序的基本思想是： 基數(shù)排序是基于排序碼的結(jié)構(gòu)分解， 然后通過“分配” 和“收集”方法實現(xiàn)的排序。7.15 給定排序碼的序列 39 、33、13、15、58、41、27、46、23 。請回答：141）采用希爾（ Shell ）排序（步長分別為 5,3,1），寫出各趟排序結(jié)果。2）采用快速排序的方法進行排序，寫出各趟排序結(jié)果。1）希爾排序：39331315 58 41274623（初始

39、）392713155841334623（ 1 趟希爾排序結(jié)果）152713334623395841（ 2 趟希爾排序結(jié)果）131523273339414658（ 3 趟希爾排序結(jié)果）2）快速排序：393313155841274623（初始）2333131527394146 58（1 層劃分結(jié)果）151323332739 414658（2 層劃分結(jié)果）13152327 3339414658（3 層劃分結(jié)果）7.16 判斷下列序列是否為堆？如果不是，則把它們調(diào)整成堆。（ 1） （503，87，512， 61， 908， 170，896，275， 653， 462）（ 2） （12，70，33，65

40、，24，48，92，86，33，55）（3） （100，55，97，30，23， 86，60，8，12）（4） （5，56，18，40，38，27，58，30，78， 28， 98）（ 1）不是堆，調(diào)整為大根堆： （908，653，896，503，462，170，512，275， 61，87）（ 2）不是堆，調(diào)整為小根堆： （12，24，33， 33，55，48，92，86，65，70）（ 3）是大根堆（ 4）不是堆，調(diào)整為小根堆： （5，28，18， 30，38，27， 58，40， 78，56，98）7.17 設(shè)待排序文件各個記錄的排序碼序列為： 19、23、2、67、 39、 91、43

41、、25，進行堆排序，請回答： （ 1）畫出初始建成的大根堆對應的完全二叉樹。（2）寫出初始大根堆序列。（ 3）畫出第一趟堆排序后對應的完全二叉樹。 （1）初始建成的大根堆（ 3）第一趟堆排序后對應的完全二叉樹2）初始大根堆序列： 91 67 43 25 39 2 19 23 完善程序題：7.18 設(shè)計一個算法， 其功能為： 利用直接插入排序的方法，將一組存儲在帶頭結(jié)點的單鏈表中的記錄遞增 排序。請將算法補充完整。typedef struct node int key;DataType other;15/* 定義單鏈表的指針域 next */ LinkList;void insertSort(L

42、inkList *L)LinkList *p,*q,*s;p=L-next; L-next=NULL; while(p) q=L;while(q-next & ) /* 指針 q 從頭開始查找，尋找合適的插入位置 */s=p-next;/* 將指針 p 所指的結(jié)點插入到 q 之后 */p=s;struct node *next;q-next-datadata q=q-next; p-next=q-next; q-next=p;第8章選擇題：8.1 對線性表進行二分查找時，要求線性表必須：A 以順序方式存儲B 以順序方式存儲，且按關(guān)鍵字有序C以鏈接方式存儲D以鏈接方式存儲，且按關(guān)鍵字有序8.2 順序查找法適合于存儲結(jié)構(gòu)為（ ）的線性表。A 散列存儲B順序存儲或鏈接存儲C壓縮存儲D索引存儲8.3 若結(jié)點的存儲地址與其關(guān)鍵字之間存在某種函數(shù)關(guān)系，則稱這種存儲結(jié)構(gòu)為： A.順序存儲結(jié)構(gòu)B.鏈式存儲結(jié)構(gòu)C.索引存儲結(jié)構(gòu)D. 散列存儲結(jié)構(gòu)8.4 下面關(guān)于散列查找的說法正確的是： A在采用線性探測法處理沖突的散列表中，同義詞在表中一定相鄰； B除留余數(shù)法是所有散列函數(shù)中最好的；C在散列表中進行查找， “比較”次數(shù)的多少與沖突有關(guān)； D散列函數(shù)構(gòu)造的