計算機二級考試真題及答案.doc

1、計算機二級考試真題1） 在下列選項中，哪個不是一個算法一般應該具有的基本特征_。（ ）A. 確定性B. 可行性C. 無窮性D. 擁有足夠的情報2） 下面敘述正確的是_。（ ）A. 算法的執(zhí)行效率與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)B. 算法的空間復雜度是指算法程序中指令（或語句）的條數(shù)（指的是算法所占用的空間）C. 算法的有窮性是指算法必須能在執(zhí)行有限個步驟之后終止D. 以上三種描述都不對3） 算法的空間復雜度是指_。（ ）A. 算法程序的長度 B. 算法程序中的指令條數(shù)C. 算法程序所占的存儲空間 D. 算法執(zhí)行過程中所需要的存儲空間4） 數(shù)據(jù)的存儲結(jié)構(gòu)是指_。（ ）A. 數(shù)據(jù)所占的存儲空間量 B. 數(shù)據(jù)的

2、邏輯結(jié)構(gòu)在計算機中的表示C. 數(shù)據(jù)在計算機中的順序存儲方式 D. 存儲在外存中的數(shù)據(jù)5） 算法一般都可以用哪幾種控制結(jié)構(gòu)組合而成_。（ ）A. 循環(huán)、分支、遞歸 B. 順序、循環(huán)、嵌套 C. 循環(huán)、遞歸、選擇 D. 順序、選擇、循環(huán)6） 在計算機中，算法是指_。（ ）A. 查詢方法B. 加工方法 C. 解題方案的準確而完整的描述 D. 排序方法7） 算法分析的目的是_。（ ）A. 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B. 找出算法中輸入和輸出之間的關(guān)系C. 分析算法的易懂性和可靠性 D. 分析算法的效率以求改進8） n個頂點的強連通圖的邊數(shù)至少有_。（ ）A. n-1 B. n(n-1) C. n D. n

3、+19） 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的_。（ ）A. 存儲結(jié)構(gòu) B. 物理結(jié)構(gòu) C. 邏輯結(jié)構(gòu) D. 物理和存儲結(jié)構(gòu)10）串的長度是_ 。（ ）A. 串中不同字符的個數(shù) B. 串中不同字母的個數(shù)C. 串中所含字符的個數(shù)且字符個數(shù)大于零 D. 串中所含字符的個數(shù)11）下列敘述中，錯誤的是_ （ ）A. 數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率密切相關(guān) B. 數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率無關(guān) C. 數(shù)據(jù)的存儲結(jié)構(gòu)在計算機中所占的空間不一定是連續(xù)的D. 一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)12）下列敘述中正確的是_。（ ）A. 線性表是線性結(jié)構(gòu) B. 棧與隊列是非線性結(jié)構(gòu)C. 線性鏈表是非線性

4、結(jié)構(gòu) D. 二叉樹是線性結(jié)構(gòu)13）棧底至棧頂依次存放元素A、B、C、D，在第五個元素E入棧前，棧中元素可以出棧，則出棧序列可能是_。（ ）A. ABCED B. DBCEA C. CDABE D. DCBEA14）下列敘述中正確的是_。（ ）A. 線性表是線性結(jié)構(gòu) B.棧與隊列是非線性結(jié)構(gòu)C. 線性鏈表是非線性結(jié)構(gòu) D. 二叉樹是線性結(jié)構(gòu)15）線性表的順序存儲結(jié)構(gòu)和線性表的鏈式存儲結(jié)構(gòu)分別是_。（ ） A. 順序存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) B. 隨機存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) C. 隨機存取的存儲結(jié)構(gòu)、隨機存取的存儲結(jié)構(gòu) D. 任意存取的存儲結(jié)構(gòu)、任意存取的存儲結(jié)構(gòu)16）以下數(shù)

5、據(jù)結(jié)構(gòu)中不屬于線性數(shù)據(jù)結(jié)構(gòu)的是_。（ ）A. 隊列 B. 線性表 C. 二叉樹 D. 棧17）在單鏈表中，增加頭結(jié)點的目的是_。（ ）A. 方便運算的實現(xiàn) B. 使單鏈表至少有一個結(jié)點C. 標識表結(jié)點中首結(jié)點的位置 D. 說明單鏈表是線性表的鏈式存儲實現(xiàn)18）用鏈表表示線性表的優(yōu)點是_。（ ）A. 便于插入和刪除操作B. 數(shù)據(jù)元素的物理順序與邏輯順序相同C. 花費的存儲空間較順序存儲少D. 便于隨機存取19）線性表L=(a1,a2,a3,ai,an)，下列說法正確的是_ （ ）A. 每個元素都有一個直接前件和直接后件 B. 線性表中至少要有一個元素C. 表中諸元素的排列順序必須是由小到大或由大

6、到小 D. 除第一個元素和最后一個元素外，其余每個元素都有一個且只有一個直接前件和直接后件20）非空的循環(huán)單鏈表head的尾結(jié)點(由p所指向)，滿足_ （ ）A. p-next=NULL B. p=NULL C. p-next=head D. p=head21）棧和隊列的共同點是_。（ ）A. 都是先進后出B. 都是先進先出 C. 只允許在端點處插入和刪除元素 D. 沒有共同點22）下列關(guān)于隊列的敘述中正確的是_。（ ）A. 在隊列中只能插入數(shù)據(jù) B. 在隊列中只能刪除數(shù)據(jù)C. 隊列是先進先出的線性表D. 隊列是先進后出的線性表23）如果進棧序列為e1，e2，e3，e4，則可能的出棧序列是_

7、（ ）A. e3，e1，e4，e2 B. e2，e4，e3，e1 C. e3，e4，e1，e2 D. 任意順序24）已知一個棧的進棧序列是1，2，3，n，輸出序列是p1,p2,p3.pn,若p1=n，則pi(1inext=s ; B. s-next= HS-next ; HS-next=s;C. s-next= HS; HS=s; D. s-next= HS; HS= HS-next;26）設棧S的初始狀態(tài)為空，6個元素入棧的順序為1,2,3,4,5,6。若出棧的順序是2,4,3,6,5,1,則棧S的容量至少應該是_（ ）A. 6 B. 4 C. 3 D. 227）為了減少棧溢出的可能性，可以

8、讓兩個棧共享一片連續(xù)存儲空間，兩個棧的棧底分別設在這片空間的兩端，這樣只有當_時才可能產(chǎn)生上溢。（ ）A. 兩個棧的棧頂在?？臻g的某一位置相遇 B. 其中一個棧的棧頂?shù)竭_棧空間的中心點C. 兩個棧的棧頂同時到達?？臻g的中心點D. 兩個棧均不空，且一個棧的棧頂?shù)竭吜硪粭５臈５?8）下列關(guān)于棧的敘述中正確的是_。（ ）A. 在棧中只能插入數(shù)據(jù) B. 在棧中只能刪除數(shù)據(jù)C. 棧是先進先出的線性表 D. 棧是先進后出的線性表29）下列關(guān)于隊列的敘述中正確的是_。（ ）A. 在隊列中只能插入數(shù)據(jù) B. 在隊列中只能刪除數(shù)據(jù)C. 隊列是先進先出的線性表 D. 隊列是先進后出的線性表30）棧和隊列的共同點是

9、_。（ ）A. 都是先進后出 B. 都是先進先出C. 只允許在端點處插入和刪除元素 D. 沒有共同點31）對線性表，下列情況下應當采用鏈表表示的是_（ ）A. 經(jīng)常需要隨機地存取元素 B. 經(jīng)常需要進行插入和刪除操作C. 表中元素需要占據(jù)一片連續(xù)的存儲空間 D. 表中元素個數(shù)不變32）在一個鏈式隊列中，假設f和r分別為隊頭與隊尾指針，則刪除結(jié)點的運算是_（ ）A. r = f-next B. r = r-next C. f = f-next D. f = r-next33）設一棵完全二叉樹共有699個結(jié)點，則在該二叉樹中的葉子結(jié)點數(shù)為_。（ ）A. 349 B.350C. 255D. 3513

10、4）若某二叉樹的前序遍歷訪問順序是abdgcefh，中序遍歷訪問順序是dgbaechf，則其后序遍歷的結(jié)點訪問順序是_ （ ）A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca35）設樹T的度為4，其中度為1,2,3,4的結(jié)點個數(shù)分別為4,2,1,1。則T中的葉子結(jié)點數(shù)為_ （ ）A. 8 B. 7 C. 6 D. 536）樹最適合用來表示_（ ）A. 有序數(shù)據(jù)元素 B. 無序數(shù)據(jù)元素C. 元素之間具有分支層次關(guān)系的數(shù)據(jù) D. 元素之間無聯(lián)系的數(shù)據(jù)37）某二叉樹的先序和后序遍歷順序正好相反，則該二叉樹一定是_（ ）A. 空或只有一個結(jié)點 B. 完全二

11、叉樹 C. 二叉排序樹 D. 深度等于其結(jié)點數(shù)38）設n，m為一棵二叉樹上的兩個結(jié)點，在中序遍歷中，n在m之前的條件是_（ ）adcfA. n在m右子樹上 Bn是m的祖先C. n在m左子樹上 D. n是m的子孫39）如圖所示二叉樹的中序遍歷序列是_（ ）A. abcdgef B. dfebagcC. dbaefcg D. abcdefg40）樹是結(jié)點的集合，它的根結(jié)點數(shù)目是_ （ ）A. 有且只有1 B. 1或多于1 C. 0或1 D. 至少241）在一棵二叉樹上第5層的結(jié)點數(shù)最多是_。（ ）A. 8 B. 16 C. 32 D. 1542）對長度為N的線性表進行順序查找，在最壞情況下所需要的

12、比較次數(shù)為_。（ ）A. N+1B. NC. (N+1)/2D. N/243）順序查找適合于存儲結(jié)構(gòu)為_的線性表（ ）A. 散列存儲B. 順序存儲或鏈式存儲C. 壓縮存儲D. 索引存儲44）采用順序法查找長度為n的線性表時，每個元素的平均查找長度為_（ ）A. nB. n/2C. (n+1)/2D. (n-1)/245）希爾排序法屬于哪一種類型的排序法_。（ ）A. 交換類排序法 B. 插入類排序法 C. 選擇類排序法 D. 建堆排序法46）在待排序的元素序列基本有序的前提下，效率最高的排序方法是_ （ ）A. 冒泡排序 B. 選擇排序 C. 快速排序 D. 歸并排序47）設有1000個元素，

13、希望用最快的速度選出其中前10個最大的元素，最好選用_排序法。（ ）A. 冒泡 B. 快速 C. 堆 D. 選擇48）在下列排序法中，_算法可能出現(xiàn)下列情況：在最后一趟開始之間，所有的元素都不在其最終位置上。（ ）A. 冒泡 B. 快速 C. 插入 D. 堆49）在下列幾種排序方法中，要求內(nèi)存量最大的是_。（ ）A. 插入排序 B. 選擇排序 C. 快速排序 D. 歸并排序50）已知數(shù)據(jù)表A中每個元素距其最終位置不遠，為節(jié)省時間，應采用的算法是_。（ ）A. 堆排序 B. 直接插入排序 C. 快速排序 D. 直接選擇排序9.2 填空題1） 算法的復雜度主要包括_ _復雜度和空間復雜度。2） 現(xiàn)

14、有按中序遍歷二叉樹的結(jié)果為abc，那么有 種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果。3） 若要對1000個元素排序，要求即快又節(jié)省空間，則最好采用 方法。4） 在平均情況下速度最快的排序方法為 排序。5） 有關(guān)鍵碼序列（16,9,4,25,15,2,13,18,17,5,8,24），要求按關(guān)鍵碼遞增順序排序。采用冒泡排序法，則第二趟冒泡后的結(jié)果為 。6） 有關(guān)鍵碼序列（16,9,4,25,15,2,13,18,17,5,8,24），要求按關(guān)鍵碼遞增順序排序。采用初始增量為4的希爾排序，則一趟掃描后的結(jié)果為 。7） 假定一組記錄為（46,79,56,38,40,80）對其進行快速排序的過程中，共需

15、要 趟排序。8） 假定一組記錄為（46,79,56,38,40,80）對其進行快速排序的第一次劃分結(jié)果為 。9） 對任意7個關(guān)鍵字進行排序，至少要進行 次關(guān)鍵字之間的兩兩比較。10）算法的基本特征是可行性、確定性、_ _和擁有足夠的情報。11）順序存儲方法是把邏輯上相鄰的結(jié)點存儲在物理位置_ _的存儲單元中。12）數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式稱為數(shù)據(jù)的_ _ _。agdbcefhi13）棧的基本運算有三種：入棧、退棧和_ 。14）如圖所示的二叉樹，其中序遍歷序列是 ；前序遍歷序列是 ；后序遍歷序列是 15）設一棵完全二叉樹共有499個結(jié)點，則在該二叉樹中有_ _個葉子結(jié)點。16）

16、在最壞情況下，冒泡排序的時間復雜度為_ _ _。17）在最壞情況下，堆排序需要比較的次數(shù)為_ _。18）在計算機中，可以采用 結(jié)構(gòu)來表示算術(shù)表達式。19）具有90個結(jié)點的完全二叉樹的深度為 。20）對具有n個元素的任意序列進行排序，在最壞情況下，采用簡單排序法時需要 次比較；采用希爾排序法進行排序時，時間復雜度為 ；采用簡單排序法進行排序時，需要比較 次；采用堆排序法進行排序時需要比較的次數(shù)為 。1） 算法的復雜度主要包括_ _復雜度和空間復雜度。2） 現(xiàn)有按中序遍歷二叉樹的結(jié)果為abc，那么有 種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果。3） 若要對1000個元素排序，要求即快又節(jié)省空間，則最好

17、采用 方法。4） 在平均情況下速度最快的排序方法為 排序。5） 有關(guān)鍵碼序列（16,9,4,25,15,2,13,18,17,5,8,24），要求按關(guān)鍵碼遞增順序排序。采用冒泡排序法，則第二趟冒泡后的結(jié)果為 。6） 有關(guān)鍵碼序列（16,9,4,25,15,2,13,18,17,5,8,24），要求按關(guān)鍵碼遞增順序排序。采用初始增量為4的希爾排序，則一趟掃描后的結(jié)果為 。7） 假定一組記錄為（46,79,56,38,40,80）對其進行快速排序的過程中，共需要 趟排序。8） 假定一組記錄為（46,79,56,38,40,80）對其進行快速排序的第一次劃分結(jié)果為 。9） 對任意7個關(guān)鍵字進行排序，

18、至少要進行 次關(guān)鍵字之間的兩兩比較。10）算法的基本特征是可行性、確定性、_ _和擁有足夠的情報。11）順序存儲方法是把邏輯上相鄰的結(jié)點存儲在物理位置_ _的存儲單元中。12）數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式稱為數(shù)據(jù)的_ _ _。agdbcegfbhei13）棧的基本運算有三種：入棧、退棧和_ 。14）如圖所示的二叉樹，其中序遍歷序列是 ；前序遍歷序列是 ；后序遍歷序列是 15）設一棵完全二叉樹共有499個結(jié)點，則在該二叉樹中有_ _個葉子結(jié)點。16）在最壞情況下，冒泡排序的時間復雜度為_ _ _。17）在最壞情況下，堆排序需要比較的次數(shù)為_ _。18）在計算機中，可以采用 結(jié)構(gòu)來表示算術(shù)表達式。19）具有90個結(jié)點的完全二叉樹的深度為 。20）對具有n個元素的任意序列進行排序，在最壞情況下，采用簡單排序法時需要 次比較；采用希爾排序法進行排序時，時間復雜度為 ；采用簡單排序法進行排序時，需要比較 次；采用堆排序法進行排序時需要比較的次數(shù)為 。1-5 CCDBD 6-10 CDCCD 11-15 BADAB 16-20 CAADC 21-25 CCBCC26-30 CADCC 31-35 BCBDA 36-40 CDCBA 41-45 BBBCB 46-50 ACCDB1) 時間2) 5 3) 堆排序 4