計(jì)算機(jī)二級(jí)考試真題及答案

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

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

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

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

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

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

7、的出棧序列是_ （ ）A. e3，e1，e4，e2 B. e2，e4，e3，e1 C. e3，e4，e1，e2 D. 任意順序24）已知一個(gè)棧的進(jìn)棧序列是1，2，3，n，輸出序列是p1,p2,p3.pn,若p1=n，則pi(1<i<n)為_ （ ）A. i B. n-i C. n-i+1 D. 不確定25）向一個(gè)棧頂指針為HS的鏈?zhǔn)綏Ｖ胁迦胍粋€(gè)s所指的結(jié)點(diǎn)時(shí)，則執(zhí)行_（ ）A. HS->next=s ; B. s->next= HS->next ; HS->next=s;C. s->next= HS; HS=s; D. s->next= HS;

8、HS= HS->next;26）設(shè)棧S的初始狀態(tài)為空，6個(gè)元素入棧的順序?yàn)?,2,3,4,5,6。若出棧的順序是2,4,3,6,5,1,則棧S的容量至少應(yīng)該是_（ ）A. 6 B. 4 C. 3 D. 227）為了減少棧溢出的可能性，可以讓兩個(gè)棧共享一片連續(xù)存儲(chǔ)空間，兩個(gè)棧的棧底分別設(shè)在這片空間的兩端，這樣只有當(dāng)_時(shí)才可能產(chǎn)生上溢。（ ）A. 兩個(gè)棧的棧頂在?？臻g的某一位置相遇 B. 其中一個(gè)棧的棧頂?shù)竭_(dá)?？臻g的中心點(diǎn)C. 兩個(gè)棧的棧頂同時(shí)到達(dá)棧空間的中心點(diǎn)D. 兩個(gè)棧均不空，且一個(gè)棧的棧頂?shù)竭吜硪粭５臈５?8）下列關(guān)于棧的敘述中正確的是_。（ ）A. 在棧中只能插入數(shù)據(jù) B. 在棧中只

9、能刪除數(shù)據(jù)C. 棧是先進(jìn)先出的線性表 D. 棧是先進(jìn)后出的線性表29）下列關(guān)于隊(duì)列的敘述中正確的是_。（ ）A. 在隊(duì)列中只能插入數(shù)據(jù) B. 在隊(duì)列中只能刪除數(shù)據(jù)C. 隊(duì)列是先進(jìn)先出的線性表 D. 隊(duì)列是先進(jìn)后出的線性表30）棧和隊(duì)列的共同點(diǎn)是_。（ ）A. 都是先進(jìn)后出 B. 都是先進(jìn)先出C. 只允許在端點(diǎn)處插入和刪除元素 D. 沒有共同點(diǎn)31）對(duì)線性表，下列情況下應(yīng)當(dāng)采用鏈表表示的是_（ ）A. 經(jīng)常需要隨機(jī)地存取元素 B. 經(jīng)常需要進(jìn)行插入和刪除操作C. 表中元素需要占據(jù)一片連續(xù)的存儲(chǔ)空間 D. 表中元素個(gè)數(shù)不變32）在一個(gè)鏈?zhǔn)疥?duì)列中，假設(shè)f和r分別為隊(duì)頭與隊(duì)尾指針，則刪除結(jié)點(diǎn)的運(yùn)算是_

10、（ ）A. r = f->next B. r = r->next C. f = f->next D. f = r->next33）設(shè)一棵完全二叉樹共有699個(gè)結(jié)點(diǎn)，則在該二叉樹中的葉子結(jié)點(diǎn)數(shù)為_。（ ）A. 349 B.350C. 255D. 35134）若某二叉樹的前序遍歷訪問順序是abdgcefh，中序遍歷訪問順序是dgbaechf，則其后序遍歷的結(jié)點(diǎn)訪問順序是_ （ ）A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca35）設(shè)樹T的度為4，其中度為1,2,3,4的結(jié)點(diǎn)個(gè)數(shù)分別為4,2,1,1。則T中的葉子結(jié)點(diǎn)數(shù)為_ （

11、）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. 空或只有一個(gè)結(jié)點(diǎn) B. 完全二叉樹 C. 二叉排序樹 D. 深度等于其結(jié)點(diǎn)數(shù)38）設(shè)n，m為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷中，n在m之前的條件是_（ ）adcfA. n在m右子樹上 Bn是m的祖先C. n在m左子樹上 D. n是m的子孫39）如圖所示二叉樹的中序遍歷序列是_（ ）A. abcdgef B. dfebagcC. dbaefcg D.

12、abcdefg40）樹是結(jié)點(diǎn)的集合，它的根結(jié)點(diǎn)數(shù)目是_ （ ）A. 有且只有1 B. 1或多于1 C. 0或1 D. 至少241）在一棵二叉樹上第5層的結(jié)點(diǎn)數(shù)最多是_。（ ）A. 8 B. 16 C. 32 D. 1542）對(duì)長度為N的線性表進(jìn)行順序查找，在最壞情況下所需要的比較次數(shù)為_。（ ）A. N+1B. NC. (N+1)/2D. N/243）順序查找適合于存儲(chǔ)結(jié)構(gòu)為_的線性表（ ）A. 散列存儲(chǔ)B. 順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)C. 壓縮存儲(chǔ)D. 索引存儲(chǔ)44）采用順序法查找長度為n的線性表時(shí)，每個(gè)元素的平均查找長度為_（ ）A. nB. n/2C. (n+1)/2D. (n-1)/245）希

13、爾排序法屬于哪一種類型的排序法_。（ ）A. 交換類排序法 B. 插入類排序法 C. 選擇類排序法 D. 建堆排序法46）在待排序的元素序列基本有序的前提下，效率最高的排序方法是_ （ ）A. 冒泡排序 B. 選擇排序 C. 快速排序 D. 歸并排序47）設(shè)有1000個(gè)元素，希望用最快的速度選出其中前10個(gè)最大的元素，最好選用_排序法。（ ）A. 冒泡 B. 快速 C. 堆 D. 選擇48）在下列排序法中，_算法可能出現(xiàn)下列情況：在最后一趟開始之間，所有的元素都不在其最終位置上。（ ）A. 冒泡 B. 快速 C. 插入 D. 堆49）在下列幾種排序方法中，要求內(nèi)存量最大的是_。（ ）A. 插入

14、排序 B. 選擇排序 C. 快速排序 D. 歸并排序50）已知數(shù)據(jù)表A中每個(gè)元素距其最終位置不遠(yuǎn)，為節(jié)省時(shí)間，應(yīng)采用的算法是_。（ ）A. 堆排序 B. 直接插入排序 C. 快速排序 D. 直接選擇排序9.2 填空題1） 算法的復(fù)雜度主要包括_ _復(fù)雜度和空間復(fù)雜度。2） 現(xiàn)有按中序遍歷二叉樹的結(jié)果為abc，那么有 種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果。3） 若要對(duì)1000個(gè)元素排序，要求即快又節(jié)省空間，則最好采用 方法。4） 在平均情況下速度最快的排序方法為 排序。5） 有關(guān)鍵碼序列（16,9,4,25,15,2,13,18,17,5,8,24），要求按關(guān)鍵碼遞增順序排序。采用冒泡排序法，

15、則第二趟冒泡后的結(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）對(duì)其進(jìn)行快速排序的過程中，共需要 趟排序。8） 假定一組記錄為（46,79,56,38,40,80）對(duì)其進(jìn)行快速排序的第一次劃分結(jié)果為 。9） 對(duì)任意7個(gè)關(guān)鍵字進(jìn)行排序，至少要進(jìn)行 次關(guān)鍵字之間的兩兩比較。10）算法的基本特征是可行性、確定性、_ _和擁有足夠的情報(bào)。11）順序存儲(chǔ)方法是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置_ _的存儲(chǔ)單元中。12）數(shù)據(jù)的邏

16、輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱為數(shù)據(jù)的_ _ _。agdbcefhi13）棧的基本運(yùn)算有三種：入棧、退棧和_ 。14）如圖所示的二叉樹，其中序遍歷序列是 ；前序遍歷序列是 ；后序遍歷序列是 15）設(shè)一棵完全二叉樹共有499個(gè)結(jié)點(diǎn)，則在該二叉樹中有_ _個(gè)葉子結(jié)點(diǎn)。16）在最壞情況下，冒泡排序的時(shí)間復(fù)雜度為_ _ _。17）在最壞情況下，堆排序需要比較的次數(shù)為_ _。18）在計(jì)算機(jī)中，可以采用 結(jié)構(gòu)來表示算術(shù)表達(dá)式。19）具有90個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 。20）對(duì)具有n個(gè)元素的任意序列進(jìn)行排序，在最壞情況下，采用簡(jiǎn)單排序法時(shí)需要 次比較；采用希爾排序法進(jìn)行排序時(shí)，時(shí)間復(fù)雜度為 ；采用簡(jiǎn)

17、單排序法進(jìn)行排序時(shí)，需要比較 次；采用堆排序法進(jìn)行排序時(shí)需要比較的次數(shù)為 。1） 算法的復(fù)雜度主要包括_ _復(fù)雜度和空間復(fù)雜度。2） 現(xiàn)有按中序遍歷二叉樹的結(jié)果為abc，那么有 種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果。3） 若要對(duì)1000個(gè)元素排序，要求即快又節(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)鍵碼遞增順序排序。采用

18、初始增量為4的希爾排序，則一趟掃描后的結(jié)果為 。7） 假定一組記錄為（46,79,56,38,40,80）對(duì)其進(jìn)行快速排序的過程中，共需要 趟排序。8） 假定一組記錄為（46,79,56,38,40,80）對(duì)其進(jìn)行快速排序的第一次劃分結(jié)果為 。9） 對(duì)任意7個(gè)關(guān)鍵字進(jìn)行排序，至少要進(jìn)行 次關(guān)鍵字之間的兩兩比較。10）算法的基本特征是可行性、確定性、_ _和擁有足夠的情報(bào)。11）順序存儲(chǔ)方法是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置_ _的存儲(chǔ)單元中。12）數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱為數(shù)據(jù)的_ _ _。agdbcegfbhei13）棧的基本運(yùn)算有三種：入棧、退棧和_ 。14）如圖所示的二叉樹，其中序遍歷序列是 ；前序遍歷序列是 ；后序遍歷序列是 15）設(shè)一棵完全二叉樹共有499個(gè)結(jié)點(diǎn)，則在該二叉樹中有_ _個(gè)葉子結(jié)點(diǎn)。16）在最壞情況下，冒泡排序的時(shí)間復(fù)雜度為_ _ _。17）在最壞情況下，堆排序需要比較的次數(shù)