1、數(shù)據(jù)結(jié)構(gòu)的綜合練習(xí)一、選擇題1.數(shù)據(jù)存儲結(jié)構(gòu)包括四種基本類型：順序、鏈接、哈希和()。數(shù)組集合向量2.以下程序的時間復(fù)雜度為()數(shù)量級。int i=0，s1=0，S2=0；而(i next=phb . p-next=ph；ph=p；C.p-next=ph；p=ph。d . p-next=ph-next；ph-next=p；11.在一個鏈表中，頭中的指針是ph，如果你想在指針q指向的節(jié)點后面插入一個指針p指向的節(jié)點，那么執(zhí)行()操作。A.q-next=p-next；p-next=q；B.p-next=q-next；q=p；C.q-next=p-next；p-next=q；D.p-next=q-n

2、ext；q-next=p；12.在單個鏈表HL中，如果你想刪除指針q所指向的節(jié)點的后繼節(jié)點(如果有的話),那么執(zhí)行()操作。A.p=q-下一個；p-next=q-next；B.p=q-下一個；q-next=p；C.p=q-下一個；q-next=p-next；D.q-next=q-next-next；q-next=q；13.在()中插入和刪除堆棧。A.堆棧頂部堆棧底部任意位置指定位置14.如果元素1、2、3和4依次堆疊，堆疊順序中不可能有()。A.3，2，1，4 B.2，1，4，3C.4，3，2，1 D1，4，2，315.假設(shè)順序循環(huán)隊列的頭指針和尾指針分別由f和r表示，那么判斷團隊空缺的條件是

3、()。a . f 1=r . b . r 1=f . c . f=0 . d . f=r16.假設(shè)順序循環(huán)隊列存儲在數(shù)組aN中，其隊列頭和隊列尾指針分別為對于f和r，判斷隊列是否滿的條件是()。A.(r-1)%N=f B.(r 1)%N=fC.(f1)% N=r d .(f1)% N=r17.二維數(shù)組A12，10采用先行存儲，每個數(shù)據(jù)元素占用4個存儲空間單位，數(shù)組的第一個地址(A 0，0的地址)是1200，然后是A 6，5的值地址是()。公元1400年至1404年，公元1372年至1460年18.在具有n個節(jié)點的二叉樹中，所有節(jié)點的空子樹的數(shù)量等于()。a . n . b . n-1 c .

4、n 1d . 2n19.如果有如圖1所示的二叉樹，二叉樹的中間順序遍歷序列是()。A.ABCDEFG20.如果有如圖1所示的二叉樹，二叉樹的第一個遍歷序列是()。A.ABCDEFG銀行21.如果有一棵二叉樹，如圖1所示，二叉樹后一個順序的方便順序是()。A.ABCDEFG銀行22.霍夫曼樹中有()個節(jié)點由n個值生成。a . n . b . n . 1 c . 2n d . 2n-123.使用3、6、8和12作為葉結(jié)點的權(quán)重，生成一棵霍夫曼樹，該樹具有權(quán)重路徑長度為()。公元前55年，公元前29年，公元58年24.在有n個頂點的無向圖中，如果有e條邊，那么所有的頂點學(xué)位是()。a . n . b

5、 . e . c . n . D225.在有n個頂點和e條邊的無向圖的鄰接矩陣中，邊是存在的中的元素數(shù)(也稱為有效元素)是()。a . n . b . ne . c . e . d . 2e26.如果圖的邊集是(A，B)(A，C)(B，D)(C，F(xiàn))(D，E)(D，F(xiàn))，則首先從頂點A搜索圖的深度，并且獲得的頂點序列可以是()。A.美國對外經(jīng)濟合作委員會27.如果圖的邊集是(A，B)(A，C)(B，D)(C，F(xiàn))(D，E)(D，F(xiàn))，則首先從頂點A開始搜索圖的寬度，并且獲得的頂點序列可以是()。A.美國廣播公司28.對于順序存儲的有序表(5，12，20，26，37，42，46，50，64)，如

6、果采用二分搜索法，搜索元素26的搜索長度為()。a2 b . 3 c . 4d . 529.如果根據(jù)查找表(23，44，36，48，52，73，64，58)建立線性哈希表，并且哈希地址由h (k)=k計算，則元素64的哈希地址是()。a4 b . 8 c . 12d . 1330.如果根據(jù)查找表(23，44，36，48，52，73，64，58)建立線性哈希表，并且哈希地址由h (k)=k計算，則哈希地址為3的元素的數(shù)量為()。答案是031.如果一個元素序列基本上是有序的，那么選擇()方法會更快。A.直接插入排序簡單選擇排序堆排序快速排序第二，填空1.數(shù)據(jù)的邏輯結(jié)構(gòu)可以分為兩類：_ _ _ _和

7、_ _。線性度；非線性的2.數(shù)據(jù)存儲結(jié)構(gòu)分為四種類型：_ _ _ _ _、_ _ _ _、_ _ _ _和_ _ _ _ _。秩序。鏈條；索引；哈希存儲結(jié)構(gòu)3.數(shù)據(jù)結(jié)構(gòu)的元素集K和它的二元關(guān)系r是：K=a，b，c，d，e，f，g，hR=，那么數(shù)據(jù)結(jié)構(gòu)有一個_ _ _ _ _結(jié)構(gòu)。線性的4.數(shù)據(jù)結(jié)構(gòu)的元素集K和它的二元關(guān)系r是：K=a，b，c，d，e，f，g，hR=，則數(shù)據(jù)結(jié)構(gòu)有_ _ _ _ _結(jié)構(gòu)。非線性的5.線性表的兩種存儲結(jié)構(gòu)是_ _ _ _ _和_ _ _ _ _。秩序。鏈式模式6.當(dāng)刪除單個鏈表中指針P指向的節(jié)點的后繼節(jié)點時，有必要給下一個指針字段賦值_ _ _ _。p-下一個-下一

8、個7.堆棧也稱為_ _ _ _ _表，隊列也稱為_ _ _ _ _表。先進后出；先入先出8.假設(shè)鏈棧的頂部指針是top，每個節(jié)點包含一個值字段數(shù)據(jù)和一個指針字段。當(dāng)P指向的節(jié)點進入堆棧時，首先執(zhí)行_ _ _ _ _操作，然后執(zhí)行_ _ _ _ _操作。p-next=頂部；top=pABCE圖2DGIHF9.隊列在_ _ _ _ _插入，在_ _ _ _ _刪除。團隊尾。賓果游戲10.在二叉樹中，假設(shè)雙分支節(jié)點的數(shù)量是5，單分支節(jié)點的數(shù)量是6，葉節(jié)點的數(shù)量是_ _ _ _。611.對于二叉樹，如果一個節(jié)點及其左子節(jié)點的個數(shù)為1，它的編號是_ _ _ _ _，如果存在正確的子節(jié)點，它的編號是_ _

9、 _ _ _，如果父母已經(jīng)結(jié)婚。如果一個點存在，它的數(shù)目是_ _ _ _。2i；2i 1；i/212.如圖1.9所示，將一個林轉(zhuǎn)換成二叉樹后，該林包含_ _ _ _ _棵樹。313.如果使用3、6、8、12和10作為葉節(jié)點的值來生成霍夫曼樹，則樹的深度為_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 4；8714.數(shù)據(jù)結(jié)構(gòu)的元素集k及其二元關(guān)系r是：K=1，2，3，4，5，6R=(

10、1，2)(2，3)(2，4)(3，4)(3，5)(3，6)(4，5)(4，6)那么數(shù)據(jù)結(jié)構(gòu)就有一個_ _ _ _ _數(shù)據(jù)結(jié)構(gòu)。圖形形狀15.假設(shè)線性表(38，25，74，52，48)被散列，H(K)=K%7被用作散列函數(shù)，并且線性探測和散列方法被用于處理沖突，在建立散列表的過程中將有_ _ _ _ _ _次沖突，并且平均搜索長度是_ _ _ _ _ _ _。5；216.如果一組記錄(46，79，56，38，40，80，35，50，74)被直接插入并排序，當(dāng)將第八條記錄插入到排序的有序表中時，有必要比較_ _ _ _ _次以找到插入位置。4Iii .簡短回答問題1.眾所周知，二叉樹的中間順序遍歷

11、序列是CDBAEGF，第一順序遍歷序列是ABCDEFG。你能唯一地確定一棵二叉樹嗎？如果是，畫二叉樹。給定前序遍歷序列和后序遍歷序列，它能唯一確定嗎？18.(1)二叉樹可以由中間順序遍歷序列和第一順序遍歷序列，或者中間順序遍歷序列和最后順序遍歷序列唯一確定。根據(jù)前序序列，當(dāng)首先訪問根節(jié)點時，可以確定根節(jié)點是A，并且從中間序列，可以確定樹的根節(jié)點是其左和右子樹之間的分離點，使得以A為根的左子樹的節(jié)點是B、C、D，而右子樹的節(jié)點是E、F、G、F、G.重復(fù)得到二叉樹。(2)二叉樹不能由第一遍歷序列和第二遍歷序列唯一確定。因為這兩種遍歷方法只能確定根節(jié)點，而不能區(qū)分左右子樹。2.將圖1.12所示的樹轉(zhuǎn)

12、換成二叉樹。3.試著畫出所有不同形式的三節(jié)點樹和三節(jié)點二叉樹。樹的狀態(tài)如圖1.21所示。三個節(jié)點的二叉樹的狀態(tài)如圖1.22所示4.假設(shè)用于通信的消息由8個字母組成，即A、B、C、D、E、F、G和H，每個字母出現(xiàn)在消息中的概率為5%、25%、4%、7%、9%、12%、30%和8%。嘗試為8個字母設(shè)計霍夫曼編碼5.給出一組關(guān)鍵詞(19，01，26，92，87，11，43，87，21)，進行冒泡排序，列出每次排序后關(guān)鍵詞的排序順序，統(tǒng)計每次排序的關(guān)鍵詞比較次數(shù)。初始關(guān)鍵字序列是：(19，01，26，92，87，11，43，87，21)第一次排序和比較是8次，經(jīng)過6次交換，變成：(01，19，26，8

13、7，11，43，87，21，92)第二次排序和比較是7次，經(jīng)過3次交換，變成：(01，19，26，11，43，87，21，87，92)第三次，排序比較6次，交換2次后，變成：(01，19，11，26，43，21，87，87，92)第四次排序和比較是5次，交換2次后，變成：(01，11，19，26，21，43，87，87，92)第五次排序比較是4次，交換一次后變成：(01，11，19，21，26，43，87，87，92)在第六次中，排序被比較3次并被交換0次。訂購?fù)瓿伞?.知道按順序存儲的有序表是(15，26，34，39，45，56，58，63，74，6)，嘗試畫出相應(yīng)的二分搜索法決策樹并找到其平均搜索長度。二分搜索法決策樹如圖1.31所示。平均搜索長度：ASL=(1 22 34 43)/10=2.97.有一組關(guān)鍵字(17，13，14，153，29，35)要插入到長度為12的哈希表中。請回答以下問題：(1)設(shè)計一