【正文】 或“先進(jìn)后出”（First In Last Out，簡稱FILO）的原則組織數(shù)據(jù)的。棧的特性是具有記憶作用。所以出棧順序是CBA321?，F(xiàn)將元素A、B、C、D、E依次入棧，然后再依次出棧，則元素出棧的順序是 A、12345ABCDE B、EDCBA54321 C、ABCDE12345 D、54321EDCBA答案：B解析：棧是按照“先進(jìn)后出”或“后進(jìn)先出”的原則組織數(shù)據(jù)的。（18）下列關(guān)于棧的敘述中，正確的是 A、棧底元素一定是最后入棧的元素 B、棧頂元素一定是最先入棧的元素 C、棧操作遵循先進(jìn)后出的原則 D、以上三種說法都不對答案：C解析：棧是限定只能在表的一端進(jìn)行插入和刪除操作的線性表，必須按“后進(jìn)先出”的規(guī)則操作元素。在主函數(shù)調(diào)用子函數(shù)時，要首先保存主函數(shù)當(dāng)前的狀態(tài)，然后轉(zhuǎn)去執(zhí)行子函數(shù)，把子函數(shù)的運(yùn)行結(jié)果返回到主函數(shù)調(diào)用子函數(shù)時的位置，主函數(shù)再接著往下執(zhí)行，這種過程符合棧的特點(diǎn)。樹是一種簡單的非線性結(jié)構(gòu)，二叉樹是樹的一種。線性結(jié)構(gòu)和非線性結(jié)構(gòu)是從數(shù)據(jù)的邏輯結(jié)構(gòu)角度來講的，與該數(shù)據(jù)結(jié)構(gòu)中有多少個元素沒有關(guān)系，即使是空的二叉樹也是非線性結(jié)構(gòu)。各數(shù)據(jù)元素之間的前后件關(guān)系是由各結(jié)點(diǎn)的指針域來指示的，指向線性表中第一結(jié)點(diǎn)的指針HEAD稱為頭指針，當(dāng)HEAD=NULL時稱為空表。（11）下列數(shù)據(jù)結(jié)構(gòu)中，屬于非線性結(jié)構(gòu)的是 A、循環(huán)隊列 B、帶鏈隊列 C、二叉樹 D、帶鏈棧答案：C解析：根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間的前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。（9）下列描述中正確的是 A、數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)必定是一一對應(yīng)的 B、由于計算機(jī)存儲空間是向量式的存儲結(jié)構(gòu)，因此，數(shù)據(jù)的存儲結(jié)構(gòu)一定是線性結(jié)構(gòu) C、程序設(shè)計語言中的數(shù)據(jù)一般是順序存儲結(jié)構(gòu)，因此，利用數(shù)組只能處理線性結(jié)構(gòu) D、以上三種說法都不對答案：D解析：數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。根據(jù)各自的定義可知，算法的時間復(fù)雜度與空間復(fù)雜度并不相關(guān)。算法的執(zhí)行效率不僅與問題的規(guī)模有關(guān)，還與數(shù)據(jù)的存儲結(jié)構(gòu)有關(guān)。（5）下列敘述中正確的是 A、算法的效率只與問題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān) B、算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量 C、數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是一一對應(yīng)的 D、算法的時間復(fù)雜度與空間復(fù)雜度一定相關(guān)答案：B解析：算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量。（3）算法的空間復(fù)雜度是指 A、算法在執(zhí)行過程中所需要的計算機(jī)存儲空間 B、算法所處理的數(shù)據(jù)量 C、算法程序中的語句或指令條數(shù) D、算法在執(zhí)行過程中所需要的臨時工作單元數(shù)答案：A解析：算法的空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。（2）下列敘述中正確的是 A、算法就是程序 B、設(shè)計算法時只需要考慮數(shù)據(jù)結(jié)構(gòu)的設(shè)計 C、設(shè)計算法時只需要考慮結(jié)果的可靠性 D、以上三種說法都不對答案：D解析：所謂算法是指解題方案的準(zhǔn)確而完整的描述。是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。這個內(nèi)存空間包括算法程序所占的空間，輸入的初始數(shù)據(jù)所占的存儲空間以及算法執(zhí)行過程中所需要的額外空間。算法的工作量用算法所執(zhí)行的基本運(yùn)算的次數(shù)來度量，而算法所執(zhí)行的基本運(yùn)算次數(shù)是問題規(guī)模的函數(shù)；算法的空間復(fù)雜度一般是指執(zhí)行這個算法所需要的內(nèi)存空間。（6）下列敘述中正確的是 A、一個算法的空間復(fù)雜度大，則其時間復(fù)雜度也必定大 B、一個算法的空間復(fù)雜度大，則其時間復(fù)雜度必定小 C、一個算法的時間復(fù)雜度大，則其空間復(fù)雜度必定小 D、算法的時間復(fù)雜度與空間復(fù)雜度沒有直接關(guān)系答案：D解析：算法的復(fù)雜度主要包括時間復(fù)雜度和空間復(fù)雜度。（7）數(shù)據(jù)的存儲結(jié)構(gòu)是指 A、存儲在外存中的數(shù)據(jù) B、數(shù)據(jù)所占的存儲空間量 C、數(shù)據(jù)在計算機(jī)中的順序存儲方式 D、數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的表示答案：D解析：在對數(shù)據(jù)進(jìn)行處理時，各數(shù)據(jù)元素在計算機(jī)中的存儲關(guān)系，即為數(shù)據(jù)的存儲結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)存儲空間中的存放形式稱為數(shù)據(jù)的存儲結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)）。循環(huán)隊列、帶鏈隊列和帶鏈棧都是線性結(jié)構(gòu)，而二叉樹是非線性結(jié)構(gòu)。棧、隊列和雙向鏈表是線性結(jié)構(gòu)，樹是一種簡單的非線性結(jié)構(gòu)。（13）下面敘述中正確的是 A、線性表是線性結(jié)構(gòu) B、棧與隊列是非線性結(jié)構(gòu) C、線性鏈表是非線性結(jié)構(gòu) D、二叉樹是線性結(jié)構(gòu)答案：A解析：線性表是最簡單的、最常用的一種線性結(jié)構(gòu)。（14）下列關(guān)于棧的敘述正確的是 A、棧按“先進(jìn)先出”組織數(shù)據(jù) B、棧按“先進(jìn)后出”組織數(shù)據(jù) C、只能在棧底插入數(shù)據(jù) D、不能刪除數(shù)據(jù)答案：B解析：棧是限定在一端進(jìn)行插入和刪除的線性表，允許進(jìn)行插入和刪除元素的一端稱為棧頂，另一端稱為棧底。所以一般采用棧式存儲方式。（19）下列敘述中正確的是 A、在棧中，棧中元素隨棧底指針與棧頂指針的變化而動態(tài)變化 B、在棧中，棧頂指針不變，棧中元素隨棧底指針的變化而動態(tài)變化 C、在棧中，棧底指針不變，棧中元素隨棧頂指針的變化而動態(tài)變化 D、上述三種說法都不對答案：C解析：在棧中，允許插入與刪除的一端稱為棧頂，而不允許插入與刪除的另一端稱為棧底。所以出棧順序是EDCBA54321。（22）下列關(guān)于棧的描述中錯誤的是 A、棧是先進(jìn)后出的線性表 B、棧只能順序存儲 C、棧具有記憶作用 D、對棧的插入與刪除操作中，不需要改變棧底指針答案：B解析：棧是限定在一端進(jìn)行插入與刪除的線性表。（23）按照“后進(jìn)先出”原則組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是 A、隊列 B、棧 C、雙向鏈表 D、二叉樹答案：B解析：棧是限定在一端進(jìn)行插入與刪除的線性表。因此，棧也稱為“后進(jìn)先出表”或“先進(jìn)后出”表。因此，隊列又稱“先進(jìn)先出”或“后進(jìn)后出”的線性表。有序線性表既可以采用順序存儲結(jié)構(gòu)，又可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。在循環(huán)隊列中，用隊尾指針rear指向隊列中的隊尾元素，用隊頭指針front指向隊頭元素的前一個位置。當(dāng)rear或front等于隊列的長度加1時，就把rear或front值置為1。（31）設(shè)循環(huán)隊列的存儲空間為Q(1:35)，初始狀態(tài)為front=rear=35。棧和隊列都是一種線性表，屬于線性結(jié)構(gòu)。采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表稱之為線性鏈表。（37）下列關(guān)于線性鏈表的敘述中，正確的是 A、各數(shù)據(jù)結(jié)點(diǎn)的存儲空間可以不連續(xù)，但它們的存儲順序與邏輯順序必須一致 B、各數(shù)據(jù)結(jié)點(diǎn)的存儲順序與邏輯順序可以不一致，但它們的存儲空間必須連續(xù) C、進(jìn)行插入與刪除時，不需要移動表中的元素 D、以上都不正確答案：C解析：線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表。而在鏈?zhǔn)酱鎯Φ姆绞街?，將存儲空間的每一個存儲結(jié)點(diǎn)分為兩部分，一部分用于存儲數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存儲下一個元素的存儲序號，稱為指針域。而在鏈?zhǔn)酱鎯Φ姆绞街?，將存儲空間的每一個存儲結(jié)點(diǎn)分為兩部分，一部分用于存儲數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存儲下一個元素的存儲序號，稱為指針域。所以每個元素只存儲其值就可以了，而在鏈?zhǔn)酱鎯Φ姆绞街校瑢⒋鎯臻g的每一個存儲結(jié)點(diǎn)分為兩部分，一部分用于存儲數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存儲下一個元素的存儲序號，稱為指針域。（42）下列敘述中正確的是 A、順序存儲結(jié)構(gòu)的存儲一定是連續(xù)的，鏈?zhǔn)酱鎯Y(jié)構(gòu)的存儲空間不一定是連續(xù)的 B、順序存儲結(jié)構(gòu)只針對線性結(jié)構(gòu)，鏈?zhǔn)酱鎯Y(jié)構(gòu)只針對非線性結(jié)構(gòu) C、順序存儲結(jié)構(gòu)能存儲有序表，鏈?zhǔn)酱鎯Y(jié)構(gòu)不能存儲有序表 D、鏈?zhǔn)酱鎯Y(jié)構(gòu)比順序存儲結(jié)構(gòu)節(jié)省存儲空間答案：A解析：順序存儲方式主要用于線性的數(shù)據(jù)結(jié)構(gòu)，它把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元里，結(jié)點(diǎn)之間的關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。（44）下列敘述中正確的是 A、有一個以上根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不一定是非線性結(jié)構(gòu) B、只有一個根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不一定是線性結(jié)構(gòu) C、循環(huán)鏈表是非線性結(jié)構(gòu) D、雙向鏈表是非線性結(jié)構(gòu)答案：B解析：在數(shù)據(jù)結(jié)構(gòu)中，樹這類的的數(shù)據(jù)結(jié)構(gòu)只有一個根結(jié)點(diǎn)，但它不是線性結(jié)構(gòu)。（46）下列關(guān)于二叉樹的敘述中，正確的是 A、葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)少一個 B、葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多一個 C、葉子結(jié)點(diǎn)數(shù)是度為2的結(jié)點(diǎn)數(shù)的兩倍 D、度為2的結(jié)點(diǎn)數(shù)是度為1的結(jié)點(diǎn)數(shù)的兩倍答案：B解析：由二叉樹的性質(zhì)可以知道在二叉樹中葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多一個。（49）一棵二叉樹共有25個結(jié)點(diǎn)，其中5個是葉子結(jié)點(diǎn)，則度為1的結(jié)點(diǎn)數(shù)為 A、16 B、10 C、6 D、4答案：A解析：根據(jù)二叉樹的性質(zhì)，在任意二叉樹中，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個，故此度為1的結(jié)點(diǎn)個數(shù)=總結(jié)點(diǎn)數(shù)葉子節(jié)點(diǎn)數(shù)度為2的節(jié)點(diǎn)數(shù)=2554=16。（52）某二叉樹共有7個結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)只有1個，則該二叉樹的深度為（假設(shè)根結(jié)點(diǎn)在第1層） A、3 B、4 C、6 D、7答案：D解析：根據(jù)二叉樹的性質(zhì)，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個。題目中的二叉樹的葉子結(jié)點(diǎn)為1，因此度為2的結(jié)點(diǎn)的數(shù)目為0，故該二叉樹為12層，每層只有一個結(jié)點(diǎn)。154211=7。由于完全二叉樹中度為1的結(jié)點(diǎn)數(shù)只有兩種可能：0或1。（56）在深度為7的滿二叉樹中，葉子結(jié)點(diǎn)的個數(shù)為 A、32 B、31 C、64 D、63答案：C解析：所謂滿二叉樹是指這樣的一種二叉樹：除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個子結(jié)點(diǎn)。（57）對下列二叉樹進(jìn)行前序遍歷的結(jié)果是 A、DYBEAFCZX B、YDEBFZXCA C、ABDYECFXZ D、ABCDEFXYZ答案：C解析：二叉樹前序遍歷的簡單描述：若二叉樹為空，則結(jié)束返回；否則：①訪問根結(jié)點(diǎn)；②前序遍歷左子樹；③前序遍歷右子樹。因此，后序遍歷二叉樹的過程也是一個遞歸過程。（60）在長度為64的有序線性表中進(jìn)行順序查找，最壞情況下需要比較的次數(shù)為 A、63 B、64 C、6 D、7答案：B解析：順序查找又稱順序搜索。順序查找的使用情況：①線性表為無序表；②表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。有序表是指線性表中的元素按值非遞減排序（即從小到大，但允許相鄰元素值相等）的表。快速排序法也是一種互換類的排序方法，但由于它比冒泡排序法的速度快，因此，稱為快速排序法。（69）下列排序方法中，最壞情況下比較次數(shù)最少的是 A、冒泡排序 B、簡單選擇排序 C、直接插入排序 D、堆排序答案：D解析：冒泡排序、簡單選擇排序和直接插入排序法在最壞的情況下比較次數(shù)為：n(n1)/2。順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)在數(shù)據(jù)插入和刪除操作上的效率就存在差別。著名的“清晰第一，效率第二”的論點(diǎn)已成為當(dāng)今主導(dǎo)的程序設(shè)計風(fēng)格。（75）下列選項中不屬于結(jié)構(gòu)化程序設(shè)計方法的是 A、自頂向下 B、逐步求精 C、模塊化 D、可復(fù)用答案：D解析：結(jié)構(gòu)化程序設(shè)計方法的主要原則可以概括為：自頂向下，逐步求精，模塊化，限制使用goto語句?？蓮?fù)用性是指軟件元素不加修改成稍加修改便可在不同的軟件開發(fā)過程中重復(fù)使用的性質(zhì)。程序設(shè)計風(fēng)格總體而言應(yīng)該強(qiáng)調(diào)簡單和清晰，程序必須是可以理解的。③語句的結(jié)構(gòu)應(yīng)該簡單直接，不應(yīng)該為提高效率而把語句復(fù)雜化。（79）下列選項中屬于面向?qū)ο笤O(shè)計方法主要特征的是 A、繼承 B、自頂向下 C、模塊化 D、逐步求精答案：A解析：面向?qū)ο笤O(shè)計方法的主要特征有封裝性、繼承性和多態(tài)性。（82）下面對對象概念描述正確的是 A、對象間的通信靠消息傳遞 B、對象是名字和方法的封裝體 C、任何對象必須有繼承性 D、對象的多態(tài)性是指一個對象有多個操作答案：A解析：對象是面向?qū)ο蠓椒ㄖ凶罨镜母拍?。不是所有的對象都必須有繼承性。（84）下列選項中不屬于面向?qū)ο蟪绦蛟O(shè)計特征的是 A、繼承性 B、多態(tài)性 C、類比性 D、封裝性答案：C解析：面向?qū)ο蟪绦蛟O(shè)計的三個主要特征是：封裝性、繼承性和多態(tài)性。（85）構(gòu)成計算機(jī)軟件的是 A、源代碼 B、程序和數(shù)據(jù) C、程序和文檔 D、程序、數(shù)據(jù)及相關(guān)文檔答案：D解析：軟件由兩部分組成：一是機(jī)器可執(zhí)行的程序和數(shù)據(jù)；二是機(jī)器不可執(zhí)行的，與軟件開發(fā)、運(yùn)行、維護(hù)、使用等有關(guān)的文檔。計算機(jī)軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。③軟件在運(yùn)行、使用期間不存在磨損、老化問題。（88）軟件按功能可以分為應(yīng)用軟件、系統(tǒng)軟件和支撐軟件（或工具軟件）。（90）軟件按功能可以分為：應(yīng)用軟件、系統(tǒng)軟件和支撐軟件（或工具軟件）。系統(tǒng)軟件是計算機(jī)管理自身資源，提高計算機(jī)使用效率并為計算機(jī)用戶提供各種服務(wù)的軟件。軟件工程主要思想是強(qiáng)調(diào)在軟件開發(fā)過程中需要應(yīng)用工程化原則。（96）軟件生命周期中的活動不包括 A、市場調(diào)研 B、需求分析 C、軟件測試 D、軟件維護(hù)答案：A解析：軟件的生命周期描述了軟件從產(chǎn)生到最終消亡的全過程，生命周期中的活動包括需求分析、軟件設(shè)計（分為概要設(shè)計和詳細(xì)設(shè)計）、軟件實現(xiàn)、軟件測試和軟件維護(hù)，不包括市場調(diào)研。（98）下列選項中不屬于軟件生命周期開發(fā)階段任務(wù)的是 A、軟件測試 B、概要設(shè)計 C、軟件維護(hù) D、詳細(xì)設(shè)計答案：C解析：軟件生命周期是指軟件產(chǎn)品從提出、實現(xiàn)、使用、維護(hù)到停止使用退役的過程。詳細(xì)設(shè)計屬于 A、定義階段 B、開發(fā)階段 C、維護(hù)階段 D、上述三個階段答案：B解析：本題考查軟件生命周期的相關(guān)概念。還可以將軟件生命周期分為軟件定義、軟件開發(fā)及軟件運(yùn)行維護(hù)三個階段。（101）下面不屬于軟件設(shè)計原則的是 A、抽象 B、模塊化 C、自底向上 D、信息隱藏答案：C解析：軟件設(shè)計的基本原則包括抽象、信息