公共機基礎答案

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

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

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

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

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

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

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