數(shù)據(jù)結構(期末復習題目

1、一是非題（線性結構 ）線性表的鏈式存儲結構具有可直接存取表中任一元素的優(yōu)點。線性表的順序存儲結構優(yōu)于鏈式存儲結構。6.在單鏈表 P 指針所指結點之后插入 S 結點的操作是：8.1011.12.P-next= S ; S- next = P-next;對于插入、刪除而言，線性表的鏈式存儲優(yōu)于順序存儲。順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。線性表的順序存儲結構具有可直接存取表中任一元素的優(yōu)點。棧和隊列是操作上受限制的線性表。隊列是與線性表完全不同的一種數(shù)據(jù)結構。13.隊列是一種操作受限的線性表，凡對數(shù)據(jù)元素的操作僅限一端進行。15.棧是限定僅在表頭進行插入和表尾進行刪除運算的線性

2、表。16隊列是一種運算受限的線性表（樹形結構 ）1.二叉樹中每個結點有兩個子結點，而對一般的樹，則無此限制，所以，二叉樹是樹的特殊情形。2.二叉樹是一棵結點的度最大為二的樹。3.赫夫曼樹中結點個數(shù)一定是奇數(shù)。5.假設B是一棵樹，B 是對應的二叉樹。則B的后根遍歷相當于的后序遍歷 。錯6.通常，二叉樹的第 i 層上有 2i-1 個結點。7.中序線索二叉樹的優(yōu)點是便于在中序下查找直接前驅結點和直接后繼結點。二叉樹的先序遍歷序列中，任意一個結點均處在其孩子結點的前面。（圖形結構 ）鄰接多重表可以用以表示無向圖，也可用以表示有向圖?？蓮娜我庥邢驁D中得到關于所有頂點的拓撲次序。6.一個無向圖的連通分量是

3、其極大的連通子圖。7.連通圖的生成樹是一個包含圖 G 所有 n 個頂點和任意n-1條邊的子圖。9.鄰接表可以表示有向圖，也可以表示無向圖。（查找）1.二叉排序樹的平均查找長度為O(log n )。2.二叉排序樹的最大查找長度與（ LOG 2N ）同階。選用好的 HASH 函數(shù)可避免沖突。折半查找不適用于有序鏈表的查找。一般來說，折半查找不適用于有序鏈表的查找。二叉排序樹的查找和折半查找的時間性能相同。排序）1. 對于目前所知的排序方法，快速排序具有最好的平均性能。2 對于任何待排序序列來說，快速排序均快于冒泡排序。錯3 在最壞情況下，堆排序的時間性能是 O（nlogn）, 比快速排序好 對選擇

4、題。1-19 是線性、樹形、圖形結構， 20-29 是查找和排序）從邏輯上可以把數(shù)據(jù)結構分成A. 動態(tài)結構和靜態(tài)結構B. 順序組織和鏈接組織C. 線性結構和非線性結構D. 基本類型和組合類型線性表L在（B ）情況下適于使用鏈表結構實現(xiàn)。A.不需修改L的結構B.需不斷對L進行刪除、插入C.需經(jīng)常修改L中結點值D. L中含有大量結點若入棧順序為A、B、C、E,則下列（D ）出棧序列是不可能的。C. C、D、B、E、AD. D、E、C、A、B遞歸程序可借助于（C）轉化為非遞歸程序。a.線性表b.隊列C：棧d.數(shù)組在下列數(shù)據(jù)結構中（C）具有先進先出（FIFO）特性,（ B ）具有先進后出（FILO ）

5、特性。a .線性表b .棧C .隊列d .廣義表6、若對編號為1 , 2 , 3的列車車廂依次通過扳道棧進行調度，不能得到（e ）的序列。a:1,2,3b:1,3,2c:2,1,3d:2,3,1e:3,1,2f：3217, 19, 22, 6,7、假設用于通訊的電文僅由6個字符組成，字母在電文中出現(xiàn)的頻率分別為32, 14。若為這6個字母設計哈夫曼編碼（設生成新的二叉樹的規(guī)則是按給出的次序g),從左至右的結合，新生成的二叉樹總是插入在最右），則頻率為7的字符編碼是（頻率為32的字符編碼是（c ) O23006000ABCDEFGH05408700BT的存儲結構如下：1其中Ichild ，rch

6、ild分別為結點的左、右孩子指針域,lchild data rchild2345678a: 00e: 011b: 01f: 110C： 10d: 118、對二叉排序樹a:按層遍歷b:前序遍歷g: 1110h:1111可得到有序序列。c:中序遍歷d:后序遍歷9、設一棵二叉樹data為結點的數(shù)據(jù)域。則該二叉樹的高度為（D ）;B. 3C. 4D. 510、在有n個結點的二叉樹的二叉鏈表表示中，空指針數(shù)B )oa.不定b. n+1c.nd.n-111、若某二叉樹有 20個葉子結點，有 20個結點僅有一個孩子，則該二叉樹的總結點數(shù)是A . 40B. 55C. 59D. 6112、已知某二叉樹的先序遍歷

7、次序為abcdefg中序遍歷次序為badcgfe ,第3層有（ A ）個結點（根結點為第 1層）。則該二叉樹的后序遍歷次序為（C ）。層次遍歷次序為（a ）。a: abcdefgb: cdebgfac: bdgfecad: edcgfba13、.圖示的三棵二叉樹中（C）為最優(yōu)二叉樹。B) Oq/2714、對一棵完全二叉樹進行層序編號。則編號為n的結點若存在右孩子,其位序是（d）。編號為n的結點若存在雙親，其位置是（a)。a: n/2b: 2nc:2 n-1d:2 n+1e:nf: 2( n+1)15、設森林F中有三棵樹，第一、第二和第三棵樹的結點個數(shù)分別為m1、m2 和 m3，則與森林F對應的

8、二叉樹根結點的右子樹上的結點個數(shù)是Ld。A. m1B. m1+m2C. m3D. m2+m316、下列二叉樹中,a）可用于實現(xiàn)符號不等長高效編碼。a:最優(yōu)二叉樹b:次優(yōu)查找樹C：二叉平衡樹？?d:二叉排序樹17、設無向圖G = （V,E）和G = （V E ），若G是G的生成樹，則下面不正確的說法是（bA. G是G的子圖B. G是G的連通分量C. G是G的無環(huán)子圖D. G是G的極小連通子圖且V = V18、任何一個連通圖的最小生成樹(b)。A .只有一棵B.有一棵或多棵C.定有多棵D.可能不存在19、已知某無向圖的鄰接表如下所示;(19 )是其原圖。E0a1b2c3d4e5f35A. aEnK

9、ZEkr0D. aE. aF. a(20 )是按該鄰接表遍歷所得深度優(yōu)先生成樹。(21 )是按該鄰接表遍歷所得廣度優(yōu)先生成樹。cdcdbB. abdeeC. a bef20、下列查找方法中(a )適用于查找單鏈表。A)順序查找B)折半查找C)分塊查找D)hash查找21、哈希表的查找效率取決于( da:哈希函數(shù)b:處理沖突的方法。C：哈希表的裝填因子。d:以上都是22、在Hash函數(shù)H(k)=k MOD m 中，一般來說， m應取( C )。A.奇數(shù)B.偶數(shù)C.素數(shù)D.充分大的數(shù)23、在順序表查找中，為避免查找過程中每一步都檢測整個表是否查找完畢，可采用方法。AA.設置監(jiān)視哨B.鏈表存貯 C.

10、二分查找D.快速查找24、靜態(tài)查找表和動態(tài)查找表的區(qū)別在于（A.前者是順序存儲，而后者是鏈式存儲B.前者只能進行查找操作，而后者可進行查找、插入和刪除操作C.前者只能順序查找，而后者只能折半查找D.前者可被排序，而后者不能被排序25、根據(jù)插入次序（80，90，100,110，85，70，75，60，72 ）建立二叉排序樹。圖（a是最終變化的結果。8070/6075/7290八10011085/72a:9075/708060 啤 72110c:8526、若有序表中關鍵字序列為:8060709085、100 110b:9014，20，/ 75/60d:25，32，34，7211045，57，69，

11、77，83，92。對其進行折半查找，則在等概率情況下，查找成功時的平均查找長度是（3。查找322、線性表的順序存儲結構是以物理存儲地址來表示數(shù)據(jù)元素之間的邏輯關系時需進行(C )次比較。A. 1B. 2C. 3D. 427、已知哈希表地址空間為A0.8，哈希函數(shù)為H(k)=k mod 7，采用線性探測再散列處理沖突。若依次將數(shù)據(jù)序列：76,45,88,21,94,77,17存入該散列表中，則元素 17存儲的下標為(h );在等概率情況下查找成功的平均查找長度為(A. 0E. 4B. 1F. 5C. 2G. 6D. 3H. 728、若從二叉樹的根結點到其它任一結點的路徑上所經(jīng)過的結點序列按其關鍵

12、字遞增有序,則該二叉樹是(C )。A.二叉排序樹B.赫夫曼樹C.堆D.平衡二叉樹29、已知一組待排序的記錄關鍵字初始排列如下:56,26,86,35,75,19,77,58,48,42下列選擇中( D )是快速排序一趟排序的結果。(B )是歸并排序一趟排序的結果。( A )是初始堆(大堆頂)86,75,77,58,42,19,56,35,48,26.26,56,35,86, 19, 75, 58, 77, 42, 48.35,26,19,42,58,48,56,75,86,77.42,26,48,35,19,56,77,58,75,86.三.填空題(1-13是線性、樹形、圖形結構， 14-15

13、是查找和排序)的。3、遞歸過程可借助于數(shù)據(jù)結構（ 棧）改寫成非遞歸過程。4、設循環(huán)隊列存于一維數(shù)組Qm中，尾指針rear指示隊尾元素在隊列中的當前位置,頭指針front指示隊列中隊頭元素的前一個位置，則隊列長度=（rear-fro nt+m ) %m )。5、在二叉樹的第i層上至少有個結點，至多有2 個結點，深度為k的二叉樹至多有2k_-1個結點.6、對樹的遍歷有先序遍歷樹和后序遍歷樹。若以二叉鏈表作樹的存儲結構則樹的先序遍歷可借用二叉樹的先序.遍歷算法來實現(xiàn)，而樹的后序遍歷可借用二叉樹的中序遍歷算法來實現(xiàn)。7、設森林F中有三棵樹，第一、第二和第三棵樹的結點個數(shù)分別為m1、m2 和 m3 ,則

14、與森林F對應的二叉樹根結點的左子樹上的結點個數(shù)是（m1-1),右子樹上的結點個數(shù)是（m2+m38、若某二叉樹有no個葉子結點，有ni個結點僅有一個孩子，則該二叉樹的總結點數(shù)是 （2no + n 1-1 )。9、如果對完全二叉樹中結點從 1開始按層進行編號，設最大編號為n；那么，可以斷定編號為i (i1)的結點的父結點編號為（i/2）;所有編號（n/2 ）的結點為葉子結點。10、若某二叉樹中，有 20個結點沒有孩子，有 20個結點僅有一個孩子，則該二叉樹的總結點數(shù)是5911、n個頂點的連通圖至少有n-1條邊，至多有n（n-1）/2條邊。12、對于圖的存儲結構有（鄰接表鄰接矩陣）等方法。13、在一

15、個無向圖的鄰接表中,若表結點的個數(shù)是 m,則圖中邊的條數(shù)是m/2條。14、若有序表中關鍵字序列為:12，22，33，44，55，66，77，88，99，100，101 對其進行折半查找，則在等概率情況下，查找成功時的平均查找長度是（3 ）。查找99時需進行（2 ）次比較。15、用中序遍歷對二叉排序樹進行訪問可得到有序序列。已知Hash函數(shù)為 H ( K)=K mod 13，散列地址為0 -14，用二次探測再散列處理沖突，關鍵字（23，34，56，24，75，12，49, 52，36，92)的分布如圖，則平均成功的查找長度為（52369256 1342324751 124978910111213140123456圖示結構題(1-4是線性、樹形、圖形結構，5-6是查找排序)1. 已知在電文中只出現(xiàn)頻率為(5,26,7,23,20,19)的6個字符,畫出你建的哈夫曼樹，并給出其哈夫曼編碼。和 BDACFEG2. 已知某二叉樹的后序遍歷和中序遍歷次序分別為DBFGECA請畫出該二叉樹。3將圖示森林轉換為二叉樹，并對該二叉樹先序遍歷。入八131415161718194某二叉樹的結點數(shù)據(jù)采用順序存儲表示如下：0123456789101112ABC 1DEFGH1I(1 )試畫出此二叉樹的圖形表示。(2)將此二叉樹看作森林的二叉樹