一、選擇題(1)～(35)每小題2分，共70分)
下列各題A)、B)、c)、D)四個選項中，只有一個選項是正確的，請將正確選項涂寫在答題卡相應位置上，答在試卷上不得分。．
(1)下面敘述正確的是_________。
A)算法的執(zhí)行效率與數(shù)據(jù)的存儲結(jié)構無關
B)算法的空間復雜度是指算法程序中指令(或語句)的條數(shù)
C)算法的有窮性是指算法必須能在執(zhí)行有限個步驟之后終止
D)算法的時間復雜度是指執(zhí)行算法程序所需要的時間
答案：C
評析：算法的設計可以避開具體的計算機程序設計語言，但算法的實現(xiàn)必須借助程序設計語言中提供的數(shù)據(jù)類型及其算法。數(shù)據(jù)結(jié)構和算法是計算機科學的兩個重要支柱。它們是一個不可分割的整體。算法在運行過程中需輔助存儲空間的大小稱為算法的空間復雜度。算法的有窮性是指一個算法必須在執(zhí)行有限的步驟以后結(jié)束。算法的時間復雜度是指執(zhí)行算法所需要的計算工作量，即算法執(zhí)行過程中所需要的基本運算次數(shù)。
(2)以下數(shù)據(jù)結(jié)構屬于非線性數(shù)據(jù)結(jié)構的是_________。
A)隊列 B)線性表 C)二叉樹 D)棧
答案：C
評析：線性表、棧和隊列等數(shù)據(jù)結(jié)構所表達和處理的數(shù)據(jù)以線性結(jié)構為組織形式。棧是一種特殊的線性表，這種線性表只能在固定的一端進行插入和刪除操作，允許插入和刪除的一端稱為棧項，另一端稱為棧底。一個新元素只能從棧頂一端進入，刪除時，只能刪除棧項的元素，即剛剛被插入的元素。所以棧又稱后進先出表(Last In First Out)：隊列可看作是插入在一端進行，刪除在另一端進行的線性表，允許插入的一端稱為隊尾，允許刪除的一端稱為隊頭。在隊列中，只能刪除隊頭元素，隊列的最后一個元素一定是最新入隊的元素。因此隊列又稱先進先出表(First In First Out)。
(3)在一棵二叉樹上第8層的結(jié)點數(shù)最多是_________。
A)8 B)16 C)128 D)256
答案：C
評析：根據(jù)二叉樹的性質(zhì)：二叉樹第i(i>1)層上至多有2卜’個結(jié)點。得到第8層的結(jié)點數(shù)最多是128。
(4)下面描述中，不符合結(jié)構化程序設計風格的是_________。
A)使用順序、選擇和重復(循環(huán))三種基本控制結(jié)構表示程序的控制邏輯
B)白頂向下
C)注重提高程序的執(zhí)行效率
D)限制使用goto語句
答案：C
評析：結(jié)構化程序設計方法的四條原則是：1．自頂向下；2．逐步求精：3．模塊化；4．限制使用goto語句。"自頂向下"是說，程序設計時，應先考慮總體，后考慮細節(jié)；先考慮全局目標，后考慮局部目標；"逐步求精"是說，對復雜問題，應設計一些子目標，作過渡j逐步細節(jié)化；"模塊化"是說，一個復雜問題，肯定是由若干稍簡單的問題構成：解決這個復雜問題的程序，也應對應若干稍簡單的問題，分解成若干稍小的部分。
(5)下面概念中，不屬于面向?qū)ο蠓椒ǖ氖莀________。
A)對象、消息 B)繼承、多態(tài)
C)類、封裝 D)過程調(diào)用
答案：D
評析：面向?qū)ο蠓椒ㄊ且环N運用對象、類、封裝、繼承、多態(tài)和消息等概念來構造、測試、重構軟件的方法。面向?qū)ο蠓椒◤膶ο蟪霭l(fā)，發(fā)展出對象，類，消息，繼承等概念。
(6)在結(jié)構化方法中，用數(shù)據(jù)流程圖(DFD)作為描述工具的軟件開發(fā)階段是________。
A)可行性分析 B)需求分析
C)詳細設計 D)程序編碼
答案：B
評析：軟件開發(fā)階段包括需求分析、總體設計、詳細設計、編碼和測試五個階段。其中需求分析階段常用的工具是數(shù)據(jù)流圖和數(shù)據(jù)字典。
下列各題A)、B)、c)、D)四個選項中，只有一個選項是正確的，請將正確選項涂寫在答題卡相應位置上，答在試卷上不得分。．
(1)下面敘述正確的是_________。
A)算法的執(zhí)行效率與數(shù)據(jù)的存儲結(jié)構無關
B)算法的空間復雜度是指算法程序中指令(或語句)的條數(shù)
C)算法的有窮性是指算法必須能在執(zhí)行有限個步驟之后終止
D)算法的時間復雜度是指執(zhí)行算法程序所需要的時間
答案：C
評析：算法的設計可以避開具體的計算機程序設計語言，但算法的實現(xiàn)必須借助程序設計語言中提供的數(shù)據(jù)類型及其算法。數(shù)據(jù)結(jié)構和算法是計算機科學的兩個重要支柱。它們是一個不可分割的整體。算法在運行過程中需輔助存儲空間的大小稱為算法的空間復雜度。算法的有窮性是指一個算法必須在執(zhí)行有限的步驟以后結(jié)束。算法的時間復雜度是指執(zhí)行算法所需要的計算工作量，即算法執(zhí)行過程中所需要的基本運算次數(shù)。
(2)以下數(shù)據(jù)結(jié)構屬于非線性數(shù)據(jù)結(jié)構的是_________。
A)隊列 B)線性表 C)二叉樹 D)棧
答案：C
評析：線性表、棧和隊列等數(shù)據(jù)結(jié)構所表達和處理的數(shù)據(jù)以線性結(jié)構為組織形式。棧是一種特殊的線性表，這種線性表只能在固定的一端進行插入和刪除操作，允許插入和刪除的一端稱為棧項，另一端稱為棧底。一個新元素只能從棧頂一端進入，刪除時，只能刪除棧項的元素，即剛剛被插入的元素。所以棧又稱后進先出表(Last In First Out)：隊列可看作是插入在一端進行，刪除在另一端進行的線性表，允許插入的一端稱為隊尾，允許刪除的一端稱為隊頭。在隊列中，只能刪除隊頭元素，隊列的最后一個元素一定是最新入隊的元素。因此隊列又稱先進先出表(First In First Out)。
(3)在一棵二叉樹上第8層的結(jié)點數(shù)最多是_________。
A)8 B)16 C)128 D)256
答案：C
評析：根據(jù)二叉樹的性質(zhì)：二叉樹第i(i>1)層上至多有2卜’個結(jié)點。得到第8層的結(jié)點數(shù)最多是128。
(4)下面描述中，不符合結(jié)構化程序設計風格的是_________。
A)使用順序、選擇和重復(循環(huán))三種基本控制結(jié)構表示程序的控制邏輯
B)白頂向下
C)注重提高程序的執(zhí)行效率
D)限制使用goto語句
答案：C
評析：結(jié)構化程序設計方法的四條原則是：1．自頂向下；2．逐步求精：3．模塊化；4．限制使用goto語句。"自頂向下"是說，程序設計時，應先考慮總體，后考慮細節(jié)；先考慮全局目標，后考慮局部目標；"逐步求精"是說，對復雜問題，應設計一些子目標，作過渡j逐步細節(jié)化；"模塊化"是說，一個復雜問題，肯定是由若干稍簡單的問題構成：解決這個復雜問題的程序，也應對應若干稍簡單的問題，分解成若干稍小的部分。
(5)下面概念中，不屬于面向?qū)ο蠓椒ǖ氖莀________。
A)對象、消息 B)繼承、多態(tài)
C)類、封裝 D)過程調(diào)用
答案：D
評析：面向?qū)ο蠓椒ㄊ且环N運用對象、類、封裝、繼承、多態(tài)和消息等概念來構造、測試、重構軟件的方法。面向?qū)ο蠓椒◤膶ο蟪霭l(fā)，發(fā)展出對象，類，消息，繼承等概念。
(6)在結(jié)構化方法中，用數(shù)據(jù)流程圖(DFD)作為描述工具的軟件開發(fā)階段是________。
A)可行性分析 B)需求分析
C)詳細設計 D)程序編碼
答案：B
評析：軟件開發(fā)階段包括需求分析、總體設計、詳細設計、編碼和測試五個階段。其中需求分析階段常用的工具是數(shù)據(jù)流圖和數(shù)據(jù)字典。