數(shù)據(jù)結(jié)構(gòu) 綜合練習(xí)題 打印

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

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

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

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

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

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

7、,b,c,d,e, 則棧的不可能的輸出序列是（ C ）C.dceab D.abcdeA. Edcba B.decba15. 一個鏈棧的棧頂指針是 topNode ,則執(zhí)行出棧操作時（棧非空）,用topElement保存被刪除結(jié)點的數(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將遞歸過程轉(zhuǎn)化為非遞歸過程需要用到（A ）18.A.棧 B.隊列C.樹D.圖棧和隊列的共同點是（C）19.A.都是先進(jìn)后出B.都是先進(jìn)先出C.只允許在端點處插入和刪除元素D.沒有共同點樹最適合用來表示（D ）A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間無聯(lián)系的數(shù)據(jù)D.元素之間具有分支層次關(guān)系的數(shù)據(jù)20. 一棵深度為9的滿二叉樹的葉結(jié)點數(shù)是（ B ）A. 255B.256C.51

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

10、序列是（A）25.26.27.28.A. CBDAFE B.CABDEF C.DABCEF D.FCABED要唯一地確定一棵二叉樹，只需要知道該二叉樹的（C ）A.前序序列B.中序序列C.中序和后序序列D.前序和后序序列任何一棵二叉樹的葉結(jié)點在先序、中序和后序遍歷中的相對次序（ A ）29.A.不發(fā)生改變B.發(fā)生改變C.不能確定D.以上都不對在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（B ）倍30.A. 1/2B.1C.2D.4用鄰接矩陣存儲圖所需的存儲空間大小僅與（A ）有關(guān)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)先搜索算法進(jìn)行遍歷，則可能得到的一種頂點序C.可能是無向圖D. 一定是有向圖列為（D ）A.abecdfB. acfebdC. aebfcdD. aedfcb精品文檔83.解答題1. 簡述數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的區(qū)別和聯(lián)系。它們?nèi)绾斡绊懰惴ǖ脑O(shè)計與實現(xiàn)?若用結(jié)點表示某個數(shù)據(jù)元素，則結(jié)點和結(jié)點之

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

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

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

15、。用樹形表示法畫出這9.以下面數(shù)據(jù)作為葉子結(jié)點的權(quán)值構(gòu)造一棵哈夫曼(Huvvman )樹。用樹形表示法畫出這個哈夫曼(Huvvma n )樹。10.設(shè)圖 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.設(shè)單鏈表結(jié)點類型和單鏈表類型定義如下:Public class ChainNode Object element ; / 結(jié)點的數(shù)據(jù)域 ChainNode next ; /結(jié)點的鏈接域 ChainNode(Object element) this .element = element;ChainNode(Object element, ChainNode next) this this.element = element;.next = next; publicChain impiementsListInterface ChainNode firstNode ; /指向鏈表第1個結(jié)點的引用 int length ; /鏈表中元素個數(shù)classprivateprivatepublic Chain() /初始時鏈表為空 firstNode = null ;length = 0;請寫出返回鏈表中指定位置的結(jié)點的引用的算法。/* Task:返回鏈表中指定位