數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題及答案

1、1數(shù)據(jù)結(jié)構(gòu)習(xí)題數(shù)據(jù)結(jié)構(gòu)習(xí)題一、一、名詞解釋名詞解釋1.數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)物理結(jié)構(gòu)、順序存儲、鏈?zhǔn)酱鎯?、算法、時間復(fù)雜度、空間復(fù)雜度。2.線性表、順序表、單鏈表、雙向鏈表、循環(huán)鏈表、雙向循環(huán)鏈表、三個概念的區(qū)別：頭指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn)(第1個元素結(jié)點(diǎn))。3.棧（順序棧、鏈棧）、隊(duì)列（順序隊(duì)、鏈隊(duì)）、循環(huán)隊(duì)列、遞歸、稀疏矩陣、三元組。4.樹、葉子結(jié)點(diǎn)、結(jié)點(diǎn)的度、樹的度、樹的高(深)度、二叉樹、遍歷、滿二

2、叉樹、完全二叉樹、哈夫曼樹、WPL、哈夫曼編碼。5.圖（有向、無向）、網(wǎng)、邊、弧、度、入度、出度、完全圖（有向、無向）、（強(qiáng)）連通圖（分量）、（最?。┥蓸洹⑧徑泳仃?、鄰接表、DFS、BFS。6.查找表、關(guān)鍵字、靜態(tài)查找、動態(tài)查找、ASL、順序查找、折半查找、分塊查找、二叉排序樹。7、排序、內(nèi)（外）排序、穩(wěn)定性、插入（直接、希爾），交換（起泡、快速），選擇（直接、堆），2路歸并。一、一、填空題填空題1.數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的_邏輯結(jié)構(gòu)__

3、和___物理結(jié)構(gòu)__，并在這種結(jié)構(gòu)上定義相關(guān)的運(yùn)算，設(shè)計(jì)實(shí)現(xiàn)這些運(yùn)算的算法，分析算法的效率。算法的效率包括時間和空間兩個方面，分別稱為___時間復(fù)雜度____和__空間復(fù)雜度___。2.數(shù)據(jù)的基本單位是__數(shù)據(jù)元素__，數(shù)據(jù)的最小單位是__數(shù)據(jù)項(xiàng)_。3.算法是對特定問題求解___步驟___的一種描述，是指令的有限序列。4.一個算法的時間復(fù)雜度為(3n32n—7)，其數(shù)量級表示為O（n3）_。5.一個算法具有5個特性：確定性、可行性、有窮

4、性、輸入和輸出。6.算法性能的分析和度量，可以從算法的時間復(fù)雜度和空間復(fù)雜度來評價算法的優(yōu)劣。7.數(shù)據(jù)的邏輯結(jié)構(gòu)包括集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖型結(jié)構(gòu)四種類型。8.數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為數(shù)據(jù)的物理結(jié)構(gòu)，它可以采用__順序存儲___或__鏈?zhǔn)酱鎯兩種存儲方法。9.線性表有兩種存儲結(jié)構(gòu)，分別為順序存儲和鏈?zhǔn)酱鎯Α?0.鏈?zhǔn)酱鎯Φ奶攸c(diǎn)是利用指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系。11.若頻繁地對線性表進(jìn)行插入和刪除操作，該線性表宜采用_

5、鏈?zhǔn)酱鎯_存儲結(jié)構(gòu)。12.線性表中的數(shù)據(jù)元素之間具有一對一的線性關(guān)系，除第一個和最后一個元素外，其他數(shù)據(jù)元素有且只有一個直接后繼和直接前趨。13.在一個單鏈表中p所指結(jié)點(diǎn)之后插入一個s所指結(jié)點(diǎn)時，應(yīng)執(zhí)行snext=__pnext______和pnext=__s______的操作。14.在一個單鏈表中刪除p的后繼結(jié)點(diǎn)q時，應(yīng)執(zhí)行以下操作pnext=qnext。15.對帶頭結(jié)點(diǎn)head的單鏈表，則判斷其為空的條件為headnext=NUL

6、L。學(xué)號姓名學(xué)號339.若深度為6的完全二叉樹的第6層有3個葉結(jié)點(diǎn)，則該二叉樹一共有34個結(jié)點(diǎn)。40.深度為15的滿二叉樹上，第11層有_2^(111)=1024個結(jié)點(diǎn)。41.一棵具有100個結(jié)點(diǎn)的完全二叉樹，它的深度為7，其中度為1的結(jié)點(diǎn)有1個。42.某二叉樹的后根遍歷序列為abd，中根遍歷序列為adb，則它的先根遍歷序列為dab。43.哈夫曼樹是指對于一組帶有確定權(quán)值的葉子結(jié)點(diǎn)構(gòu)造的具有最小帶權(quán)路徑長度的二叉樹。44.具有m個葉子結(jié)

7、點(diǎn)的哈夫曼樹共有2m1個結(jié)點(diǎn)。45.已知一棵哈夫曼樹含有60個葉子結(jié)點(diǎn)，則該樹中共有59個非葉子結(jié)點(diǎn)。46.在一個具有n個頂點(diǎn)無向完全圖中，含有n(n1)2邊；在一個具有n個頂點(diǎn)有向完全圖中，含有n(n1)邊。一個具有4個頂點(diǎn)的無向完全圖有6條邊。47.具有n個頂點(diǎn)的連通圖至少需有n1條邊。48.一個連通圖的生成樹是該圖的極小連通子圖。若這個連通圖有n個頂點(diǎn)，則它的生成樹有n1條邊。49.在有向圖的鄰接矩陣中，第i行中非零元素的個數(shù)正好

8、是第i個頂點(diǎn)的出度；第i列中非零元素的個數(shù)正好是第i個頂點(diǎn)的入度。50.在一個圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的2倍。51.在無向圖G的鄰接矩陣A中，若A［i］［j］等于1，則A［j］［i］等于1。52.對二叉排序樹進(jìn)行中序遍歷，可以得到按關(guān)鍵字從小到大排列的結(jié)點(diǎn)序列。53.一個有序表為1，3，9，12，32，41，45，62，75，77，82，95，100，當(dāng)折半查找值為82的結(jié)點(diǎn)時，經(jīng)過4次比較后查找成功。54.在線性表中采用折

9、半查找法查找一個數(shù)據(jù)元素，線性表中元素應(yīng)該按值有序，并且采用___順序存儲__存儲方法。55.在簡單選擇排序、堆排序、快速排列、歸并排序四種排序方法中，排序方法穩(wěn)定的是__歸并排序。56.冒泡排序是一種穩(wěn)定的排序方法，對n個元素的序列進(jìn)行冒泡排序時，最多需進(jìn)行n1趟。該排序方法的時間復(fù)雜度為O(n2)。57.給定序列100，86，48，73，35，39，42，57，66，21，按堆的定義，則它一定大根堆。58.數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之