數(shù)據(jù)結構 綜合練習題 打印

1、數(shù)據(jù)結構綜合練習題精品文檔6填空題1.數(shù)據(jù)結構包含三個方面的內(nèi)容，分別是 數(shù)據(jù)的邏輯結構、數(shù)據(jù)的存儲結構和數(shù)據(jù)的運算。2.實現(xiàn)數(shù)據(jù)結構的四種存儲方法有順序存儲方法、鏈接存儲方法、索引存儲方法和散列存儲方法。3.4.一種抽象數(shù)據(jù)類型包括抽象數(shù)據(jù)的組織和與之相關的操作兩個部分。5.算法的五個重要特性是輸入、輸出、確定性、可行性和有窮性。6.棧頂?shù)奈恢檬请S 進棧和出棧 操作而變化的。7.在鏈隊列只有一個元素的情況下， 對其做刪除操作時,應當把 對頭指針和 隊尾指針都置為null。數(shù)據(jù)結構的邏輯結構有 線性結構 和 非線性結構 兩大類。8.9.回答下列問題。11.有一棵樹如下圖所示，回答下列問題。10

2、.有一棵樹如下圖所示,(1)這棵樹的根結點是K12(1)結點k3的度是(2)這棵樹的葉子結點是K2，K4，K5，K7(2)這棵樹的度為操作系統(tǒng)中先來先服務是數(shù)據(jù)結構中的 隊列 應用的典型例子。在解決計算機主機與打印機之間速度不匹配問題時，通常設置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機從該緩沖區(qū)中取出數(shù)據(jù)打印。該緩沖區(qū)應該是一個 隊列 結 構。12. 有一棵樹如下圖所示，回答下列問題。13有一棵樹如下圖所示，回答下列問題。14.在一棵二叉樹中，度為零的結點個數(shù)為(1) 結點K3的子女是K5，K6 ；(2) 結點K3的雙親結點是n0 ,度為2的結點的個數(shù)為n2 ,則有n0

3、= n2+1。n_，其深度最小是Iog2(n+1)或log 2 n中1。K1 。15. n( n0 )個結點的二叉樹高度最大是16. n(n0)個結點的滿二叉樹深度是Iog2(n+1)，葉子結點數(shù)是(n+1)/2。阿17. 下面二叉樹的中序序列是 GDHABC 。的結點共218.n19.n(n0 )個結點的哈夫曼樹中度為個頂點的有向圖最多有n*(n-1)(n-1)/2個，葉子結點共(n+1)/2個。條邊。2O.n(n0 )個頂點的連通無向圖各頂點度之和最少是2(n-1)。21. 有6個頂點的無向圖至少應有 5條邊才能確保是一個連通圖。22. n(n0)個頂點的連通無向圖至少有n-1 條邊。23

4、. 恰有n( n-1)條邊的有向圖稱為有向完全圖。1.單項選擇題下列說法正確的是（B ）A.B.C.D.數(shù)據(jù)元素是具有獨立意義的最小標識單位原子類型的值不可再分解原子類型的值由若干個數(shù)據(jù)段組成結構類型的值不可再分解2.3.4.5.6.一個存儲結點存放一個（B ）A.數(shù)據(jù)項B.數(shù)據(jù)元素C.數(shù)據(jù)結構D.數(shù)據(jù)類型在數(shù)據(jù)結構中，從邏輯上可以把數(shù)據(jù)結構分成（ C）A.動態(tài)結構和靜態(tài)結構B.緊湊結構和非緊湊結構C.線性結構和非線性結構D.內(nèi)部結構和外部結構線性結構是數(shù)據(jù)元素之間存在一種（D ）A. 一對多關系B.多對多關系算法分析的目的是（B ）A.正確性和簡明性C.可讀性和文檔性算法必須具備輸入輸出和（

5、D.對一關系B.時間復雜性和空間復雜性D.數(shù)據(jù)復雜性和程序復雜性7.CA.計算方法B.排序方法線性表中正確的說法是（D ）C.解決問題的有限運算步驟D.程序設計方法8.A.B.C.每個元素都有一個直接前驅和一個直接后繼線性表至少要求一個元素表中的元素必須按由小到大或由大到小排序除了第一個和最后一個元素外，其余每個元素都有且僅有一個直接前驅和一個直接后繼D.線性表是具有n個（C ）的有限序列9.A.整數(shù)B.字符C.數(shù)據(jù)元素D.數(shù)據(jù)項線性表采用鏈式存儲結構時，結點的存儲地址（ C）A. 必須是不連續(xù)的B.必須是連續(xù)的C是否連續(xù)都可以D.和頭結點的存儲地址相連續(xù)10. 在帶有頭結點的單鏈表中插入一個

6、新結點時不可能修改（ A）A. 頭指針B.頭結點指針域C.開始結點指針域D其它結點指針域11. 相對于順序存儲結構而言，鏈接存儲的優(yōu)點是（ C ）A.隨機存取B.節(jié)約空間C.增、刪操作方便D.結點關系簡單12. 設線性表有n個元素，下面算法中在順序表上實現(xiàn)比在鏈表上實現(xiàn)效率更高的是（A. 輸出第i （1蘭iv環(huán)）個元素值B. 交換第0個元素與第1個元素的值C. 順序輸出這n個元素的值D. 輸出與給定值x相等的元素在線性表中的序號13. 下列說法正確的是（A）A.B.C.D.棧是一種線性表棧具有先進先出特性棧刪除運算會引起其它元素的移動棧插入運算會引起其它元素的移動14. 一個棧的入棧序列是：a

7、,b,c,d,e, 則棧的不可能的輸出序列是（ C ）C.dceab D.abcdeA. Edcba B.decba15. 一個鏈棧的棧頂指針是 topNode ,則執(zhí)行出棧操作時（棧非空）,用topElement保存被刪除結點的數(shù)據(jù)元素，則執(zhí)行（D ）A.B.C.D.top Eleme nt = top; top = topN ode .n ext;top Eleme nt = topN ode.eleme nt;topN ode = topN ode .n ext; top Eleme nt = topN ode.eleme nt; top Eleme nt = topN ode.elem

8、e nt; topN ode = topN ode .n ext;16.17.一個隊列的入隊序列是a,b,c,d,則隊列的輸出序列是（B ）A. d,c,b,a B.a,b,c,d C.a,d,c,b D.c,b,a,d將遞歸過程轉化為非遞歸過程需要用到（A ）18.A.棧 B.隊列C.樹D.圖棧和隊列的共同點是（C）19.A.都是先進后出B.都是先進先出C.只允許在端點處插入和刪除元素D.沒有共同點樹最適合用來表示（D ）A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間無聯(lián)系的數(shù)據(jù)D.元素之間具有分支層次關系的數(shù)據(jù)20. 一棵深度為9的滿二叉樹的葉結點數(shù)是（ B ）A. 255B.256C.51

9、1D.51221. n個結點的滿二叉樹的高度是（ B ）A.n/2B.log2（n+1） c.lg2（nT） D.log2 n22. 按照二叉樹的定義，具有 3個結點的二叉樹有（ C ）種A. 3B.4C.5D.623. 深度為5的二叉樹至多有（C ）個結點A. 16B32C.31D.1024. 由結點 A、B、C構成不同的二叉樹共（ D）棵A. 6B.18C.36D.30下列說法正確的是（D ）A. 二叉樹是度為2的無序樹B.二叉樹中結點只有一個孩子時無左右之分C.二叉樹中必有度為2的結點D.二叉樹中的一個結點最多只有兩棵子樹，并且有左右之分一棵二叉樹的先序序列是 ABCDEF，它可能的中序

10、序列是（A）25.26.27.28.A. CBDAFE B.CABDEF C.DABCEF D.FCABED要唯一地確定一棵二叉樹，只需要知道該二叉樹的（C ）A.前序序列B.中序序列C.中序和后序序列D.前序和后序序列任何一棵二叉樹的葉結點在先序、中序和后序遍歷中的相對次序（ A ）29.A.不發(fā)生改變B.發(fā)生改變C.不能確定D.以上都不對在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（B ）倍30.A. 1/2B.1C.2D.4用鄰接矩陣存儲圖所需的存儲空間大小僅與（A ）有關D.圖的各頂點度之和31.32.33.A.圖的頂點數(shù) B.圖的邊數(shù)C.圖的頂點數(shù)與邊數(shù)之和若存儲圖G的

11、鄰接矩陣是對稱矩陣，則 G （ C ）A. 一定是無向圖B.一定是連通無向圖下列說法正確的是（B ）A.有向圖的鄰接矩陣一定是非對稱矩陣B.無向圖的鄰接矩陣一定是對稱矩陣C.若圖G的鄰接矩陣是對稱的，則 G 一定是無向圖D.有向圖的鄰接矩陣一定是下三角矩陣已知一個圖如下所示。若從頂點 a出發(fā)按深度優(yōu)先搜索算法進行遍歷，則可能得到的一種頂點序C.可能是無向圖D. 一定是有向圖列為（D ）A.abecdfB. acfebdC. aebfcdD. aedfcb精品文檔83.解答題1. 簡述數(shù)據(jù)結構的邏輯結構和存儲結構的區(qū)別和聯(lián)系。它們?nèi)绾斡绊懰惴ǖ脑O計與實現(xiàn)?若用結點表示某個數(shù)據(jù)元素，則結點和結點之

12、間的邏輯關系就稱為數(shù)據(jù)的邏輯結構。數(shù)據(jù)在計算機中 的存儲表示稱為數(shù)據(jù)的存儲結構。可見，數(shù)據(jù)的邏輯結構是反映數(shù)據(jù)之間的固有聯(lián)系，而數(shù)據(jù)的存儲 結構是數(shù)據(jù)在計算機中的存儲表示。盡管因采用的存儲結構不同，邏輯上相鄰的結點，其物理地址未 必相鄰，但可通過結點的內(nèi)部信息，找到其相鄰的結點，從而保留了邏輯結構的特點。由于采用的存 儲結構不同，該數(shù)據(jù)結構上的操作靈活性、算法復雜度等區(qū)別較大。2. 簡述數(shù)據(jù)的運算與數(shù)據(jù)邏輯結構和存儲結構之間的關系。數(shù)據(jù)的運算定義在邏輯結構上，也就是說，一旦數(shù)據(jù)的邏輯結構確定了，就可以定義在這種邏輯結構 上可以進行何種運算了。但是，數(shù)據(jù)的運算的具體實現(xiàn)時依賴于數(shù)據(jù)的存儲結構的。

13、同樣的邏輯結構,可能有不同的存儲結構。那么，在不同的存儲結構上實現(xiàn)同一個數(shù)據(jù)運算的方法也不一樣。所以，要 具體實現(xiàn)某個運算，還要根據(jù)數(shù)據(jù)的存儲結構來定。3. 試舉一個應用數(shù)據(jù)結構的例子，敘述其邏輯結構、存儲結構、運算這三方面的內(nèi)容。要點：說明邏輯結構、存儲結構的概念，同時用自然語言例子中的邏輯結構和存儲結構和運算的基本 規(guī)則4. 何時選用順序表、何時選用鏈表作為線性表的存儲結構為宜?（1）基于空間的考慮：當線性表的長度變化較大，難以估計其存儲規(guī)模時，采用動態(tài)鏈表作為存儲 結構為好。當線性表的長度變化不大，易于事先確定其大小時，為了節(jié)省存儲空間，采用順序表為好。（2）基于時間的考慮：若線性表的操

14、作主要是進行查找，很少做插入和刪除操作時，采用順序表做 存儲結構為好。反之，對于頻繁進行插入和刪除的線性表，采用鏈表為好。b/C5. 設二叉樹如下所示，試采用順序存儲方法和鏈接存儲方法畫出它的存儲結構。d O.I c I Al順序存儲結構如下:4ab00c0000d鏈式存儲結構如下:精品文檔226. 設二叉樹如下所示，試采用順序存儲方法和鏈式存儲方法畫出它的存儲結構。7. 設樹形結構如下，請畫出該樹的雙親孩子鏈表表示。解:A-1B0AC0D2AE2AF2A012345*rn8.現(xiàn)有權值：個哈夫曼(Huvvman ) 樹。527，16，5，28，2。試構造這組權值的哈夫曼( Huvvman )樹

15、。用樹形表示法畫出這9.以下面數(shù)據(jù)作為葉子結點的權值構造一棵哈夫曼(Huvvman )樹。用樹形表示法畫出這個哈夫曼(Huvvma n )樹。10.設圖 G= (V, E), V= vO , v1 , v2 , v3 , v4 , E= , , , , = 1) & (give nPo sition = result = entry givenPosition - 1;if (givenPosition length ) removeGa p( give nPo sition);length -;return result;privatevoid removeGap( int givenPos

16、ition) for (int index = givenPosition; index = 1) & (new Position = newPosition; index-) entry index = entry index - 1;3.設單鏈表結點類型和單鏈表類型定義如下:Public class ChainNode Object element ; / 結點的數(shù)據(jù)域 ChainNode next ; /結點的鏈接域 ChainNode(Object element) this .element = element;ChainNode(Object element, ChainNode next) this this.element = element;.next = next; publicChain impiementsListInterface ChainNode firstNode ; /指向鏈表第1個結點的引用 int length ; /鏈表中元素個數(shù)classprivateprivatepublic Chain() /初始時鏈表為空 firstNode = null ;length = 0;請寫出返回鏈表中指定位置的結點的引用的算法。/* Task:返回鏈表中指定位