【文章內(nèi)容簡介】 A） ABCDEF B） DBEAFC C） ABDECF D） DEBFCA （ 15）在深度為 7 的滿二叉樹中，葉子結(jié)點的個數(shù)為 A） 32 B） 31 C） 64 D） 63 （ 16）下列數(shù)據(jù)結(jié)構(gòu)中，能用二分法進行查找的是 A）順序存儲的有序線性表 B）線性鏈表 C）二叉鏈表 D）有序線性鏈表 （ 17）下列關(guān)于棧的描述正確的是 A）在棧中只能插入元素而不能刪除元素 B）在棧中只能刪除元素而不能插入元素 C）棧是特殊的線性表，只能在一端插入成刪除元素 D）棧是特殊的線性表，只能在一端插入 元素，而在另一端刪除元素 （ 18）下列敘述中正確的是 A）一個邏輯數(shù)據(jù)結(jié)構(gòu)只能有一種存儲結(jié)構(gòu) B）數(shù)據(jù)的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，且各種存儲結(jié)構(gòu)不影響數(shù)據(jù)處理的效率 C）一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且各種存儲結(jié)構(gòu)不影響數(shù)據(jù)處理的效率 D）一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且各種存儲結(jié)構(gòu)影響處理的效率 （ 19）數(shù)據(jù)的存儲結(jié)構(gòu)是指 A）存儲在外存中的數(shù)據(jù) B）數(shù)據(jù)所占的存儲空間量 C）數(shù)據(jù)在計算機中的順序存儲方式 D）數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示 （ 20）下列關(guān)于棧的描述中錯誤的是 A）棧是先進后出 的線性表 B）棧只能順序存儲 C）棧具有記憶作用 D）對棧的插入與刪除操作中，不需要改變棧底指針 （ 21）對于長度為 n 的線性表，在最壞情況下，下列各排序法所對應(yīng)的比較次數(shù)中正確的是 A）冒泡排序為 n/2 B）冒泡排序為 n C）快速排序為 n D）快速排序為 n(n1)/2 （ 22）對長度為 n 的線性表，在最壞情況下，下列各排序法所對應(yīng)的比較次數(shù)中正確的是 A） log2n B） n/2 C） n D） n+1 （ 23）下列對于線性鏈表的描述中正確的是 A）存儲空間不一定是連續(xù)，且各元素的存儲順序是任意的 B）存儲空間不一定是連續(xù)，且前件元素一定存儲在后件元素的前面 C）存儲空間必須連續(xù)，且前件元素一定存儲在后件元素的前面 D）存儲空間必須連續(xù)，且各元素的存儲順序是任意的 二、填空題 A B C E E F 選擇題第（ 14）題圖 F C E A D G B 選擇題第（ 11）題圖 （ 1）線性表的存儲結(jié)構(gòu)主要分為順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。隊列是一種特殊的線性表，循環(huán)隊列的 [1] 存儲結(jié)構(gòu)。 （ 2）對下列二叉地進行中序遍歷的結(jié)果為 [2] 。 （ 3）在深度為 7 的滿二叉樹中，度為 2 的結(jié)點個數(shù)為 [3] 。 （ 4）按“先進后出”原則組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是 [4] 。 （ 5）數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu) 和非線性結(jié)構(gòu)，帶鏈的隊列屬于 [5] 。 （ 6）對長度為 10 的線性表進行冒泡排序，最壞情況下需要比較的次數(shù)為 （ 6） 。 （ 7）算法復(fù)雜度主要包括時間復(fù)雜度和 [7] 復(fù)雜度。 （ 8）一棵二叉樹第六層（根結(jié)點為第一層）的結(jié)點數(shù)最多為 [8] 個。 （ 9）數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，循不隊列屬于 [9] 結(jié)構(gòu)。 （ 10）某二叉樹中度為 2 的結(jié)點有 18個，則該二叉樹中有 [10] 個葉子結(jié)點。 （ 11）問題處理方案的正確而完整的描述稱為 [11] 。 1． 1． 3 全真試題訓(xùn)練 一、選擇 題 （ 1）長度為 10的順序表的首地址是從 1023 開始的，順序表中的每個元素的長度為 2，在第 4 個元素前面插入一個元素和刪除第 7 個元素后，順序表的總長度還是不變。問在執(zhí)行插入和刪除操作前，順序表中第 5 個元素在執(zhí)行插入和刪除操作后在順序表中的存儲地址是 A） 1028 B） 1029 C） 1031 D） 1033 （ 2）下列關(guān)于線性表的兩種存儲結(jié)構(gòu)敘述正確的是 A）若存儲相同數(shù)目的元素，則線性鏈表比順序表要節(jié)省存儲空間 B）對無序表的查找，順序表和線性鏈表的效率基本上是一樣的 C）順序表適用于插入，刪除等更新操作 頻繁的場合 D）線性表適用于查詢操作比較頻繁的場合 （ 3）已知元素的人棧順序為 abcde ，則下列哪種出棧順序是不可能的（出棧和入棧操作可交叉進行）？ A） edcba B） cabde C） dcbae D） bcdea （ 4）在線性鏈表的插入算法中，若要把結(jié)點 q 插在結(jié)點 p 后面，下列操作正確的是： A）使結(jié)點 p 指向結(jié)點 q，再使結(jié)點 q 指向結(jié)點 p 的后件結(jié)點 B）使結(jié)點 q 指向 p 的后件結(jié)點，再使結(jié)點 p 指向結(jié)點 q C）使結(jié)點 q 指向結(jié)點 p 的后件結(jié)點，再使結(jié)點 q 指向結(jié)點 p D）使結(jié)點 p 指向 q 的后件結(jié)點，再使 結(jié)點 q 指向結(jié)點 p （ 5）下列敘述中錯誤的是： A）循環(huán)鏈表中，通過表中的任何一個結(jié)點可以訪問到表中其他所有的結(jié)點 B）線性鏈表的插入和刪除效率比順序表的插入和刪除效率高 C）線性鏈表與順序表相比，它容易實現(xiàn)動態(tài)增長 D）在線性鏈表中查找一個元素要比在順序中查找一個元素快 （ 6）一棵度數(shù)為 4 的樹，它的 4 度結(jié)點有 1 個， 3 度結(jié)點有 2 個， 2 度結(jié)點有 3 個， 1 度結(jié)點 4 個，問它的葉子結(jié)點有多少個？ A） 5 B） 6 C） 9 D） 11 （ 7）一棵深度為 m的二叉樹 2m1 個結(jié)點，則最多可以斷定此二叉樹是 A）滿二叉樹 B）一般的完全二叉樹 C）一般的二叉樹 D）一般的樹 （ 8）以下四種樹中不是完全二叉樹的是 A） B） C） D） P F C E A D G H B 填空題第（ 2）題圖 （ 9）在一個 x m 的二維線性表中順序查找一個數(shù)據(jù)元素的算法時間復(fù)雜度是 A） O(n+m) B） O(n m) C） O(n2) D） O(m2) （ 10）下面排序算法中，平均排序速度最快的是 A）冒泡排序法 B）選擇排序法 C）交換排序法 D）堆排序法 （ 11）下面哪一個不是算法的基本特征？ A）可靠性 B）確定性 C）有窮性 D）擁有足夠的情報 （ 12）通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般的關(guān)系的算法設(shè)計思想是 A）列舉法 B）歸納法 C）遞推法 D）遞歸法 （ 13）常用于解決“是否存在”或“有多少種可能”等類型的問題（例如求解不定議程的問題）的算法設(shè)計基本方法是 A）歸納法 B）遞推法 C）列舉法 D）減半遞推技術(shù) （ 14）以下算法設(shè)計基本方法中基本思想不屬于歸納法的是 A）遞推法 B）遞歸法 C）減半遞推技術(shù) D）回 溯法 （ 15）在用于分法求解議程在一個閉區(qū)間上的實根時，采用的算法設(shè)計技術(shù)是 A）列舉法 B）歸納法 C）遞歸法 D）減半遞推法 （ 16）右下圖表示的數(shù)據(jù)結(jié)構(gòu)是 A） D={di |1=i=6}={d1,d2,d3,d4,d5,d6} R={(d1,d2),(d1,d3),(d3,d4)(d5,d4),(d5,d6)} B） D={di|1=i=6}={d1,d2,d3,d4,d5,d6} R={(d1,d2),(d1,d3),(d3,d4),(d3,d5),(d5,d4),(d5,d6)} C） D={di|1=i=6}={d1,d2,d3,d4,d5,d6} R={(d1,d2),(d1,d3),(d3,d4),(d3,d5),(d5,d6)} D） D={di|1=i=6}={d1,d2,d3,d4,d5,d6} R={(d1,d2),(d1,d3),(d3,d4),(d5,d3),(d5,d4),(d5,d6)} （ 17）已知線性表的首元素的地址是 1025，每個數(shù)據(jù)元素的長度為 2，則第 10 個元素的地址為 A） 1035 B） 1045 C） 1027 D） 1043 （ 18） 下列關(guān)于鏈表結(jié)構(gòu)的敘述正確的是 A）線性鏈表、帶鏈的棧和帶鏈的隊列的結(jié)點的結(jié)構(gòu)都是相同的 B）雙向鏈表也就是循環(huán)鏈表 C）線性鏈表與帶鏈的棧的結(jié)點的結(jié)構(gòu)是不同的 D）在循環(huán)鏈表中通過任意一個結(jié)點可以找到鏈表中其他所有的結(jié)點，而在雙向鏈表中做不到這一點 （ 19）在表示樹的多重鏈表中，除了要存儲結(jié)點的值和多個指針之外，還必須需要存儲 A）結(jié)點的度 B）結(jié)點的層次 C）結(jié)點的高度 D）結(jié)點的深度 （ 20）樹 T 的度為 4，其中度為 1， 2， 3， 4 的結(jié)點個數(shù)分別為 4， 2， 1， 1。則 T 中的葉子結(jié)點數(shù)為 A） 8 B） 7 C） 6 D） 5 （ 21）具有 8 個結(jié)點的完全二叉樹中編號為 4 的結(jié)點的右子結(jié)點的編號為 A） 8 B） 9 C）無此結(jié)點 D） 8 或是 9 （ 22）通過相鄰數(shù)據(jù)元素的交換逐步將線性表變成有序的排序方法是 A）冒泡排序法 B）簡單選擇排序法 C）簡單插入排序法 D）希爾排序法 （ 23）快速排序法屬于 A）選擇類排序法 B）交換類排序法 C）插入類排序法 D）歸并類排序法 （ 24）對長度為 n 的線性表進行推排序的時間復(fù)雜度是 A） O(n) B） O(nlog2n) C） O(n2) D） O() 二、填空題 （ 1）假如剛開始時棧為空，依次有‘ A’，‘ B’，‘ C’，‘ D’四個元素入棧，此時棧底指針指向元素 [1] ，棧頂指針值為 [2] （假設(shè)每個元素的長度為 1）。執(zhí)行四次出棧操作后把‘ E’，‘ F’，‘ G’壓入棧，問此時棧底指針指向元素 [3] ，此時棧的長度為 [4] 。 （ 2）在一個容量為 15 的循環(huán)險旬中，若頭指針 front=6, 尾指針 rear=4，則該循環(huán)隊列中共有 [5]個元素；若頭指針 front=4，尾指針 rear=6，則該循環(huán)隊列中共有 [6] 個元素；若頭指針 front=6，尾指針 rear=6，則該循環(huán)隊列中共有 [7] 個元素。 （ 3）擁有奇數(shù)個結(jié)點的完全二叉樹中有 4 個內(nèi)部結(jié)點（非葉子結(jié)點），請問它的葉子結(jié)點數(shù)是 [8] 。 （ 4）請寫出用二分查找法在有序順序表（ 1， 2， 3， 4， 6， 8， 9， 11）中查找 3 的比較序列 [9] 。 （ 5）設(shè)一棵二叉樹的中序遍歷結(jié)果為 DBEACF，前序遍歷結(jié)果為 ABDECF，則后序遍歷結(jié)果為 [10] 。 （ 6）請寫出用冒泡排序法對序列（ 5， 1， 7， 3， 1， 6， 9， 3， 2， 7， 6）進行第一遍掃描后的中間結(jié)果是 [11] 。 （ 7）請寫 出用冒泡排序法對序列（ 5， 1， 7， 3， 1， 6， 9， 3， 2， 7， 6）進行第一遍掃描后的中間結(jié)果是 [12] 。 （ 8）請寫出用簡單選擇排序法對序列（ 5， 1， 7， 3， 1， 6， 9， 3， 2， 7， 6）進行第一遍掃描后的中間結(jié)果是 [13] 。 （ 9）一個算法通常由兩種基本要素組成，一是對數(shù)據(jù)對象的運算和操作，二是 [14] 。 （ 10）在一般的計算機系統(tǒng)中，有算術(shù)運算、邏輯運算、關(guān)系運算和 [15] 四類基本的操作和運算。 （ 11）算法中的每一個步驟都必須有明確的定義，不允許有模棱兩可的解釋，也不允許有多義 性，這是算法的 [16] 特征。 （ 12）算法必須能在有限的時間內(nèi)完成，即算法必須能在執(zhí)行有限個步驟之后終止，這是算法的 [17] 特征。 （ 13） [18] 是一組嚴謹?shù)囟x運算順序的規(guī)則，并且每一個規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。 （ 14）算法中各操作之間的執(zhí)行順序稱為 （ 19） 。描述算法的工具通常有 [20]、 [21] 、 [22] 等。 （ 15）一個算法一般都可以用 [23] 、 [24] 、 [25] 三種控制結(jié)構(gòu)組合完成。 （ 16）根據(jù)提出的問題，列舉所 有可能的情況，并且問題中給定的條件檢驗?zāi)男┦切枰模男┦遣恍枰?，這是算法設(shè)計基本方法中的 [26] 。 （ 17）通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般的關(guān)系，這是算法設(shè)計基本方法中的 [27] 。 （ 18）從已知的初始條件出發(fā)，逐步推出所要求的各中間結(jié)果和最后結(jié)果，這是算法設(shè)計基本方法中的 [28] 。 （ 19）將一個復(fù)雜的問題歸結(jié)為若干個簡單的問題，然后將這些較簡單的問題再歸結(jié)為更簡單的問題，這個過程可以一直做下去，直到最簡單的問題的問題為止，這是算法設(shè)計基本方法中的 [29] 。如果 一個算法 P 顯式地調(diào)用自己則稱為 [30] 。如果算法 P 調(diào)用另一個算法 Q，而算法 Q 又調(diào)用算法 P，則稱為 [31] 。 （ 20）將問題的規(guī)模減半，而問題的性質(zhì)不變，再重復(fù)“減半”的過程，這是算法設(shè)計基本方法中的 [32] 。 （ 21）通過對問題的分析，找出一個解決問題的線索，然后沿著這個線索逐步試探，對于每一步的試探，若試探成功，就得到問題的解，若試探失敗，就逐步回退，換別的路線再進行試探，這是算法設(shè)計基本方法中的 [33] 。 （ 22）數(shù)據(jù)的邏輯