數(shù)據(jù)結(jié)構(gòu)試題及答案精編

1、數(shù)據(jù)結(jié)構(gòu)試題及答案一、選擇題（每小題 2 分，共 20 分），每個題的備選答案中，只有一個是正確 的，請將答案填寫在試題的括號中。1、對順序存儲的線性表，設(shè)其長度為 20 ，在任何位置上插入或刪除操作都是 等概率的。插入一個元素時平均要移動表中的（ A ）個元素。A 10B 9C 11D 122、若某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一 個元素，則采用（ D ）存儲方式最節(jié)省運(yùn)算時間。A. 單鏈表B 僅有頭指針的單循環(huán)鏈表C.雙鏈表D .僅有尾指針的單循環(huán)鏈表3、當(dāng)利用大小為 n 的數(shù)組順序存儲一個棧時，假定用 top=n 表示?？?，則向 這個棧插入一個元素時，首先應(yīng)

2、執(zhí)行（ B ）語句修改 top 指針。A. top+ B . top- C . top = 0 D . top4、設(shè)入棧順序?yàn)锳, B, C, D, E,則出棧序列不可能是（C ）。A. EDCBA B. ABCDE C. ADEBC D . ABDEC5、已知關(guān)鍵字序列（ 46, 79, 56, 38, 40, 84 ）,采用快速排序（以位于最左位 置的關(guān)鍵字為基準(zhǔn)）得到的第一次劃分結(jié)果為：（ A ）A. 40, 38, 46, 56, 79, 84 B. 38, 46, 79, 56, 40, 84 C. 38, 46, 56, 79, 40, 84 D. 40, 38, 46, 79,

3、56, 84 6、一個有 n 個頂點(diǎn)和 n 條邊的無向圖一定是（ C ）。A .不連通的 B .連通的 C .有環(huán)的 D .無環(huán)的7、 在一棵具有n個結(jié)點(diǎn)的二叉樹的第i層上，最多具有（B ）個結(jié)點(diǎn)。A . 2i B . 2i-1 C . 2i+1 D . 2n8、 對線性表采用折半查找法,該線性表必須（B ）。A.采用順序存儲結(jié)構(gòu)B.采用順序存儲結(jié)構(gòu)，且元素按值有序C.采用鏈?zhǔn)酱鎯Y(jié)構(gòu)D .采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，且元素按值有序9、在一棵具有 n 個結(jié)點(diǎn)的完全二叉樹中,分支結(jié)點(diǎn)的最大編號為（ C ）。A. ?（n-1）/2? B . ?n/2? C . ?n/2? D . ?n/2? -110、 在

4、一個無向圖中,所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（ D ） 倍。A. 3 B . 1/2 C . 1 D . 2二、填空題（每小題 2 分,共 20 分）,請將正確的結(jié)果,填寫在試題的橫線上。1、帶頭結(jié)點(diǎn)的循環(huán)鏈表 L 為空的條件是。2、 序列A=12, 70, 33, 65, 24, 56 給出對應(yīng)于序列A的大頂堆HA （以線性數(shù) 組表示）。3、每次使兩個相鄰的有序表合并成一個有序表,這種排序方法叫做 排序。4、 設(shè)循環(huán)隊(duì)列Q的隊(duì)頭和隊(duì)尾指針分別為front和rear，隊(duì)列的最大容量為 MaxSize,且規(guī)定判斷隊(duì)空的條件為 Q.front = = Q.rear ，則隊(duì)列的長度 為。5、已知數(shù)

5、組 A0.110.8 按行優(yōu)先存儲,每個元素占有 5個存儲單元,且A00 的地址為 1000（十進(jìn)制）,則 A67 的地址為 。6、已知廣義表 A=（a, （）, （b, （c） ,則其深度為。7、在一棵二叉樹中,假定度為 2 的結(jié)點(diǎn)個數(shù)為 5 個,度為 1 的結(jié)點(diǎn)個數(shù)為 6個,則葉子結(jié)點(diǎn)數(shù)為 _ 個。8、 設(shè)森林F中有3棵樹，第1、2、3棵樹的結(jié)點(diǎn)個數(shù)分別為n1、n2、n3 ,當(dāng) 把森林F轉(zhuǎn)換成一棵二叉樹后，其根結(jié)點(diǎn)的右子樹中有 個結(jié)點(diǎn)。9、 將含有 64 個結(jié)點(diǎn)的完全二叉樹從根結(jié)點(diǎn)開始順序編號，根結(jié)點(diǎn)為第1 號， 其他結(jié)點(diǎn)自上向下，同一層自左向右連續(xù)編號。則第 30 號結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編

6、號為 。10、有序表 （1,2,3,4,5,6,7,8,9） 用折半查找方法，查找元素 3 的比較次數(shù)為 。三、判斷題（每小題2分，共20分），下列說法正確的在前面括號內(nèi)畫“乂”錯誤的畫“&”（） 1 、線性表的邏輯順序與存儲順序總是一致的。（） 2、在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此，單鏈表是隨機(jī)存取的存儲結(jié)構(gòu)。（） 4、棧是僅限定在一端進(jìn)行插入和刪除的線性表。（） 5、用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小與圖中的頂點(diǎn)個數(shù)無關(guān)，只與圖的邊數(shù)有關(guān)。（） 6、對于 AOE 網(wǎng)絡(luò)，加速任一關(guān)鍵活動就能使整個工程提前完成。（） 7、對兩棵具有

7、相同關(guān)鍵字集合而形狀不同的二叉排序樹，按中序遍歷它們得到的序列的順序是一樣的。（） 8、有向網(wǎng)中從一個頂點(diǎn)到另一個頂點(diǎn)的最短路徑只有一條。（） 9、對于一棵具有 n 個結(jié)點(diǎn)，其深度為 h 的二叉樹，進(jìn)行任一種次序遍歷的時間復(fù)雜度為 O（n）。（） 10 、快速排序和堆排序是不穩(wěn)定的排序方法。四、應(yīng)用題（共 40 分）1、（10分）假定一個待哈希存儲的線性表為 32,75,63,48,94,25,36,18 ，哈 希地址空間為010,若采用哈希函數(shù)H（k）=k MOD 11和線性探測再散列法 處理沖突，試給出對應(yīng)的哈希表（給出求解過程），并求出在等概率情況下查 找成功時的平均查找長度。2、（10

8、 分）有 8 個帶權(quán)結(jié)點(diǎn)，其權(quán)值分別為 4， 26， 12， 8， 7， 13， 15， 15， 試以它們?yōu)槿~結(jié)點(diǎn)生成一棵 Haffman 樹（給出過程），然后求出該樹的帶權(quán)路 徑長度 WPL。3、 （ 10分）已知一棵二叉樹，其先序序列為：ABDEGMNCFH中序序列為： DBMGNEACHF,請畫出這棵二叉樹（給出過程），并給出其后序序列。4、（ 10 分）已知關(guān)鍵字序列（ 37，23，42，55，61 ，36，28，33），請給出 采用快速排序法對序列作升序排序時每一趟的過程。答案一、選擇題（每小題 2 分，共 20 分）題號 1 2 3 4 5 6 7 8 9 10答案 A D B C

9、 A C B B C D二、填空題（每小題 2 分，共 20 分）1、L-next=L2 、 70，65，56，12，24，333、歸并 4、（Q.rearQ.front+MaxSize）%MaxSize5 、 13056、 37 、 6 8、 n2+n39 、 1510、3三、判斷題（每小題 2 分，共 20 分）題號 1 2 3 4 5 6 7 8 9 10答案 x x x V x x V x V V四、應(yīng)用題(共 40 分)1、過程 4分，哈希表 4分，平均查找長度 2分，共 10 分 H(32)=32 Mod 11=10 H(75) =75 Mod 11=9 H(63) =63 Mod

10、 11=8 H(48) =48 Mod 11=4 H(94) =94 Mod 11=6 H(25) =25 Mod 11=3 H(36) =36 Mod 11=3 ，與 25 沖突，所以 H1= (3+1 )Mod 11=4 ，與 48 沖突， H2= (3+2 )Mod 11=5 ，所以 36 的哈希地址是 5， H(18) =18 Mod 11=7 0 1 2 3 4 5 6 7 8 9 1025 48 36 94 18 63 75 32 查找成功時， 36 將比較 3 次，其它都是比較 1 次，所以平均查找長度是： ASL=( 1+1+1+1+1+1+3+1 )/8=10/8=5/4=1

11、.252、WPL值正確3分；過程每步1分；共7分WPL=4*4+7*4+12*3+13*3+8*3+15*3+15*3+26*2=2853、過程 8 分，后序序列 2 分，共 10 分 后序序列： DMNGEBHFCA4、快速排序的每一趟的過程： (共 10 分) 初始序列 37 23 42 55 61 36 28 3333 23 28 36 37 61 55 42(2 分) 28 23 33 36 3761 55 42(2 分) 23 28 33 36 37 61 55 42(2 分)23 28 33 36 37 42 55 61( 2 分)23 28 33 36 37 42 55 61(

12、2 分)數(shù)據(jù)結(jié)構(gòu)綜合測試題一、單選題1. 以下數(shù)據(jù)結(jié)構(gòu)中哪一個是線性結(jié)構(gòu)？ ( B )A. 有向圖 B. 棧 C. 線索二叉樹 D. B 樹2. 在一個單鏈表HL中，若要向表頭插入一個由指針p指向的結(jié)點(diǎn)，則執(zhí) 行 (B ) 。A. HL=p; p-next=HL;B. p-next=HL; HL=p;C. p-next=HL; p=HL;D. p-next=HL-next; HL-next=p;3. 在一個帶有頭結(jié)點(diǎn)的單鏈表HL中，若要向表頭插入一個由指針p指向 的結(jié)點(diǎn)，則執(zhí)行 ( D ) 。A. HL=p; p-next=HL;B. p-next=HL; HL=p;C. p-next=HL;

13、 p=HL;D. p-next=HL-next; HL-next=p;4. 單鏈表的每個結(jié)點(diǎn)中包括一個指針 next ，它指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)。 現(xiàn)要將指針q指向的新結(jié)點(diǎn)插入到指針p指向的單鏈表結(jié)點(diǎn)之后，下面的操作 序列中哪一個是正確的？( C )A q= p-next; p-next=q-next;B.p-next=q-next;q=p-nextC. q-next=p-next; p-next=q;D. P-next=q; q-next=p-next;5. 在一個循環(huán)順序存儲的隊(duì)列中，隊(duì)首指針指向隊(duì)首元素 的( B )位置。A 前一個B. 后一個 C. 當(dāng)前6. 以下哪一個不是隊(duì)列的基本運(yùn)算

14、？( B )A. 從隊(duì)尾插入一個新元素B. 從隊(duì)列中刪除第 i 個元素C. 判斷一個隊(duì)列是否為空D. 讀取隊(duì)頭元素的值7. 用鏈接方式存儲的隊(duì)列，在進(jìn)行刪除運(yùn)算時 (D ).A. 僅修改頭指針B. 僅修改尾指針C. 頭、尾指針都要修改D. 頭、尾指針可能都要修改8. 對線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？ ( B )A. 經(jīng)常需要隨機(jī)地存取元素B. 經(jīng)常需要進(jìn)行插入和刪除操作C. 表中元素需要占據(jù)一片連續(xù)的存儲空間D. 表中元素的個數(shù)不變9.字符 A、 B、 C 依次進(jìn)入一個棧，按出棧的先后順序組成不同的字符串，至多可以組成 ( A ) 個不同的字符串？A.5 B.4 C.6 D.1 1

15、0. 下述哪一條是順序存儲方式的優(yōu)點(diǎn)？( A )A.存儲密度大B.插入運(yùn)算方便C.刪除運(yùn)算方便D.可方便地用于各種邏輯結(jié)構(gòu)的存儲表示11. 從二叉搜索樹中查找一個元素時，其時間復(fù)雜度大致為 ( C ) 。A. O(n) B. O(1)C. O(log 2n)D. O(n 2)12. 由權(quán)值分別為 3,8,6,2,5 的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為 D。A 24 B 48C 72D 5313. 下列關(guān)于二叉樹遍歷的敘述中，正確的是 ( D ) 。A. 若一個結(jié)點(diǎn)是某二叉樹的中序遍歷的最后一個結(jié)點(diǎn)，則它必是該 二叉樹的前序最后一個結(jié)點(diǎn)B. 若一個點(diǎn)是某二叉樹的前序遍歷最后一個結(jié)點(diǎn)，

16、則它必是該二 叉樹的中序遍歷的最后一個結(jié)點(diǎn)C. 若一個樹葉是某二叉樹的中序遍歷的最后一個結(jié)點(diǎn)，則它必是 該二叉樹的前序遍歷最后一個結(jié)點(diǎn)D. 若一個樹葉是某二叉樹的前序最后一個結(jié)點(diǎn)，則它必是該 二叉樹的中序遍歷最后一個結(jié)點(diǎn)14. 高度 k 的二叉樹的最大結(jié)點(diǎn)數(shù)為 (A ).A.2k-1B.2K+1C.2K-1D. 2 k-115. 下面關(guān)于圖的存儲的敘述中正確的是 ( C ).A. 用鄰接表法存儲圖，占用的存儲空間大小只與圖中結(jié)點(diǎn) 個數(shù)有關(guān)，而與邊數(shù)無關(guān)B. 用鄰接表法存儲圖，占用的存儲空間大小只與圖中邊數(shù) 有關(guān)，而與結(jié)點(diǎn)個數(shù)無關(guān)C. 用鄰接矩陣法存儲圖，占用的存儲空間大小只與圖中結(jié)點(diǎn)個數(shù)有 關(guān)

17、，而與邊數(shù)無關(guān)D. 用鄰接矩陣法存儲圖，占用的存儲空間大小只與圖中邊數(shù) 有關(guān)，而與結(jié)點(diǎn)個數(shù)無關(guān)中, 用二分法查找關(guān)鍵碼值 10,16. 在順序表 (2,5,7,10,14,15,18,23,35,41,52) 所需的關(guān)鍵碼比較次數(shù)為 BA.2 B.3 C.4 D.517. 對線性表進(jìn)行二分法查找，其前提條件是 (A ).A. 線性表以順序方式存儲，并且按關(guān)鍵碼值排好序B. 線性表以順序方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序C. 線性表以鏈接方式存儲，并且按關(guān)鍵碼值排好序D. 線性表以鏈接方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序18.下列哪一個關(guān)鍵碼序列不符合堆的定義？（C）A. a、c、d、

18、 g、h、m、p、q、r、xB. a、 c 、m、d、h、p、x、g、o、rC.a、d、p、r 、c、q、x、 m、h、 gD.a、d、c、m、p、g、h、x、r、q19.對n 個記錄的文件進(jìn)行快速排序，所需要的輔助存儲空間為BA. O （1)B. O（1og2n）C.O（ n）D.O(n2)20. 在待排序文件已基本有序的前提下，下述排序方法中效率 最高的是 AA.直接插入排序B.直接選擇排序C.快速排序D.歸并排序21. 設(shè)有關(guān)鍵碼序列 (q ， g， m， z， a， n， p， x， h) ，下面哪一個序列是從 上述序列出發(fā)建堆的結(jié)果 ?A.a， g， h， m， n， p， q， x

19、， zzC. g ， m， q， a， n， p， x ， h， zB.D.a ， g ， m， h ，q， n， p， x，h ， g ， m， p ， a ， n ， q ，x， z22. 下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是 ( A ).A. 數(shù)組是同類型值的集合B. 遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精煉C. 樹是一種線性結(jié)構(gòu)D. 用一維數(shù)組存儲二叉樹，總是以先序遍歷的順序存儲各結(jié)點(diǎn)二、填空題1. 數(shù)據(jù)的邏輯結(jié)構(gòu)被分為 、 、和四種。2. 數(shù)據(jù)的物理結(jié)構(gòu)被分為 順序、_鏈表、索引和散列 四種。3. 一個算法的時間復(fù)雜度為 (3 n +2nlog 2 n +4n-7)/(5 n)

20、，其數(shù)量級表示為。4. 對于一個長度為 n 的單鏈存儲的線性表，在表頭插入元素的時間復(fù)雜度為 ，在表尾插入元素的時間復(fù)雜度為 。5. 對于一個長度為 n 的順序存儲的線性表，在表頭插入元素的時間復(fù)雜度為 ，在表尾插入元素的時間復(fù)雜度為 。6. 在以 HL 為表頭指針的帶表頭附加結(jié)點(diǎn)的單鏈表和循環(huán)單鏈 表中，鏈表為空的條件分別為 和 。7. 一個廣義表中的元素分為 單元素和 表元素兩類。8. 從一個鏈棧中刪除一個結(jié)點(diǎn)時，需要把棧頂結(jié)點(diǎn)的_指針 域的值賦給 _棧頂指針 。9. 進(jìn)行函數(shù)調(diào)用時，需要把每個實(shí)參的值和調(diào)用后的_返回地址傳送給被調(diào)用的函數(shù)中。10. 設(shè)W為一個二維數(shù)組，其每個數(shù)據(jù)元素占用

21、 6個字節(jié)，行下標(biāo)i從0到8，列下標(biāo)j從0到3 ,則二維數(shù)組 W的數(shù)據(jù)元素共占用個字節(jié)。 W中第6行的元素和第4列的元素共占用個字節(jié)。若按行順序存放二維數(shù)組W其起始地址為100,則二維數(shù)組W勺最后一個數(shù)據(jù)元素的起始地址為。11. 在線性表的單鏈存儲中，若一個元素所在的結(jié)點(diǎn)地址為 p,則其后繼結(jié)點(diǎn)的地址為 若假定p為一個數(shù)組a中的下標(biāo)，則其后繼結(jié)點(diǎn)的下標(biāo)為 。12. 在稀疏矩陣所對應(yīng)的三元組線性表中，每個三元組元素按 行號為主序、 列號為輔序的次序排列。13. 棧又稱為 表，隊(duì)列又稱為 表。14. 中綴算式（ 3+4）*2/ （8-5）所對應(yīng)的后綴算式為15. 后綴算式 4 2 3 * + 10

22、 5 / - 的值為。16. 對于一棵具有n個結(jié)點(diǎn)的二叉樹，一個結(jié)點(diǎn)的編號為i（1 i n），若它有左孩子則左孩子結(jié)點(diǎn)的編號為 ，若它有右孩子，則右孩子結(jié)點(diǎn)的編號為 ，若它有雙親，則雙親結(jié)點(diǎn)的編號為 _i/2_ 。17. 在一棵高度為 5 的理想平衡樹中，最少含有 16個結(jié)點(diǎn)，最多含有個結(jié)點(diǎn)。18. 假定一棵樹的廣義表表示為 A（B（C， D（E， F， G）， H（I ， J），則樹中所含的結(jié)點(diǎn)數(shù)為 個，樹的深度為 ，樹的度為 。19. 若一棵二叉樹中只有葉子結(jié)點(diǎn)和左、右子樹皆非空的結(jié)點(diǎn)，設(shè)葉結(jié)點(diǎn)的個數(shù)為K,則左、右子樹皆非空的結(jié)點(diǎn)個數(shù)是 。20. 在樹中，一個結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的個數(shù)稱為該

23、結(jié)點(diǎn)的 。21. 在 n 個帶權(quán)葉子結(jié)點(diǎn)構(gòu)造出的所有二叉樹中，帶權(quán)路徑長度最小的二叉樹稱為霍夫曼樹。WPL稱為帶權(quán)路徑長度。22. 對一棵二叉搜索樹進(jìn)行中序遍歷時，得到的結(jié)點(diǎn)序列是一個_有序序列 。23. 當(dāng)向一個小根堆插入一個具有最小值的元素時，需要逐層 向上調(diào)整，直到被調(diào)整到 根位置為止。24. 在一個堆的順序存儲中，若一個元素的下標(biāo)為 i（0 i Wn-1），貝U它的左孩子元素的下標(biāo)為 ，右孩子元素的下標(biāo)為 。25. 在一個具有 n 個頂點(diǎn)的無向完全圖中，包含有 條邊，在一個具有 n 個頂點(diǎn)的有向完全圖中，包含有 條邊。26. 對于一個具有 n 個頂點(diǎn)和 e 條邊的有向圖和無向圖，若采用

24、邊集數(shù)組表示，則存于數(shù)組中的邊數(shù)分別為 和條。27. 以二分查找方法從長度為12的有序表中查找一個元素時，平均查找長度為。28. 假定一個線性表為(12,23,74,55,63,40,82,36) ，若按Key % 3條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個子表，則得到的三個子表分別為 、和。29. 在線性表的散列存儲中，裝填因子 a又稱為裝填系數(shù)，若用m表示散列表的長度，n表示待散列存儲的元素的個數(shù)，則a等于。30. 在一棵m階BJ樹上，每個非樹根結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)目最少為 個,最多為 ，其子樹數(shù)目最少為 最多為。31. 表示圖的三種常用的存儲結(jié)構(gòu)為 、和。32. 對于一個具有n個頂點(diǎn)和e條邊的

25、有向圖和無向圖，在其對應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)分別有和。33. 對用鄰接矩陣表示的有向圖進(jìn)行任一種遍歷時，其時間復(fù)雜度為 。對用鄰接表表示的有向圖進(jìn)行任一種遍歷時，其時間復(fù)雜度為。34. 對于線性表(70，34，55, 23, 65，41, 20，100)進(jìn)行散列存儲時，若選用H( K)=K %9作為散列函數(shù)，貝U散列地址為1的元素有 ，散列地址為7的有 。35. 在索引表中，若一個索引項(xiàng)對應(yīng)主表的一個記錄，則此索引為 引，若對應(yīng)主表的若干條記錄，則稱此索引為 引。36. 向一棵BJ樹插入元素的過程中，若最終引起樹根結(jié)點(diǎn)的分裂，則新樹比原樹的高度。37. 在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行篩

26、運(yùn)算的時間復(fù)雜度為，整個堆排序過程的時間復(fù)雜度為 。38. 快速排序在平均情況下的時間復(fù)雜度為 在最壞情況下的時間復(fù)雜度為。39. 在歸并排序中，進(jìn)行每趟歸并的時間復(fù)雜度為 ，整個排序過程的時間復(fù)雜度為 ，空間復(fù)雜度為 。40. 在快速排序、堆排序、歸并排序中， 卡序是穩(wěn)定的。三、運(yùn)算題1. 在如下數(shù)組A中鏈接存儲了一個線性表，表頭指針為A 0.next ，試寫出該線性表。a 01234567data605078903440n ext43025712. 假定一棵二叉樹廣義表表示為a(b(c),d(e,f)，分別寫出對它進(jìn)行先 序、中序、后序、按層遍歷的結(jié)果。先序：中序：后序：按層：3. 已知一

27、棵二叉樹的先序遍歷的結(jié)果是 ABECDFGHIJ,中序遍歷的結(jié)果是 EBCDAFHIG J試畫出這棵二叉樹。4. 鐵路進(jìn)行列車調(diào)度時 , 常把站臺設(shè)計(jì)成棧式結(jié)構(gòu)的站臺，如下圖 1 所示 試問：(1) 設(shè)有編號為 1,2,3,4 的四輛列車 , 順序開入棧式結(jié)構(gòu)的站臺 , 則可能的出棧序列有多少種 ?(2) 若進(jìn)站的四輛列車順序如上所述 , 那么是否能夠得到4123這樣的出棧序列？ 如果不能 , 說明為什么不能。如果能 , 說明如何得到 該序列的(即寫出“進(jìn)棧”或“出?！钡男蛄?。(3) 若進(jìn)站的四輛列車順序如上所述 , 那么是否能夠得到 3421這樣的出棧序列？ 如果不能 , 說明為什么不能。

28、如果能 , 說明如何得到 該序列的(即寫出“進(jìn)?！被颉俺鰲！钡男蛄?。圖15. 寫出下列中綴表達(dá)式的后綴形式：(1) A * B * C(2) A + B - C + D(3) A* B + C(4) (A + B) * D + E / (F + A * D) + C6. 畫出下列廣義表的帶有附加表頭結(jié)點(diǎn)的鏈接存儲結(jié)構(gòu)圖，并給出它們的 長度和深度。(1) D= (a,b),(c,d )(2) A= (a, (b,c ), ( d) ,e )7. 將一組元素 37,56,23,65,22,10,29 依次插入一棵空二叉搜索樹中，請 畫出該二叉搜索樹。8. 設(shè)有序順序表中的元素依次為 017, 0

29、94, 154, 170, 275,503, 509,512, 553, 612, 677, 765, 897, 908 。試畫出對其進(jìn)行折半搜索時的判定樹 , 并計(jì)算搜索成功的平均搜索長度和搜索不成功的平均搜索長度。9. 已知一個圖的頂點(diǎn)集 V 和邊集 E 分別為：V=0,1,2,3,4,5,6,7;E=(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10,(4,6)4,(5,7)20;(1) 按照普里姆算法從頂點(diǎn) 0 出發(fā)得到最小生成樹，試寫出在最小生成樹中依 次得到的各條邊。(2) 用克魯斯卡爾算法得到最小生成樹，試寫出在最

30、小生成樹中依次得到的各 條邊。10. 已知一個圖的頂點(diǎn)集V和邊集E分別為：V=1,2,3,4,5,6,7， 8;E=(1,2),(1,3),(2,4),(2,5),(3,6),(3,7),(4,8),(5,8),(6,8),(7,8); 若存儲它采用鄰接表，并且每個頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號從小 到大的次序鏈接的，則：( 1 )給出從 1 號頂點(diǎn)出發(fā)按主教材中介紹的按深度優(yōu)先搜索遍歷的頂點(diǎn)序列(2) 給出從 1 號頂點(diǎn)出發(fā)按主教材中介紹的按廣度優(yōu)先搜索遍歷的頂點(diǎn)序列 (提示：先畫出對應(yīng)的圖形，然后再運(yùn)算)。11. 已知一個圖的頂點(diǎn)集V和邊集E分別為：V=0,1,2,3,4,5,6,7

31、;E=(0,2),(1,3),(1,4),(2,4),(2,5),(3,6),(3,7),(4,7),(4,8), (5,7),(6,7),(7,8);若存儲它采用鄰接表，并且每個頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號從小 到大的次序鏈接的，按主教材中介紹的拓樸排序算法進(jìn)行排序，試給出得到的 拓樸排序的序列。(提示：先畫出對應(yīng)的圖形，然后再運(yùn)算)。12. 散列表的地址區(qū)間為0-16，散列函數(shù)為H( K) =K % 17,采用線性探查法處 理沖突，并已將關(guān)鍵字序列26、25、72、38、& 18、59依次存儲到了散列表 中：(1) 元素59存放在散列表中的地址是多少？(2) 搜索元素59需要比較的

32、次數(shù)是多少？13. 已知待散列的線性表為(36，15, 40，63, 22)，散列用的一維地址空間為 0.6，假定選用的散列函數(shù)是H( K)=K % 7,若發(fā)生沖突采用線性探查法處 理，試：(1) 計(jì)算出每一個元素的散列地址并在下圖中填寫出散列表；(2) 求出在查找每一個元素概率相等情況下的平均查找長度。012345614. 假定一組記錄的排序碼為(46,79,56,38,40,80,25,34)，試寫出對其進(jìn)行快 速排序的第一次劃分的結(jié)果。四、閱讀算法，回答問題1. void AE(Stack& S)Ini tStack(S);Push(S,30);Push(S,40);Push(S,50)

33、;int x=Pop(S)+2*Pop(S);Push(S,x);int i,a4=5,8,12,15;for(i=0;i4;i+) Push(S,ai); while(!StackEmpty(S) coutPop(S)adjvex;if(!visitedj) coutjnext;該算法的功能為：3. 指出下列算法的功能，并求出時間復(fù)雜度：( 1) int sum1(int n)int p=1,s=0;for (int i=1;i=n;i+)p*=i;s+=p;return s;( 2) int sum2(int n)int s=0;for (int i=1;i=n;i+)int p=1;fo

34、r (int j=1;j=i;j+)p*=j;s+=p;return s;4. 在下面的每個程序段中，假定線性表 La 的類型為 List ，元素類型 ElemType為int，并假定每個程序段是連續(xù)執(zhí)行的。試寫出每個程序段執(zhí)行后 所得到的線性表 La。(1) InitList(La);Int a=48,26,57,34,62,79;For (i=0;i6;i+)Insert(La,ai);TraverseList(La);(2) Insert(La,56);DeleteFront(La);InsertRear(La, DeleteFront(La);TraverseList(La);( 3)

35、 For (i=1;i=3;i+)Int x=GetElem(La,i);If (x%2=0) Delete(La,x);TraverseList(La);( 4) ClearList(La);For (i=0;i6;i+)InsertRear(La,ai);Delete(La,a5);Sort(La);Insert(La,a5/2);TraverseList(La);五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容。1. 向單鏈表的末尾添加一個元素的算法。 Void InsertRear(LNode*& HL,const ElemType& item) LNode* newptr; newptr

36、=new LNode;If ()cerrMemory allocation failare!data=item;=NULL;if (HL=NULL)HL=newptr;elseLNode* P=HL;While (P-next!=NULL) p-next=newptr;2. 向以 BST 為樹根指針的二叉搜索樹上插入值為 item 的結(jié)點(diǎn)的遞歸算法 void Insert(BTreeNode*& BST, const ElemType& item) if(BST=NULL) BTreeNode* p=new BTreeNode; p-data=item;BST=p;else if(itemda

37、ta) ;else ;3. 二分查找的遞歸算法。Int Binsch(ElemType A,int low,int high,KeyType K)if (low=high)int mid=(low+high)/2;if ()return mid; / 查找成功，返回元素的 下標(biāo)else if (K=n) 。請編寫一個函數(shù)將這 個線性表原地逆置，即將數(shù)組的前 n 個原址內(nèi)容置換為 ( en-1, en-2, ,e1,e0) 。void inverse ( ElemType A , int n )3. 試編寫一個算法，在帶表頭結(jié)點(diǎn)的單鏈表中尋找第 i 個結(jié)點(diǎn)。若找到，則函數(shù)返回第 i 個結(jié)點(diǎn)的地址

38、；若找不到，則函數(shù)返回NULL。LNode* GetANode (LNode* & HL， int i )參考答案一、單選題1. B 2.B 3.D 4.C 5.A 6.B 7.D 8.B 9.A 10.A 11.C 12.D13. D 14.A 15.C 16.B 17.A 18.C 19.B 20.A 21.C 22.A二、填空題1. 集合結(jié)構(gòu) 線性結(jié)構(gòu) 樹結(jié)構(gòu) 圖結(jié)構(gòu) 2.順序 鏈表 索引 散列3. O(n) 4. O(1) O(n)HL-next=NULL HL-next=HL 指針（或 next ） 棧頂指針（或 HS） 310 矩陣元素的）9.返回地址 10. 36*6( 或 21

39、6) 12*6（或 72）11.p-next ap.next 12.(矩陣元素的)行號列號13.先進(jìn)后出表（或后進(jìn)先出表） 先進(jìn)先出表14.5 - /15.8 16.2i 2i+1 ?i/2? (或 i/2 )17.16 3118. 10 4 319.k-1 20.度21.哈夫曼樹木帶權(quán)路徑長度 22.有（或升）序序列23.向上 根24. 2i+1 2i+225.n(n-1)/2n(n-1) 26. e e27.37/12 28.(12,63,36) (55,40,82)(23,74)29.n/m 30.em/2u-1m-1em/2um31.鄰接矩陣鄰接表 邊集數(shù)組 32. e2e33.O(n

40、2) O(e) 34. 2 235.稠密 稀疏 36. 增加 137.O(log 2n)2O(nlog 2n) 38.O(nlog 2n) O(n 2)39.O(n) O(nlog 2n) O(n) 40.歸并5.7.O(n) O(1) 6. 單 表 8.3 4 + 2 * 8三、運(yùn)算題1. 【解答】 （90,34,40,60,78,50）2. 先序： a,b,c,d,e,f中序： c,b,a,e,d,f后序： c,b,e,f,d,a按層： a,b,d,c,e,f3. 【解答】當(dāng)前序序列為ABECDFGH,中序序列為EBCDAFHIG時，逐步形成二叉樹的過 程如下圖 2 所示：EBCDFHIG

41、JAABEFCDHIGJABEFCDGJHIABEFCDGJhI圖24. 【解答】( 1)不同的出棧序列有 14 種。(2)不能得到 4123這樣的出棧序列。因?yàn)槿粼?4 之后再將 1, 2 ，3 出棧，則必有 1, 2 ，3 在 4 前入棧，即 1 先進(jìn)棧， 2 后進(jìn)棧， 3 再進(jìn)棧，此時 3 壓 在 2 上， 2 壓在 1 上。最后 4 進(jìn)棧。 4 首先出棧，由于 1 壓在最下面，由棧的特 性知此時 1 不可能先于 2 和 3 出棧，所以 4123 種出棧序列不可能出現(xiàn)。(3) 能得到 3421 這樣的出棧序列。即 1 入棧，2 入棧，3 入棧，然后 3 出棧， 再 4 入棧，接著 4 出

42、棧， 2 出棧， 1 出棧。5. 【解答】(1) A B * C *(2) AB + C - D +(3) AB * C +(4) A B + D * E F A D * + / + C +6. 【解答】 (1) D 的長度為 2，深度為 2，其鏈接存儲結(jié)構(gòu)見下圖 3(a)D(2) A 的長度為 1，深度為 4，其鏈接存儲結(jié)構(gòu)見下圖 3(b9. (1)普里姆： (0,3)2, (0,2)5, (0,1)8, (1,5)6, (3,6)10, (6,4)4,(5,7)20(2)克魯斯卡爾： (0,3)2, (4,6 ) 4,(0,2)5,(1,5)6,(0,1)8,(3,6)10,(5,7)20

43、10. (1)DFS：1，2，4，8，5，6，3，7(2)BFS：1，2，3，4，5，6，7，811. 拓?fù)湫蛄校?1,3,6,0,2,5,4,7,812. (1)11(2)413. (1) H(36)=36 % 7=1H(15)=15 % 7=1 沖突H1(15)=(15+1) % 7=2H (40) =40 % 7=5H (63) =63 %7=0H (22) =22 % 7=1 沖突 H (22) = (22+1) % 7=2 沖突 H2 (22)=(22+2) %7=301234566336152240(2)平均查找長度=(1+2+1+1+3)/5=1.614. 40 34 25 38

44、 46 80 56 79四、閱讀算法，回答冋題1. 輸出結(jié)果為：15 12 8 5 130 302. 功能為：從初始點(diǎn)Vi出發(fā)廣度優(yōu)先搜索由鄰接表 GL所表示的圖。3. (1)功能為：s=1!+2!+,n!時間復(fù)雜度0(n)(2)功能同(1)，時間復(fù)雜度O(n2)4. (1)(26,34,48,57,62,79)(2) (48,56,57,62,79,34)(3) (57,62,79,34)(4) (26,34,39,48,57,62)五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容。1. n wptr=NULLn ewptr-p=p-n ext;2. p-left=p-right=NULLIn

45、sert(BST-left, item)In sert(BST-right, item)3. K=Amid.keyBinsch(A,mid+1,hight,K)return -1六、編寫算法1. void In sert1(List& L, int i, ElemType x)for(i nt j=L.size-1; j=i-1; j-)L.listj+1=L.listj;L.listi-1=x;/第i個元素的下標(biāo)為i-1L.size+;2. void in verse ( ElemType A , i nt n )ElemType tmp;for ( int i = 0; i = ( n-1

46、 ) / 2; i+ ) tmp = Ai; Ai = A n-i-1;A n-i-1 = tmp;3. LNode* GetANode (LNode* & HL , int i )/取得帶有頭對點(diǎn)的單鏈表中第i個結(jié)點(diǎn)地址(i從1開始計(jì)數(shù))。若i 表長時，返回的指針值為 NULLif ( i next; int k = 1;while ( p != NULL & k next;k+; return p; 數(shù)據(jù)結(jié)構(gòu)試卷(三)(A) q=p-next ；p-data=q-data(B) q=p-next ；q-data=p-datap-next=q-next ；free(q) ； p-next=q

47、-next ；free(q) ；一、選擇題 ( 每題 1分，共 20 分)1設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=(D，R)，D=01 ，02，03，04，05，06，07，08，09，R=r ，r=， , , , ，則數(shù)據(jù)結(jié)構(gòu) A是()。(A) 線性結(jié)構(gòu) (B) 樹型結(jié)構(gòu)(C) 物理結(jié)構(gòu)(D) 圖型結(jié)構(gòu)2下面程序的時間復(fù)雜為()for (i=1 , s=0； i=n ； i+ )t=1 ；for(j=1；jnext ；p-next=q-next ；free(q) ；(D) q=p-next ；p-data=q-data ；free(q) ；4設(shè)有 n 個待排序的記錄關(guān)鍵字,則在堆排序中需要()個

48、輔助記錄單元。2(A) 1(B) n(C) nlog 2n(D) n 25設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為 (20, 15, 14, 18, 21, 36, 40, 10),則以20 為基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為 ( ) 。(A) 10 , 15, 14, 18, 20, 36, 40, 21(B) 10, 15, 14, 18, 20, 40,36, 21(C) 10 , 15, 14, 20, 18, 40, 36, 2l (D) 15, 10, 14, 18, 20, 36,40, 216設(shè)二叉排序樹中有 n 個結(jié)點(diǎn),則在二叉排序樹的平均平均查找長度為( ) (A) O(1)(B)

49、 O(log 2n) (C)(D) O(n 2)7設(shè)無向圖G中有n個頂點(diǎn)e條邊，則其對應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn) 的個數(shù)分別為( )。(A) n, e(B) e , n (C) 2n , e (D) n , 2e8.設(shè)某強(qiáng)連通圖中有n個頂點(diǎn)，則該強(qiáng)連通圖中至少有()條邊。(A) n(n-1)(B) n+1(C) n(D) n(n+1)9設(shè)有 5000 個待排序的記錄關(guān)鍵字,如果需要用最快的方法選出其中最小的 10個記錄關(guān)鍵字,則用下列( )方法可以達(dá)到此目的。(A)快速排序(B)堆排序 (C)歸并排序(D)插入排序10. 下列四種排序中( )的空間復(fù)雜度最大。(A) 插入排序 (B) 冒泡

50、排序 (C) 堆排序 (D) 歸并排序二、填空殖 ( 每空 1分 共 20 分)1. 數(shù)據(jù)的物理結(jié)構(gòu)主要包括 和兩種情況。2. 設(shè)一棵完全二叉樹中有 500 個結(jié)點(diǎn)，則該二叉樹的深度為 ；若用二叉鏈表作為該完全二叉樹的存儲結(jié)構(gòu)，則共有 個空指針域。3. 設(shè)輸入序列為 1、2、3，則經(jīng)過棧的作用后可以得到 種不同的輸出序列。4. 設(shè)有向圖G用鄰接矩陣Ann作為存儲結(jié)構(gòu)，則該鄰接矩陣中第i行上所 有元素之和等于頂點(diǎn) i 的，第 i 列上所有元素之和等于頂點(diǎn) i 的5. 設(shè)哈夫曼樹中共有 n 個結(jié)點(diǎn)，則該哈夫曼樹中有 個度數(shù)為 1 的結(jié)點(diǎn)。6. 設(shè)有向圖G中有n個頂點(diǎn)e條有向邊，所有的頂點(diǎn)入度數(shù)之和為d，則e和d的關(guān)系為。7. 遍歷二叉排序樹中的結(jié)點(diǎn)可以得到一個遞增的關(guān)鍵字序列(填先序、中序或后序) 。8. 設(shè)查找表中有100個元素，如果用二分法查找方法查找數(shù)據(jù)元素X,則最多需要比較 就可以斷定數(shù)據(jù)元素 X是否在查找表中。9. 不論是順序存儲結(jié)構(gòu)的棧還是鏈?zhǔn)酱鎯Y(jié)構(gòu)的棧，其入棧和