數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)提綱

復(fù)習(xí)提綱第一章數(shù)據(jù)結(jié)構(gòu)概述基本概念與術(shù)語(yǔ)數(shù)據(jù)：數(shù)據(jù)是用來(lái)描述現(xiàn)實(shí)世界的文字，字符，圖像，聲音，以及能夠輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)處理的符號(hào)。數(shù)據(jù)元素：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，是數(shù)據(jù)這個(gè)集合中的個(gè)體，也稱之為元素，結(jié)點(diǎn)，頂點(diǎn)記錄。（補(bǔ)充：一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。）數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象是具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。（有時(shí)候也叫做屬性。）數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。（1） 數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間存在的固有邏輯關(guān)系，常稱為數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)是從數(shù)據(jù)元素之間存在的邏輯關(guān)系上描述數(shù)據(jù)與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問(wèn)題抽象出來(lái)的數(shù)學(xué)模型。依據(jù)數(shù)據(jù)元素之間的關(guān)系，可以把數(shù)據(jù)的邏輯結(jié)構(gòu)分成以下幾種：集合：數(shù)據(jù)中的數(shù)據(jù)元素之間除了“同屬于一個(gè)集合“的關(guān)系以夕卜，沒(méi)有其他關(guān)系。線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在“一對(duì)一“的關(guān)系。若結(jié)構(gòu)為非空集合，則除了第一個(gè)元素之外，和最后一個(gè)元素之外，其他每個(gè)元素都只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。樹(shù)形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在“一對(duì)多“的關(guān)系。若數(shù)據(jù)為非空集，則除了第一個(gè)元素（根）之外，其它每個(gè)數(shù)據(jù)元素都只有一個(gè)直接前驅(qū)，以及多個(gè)或零個(gè)直接后繼。圖狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素存在“多對(duì)多”的關(guān)系。若結(jié)構(gòu)為非空集，折每個(gè)數(shù)據(jù)可有多個(gè)（或零個(gè)）直接后繼。（2） 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)內(nèi)的表示稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。想要計(jì)算機(jī)處理數(shù)據(jù)，就必須把數(shù)據(jù)的邏輯結(jié)構(gòu)映射為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。邏輯結(jié)構(gòu)可以映射為以下兩種存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)：把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理位置也相鄰的存儲(chǔ)單元中，借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)之間的邏輯關(guān)系。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：借助指針表達(dá)數(shù)據(jù)元素之間的邏輯關(guān)系。不要求邏輯上相鄰的數(shù)據(jù)元素物理位置上也相鄰。5.時(shí)間復(fù)雜度分析：1.常量階：算法的時(shí)間復(fù)雜度與問(wèn)題規(guī)模n無(wú)關(guān)系T(n)=O(1)線性階：算法的時(shí)間復(fù)雜度與問(wèn)題規(guī)模n成線性關(guān)系T(n)=O(n)平方階和立方階：一般為循環(huán)的嵌套，循環(huán)體最后條件為i++時(shí)間復(fù)雜度的大小比較：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)算法與程序：1、 輸入：有零個(gè)或多個(gè)輸入2、 輸出：有一個(gè)或多個(gè)輸出3、 有窮性：要求序列中的指令是有限的；每條指令的執(zhí)行包含有限的工作量；整個(gè)指令序列的執(zhí)行在有限的時(shí)間內(nèi)結(jié)束。(程序與算法的區(qū)別在于，程序不需要有有窮性)4、 確定性：算法中的每一個(gè)步驟都必須是確定的，而不應(yīng)當(dāng)含糊、模棱兩可。沒(méi)有歧義。5、 可行性：算法中的每一個(gè)步驟都應(yīng)當(dāng)能被有效的執(zhí)行，并得到確定的結(jié)果。算法設(shè)計(jì)的準(zhǔn)則：1、 正確性(達(dá)到預(yù)期效果，滿足問(wèn)題需求)2、 健壯性(能處理合法數(shù)據(jù)，也能對(duì)不合法的數(shù)據(jù)作出反應(yīng)，不會(huì)產(chǎn)生不可預(yù)期的后果)3、 可讀性(要求算法易于理解，便于分析)4、 可修改可擴(kuò)展性5、 高效率(較好的時(shí)空性能)1、 名詞解釋?zhuān)簲?shù)據(jù)結(jié)構(gòu)、二元組數(shù)據(jù)結(jié)構(gòu)就是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。二元組就是一種用來(lái)表示某個(gè)數(shù)據(jù)對(duì)象以及各個(gè)元素之間關(guān)系的有限集合。2、 根據(jù)數(shù)據(jù)元素之間關(guān)系的不同，數(shù)據(jù)的邏輯結(jié)構(gòu)可以分為集合、線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和圖狀結(jié)構(gòu)四種類(lèi)型。3、 常見(jiàn)的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)一般有兩種類(lèi)型，它們分別是順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)4、 以下說(shuō)法中，正確的是(D)數(shù)據(jù)元素是數(shù)據(jù)這個(gè)集合中的個(gè)體數(shù)據(jù)元素均由數(shù)據(jù)項(xiàng)組成數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位數(shù)據(jù)元素是數(shù)據(jù)的最小單位以下有關(guān)抽象數(shù)據(jù)類(lèi)型的描述中，正確的是(B抽象數(shù)據(jù)類(lèi)型是一個(gè)值的集合抽象數(shù)據(jù)類(lèi)型是數(shù)據(jù)的邏輯結(jié)構(gòu)及操作的組合抽象數(shù)據(jù)類(lèi)型的操作可以沒(méi)有操作結(jié)果抽象數(shù)據(jù)類(lèi)型只能夠用C語(yǔ)言來(lái)描述在一般情況下，一個(gè)算法的時(shí)間復(fù)雜度是問(wèn)題規(guī)模的函數(shù)7.常見(jiàn)時(shí)間復(fù)雜度有：常數(shù)階O(1)、線性階O(n)、對(duì)數(shù)階O(log2n)、平方階。(”2)、指數(shù)階0(25)。通常認(rèn)為，具有常數(shù)階量級(jí)的算法是好算法，而具有指數(shù)階量級(jí)的算法是差算法。第二章線性表順序表結(jié)構(gòu)線性表的順序存儲(chǔ)是指在內(nèi)存中用地址連續(xù)的一塊存儲(chǔ)空間順序存放線性表的各元素，用這種存儲(chǔ)形式存儲(chǔ)的線性表稱為順序表。2.單鏈表鏈表結(jié)點(diǎn)結(jié)構(gòu)線性表中的數(shù)據(jù)元素可以用任意的一組存儲(chǔ)單元來(lái)存儲(chǔ)，用指針表示邏輯關(guān)系邏輯相鄰的兩元素的存儲(chǔ)空間可以是不連續(xù)的。結(jié)點(diǎn)遍歷鏈表操作算法：初始化、插入、輸出、刪除1、 線性表中，第一個(gè)元素沒(méi)有直接前驅(qū)，最后一個(gè)元素沒(méi)有直接后驅(qū)。2、 在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)是q所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，則刪除結(jié)點(diǎn)q的操作語(yǔ)句為P->next=q->next;free(q);3、 在長(zhǎng)度為N的順序表仲，插入一個(gè)新元素平均需要移動(dòng)表中N/2個(gè)元素，刪除一個(gè)元素平均需要移動(dòng)(N-1)/2個(gè)元素。4、 若線性表的主要操作是在最后一個(gè)元素之后插入一個(gè)元素或刪除最后一個(gè)元素，則采用數(shù)序表存儲(chǔ)結(jié)構(gòu)最節(jié)省運(yùn)算時(shí)間。5、 已知順序表中每個(gè)元素占用3個(gè)存儲(chǔ)單元，第13個(gè)元素的存儲(chǔ)地址為336,則順序表的首地址為300

6、設(shè)有一帶頭結(jié)點(diǎn)單鏈表L,請(qǐng)編寫(xiě)該單鏈表的初始化，插入、輸出和刪除函數(shù)。(函數(shù)名自定義)結(jié)點(diǎn)定義：typedefintdatatype; 〃結(jié)點(diǎn)數(shù)據(jù)類(lèi)型，假設(shè)為inttypedefstructnode{ 〃結(jié)點(diǎn)結(jié)構(gòu)datatypedata;structnode*next;}Lnode,*pointer;〃結(jié)點(diǎn)類(lèi)型，結(jié)點(diǎn)指針類(lèi)型typedefpointerlklist;〃單鏈表類(lèi)型，即頭指針類(lèi)型初始化函數(shù)：lklistinitlist(){pointerhead;head=newnode;head->next=NULL;returnhead;}插入函數(shù)：intinsert(lklisthead,datatypex,inti){pointerq,s;q=get(head,i-1);//找第i-1個(gè)點(diǎn)if(q==NULL) 〃無(wú)第/T點(diǎn)，即/<1或i>n+1時(shí){cout<<”非法插入位置!\n”;return0;}s=newnode; 〃生成新結(jié)點(diǎn)s->data=x;s->next=q->next;〃新點(diǎn)的后繼是原第i個(gè)點(diǎn)q->next=s; 〃原第i-1個(gè)點(diǎn)的后繼是新點(diǎn)return1; 〃插入成功}刪除函數(shù)：intdelete(lklisthead,inti){pointerp,q;q=get(head,i-1); 〃找待刪點(diǎn)的直接前趨if(q==NULL||q->next==NULL)//即i<1或i>n時(shí){cout<<”非法刪除位置!\n”;return0;}〃保存待刪點(diǎn)地址〃修改前趨的后繼指針〃釋放結(jié)點(diǎn)〃刪除成〃保存待刪點(diǎn)地址〃修改前趨的后繼指針〃釋放結(jié)點(diǎn)〃刪除成q->next=p->next;deletep;return1;不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是(A)head=NULLB.head->next=NULLC.head->next=headD.head!=NULL帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是(B)A.head=NULLB.head->next=NULLC.head->next=headD.head!=NULL在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行(B)A.s->next=p;p->next=s; B.s->next=p->next;p->next=s;C.s->next=p->next;p=s; D.p->next=s;s->next=p;在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行(A)p->next=p->next->next;p=p->next;p->next=p->next->next;p->next=p->nextp=p->next->next從一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較(B)個(gè)結(jié)點(diǎn)。A.nB.n/2C.(n-1)/2 D.O(nlog2n)給定有n個(gè)元素的向量，建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度(BA.O(1)B.O(n) C.O(n2) D.O(ng2n)在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜度是(B)A.O(1)B.O(n) C.O(n2) D.O(ng2n)在一個(gè)單鏈表中刪除q所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行如下操作：q=p->next;p->next=(p->next->next);free(q);//這種題目靠一根指針是沒(méi)有辦法完成的，必須要借助第二根指針。在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行：s->next=(p->next)p->next=(s)操作。對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的單鏈表，在已知所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是(O)；在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是(O(n))。問(wèn)答題線性表可用順序表或鏈表存儲(chǔ)。試問(wèn)：⑴兩種存儲(chǔ)表示各有哪些主要優(yōu)缺點(diǎn)?順序表的存儲(chǔ)效率高，存取速度快。但它的空間大小一經(jīng)定義，在程序整個(gè)運(yùn)行期間不會(huì)發(fā)生改變，因此，不易擴(kuò)充。同時(shí)，由于在插入或刪除時(shí)，為保持原有次序，平均需要移動(dòng)一半（或近一半）元素，修改效率不高。鏈接存儲(chǔ)表示的存儲(chǔ)空間一般在程序的運(yùn)行過(guò)程中動(dòng)態(tài)分配和釋放，且只要存儲(chǔ)器中還有空間，就不會(huì)產(chǎn)生存儲(chǔ)溢出的問(wèn)題。同時(shí)在插入和刪除時(shí)不需要保持?jǐn)?shù)據(jù)元素原來(lái)的物理順序，只需要保持原來(lái)的邏輯順序，因此不必移動(dòng)數(shù)據(jù)，只需修改它們的鏈接指針，修改效率較高。但存取表中的數(shù)據(jù)元素時(shí)，只能循鏈順序訪問(wèn)，因此存取效率不高。（2）若表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取表中的元素，這時(shí)，應(yīng)采用哪種存儲(chǔ)表示？為什么？應(yīng)采用順序存儲(chǔ)表示。因?yàn)轫樞虼鎯?chǔ)表示的存取速度快，但修改效率低。若表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取表中的元素，這時(shí)采用順序存儲(chǔ)表示較好。第三章棧和隊(duì)列棧（1） 棧的結(jié)構(gòu)與定義（2） 順序棧操作算法：入棧、出棧、判斷?？盏龋?） 鏈棧的結(jié)構(gòu)與定義隊(duì)列（1） 隊(duì)列的定義1、 一個(gè)棧的入棧序列為“ABCDE”，則以下不可能的出棧序列是（BA.BCDAE B.EDACB C.BCADE D.AEDCB2、 棧的順序表示中，用TOP表示棧頂元素，那么?？盏臈l件是（DA.TOP==STACKSIZEB.TOP==1C.TOP==0D.TOP==-13、 允許在一端插入，在另一端刪除的線性表稱為隊(duì)列。插入的一端為表頭，刪除的一端為表尾。4、 棧的特點(diǎn)是先進(jìn)后出，隊(duì)列的特點(diǎn)是先進(jìn)先出。5、 對(duì)于棧和隊(duì)列，無(wú)論他們采用順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，進(jìn)行插入和刪除操作的時(shí)間復(fù)雜度都是O（1）。6、 已知鏈棧Q，編寫(xiě)函數(shù)判斷棧空，如果?？談t進(jìn)行入棧操作，否則出棧并輸出。（要求判斷棧空、出棧、入棧用函數(shù)實(shí)現(xiàn)）考點(diǎn)1：隊(duì)列的編程：考點(diǎn)2：棧的編程：出隊(duì)與取隊(duì)頭元素的區(qū)別：出隊(duì)就是刪除對(duì)頭的數(shù)據(jù)元素，取隊(duì)頭元素是獲取對(duì)頭的數(shù)據(jù)元素值，不需要?jiǎng)h除。鏈棧與順序棧相比，比較明顯的優(yōu)點(diǎn)是：(D1插入操作比較容易 B.刪除操作比較容易C.不會(huì)出現(xiàn)棧空的情況 D.不會(huì)出現(xiàn)棧滿的情況第六章樹(shù)和二叉樹(shù)樹(shù)樹(shù)的概念及術(shù)語(yǔ)樹(shù)：n(〃30)個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n=0時(shí)，稱為空樹(shù)；任意一棵非空樹(shù)滿足以下條件：⑴有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)；⑵當(dāng)n>1時(shí)，除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)被分成m(m>0)個(gè)互不相交的有限集合T1,T2,...,Tm，其中每個(gè)集合又是一棵樹(shù)，并稱為這個(gè)根結(jié)點(diǎn)的壬樹(shù)。結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹(shù)的個(gè)數(shù)。樹(shù)的度：樹(shù)中所有結(jié)點(diǎn)的度的最大值。葉子結(jié)點(diǎn)：度為0的結(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)。分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)，也稱為非終端結(jié)點(diǎn)。孩子、雙親樹(shù)中某結(jié)點(diǎn)的子樹(shù)的根結(jié)點(diǎn)稱為這個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)稱為它孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)；兄弟： 具有同一個(gè)雙親的孩子結(jié)點(diǎn)互稱為兄弟。路徑：如果樹(shù)的結(jié)點(diǎn)序列n1,n2,…,nk有如下關(guān)系:結(jié)點(diǎn)ni是ni+1的雙親(1<=i<k)，則把n1,n2,...,nk稱為一條由n1至nk的路徑；路徑上經(jīng)過(guò)的邊的個(gè)數(shù)稱為路徑長(zhǎng)度。祖先、子孫：在樹(shù)中，如果有一條路徑從結(jié)點(diǎn)x到結(jié)點(diǎn)y，那么x就稱為y的祖先，而y稱為x的子孫。結(jié)點(diǎn)所在層數(shù)：根結(jié)點(diǎn)的層數(shù)為1；對(duì)其余任何結(jié)點(diǎn)，若某結(jié)點(diǎn)在第k層，則其孩子結(jié)點(diǎn)在第k+1層。樹(shù)的深度： 樹(shù)中所有結(jié)點(diǎn)的最大層數(shù)，也稱高度。層序編號(hào)：將樹(shù)中結(jié)點(diǎn)按照從上層到下層、同層從左到右的次序依次給他們編以從1開(kāi)始的連續(xù)自然數(shù)。有序樹(shù)、無(wú)序樹(shù)：如果一棵樹(shù)中結(jié)點(diǎn)的各子樹(shù)從左到右是有次序的，稱這棵樹(shù)為有序樹(shù)；反之，稱為無(wú)序樹(shù)。數(shù)據(jù)結(jié)構(gòu)中討論的一般都是有序樹(shù)樹(shù)通常有前序(根)遍歷、后序(根)遍歷和層序(次)遍歷三種方式(樹(shù)，不是二叉樹(shù)，沒(méi)中序遍歷。二叉樹(shù)二叉樹(shù)的定義：二叉樹(shù)是n(n30)個(gè)結(jié)點(diǎn)的有限集合，該集合或者為空集(稱為空二叉樹(shù))，或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的、分別稱為根結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。滿二叉樹(shù)：在一棵二叉樹(shù)中，如果所有分支結(jié)點(diǎn)都存在左子樹(shù)和右子樹(shù)，并且所有葉子都在同一層上。(滿二叉樹(shù)的特點(diǎn):葉子只能出現(xiàn)在最下一層;只有度為0和度為2的結(jié)點(diǎn)。)完全二叉樹(shù)：對(duì)一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)按層序編號(hào)，如果編號(hào)為i(1</<n)的結(jié)點(diǎn)與同樣深度的滿二叉樹(shù)中編號(hào)為i的結(jié)點(diǎn)在二叉樹(shù)中的位置完全相同。(完全二叉樹(shù)的特點(diǎn)：1.在滿二叉樹(shù)中，從最后一個(gè)結(jié)點(diǎn)開(kāi)始，連續(xù)去掉任意個(gè)結(jié)點(diǎn)，即是一棵完全二叉樹(shù)。葉子結(jié)點(diǎn)只能出現(xiàn)在最下兩層，且最下層的葉子結(jié)點(diǎn)都集中在二叉樹(shù)的左部；完全二叉樹(shù)中如果有度為1的結(jié)點(diǎn)，只可能有一個(gè)，且該結(jié)點(diǎn)只有左孩子。深度為k的完全二叉樹(shù)在k-1層上一定是滿二叉樹(shù)。)二叉樹(shù)的性質(zhì)：性質(zhì)1：二叉樹(shù)的第i層上最多有2/-1個(gè)結(jié)點(diǎn)(i31)。，性質(zhì)2：一棵深度為k的二叉樹(shù)中，最多有2k-1個(gè)結(jié)點(diǎn)，最少有k個(gè)結(jié)點(diǎn)。深度為k且具有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)一定是滿二叉樹(shù)性質(zhì)3：在一棵二叉樹(shù)中，如果葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則有:n0=n2+1。(一個(gè)結(jié)點(diǎn)的度就是指它放出的射線)，性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log2n+1。性質(zhì)5：對(duì)一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中從1開(kāi)始按層序編號(hào)，則對(duì)于任意的序號(hào)為/(1WiWn)的結(jié)點(diǎn)(簡(jiǎn)稱為結(jié)點(diǎn)i)，有：如果/?>1，則結(jié)點(diǎn)/?的雙親結(jié)點(diǎn)的序號(hào)為i/2；如果i=1，則結(jié)點(diǎn)/?是根結(jié)點(diǎn)，無(wú)雙親結(jié)點(diǎn)。如果2iWn，則結(jié)點(diǎn)/?的左孩子的序號(hào)為2i；如果2i>n，則結(jié)點(diǎn)/?無(wú)左孩子。如果2/+1Wn，則結(jié)點(diǎn)/?的右孩子的序號(hào)為2/+1；如果2/+1>n，則結(jié)點(diǎn)i無(wú)右孩子。二叉樹(shù)的遍歷前序遍歷中序遍歷后序遍歷森林(1)森林的遍歷：先序遍歷森林和中序森林先序遍歷：若森林不空，則訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)；

先序遍歷森林中第一棵樹(shù)的子樹(shù)森林；先序遍歷森林中（除第一棵樹(shù)之外）其余樹(shù)構(gòu)成的森林。（約定：依次從左至右對(duì)森林中的每一棵樹(shù)進(jìn)行先根遍歷。）后序遍歷：若森林不空，則后序遍歷森林中第一棵樹(shù)的子樹(shù)森林；訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)；后序遍歷森林中（除第一棵樹(shù)之外）其余樹(shù)構(gòu)成的森林。（約定：依次從左至右對(duì)森林中的每一棵樹(shù)進(jìn)行后根遍歷。）（2）森林：m（m30）棵互不相交的樹(shù)的集合。二叉搜索樹(shù)（1）二叉搜索樹(shù)的定義及構(gòu)建：哈夫曼樹(shù)（1） 哈夫曼樹(shù)的基本概念：哈夫曼樹(shù)：給定一組具有確定權(quán)值的葉子結(jié)點(diǎn)，帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)。（2） 哈夫曼樹(shù)的特點(diǎn)：權(quán)值越大的葉子結(jié)點(diǎn)越靠近根結(jié)點(diǎn)，而權(quán)值越小的葉子結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn)。只有度為0（葉子結(jié)點(diǎn)）和度為2（分支結(jié)點(diǎn)）的結(jié)點(diǎn)，不存在度為1的結(jié)點(diǎn).（3） 哈夫曼樹(shù)的構(gòu)造算法思想及構(gòu)造過(guò)程（7森林與哈夫曼編碼1、 已知一棵完全二叉樹(shù)有47個(gè)結(jié)點(diǎn)，則該二叉樹(shù)有（）個(gè)葉子結(jié)點(diǎn)。A.6B.12C.24 D.482、 已知遍歷一棵二叉樹(shù)的前序序列ABCDEFG和中序序列CBEDAFG，那么是下面哪棵AB樹(shù)（C）

AB3、如下圖所示的一棵二叉樹(shù)進(jìn)行遍歷，得到的遍歷序列是CADREFB，則該遍歷序列是哪種遍歷（3、如下圖所示的一棵二叉樹(shù)進(jìn)行遍歷，得到的遍歷序列是CADREFB，則該遍歷序列是哪種遍歷（B）的結(jié)果。A.前序遍歷B.中序遍歷 C.后序遍歷D.層次遍歷4、 完全二叉樹(shù)必須滿足的條件為：:一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，它的結(jié)構(gòu)與滿二叉樹(shù)的前n個(gè)結(jié)點(diǎn)的的結(jié)構(gòu)相同。5、 哈夫曼樹(shù)不存在度為1的結(jié)點(diǎn)。6、有5個(gè)帶權(quán)結(jié)點(diǎn)，其權(quán)值分別為2,5,3,7,11，根據(jù)哈夫曼算法構(gòu)建該樹(shù)，并計(jì)算該樹(shù)的帶權(quán)路徑長(zhǎng)度。（構(gòu)建哈夫曼樹(shù)，很簡(jiǎn)單，從小開(kāi)始，計(jì)算相加，然后把所有葉子結(jié)點(diǎn)乘以等級(jí)數(shù)字然后相加。也即是：帶權(quán)路徑長(zhǎng)度=葉結(jié)點(diǎn)的權(quán)值*路徑長(zhǎng)度）8、寫(xiě)出前序和后序遍歷下面森林得到的序列，并將森林轉(zhuǎn)化成二叉樹(shù)前序：abdjcefhi后序：djbaechif前序遍歷和中序遍歷結(jié)果相同的二叉樹(shù)是（D）。A根結(jié)點(diǎn)無(wú)左孩子的二叉樹(shù) B根結(jié)點(diǎn)無(wú)右孩子的二叉樹(shù)C所有結(jié)點(diǎn)只有左子樹(shù)的二叉樹(shù)D所有結(jié)點(diǎn)只有右子樹(shù)的二叉樹(shù)用順序存儲(chǔ)的方法將完全二叉樹(shù)中的所有結(jié)點(diǎn)逐層存放在數(shù)組A[1]~A[n]中，結(jié)點(diǎn)A[i]若有左子樹(shù)，則左子樹(shù)的根結(jié)點(diǎn)是(D)。AA[2i-1]BA[2i+1]CA[i/2]DA[2i]對(duì)任何一棵二叉樹(shù)T,如果其終端結(jié)點(diǎn)的個(gè)數(shù)為n0,度為2的結(jié)點(diǎn)個(gè)數(shù)為門(mén)2,則(C)。A.n0=n2-1B.n0=n2C.n0=n2+1D.沒(méi)有規(guī)律對(duì)于完全二叉樹(shù)中的任一結(jié)點(diǎn)，若其右分支下的子孫的最大層次為h,則其左分支下的子孫的最大層次為(C)。A.h B.h+1C.h或h+1D任意假定一棵度為3的樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為50,則它的最小深度為—如最大深度為_(kāi)5d。A3 B4 C5 D6試找出分別滿足下列條件的所有二叉樹(shù)：⑴前序序列和中序序列相同：只有右子樹(shù)⑵中序序列和后序序列相同：只有左子樹(shù)⑶前序序列和后序序列相同：只有根，空二叉樹(shù)8二叉樹(shù)的前序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面，這種說(shuō)法(A)(A)正確(B)錯(cuò)誤由于二叉樹(shù)中每個(gè)結(jié)點(diǎn)的度最大為2,所以二叉樹(shù)是一種特殊的樹(shù)，這種說(shuō)法(B)(A)正確(B)錯(cuò)誤已知某二叉樹(shù)的后序遍歷序列是dabec。中序遍歷序列是debac，它的前序遍歷序列是(D)。(A)acbed(B)decab(C)deabc(D)cedba某二叉樹(shù)的前序遍歷結(jié)點(diǎn)訪問(wèn)順序是abdgcefh,中序遍歷的結(jié)點(diǎn)訪問(wèn)順序是dgbaechf,則其后序遍歷的結(jié)點(diǎn)訪問(wèn)順序是(D)。(A)bdgcefha(B)gdbecfha(C)bdgaechf(D)gdbehfca在一非空二叉樹(shù)的中序遍歷序列中，根結(jié)點(diǎn)的右邊(C)(A)只有右子樹(shù)上的所有結(jié)點(diǎn) (B)只有右子樹(shù)上的部分結(jié)點(diǎn)(C)只有左子樹(shù)上的部分結(jié)點(diǎn) (D)只有左子樹(shù)上的所有結(jié)點(diǎn)15.任何一棵二叉樹(shù)的葉子結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序(B)(A)不發(fā)生改變 (B)發(fā)生改變(C)不能確定(D)以上都不對(duì)第七章圖圖的基本概念：圖的基本術(shù)語(yǔ)及推論鄰接矩陣：鄰接矩陣的定義圖的遍歷深度優(yōu)先遍歷廣度優(yōu)先遍歷1、 對(duì)于上圖所示的有向圖，其深度優(yōu)先搜索遍歷序列為ADFCEB，廣度優(yōu)先搜索遍歷序列為ABCDEF，其拓?fù)渑判蛐蛄袨锳(去掉A發(fā)出的射線)B(去掉B發(fā)出的射線)EDFC。2、 一個(gè)具有N個(gè)頂點(diǎn)的完全無(wú)向圖的邊數(shù)為1/2N(N-1)；一個(gè)具有N個(gè)頂點(diǎn)的完全有向圖的弧數(shù)為N(N-1)。3、 在有向圖中，總?cè)攵?、總出度和總邊?shù)相等。在無(wú)向圖中，總度數(shù)是總邊數(shù)的兩倍。4、 一個(gè)有16個(gè)頂點(diǎn)的無(wú)向圖，至少應(yīng)該有15(n-1)條邊才能確保它是連通圖。5、 給出下面所示有向圖的鄰接矩陣。第九章排序1.直接排序：直接插入、直接選擇算法思想直接插入排序法：依次將待排序數(shù)據(jù)元素按其關(guān)鍵字的大小插入到有序區(qū)的適當(dāng)位置上，這就是直接插入排序法。Eg:(25，6，23，11，67，45)25，6，23，11，67，456,25，23，11，67，4523,25,11，67，45(在有序區(qū)內(nèi)進(jìn)行比較排序)直接選擇排序法：每趟排序在當(dāng)前待排序序列中選出關(guān)鍵碼最小的記錄，添加到有序序列中。Eg:(70,89,3,8,25,18)先固定第一個(gè)元素，然后從剩下的元素中選出最小的，與固定元素比較，交換(3,89,70,8,25,18)(3,8,70,89,25,18)冒泡排序:算法思想：兩兩比較相鄰記錄的關(guān)鍵碼，如果反序則交換，直到?jīng)]有反序的記錄為止。Eg（98,25,70,36,13,85）首先，我們假設(shè)是升序排序，98先出來(lái)與25比，若大于25,交換繼續(xù)比較，直到遇見(jiàn)比它大的數(shù)字或者到了最后，停下。詳細(xì)參考書(shū)本P295筆記3.快速排序：算法思想首先選一個(gè)軸值（即比較的基準(zhǔn)），通過(guò)一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩部分，前一部分記錄的關(guān)鍵碼均小于或等于軸值，后一部分記錄的關(guān)鍵碼均大于或等于軸值，然后分別對(duì)這兩部分重復(fù)上述方法，直到整個(gè)序列有序。快速排序比較難以理解，（31， 68，45， 90， 23， 39， 54， 12， 87， 7631<76,指向31的左指針不用移動(dòng)；指向76的右指針移動(dòng)87，12。當(dāng)?shù)搅?2之后，因?yàn)?1>12，交換，（12，68，45， 90， 23， 39， 54， 31， 87， 76）68與31按照前面的，交換！堆排序：堆的定義首先將待排序的記錄序列構(gòu)造成一個(gè)堆，此時(shí)，選出了堆中所有記錄的最大者，然后將它從堆中移走，并將剩余的記錄再調(diào)整成堆，然后又將它從堆中移走，這樣又找出了次小的記錄，以此類(lèi)推，直到堆中只有一個(gè)記錄。（大根堆：越往上越大；小根堆：越往下越大）按照給出的數(shù)據(jù)的順序由上往下建一個(gè)堆；根據(jù)題目要求，看是要大根堆還是小根堆；從最下面的支點(diǎn)開(kāi)始調(diào)整；1、 排序方法的穩(wěn)定性是指（BA.排序算法能在規(guī)定的時(shí)間內(nèi)完成排序 B.排序算法能得到確定的結(jié)果C.排序算法不允許有相同關(guān)鍵字的數(shù)據(jù)元素D.以上都不對(duì)2、 在對(duì)一組關(guān)鍵字序列｛70，55，100，15，33，65，50，40，95｝進(jìn)行直接插入排序時(shí)，把65插入到有序序列需要比較（B）次。A.2B.4C.6D.83、 若有關(guān)鍵字序列｛42,70,50,33,40,80｝，則利用快速排序的方法，以第一個(gè)關(guān)鍵字為基準(zhǔn)元素得到的一次劃分結(jié)果為（A）。（指著第一個(gè)原始元素的那個(gè)指針成為不動(dòng)指針，又叫做伴隨指針，另一個(gè)指針叫做比較指針）A.40,33,42,50,70,80 B.40,33,80,42,50,70C.40,33,42,80,50,70 D.33,40,42,50,70,804、 以下排序方法中，排序過(guò)程中的比較次數(shù)與排序方法無(wú)關(guān)的是（A）A.直接選擇排序B.快速排序法 C.堆排序 D.直接插入排序5、 以下（B）排序方法是不穩(wěn)定的排序方法A.冒泡 B.堆 C.直接插入 D.二路歸并以下各種排序方法中，最好情況下時(shí)間復(fù)雜度為O（n）的是（D）。A.歸并排序B.快速排序 C.堆排序D.直接插入排序和冒泡排序在待排序序列局部有序時(shí)，效率最高的排序方法是（C）。A.直接選擇排序B.快速排序C.直接插入排序和冒泡排序 D.歸并排序已知