二級試題演算法設計只考慮什麼

㈠ 2012年江蘇省C++二級考試試卷及答案

一、選擇題(每小題2分，共70分)
下列各題A)、B)、C)、D)四個選項中，只有一個選項是正確的。請將正確選項填塗在答題卡相應位置上，答在試卷上不得分。
(1)下列敘述中正確的是（）。
A)演算法就是程序
B)設計演算法時只需要考慮數據結構的設計
C)設計演算法時只需要考慮結果的可靠性
D)以上三種說法都不對

(2)下列關於線性鏈表的敘述中，正確的是（）。
A)各數據結點的存儲空間可以不連續，但它們的存儲順序與邏輯順序必須一致
B)各數據結點的存儲順序與邏輯順序可以不一致，但它們的存儲空間必須連續
C)進行插入與刪除時，不需要移動表中的元素
D)以上三種說法都不對

(3)下列關於二叉樹的敘述中，正確的是（）。
A)葉子結點總是比度為2的結點少一個
B)葉子結點總是比度為2的結點多一個
C)葉子結點數是度為2的結點數的兩倍
D)度為2的結點數是度為1的結點數的兩倍

(4)軟體按功能可以分為應用軟體、系統軟體和支撐軟體(或工具軟體)。下面屬於應用軟體的是（）。
A)學生成績管理系統
B)C語言編譯程序
C)UNIX操作系統
D)資料庫管理系統

(5)某系統總體結構圖如下圖所示：

該系統總體結構圖的深度是（）。
A)7
B)6
C)3
D)2

(6)程序調試的任務是（）。
A)設計測試用例
B)驗證程序的正確性
C)發現程序中的錯誤
D)診斷和改正程序中的錯誤

(7)下列關於資料庫設計的敘述中，正確的是（）。
A)在需求分析階段建立數據字典
B)在概念設計階段建立數據字典
C)在邏輯設計階段建立數據字典
D)在物理設計階段建立數據字典

(8)資料庫系統的三級模式不包括（）。
A)概念模式
B)內模式
C)外模式
D)數據模式

(9)有三個關系R、S和T如下：

則由關系R和S得到關系T的操作是（）。
A)自然連接
B)差
C)交
D)並

(10)下列選項中屬於面向對象設計方法主要特徵的是（）。
A)繼承
B)自項向下
C)模塊化
D)逐步求精
(11)在對函數進行原型聲明時，下列語法成分中，不需要的是()。
A)函數返回類型
B)函數參數列表
C)函數名
D)函數體

(12)下列關於this指針的描述中，正確的是()。
A)類的成員函數都有this指針
B)類的友元函數都有this指針
C)任何與類相關的函數都有this指針
D)類的非靜態成員函數都有this指針

(13)

(14)為類Matrix重載下列運算符時，只能作為Matrix類成員函數重載的運算符是（）。
A)+
B)=
C)<<
D)++

(15)下列關於模板的描述中，錯誤的是()。
A)類模板的成員函數都是模板函數
B)函數模板是一種參數化類型的函數
C)滿足一定條件時可以省略模板實參
D)模板形參只能由關鍵字typename聲明

(16)要利用C++流實現輸入輸出的各種格式控制，必須在程序中包含的頭文件是()。
A)fstream
B)istreara
C)ostream
D)iomanip

(17)下列選項中，不是C++關鍵字的是()。
A)class
B)functi013
C)friend
D)virtual

(18)若有定義語句「int i=2,j=3;」，則表達式i/j的結果是（）。
A)0
B)0．7
C)0．66667
D)0．66666667

(19)

㈡ 設計一個好的演算法通常要考慮哪些要求

數據結構中評價一個好的演算法，應該從四個個方面來考慮，分別是：

一、演算法的正確性。

二、演算法的易讀性。

三、是演算法的健壯性。

四、是演算法的時空效率（運行）。

演算法的設計取決於數據（邏輯）結構，演算法的實現取決於所採用的存儲結構。數據的存儲結構本質上是其邏輯結構在計算機存儲器中的實現。為了全面反映一個數據的邏輯結構，它在內存中的映像包括兩個方面，即數據元素之間的信息和數據元素之間的關系。

不同的數據結構有相應的操作。數據的操作是在數據的邏輯結構上定義的操作演算法，如檢索、插入、刪除、更新和排序。

(2)二級試題演算法設計只考慮什麼擴展閱讀

演算法可大致分為基本演算法、數據結構的演算法、數論與代數演算法、計算幾何的演算法、圖論的演算法、動態規劃以及數值分析、加密演算法、排序演算法、檢索演算法、隨機化演算法、並行演算法，厄米變形模型，隨機森林演算法。

演算法可以宏泛的分為三類：

一、有限的，確定性演算法 這類演算法在有限的一段時間內終止。他們可能要花很長時間來執行指定的任務，但仍將在一定的時間內終止。這類演算法得出的結果常取決於輸入值。

二、有限的，非確定演算法 這類演算法在有限的時間內終止。然而，對於一個（或一些）給定的數值，演算法的結果並不是唯一的或確定的。

三、無限的演算法 是那些由於沒有定義終止定義條件，或定義的條件無法由輸入的數據滿足而不終止運行的演算法。通常，無限演算法的產生是由於未能確定的定義終止條件。

㈢ 計算機二級考試MS Office題庫及答案

1、 對長度為n的線性表排序，在最壞情況下，比較次數不是n(n-1)/2的排序方法是

A) 快速排序 B) 冒泡排序 C) 直接插入排序 √D) 堆排序

2、下列關於棧的敘述正確的是

A) 棧按""先進先出""組織數據 √B) 棧按""先進後出""組織數據

C) 只能在棧底插入數據 D) 不能刪除數據

3、演算法的空間復雜度是指

√A) 演算法在執行過程中所需要的計算機存儲空間

B) 演算法所處理的數據量

C) 演算法程序中的語句或指令條數 D) 演算法在執行過程中所需要的臨時工作單元數

4、某二叉樹有5個度為2的結點，則該二叉樹中的葉子結點數是

A) 10 B) 8 √C) 6 D) 4

5、 演算法的有窮性是指

√A) 演算法程序的運行時間是有限的 B) 演算法程序所處理的數據量是有限的

C) 演算法程序的長度是有限的 D) 演算法只能被有限的用戶使用

6、下列敘述中正確的是

A) 演算法復雜度是指演算法控制結構的復雜程度

B) 演算法復雜度是指設計演算法的難度

C) 演算法的時間復雜度是指設計演算法的工作量

√D) 演算法的復雜度包括時間復雜度與空間復雜度

7、下列數據結構中，屬於非線性結構的是

A) 循環隊列 B) 帶鏈隊列 √C) 二叉樹 D) 帶鏈棧

8、一個棧的初始狀態為空。現將元素1、2、3、4、5、A、B、C、D、E依次入棧，然後再依次出棧，則元素出棧的順序是

A) 12345ABCDE √B) EDCBA54321 C) ABCDE12345 D) 54321EDCBA

9、下列敘述中正確的是

A) 循環隊列有隊頭和隊尾兩個指針，因此，循環隊列是非線性結構

B) 在循環隊列中，只需要隊頭指針就能反映隊列中元素的動態變化情況

C) 在循環隊列中，只需要隊尾指針就能反映隊列中元素的動態變化情況

√D) 循環隊列中元素的個數是由隊頭指針和隊尾指針共同決定

10、下列敘述中正確的是

√A) 順序存儲結構的存儲一定是連續的，鏈式存儲結構的存儲空間不一定是連續的

B) 順序存儲結構只針對線性結構，鏈式存儲結構只針對非線性結構

C) 順序存儲結構能存儲有序表，鏈式存儲結構不能存儲有序表

D) 鏈式存儲結構比順序存儲結構節省存儲空間

11、對於循環隊列，下列敘述中正確的是

A) 隊頭指針是固定不變的 B) 隊頭指針一定大於隊尾指針

C) 隊頭指針一定小於隊尾指針 √D) 隊頭指針可以大於隊尾指針，也可以小於隊尾指針

12、下列排序方法中，最壞情況下比較次數最少的是

A) 冒泡排序 B) 簡單選擇排序 C) 直接插入排序 √D) 堆排序

13、下列敘述中正確的是

A) 棧是""先進先出""的線性表 B) 隊列是""先進後出""的線性表

C) 循環隊列是非線性結構 √D) 有序線性表既可以採用順序存儲結構，也可以採用鏈式存儲結構

14、支持子程序調用的數據結構是

√A) 棧 B) 樹 C) 隊列 D) 二叉樹

15、下列數據結構中，能夠按照""先進後出""原則存取數據的是

A) 循環隊列 √B) 棧 C) 隊列 D) 二叉樹

16、下列敘述中正確的是

A) 線性表的鏈式存儲結構與順序存儲結構所需要的存儲空間是相同的

√B) 線性表的鏈式存儲結構所需要的存儲空間一般要多於順序存儲結構

C) 線性表的鏈式存儲結構所需要的存儲空間一般要少於順序存儲結構

17、下列敘述中正確的是

A) 棧是一種先進先出的線性表 B) 隊列是一種後進先出的線性表

C) 棧與隊列都是非線性結構 √D) 棧與隊列都是線性結構

18、一棵完全二叉樹共有360個結點，則在該二叉樹中度為1的結點個數為

A) 0 √B) 1 C) 180 D) 181

19、演算法的時間復雜度是指

A) 設計該演算法所需的工作量 B) 執行該演算法所需要的時間

√C) 執行該演算法時所需要的基本運算次數

D) 演算法中指令的條數

20、下列關於棧敘述正確的是

√A) 棧頂元素最先能被刪除 B) 棧頂元素最後才能被刪除

C) 棧底元素永遠不能被刪除

21、下列敘述中正確的是

A) 在棧中，棧中元素隨棧底指針與棧頂指針的變化而動態變化

B) 在棧中，棧頂指針不變，棧中元素隨棧底指針的變化而動態變化

√C) 在棧中，棧底指針不變，棧中元素隨棧頂指針的變化而動態變化

22、某二叉樹共有7個結點，其中葉子結點只有1個，則該二叉樹的深度為(假設根結點

在第1層)

A) 3 B) 4 C) 6 √D) 7

23、設循環隊列存儲空間為Q(1:50),初始狀態為front=rear=50。經過一系列入隊和退隊操作後，front=rear=25，則該循環隊列中元素個數為

A) 26 B) 25 C) 24 √D) 0或50

24、下列敘述中正確的是

A) 演算法就是程序 B) 設計演算法時只需要考慮數據結構的設計C) 設計演算法時只需要考慮結果的可靠性√D) 以上三種說法都不對

25、下列敘述中正確的是

A) 有一個以上根結點的數據結構不一定是非線性結構

√B) 只有一個根結點的數據結構不一定是線性結構

C) 循環鏈表是非線性結構 D) 雙向鏈表是非線性結構

26、下列關於二叉樹的敘述中，正確的是

A) 葉子結點總是比度為2的結點少一個

√B) 葉子結點總是比度為2的結點多一個

C) 葉子結點數是度為2的結點數的兩倍

D) 度為2的結點數是度為1的結點數的兩倍

27、下列各組的排序方法中，最壞情況下比較次數相同的是

√A) 冒泡排序與快速排序 B) 簡單插入排序與希爾排序

C) 堆排序與希爾排序 D) 快速排序與希爾排序

28、下列敘述中正確的是

A) 循環隊列是隊列的一種鏈式存儲結構

√B) 循環隊列是隊列的一種順序存儲結構

C) 循環隊列是非線性結構 D) 循環隊列是一種邏輯結構

29、下列關於線性鏈表的敘述中，正確的是

A) 各數據結點的存儲空間可以不連續，但它們的存儲順序與邏輯順序必須一致

B) 各數據結點的存儲順序與邏輯順序可以不一致，但它們的存儲空間必須連續

√C) 進行插入與刪除時，不需要移動表中的元素

30、一棵二叉樹共有25個結點，其中5個是葉子結點，則度為1的結點數為

√A) 16 B) 10 C) 6 D) 4

31、設循環隊列存儲空間為Q(1:50)。初始狀態為front=rear=50。經過一系列入隊和退隊操作後，front=14，rear=19，則該循環隊列中的元素個數為

A) 46 B) 45 C) 6 √D) 5

32、下列鏈表中，其邏輯結構屬於非線性結構的是

√A) 二叉鏈表 B) 循環鏈表 C) 雙向鏈表 D) 帶鏈的棧

33、設循環隊列的存儲空間為Q(1: 35)，初始狀態為front=rear=35。現經過一系列入隊與退隊運算後，front=15，rear=15，則循環隊列中的元素個數為

A) 15 B) 16 C) 20 √D) 0或35

34、下列關於棧的敘述中，正確的是

A) 棧底元素一定是最後入棧的元素 B) 棧頂元素一定是最先入棧的元素

√C) 棧操作遵循先進後出的原則

35、設二叉樹共有150個結點，其中度為1的結點有10個，則該二叉樹中的葉子結點數為

A) 71 B) 70 C) 69 √D) 不可能有這樣的二叉樹

36、下列敘述中正確的是

√A) 程序執行的效率與數據的存儲結構密切相關

B) 程序執行的效率只取決於程序的控制結構

C) 程序執行的效率只取決於所處理的數據量

37、下列與隊列結構有關聯的是

A) 函數的遞歸調用 B) 數組元素的引用 C) 多重循環的執行 √D) 先到先服務的作業調度

38、一個棧的初始狀態為空。現將元素1,2,3,A,B,C依次入棧，然後再依次出棧，則元素出棧的順序是

A) 1,2,3,A,B,C B) C,B,A,1,2,3 √C) C,B,A,3,2,1 D) 1,2,3,C,B,A

39、下列敘述中正確的是

A) 一個演算法的空間復雜度大，則其時間復雜度也必定大

B) 一個演算法的空間復雜度大，則其時間復雜度必定小

C) 一個演算法的時間復雜度大，則其空間復雜度必定小

√D) 演算法的時間復雜度與空間復雜度沒有直接關系

40、下列敘述中正確的'是

√A) 循環隊列中的元素個數隨隊頭指針與隊尾指針的變化而動態變化

B) 循環隊列中的元素個數隨隊頭指針的變化而動態變化

C) 循環隊列中的元素個數隨隊尾指針的變化而動態變化

41、一棵二叉樹中共有80個葉子結點與70個度為1的結點，則該二叉樹中的總結點數為

A) 219 √B) 229 C) 230 D) 231

42、對長度為10的線性表進行冒泡排序，最壞情況下需要比較的次數為

A) 9 B) 10 √C) 45 D) 90

43、下列敘述中正確的是

A) 演算法的效率只與問題的規模有關，而與數據的存儲結構無關

√B) 演算法的時間復雜度是指執行演算法所需要的計算工作量

C) 數據的邏輯結構與存儲結構是一一對應的

D) 演算法的時間復雜度與空間復雜度一定相關

44、下列敘述中正確的是

A) 線性表鏈式存儲結構的存儲空間一般要少於順序存儲結構

B) 線性表鏈式存儲結構與順序存儲結構的存儲空間都是連續的

√C) 線性表鏈式存儲結構的存儲空間可以是連續的，也可以是不連續的

45、某二叉樹共有12個結點，其中葉子結點只有1個。則該二叉樹的深度為(根結點在第1層)

A) 3 B) 6 C) 8 √D) 12

46、對長度為n的線性表作快速排序，在最壞情況下，比較次數為

A) n B) n-1 C) n(n-1) √D) n(n-1)/2

47、下列敘述中正確的是

A) 有且只有一個根結點的數據結構一定是線性結構

B) 每一個結點最多有一個前件也最多有一個後件的數據結構一定是線性結構

C) 有且只有一個根結點的數據結構一定是非線性結構

√D) 有且只有一個根結點的數據結構可能是線性結構，也可能是非線性結構

48、下列敘述中錯誤的是

A) 在雙向鏈表中，可以從任何一個結點開始直接遍歷到所有結點

B) 在循環鏈表中，可以從任何一個結點開始直接遍歷到所有結點

√C) 在線性單鏈表中，可以從任何一個結點開始直接遍歷到所有結點

D) 在二叉鏈表中，可以從根結點開始遍歷到所有結點

49、某二叉樹共有13個結點，其中有4個度為1的結點，則葉子結點數為

√A) 5 B) 4 C) 3 D) 2

50、設棧的順序存儲空間為S(1: 50),初始狀態為top=0。現經過一系列入棧與退棧運算後，top=20，則當前棧中的元素個數為

㈣ 計算機二級選擇題干貨（五）——數據結構和演算法

1、線性表、棧和隊列等數據結構所表達和處理的數據以線性結構為組織形式。棧是一種特殊的線性表，這種線性表只能在固定的一端進行插入和刪除操作，允許插入和刪除的一端稱為棧頂，另一端稱為棧底。一個新元素只能從棧頂一端進入，刪除時，只能刪除棧頂的元素，即剛剛被插入的元素。所以棧又稱後進先出表（Last In First Out）；隊列可看作是插入在一端進行，刪除在另一端進行的線性表，允許插入的一端稱為隊尾，允許刪除的一端稱為隊頭。在隊列中，只能刪除隊頭元素，隊列的最後一個元素一定是最新入隊的元素。因此隊列又稱先進先出表（First In First Out）。

2、棧和隊列都是一種特殊的操作受限的線性表，只允許在端點處進行插入和刪除。二者的區別是：棧只允許在表的一端進行插入或刪除操作，是一種"後進先出"的線性表；而隊列只允許在表的一端進行插入操作，在另一端進行刪除操作，是一種"先進先出"的線性表。

3、棧是一種特殊的線性表，這種線性表只能在固定的一端進行插入和刪除操作，允許插入和刪除的一端稱為棧頂，另一端稱為棧底。一個新元素只能從棧頂一端進入，刪除時，只能刪除棧頂的元素，即剛剛被插入的元素。所以棧又稱先進後出表（FILO-First In Last Out）。線性表可以順序存儲，也可以鏈式存儲，而棧是一種線性表，也可以採用鏈式存儲結構。

4、棧和隊列都是一種特殊的操作受限的線性表，只允許在端點處進行插入和刪除。二者的區別是：棧只允許在表的一端進行插入或刪除操作，是一種"後進先出"的線性表；而隊列只允許在表的一端進行插入操作，在另一端進行刪除操作，是一種"先進先出"的線性表。

5、在棧中，棧底指針不變，棧中元素隨棧頂指針的變化而動態變化

top=0表示棧空，top=50表示棧滿。入棧操作首先將top加1，然後將新元素插入到top指針指向的位置；退棧操作首先將top指針指向的元素賦給一個指定的變數，然後將top減1。棧頂指針top動態反映了棧中元素的變化情況。

6、棧是一種先進後出的線性表，棧實際上也是線性表，只不過是一種特殊的線性表。隊列是指允許在一端進行插入、而在另一端進行刪除的線性表，隊列是一種"先進先出"或"後進後出"的線性表

隊列是指允許在一端進行插入、而在另一端進行刪除的線性表。它又稱為"先進先出"或"後進後出"的線性表，體現了"先來先服務"的原則。

7、帶鏈的隊列也是線性鏈表，在線性鏈表中指向線性表中的第一個結點的指針稱為頭指針，頭指針為NULL或0時稱為空表，指向隊尾元素的指針稱為尾指針。隊列在隊尾插入元素，稱為入隊運算；在隊頭刪除元素，稱為退隊運算。帶鏈隊列在開辟存儲空間時，可以按照存儲空間地址增大的方向開辟，也可以按照存儲空間地址減少的方向開辟。

8、所謂循環隊列，就是將隊列存儲空間的最後一個位置繞到第1個位置，形成邏輯上的環狀空間，供隊列循環使用。所以循環隊列還是屬於線性結構。循環隊列的頭指針front指向隊列的第一個元素的前一位置，隊尾指針rear指向隊列的最後一個元素，循環隊列的動態變化需要頭尾指針共同反映循環隊列的長度是：(sq.rear-sq.front+maxsize)%maxsize，所以循環隊列的長度是由隊頭和隊尾指針共同決定的

 在循環隊列中，用隊尾指針rear指向隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置。

 循環隊列主要有兩種基本運算：入隊運算與退隊運算。每進行一次入隊運算，隊尾指針就進一。每進行一次退隊運算，排頭指針就進一。當rear或front的值等於隊列的長度+1時，就將rear或front的值置為1。一般情況下，rear大於front，因為入隊的元素肯定比出隊的元素多。特殊的情況是rear到達數組的上限之後又從數組的低端開始，此時，rear是小於front的。

循環隊列就是將隊列存儲空間的最後一個位置繞到第一個位置，形成邏輯上的環狀空間，供隊列循環使用。在實際應用中，隊列的順序存儲結構一般採用循環隊列的形式。因此，循環隊列不是隊列的一種鏈式存儲結構。循環隊列是一種存儲結構，因此循環隊列是一種物理結構，而不是邏輯結構。循環隊列是隊列的順序存儲結構，因此循環隊列是線性結構。

9、循環隊列不同於循環鏈表，循環隊列是順序存儲結構，循環鏈表是鏈式存儲結構。雙向鏈表是鏈式存儲結構，其中每個結點都有左指針和右指針，不同於二叉樹結點的左子樹指針和右子樹指針。非線性結構和線性結構是數據的邏輯結構，順序和鏈式是數據的存儲結構，例如二叉樹是非線性結構，也可以按照層序進行順序存儲。

10、非線性結構的邏輯特徵是一個結點元素可能對應多個直接前驅和多個後驅。常見的非線性結構有：樹（二叉樹等），圖（網等）。

11、由於二叉樹的存儲結構中每一個存儲結點有兩個指針域，因此，二叉樹的鏈式存儲結構也稱為二叉鏈表，二叉鏈表屬於非線性結構。

12、遍歷是指不重復的訪問所有結點。線性單鏈表每個結點只有一個指針域，由這個指針只能找到後件結點，但不能找到前件結點。雙向鏈表中的每個結點設置兩個指針，左指針指向其前件結點，右指針指向其後件結點。循環鏈表中增加了一個表頭結點，循環鏈表中的所有結點的指針構成了一個環狀鏈。二叉鏈表即二叉樹的鏈式存儲結構，每個存儲結點有兩個指針域，左指針域指向該結點的左子結點的存儲地址，右指針域指向該結點的右子結點的存儲地址。

13、線性表的順序存儲結構具有兩個基本特點：（1）線性表中所有元素所佔的存儲空間是連續的;（2）線性表中各元素在存儲空間中是按邏輯順序依次存放的。

14、循環鏈表具有以下兩個特點：(1)在循環鏈表中增加了一個表頭結點，其數據域為任意或者根據需要來設置，指針域指向線性表的第一個元素的結點。循環鏈表的頭指針指向表頭結點。(2)循環鏈表中最後一個結點的指針域不是空，而是指向表頭結點。即在循環鏈表中，所有結點的指針構成了一個環狀鏈。

15、在循環鏈表中，只要指出表中任何一個結點的位置，就可以從它出發訪問到表中其他所有的結點，而線性單鏈表做不到這一點。

16、根據二叉樹的性質：二叉樹第i（i≥1）層上至多有2i-1個結點。

17、所謂滿二叉樹是指這樣的一種二叉樹：除最後一層外，每層上的所有結點都有兩個子結點。這就是說，在滿二叉樹中，每一層上的結點數都達到最大值，即在滿二叉樹的第K層上有2K-1個結點，且深度為m的滿二叉樹有2m個結點。

18、在任意一顆樹中，結點總數=總分支數目+1

19、二叉樹的性質：在任意一棵二叉樹中，度為0的結點（即葉子結點）總是比度為2的結點多一個。本題中度為2的結點數為n，故葉子結點數為n+1個。

二叉樹的性質：在任意一棵二叉樹中，度為0的結點（即葉子結點）總是比度為2的結點多一個。

20、在用完全二叉樹表示堆，樹中所有非葉子結點值均不小於其左右子樹的根結點值，因此，堆頂元素必為序列的n個元素中的最大項。

21、作為一個演算法，一般應具有以下幾個基本特徵。

 可行性

 確定性

 有窮性

擁有足夠的情報

22、計算機演算法是指解題方案的准確而完整的描述

演算法的有窮性，是指演算法必須在有限的時間內做完，即演算法必須能在執行有限個步驟之後終止。

23、希爾排序法的基本思想是：將整個無序序列分割成若干小的子序列分別進行插入排序。所以希爾排序法屬於插入類排序，但它對簡單插入排序做了很大的改進。

24、快速排序的基本思想是，通過一趟排序將待排序記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，再分別對這兩部分記錄繼續進行排序，以達到整個序列有序；插入排序的基本操作是指將無序序列中的各元素依次插入到已經有序的線性表中，從而得到一個新的序列；選擇排序的基本思想是：掃描整個線性表，從中選出最小的元素，將它交換到表的最前面（這是它應有的位置），然後對剩下的子表採用同樣的方法，直到表空為止；歸並排序是將兩個或兩個以上的有序表組合成一個新的有序表。

25、在單鏈表中，增加頭結點的目的是______。

頭結點不僅標識了表中首結點的位置，而且根據單鏈表（包含頭結點）的結構，只要掌握了表頭，就能夠訪問整個鏈表，因此增加頭結點目的是為了便於運算的實現。

26、演算法分析是指對一個演算法的運行時間和佔用空間做定量的分析，一般計算出相應的數量級，常用時間復雜度和空間復雜度表示。分析演算法的目的就是要降低演算法的時間復雜度和空間復雜度，提高演算法的執行效率。

27、演算法是指解題方案的准確而完整的描述。但演算法不等於程序，也不等於計算方法。當然，程序也可以作為演算法的一種描述，但程序通常還需要考慮很多與方法和分析無關的細節問題，這是因為在編寫程序時要受到計算機系統運行環境的限制。通常，程序的編制不可能優於演算法的設計。作為一個演算法，一般應具有可行性、確定性、有窮性、擁有足夠情報四個基本特徵。因此設計演算法時不僅僅要考慮結果的可靠性，即不僅考慮演算法結果的可行性，還要考慮步驟的確定性，時間和步驟的有窮性等。因此，演算法是一組嚴謹地定義運算順序的規則，並且每一個規則都是有效的，且是明確的，此順序將在有限的次數下終止。

28、一個演算法通常由兩種基本要素組成：一是對數據對象的運算和操作，二是演算法的控制結構。因此設計演算法時不僅需要考慮數據結構的設計，還要考慮數據的操作和運算及各操作之間的執行順序。

29、在有向圖中，若任意兩個頂點都連通，則稱該圖是強連通圖，這樣的有向圖的形狀是環狀，因而至少應有n條邊。

30、當數據表A中每個元素距其最終位置不遠，說明數據表A按關鍵字值基本有序，在待排序序列基本有序的情況下，採用插入排序所用時間最少。

31、數據的邏輯結構在計算機存儲空間中的存放形式稱為數據的存儲結構（也稱數據的物理結構）。

32、假設線性表的長度為n，則在最壞情況下，冒泡排序需要經過n/2遍的從前往後掃描和n/2遍的從後往前掃描，需要比較次數為n(n-1)/2。快速排序法的最壞情況比較次數也是n(n-1)/2

（1）冒泡排序法：是一種最簡單的交換類排序法，它是通過相鄰數據元素的交換逐步將線性表變成有序。假設線性表的長度為n，則在最壞情況下，冒泡排序需要經過n/2遍的從前往後的掃描和n/2遍的從後往前的掃描，需要比較的次數為n(n-1)/2次。

 （2）簡單插入排序法：在簡單插入排序法中，每一次比較後最多移掉一個逆序，因此，這種排序方法的效率與冒泡排序法相同。在最壞情況下，簡單插入排序需要n(n-1)/2次比較。

 （3）簡單選擇排序法：對於長度為n的序列，選擇排序需要掃描n-1遍，每一遍掃描均從剩下的子表中選出最小的元素，然後將該最小的元素與子表中的第一個元素進行交換。簡單選擇排序法在最壞情況下需要比較n(n-1)/2次。

 （4）堆排序法：堆排序的方法為：①首先將一個無序序列建成堆。②然後將堆頂元素（序列中的最大項）與堆中最後一個元素交換（最大項應該在序列的最後）。在最壞情況下，堆排序需要比較的次數為。

 假設線性表的長度為16，那麼冒泡排序、直接插入排序、簡單選擇排序都需要比較120次，而堆排序需要比較64次。

33、對於長度為n的線性表，在最壞的情況下，快速排序所需要的比較次數為n(n-1)/2；冒泡排序所需要的比較次數為n(n-1)/2；直接插入排序所需要的比較次數為n(n-1)/2；堆排序所需要的比較次數為。

34、在進行順序查找過程中，如果線性表中的第一個元素就是被查找元素，則只需做一次比較就查找成功，查找效率最高；但如果被查找的元素是線性表中的最後一個元素，或者被查找的元素根本就不在線性表中，則為了查找這個元素需要與線性表中所有的元素進行比較，這是順序查找的最壞情況。所以對長度為n的線性表進行順序查找，在最壞情況下需要比較n次。

35、二分法查找只適用於順序存儲的有序表。在此所說的有序表是指線性表中的元素按值非遞減排列（即從小到大，但允許相鄰元素值相等）。

二分法檢索要求線性表結點按關鍵值排序且以順序方式存儲。在查找時，首先與表的中間位置上結點的關鍵值比較，若相等則檢索成功；否則根據比較結果確定下一步在表的前半部分或後半部分繼續進行。二分法檢索的效率比較高，設線性表有n個元素，則最多的檢索次數為大於log2n(2為底數)的最小整數，最少的檢索次數為1。

36、一般來說，一種數據的邏輯結構根據需要可以表示成多種存儲結構，常用的存儲結構有順序、鏈接、索引等存儲結構。而採用不同的存儲結構，其數據處理的效率是不同的。

37、順序存儲結構就是用一組地址連續的存儲單元依次存儲該線性表中的各個元素，鏈式存儲結構中各數據結點的存儲序號是不連續的，並且各結點在存儲空間中的位置關系與邏輯關系也不一致。兩者都可以存儲線性的、有序的邏輯結構，順序結構使用的是連續物理空間，鏈式結構可以使用零散的物理空間存儲，鏈式結構更靈活，不存在誰節約空間的說法

38、順序存儲結構中，數據元素存放在一組地址連續的存儲單元中，每個數據元素地址可通過公式LOC(ai)=LOC(a1)+(i-1)L計算得到，從而實現了隨機存取。對於鏈式存儲結構，要對某結點進行存取，都得從鏈的頭指針指向的結點開始，這是一種順序存取的存儲結構。

39、鏈式存儲結構克服了順序存儲結構的缺點：它的結點空間可以動態申請和釋放；它的數據元素的邏輯次序靠結點的指針來指示，不需要移動數據元素。故鏈式存儲結構下的線性表便於插入和刪除操作。

40、線性表的順序存儲結構的存儲空間只用於存放結點數據，而鏈式存儲結構的存儲空間不僅要存放結點數據，還要存放數據的指針，所以線性表的鏈式存儲結構所需要的存儲空間一般要多於順序存儲結構

41、在進行順序查找過程中，如果線性表中的第1個元素就是被查找元素，則只需做一次比較就查找成功，查找效率最高；但如果被查找的元素是線性表中的最後一個元素，或者被查找的元素根本就不在線性表中，則為了查找這個元素需要與線性表中所有的元素進行較，這是順序查找的最壞情況。所以對長度為n的線性表進行順序查找，在最壞情況下需要比較n次

42、對於長度為n的有序線性表，在最壞情況下，二分查找只需要比較 次，而順序查找需要比較n次。二分法查找只適用於順序存儲的有序表，如果採用鏈式存儲結構，也只能用順序查找,所以，對長度為n的有序鏈表進行查找，最壞情況下需要的比較次數為n

43、根據數據結構中各數據元素之間前後件關系的復雜程度，一般將數據結構分為兩大類型：線性結構與非線性結構。

44、如果一個非空的數據結構滿足下列兩個條件：（1）有且只有一個根結點；（2）每一個結點最多有一個前件，也最多有一個後件。則稱該數據結構為線性結構，又稱線性表。

45、有一個以上根結點的數據結構肯定是非線性結構，循環鏈表、雙向鏈表是線性結構；線性表、棧與隊列、線性鏈表都是線性結構，而二叉樹是非線性結構。

46、在鏈表中，如果有兩個結點的同一個指針域的值相等，則該鏈表一定是非線性結構

47、線性表的鏈式存儲結構稱為線性鏈表，為了適應線性表的鏈式存儲結構，計算機存儲空間被劃分為一個一個小塊，每一小塊占若干位元組，通常稱這些小塊為存儲結點。每一個存儲結點分為兩部分：一部分用於存儲數據元素的值，稱為數據域；另一部分用於存放下一個數據元素的存儲序號，即指向後件的結點，稱為指針域。在鏈式存儲結構中，存儲數據結構的存儲空間可以不連續，各數據結點的存儲順序與數據元素之間的邏輯關系可以不一致。為了要在線性鏈表中插入一個新元素，首先要給該元素分配一個新結點，以便用於存儲該元素的值，然後將存放新元素值的結點鏈接到線性表中指定的位置。在線性鏈表的插入過程中不發生數據無素移動的現象，只需改變有關結點的指針即可，從而提高了插入的效率。為了在線性鏈表中刪除包含指定元素的結點，首先要在線性鏈表中找到這個結點，然後將要刪除結點放回到可利用棧。在線性鏈表中刪除一個元素後，不需要移動表的數據元素，只需改變被刪元素所在結點的前一個結點的指針域即可。因此，進行插入與刪除時，不需要移動表中的元素。

48、在先左後右的原則下，根據訪問根結點的次序，二叉樹的遍歷可以分為3種：前序遍歷、中序遍歷和後序遍歷。

前序遍歷是指在訪問根結點、遍歷左子樹與遍歷右子樹這三者中，首先訪問根結點，然後遍歷左子樹，最後遍歷右子樹；並且遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹。

後序遍歷指在訪問根結點、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然後遍歷右子樹，最後訪問根結點；並且遍歷左、右子樹時，仍然先遍歷左子樹，然後遍歷右子樹，最後訪問根結點。

二叉樹的中序遍歷指在訪問根結點、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹；並且遍歷左、右子樹時，仍然先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。

49、鏈表有線性鏈表，也有非線性鏈表。線性鏈表和二叉樹鏈表的結點都有兩個指針域，前者是線性結構，後者是非線性結構。線性單鏈表中的結點只有一個指針，葉子結點一般是對樹結構而言，樹結構是非線性結構，不是線性表。

50、演算法的復雜度主要包括時間復雜度和空間復雜度：演算法在運行過程中需輔助存儲空間的大小稱為演算法的空間復雜度；演算法的時間復雜度是指執行演算法所需要的計算工作量，即演算法執行過程中所需要的基本運算次數，為了能夠比較客觀地反映出一個演算法的效率，在度量一個演算法的工作量時，不僅應該與所使用的計算機、程序設計語言以及程序編制者無關，而且還應該與演算法實現過程中的許多細節無關。為此，可以用演算法在執行過程中所需基本運算的執行次數來度量演算法的工作量。二者沒有直接關系。

51、一個演算法的空間復雜度，一般是指執行這個演算法所需要的內存空間。一個演算法所佔用的存儲空間包括程序所佔的空間、輸入的初始數據所佔的存儲空間以及演算法執行過程中所需要的額外空間。其中額外空間包括演算法程序執行過程中的工作單元以及某種數據結構所需要的附加存儲空間。如果額外空間相對於問題規模來說是常數，則稱該演算法是原地(in place)工作的。

52、我們通常用時間復雜度和空間復雜度來衡量演算法效率，演算法的時間復雜度是指執行演算法所需要的計算工作量；演算法所執行的基本運算次數與問題的規模有關，而一個演算法的空間復雜度，一般是指執行這個演算法所需要的內存空間；一般來說，一種數據的邏輯結構根據需要可以表示成多種存儲結構。

所謂演算法的時間復雜度，是指執行演算法所需要的計算工作量。為了能夠比較客觀地反映出一個演算法的效率，在度量一個演算法的工作量時，不僅應該與所使用的計算機、程序設計語言以及程序編制者無關，而且還應該與演算法實現過程中的許多細節無關。為此，可以用演算法在執行過程中所需基本運算的執行次數來度量演算法的工作量。

53、子程序調用是一種層次關系，子程序調用功能模塊，調用功能模塊的個數也不確定，可以是一個，也可以是多個。二叉樹是一種很有用的非線性結構，二叉樹不同於樹形結構。二叉樹具有以下兩個特點：①非空二叉樹只有一個根結點；②每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。選項D規定每個結點只能有兩個後件。在子程序調用中，調用的功能模塊可以是多個，可以調用超過兩個功能模塊。

54、結構圖的深度表示控制的層數結構圖的深度表示控制的層數

55、數據結構是指反映數據元素之間關系的數據元素集合的表示。更通俗地說，數據結構是指帶有結構的數據元素的集合。所謂結構實際上就是指數據元素之間的前後件關系。線性結構與非線性結構都可以是空的數據結構。一個空的數據結構究竟是屬於線性結構還是屬於非線性結構，還要根據具體情況來確定。如果對該數據結構的運算是按線性結構的規則來處理的，則屬於線性結構；否則屬於非線性結構。

㈤ 設計演算法時只需要考慮結果的可靠性 對嗎

程序=數據結構+演算法。你找一本演算法書看看，就知道什麼是演算法了。可以看看《演算法導論》（有一定的難度）很不錯的。比如分治演算法，動態規劃，搜索演算法，回溯，貪心演算法，這些都是經典的演算法，學好之後你就發現你的編程能力上了一個高度的。演算法的學習需要花費大量的精力，冰凍三尺非一日之寒。

㈥ 設計演算法的原則

設計演算法的原則：

1、正確性：演算法的正確性是指演算法至少應該具有輸入、輸出和加工處理無歧義性、能正確反映問題的需要、能夠得到問題的正確答案。

2、可讀性：設計演算法的目的，一方面是為了讓計算機執行，但還有一個重要的目的就是為了便於他人的閱讀，讓人理解和交流，自己將來也可閱讀。如果可讀性不好，時間長了自己都不知道寫了什麼，可讀性是評判演算法（也包括實現它的程序代碼）好壞很重要的標志。

3、健壯性：當輸入的數據非法時，演算法應當恰當地做出反應或進行相應處理，而不是莫名其妙的輸出結果。並且處理出錯的方法不應是中斷程序的執行，而應是返回一個表示錯誤或錯誤性質的值，以便於在更高的抽象層次上進行處理。

4、高效率與低存儲量：通常，演算法的效率指的是演算法的執行時間；演算法的存儲量指的是演算法執行過程中所需要的最大存儲空間，兩者的復雜度都與問題的規模有關。演算法分析的任務是對設計的每一個具體的演算法，利用數學工具，討論其復雜度，探討具體演算法對問題的適應性。

(6)二級試題演算法設計只考慮什麼擴展閱讀：

演算法的「正確」通常在用法上有很大的差別，大體分為以下4個層次：

1、演算法程序沒有語法錯誤；

2、演算法程序能夠根據正確的輸入的值得到滿足要求的輸出結果；

3、演算法程序能夠根據錯誤的輸出的值滿足規格說明的輸出結果；

4、演算法程序對於精心設計、極其刁難的測試數據都能滿足要求的輸出結果。

對於這4層含義，層次要求最低，因為僅僅沒有語法錯誤實在談不上是好的演算法。而層次（4）是最困難的，人們幾乎不可能逐一驗證所有的輸入都得到正確的結果。因此，演算法的正確性在大部分情況下都不可能用程序來證明，而是用數學方法證明的。

㈦ 演算法設計原則是什麼

原則：首先說設計的演算法必須是"正確的"，其次應有很好的"可讀性"，還必須具有"健壯性"，最後應考慮所設計的演算法具有"高效率與低存儲量"。

所謂演算法是正確的，除了應該滿足演算法說明中寫明的"功能"之外，應對各組典型的帶有苛刻條件的輸入數據得出正確的結果。

在演算法是正確的前提下，演算法的可讀性是擺在第一位的，這在當今大型軟體需要多人合作完成的環境下是換重要的，另一方面，晦澀難讀的程序易於隱藏錯誤而難以調試。演算法的效率指的是演算法的執行時間，演算法的存儲量指的是演算法執行過程中所需最大存儲空間。

演算法是程序設計的另一個不可缺的要素，因此在討論數據結構的同時免不了要討論相應的演算法。這里有兩重意思，即演算法中的操作步驟為有限個，且每個步驟都能在有限時間內完成。

確定性表現在對演算法中每一步的描述都沒有二義性，只要輸入相同，初始狀態相同，則無論執行多少遍，所得結果都應該相同。

可行性指的是，序列中的每個操作都是可以簡單完成的，其本身不存在演算法問題，例如，"求x和y的公因子"就不夠基本。

輸入值即為演算法的操作對象，但操作的對象也可以由演算法自身生成，如"求100以內的素數"，操作對象是自然數列，可以由變數逐個增1生成。

演算法的健壯性指的是，演算法應對非法輸入的數據作出恰當反映或進行相應處理，一般情況下，應向調用它的函數返回一個表示錯誤或錯誤性質的值。

㈧ 19年3月二級C--數據結構與演算法

1.假設線性表的長度為n，則最壞情況下:

冒泡排序: 需要經過n/2遍的從前往後掃描和n/2遍從後往前掃描，需要比較的次數為n(n-1)/2。總的時間復雜度為O(n的平方)。

快速排序: 比較次數也是n(n-1)/2。總的時間復雜度為O(n的平方)。

直接插入排序: 所需要比較的次數為n(n-1)/2。總的時間復雜度為O(n的平方)。

希爾排序所需要比較的次數為O(n的1.5次方)。(時間復雜度小於以上三種)

堆排序: 最壞情況下，其時間復雜度為O(nlogn)。(小於O(n的平方))。

2.根據數據結構中各元素之間前後關系的復雜程度，一般數據結構分為兩大類: 線性結構和非線性結構。

如果一個非空的數據結構滿足下列兩個條件，①有且只有一個根結點 ②每個結點最多有一個前件，也最多有一個後件。則稱該數據結構為線性結構，又稱線性表。

3.演算法時間復雜度與空間復雜度沒有關系。

4.所謂演算法的時間復雜度，是指執行演算法所需要的計算工作量。

為了能夠比較客觀的反映出一個演算法的效率，在度量一個演算法的工作量時，不僅應該與所用的計算機程序設計語言，以及程序編制者無關，而且還應該與演算法實現過程中的許多細節無關。

5.同一問題可用不同演算法解決，而一個演算法的質量優劣將影響到演算法乃至程序的效率。

演算法分析的目的在於選擇合適演算法和改進演算法。

6.堆排序在平均情況下的時間復雜度與最壞情況下的時間復雜度都是O(nlogn)。

7.二叉鏈表: 以二叉鏈表作為樹的存儲結構。鏈表中結點的兩個鏈域分別指向該結點的第一個孩子結點和第一個孩子下的一個兄弟結點。

  循環鏈表是鏈式存儲結構，循環隊列是線性存儲結構。( 【×】循環鏈表是循環隊列的鏈式存儲結構)

  雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點都有兩個指針，分別指向直接後繼和直接前驅，所以從雙鏈表中的任意一個結點開始都可以很方便地訪問它的前驅結點和後繼結點。

8.數據的邏輯結構由兩個要素: 一是數據元素的集合，通常記為D。二是D上的關系，它反映了D中各元素之間的前後件關系，通常記為R。

即一個數據結構可以表示成B=(D,R)，其中B表示數據結構，為了反映D中各元素之間的前後件關系，一般用二元組來表示。例如，假如a與b是D中的兩個數據，則二元組表示a是b的前件，b是a的後件。

  線性結構用圖形表示更加直觀。例如: R=｛(5,1)，(7,9)，(1,7)，(9,3)｝，結構為: 5→1→7→9→3

9.快速排序法是一種互換類的排序方法，但由於比冒泡排序的速度快，因此稱為快速排序。

其基本思想是從線性表中選擇一個元素設為t，將線性表後面小於t的元素移到前面，而前面大於t的元素移到後面，結果就將線性表分成了兩部分，t插入到分界線的位置處，這個過程稱為線性表的分割。

  簡單插入排序法，是指將無序序列中的各元素依次插入到已經有序的線性表中。

  冒泡排序法是一種最簡單的交換類排序方法，它是通過相鄰數據元素的交換，逐步將線性表變為有序。

  後兩種元素的移動過程中不會產生新的逆序。

10.程序可作為演算法的一種描述。

11.為了降低演算法的空間復雜度，要求演算法盡量採用原地工作，所謂的原地工作是指執行演算法時所使用的額外空間固定。

  一個演算法的空間復雜度一般是指執行這個演算法所需要的內存空間，一個演算法所佔用的存儲空間包括程序所佔的空間，輸入的初始數據所佔的空間以及演算法執行過程中所需要的額外空間。

12.能從任意一個結點開始沒有重復的掃描到所有結點的數據結構是循環鏈表。

13.循環隊列是隊列的一種存儲結構

14.演算法的設計要求包括效率與低存儲量，即要考慮演算法的時間復雜度與空間復雜度。

  演算法的復雜度包括時間復雜度和空間復雜度。

  時間復雜度: 是指執行演算法所需要的計算工作量。

  空間復雜度: 一般是指執行這個演算法所需要的內存空間。

15.棧是一種特殊的線性表。鏈式結構把每一個存儲結點分為數據域與指針域，帶鏈的棧可以通過指針域的變化改變原有的棧的組織數據原則; 而順序棧的棧底指針不變，棧頂指針改變。

16.堆排序在最壞的情況下需要比較nlogn次。

  快速排序，在最壞情況下需要比較n(n-1)/2次。

  順序查找，在最壞情況下需要比較n次。

  最壞情況下，二分查找需要log2n(小於n-1)

  在長度為n的順序表中尋找最大項/最小項時，比較次數最少為1，最多為n-1。

17.如果一個非空的數據結構滿足下列兩個條件，①有且只有一個根節點 ②每一個結點最多有一個前件，也最多有一個後件，則稱該數據結構為線性結構。如果一個數據結構不是線性結構，則稱為非線性結構。

18.帶鏈棧空的條件是 top=bottom=NULL

19.滿二叉樹也是完全二叉樹，完全二叉樹不一定是滿二叉樹。對於滿二叉樹和完全二叉樹來說，可以按照程序進行順序存儲，不僅節省了空間，又能方便地確定每一個結點的父結點等於左右子結點的位置，但順序存儲結構對於一般的二叉樹不適用。

20.帶鏈棧隊頭指針與隊尾指針相同，且不為空時，隊列元素個數為1; 若為空時，隊列元素個數為0。

帶鏈棧的棧底指針是隨棧的操作而動態變化的。

21.二叉樹的鏈式存儲結構，也稱為二叉鏈表。在二叉樹中，由於每一個元素可以有兩個後件，因此用於存儲二叉樹的存儲結點的指針域有兩個，所以二叉鏈表屬於非線性結構。

22.線性表由一組元素數據元素構成，各元素的數據類型必須相同，矩陣是一個比較復雜的線性表，線性表除了插入和刪除運算之外，還可以查找，排序，分解，合並等。數組是長度固定的線性表。

23.冒泡排序中，在互換兩個相鄰元素時，只能消除一個逆序; 快速排序及希爾排序中，一次交換可以消除多個逆序。

24.二分法檢索的效率比較高，設線性表有n個元素，則最多的比較次數為log2n，最少檢索次數為1。

25.循環鏈表的結構具有以下兩個特點。一，在循環鏈表中，增加了一個表頭結點，其數據域為任意或者根據需要來設置指針域指向線性表的第一個元素的結點。循環鏈表的頭指針指向表頭結點。二、循環鏈表中最後一個節點的指針域不是空，而是指向表頭結點，即在循環鏈表中所有的結點指針構成一個環狀鏈。

26.二叉樹的存儲結構是非線性結構，而完全二叉樹是特殊形態的二叉樹。採用順序存儲的完全二叉樹屬於非線性結構。

27.時間復雜度和計算機運行速度以及存儲空間無關。

演算法的空間復雜度和存儲結構無關。

數據處理效率與數據的存儲結構有關。

28.線性表，向量，棧，隊列都屬於線性結構的順序存儲。

29.循環隊列是隊列的存儲結構。

  循環鏈表是另一種形式的念式存儲結構。

  (✘循環鏈表是循環隊列的鏈式存儲結構。✘)

30.完全二叉樹的總結點為奇數時，葉子結點是總結點加一再除以二。

31.在實際處理中，可以用一位數組來存儲堆序列中的元素，也可以用完全二叉樹來直觀的表示堆的結構。在用完全二叉樹表示堆時，樹中所有非葉子結點值均不小於其左，右子樹的根結點值，因為堆頂元素必須為序列的n個元素的最大項，因此其中序並不是有序序列。

  多重鏈表指表中每個結點由兩個或兩個以上的指針域的鏈表。如果一個非空的數據結構滿足下列兩個條件，①有且只有一個根結點，②每個結點最多有一個前件，也最多有一個後件，則稱該數據結構為線性結構，所以多重鏈表不一定是非線性結構。

  在計算機中二叉樹通常採用鏈式存儲結構，對於滿二叉樹和完全二叉樹來說，可以按層次進行順序存儲。

  排序二叉樹的中序遍歷序列是有序序列。

32.對於一個固定的規模，演算法所執行的基本運算次數還可能與特定的輸入有關。

33.在線性表中尋找最大項時，平均情況下和最壞情況下比較次數都是n-1。

34.在長度為n的順序表中查找一 個元素， 假沒需要查找的元素有一半的機會在表中，並且如果元素在表中，則出現在表中每個位置上的可能性是相

同的。則在平均情況下需要比較的次數大約為_

A.3n/4    B.n    C.n/2  D.n/4

本題的考查知識點是順序表的存儲結構。

因為需要查找的元素有一半機會在表中，所以二分之一的情況下平均比較次數為n/2，另二分之一的情況下平均比較次數為n。總的平均比較次數為(n/2+n) /2-3n/4。

故本題答案為A。

35.設數據結構B=(D, R)，其中

D={a,b,c,d，e，f}

R={(a，b)，(b，c)，(c，d)，(d，e)，(e，f)，(f,a)}該數據結構為

A.線性結構    B.循環隊列

C.循環鏈表    D.非線性結構

本題的考查知識點是數據結構。

如果一個非控的數據結構滿足下列兩個條件: 1) 有且只有一個根節點; 2) 每一一個結點最多有一一個前件，也最多有一一個後件。則稱該數據結構為線性結構。如果一個數據結構不是線性結構，則稱之為非線性結構。

數據結構B=(D, R)中， 每一個結點均有一個前件，不符合「有且只有一個根節點」的條件，所以為非線性結構。故本題答案選D。

36.某帶鏈的隊列初始狀態為front=rear=NULL。經過一系列正常的入隊與退隊操作後，front=rear=10。 該隊列中的元素個數為_

A.1    B.0    C.1或0    D.不確定

本題的考查知識點是帶鏈隊列。

在初始狀態為front=rear=NULL的帶鏈隊列入隊時，如果插入的結點既是隊首結點又是隊尾結點，則rear和front同時指向這個結點;否則在循環隊列的隊尾加入一一個新元素，rear指向新增結點的數據域，rear+1, front不變。 退隊時，在循環隊列的排頭位置退出一個元素並賦給指定的變數，front指向第二個結點的數據域，front+1, rear不變。當front=rear=10時， front和rear同時指向這個唯一 元素，所以該隊列中的元素個數為1。

故本題答案為A。

37.若二叉樹沒有葉子結點，則為空二叉樹。

38.某帶鏈棧的初始狀態為top=bottom=NULL, 經過一系列正 常的入棧與退棧操作後，top=10, bottom=20。 該棧中的元素個數為_____。

A.不確定    B. 10    C.1    D.0

本題考查的知識點是棧。

帶鏈的棧是具有棧屬性的鏈表，線性鏈表的存儲單元是不連續的，為把存儲空間中一-些離散的空閑存 儲結點利用起來，把所有空閑的結點組織成一個帶鏈的棧，稱為可利用棧。

線性鏈表執行刪除操作運算時， 被刪除的結點可以」回收到可利用棧，對應於可利用棧的入棧運算;線性鏈表執行插入運算時，需要一個新的結點，可以在可利用棧中取棧頂結點，對應於可利用棧的退棧運算。

可利用棧的入棧運算和退棧運算只需要改動top指針即可。因為是不連續的存儲空間，所以top指針將不會有規律地連續變化，因此無法據此判斷棧中的元素個數。

所以本題答案為A。

㈨ 9月計算機二級MSOffice高級應用試題「經典」

2017年9月計算機二級MSOffice高級應用試題「經典」

隨著移動互聯網科技的發展，蘋果公司重新定義了手機，手機開始逐漸具備電腦的功能，辦公軟體率先出現在了諾基亞的塞班系統和iPhone的手機系統。下面是我收集的關於計算機二級MSOffice高級應用試題，希望大家認真練習!

一、選擇題(每小題1分。共20分)

1.下列敘述中正確的是()。

A.演算法就是程序

B.設計演算法時只需要考慮數據結構的設計

C.設計演算法時只需要考慮結果的可靠性

D.以上三種說法都不對

2.下列敘述中正確的是()。

A.有一個以上根結點的數據結構不一定是非線性結構

B.只有一個根結點的數據結構不一定是線性結構

C.循環鏈表是非線性結構

D.雙向鏈表是非線性結構

3.下列關於二叉樹的敘述中，正確的是()。

A.葉子結點總是比度為2的結點少一個

B.葉子結點總是比度為2的結點多一個

C.葉子結點數是度為2的結點數的兩倍

D.度為2的結點數是度為1的結點數的兩倍

4.軟體生命周期中的活動不包括()。

A.市場調研

B.需求分析

C.軟體測試

D.軟體維護

5.假設某台式計算機的內存儲器容量為256MB，硬碟容量為40GB，硬碟的容量是內存容量的()。

A.200倍

B.160倍

C.120倍

D.100倍

6.程序調試的.任務是()。

A.設計測試用例

B.驗證程序的正確性

C.發現程序中的錯誤

D.診斷和改正程序中的錯誤

7.下列關於資料庫設計的敘述中，正確的是()。

A.在需求分析階段建立數據字典

B.在概念設計階段建立數據字典

C.在邏輯設計階段建立數據字典

D.在物理設計階段建立數據字典

8.資料庫系統的三級模式不包括()。

A.概念模式

B.內模式

C.外模式

D.數據模式

9.一般而言，Internet環境中的防火牆建立在()。

A.每個子網的內部

B.內部子網之間

C.內部網路與外部網路的交叉點

D.以上3個都不對

10.下列選項中屬於面向對象設計方法主要特徵的是()。

A.繼承

B.自頂向下

C.模塊化

D.逐步求精

二、宇處理題(共30分)

請在【答題】菜單下選擇【進入考生文件夾】命令，並按照題目要求完成下面的操作。

注意：以下的文件必須都保存在考生文件夾[%USER%]下。

在考生文件夾下打開文檔WORD.DOCX。

【背景素材】

為了更好地介紹公司的服務與市場戰略，市場部助理小王需要協助製作完成公司戰略規劃文檔，並調整文檔的外觀與格式。

現在，請你按照如下需求，在Word.docx文檔中完成製作工作：

(1)調整文檔紙張大小為A4幅面，紙張方向為縱向;並調整上、下頁邊距為2.5厘米，左、右頁邊距為3.2厘米。

(2)打開考生文件夾下的“word一樣式標准.docx”文件，將其文檔樣式庫中的“標題1，標題樣式一”和“標題2，標題樣式二”復制到Word.docx文檔樣式庫中。

(3)將Word.docx文檔中的所有紅顏色文欄位落應用為“標題1，標題樣式一”段落樣式。

(4)將Word.docx文檔中的所有綠顏色文欄位落應用為“標題2，標題樣式二”段落樣式。

(5)將文檔中出現的全部“軟回車”符號(手動換行符)更改為“硬回車”符號(段落標記)。

(6)修改文檔樣式庫中的“正文”樣式，使得文檔中所有正文段落首行縮進2個字元。

(7)為文檔添加頁眉，並將當前頁中樣式為“標題l，標題樣式一”的文字自動顯示在頁眉區域中。

(8)在文檔的第4個段落後(標題為“目標”的段落之前)插入一個空段落，並按照下面的數據方式在此空段落中插入一個折線圖圖表，將圖表的標題命名為“公司業務指標”。

銷售額成本利潤

2010年4.32.41.9

2011年6.35.11.2

2012年5.93.62.3

2013年7.83.2 4.6

三、電子表格題(共30分)

請在【答題】菜單下選擇【進入考生文件夾】命令，並按照題目要求完成下面的操作。

注意：以下的文件必須都保存在考生文件夾[%USER%]下。

在考生文件夾下打開文檔EXCEL.XLSX。

【背景素材】

財務部助理小王需要向主管匯報2013年度公司差旅報銷情況，現在請按照如下需求，在EXCEL.XLSX文檔中完成工作：

(1)在“費用報銷管理”工作表“日期”列的所有單元格中，標注每個報銷日期屬於星期幾，例如日期為“2013年1月20日”的單元格應顯示為“2013年1月20日星期日”，日期為“2013年1月21日”的單元格應顯示為“2013年1月21日星期一”。

(2)如果“日期”列中的日期為星期六或星期日，則在“是否加班”列的單元格中顯示“是”，否則顯示“否”(必須使用公式)。

(3)使用公式統計每個活動地點所在的省份或直轄市，並將其填寫在“地區”列所對應的單元格中，例如“北京市”、“浙江省”。

(4)依據“費用類別編號”列內容，使用VLOOKUP函數，生成“費用類別”列內容。對照關系參考“費用類別”工作表。

(5)在“差旅成本分析報告”工作表B3單元格中，統計2013年第二季度發生在北京市的差旅費用總金額。

(6)在“差旅成本分析報告”工作表B4單元格中，統計2013年員工錢順卓報銷的火車票費用總額。

(7)在“差旅成本分析報告”工作表B5單元格中，統計2013年差旅費用中，飛機票費用占所有報銷費用的比例，並保留2位小數。

(8)在“差旅成本分析報告”工作表B6單元格中，統計2013年發生在周末(星期六和星期日)的通訊補助總金額。

四、演示文稿題(共20分)

請在【答題】菜單下選擇【進入考生文件夾】命令，並按照題目要求完成下面的操作。

注意：以下的文件必須都保存在考生文件夾[%USER%]下。

【背景素材】

校攝影社團在今年的攝影比賽結束後，希望可以藉助PowerPoint將優秀作品在社團活動中進行展示。

這些優秀的攝影作品保存在考試文件夾中，並以Photo(1).jpg～Photo(12).jpg命名。

現在，請你按照如下需求，在PowerPoint中完成製作工作：

(1)利用PowerPoint應用程序創建一個相冊，並包含Photo(1).jpg～Photo(12).jpg共12幅攝影作品。 在每張幻燈片中包含4張圖片，並將每幅圖片設置為“居中矩形陰影”相框形狀。

(2)設置相冊主題為考試文件夾中的“相冊主題.pptx”樣式。

(3)為相冊中每張幻燈片設置不同的切換效果。

(4)在標題幻燈片後插入一張新的幻燈片，將該幻燈片設置為“標題和內容”版式。在該幻燈片的標題位置輸入“攝影社團優秀作品賞析”;並在該幻燈片的內容文本框中輸入3行文字，分別為“湖光春色”、“冰消雪融”和“田園風光”。

(5)將“湖光春色”、“冰消雪融”和“田園風光”3行文字轉換為樣式為“蛇形圖片題注列表”的SmartArt對象，並將Photo(1).jpg、Photo(6).jpg和Photo(9).jP9定義為該SmartArt對象的顯示圖片。

(6)為SmartArt對象添加自左至右的“擦除”進入動畫效果，並要求在幻燈片放映時該SmartArt對象元素可以逐個顯示。

(7)在SmartArt對象元素中添加幻燈片跳轉鏈接，使得單擊“湖光春色”標注形狀可跳轉至第3張幻燈片，單擊“冰消雪融”標注形狀可跳轉至第4張幻燈片，單擊“田園風光”標注形狀可跳轉至第5張幻燈片。

(8)將考試文件夾中的“ELPHRG01.wav”聲音文件作為該相冊的背景音樂，並在幻燈片放映時即開始播放。

(9)將該相冊保存為“PowerPoint.pptx”文件。

㈩ 計算機二級考試考什麼內容啊

因為你沒有具體指出你要考哪門課程，C、C++、JAVA、Visual Basic，Access 還是Visual FoxPro ？？

全國計算機等級考試二級公共基礎知識
基本要求
1. 掌握演算法的基本概念。
2. 掌握基本數據結構及其操作。
3. 掌握基本排序和查找演算法。
4. 掌握逐步求精的結構化程序設計方法。
5. 掌握軟體工程的基本方法，具有初步應用相關技術進行軟體開發的能力。
6. 掌握數據的基本知識，了解關系資料庫的設計。

考試內容
一、 基本數據結構與演算法
1. 演算法的基本概念；演算法復雜度的概念和意義（時間復雜度與空間復雜度）。
2. 數據結構的定義；數據的邏輯結構與存儲結構；數據結構的圖形表示；線性結構與非線性結構的概念。
3. 線性表的定義；線性表的順序存儲結構及其插入與刪除運算。
4. 棧和隊列的定義；棧和隊列的順序存儲結構及其基本運算。
5. 線性單鏈表、雙向鏈表與循環鏈表的結構及其基本運算。
6. 樹的基本概念；二叉樹的定義及其存儲結構；二叉樹的前序、中序和後序遍歷。
7. 順序查找與二分法查找演算法；基本排序演算法（交換類排序，選擇類排序，插入類排序）。
二、 程序設計基礎
1. 程序設計方法與風格。
2. 結構化程序設計。
3. 面向對象的程序設計方法，對象，方法，屬性及繼承與多態性。
三、 軟體工程基礎
1. 軟體工程基本概念，軟體生命周戎概念，軟體工具與軟體開發環境。
2. 結構化分析方法，數據流圖，數據字典，軟體需求規格說明書。
3. 結構化設計方法，總體設計與詳細設計。
4. 軟體測試的方法，白盒測試與黑盒測試，測試用例設計，軟體測試的實施，單元測試、集成測試和系統測試。
5. 程序的調試，靜態調試與動態調試。
四、 資料庫設計基礎
1. 資料庫的基本概念：資料庫，資料庫管理系統，資料庫系統。
2. 數據模型，實體聯系模型及E-R圖，從E-R圖導出關系數據模型。
3. 關系代數運算，包括集合運算及選擇、投影、連接運算，資料庫規范化理論。
4. 資料庫設計方法和步驟：需求分析、概念設計、邏輯設計和物理設計的相關策略。

考試方式
1、 公共基礎的考試方式為筆試，與C語言（VisualBASIC、Visual FoxPro、Java、Access、Visual C++）的筆試部分合為一張試卷。公共基礎部分佔全卷的30分。
2、 公共基礎知識有10道選擇題和5道填空題。

參考網站：
全國計算機等級考試二級C考試大綱
http://ncre.csai.cn/ncredg/200605160849041980.htm

全國計算機等級考試二級Access語言考試大綱
http://ncre.csai.cn/ncredg/200605170846131747.htm

全國計算機等級考試二級Java考試大綱
http://ncre.csai.cn/ncredg/200605160911201577.htm

全國計算機等級考試二級C++考試大綱
http://ncre.csai.cn/ncredg/200605160915441498.htm

全國計算機等級考試二級VB考試大綱
http://ncre.csai.cn/ncredg/200605160904311624.htm

全國計算機等級考試二級VFP考試大綱
http://ncre.csai.cn/ncredg/200605170854421935.htm

另外，還有可以上http://ncre.csai.cn 上去看看，這上面有很多計算機二級的相關資源，可以參考。

參考：網路