數(shù)據(jù)結(jié)構(gòu)名詞解釋

數(shù)據(jù)結(jié)構(gòu)是一門研究什么內(nèi)容的學(xué)科？數(shù)據(jù)結(jié)構(gòu)是一門研究在非數(shù)值計(jì)算的程序設(shè)計(jì)問題中，計(jì)算機(jī)的操作對(duì)象及對(duì)象間的關(guān)系和施加于對(duì)象的操作等的學(xué)科。數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有幾種表示方法？各有什么特點(diǎn)？四種表示方法（1） 順序存儲(chǔ)方式。數(shù)據(jù)元素順序存放，每個(gè)存儲(chǔ)結(jié)點(diǎn)只含一個(gè)元素。存儲(chǔ)位置反映數(shù)據(jù)元素間的邏輯關(guān)系。存儲(chǔ)密度大，但有些操作（如插入、刪除）效率較差。（2） 鏈?zhǔn)酱鎯?chǔ)方式。每個(gè)存儲(chǔ)結(jié)點(diǎn)除包含數(shù)據(jù)元素信息外還包含一組（至少一個(gè)）指針。指針反映數(shù)據(jù)元素間的邏輯關(guān)系。這種方式不要求存儲(chǔ)空間連續(xù)，便于動(dòng)態(tài)操作（如插入、刪除等），但存儲(chǔ)空間開銷大（用于指針），另外不能折半查找等。（3） 索引存儲(chǔ)方式。除數(shù)據(jù)元素存儲(chǔ)在一地址連續(xù)的內(nèi)存空間外，尚需建立一個(gè)索引表，索引表中索引指示存儲(chǔ)結(jié)點(diǎn)的存儲(chǔ)位置（下標(biāo)）或存儲(chǔ)區(qū)間端點(diǎn)（下標(biāo)），兼有靜態(tài)和動(dòng)態(tài)特性。（4） 散列存儲(chǔ)方式。通過散列函數(shù)和解決沖突的方法，將關(guān)鍵字散列在連續(xù)的有限的地址空間內(nèi)，并將散列函數(shù)的值解釋成關(guān)鍵字所在元素的存儲(chǔ)地址，這種存儲(chǔ)方式稱為散列存儲(chǔ)。其特點(diǎn)是存取速度快，只能按關(guān)鍵字隨機(jī)存取，不能順序存取，也不能折半存取。數(shù)據(jù)類型和抽象數(shù)據(jù)類型是如何定義的。二者有何相同和不同之處，抽象數(shù)據(jù)類型的主要特點(diǎn)是什么？使用抽象數(shù)據(jù)類型的主要好處是什么？數(shù)據(jù)類型是程序設(shè)計(jì)語言中的一個(gè)概念，它是一個(gè)值的集合和操作的集合。如C語言中的整型、實(shí)型、字符型等。整型值的范圍（對(duì)具體機(jī)器都應(yīng)有整數(shù)范圍），其操作有加、減、乘、除、求余等。實(shí)際上數(shù)據(jù)類型是廠家提供給用戶的已實(shí)現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)?！俺橄髷?shù)據(jù)類型（ADT）”指一個(gè)數(shù)學(xué)模型及定義在該模型上的一組操作。“抽象”的意義在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性。抽象數(shù)據(jù)類型的定義僅取決于它的邏輯特性，而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無關(guān)。無論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變就不影響它的外部使用。抽象數(shù)據(jù)類型和數(shù)據(jù)類型實(shí)質(zhì)上是一個(gè)概念。此外，抽象數(shù)據(jù)類型的范圍更廣，它已不再局限于機(jī)器已定義和實(shí)現(xiàn)的數(shù)據(jù)類型，還包括用戶在設(shè)計(jì)軟件系統(tǒng)時(shí)自行定義的數(shù)據(jù)類型。使用抽象數(shù)據(jù)類型定義的軟件模塊含定義、表示和實(shí)現(xiàn)三部分，封裝在一起，對(duì)用戶透明（提供接口），而不必了解實(shí)現(xiàn)細(xì)節(jié)。抽象數(shù)據(jù)類型的出現(xiàn)使程序設(shè)計(jì)不再是“藝術(shù)”而是向“科學(xué)”邁進(jìn)了一步。對(duì)于一個(gè)數(shù)據(jù)結(jié)構(gòu)，一般包括哪三個(gè)方面：邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、操作（運(yùn)算）。根據(jù)數(shù)據(jù)元素之間的邏輯關(guān)系，一般有哪幾類基本的數(shù)據(jù)結(jié)構(gòu)？集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形或網(wǎng)狀結(jié)構(gòu)。線性表有兩種存儲(chǔ)結(jié)構(gòu)：一是順序表，二是鏈表。試問：（1） 如果有n個(gè)線性表同時(shí)并存，并且在處理過程中各表的長度會(huì)動(dòng)態(tài)變化，線性表的總數(shù)也會(huì)自動(dòng)地改變。在此情況下，應(yīng)選用哪種存儲(chǔ)結(jié)構(gòu)？為什么？選鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。它可動(dòng)態(tài)申請(qǐng)內(nèi)存空間，不受表長度（即表中元素個(gè)數(shù)）的影響，插入、刪除時(shí)間復(fù)雜度為O（1）。（2） 若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取線性表中的元素，那么應(yīng)采用哪種存儲(chǔ)結(jié)構(gòu)？為什么？選順序存儲(chǔ)結(jié)構(gòu)。順序表可以隨機(jī)存取，時(shí)間復(fù)雜度為0（1）。線性表的順序存儲(chǔ)結(jié)構(gòu)具有三個(gè)弱點(diǎn)：其一，在作插入或刪除操作時(shí)，需移動(dòng)大量元素；其二，由于難以估計(jì)，必須預(yù)先分配較大的空間，往往使存儲(chǔ)空間不能得到充分利用；其三，表的容量難以擴(kuò)充。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是否一定都能夠克服上述三個(gè)弱點(diǎn)，試討論之。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一般說克服了順序存儲(chǔ)結(jié)構(gòu)的三個(gè)弱點(diǎn)。首先，插入、刪除不需移動(dòng)元素，只修改指針，時(shí)間復(fù)雜度為0(1)；其次，不需要預(yù)先分配空間，可根據(jù)需要?jiǎng)討B(tài)申請(qǐng)空間;其三，表容量只受可用內(nèi)存空間的限制。其缺點(diǎn)是因?yàn)橹羔樤黾恿丝臻g開銷，當(dāng)空間不允許時(shí)，就不能克服順序存儲(chǔ)的缺點(diǎn)。棧是只準(zhǔn)在一端進(jìn)行插入和刪除操作的線性表，允許插入和刪除的一端叫棧頂，另一端叫棧底。最后插入的元素最先刪除，故棧也稱后進(jìn)先出(LIFO)表。隊(duì)列是允許在一端插入而在另一端刪除的線性表，允許插入的一端叫隊(duì)尾，允許刪除的一端叫隊(duì)頭。最先插入隊(duì)的元素最先離開(刪除)，故隊(duì)列也常稱先進(jìn)先出(FIFO)表。什么是循環(huán)隊(duì)列？用常規(guī)意義下順序存儲(chǔ)結(jié)構(gòu)的一維數(shù)組表示隊(duì)列，由于隊(duì)列的性質(zhì)(隊(duì)尾插入和隊(duì)頭刪除)，容易造成“假溢出”現(xiàn)象，即隊(duì)尾已到達(dá)一維數(shù)組的高下標(biāo)，不能再插入，然而隊(duì)中元素個(gè)數(shù)小于隊(duì)列的長度(容量)。循環(huán)隊(duì)列是解決“假溢出”的一種方法。通常把一維數(shù)組看成首尾相接。在循環(huán)隊(duì)列下，通常采用“犧牲一個(gè)存儲(chǔ)單元”或“作標(biāo)記”的方法解決“隊(duì)滿”和“隊(duì)空”的判定問題。若元素的進(jìn)棧序列為：A、B、C、D、E，運(yùn)用棧操作，能否得到出棧序列B、C、A、E、D和D、B、A、C、E?為什么？能得到出棧序列B、C、A、E、D，不能得到出棧序列D、B、A、C、E。其理由為：若出棧序列以D開頭，說明在D之前的入棧元素是A、B和C，三個(gè)元素中C是棧頂元素，B和A不可能早于C出棧，故不可能得到D、B、A、C、E出棧序列。串？串是零個(gè)至多個(gè)字符組成的有限序列。從數(shù)據(jù)結(jié)構(gòu)角度講，串屬于線性結(jié)構(gòu)。與線性表的特殊性在于串的元素是字符。描述以下概念的區(qū)別：空格串與空串。空格是一個(gè)字符，其ASCII碼值是32?？崭翊怯煽崭窠M成的串，其長度等于空格的個(gè)數(shù)?？沾遣缓魏巫址拇?，即空串的長度是零。數(shù)組A[1..8,-2..6,0..6]以行為主序存儲(chǔ)，設(shè)第一個(gè)元素的首地址是78,每個(gè)元素的長度為4,試求元素A[4,2,3]的存儲(chǔ)首地址。958三維數(shù)組以行為主序存儲(chǔ)，其元素地址公式為：LOC(A)=LOC(A)+[(i-c)VV+(j-c)V+(k-c)]*L+1ijk c1c2c3 1 23 2 3 3其中ci,di是各維的下界和上界，Vi=di-ci+1是各維元素個(gè)數(shù)，L是一個(gè)元素所占的存儲(chǔ)單元數(shù)。數(shù)組A中，每個(gè)元素A[i,j]的長度均為32個(gè)二進(jìn)位，行下標(biāo)從-1到9,列下標(biāo)從1到11，從首地址S開始連續(xù)存放主存儲(chǔ)器中，主存儲(chǔ)器字長為16位。求：存放該數(shù)組所需多少單元？存放數(shù)組第4列所有元素至少需多少單元？數(shù)組按行存放時(shí)，元素A[7,4]的起始地址是多少？數(shù)組按列存放時(shí)，元素A[4,7]的起始地址是多少？答：每個(gè)元素32個(gè)二進(jìn)制位，主存字長16位，故每個(gè)元素占2個(gè)字長，行下標(biāo)可平移至1到11。242 (2)22 (3)s+182 (4)s+142從概念上講，樹，森林和二叉樹是三種不同的數(shù)據(jù)結(jié)構(gòu)，將樹，森林轉(zhuǎn)化為二叉樹的基本目的是什么，并指出樹和二叉樹的主要區(qū)別。樹的孩子兄弟鏈表表示法和二叉樹二叉鏈表表示法，本質(zhì)是一樣的，只是解釋不同，也就是說樹(樹是森林的特例，即森林中只有一棵樹的特殊情況)可用二叉樹唯一表示，并可使用二叉樹的一些算法去解決樹和森林中的問題。樹和二叉樹的區(qū)別有三：一是二叉樹的度至多為2，樹無此限制；二是二叉樹有左右子樹之分，即使在只有一個(gè)分枝的情況下，也必須指出是左子樹還是右子樹，樹無此限制；三是二叉樹允許為空，樹一般不允許為空(個(gè)別書上允許為空)。請(qǐng)分析線性表、樹、廣義表的主要結(jié)構(gòu)特點(diǎn)，以及相互的差異與關(guān)聯(lián)。線性表屬于約束最強(qiáng)的線性結(jié)構(gòu)，在非空線性表中，只有一個(gè)“第一個(gè)”元素，也只有一個(gè)“最后一個(gè)”元素；除第一個(gè)元素外，每個(gè)元素有唯一前驅(qū)；除最后一個(gè)元素外，每個(gè)元素有唯一后繼。樹是一種層次結(jié)構(gòu)，有且只有一個(gè)根結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)可以有多個(gè)子女，但只有一個(gè)雙親(根無雙親)，從這個(gè)意義上說存在一(雙親)對(duì)多(子女)的關(guān)系。廣義表中的元素既可以是原子，也可以是子表，子表可以為它表共享。從表中套表意義上說，廣義表也是層次結(jié)構(gòu)。從邏輯上講，樹和廣義表均屬非線性結(jié)構(gòu)。但在以下意義上，又蛻變?yōu)榫€性結(jié)構(gòu)。如度為1的樹，以及廣義表中的元素都是原子時(shí)。另外，廣義表從元素之間的關(guān)系可看成前驅(qū)和后繼，也符合線性表，但這時(shí)元素有原子，也有子表，即元素并不屬于同一數(shù)據(jù)對(duì)象。一棵二叉樹中的結(jié)點(diǎn)的度或?yàn)?或?yàn)?,則二叉樹的枝數(shù)為2(n0-1)，其中n0是度為0的結(jié)點(diǎn)的個(gè)數(shù)。證明：設(shè)二叉樹度為0和2的結(jié)點(diǎn)數(shù)及總的結(jié)點(diǎn)數(shù)分別為n0，n2和n，則n=n0+n2…(1)再設(shè)二叉樹的分支數(shù)為B,除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都有一個(gè)分支所指，則n=B+1 (2)度為零的結(jié)點(diǎn)是葉子，沒有分支，而度為2的結(jié)點(diǎn)有兩個(gè)分支，因此(2)式可寫為n=2*n2+1 (3)由(1)、(3)得n2=n0-1,代入(1)，并由(1)和(2)得B=2*(n0-1)。證畢。(1).如果G1是一個(gè)具有n個(gè)頂點(diǎn)的連通無向圖，那么G1最多有多少條邊？G1最少有多少條邊？.如果G2是一個(gè)具有n個(gè)頂點(diǎn)的強(qiáng)連通有向圖，那么G2最多有多少條邊？G2最少有多少條邊？.如果G3是一個(gè)具有n個(gè)頂點(diǎn)的弱連通有向圖，那么G3最多有多少條邊？G3最少有多少條邊？答：(1)G1最多n(n-1)/2條邊，最少n-1條邊(2)G2最多n(n-1)條邊，最少n條邊⑶G3最多n(n-1)條邊，最少n-1條邊(注：弱連通有向圖指把有向圖看作無向圖時(shí)，仍是連通的)n個(gè)頂點(diǎn)的無向連通圖最少有多少條邊？n個(gè)頂點(diǎn)的有向連通圖最少有多少條邊？n-1，n內(nèi)部排序(名詞解釋)假設(shè)含n個(gè)記錄的序列為｛R,R,…，R｝，其相應(yīng)的關(guān)鍵字序列為｛K,K,…，K｝，這些關(guān)鍵字相互之間可以進(jìn)行比較，即在它們之間存在著這樣一個(gè)關(guān)系KsWKsW???WI^s，按此固有關(guān)系將n個(gè)記錄序列重新排列為｛Rs『Rs2,…，Rsn｝。若整個(gè)排序過程都在內(nèi)存中完成，則稱此類排序問題為內(nèi)部排序。 12n

22.在各種排序方法中，哪些是穩(wěn)定的？哪些是不穩(wěn)定的？并為每一種不穩(wěn)定的排序方法舉出一個(gè)不穩(wěn)定的實(shí)例。排序方法平均時(shí)間最壞情況輔助空間穩(wěn)定性不穩(wěn)定排序舉例直接插O（R2）O(n2)O(1)穩(wěn)定入排序折半插O（R2）O(n2)O(1)穩(wěn)定入排序二路插O（R2）O(n2)O(n)穩(wěn)定入排序表插入O（R2）O(n2)O(1)穩(wěn)定排序起泡排O（R2）O(n2)O(1)穩(wěn)定序直接選O（R2）O(n2)O(1)不穩(wěn)2,2’，1擇排序定希爾排O(ni.3)O(ni.3)O(1)不穩(wěn)3,2,2’，1(d=2,d=1)序定快速排O(nlog2n)O(n2)O(log2n)不穩(wěn)2,2’，1序定堆排序O(nlog2n)O(nlog2n)O(1)不穩(wěn)2,1,1’（極大堆）定2-路歸O(nlog2n)O(nlog2n)O(n)穩(wěn)定并排序基數(shù)排OOO(rd)穩(wěn)定序(d*(rd+n))(d*(rd+n))23.文件文件是由大量性質(zhì)相同的記錄組成的集合，按記錄類型不同可分為操作系統(tǒng)文件和數(shù)據(jù)庫文件。文件存儲(chǔ)結(jié)構(gòu)的基本形式有哪些？一個(gè)文件采用何種存儲(chǔ)結(jié)構(gòu)應(yīng)考慮哪些因素？文件的基本組織方式有順序組織、索引組織、散列組織和鏈組織。文件的存儲(chǔ)結(jié)構(gòu)可以采用將基本組織結(jié)合的方法，常用的結(jié)構(gòu)有順序結(jié)構(gòu)、索引結(jié)構(gòu)、散列結(jié)構(gòu)。（1） 順序結(jié)構(gòu)，相應(yīng)文件為順序文件，其記錄按存入文件的先后次序順序存放。順序文件本質(zhì)上就是順序表。若邏輯上相鄰的兩個(gè)記錄在存儲(chǔ)位置上相鄰，則為連續(xù)文件；若記錄之間以指針相鏈接，則稱為串聯(lián)文件。順序文件只能順序存取，要更新某個(gè)記錄，必須復(fù)制整個(gè)文件。順序文件連續(xù)存取的速度快，主要適用于順序存取，批量修改的情況。（2） 帶索引的結(jié)構(gòu)，相應(yīng)文件為索引文件。索引文件包括索引表和數(shù)據(jù)表，索引表中的索引項(xiàng)包括數(shù)據(jù)表中數(shù)據(jù)的關(guān)鍵字和相應(yīng)地址，索引表有序，其物理順序體現(xiàn)了文件的邏輯次序，實(shí)現(xiàn)了文件的線性結(jié)構(gòu)。索引文件只能是磁盤文件，既能順序存取，又能隋機(jī)存取。（3） 散列結(jié)構(gòu)，也稱計(jì)算尋址結(jié)構(gòu)，相應(yīng)文件稱為散列文件，其記錄是根據(jù)關(guān)鍵字值經(jīng)散列函數(shù)計(jì)算確定其地址，存取速度快，不需索引，節(jié)省存儲(chǔ)空間。不能順序存取，只能隨機(jī)存取。其它文件均由以上文件派生而得。文件采用何種存儲(chǔ)結(jié)構(gòu)應(yīng)綜合考慮各種因素，如：存儲(chǔ)介質(zhì)類型、記錄的類型、大小和關(guān)鍵字的數(shù)目以及