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

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