公共機(jī)基礎(chǔ)答案

1、昆明新視野教育咨詢有限公司昆明新視野教育咨詢有限公司1第一章第一章數(shù)據(jù)結(jié)構(gòu)和算法數(shù)據(jù)結(jié)構(gòu)和算法一、選擇題一、選擇題1、B（p1）解析：算法的基本特征：確定性、有窮性、可行性、擁有足夠的情報2、C（p2）解析：算法的時間復(fù)雜度指的是：算法執(zhí)行過程中所需要的基本運算次數(shù)。3、D（p3）解析：算法的空間復(fù)雜度指的是：算法在執(zhí)行過程中所需要的存儲單位。包括三個部分：1、輸入數(shù)據(jù)多占的存儲空間。2、程序本身占有的存儲空間。3、算法執(zhí)行過程中所需要

2、的額外的空間。4、D解析：時間復(fù)雜度和空間復(fù)雜度之間沒有的關(guān)系。5、A（P5）解析：數(shù)據(jù)的存儲結(jié)構(gòu)指的是數(shù)據(jù)在計算機(jī)中的存放方式。面向計算機(jī)的，即是外存中的數(shù)據(jù)。6、B（P5）解析：采用不同的存儲結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。7、D（p4p5）解析：一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)：鏈?zhǔn)?、順序、索引等存儲，A答案錯誤。B答案數(shù)據(jù)的存儲結(jié)構(gòu)也可以是線性結(jié)構(gòu)，如數(shù)組。C答案一個數(shù)據(jù)的邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)是正確的，但是采用不同的存儲

3、結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。8、C（P11）解析：棧是線性的。棧既可以插入元素，也可以刪除元素。但是只能在棧的一端插入和刪除元素。D答案中說的是隊列，隊列是在一端插入數(shù)據(jù)，在另外一端刪除數(shù)據(jù)。9、B（P11）（913題所在頁數(shù)為11）解析：棧的特點：棧是一種先進(jìn)后出合或者是后進(jìn)先出的線性表。具有記憶功能。由于棧只能在一端插入和刪除數(shù)據(jù)，所以在插入和刪除操作中，不需要改變棧底的指針。棧也可以隨機(jī)存儲。10、D11、B12、B13、C1

4、4、C（P12）解析：隊列是一種特殊的線性表，只能在一端插入元素，在另外一端刪除元素。既可以插入數(shù)據(jù)，也可以刪除數(shù)據(jù)。是一種先進(jìn)先出的線性表?；蛘哒f是后進(jìn)后出的線性表。15、A解析：由于棧是先進(jìn)后出的線性表，隊列是先進(jìn)先出的線性表，所以根據(jù)它們陳虎隊列的順序，可以得知棧的容量為3.它們進(jìn)入棧的順序為a緊接著是b移走bc進(jìn)入，d進(jìn)入，移走d移走de進(jìn)入，f進(jìn)入，移走f移走e移走a。昆明新視野教育咨詢有限公司昆明新視野教育咨詢有限公司3以。

5、30、A（p20）解析：用二分法查找數(shù)據(jù)時，最壞的情況下，需要比較的次數(shù)為：log2n次。31、B（p19）解析：在有序的線性表中查找數(shù)據(jù)的時候，最壞的情況下，需要比較的次數(shù)為n次。所以該題為64.32、D解析：在最壞的情況下，冒泡法排序的時間復(fù)雜度是：n（n1）2插入排序的時間復(fù)雜度為：n（n1）2。堆排序的時間復(fù)雜度為：nlog2n快速排序法的時間復(fù)雜度為n（n1）2.所以答案為D33、D解析：同上34、A（p1）解析：算法的有窮性

6、是指：算法在經(jīng)過有窮的步驟后結(jié)束。即在時間上是有限的。35、D解析：堆排序的時間復(fù)雜度是：：nlog2n36、B（P11）解析：棧是先進(jìn)后出的順序組織數(shù)據(jù)的。只能在棧的一端插入和輸出數(shù)據(jù)。37、A（p5）解析：采用不同的存儲結(jié)構(gòu)，數(shù)據(jù)的處理效率是不同的。38、D（p8）解析：選項A數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的類型可以對應(yīng)，也可以不一一對應(yīng)。選項B數(shù)據(jù)的存儲結(jié)構(gòu)有順序、鏈?zhǔn)?、索引等多種存儲結(jié)構(gòu)，而不是向量式的存儲結(jié)構(gòu)。選項C數(shù)組可以處理線性

7、的結(jié)構(gòu)，也可以處理其他結(jié)構(gòu)，只是這種不常用而已。39、C（p20）解析：冒泡法排序在最壞的情況下的比較次數(shù)為n（n1）2。40、A（p15例題2）解析：在二叉樹中，度為2的結(jié)點比度為0的結(jié)點的個數(shù)少一個，有70個葉子結(jié)點，所以度為2的結(jié)點的個數(shù)為69個，所以總的結(jié)點的個數(shù)697080=219.41、B（p2）解析：算法的時間復(fù)雜度是值執(zhí)行算法所需要的計算的工作量。計算工作量是問題規(guī)模的函數(shù)。42、D（p12）解析：棧和隊列都是線性結(jié)構(gòu)，