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

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

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

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

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

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

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

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