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

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