數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，也稱節(jié)點(node)或記錄(record)。數(shù)據(jù)對象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)項：有獨立含義的數(shù)據(jù)最小單位，也稱域(field)。數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。根據(jù)數(shù)據(jù)元素間關(guān)系的基本特性，有四種基本數(shù)據(jù)結(jié)構(gòu)集合：結(jié)構(gòu)中的數(shù)據(jù)元素之間除了“同屬于一個集合”的關(guān)系外，別無其他關(guān)系。線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個對一個的關(guān)系。樹形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個對多個的關(guān)系。圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多個對多個的關(guān)系。邏輯結(jié)構(gòu)：抽象反映數(shù)據(jù)元素之間的邏輯關(guān)系。(算法設(shè)計)物理結(jié)構(gòu)(存儲結(jié)構(gòu)):數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的表示。(算法實現(xiàn))順序存儲結(jié)構(gòu)：借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素間的邏輯關(guān)系。鏈?zhǔn)酱鎯Y(jié)構(gòu)：借助指示元素存儲地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系。算法：對特定問題求解步驟的一種描述。算法的五個重要特性：有窮性，確定性，可行性，輸入和輸出。算法設(shè)計的原則或要求：正確性，可讀性，健壯性，效率與低存儲量需求。衡量算法效率的方法：事后統(tǒng)計法和事前分析估算法。算法運行時間的衡量準(zhǔn)則：以基本操作在算法中重復(fù)執(zhí)行的次數(shù)。隊列：只能在隊首進(jìn)行刪除、隊尾進(jìn)行插入的線性表。允許插入的一端叫隊尾，刪除的一端叫隊頭。串：由零個或多個字符組成的有限序列；空串：零個字符的串；長度：串中字符的數(shù)目；空串：零個字符的串；子串：;串中任意個連續(xù)的字符組成的子序列；位置：字符在序列中的序號；相等：串的值相等；空格串：由一個或多個空格組成的串，空格串的長度為串中空格字符的個數(shù)。性質(zhì)1:在二叉樹的第i層上至多有2-1個結(jié)點。(i≥1)性質(zhì)2:深度為k的二叉樹上至多含2*-1個結(jié)點。(k≥1)性質(zhì)3:對任何一棵二叉樹，若它含有n?個葉子結(jié)點、n?個度為2的結(jié)點，性質(zhì)4:具有n個結(jié)點的完全二叉樹的深度為[log?n」+1。滿二叉樹：指的是深度為k且含有2*-1個結(jié)點的二叉樹。完全二叉樹：樹中所含的n個結(jié)點和滿二叉樹中編號為1至n的結(jié)點一一對應(yīng)。路徑長度：路徑上分支的數(shù)目。樹的路徑長度：樹根到每個結(jié)點的路徑長度之和。帶權(quán)路徑長度最小的二叉樹，稱為最優(yōu)樹二叉樹或赫夫曼樹。邊、?。篜(vi,vi)表示頂點vi和頂點vj之間的直接連線，在無向圖中稱為邊，在有向圖中稱為弧。任意兩個頂點構(gòu)成的偶對(vi,vj)∈E是無序的，該連線稱為邊。是有序的，該連線稱為弧?；☆^、弧尾：帶箭頭的一端稱為弧頭，不帶箭頭的一端稱為弧尾。圖的遍歷算法是求解圖的連通性問題、拓?fù)渑判蚝颓箨P(guān)鍵路徑等算法的基礎(chǔ)。通常有兩條遍歷圖的路徑：深度優(yōu)先搜索和廣度優(yōu)先搜索。外部排序：排序過程中需對外存進(jìn)行訪問的排序插入排序：直接插入排序、折半插入排序、希爾排序選擇排序：簡單選擇排序、堆排序ADT:抽象數(shù)據(jù)型是一個數(shù)學(xué)模型和在該模型上定義的操作的集合線性表：線性表是由n(n≥0)個相同類型的元素組成的有序集合。棧：線性表的一種特殊形式，是一種限定性數(shù)據(jù)結(jié)構(gòu)，也就是在對線性表的操作加以限制后，形成的一種新的數(shù)據(jù)結(jié)構(gòu)。是限定只在表尾進(jìn)行插入和刪除操作的線性表。棧又稱為后進(jìn)先出的線性表。隊列：將線性表的插入和刪除操作分別限制在表的兩端進(jìn)行，和棧相反，隊列是串：線性表的一種特殊形式，表中每個元素的類型為字符型，是一個有限的廣義表：由零個原子，或若干個原子或若干個廣義表組成的有窮序列。樹：1、一個結(jié)點x組成的集{x}是一株樹(Tree),這個結(jié)點x也是這株樹的根。一株新樹：令x為根，并有k條邊由x指向樹T1,T2,…,Tk。這些邊也叫做滿二叉樹：深度為k且有2k-1個結(jié)點的二叉樹稱為滿二叉樹。完全二叉樹：深度為k的，有n個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對線索二叉樹：若結(jié)點p有左孩子，則p->lchild指向其左孩子結(jié)點，否則令其指向其(中序)前驅(qū)。若結(jié)點p有右孩子，則p->rchild指向其右孩子結(jié)點，否則令其指向其(中序)后繼。和右兒子結(jié)點(如果有的話)的元素，則稱此完全二叉樹為最大堆。結(jié)點和右兒子結(jié)點(如果有的話)的元素，則稱此完全二叉樹為最小堆。仍表示成(v,w)。開放樹。將生成樹中所有邊長之總和稱為生成樹的價(cost成樹稱為圖G的最小生成樹。無向圖雙連通分量：設(shè)Vi是Ei中各邊所連接的點集(1≤i≤k),每雙連通圖：若對V中每個不同的三元組v,w,a;在v和w之間都存在一條不包含a的路，就說G是雙連通的強連通性：設(shè)G=(V,E)是一個有向圖，稱頂點v,w∈V是等價的，要么v=w;要么從頂點v到w有一條有向路，并且從頂點w到v也有一條有向路。拓?fù)渑判颍航o定一個無環(huán)路有向圖G=(V,E),各結(jié)點的編號為v=(1,2,…,n)。要求對每一個結(jié)點i重新進(jìn)行編號，使得若i是j的前導(dǎo)，則有Label[i]<label[j]。即拓?fù)浞诸愂菍o環(huán)路有向圖排當(dāng)從結(jié)點i到結(jié)點j存在一條邊，則在線性序列中，將i排在j的前面。AOE網(wǎng)：在帶權(quán)的有向圖中，用結(jié)點表示事件，用動的開銷(如持續(xù)時間),則稱此有向圖為邊表示活動的網(wǎng)絡(luò)，簡稱AOE網(wǎng)。關(guān)鍵路徑：在AOE網(wǎng)中，由于有些活動可以并行，所以完成工程的最短時間是從源點到匯點的最大路徑長度。因此，把從源點到匯點具有最大長度的路徑稱為查找表：由同一類型的數(shù)據(jù)元素(或紀(jì)錄)構(gòu)成的集合。關(guān)鍵字：數(shù)據(jù)元素中某一數(shù)據(jù)項的值，用以表示一個數(shù)據(jù)元素。其左子樹和右子樹都是高度平衡的二叉樹，且左子樹和右子樹高度之差的絕對值不超過1。B-樹：B-樹是一種非二叉的查找樹除了要滿足查找樹的特性，還要滿足以下結(jié)(1)樹的根或者是一片葉子(一個節(jié)點的樹),或者其兒子數(shù)在2和m之間。(2)除根外，所有的非葉子結(jié)點的孩子數(shù)在m/2和m之間。(3)所有的葉子結(jié)點都在相同的深度。1、有k個子結(jié)點的結(jié)點必然有k個關(guān)鍵碼；地址散列法：被查找元素的存儲地址=Hash(Key)。(1)若2*i≤n,則(2)若2*i+1≤n,則A[i].key≤A[2*i+1].key;小頂堆(1)若2*i≤n,則A[i].key≥A[2*i].keyA[2*i+1].key;大頂堆詞典排序：設(shè)集合S中的元素為整數(shù)元組，關(guān)系≤為S的線性序，對兩個元在(sl,s2,…,sp))≤(t1,t2,…,tq),當(dāng)存在一個整數(shù)j≤max[p,q],使得sj≤tj,且所有1≤i<j,si=ti;或者p≤q,并且si=ti,1≤i≤p,則關(guān)系≤稱為詞典序。并段),然后將有序段寫回外存；對多歸并段進(jìn)行多遍歸并，最后形成一個有序二、重要算法總結(jié)第三章：1、二叉樹的先、中、后序遍歷(遞歸算法)2、二叉樹的中序非遞歸遍歷(輔助棧、非輔助棧)5、Dijkstra算法單源最短路徑第五章：1、二叉排序樹第六章：簡單排序算法及快排1.數(shù)據(jù)結(jié)構(gòu)是一門研究什么內(nèi)容的學(xué)科?數(shù)據(jù)結(jié)構(gòu)是一門研究在非數(shù)值計算的程序設(shè)計問題中，計算機(jī)的操作對象及對象間的關(guān)系和施加于對象的操作等的學(xué)科。2.數(shù)據(jù)元素之間的關(guān)系在計算機(jī)中有幾種表示方法?各有什么特點?四種表示方法(1)順序存儲方式。數(shù)據(jù)元素順序存放，每個存儲結(jié)點只含一個元素。存儲位置反映數(shù)據(jù)元素間的邏輯關(guān)系。存儲密度大，但有些操作(如插入、刪除)效率較差。(2)鏈?zhǔn)酱鎯Ψ绞?。每個存儲結(jié)點除包含數(shù)據(jù)元素信息外還包含一組(至少一個)指針。指針反映數(shù)據(jù)元素間的邏輯關(guān)系。這種方式不要求存儲空間連續(xù)，便于動態(tài)操作(如插入、刪除等),但存儲空間開銷大(用于指針),另外不能折半查找等。(3)索引存儲方式。除數(shù)據(jù)元素存儲在一地址連續(xù)的內(nèi)存空間外，尚需建立一個索引表，索引表中索引指示存儲結(jié)點的存儲位置(下標(biāo))或存儲區(qū)間端點(下標(biāo)),兼有靜態(tài)和動態(tài)特性。(4)散列存儲方式。通過散列函數(shù)和解決沖突的方法，將關(guān)鍵字散列在連續(xù)的有限的地址空間內(nèi)，并將散列函數(shù)的值解釋成關(guān)鍵字所在元素的存儲地址，這種存儲方式稱為散列存儲。其特點是存取速度快，只能按關(guān)鍵字隨機(jī)存取，不能順序存取，也不能折半存取。3.數(shù)據(jù)類型和抽象數(shù)據(jù)類型是如何定義的。二者有何相同和不同之處，抽象數(shù)據(jù)類型的主要特點是什么?使用抽象數(shù)據(jù)類型的主要好處是什么?數(shù)據(jù)類型是程序設(shè)計語言中的一個概念，它是一個值的集合和操作的集合。如C語言中的整型、實型、字符型等。整型值的范圍(對具體機(jī)器都應(yīng)有整數(shù)范圍),其操作有加、減、乘、除、求余等。實際上數(shù)據(jù)類型是廠家提供給用戶的已實現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)?！俺橄髷?shù)據(jù)類型(ADT)”指一個數(shù)學(xué)模型及定義在該模型上的一組操作。“抽象”的意義在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性。抽象數(shù)據(jù)類型的定義僅取決于它的邏輯特性，而與其在計算機(jī)內(nèi)部如何表示和實現(xiàn)無關(guān)。無論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變就不影響它的外部使用。抽象數(shù)據(jù)類型和數(shù)據(jù)類型實質(zhì)上是一個概念。此外，抽象數(shù)據(jù)類型的范圍更廣，它已不再局限于機(jī)器已定義和實現(xiàn)的數(shù)據(jù)類型，還包括用戶在設(shè)計軟件系統(tǒng)時自行定義的數(shù)據(jù)類對用戶透明(提供接口),而不必了解實現(xiàn)細(xì)節(jié)。抽象數(shù)據(jù)類型的出現(xiàn)使程序設(shè)計不再是“藝術(shù)”,而是向“科學(xué)”邁進(jìn)了一步。4.對于一個數(shù)據(jù)結(jié)構(gòu)，一般包括哪三個方面：邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、操作(運算)。5.根據(jù)數(shù)據(jù)元素之間的邏輯關(guān)系，一般有哪幾類基本的數(shù)據(jù)結(jié)構(gòu)?集合、線性如果有n個線性表同時并存，并且在處理過程中各表的長度會動態(tài)變化，線性表的總數(shù)也會自動地改變。在此情況下，應(yīng)選用哪種存儲結(jié)構(gòu)?為什么?選鏈?zhǔn)酱鎯Y(jié)構(gòu)。它可動態(tài)申請內(nèi)存空間，不受表長度(即表中元素個數(shù))的影響，插入、刪除時間復(fù)雜度為0(1)。(2)若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取線性表中的元素，那么應(yīng)采用哪種存儲結(jié)構(gòu)?為什么?選順序存儲結(jié)構(gòu)。順序表可以隨機(jī)存取，時間復(fù)雜度為0(1)。7.線性表的順序存儲結(jié)構(gòu)具有三個弱點：其一，在作插入或刪除操作時，需移動大量元素；其二，由于難以估計，必須預(yù)先分配較大的空間，往往使存儲空間不能得到充分利用；其三，表的容量難以擴(kuò)充。線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是否一定都能夠克服上述三個弱點，試討論之。鏈?zhǔn)酱鎯Y(jié)構(gòu)一般說克服了順序存儲結(jié)構(gòu)的三個弱點。首先，插入、刪除不需移動元素，只修改指針，時間復(fù)雜度為O(1);其次，不需要預(yù)先分配空間，可根據(jù)需要動態(tài)申請空間；其三，表容量只受可用內(nèi)存空間的限制。其缺點是因為指針增加了空間開銷，當(dāng)空間不允許時，就不能克服順序存儲的缺點。8.棧是只準(zhǔn)在一端進(jìn)行插入和刪除操作的線性表，允許插入和刪除的一端叫棧頂，另一端叫棧底。最后插入的元素最先刪除，故棧也稱后進(jìn)先出(LIFO)表。9.隊列是允許在一端插入而在另一端刪除的線性表，允許插入的一端叫隊尾，允許刪除的一端叫隊頭。最先插入隊的元素最先離開(刪除),故隊列也常稱先進(jìn)先出(FIFO)表。10.什么是循環(huán)隊列?用常規(guī)意義下順序存儲結(jié)構(gòu)的一維數(shù)組表示隊列，由于隊列的性質(zhì)(隊尾插入和隊頭刪除),容易造成“假溢出”現(xiàn)象，即隊尾已到達(dá)一維數(shù)組的高下標(biāo)，不能再插入，然而隊中元素個數(shù)小于隊列的長度(容量)。循環(huán)隊列是解決“假溢出”的一種方法。通常把一維數(shù)組看成首尾相接。在循環(huán)隊列下，通常采用“犧牲一個存B、C、D、E,運用棧操作，能否得到出棧序列B、C、A、E、D和D、B、A、C、E?為什么?能得到說明在D之前的入棧元素是A、B和C,三個元素中C是棧頂元素，B和A不可能早于C出棧，故不可能得到D、B、A、C、E出棧序列。12.串?串是零個至多個字符組成的有限序列。從數(shù)據(jù)結(jié)構(gòu)角度講，串屬于線性結(jié)構(gòu)。與線性表的特殊性在于串的元素是字符。13.描述以下概念的區(qū)別：空格串與空串?？崭袷且粋€字符，其ASCII碼值是32。空格串是由空格組成的串，其長度等于空格的儲，設(shè)第一個元素的首地址是78,每個元素的長度為4,試求元素A[4,2,3]的存儲首地址。958三維的存儲單元數(shù)。15.數(shù)組A中，每個元素A[ij]的長度均為32個二進(jìn)位，行下標(biāo)從-1到9,列下標(biāo)從1到11,從首地址S開始連續(xù)存放主存儲器中，主存儲器字長為16位。求：(1)存放該數(shù)組所需多少單元?(2)存放數(shù)組第4列所有元素至少需多少單元?(3)數(shù)組按行存放時，元素A[7,4]的起始地址是多少?(4)數(shù)組按列存放時，元素A[4,7]的起始地址是多少?答：每個元素32個二進(jìn)制位，主存字長16位，故每個元素占2個字長，行下標(biāo)可平移至1到11。(1)242(2)22(3)16.從概念上講，樹，森林和二叉樹是三種不同的數(shù)據(jù)結(jié)構(gòu)，將樹，森林轉(zhuǎn)化為二叉樹的基本目的是什么,并指出樹和二叉樹的主要區(qū)別。樹的孩子兄弟鏈表表示法和二叉樹二叉鏈表表示法，本質(zhì)是一樣的，只是解釋不同，也就是說樹(樹是森林的特例，即森林中只有一棵樹的特殊情況)可用二叉樹唯一表示，并可使用二叉樹的一些算法去解決樹和森林中的問題。樹和二叉樹一是二叉樹的度至多為2,樹無此限制；二是二叉樹有左右子樹之分，即使在只有一個分枝的情況下，也必須指出是左子樹還是右子樹，樹無此限制；三是二叉樹允許為空，樹一般不允許為空(個別書上允許為空)。17.請分析線性表、樹、廣義表的主除第一個元素外，每個元素有唯一前驅(qū)；除最后一個元素外，每個元素有唯一后繼。樹是一種層次結(jié)構(gòu)，有且只有一個根結(jié)點，每個結(jié)點可以有多個子女，但只有一個雙親(根無雙親),從這個意義上說存在一(雙親)對多(子女)的關(guān)系。廣義表中的元素既可以是原子，也可以是子表，子表可以為它表共享。從表中套表意義上說，廣義表也是層次結(jié)構(gòu)。從邏輯上講，樹和廣義表均屬非線性結(jié)構(gòu)。但在以下意義上，又蛻變?yōu)榫€性結(jié)構(gòu)。如度為1的樹，以及廣義表中的元素都是原子時。另外，廣義表從元素之間的關(guān)系可看成前驅(qū)和后繼，也符合線性表，但這時元素有原子，也有子表，即元素并不屬于同一數(shù)據(jù)對象。18.一棵二叉樹中的結(jié)點的度或為0或為2,則二叉樹的枝數(shù)為2(n0-1),其中nO是度為0的結(jié)點的個數(shù)。證明：設(shè)二叉樹度為0和2的結(jié)點數(shù)及總的結(jié)點數(shù)分別為n0,n2和n,則n=nO+n2…(1)再設(shè)二叉樹的分支數(shù)為B,除根結(jié)點外，每個結(jié)點都有一個分支所指，則n=B+1………(2)度為零的結(jié)點是葉子，沒有分支，而度為2的結(jié)點有兩個分支，因此(2)式可寫為n=2*n2+1…………(3)由(1)、(3)得n2=n0-1,代入(1),并由(1)和(2)得B=2*(nO-1)。證畢。19.(1).如果G1是一個具有n個頂點的連通無向圖，那么G1最多有多少條邊?G1最少有多少條邊?(2).如果G2是一個具有n個頂點的強連通有向圖，那么G2最多有多少條邊?G2最少有多少條邊?(3).如果G3是一個具有n個頂點的弱連通有向圖，那么G3最多有多少條邊?G3最少有多少條邊?答：(1)G1最多n(n-1)2條邊，最少n-1條邊(2)G2最多n(n-1)條邊，最少n條邊(3)G3最多n(n-1)條邊，最少n-1條邊(注：弱連通有向圖指把有向圖看作無向圖時，仍是連通的)20.n個頂點的無向連通圖最少有多少條邊?n個頂點的有向連通圖最少有多少條邊?n-1,n21.內(nèi)部排序(名詞解釋)假設(shè)含n個記錄的序列為{R1,R2……Rn},其相應(yīng)的關(guān)鍵字序列為{K1,K2……Kn},這些關(guān)鍵字相互之間可以進(jìn)行比較，即在它們之間存在著這樣一個關(guān)系Ks1≤Ks2≤…≤Ksn,按此固有關(guān)系將n個記錄序列重新排列為{Rs1,Rs2……Rsn}。若整個排序過程都在內(nèi)存中22.在各種排序方法中，哪些是穩(wěn)定的?哪些是不穩(wěn)定的?并為每一種不穩(wěn)定的排序方法舉出一0(n2)0(n2)O(1)穩(wěn)定折半插入排序0(n2)0(n2)O(1)穩(wěn)定二路插入排序O (n2)O(n2)0(n)穩(wěn)定表插入排序0(n2)0(n2)O(1)穩(wěn)定起泡排