1.1. 2歷屆最新考題彙編
一、選擇題
1、資料的儲存結構是指
a、儲存在外存中的資料b、資料所佔的儲存空間量
c、資料在計算機中的順序儲存方式 d、資料的邏輯結構在計算機中的表示
2、下列關於棧的描述中錯誤的是
a、棧是先進後出的線性表 b、棧只能順序儲存
c、棧具有記憶作用 d、對棧的插入與刪除操作中，不需要改變棧底指標
3、對於長度為n的線性表，在最壞的情況下，下列各排序法所對應的比較次數中正確的是
a、氣泡排序為n/2b、氣泡排序為n
c、快速排序為nd、快速排序為n(n-1)/2
4、對長度為n的線性表進行順序查詢，在最壞情況下所需要的比較次數為
a、log2n b、n/2 c、n d、n+1
5、下列對於線性鍊錶描述中正確的是
a、儲存空間不一定是連續，且各元素的儲存順序是任意的
b、儲存空間不一定是連續，且前件元素一定儲存在後件元素的前面
c、儲存空間必須連續，且前件元素一定儲存在後件元素的前面
d、儲存空間必須連續，且各元素的儲存順序是任意的
6、演算法的時間複雜度是指
a、執行演算法程式所需要的時間b、演算法程式的長度
c、演算法執行過程中所需要的基本運算次數 c、演算法程式中的指令條數
7、演算法的空間複雜度是指
a、演算法程式的長度b、演算法程式中的指令條數
c、演算法程式中所佔的儲存空間 d、演算法執行過程中所需要的儲存空間
8、下列敘述中正確的是
a、線性表是線性結構 b、棧和佇列是非線性結構
c、線性鍊錶是非線性結構 d、二叉樹是線性結構
10、下列關於線性表的兩種儲存結構敘述正確的是
a、若儲存相同數目的元素，則線性鍊錶比順序表要節省儲存空間
b、對無序表的查詢，順序表和線性鍊錶的效率是一樣的
c、順序表適用於插入、刪除等更新操作頻率的場合
d、線性鍊錶適用於查詢操作比較頻繁的場合
11、下列關於棧的敘述中不正確的是
a、在棧中只能在同一端插入、刪除資料
b、在棧中只能在一端插入資料，在另一端刪除資料
c、棧是先進後出的線性表d、棧是後進先出的線性表
12、已知元素的入棧順序為abcde，則下列哪種出棧順序是不可能的（出棧和入棧操作可交叉進行）？
a、edcbab、cabde c、dcbae d、bcdea
13、**性鍊錶的插入演算法中，若要把結點q插在結點p後面，下列操作正確的是：
a、使結點p指向結點q，再使結點q指向結點p的後件結點
b、使結點q指向p的後件結點，再使結點p指向結點q
c、使結點q指向結點p，再使結點p指向結點q的後件結點
d、使結點p指向q的後件結點，再使結點q指向結點p
14、下列敘述中錯誤的是：
a、迴圈鍊錶中，通過表中的任何乙個結點可以訪問到表中其他所有的結點
b、線性鍊錶的插入和刪除效率比順序表的插入和刪除效率高
c、線性鍊錶與順序表相比，它容易實現動態增長
d、**性煉表中查詢乙個元素要比在順序表中查詢乙個元素塊
15、一棵度數為4的樹，它的4度結點有1個，3度結點有2個，2度結點有3個，1度結點4個，問它的葉子結點有多少個？
a、5b、6 c、9 d、11
16、一棵深度為m的二叉樹有2m-1個結點，則最多可以斷定此二叉樹是
a、滿二叉樹 b、一般完全二叉樹 c、一般的二叉樹 d、一般的樹
17、以下四棵樹中不是完全二叉樹的是
abcd、
19、下列排序演算法中，平均排序速度最快的是
a、氣泡排序法 b、選擇排序法 c、交換排序法 d、堆排序法
二、填空題
1、某二叉樹中度為2的結點有18個，則該二叉樹中有 【1】 個葉子結點。
2、問題處理方案的正確而完整的描述稱為 【2】 。
8、擁有奇數個結點的完全二叉樹中有4個內部結點（非葉子結點），請問它的葉子結點數是 【21】 。
1.1.3全真試題訓練
一、選擇題
1、下面哪乙個不是演算法的基本特徵？
a、可靠性 b、確定性 c、有窮性 d擁有足夠的報情
7、對長度為n的線性表進行順序查詢，在最壞情況下所需要的比較次數為
a、n+1 b、n c、(n+1)/2 d、n/2
8、下面哪一項敘述不是非空線性表的結構特徵的正確描述？
a、有且只有乙個根結點，它無前件
b、有且只有乙個終端結點，它無後件
c、除根結點和終端結點外，其他所有結點有且只有乙個前件，也有且只有乙個後件
d、每乙個結點都有乙個前件和一后件
10、下列關於佇列的敘述中正確的是
a、在佇列中只能刪除資料 b、在佇列中只能插入資料
c、佇列是先進先出的線性表 d、佇列是後進先出的線性表
13、樹t的度為4，其中度為1，2，3，4的結點個數分別為4，2，1，1。則t中的葉子結點數為
a、8 b、7 c、6 d、5
14、在深度為5的滿二叉樹中，葉子結點的個數為
a、32 b、31 c、16 d、15
15、具有8個結點的完全二叉樹中編號為4的結點的右子結點的編號為
a、8b、9
c、 無此結點 d、8或是9
16、圖1.6中二叉樹的前序遍歷順序為
a、abdecf b、debacf
c、abcdef d、debafc圖1.6
17、在長為n的有序表中進行二分查詢，需要的最大次數為
a、n b、n/2 c、log2n d、log2n/2
18、通過相鄰資料元素的交換逐步將線性表變成有序的排序方法是
a、氣泡排序法b、簡單選擇排序法
c、簡單插入排序法 d、希爾排序法
19、快速排序法屬於
a、選擇類排序法 b、交換類排序法
c、插入類排序法 d、歸併類排序法
20、對長度為n的線性表進行堆排序的時間複雜度是
a、o（n） b、o(nlog2n) c、o(n2) d、o(n1.5)
二、填空題
1、乙個演算法通常由兩種基本要素組成：一是對資料物件的運算和操作，二是【1】 。
2、在一般的計算機系統中，有算術運算、邏輯運算、關係運算和【2】 四類基本的操作和運算。
3、演算法中的每乙個步驟都必須有明確的定義，不允許有模稜兩可的解釋，也不允許有多義性，這是演算法的【3】特徵。
4、演算法必須能在有限的時間內完成，即演算法必須能在執行有限個步驟之後終止，這是演算法的【4】特徵。
5、【5】是一組嚴謹地定義運算順序的規則，並且每乙個規則都是有效的，且是明確的，比順序將在有限的次數下終止。
6、演算法中各操作之間的執行順序稱為【6】 。描述演算法的工具通常有【7】 、【8】 、【9】 等。
7、乙個演算法一般都可以用【10】 、【11】 、【12】 三種控制結構組合完成。
8、根據提出的問題，列舉所有可能的情況，並用問題中給定的條件檢驗哪些是需要的，哪些是不需要的，這是演算法設計基本方法中的【13】 。
10、從已知的初始條件出發，逐步推出所要求的各中間結果和最後結果，這是演算法設計基本方法中的【15】 。
11、將乙個複雜的問題歸結為若干個較簡單的問題，然後將這些較簡單的問題再歸結為更簡單的問題，這個過程可以一直做下去，直到最簡單的問題為止，這是演算法設計基本方法中的【16】 。如果乙個演算法p顯式地呼叫自己則稱為【17】 。如果演算法p呼叫另乙個演算法q，而演算法q又呼叫演算法p，則稱為【18】 。
12、將問題的規模減半，而問題的性質不變，再重複「減半」的過程，這是演算法設計基本方法中的【19】 。
14、演算法的時間複雜度是用演算法所執行的【21】 來度量。
15、反映資料元素之間邏輯關係的資料結構是【22】 。資料的邏輯結構在計算機儲存空間中的存放形式稱為【23】 。
16、資料的邏輯結構有兩個要素：一是【24】 ，通常記為【25】 ；二是【26】 ，通常記為【27】 。
17、表示資料結構的兩種方法是【28】 和【29】 。
18、在長度為n的順序儲存結構的線性表中，要在第i(1≤i≤n)個元素之前插入乙個新元素，則需要移動表中的【30】個元素，表的長度變為【31】 ；若刪除表中的i(1≤1≤n)個元素，則需要移動表中的【32】個元素，表的長度變為【33】 。
19、在長度為n的順序儲存結構的線性表中，插入（或刪除）乙個元素，在平均情況下需要移動表中的【34】個元素，在最壞情況下需要移動表中的【35】個元素。
21、資料按照「先進後出」的順序組織的資料結構是【37】 ，按照「後進先出」組織的資料結構是【38】 ，按照「先進先出」組織的資料結構是【39】 。
23、樹是一種簡單的【41】 （線性/非線性）結構，在樹中，所有資料元素之間的關係具有明顯的【42】特徵。
24、設一棵完全二叉樹菜有700個結點，則在該二
叉樹中有【43】個葉子結點。
25、具有16個結點完全二叉樹的深度為【43】 。
26、設有右圖1.8所示的二叉樹，對此二叉樹的前
序遍歷序列是【44】 ，中序遍歷序列是【45】 ，後序
遍歷序列是【46】 。
27、在最壞情況下，氣泡排序的時間複雜度為【47】 ，簡單插入排序的時間複雜度為【48】 ，希爾排序的時間複雜度為【49】 ，簡單選擇排序的時間複雜度為【50】 ，堆排序的時間複雜度為【51】 。
28、以下排序技術中屬於交換類排序法的有【52】 ，屬於插入類排序法的有【53】 ，屬於選擇類排序法的有【54】 。
一選擇題
1~10 dbdcacdadb11~19 bbbddadbd
二填空題
（1）19 （2）演算法
公共基礎知識
第一章資料結構與演算法 考點1 演算法的基本概念 演算法 是指一組有窮的指令集，是解題方 而完整的描述。演算法不等於程式，也不等於計算方法。演算法的基本特徵 確定性，演算法中每一步驟都必須有明確定義，不允許有多義性 有窮性，演算法必須能在有限的時間內做完，即能在執行有限個步驟後終止 可行性，演算法原...
公共基礎知識
公共基礎知識.txt花前月下，不如花錢 日 下。葉子的離開，是因為風的追求還是樹的不挽留？乾掉熊貓，我就是國寶！別和我談理想，戒了！1 制度化教育階段開始於 近代。2 各國的學校教育系統基本形成於 19世紀末。3 現在世界上大多數國家的義務教育年限在 9年或9年以上。4 不憤不啟，不悱不發 啟發教學...
公共基礎知識
第一部分馬克思主義哲學 1 哲學 世界觀 方 哲學，是系統化 理論化的世界觀。方 是人們認識世界 改造世界的根本方法。2 哲學的基本問題 哲學的基本問題，包括兩個方面，兩個層次。第一方面，是關於物質和意識誰是第一性 誰是第二性的問題，是劃分唯物主義和唯心主義的根本依據。第二方面，是物質和意識是否具有...