數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)要點(diǎn)(整理版)

1.數(shù)據(jù)：數(shù)據(jù)是對(duì)客觀事物的符號(hào)表示，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被3.數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象是具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。(有時(shí)候也4.數(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)系，常稱(chēng)為數(shù)數(shù)據(jù)的邏輯結(jié)構(gòu)是從數(shù)據(jù)元素之間存在的邏輯關(guān)系上描述數(shù)據(jù)與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)，是依據(jù)數(shù)據(jù)元素之間的關(guān)系，可以把數(shù)據(jù)的邏輯結(jié)構(gòu)分成以下幾種：1.集合：數(shù)據(jù)中的數(shù)據(jù)元素之間除了“同屬于一個(gè)集合“的關(guān)系以外，沒(méi)有其他關(guān)系。2.線(xiàn)性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在“一對(duì)一“的關(guān)系。若結(jié)構(gòu)一個(gè)元素之外，和最后一個(gè)元素之外，其他每個(gè)元素都只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。3.樹(shù)形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在“一對(duì)多“的關(guān)系。若數(shù)據(jù)為非空集，則除了第一個(gè)元素(根)之外，其它每個(gè)數(shù)據(jù)元素都只有一個(gè)直接前驅(qū)，以及多個(gè)或零個(gè)直4.圖狀結(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)的表示稱(chēng)為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。想要計(jì)算機(jī)處理數(shù)據(jù)，就必須把數(shù)據(jù)的邏輯結(jié)構(gòu)映射為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。邏輯結(jié)構(gòu)可以映射1.順序存儲(chǔ)結(jié)構(gòu)：把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理位置也相鄰的存儲(chǔ)單元中，借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)之間的邏輯關(guān)系。2.鏈?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)2.線(xiàn)性階：算法的時(shí)間復(fù)雜度與問(wèn)題規(guī)模n成線(xiàn)性關(guān)系T(n)=O(n)O(1)<0(log2n)<0(n)<O(nlog2n)<0(n2)<O(n3)<O(2n)<0(n!)<O(nn)(1)算法的5個(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é)果。(2).算法設(shè)計(jì)的要求：1、正確性(達(dá)到預(yù)期效果，滿(mǎn)足問(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)可以分為集合、線(xiàn)性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和3、常見(jiàn)的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)一般有兩種類(lèi)型，它們分別是順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)指數(shù)階O(2^n)。通常認(rèn)為，具有常數(shù)階量級(jí)的算法是好算法，而具有指數(shù)階量級(jí)的算法是定義：線(xiàn)性表是n個(gè)數(shù)據(jù)元素的有限序列。一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。線(xiàn)性表的順序存儲(chǔ)是指在內(nèi)存中用地址連續(xù)的一塊存儲(chǔ)空間順序存放線(xiàn)性表的各元素，用這2.單鏈表線(xiàn)性表中的數(shù)據(jù)元素可以用任意的一組存儲(chǔ)單元來(lái)存(2)鏈表操作算法：初始化、插入、輸出、刪除、遍歷1、線(xiàn)性表中，第一個(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ǔ)句為3、在長(zhǎng)度為N的順序表中，插入一個(gè)新元素平均需要移動(dòng)表中N/2個(gè)元素，刪除一個(gè)元素平均需要移動(dòng)(N-1)/2個(gè)元素。4、若線(xiàn)性表的主要操作是在最后一個(gè)元素之后插入一個(gè)元素或刪除最后一個(gè)元素，則采用順序表存儲(chǔ)結(jié)構(gòu)最節(jié)省運(yùn)算時(shí)間。5、已知順序表中每個(gè)元素占用3個(gè)存儲(chǔ)單元，第13個(gè)元素的存儲(chǔ)地址為336,則順序表的首地址為300。(第n個(gè)元素的地址即首地址+(n-1)*每個(gè)元素的存儲(chǔ)空間，如a[12](第13個(gè)元素)的地址=a[0]+12*3)6、設(shè)有一帶頭結(jié)點(diǎn)單鏈表L,請(qǐng)編寫(xiě)該單鏈表的初始化，插入、輸出和刪除函數(shù)。(函數(shù)名自定義)//head=(pointer)malloc(sizeof(Lnode));這是C語(yǔ)言做法}intinsert(lklisthead,datatypex,s->next=q->next;//新點(diǎn)的后繼是原第i個(gè)點(diǎn)11.不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是(A)2.帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是(B)3.在一個(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;4.在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行(A)B.p=p->next;p->next=p->5.從一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功的情況下，需6.給定有n個(gè)元素的向量，建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度(B)7.在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜度是(B)8.在一個(gè)單鏈表中刪除q所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行如下操作：9.在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行：10.對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的單鏈表,在已知所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是(O(1));在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是(O(n))。(1)兩種存儲(chǔ)表示各有哪些主要優(yōu)缺點(diǎn)?順序表的存儲(chǔ)效率高，存取速度快。但它的空間大小一經(jīng)定義，在程序整個(gè)運(yùn)行期間不會(huì)發(fā)生改變，因此，不易擴(kuò)充。同時(shí)，由于在插入或刪除時(shí)，為保持原有次序，平均需要移動(dòng)一鏈接存儲(chǔ)表示的存儲(chǔ)空間一般在程序的運(yùn)行但存取表中的數(shù)據(jù)元素時(shí)，只能循鏈順序訪(fǎng)問(wèn)，因此存取效率不高。(2)若表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取表中的元素，這時(shí)，應(yīng)采用哪種存儲(chǔ)表示?為什么?應(yīng)采用順序存儲(chǔ)表示。因?yàn)轫樞虼鎯?chǔ)表示的存取速度快，但定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取表中的元素，這時(shí)采用順序存儲(chǔ)表示第三章棧和隊(duì)列定義：限定僅在表尾進(jìn)行插入或刪除操作的線(xiàn)性表。typedefstructlist{門(mén)(2)順序棧操作算法：入棧、出棧、判斷?？盏?這個(gè)是使用數(shù)組進(jìn)行操作的，具體內(nèi)定義：只允許在表的一端進(jìn)行插入，而在另一端刪除元素。1、一個(gè)棧的入棧序列為“ABCDE”,則以下不可能的出棧序列是(B)2、棧的順序表示中，用TOP表示棧頂元素，那么?？盏臈l件是(D)3、允許在一端插入，在另一端刪除的線(xiàn)性表稱(chēng)為隊(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)(即與已有元素N無(wú)關(guān))。6、已知鏈棧Q,編寫(xiě)函數(shù)判斷棧空，如果?？談t進(jìn)行入棧操作，否則出棧并輸出。(要求判斷?？铡⒊鰲?、入棧用函數(shù)實(shí)現(xiàn))(詳看考點(diǎn)2)7.出隊(duì)與取隊(duì)頭元素的區(qū)別：出隊(duì)就是刪除對(duì)頭的數(shù)據(jù)元素，取隊(duì)頭元素是獲取對(duì)頭的數(shù)據(jù)A.插入操作比較容易B.刪除操作比較容易C.不會(huì)出現(xiàn)?？盏那闆rD.不會(huì)出現(xiàn)棧滿(mǎn)的情況考點(diǎn)1:隊(duì)列的編程：typedefstructQNode{typedefstruct{{Q.front=Q.rear=(QueuePtr)mallo入隊(duì)：p=(QueuePtr)malloc(sizeof(QNoif(Q.rear==p)Q.rear考點(diǎn)2:棧的編程：1第四章串(不是重點(diǎn)內(nèi)容)第五章數(shù)組和廣義表(不是重點(diǎn)內(nèi)容)用的地址空間并組給出多維數(shù)組的維數(shù)，然后要求你求出該數(shù)組中的某個(gè)元素所在的位置。2.明確按行存儲(chǔ)和按列存儲(chǔ)的區(qū)別和聯(lián)系，并能夠按照這兩種不同的存儲(chǔ)方式求解1中類(lèi)3.將特殊矩陣中的元素按相應(yīng)的換算方式存入數(shù)組中。這些矩陣包括：對(duì)稱(chēng)矩陣，三角矩陣，具有某種特點(diǎn)的稀疏矩陣等。熟悉稀疏矩陣的三種不同存儲(chǔ)方式：三元組，帶輔助行向typedefstruct{typedefstructOLNode{typedefstruct/行和列的表頭指針組的首地址}M.rhead=(OLink*)malloc((m+1)*sizeM.chead=(OLink*)malloc((n+1)*size第六章樹(shù)和二叉樹(shù)(1)樹(shù)的概念及術(shù)語(yǔ)(1)有且僅有一個(gè)特定的稱(chēng)為根的結(jié)點(diǎn)；(2)當(dāng)n>1時(shí)，除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)被分成m(m>0)個(gè)互不相交的有限集合(2)結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹(shù)的個(gè)數(shù)。樹(shù)的度：樹(shù)中所有結(jié)點(diǎn)的度的最大值。(3)葉子結(jié)點(diǎn)：度為0的結(jié)點(diǎn)，也稱(chēng)為終端結(jié)點(diǎn)。分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)，也稱(chēng)為非終端結(jié)點(diǎn)。(4)孩子、雙親：樹(shù)中某結(jié)點(diǎn)的子樹(shù)的根結(jié)點(diǎn)稱(chēng)為這個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)稱(chēng)為它孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)；兄弟：具有同一個(gè)雙親的孩子結(jié)點(diǎn)互稱(chēng)為兄弟。則把n1,n2,…,nk稱(chēng)為一條由n1至nk的路徑；路徑上經(jīng)過(guò)的邊的個(gè)數(shù)稱(chēng)為路徑長(zhǎng)度。(6)祖先、子孫：在樹(shù)中，如果有一條路徑從結(jié)點(diǎn)x到結(jié)點(diǎn)y,那么x就稱(chēng)為y的祖先，而y稱(chēng)為x的子孫。(7)結(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ù)，也稱(chēng)高度。(8)層序編號(hào)：將樹(shù)中結(jié)點(diǎn)按照從上層到下層、同層從左到右的次序依次給他們編以從1開(kāi)始的連續(xù)自然數(shù)。(10)樹(shù)通常有前序(根)遍歷、后序(根)遍歷和層序(次)遍歷三種方式(樹(shù)，(1)二叉樹(shù)的定義：二叉樹(shù)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集合，該集合或者為空集(稱(chēng)為空二叉樹(shù)),或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的、分別稱(chēng)為根結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的二叉滿(mǎn)二叉樹(shù)：在一棵二叉樹(shù)中，如果所有分支結(jié)點(diǎn)都存在左子樹(shù)和右子樹(shù)，并且所有葉子都在(滿(mǎn)二叉樹(shù)的特點(diǎn)：葉子只能出現(xiàn)在最下一層；只有度為0和度為2的結(jié)點(diǎn)。)完全二叉樹(shù)：對(duì)一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)按層序編號(hào)，如果編號(hào)為i(1≤i≤n)的結(jié)點(diǎn)與同樣深度的滿(mǎn)二叉樹(shù)中編號(hào)為i的結(jié)點(diǎn)在二叉樹(shù)中的位置完全相同。1.在滿(mǎn)二叉樹(shù)中，從最后一個(gè)結(jié)點(diǎn)開(kāi)始，連續(xù)去掉任意個(gè)結(jié)點(diǎn)，即是一棵完全二叉樹(shù)。2.葉子結(jié)點(diǎn)只能出現(xiàn)在最下兩層，且最下層的葉子結(jié)點(diǎn)都集中在二3.完全二叉樹(shù)中如果有度為1的結(jié)點(diǎn)，只可能有一個(gè)，且該結(jié)點(diǎn)只有左孩子。4.深度為k的完全二叉樹(shù)在k-1層上一定是滿(mǎn)二叉樹(shù)。(3)二叉樹(shù)的性質(zhì)：性質(zhì)1:二叉樹(shù)的第i層上最多有2i-1個(gè)結(jié)點(diǎn)(i≥1)。性質(zhì)2:一棵深度為k的二叉樹(shù)中，最多有2k-1個(gè)結(jié)點(diǎn)，最少有k個(gè)結(jié)點(diǎn)。深度為k且具有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)一定是滿(mǎn)二叉樹(shù)性質(zhì)3:在一棵二叉樹(shù)中，如果葉子結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2,則有：n0=n2+1。(一個(gè)結(jié)點(diǎn)的度就是指它放出的射線(xià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)為i(1≤i≤n)的結(jié)點(diǎn)(簡(jiǎn)稱(chēng)為結(jié)點(diǎn)i),有：(1)如果i>1,則結(jié)點(diǎn)i的雙親結(jié)點(diǎn)的序號(hào)為i/2;如果i=1,則結(jié)點(diǎn)i是根結(jié)點(diǎn)，無(wú)雙(2)如果2i≤n,則結(jié)點(diǎn)i的左孩子的序號(hào)為2i;如果2i>n,則結(jié)點(diǎn)i無(wú)左孩子。(3)如果2i+1≤n,則結(jié)點(diǎn)i的右孩子的序號(hào)為2i+1;如果2i+1>n,則結(jié)點(diǎn)i無(wú)右孩子。3.二叉樹(shù)的遍歷(遞歸調(diào)用與訪(fǎng)問(wèn)的順序不同而產(chǎn)生不同的遍歷方法)voidXianXu(BiTree}4.森林與二叉樹(shù)的轉(zhuǎn)換(1)同級(jí)以左為親，即左一結(jié)點(diǎn)的右孩子是與它同級(jí)的右一結(jié)點(diǎn)(2)只認(rèn)最左路線(xiàn)為親子路線(xiàn)，即結(jié)點(diǎn)的左孩子是它下一級(jí)結(jié)點(diǎn)的最左的元素(1)哈夫曼樹(shù)的基本概念：哈夫曼樹(shù)：給定一組具有確定權(quán)值的葉子結(jié)點(diǎn)，帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)。(2)哈夫曼樹(shù)的特點(diǎn)：1.權(quán)值越大的葉子結(jié)點(diǎn)越靠近根結(jié)點(diǎn)，而權(quán)值越小的葉子結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn)。2.只有度為0(葉子結(jié)點(diǎn))和度為2(分支結(jié)點(diǎn))的結(jié)點(diǎn)，不存在度為1的結(jié)點(diǎn).(3)哈夫曼樹(shù)的構(gòu)造算法思想及構(gòu)造過(guò)程(森林與哈夫曼編碼)就是求各權(quán)值和路徑相乘之后疊加的最小值。1、已知一棵完全二叉樹(shù)有47個(gè)結(jié)點(diǎn)，則該二叉樹(shù)有(C)個(gè)葉子結(jié)點(diǎn)。所以，葉子結(jié)點(diǎn)數(shù)=16+8=24計(jì)算從第一層到n-1層的結(jié)點(diǎn)個(gè)數(shù)計(jì)算第n層的葉子結(jié)點(diǎn)個(gè)數(shù)計(jì)算第n-1層的葉子結(jié)點(diǎn)個(gè)數(shù)計(jì)算第n層和第n-1層的總?cè)~子結(jié)點(diǎn)數(shù)2、已知遍歷一棵二叉樹(shù)的前序序列ABCDEFG和中序序列CBEDAFG,那么是下面哪棵樹(shù)4、完全二叉樹(shù)必須滿(mǎn)足的條件為：:一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，它的結(jié)構(gòu)與滿(mǎn)二叉樹(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)度)7.試找出分別滿(mǎn)足下列條件的所有二叉樹(shù)：(1)前序序列和中序序列相同：只有右子樹(shù)(3)前序序列和后序序列相同