2017中國(guó)移動(dòng)校園招聘考試備考資料—計(jì)算機(jī)類(lèi)習(xí)題二

數(shù)據(jù)結(jié)構(gòu)

(6)下列敘述中正確的是( )

A)程序執(zhí)行的效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)密切相關(guān)

B)程序執(zhí)行的效率只取決于程序的控制結(jié)構(gòu)

C)程序執(zhí)行的效率只取決于所處理的數(shù)據(jù)量

D)以上三種說(shuō)法都不對(duì)

【答案】A

【解析】本題考查程序效率。程序效率是指程序運(yùn)行速度和程序占用的存儲(chǔ)空間。影響程序效率的因素是多方面的， 包括程序的設(shè)計(jì)、使用的算法、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)等。在確定數(shù)據(jù)邏輯結(jié)構(gòu)的基礎(chǔ)上，選擇一種合適的存儲(chǔ)結(jié)構(gòu)，可 以使得數(shù)據(jù)操作所花費(fèi)的時(shí)間少，占用的存儲(chǔ)空間少，即提高程序的效率。因此，本題選項(xiàng) A 的說(shuō)法是正確的。

(7)下列敘述中正確的是( )

A)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)必定是一一對(duì)應(yīng)的

B)由于計(jì)算機(jī)存儲(chǔ)空間是向量式的存儲(chǔ)結(jié)構(gòu)，因此，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)一定是線性結(jié)構(gòu)

C)程序設(shè)計(jì)語(yǔ)言中的數(shù)組一般是順序存儲(chǔ)結(jié)構(gòu)，因此，利用數(shù)組只能處理線線結(jié)構(gòu)

D)以上三種說(shuō)法都不對(duì)

【答案】D

【解析】本題考查數(shù)據(jù)結(jié)構(gòu)的基本知識(shí)。 數(shù)據(jù)之間的相互關(guān)系稱(chēng)為邏輯結(jié)構(gòu)。通常分為四類(lèi)基本邏輯結(jié)構(gòu)，即集合、線性結(jié)構(gòu)、樹(shù)型結(jié)構(gòu)、圖狀結(jié)構(gòu)或網(wǎng)狀 結(jié)構(gòu)。存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在存儲(chǔ)器中的映象，它包含數(shù)據(jù)元素的映象和關(guān)系的映象。存儲(chǔ)結(jié)構(gòu)在計(jì)算機(jī)中有兩種， 即順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)是把數(shù)據(jù)元素存儲(chǔ)在一塊連續(xù)地址空間的內(nèi)存中;鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是 使用指針把相互直接關(guān)聯(lián)的節(jié)點(diǎn)鏈接起來(lái)。因此，這兩種存儲(chǔ)結(jié)構(gòu)都是線性的�？梢�(jiàn)，邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)不是一 一對(duì)應(yīng)的。因此，選項(xiàng) A 和選項(xiàng) B 的說(shuō)法都是錯(cuò)誤的。 無(wú)論數(shù)據(jù)的邏輯結(jié)構(gòu)是線性的還是非線性的，只能選擇順序存儲(chǔ)結(jié)構(gòu)或鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來(lái)實(shí)現(xiàn)存儲(chǔ)。程序設(shè)計(jì)語(yǔ)言中，數(shù)組是內(nèi)存中一段連續(xù)的地址空間，可看作是順序存儲(chǔ)結(jié)構(gòu)。可以用數(shù)組來(lái)實(shí)現(xiàn)樹(shù)型邏輯結(jié)構(gòu)的存儲(chǔ)，比如二叉樹(shù)。 因此，選項(xiàng)c的說(shuō)法是錯(cuò)誤的

(8)冒泡排序在最壞情況下的比較次數(shù)是( )

A)n(n+1)/2

B)nlog2n

C)n(n-1)/2

D)n/2

【答案】C

【解析】冒泡排序的基本思想是：將相鄰的兩個(gè)元素進(jìn)行比較，如果反序，則交換;對(duì)于一個(gè)待排序的序列，經(jīng)一 趟排序后，最大值的元素移動(dòng)到最后的位置，其他值較大的元素也向最終位置移動(dòng)，此過(guò)程稱(chēng)為一趟冒泡。對(duì)于有 n 個(gè)數(shù)據(jù)的序列，共需n-1趟排序，第i趟對(duì)從l到n-i個(gè)數(shù)據(jù)進(jìn)行比較、交換。冒泡排序的最壞情況是待排序序列 逆序，第l趟比較n-1次，第2趟比較n-2次。依此類(lèi)推，最后趟比較1次，一共進(jìn)行n-l趟排序。因此，冒泡排 序在最壞情況下的比較次數(shù)是(n-1)+(n-2)+…+l，結(jié)果為n(n-1)/2。本題的正確答案是選項(xiàng)c。

(9)一棵二叉樹(shù)中共有70個(gè)葉子結(jié)點(diǎn)與80個(gè)度為1的結(jié)點(diǎn)，則該二叉樹(shù)中的總結(jié)點(diǎn)數(shù)為( )

A)219

B)221

C)229

D)231

【答案】A

【解析】本題考查數(shù)據(jù)結(jié)構(gòu)中二叉樹(shù)的性質(zhì)。二叉樹(shù)滿(mǎn)足如下一條性質(zhì)，即：對(duì)任意一棵二叉樹(shù)，若終端結(jié)點(diǎn)(即葉 子結(jié)點(diǎn))數(shù)為n0，而其度數(shù)為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+l。 根據(jù)這條性質(zhì)可知，若二叉樹(shù)中有70個(gè)葉子結(jié)點(diǎn)，則其度為2的結(jié)點(diǎn)數(shù)為70-1，即69個(gè)。二叉樹(shù)的總結(jié)點(diǎn)數(shù)是度為2、度為1和葉子結(jié)點(diǎn)的總和，因此，題目中的二叉樹(shù)總結(jié)點(diǎn)數(shù)為69+80+70，即219。因此，本題的正確答案是選項(xiàng)A。

(10)下列敘述中正確的是( )

A)算法的效率只與問(wèn)題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)

B)算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量

C)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)是一一對(duì)應(yīng)的

D)算法的時(shí)間復(fù)雜度與空間復(fù)雜度一定相關(guān)

【答案】B

【解析】本題考查數(shù)據(jù)結(jié)構(gòu)中有關(guān)算法的基本知識(shí)和概念。數(shù)據(jù)的結(jié)構(gòu)，直接影響算法的選擇和效率。而數(shù)據(jù)結(jié)構(gòu) 包括兩方面，即數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)都影響算法的效率。選項(xiàng)A 的說(shuō)法是錯(cuò)誤的。算法的時(shí)間復(fù)雜度是指算法在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所需時(shí)間的度量;與時(shí)間復(fù)雜度類(lèi)似，空間復(fù)雜度 是指算法在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所需存儲(chǔ)空間的度量。因此，選項(xiàng) B 的說(shuō)法是正確的。 數(shù)據(jù)之間的相互關(guān)系稱(chēng)為邏輯結(jié)構(gòu)。通常分為四類(lèi)基本邏輯結(jié)構(gòu)，即集合、線性結(jié)構(gòu)、樹(shù)型結(jié)構(gòu)、圖狀結(jié)構(gòu)或網(wǎng)狀 結(jié)構(gòu)。存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在存儲(chǔ)器中的映象，它包含數(shù)據(jù)元素的映象和關(guān)系的映象。存儲(chǔ)結(jié)構(gòu)在計(jì)算機(jī)中有兩種， 即順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。可見(jiàn)，邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)不是一一對(duì)應(yīng)的。因此，選項(xiàng)c的說(shuō)法是錯(cuò)誤的。有 時(shí)人們?yōu)榱颂岣咚惴ǖ臅r(shí)間復(fù)雜度，而以犧牲空間復(fù)雜度為代價(jià)。但是，這兩者之間沒(méi)有必然的聯(lián)系。因此，選項(xiàng) D 的說(shuō)法是錯(cuò)誤的。

相關(guān)內(nèi)容推薦：