數據結構清華大學出版社嚴蔚敏吳偉民編著

1、第一章 緒論1、數據結構是計算機中 存儲、組織數據 的方式。精心選擇的數據 結構可以帶來 最優(yōu)效率 的算法。2、程序設計 = 算法 +數據結構3、解決問題方法的效率：跟數據的組織方式有關跟空間的利用效率有關跟算法的巧妙程度有關4、數據 ：所有能輸入到計算機中 ,且被計算機處理的符號的集合， 是計算機操作對象的總稱；是計算機處理的信息的某種特定的符號表示形式。5、數據元素 ：數據中的一個“個體” ,數據結構中討論的基本單 位。 相當于“記錄” ,在計算機程序中通常作為一個整體考 慮和處理。6、數據項 : 相當于記錄的“域”, 是數據的不可分割的最小單位 如學號。數據元素是數據項的集合。7、數據對

2、象 ：性質相同的數據元素的集合 .例如 : 所有運動員的記錄集合8、數據結構 ：是相互間存在某種關系的數據元素集合。9、數據結構是帶結構的數據元素的集合。10、不同的關系構成不同的結構。11、次序關系 ：<ai,ai+1>|i=1,2,3,4,5,612、對每種數據結構，主要討論如下兩方面的問題：1）數據的邏輯結構，數據結構的基本操作；2）數據的存儲結構，數據結構基本操作的實現；13、數據的邏輯結構： 數據之間的結構關系，是具體關系的抽象。 數據結構的基本操作： 指對數據結構的加工處理。14、數據的存儲結構 （物理結構 ）： 數據結構在計算機內存中的表示。 數據結構基本操作的實現：

3、 基本操作在計算機上的實現（方法 ）。15、數據結構的有關概念16、數據元素的 4 類的基本結構 ： 集合； 線性結構：結構中數據元素之間存在一對一的關系； 樹形結構：結構中數據元素之間存在一對多的關系； 4 圖狀結構或網狀結構：結構中數據元素之間存在多對多 的關系。17、C語言的優(yōu)點：C語言可以直接操作內存。18、每個節(jié)點都由兩部分組成： 數據域和指針域 。19、鏈接存儲結構特點：比順序存儲結構的存儲密度小(每個節(jié)點都由數據域和指針域組成 )。 邏輯上相鄰的節(jié)點物理上不必相鄰。插入、刪除靈活 (不必移動節(jié)點，只要改變節(jié)點中的指針 )。20、數據類型 是一個值的集合和定義在此集合上的一組操作的

4、 總稱。21、ADT 有兩個重要特征 :數據抽象 和數據封裝 。22、抽象數據類型(Abstract Data Type簡稱ADT):是指一個數 學模型以及定義在此數學模型上的一組操作。23、抽象數據類型有:數據對象 數據對象的定義 、數據關系數據關系的定義、 基本操作 基本操作的定義 。24、數據類型的定義和含義。 定義:數據類型是一個值的集合和定義在這個值集上的一組 操作的總稱。含義:將數據按一定次序與形式存放的結構。24、算法空間復雜度 S(n) 算法的存儲量包括: 輸入數據所占的空間； 程序本身所占的空間； 輔助變量所占的空間。25、算法具有 有窮性、確定性、可行性、輸入和輸出五大特性

5、。26、抽象數據類型具有 數據抽象、數據封裝 的特點。27、數據的儲存結構分為： 順序存儲結構 和 鏈式存儲結構 。 第二章 線性表1、線性結構的特點：在數據元素中的非空有限集中。(1) 存在唯一的一個被稱作“第一”的數據元素；(2) 存在唯一的一個被稱作“最后一個”的數據元素；(3) 除第一個外，集合中的每一個數據元素均只有一個前驅；(4) 除最后一個外，集合中的每一個數據元素均只有一個后繼。2、線性表 (Linear List) ：一個線性表是 n 個數據元素的有限序列3、線性表的順序存儲實現：typedef struct ElementType DataMAXSIZE;int Last;

6、 List;List L, *PtrL;4、初始化(建立空的順序表)List *MakeEmpty( ) List *PtrL;PtrL = (List *)malloc( sizeof(List) );PtrL->Last = -1;return PtrL;5、查找int Find( ElementType X, List *PtrL ) int i = 0;while( i <= PtrL->Last && PtrL->Datai!= X )i+;if (i > PtrL->Last) return -1; /* 如果沒找到，返回 -1

7、*/else return i; /* 找到后返回的是存儲位置 */6、插入算法void Insert( ElementType X, int i, List *PtrL ) int j;if ( PtrL->Last = MAXSIZE-1 )/* 表空間已滿， 不能插入 */ printf( 表滿 );return;if ( i < 1 | i > PtrL->Last+2) /*檢查插入位置的合法性 */ printf( 位置不合法 );return;for ( j = PtrL->Last; j >= i-1; j- )PtrL->Dataj+

8、1 = PtrL->Dataj; /* 將 ai an 倒序向后移動 */PtrL->Datai-1 = X; /* 新元素插入 */PtrL->Last+; /*Last 仍指向最后元素 */ return;7、刪除算法void Delete( int i, List *PtrL ) int j;if( i < 1 | i > PtrL->Last+1 ) /* 檢查空表及刪除位置的合法性 */printf (不存在第d個元素” ,i ); return ;for ( j = i; j <= PtrL->Last; j+ )PtrL->D

9、ataj-1 = PtrL->Dataj; /* 將 ai+1 an順序向 前移動*/PtrL->Last-; /*Last 仍指向最后元素 */ return;8、求表長int Length ( List *PtrL ) List *p = PtrL;/* p 指向表的第一個結點 */int j = 0;while ( p ) p = p->Next;j+; /* 當前 p 指向的是第 j 個結點 */return j;9、查找( 1)按序號查找 : FindKth;List *FindKth( int K, List *PtrL ) List *p = PtrL;int

10、i = 1;while (p !=NULL && i < K ) p = p->Next;i+;if ( i = K ) return p;/* 找到第 K 個，返回指針 */else return NULL;/* 否則返回空 */( 2)按值查找 : FindList *Find( ElementType X, List *PtrL )List *p = PtrL;while ( p!=NULL && p->Data != X )p = p->Next;return p;10、插入(在鏈表的第i-1(1w iw n+1)個結點后插入一個

11、值為 X的新 結點 )List *Insert( ElementType X, int i, List *PtrL )List *p, *s;if ( i = 1 ) /* 新結點插入在表頭 */s = (List *)malloc(sizeof(List); /*申請、填裝結點 */ s->Data = X;s->Next = PtrL;return s; /* 返回新表頭指針 */p = FindKth( i-1, PtrL );/* 查找第 i-1 個結點 */if ( p = NULL ) /* 第 i-1 個不存在，不能插入 */printf(H 參數 i 錯"

12、)；return NULL;else s = (List *)malloc(sizeof(List); /*申請、填裝結點*/s->Data = X;s->Next = p->Next; /* 新結點插入在第 i-1 個結點的后面 */p->Next = s;return PtrL;11、刪除(刪除鏈表的第i (1<iWn)個位置上的結點)List *Delete( int i, List *PtrL )List *p, *s;/* 若要刪除的是表的/*s 指向第 1 個結點/* 從鏈表中刪除 */* 釋放被刪除結點if ( i = 1 ) 第一個結點 */s =

13、 PtrL;*/PtrL = PtrL->Next; free(s);*/return PtrL;if ( p = NULL ) NULL; elseNULL; elseprintf（第小個結點不存在”卜1）;if ( p->Next = NULL )printf（ 第%d個結點不存在” j）;s = p->Next;returnreturn/*s指向第i個結點*/p->Next = s->Next;/*從鏈表中刪除*/free(s);/*釋放被刪除結點*/retur n PtrL;12、鏈表不具備的特點是可隨機訪問任一節(jié)點插入刪除不須要移動元素 不必事先估計存儲

14、空間所需空間與其長度成正比13、帶頭結點的單鏈表head為空的判定條件是 2 head=NULL head->n ext=head head-> next=NULL head!二NULL14、如果最常用的操作是取第i個結點及其前驅，則采用 存儲方式最節(jié)省時間。單鏈表 雙鏈表 單循環(huán)鏈表 順序表第三章 Chapter 3 棧(stacks)和隊列(queues)1、棧是限定僅能在表尾一端進行 插入、刪除 操作的線性表。2、棧的特點是“后進棧的元素先出棧” (last in, first out),故棧又 稱為后進先出表( LIFO)。3、一個棧是一些元素的線形列表，其中元素的插入和刪

15、除均在表的同一端進行。插入和刪除發(fā)生的一端稱為棧頂(the top of thestack)。4、第一個進棧的元素在棧底，5、最后一個進棧的元素在棧頂， 第一個出棧的元素為棧頂元素， 最后一個出棧的元素為棧底元素。6、連續(xù)棧(Contiguous Stack的類型定義#define MaxStack 50Typedef structdatatype stackMaxStack;int top;Seqstack;Seqstack *s;7、判斷棧是否已滿viod Push(Seqstack *s, datatype x )if (s->top>=MaxStack-1) printf(

16、“ overflow ” ); else s-> top+;s->stacks->top=x;8、判斷棧是否為空datatype pop(Seqstack *s ) if (s->top<0)printf(“underflow”); return(NULL); return(s->stacks->top); s->top-;9、返回棧頂元素的值，棧不發(fā)生變化。datatype top(Seqstack *s ) if (s->top<0)printf(“underflow”); return(NULL); return(s->s

17、tacks->top);10、鏈棧(Linked Stack的類型定義棧的鏈式存儲結構稱為鏈棧， 它是運算受限的單鏈表， 插入和刪除操作僅限制在表頭位置上進行。 由于只能在鏈表頭部進行操作， 故鏈表沒有必要像單鏈表那樣附加頭結點。棧頂指針就是鏈表的頭指針鏈棧的類型說明如下：typedef struct stacknode datatype datastruct stacknode *nextstacknode11、鏈式棧的特點： 鏈式棧無棧滿問題；空間可擴充；插入與刪除僅在棧頂處執(zhí)行； 鏈式棧的棧頂在鏈頭；適合于多棧操作。11、棧是限定僅能在表的一端進行插入、刪除操作的線性表 。12、棧

18、的元素具有后進先出的特點 。13、棧頂元素的位置由棧頂指針的指示 , 進棧、出棧操作要修改棧 頂指針。14、抽象數據類型隊列的定義：隊列(Queue)也是一種運算受限的線性表。它只允許在表的一端進 行插入，而在另一端進行刪除。允許刪除的一端稱為隊頭(front),允許插入的一端稱為隊尾 (rear)。15、 隊列亦稱作先進先出(First In First Out的線性表，簡稱FIFO表。16、雙端隊列：就是限定插入和刪除操作在表的兩端進行的線性表。17、鏈隊列結點定義：typedef struct Qnode QElemType data;struct QNode *n ext; QNode

19、,*QueuPtr;18、隊列的順序存儲結構稱為 順序隊列，在隊列的順序存儲結構中， 除了用一組地址連續(xù)的儲存單元依次存放從隊頭到隊尾的元素 之外，尚需要附設兩個指針front和rear分別指示隊列頭元素 和隊列尾元素的位置。19、在非空隊列中，頭指針始終指向隊頭元素，而尾指針始終指向 隊尾元素的下一位置。20、棧的特點是先講后出，隊列的特點是先講后出 21、棧和隊列的共同特點是只允許在端點處插入和刪除元素 22、一個棧的進棧序列是a, b, c, d, e,則棧的不可能的輸出序列(A) edcba (B) decba(C) dceab(D) abcde 23、若已知一個棧的進棧序列是p1,

20、p2, p3,，pn。其輸出序列為1, 2, 3,，n，若p3=1，則p1為 C 。(A) 可能是2 (B)定是2 (C)不可能是2 (D)不可能是324、設有一個空棧，棧頂指針為 1000H (十六進制，下同)，現有輸入序列為 1、2、3、4、5,經過 PUSH PUSH POP PUSH POP PUSHPUSH 后，輸出 序列是 3, 棧頂指針是8。 5、4、3、2、12、1 2、33、41002H1004H24、一個隊列的入隊序列是若1, 2 , 3, 4,則隊列的輸出序列是B。(A) 4, 3, 2, 1(B) 1, 2, 3, 4(C) 1, 4, 3, 2(D) 3, 2, 4,

21、 125、若用一個大小為6的一維數組來實現循環(huán)隊列，且當前rear和 front的值分別為0和3。當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別是B。(A) 1 禾口 5(B) 2 和 4(C) 4 和 2( D) 5 和 126、有5個元素，其入棧次序為A、B、C D、E,在各種可能的出棧 次序中，以元素C、D最先出棧（即C第一個且D第二個出棧）的次 序有哪幾個C、D、B、A、EC、D、E、B、AC、D、B、E、A第六章樹和二叉樹1、樹型結構是一類重要的非線性結構。2、樹的定義：樹是n（n>=0）個結點的有限集T, T為空時稱為空樹， 否則它滿足如下兩個條件：（

22、1）有且僅有一個特定的稱為根的結點；（2）當n>1時，其余結點可分為 m（m>0）個互不相交的有限集T1, T2, T3Tm,其中每個子集又是一棵樹，并稱其為根的子樹 。3、基本術語結點表示樹中的元素， 包括數據項及若干指向其子樹的分支結點的度(degree)結點擁有的子樹數葉子(leaf)度為0的結點孩子(child)結點子樹的根稱為該結點的孩子雙親(parents)孩子結點的上層結點叫該結點的兄弟(sibling)同一雙親的孩子樹的度 一棵樹中最大的結點度數結點的層次(level)從根結點算起，根為第一層，它的孩子為第二層深度(depth)樹中結點的最大層次數森林(forest

23、)m(m 0)棵互不相交的樹的集合例題:4、二叉樹是由n(n>=0個結點的有限集合構成，此集合或者為空集， 或者由一個根結點及兩棵互不相交的左右子樹組成， 并且左右子樹都 是二叉樹。二叉樹可以是空集合，根可以有空的左子樹或空的右子樹。性質1:在二叉樹的第i層上至多有2i-1個結點(i>=1)。性質2：深度為k的二叉樹至多有2k1個結點(k>=1)。性質3:對任何一棵二叉樹T,如果其終端結點數為n0,度為2的 結點數為n2,則n0= n2 + 1。性質 4：具有 n 個結點的完全二叉樹的深度為 log2n 1。性質 5： 如果對一棵有 n 個結點的完全二叉樹的結點按層序編號 (

24、從 第 1 層到第 log2n +1 層，每層從左到右 ) ，則對任一結點 (i 1<=i<=n)，有：(1) 如果i= 1,則結點i無雙親，是二叉樹的根；如果i>1, 則其雙親是結點 i/2 。(2) 如果2i>n,則結點i為葉子結點，無左孩子；否則，其左 孩子是結點 2i。(3) 如果2i+1>n,貝卩結點i無右孩子；否則，其右孩子是結 點 2i1 。一棵深度為 k 且有 2k-1 個結點的二叉樹稱為滿二叉樹。如：5、二叉樹的存儲結構順序存儲結構define MAX-TREE-SIZE 1 00Typedef TelemType SqBiTree MAX-TR

25、EE-SIZE;SqBitree bt;缺點是有可能對存儲空間造成極大的浪費。鏈式存儲結構 二叉鏈式存儲結構typedef struct BiTNode TElemType data;struct BiTNode *lchild, *rchild;BiTNode,*BiTree;三叉鏈表typedef struct node datatype data;struct node *lchild, *rchild, *parent;JD;6、遍歷二叉樹 二叉樹是由三個基本單元組成：根結點、左子樹和右子樹。 若限定先左后右，則只有前三種情況，分別稱之為 先(根)序遍歷， 中(根)序遍歷和后(根)序遍

26、歷 。( 1)先序遍歷算法 若二叉樹為空樹，則空操作；否則，訪問根結點；先序遍歷左子樹；先序遍歷右子樹。void PreOrder(BiTree bt)/* 先序遍歷二叉樹 bt*/ if (bt=NULL) return; /* 遞歸調用的結束條件 */ Visite(bt->data);/*(1) 訪問結點的數據域 */PreOrder(bt->lchild); /*(2)先序遞歸遍歷 bt 的左子樹*/PreOrder (bt->rchild) ;/*(3)先序遞歸遍歷 bt 的右子樹 */ 例題：先序遍歷序列： A B D Cvoid preorder(JD *bt)

27、 if(bt!=NULL) printf("%dt",bt->data);preorder(bt->lchild);preorder(bt->rchild);(2)中序遍歷算法 若二叉樹為空樹，則空操作；否則，先序遍歷左子樹；訪問根結點；先序遍歷右子樹。void InOrder( BiTree bt)/* 先序遍歷二叉樹 bt*/ if (bt=NULL) return; /* 遞歸調用的結束條件 */ InOrder(bt->lchild); /*(2)先序遞歸遍歷 bt 的左子樹*/ Visite( bt->data);/*(1) 訪問結點

28、的數據域 */In Order (bt->rchild) ;/*(3)先序遞歸遍歷bt的右子樹*/ 例題：中序遍歷序列： B D A C( 3)后序遍歷算法 若二叉樹為空樹，則空操作；否則，先序遍歷左子樹；先序遍歷右子樹；訪問根結點。void PostOrder(BiTree bt)/* 后序遍歷二叉樹 bt*/if (bt=NULL) return; /* 遞歸調用的結束條件 */PostOrder (bt->lchild) ;/*(1)后序遞歸遍歷 bt 的左子樹 */ PostOrder(bt->rchild); /*(2) 后序遞歸遍歷 bt 的右子樹 Visite(

29、 bt->data);/*(3) 訪問結點的數據域 */例題：后序遍歷序列： D B C A( 4)層次遍歷所謂二叉樹的層次遍歷，是指從二叉樹的第一層(根結點)開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序對結點逐個訪問層次遍歷序列 :12 3 4 5 67、例題： 1 、先序序列：A B C D E F G H K中序序列：B D C A E H G K F后序序列：D C B H K G F E K層次序列：A B E C F D G H K2、若先序遍歷此二叉樹， 按訪問結點的先后次序將結點排列起來， 其先 序序列為： -+a*b-cd/ef按中序遍歷，其中序序列為： a+

30、b*c-d-e/f 按后序遍歷，其后序序列為： abcd-*+ef/ -8、( 1 )查詢二叉樹中某個結點Status Preorder (BiTree T, ElemType x, BiTree &p) / 若二叉樹中存在和 x 相同的元素，則 p 指向該結點并/ 返回 OK,/ 否則返回 FALSEif (T) if (T->data= =x) p = T; return OK,else if (Preorder(T->lchild, x, p) return OK;else (Preorder(T->rchild, x, p) return OK;/else/i

31、felse return FALSE;(2)計算二叉樹中葉子結點的個數int CountLeaf (BiTree T)/ 返回指針 T 所指二叉樹中所有葉子結點個數if (!T ) return 0;if (!T->lchild && !T->rchild) return 1;elsem = CountLeaf( T->lchild);n = CountLeaf( T->rchild);return (m+n); /else / CountLeaf3) 求二叉樹的深度 (后序遍歷 )int Depth (BiTree T ) / 返回二叉樹的深度if (

32、 !T ) depthval = 0; else depthLeft = Depth( T->lchild );depthRight= Depth( T->rchild );depthval = 1 + (depthLeft > depthRight ?depthLeft : depthRight);return depthval;4) 按先序遍歷序列建立二叉樹Status CreateBiTree(BiTree &T ) /按先序次序輸入二叉樹中結 點的值 (一個字符)，空格字符表示空樹， 構造二叉鏈表表示的 二叉樹 Tscanf (&ch);if ( ch

33、= ) T=NULL; else if(!T=(BiTNode *)malloc(sizeof(BiTNode) exit (OVERFLOW); T->data=ch; /生成根結點CreateBiTree(T->lchild);/構造左子樹CreateBiTree(T->rchild);/構造右子樹Return OK; /CreateBiTree9、遍歷二叉樹的非遞歸算法1) 先序遍歷二叉樹的非遞歸算法void inorder(JD *r)/ 先序遍歷二叉樹非遞歸算法 / int i=0; JD *p,*sM; p=r;do while(p!=NULL) printf(&

34、quot;%dt",p->data);if (p->rc!=NULL)si+=p->rc;p=p->lc;if ( i > 0) p=s-i;while( i>0 | p!=NULL); 2) 中序遍歷二叉樹的非遞歸算法void inorder(JD *r)/ 先序遍歷二叉樹非遞歸算法 / int i=0; JD *p,*sM; p=r;do while(p!=NULL) si+=p; p=p->lc;if (i>0)p=s-i;printf("%dt",p->data);p=p->lc;if ( i &

35、gt; 0) p=s-i;while( i>0 | p!=NULL); ( 3)后序遍歷二叉樹的非遞歸算法void inorder(JD *r)/ 先序遍歷二叉樹非遞歸算法 / int s2M,b,i=0; JD *p,*s1M; p=r;do while(p!=NULL) s1i-1=p;s2i+=0;p=p->lc;while (i>0 && (s2i-1=1)p=s1-i; printf( “%dt”,p->data ); if (i>0)p=s-i;printf("%dt",p->data);p=p->lc;

36、if ( i > 0) s2i-1=1; p=s1i-1; p=p->rc; while( i>0); 12、線索二叉樹：以二叉鏈表作為存儲結構時，只能找到結點的左右孩子的信息，而不能在結點的任一序列的前驅與后繼信息，這種信息只有在遍歷的動態(tài)過程中才能得到，為了能保存所需的信息，可增加標志域lchildLtagdataRtagrchildLtag=O , Ichild域指示結點的左孩子；Ltag=1, Ichild域指示結 點的前驅。Rtag=O, rchild域指示結點的右孩子；Rtag=1, rchild域指示結點 的后驅。以這種結構構成的二叉鏈表作為二叉樹的存儲結構，

37、叫做線索鏈 表，其中指向結點前驅與后繼的指針叫做線索， 加上線索的二叉樹稱 之為線索二叉樹。（1）先序線索二叉樹（2）中序線索二叉樹（3）后序線索二叉樹13、樹的存儲結構雙親表示法#define MAX_TREE_SIZE100typedef struct PTNode /結點結構ElemType data;int pare nt; /雙親位置域 PTNode;typedef struct / 樹結構PTNode nodesMAX_TREE_SIZE; PTree;孩子表示法（帶雙親的孩子鏈表 孩子兄弟表示法 鏈表中每個結點的兩個指針域分別指向其第一個孩子結點和下一個 兄弟結點。typedef

38、 struct node datatype data;struct node *fch, *nsib;JD;13、樹和森林與二叉樹的轉換 加線：在兄弟之間加一連線 。 抹線：對每個結點，除了其左孩子外， 去除其與其余孩子之間的關系， 旋轉：以樹的根結點為軸心，將整樹順時針轉 45°。14、將二叉樹轉換成樹加線：若p結點是雙親結點的左孩子，則將p的右孩子，右孩 子的右孩子，沿分支找到的所有右孩子，都與 p的雙親用 線連起來 .抹線：抹掉原二叉樹中雙親與右孩子之間的連線 調整：將結點按層次排列，形成樹結構14、森林轉換二叉樹（1）將各棵樹分別轉換成二叉樹(2) 將每棵樹的根結點用線相連.

39、(3) 以第一棵樹根結點為二叉樹的根，再以根結點為軸心，順時針 旋轉，構成二叉樹型結構15、二叉樹轉換成森林抹線：將二叉樹中根結點與其右孩子連線， 及沿右分支搜索到的所有 右孩子間連線全部抹掉，使之變成孤立的二叉樹.還原：將孤立的二叉樹還原成16、樹和森林的遍歷樹的遍歷 兩種次序遍歷樹的方法：一種是先根(次序)遍歷樹，即先訪問樹的根結點，然后依次先根遍歷根的每棵子樹；結點森林的遍歷一種是后根(次序)遍歷，即先依次后根遍歷每棵子樹，然后訪問根先根序列：A B C D E后根序列：B D C E A先序遍歷：A B C D E F G H I J中序遍歷：B C D A F E H J I G17

40、、赫夫曼樹及其應用例題： w=5, 29, 7, 8, 14, 23, 3, 11習題:1、 由于二叉樹中每個結點的度最大為2,所以二叉樹是一種特殊的 樹，這種說法旦。（A）正確（B）錯誤2、某二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹一定是D_。（A）空或只有一個結點（B）完全二叉樹（C）二叉排序樹（D）高度等于其節(jié)點數3、深度為5的二叉樹至多有C個結點。（A）16（ B）32（C）31（D）104、根據使用頻率為5個字符設計的赫夫曼編碼不可能是 C_.（A）111，110，10，01，00（B）000，001，010，011，1（C）100，11，10，1，0（D）001，00

41、0，01，11，105、樹和二叉樹的主要差別是（1）樹的結點個數至少為 1，而二叉 樹的結點個數可以為 0 （2）樹中結點的最大度數沒有限制，而二叉 樹結點的最大度數為 2 （3）樹的結點無左、右之分，而二叉樹的結 點右左、右之分。6、 深度為k的完全二叉樹至少有 個結點，至多有 個結點，若按自上而下，從左到右次序給結點編號（從 1開始），則編 號最小的葉子結點的編號 。7、一棵二叉樹的第i(i 1)層最多有個結點；一棵有n(n>0)個結點的滿二叉樹共有 個葉子結點和_個非葉子結點。8已知二叉樹的先序、中序和后序序列分別如下，其中有一些看不清的字母用*表示，請構造出一棵符合條件的二叉樹并

42、畫出該二叉樹。先序序列是：*BC*FG中序序列是：CB*EAG*后序序列是：*EDB*FA9、將右圖所示的樹轉化為二叉樹，并寫出先序遍歷，中序遍歷和后 序遍歷的結果。解：先序：ABEFGCDHI中序：EFGBCHIDA后序：GFEIHDCBA10、設給定權集w=2, 3，4，7，8，9，試構造關于w的一棵赫夫 曼樹，并求其加權路徑長度WPL。WPL=(9+7+8)*2+4*3+(2+3)*4=80第十章內部排序1、內排序大致可分為五類：插入排序、交換排序、選擇排序、歸并 排序和分配排序。2、直接插入排序直接插入的算法實現void sort(NODE array,i nt n)/待排序元素用一個

43、數組array表示，數組有 n個元素 int i, j;NODE x;/ x為中間結點變量for ( i=1; i<n; i+)/i表示插入次數，共進行n-1次插入 x=arrayi; /把待排序元素賦給xj=i-1;while (j>=0)&& (x.key<arrayj.key)arrayj+1=arrayj; j-; / 順序比較和移動 arrayj+1=x; 例如，n=6,數組R的六個排序碼分別為：17，3, 25,14, 20，9。它的直接插入排序的執(zhí)行過程如圖7-1所示。012345初始直接插入排序的時間復雜度為14 O( n2»)o9第

44、-直接插入算法的元素移動是順序的，該方法是9穩(wěn)定的。Kt3、第希次插排序(31725 )14209希爾排序的時間復雜性在 0 (nlog2n)和0 (n2 )之間，大致為第三次插入 (3141725 )209O(n1.3)。F第四次插入(31417 2025 )9由于希爾排序對每個子序列單獨比較，在比較時進行元素移動，有可1改變相同排序碼元素的原始順序,20因此希爾排序是不穩(wěn)定的。圖10-1直接插入排序示例例如，n=8,數組array的八個元素分別為：91，67，35，62，29,72, 46, 57。下面用圖10-2給出希爾排序算法的執(zhí)行過程4、交換排序1) 冒泡排序 冒泡排序的算法實現vo

45、id Bubblesort( NODE array,int n) int i, j, flag; / 當 flag 為 0 則停止排序NODE temp;for ( i=1; i<n; i+) / i 表示趟數，最多 n-1 趟 flag=0;/ 開始時元素未交換for ( j=n-1; j>=i; j-)if (arrayj.key<arrayj-1.key) / 發(fā)生逆序 temp=arrayj;arrayj=arrayj-1;arrayj-1=temp; flag=1; / 交換，并標記發(fā)生了交換if(flag=0) break; 例如，n=6,數組R的六個排序碼分別為

46、：17, 3, 25,14, 20, 9。下面用圖 10-3 給出冒泡排序算法的執(zhí)行過程。冒泡排序算法的時間復雜度為 O (n2)。由于其中的元素移動較多， 所以屬于內排序中速度較慢的一種。因為冒泡排序算法只進行元素間的順序移動,所以是一個穩(wěn)定的算 法。2) 快速排序 快速排序(Quick Sorting)是迄今為止所有內排序算法中速度最快的一種。快速排序的算法實現void quicksort(NODE array,int start , int end) int i , j; NODE mid;if (start>=end) return;i=start;j=end;mid=array

47、i;while (i<j) while (i<j && arrayj.key>mid.key) j-;if (i<j) arrayi=arrayj; i+;while (i<j && arrayi.key<=mid.key) i+;if (i<j) arrayj=arrayi; j-; / 一次劃分得到基準值的正確位置arrayi=mid;quicksort(array,start,i-1);/ 遞歸調用左子區(qū)間quicksort(array,i+1,end); /遞歸調用右子區(qū)間 例如，給定排序碼為： ( 46，55，

48、13，42，94，05，17，70) ，具 體劃分如圖 10-4 所示?？焖倥判蛩加玫妮o助空間為棧的深度， 故最好的空間復雜度為O(log2n),最壞的空間復雜度為 0(n)?？焖倥判蚴且环N不穩(wěn)定的排序方法。5、選擇排序1) 直接選擇排序例如，給定n=8,數組R中的8個元素的排序碼為：(8, 3, 2, 1,乙 4， 6， 5)，則直接選擇排序過程如圖 7-5 所示。直接選擇排序的時間復雜度為 0( n2)數量級2) 樹形選擇排序例如,給定排序碼頭 50, 37, 66, 98, 75, 12, 26, 49,樹形選擇 排序過程見圖 7-7。3) 堆排序例如,給定排序碼 49, 38, 65

49、, 97, 76, 13, 27, 70,建立初始堆 的過程如圖 7-8所示。按層次遍歷完全二叉樹,得到一個由大到小排列的有序序列：97, 76, 70, 65, 49, 38, 27, 13每次篩選運算的時間復雜度為 O(log2 n),故整個堆排序過程的時間復 雜度為 0(nlog2n)。5、歸并排序例如,給定排序碼 46, 55, 13, 42, 94, 05, 17, 70,二路歸并排 序過程如圖 7-10所示。二路歸并排序的時間復雜度為 0(nlog2n)。6、各種內排序方法的比較和選擇1)從時間復雜度比較 從平均時間復雜度來考慮,直接插入排序、冒泡排序、直接選擇 排序是三種簡單的排

50、序方法，時間復雜度都為0(n2),而快速排序、 堆排序、二路歸并排序的時間復雜度都為 O(nl og2 n),希爾排序的復 雜度介于這兩者之間。 若從最好的時間復雜度考慮， 則直接插入排序 和冒泡排序的時間復雜度最好，為0(n),其它的最好情形同平均情形 相同。若從最壞的時間復雜度考慮，則快速排序的為 0(n2),直接插 入排序、冒泡排序、希爾排序同平均情形相同, 但系數大約增加一倍, 所以運行速度將降低一半, 最壞情形對直接選擇排序、 堆排序和歸并 排序影響不大。2) 從空間復雜度比較歸并排序的空間復雜度最大，為0(n),快速排序的空間復雜度為O(log2 n),其它排序的空間復雜度為 0(

51、 1)。3) 從穩(wěn)定性比較直接插入排序、冒泡排序、 歸并排序是穩(wěn)定的排序方法,而直接選擇 排序、希爾排序、快速排序、堆排序是不穩(wěn)定的排序方法。4) 從算法簡單性比較直接插入排序、冒泡排序、 直接選擇排序都是簡單的排序方法,算法 簡單,易于理解,而希爾排序、快速排序、堆排序、歸并排序都是改 進型的排序方法,算法比簡單排序要復雜得多,也難于理解。8、各種內排序方法的選擇1 )從時間復雜度選擇 對元素個數較多的排序,可以選快速排序、堆排序、歸并排序, 元素個數較少時,可以選簡單的排序方法。2)從空間復雜度選擇盡量選空間復雜度為 0( 1)的排序方法，其次選空間復雜度為O(log2n)的快速排序方法，

52、最后才選空間復雜度為0 (n)二路歸并排 序的排序方法。3) 一般選擇規(guī)則當待排序元素的個數 n 較大，排序碼分布是隨機，而對穩(wěn)定性不 做要求時，則采用快速排序為宜。當待排序元素的個數 n 大，內存空間允許，且要求排序穩(wěn)定時， 則采用二路歸并排序為宜。當待排序元素的個數 n 大，排序碼分布可能會出現正序或逆序的 情形，且對穩(wěn)定性不做要求時，則采用堆排序或二路歸并排序為 宜。當待排序元素的個數 n 小，元素基本有序或分布較隨機，且要求 穩(wěn)定時，則采用直接插入排序為宜。當待排序元素的個數 n 小，對穩(wěn)定性不做要求時，則采用直接選 擇排序為宜，若排序碼不接近逆序，也可以采用直接插入排序。 冒泡排序一

53、般很少采用。第9章查找1、順序表的查找(順序查找)順序查找的缺點是平均查找長度較大， 特別是當n很大時，查找效率 低。然而，它有很大的優(yōu)點是：算法簡單且適應面廣。2、有序表的查找(折半查找)算法實現：假設表長為 n， low、high 和 mid 分別指向待查元素所在 區(qū)間的上界、下界和中點， k 為給定值，初始時，令 low=1， high=n， mid= （low+high）/2讓 k 與 mid 指向的記錄比較若 k=rmid.key ，查找成功若 k<rmid.key ，則 high=mid-1若 k>rmid.key ，則 low=mid+1重復上述操作，直至 low&g

54、t;high 時，查找失敗。例如：已知如下 11 個數據元素的有序表（ 05，13，19，21，37，56， 64，75，80，88，92），現要查找關鍵字為 21和 70 的數據元素。 折半查找的效率比順序查找高， 但折半查找只適用于有序表， 且限于 順序存儲結構。3、查找方法的比較4、二叉排序樹的插入例 45，24， 53， 45，12，24，905、二叉排序樹的刪除5、含有 n 個結點的二叉排序樹的平均查找長度和樹的形態(tài)有關。第 7章 圖1、圖的定義和術語 若圖中的邊是頂點的有序對，則稱此圖為有向圖。 若圖中的邊是頂點的無序對，則稱此圖為無向圖。有向邊又稱為弧，通常用尖括號表示一條有向邊

55、，vv, w>表示從頂點v到w頂點的一條弧，v稱為邊的始點（或弧尾），w稱為邊的終點(或弧頭)。有向完全圖：具有n(n-1)條弧的有向圖稱為有向完全圖。無向完全圖：n個頂點的無向圖最大邊數是 n(n-1)/2,具有n(n-1)/2條邊的無向圖稱為無向完全圖。度的例題：子圖的例題：總的例題：若G中任意兩個頂點都是連通的，則稱 G為連通圖。非連通圖的極大連通子圖叫做連通分量。強連通圖與強連通分量在有向圖中，若對于每一對頂點vi和vj，都存在一條從vi到vj和 從vj到vi的路徑，則稱此圖是強連通圖。非強連通圖的極大強連通2、圖的存儲結構無向圖的鄰接矩陣是對稱的，有向圖的鄰接矩陣可能是不對稱的數組表示法(鄰接矩陣)網的鄰接矩陣可為：3、儲存表示1）有向圖的十字鏈表表示法 2）無向圖的鄰接多重表存儲表示4、圖的遍歷通常有兩條遍歷圖的路徑：深度優(yōu)