數(shù)據(jù)結(jié)構(gòu)概念名詞解釋大全-資料下載頁
2025-06-25 07:23本頁面
【正文】 要結(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ù)對象。 18．一棵二叉樹中的結(jié)點的度或為0或為2，則二叉樹的枝數(shù)為2(n01)，其中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=n01,代入（1），并由（1）和（2）得B=2*(n01)。 證畢。 19．（1）．如果G1是一個具有n個頂點的連通無向圖，那么G1最多有多少條邊？G1最少有多少條邊？ （2）．如果G2是一個具有n個頂點的強連通有向圖，那么G2最多有多少條邊？G2最少有多少條邊？ （3）．如果G3是一個具有n個頂點的弱連通有向圖，那么G3最多有多少條邊？G3最少有多少條邊？ 答：（1）G1最多n(n1)/2條邊，最少n1條邊 (2) G2最多n(n1)條邊，最少n條邊 (3) G3最多n(n1)條邊，最少n1條邊 (注：弱連通有向圖指把有向圖看作無向圖時，仍是連通的) 20．n個頂點的無向連通圖最少有多少條邊？n個頂點的有向連通圖最少有多少條邊？ n1，n 21．內(nèi)部排序（名詞解釋） 假設(shè)含n個記錄的序列為{ R1, R2, …，Rn }，其相應(yīng)的關(guān)鍵字序列為{ K1, K2, …，Kn }，這些關(guān)鍵字相互之間可以進行比較，即在它們之間存在著這樣一個關(guān)系Ks1≤Ks2≤…≤Ksn，按此固有關(guān)系將n個記錄序列重新排列為{ Rs1, Rs2, …，Rsn }。若整個排序過程都在內(nèi)存中完成，則稱此類排序問題為內(nèi)部排序。22．在各種排序方法中，哪些是穩(wěn)定的？哪些是不穩(wěn)定的？并為每一種不穩(wěn)定的排序方法舉出一個不穩(wěn)定的實例。 排序方法 平均時間 最壞情況 輔助空間 穩(wěn)定性 不穩(wěn)定排序舉例 直接插入排序 O（n2） O（n2） O（1） 穩(wěn)定 折半插入排序 O（n2） O（n2） O（1） 穩(wěn)定 二路插入排序 O（n2） O（n2） O（n） 穩(wěn)定 表插入排序 O（n2） O（n2） O（1） 穩(wěn)定 起泡排序 O（n2） O（n2） O（1） 穩(wěn)定 直接選擇排序 O（n2） O（n2） O（1） 不穩(wěn)定 2,2’,1 希爾排序 O（） O（） 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ù)排序 O ( d*(rd+n) ) O ( d*(rd+n) ) O (rd ) 穩(wěn)定 23．文件 文件是由大量性質(zhì)相同的記錄組成的集合，按記錄類型不同可分為操作系統(tǒng)文件和數(shù)據(jù)庫文件。 24．文件存儲結(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)文件。順序文件只能順序存取，要更新某個記錄，必須復(fù)制整個文件。順序文件連續(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ù)目以及對文件作何種操作。25．索引文件 在主文件外，再建立索引表指示關(guān)鍵字及其物理記錄的地址間一一對應(yīng)關(guān)系。這種由索引表和主文件一起構(gòu)成的文件稱為索引文件。索引表依關(guān)鍵字有序。主文件若按關(guān)鍵字有序稱為索引順序文件，否則稱為索引非順序文件（通常簡稱索引文件）。索引順序文件因主文件有序，一般用稀疏索引，占用空間較少。常用索引順序文件有ISAM和VSAM。ISAM采用靜態(tài)索引結(jié)構(gòu)，而VSAM采用B+樹的動態(tài)索引結(jié)構(gòu)。索引文件既能順序存取，也能隨機存取。 26．索引順序文件 在索引文件中，若（數(shù)據(jù)區(qū)）主文件中關(guān)鍵字有序，則文件稱為索引順序文件。
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1