1.4 過關(guān)全真模擬題解析

【試題1分析】數(shù)據(jù)的存儲結(jié)構(gòu)分順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，一個數(shù)據(jù)的邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)。順序結(jié)構(gòu)中數(shù)據(jù)元素所占的存儲空間是連續(xù)的，而鏈?zhǔn)酱鎯Y(jié)構(gòu)中，數(shù)據(jù)元素通過指針就聯(lián)系在一起了，所以所占的存儲空間不一定是連續(xù)的。

【答案】B

【試題2分析】隊(duì)列（Queue）是指允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表。允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為隊(duì)頭。在隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)中，最先插入的元素將能夠最先被刪除；反之，最后插入的元素最后才能被刪除。因此，隊(duì)列又稱“先進(jìn)先出”或“后進(jìn)后出”的線性表。

【答案】D

【試題3分析】鏈表采用的是鏈?zhǔn)酱鎯Y(jié)構(gòu)，它的節(jié)點(diǎn)空間可以動態(tài)申請和釋放；它的數(shù)據(jù)元素的邏輯次序靠節(jié)點(diǎn)的指針來指示，插入或刪除不需要移動數(shù)據(jù)元素。但是鏈?zhǔn)酱鎯Y(jié)構(gòu)也有不足之處，每個節(jié)點(diǎn)中的指針域需額外占用存儲空間，它是一種非隨機(jī)存儲結(jié)構(gòu)。

【答案】B

【試題4分析】棧是線性表的一種，它的特點(diǎn)是先進(jìn)后出，并且只能在表的一端進(jìn)行插入和刪除操作。入棧和出棧都是在棧頂進(jìn)行的，因此具有記憶作用。棧可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯Α?/p>

【答案】B

【試題5分析】在任意一棵二叉樹中，度為0的節(jié)點(diǎn)（即葉子節(jié)點(diǎn)）總是比度為2的節(jié)點(diǎn)多一個，所以該二叉樹的葉子節(jié)點(diǎn)數(shù)等于n+1。

【答案】A

【試題6分析】二叉樹前序遍歷的簡單描述為：若二叉樹為空，則返回節(jié)點(diǎn)；否則先訪問根節(jié)點(diǎn)，然后前序遍歷左子樹，最后前序遍歷右子樹。可見，前序遍歷二叉樹的過程是一個遞歸的過程。根據(jù)題目中給出的二叉樹的結(jié)構(gòu)可知前序遍歷的結(jié)果是ABDYECFXZ。

【答案】C

【試題7分析】若數(shù)據(jù)表A中每個元素距其最終位置不遠(yuǎn)，說明數(shù)據(jù)表A按關(guān)鍵字值的排序是有序的。在待排序列基本有序的情況下，采用插入排序所用的時間最少。

【答案】B

【試題8分析】數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲空間中的存放形式稱為數(shù)據(jù)的存儲結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)）。一般來說，一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲結(jié)構(gòu)，常用的存儲結(jié)構(gòu)有順序、鏈接和索引等。

【答案】D

【試題9分析】算法分析是指對一個算法的運(yùn)行時間和占用空間做定量的分析，計(jì)算相應(yīng)的數(shù)量級。分析算法的目的就是要降低算法的時間復(fù)雜度和空間復(fù)雜度，提高算法的執(zhí)行效率。

【答案】D

【試題10分析】隊(duì)列是一種特殊的線性表示，只允許在表的一端插入元素；在表的另一端刪除元素，插入元素的一端叫“隊(duì)尾”，刪除元素的一端叫“隊(duì)頭”；先插入的元素先被刪除，是按“先進(jìn)先出”的原則組織數(shù)據(jù)的。

【答案】A

【試題11分析】棧和隊(duì)列都是操作受限的線性表，只允許在端點(diǎn)插入和刪除。不同點(diǎn)是棧只允許在表的一端進(jìn)行插入和刪除操作，而隊(duì)列允許在表的一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作。

【答案】C

【試題12分析】在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù)，各數(shù)據(jù)節(jié)點(diǎn)的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)之間的邏輯關(guān)系是由指針域來確定的。

【答案】B

【試題13分析】二分法查找只用于順序存儲的有序線性表，而順序查找用于順序存儲的非有序線性表和線性鏈表。

【答案】A

【試題14分析】對線性表進(jìn)行檢索，要求線性表是按順序方式存儲的，并按關(guān)鍵碼的大小排好序，而不按關(guān)鍵碼檢索頻率排序。

【答案】A

【試題15分析】根據(jù)二分法的查找過程，首先將90與表中的中間元素50進(jìn)行比較，由于90大于50，所以在線性表的后半部分查找。第二次比較的元素是后半部分的中間元素，即90，這時兩者相等，即查找成功。

【答案】B

【試題16分析】線性表的存儲通常有兩種存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。

【答案】A

【試題17分析】快速排序的基本思想是：經(jīng)過一趟排序待排序記錄分割成獨(dú)立的部分，其中前半部分元素都比基準(zhǔn)元素小，而后半部分元素都比基準(zhǔn)元素大；再分別對這兩個部分的記錄繼續(xù)進(jìn)行排序，以達(dá)到整個序列有序。在上述序列中，比關(guān)鍵碼33小的元素有4個，因此第一趟排序完成后關(guān)鍵碼33被放到第5個數(shù)的位置上。

【答案】B

【試題18分析】數(shù)據(jù)的存儲結(jié)構(gòu)有順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)兩種，不同存儲結(jié)構(gòu)的數(shù)據(jù)處理效率不同。由于鏈表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，元素的物理順序并不連續(xù)，對于插入和刪除無需移動元素，很方便，但當(dāng)查找元素時就需要逐個元素查找，因此查找的時間相對更長。

【答案】C

【試題19分析】線性鏈表的節(jié)點(diǎn)包括節(jié)點(diǎn)內(nèi)容以及指向下一節(jié)點(diǎn)的指針，因此其各個元素在存儲空間的位置不一定是連續(xù)的，同樣表頭元素也不一定存儲在其他元素的前面。

【答案】D

【試題20分析】一個算法應(yīng)該有0個或多個輸入，但是必須有一個或多個輸出。

【答案】B