(考試資料下載)數(shù)據(jù)結(jié)構(gòu)試題4

肇慶學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系數(shù)據(jù)結(jié)構(gòu)2001級試卷(A)班級： 姓名： 學(xué)號： . -密-封-線- 考試時間：2003.07題號一二三四五總分分?jǐn)?shù)得分一、 單項(xiàng)選擇題（2分10=20分） 1若某線性表中最常用的操作是刪除第1個元素，則不宜采用（ ）存儲方式。A.單鏈表 B.雙鏈表 C.單向循環(huán)鏈表 D.順序表 2在一棵完全二叉樹的順序存儲方式中，若編號i的結(jié)點(diǎn)有右孩子1，則其右孩子的編號為（ ）。A. 2i B. 2i-1 C. 2i+1 D. i/2 3. 按照二叉樹的定義，具有3個結(jié)點(diǎn)的二叉樹有（ ）種不同形態(tài)。A. 3 B. 4 C. 5 D. 6 4. 在長為n的順序表中，刪除第i個元素(1in+1)需要向前移動（ ）個元素。A. n-i B. n-i+1 C. n-i-1 D. i 5. 一個隊(duì)的入隊(duì)順序是1、2、3、4、5，則此隊(duì)的出隊(duì)順序?yàn)椋?）。A. 5、4、3、2、1 B. 4、5、3、2、1C. 4、3、5、1、2 D. 1、2、3、4、5 6. 棧是一種特殊的線性表，其特殊性表現(xiàn)在（ ）。A. 可以順序存儲 B.只能從端點(diǎn)進(jìn)行插入和刪除 C. 可以鏈?zhǔn)酱鎯?D. 可以在任何位置進(jìn)行插入和刪除 7. 一棵二叉樹中，第k層上最多有（ ）個結(jié)點(diǎn)。A. 2k B.2k-1 C.2k D.2k-1 8. 一棵有18個結(jié)點(diǎn)的二叉樹，其高度最小為（ ）層。 A. 4 B. 5 C. 6 D. 189. n個頂點(diǎn)的有向圖中最多有（ ）條弧。 A. n(n-1)/2 B. n(n-1) C. n(n+1) D. n(n+1)/210.有向圖中，所有頂點(diǎn)入度和是所有頂點(diǎn)出度和的（ ）倍。 A. 0.5 B. 1 C. 2 D. 4得分二、 判斷題（1分10=10分）（ F ） 1. 在線性結(jié)構(gòu)的順序存儲結(jié)構(gòu)中，邏輯上相鄰的兩個元素在物理位置上不一定相鄰。（ F ） 2. 二叉樹就是度為2的樹。（ T ） 3. 存在這樣的二叉樹，其后序遍歷與中序遍歷得到的訪問序列相同。（ T ） 4.滿二叉樹一定是完全二叉樹。（ F ） 5.由空格組成的串叫空串。（ T ） 6. 在AOE網(wǎng)中，可能有多條關(guān)鍵路徑。（ T ） 7. m階B-樹具有k個子樹的非葉子結(jié)點(diǎn)含有k-1個關(guān)鍵字。（ T ） 8. 起泡排序是穩(wěn)定的。（ F ） 9. 鏈?zhǔn)酱鎯Φ木€性表可以實(shí)現(xiàn)隨機(jī)存取。（ F ）10.二叉樹按某種順序線索化后，任一結(jié)點(diǎn)均有指向其直接前驅(qū)和直接后繼的線索。得分三、填空題（2分8=16分）1在單鏈表中，若刪除指針p所指結(jié)點(diǎn)的直接后繼，則需要執(zhí)行下列三條語句：q=p-next； ；free（q）；2. 在有頭結(jié)點(diǎn)的單鏈表L中，指針p所指結(jié)點(diǎn)是最后一個結(jié)點(diǎn)的條件是 。3. 隊(duì)是一種受限制的線性表，也叫FIFO結(jié)構(gòu)，F(xiàn)IFO的含義是 。4. 對于棧，只能在 插入元素，只能在 刪除元素。5. 數(shù)據(jù)的基本單位是 ，在計(jì)算機(jī)程序中通常作為一個整體進(jìn)行考慮和處理。6. 圖的遍歷方式通常有 遍歷和 遍歷兩種。得分四、簡答和應(yīng)用題（38分）1. （8分）某二叉樹后序遍歷的結(jié)果是ABCDEFG，中序遍歷的結(jié)果是ADBCGFE.（1） 畫出此二叉樹；（2） 寫出其先序遍歷的結(jié)果。2. （9分）已知如圖所示有向圖， （1） 求各點(diǎn)的入度和出度；（2） 給出該圖的鄰接矩陣；（3） 給出該圖的一個拓?fù)渑判颉?. 給出下面稀疏矩陣的三元組。（5分）4. （8分）已知序列5，3，4，8，6。（1） 以該序列為權(quán)構(gòu)造一棵有5個葉子結(jié)點(diǎn)的Huffman樹。（2） 求上邊構(gòu)造的Huffman樹的帶權(quán)路徑長度WPL.5. （8分）已知如圖所示的連通網(wǎng)。求其最小生成樹（要求畫出生成的過程）。V1V2V3V4V5V632243132得分五、設(shè)計(jì)題（16分）1. 編寫實(shí)現(xiàn)“直接插入排序”的子函數(shù)，入口參數(shù)是整形數(shù)組L 和數(shù)組長度n.2. 寫出統(tǒng)計(jì)二叉樹葉子結(jié)點(diǎn)個數(shù)的子函數(shù)，入口參數(shù)是其根結(jié)點(diǎn)指針：BiTree型指針T，其中BiTree定義為：typed