《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)卷

1、數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)卷一、填空題1、組成數(shù)據(jù)的基本單位是 數(shù)據(jù)元素 ，最小單位是 數(shù)據(jù)項 。2、算法的五個重要特性是 有窮性 、 確定性 、 可行性 、 1個或多個輸出 、 0個或多個輸入 。3、數(shù)據(jù)的存儲結(jié)構(gòu)主要分為 順序存儲結(jié)構(gòu) 和 鏈?zhǔn)酱鎯Y(jié)構(gòu) 兩種。4、下面程序段的時間復(fù)雜度是 n*m 。for(i=0;i<n;i+) for(j=0;j<m;j+) Aij=0;5、棧的特點是 先進后出 ，隊列的特點是 先進先出 ，棧和隊列都屬于 線性 結(jié)構(gòu)。6、圖定義為：G=(V，E)，其中，V是_頂點的有窮非空 的集合，E是 頂點間關(guān)系的有窮 的集合。k1k2k3k4k5k6k77、有一棵樹如

2、圖所示，請回答以下問題：（1）這棵樹的根結(jié)點是_ K1_；（2）這棵樹的葉子結(jié)點是_ K2 K5 K7 K4_；（3）這棵樹的深度是_4_；8、二叉樹的三種遍歷方法分別為 先根遍歷 、 中根遍歷 、 后根遍歷 。 9、圖的遍歷方法_深度優(yōu)先搜索遍歷_和_廣度優(yōu)先搜索遍歷_。10、按照排序過程中存儲器的不同，可將排序分為 內(nèi)部排序 和 外部排序 。11、算法的復(fù)雜度分為 時間復(fù)雜度 、 空間復(fù)雜度 兩種。12、算法的五個重要特性是1個或多個輸出 、 0個或多個輸入 、有窮性、 確定性 、 可行性 。13、數(shù)據(jù)的存儲結(jié)構(gòu)主要分為 邏輯存儲結(jié)構(gòu) 和 物理存儲結(jié)構(gòu) 兩種。14、棧和隊列都是 運算受限

3、的線性表，棧的特點是 先進后出 ，隊列的特點是 先進先出 。15、圖定義為：G=(V，E)，其中，V是_頂點的有窮非空_的集合，E是_頂點間關(guān)系的有窮_的集合。16、有一棵樹如圖所示，請回答以下問題：（1）這棵樹的根結(jié)點是_a _；（2）這棵樹的葉子結(jié)點是_ g,e,i _；（3）這棵樹的深度是_5 _；（4）結(jié)點c的孩子結(jié)點是_ e,f _；（5）結(jié)點h的雙親結(jié)點是_f _；（6）結(jié)點e的堂兄弟是 d ，兄弟是 f 。17、線性表中 元素的個數(shù) 稱為表的長度。18、在任意二叉樹中，若葉子結(jié)點的個數(shù)為n0，度為1的結(jié)點數(shù)為n1，度為2的結(jié)點數(shù)為n2，則滿足關(guān)系 n0= n2+1 。19、圖的遍

4、歷方法_深度優(yōu)先搜索_和 廣度優(yōu)先搜索_。20、按照排序過程中存儲器的不同，可將排序分為 內(nèi)部排序 和 外部排序 。二、選擇題（將答案寫在題后的方框內(nèi)）1、一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（B）。A、110 B、108 C、100 D、1202、樹最適合用來表示（ C ）。A、有序數(shù)據(jù)元素B、無序數(shù)據(jù)元素C、元素之間具有分支層次關(guān)系的數(shù)據(jù)D、元素之間無聯(lián)系的數(shù)據(jù)3、一棵二叉排序樹T，用（ B ）方法進行遍歷，可以得到各結(jié)點鍵值的遞增序列。  A、先根遍歷B、中根遍歷C、層次遍歷D、后根遍歷4、在下述的排序方法中，不屬于內(nèi)部排序的是（ C

5、）。A、選擇排序法 B、插入排序法 C、拓撲排序法 D、歸并排序法5、線性表是一個（A ）。A、有限序列，可以為空B、有限序列，不能為空C、無限序列，可以為空D、無限序列，不能為空6、以下數(shù)據(jù)結(jié)構(gòu)中，（ A ）是非線性數(shù)據(jù)結(jié)構(gòu)。A、樹 B、字符串 C、隊 D、棧7、如果最常用的操作是取第i個結(jié)點及其前驅(qū)，最節(jié)省時間的存儲方式是（ D ）。A、單鏈表B、雙向鏈表C、單循環(huán)鏈表D、順序表8、按照二叉樹的定義，具有3個結(jié)點的二叉樹有（ C ）種.A、3 B、4 C、5 D、69、算法指的是（ D ）。A、計算機程序B、解決問題的計算方法C、排序算法D、解決問題的有限運算序列10、深度為5的二叉樹至多

6、有（ C ）個結(jié)點。A、16B、32C、31D、1011、一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（ B ）。A、110 B、108 C、100 D、12012、樹最適合用來表示（ C ）。A、有序數(shù)據(jù)元素B、無序數(shù)據(jù)元素C、元素之間具有分支層次關(guān)系的數(shù)據(jù)D、元素之間無聯(lián)系的數(shù)據(jù)13、一棵二叉排序樹T，用（ B ）方法進行遍歷，可以得到各結(jié)點鍵值的遞增序列。  A、先根遍歷B、中根遍歷C、層次遍歷D、后根遍歷14、在下述的排序方法中，不屬于內(nèi)部排序的是（ C ）。A、選擇排序法 B、插入排序法 C、拓撲排序法 D、歸并排序法15、有關(guān)二叉樹下列說

7、法正確的是（ A ）A、二叉樹的度為2B、一棵二叉樹的度可以小于2C、二叉樹中至少有一個結(jié)點的度為2D、二叉樹中任何一個結(jié)點的度都為216、以下數(shù)據(jù)結(jié)構(gòu)中，（ A ）是非線性數(shù)據(jù)結(jié)構(gòu)。A、樹 B、字符串 C、隊 D、棧17、鏈表不具備的特點是（ A ）。A、可隨機訪問任意一個結(jié)點B、插入和刪除不需要移動任何元素C、不必事先估計存儲空間D、所需空間與其長度成正比18、向一個有126個元素的順序表中插入一個新元素并保存，原來順序不變，平均要移動（ C ）個元素。A、8B、63.5C、63D、719、如果最常用的操作是取第i個結(jié)點及其前驅(qū)，最節(jié)省時間的存儲方式是（ D ）。A、單鏈表B、雙向鏈表C、

8、單循環(huán)鏈表D、順序表20、按照二叉樹的定義，具有3個結(jié)點的二叉樹有（ C ）種. A. 3 B. 4 C. 5 D. 621、深度為5的二叉樹至多有（ C ）個結(jié)點。A、16B、32C、31D、1022、算法指的是（ D ）。A、計算機程序B、解決問題的計算方法C、排序算法D、解決問題的有限運算序列23、以下何種排序是穩(wěn)定的？（ A ）A、直接插入排序 B、希爾排序C、快速排序 D、直接選擇排序24、對線性表，在下列情況下應(yīng)當(dāng)采用鏈表表示的是（ B ）。A、經(jīng)常需要隨機地存取元素B、經(jīng)常需要進行插入和刪除操作C、表中元素需要占據(jù)一片連續(xù)的存儲空間D、表中元素的個數(shù)不變25、在單鏈表中，指針p指

9、向元素為x的結(jié)點，實現(xiàn)“刪除x的后繼”的語句是（ B ）。A、p =pnext；B、pnext=pnextnext；C、pnext=p；D、p=pnextnext；26、在（ C ）運算中，使用順序表比鏈表好。 A、插入 B、刪除 C、根據(jù)序號查找 D、根據(jù)元素值查找27、線性表是一個（ A ）。A、有限序列，可以為空B、有限序列，不能為空C、無限序列，可以為空D、無限序列，不能為空28、一個有n個頂點的無向圖最多有（ C ）條邊。A、n B、n (n-1) C、n (n-1)/2 D、2n29、對線性表進行折半查找時，要求線性表必須（ C ）。A、以順序方式存儲B、以鏈接方式存儲C、以順序方

10、式存儲，且結(jié)點按關(guān)鍵字有序排列D、以鏈接方式存儲，且結(jié)點按關(guān)鍵字有序排列30、若讓元素1，2，3依次進棧，則出棧次序不可能出現(xiàn)（ C ）的情況。A、3，2，1 B、2，1，3 C、3，1，2 D、1，3，2三、綜合題1、請畫出具有3個結(jié)點的所有二叉樹形狀。ABCABCABCABCABC2試寫出右圖所示的二叉樹的前序、中序和后序序列。前序序列：abdgcefhi中序序列：dgbaechif后序序列：gdbeihfca3、請將下圖所給的樹轉(zhuǎn)換為的二叉樹。HIKLMJABCDEFHABCDEFIKJML4、對于權(quán)值W=14，7，4，20，2，試寫出構(gòu)造哈夫曼樹的過程，并計算其帶權(quán)路徑長度WPL。27147204261347帶權(quán)路徑長度WPL=2*4+4*4+7*3+14*2+20*1=935、已知序列30，50，60，35，86，10 ，請給出采用起泡排序法對該序列作降序排序時的每一趟的結(jié)果。初始關(guān)鍵字：30 5060358610第一趟：506035863010第二趟：605086353010第三趟：608650353010第四趟：8660503530106、（1）將樹轉(zhuǎn)換成二叉樹。（2）將二叉樹轉(zhuǎn)換成森林。ABCDEFABCEGDF（1）（2）ABCDEF7、對于權(quán)值W=14，7