國家二級C++機試（數(shù)據(jù)結(jié)構(gòu)與算法）模擬試卷1（共207題）

國家二級C++機試（數(shù)據(jù)結(jié)構(gòu)與算法）模擬試卷1（共9套）（共207題）國家二級C++機試（數(shù)據(jù)結(jié)構(gòu)與算法）模擬試卷第1套一、選擇題(本題共18題，每題1.0分，共18分。)1、某二叉樹中有n個度為2的結(jié)點，則該二叉樹中的葉子結(jié)點數(shù)為()。A、n+1B、n—1C、2nD、n/2標(biāo)準(zhǔn)答案：A知識點解析：在任意一棵二叉樹中，度為0的結(jié)點(即葉子結(jié)點)總是比度為2的結(jié)點多一個。所以該二叉樹的葉子結(jié)點數(shù)等于n+l。2、—棵二叉樹共有25個結(jié)點，其中5個是葉子結(jié)點，則度為l的結(jié)點數(shù)為()。A、16B、10C、6D、4標(biāo)準(zhǔn)答案：A知識點解析：根據(jù)二叉樹的性質(zhì)，在任意二叉樹中，度為0的結(jié)點(即葉子結(jié)點)總是比度為2的結(jié)點多一個，故此度為l的結(jié)點個數(shù)：總結(jié)點數(shù)·葉子節(jié)點數(shù)．度為2的節(jié)點數(shù)=25—5—4=16。3、一棵二叉樹中共有80個葉子結(jié)點與70個度為1的結(jié)點，則該二叉樹中的總結(jié)點數(shù)為()。A、219B、229C、230D、231標(biāo)準(zhǔn)答案：B知識點解析：根據(jù)二叉樹的性質(zhì)，在任意二叉樹中，度為0的結(jié)點(即葉子結(jié)點)總是比度為2的結(jié)點多一個，故總結(jié)點數(shù)：葉子節(jié)點數(shù)+度為2的節(jié)點數(shù)+度為l的節(jié)點數(shù)=80+79+7=229。4、—棵二叉樹中共有70個葉子結(jié)點與80個度為1的結(jié)點，則該二叉樹中的總結(jié)點數(shù)為()。A、219B、221C、229D、231標(biāo)準(zhǔn)答案：A知識點解析：在二叉樹中，葉子結(jié)點個數(shù)為n0，則度為2的結(jié)點數(shù)n2=n0—1。本恿中葉子結(jié)點的個數(shù)為70，所以度為2的結(jié)點個數(shù)為69，因而總結(jié)點數(shù)=葉子結(jié)點數(shù)+度為1的結(jié)點數(shù)+度為2的結(jié)點數(shù)=70+80+69=219。5、某二叉樹共有7個結(jié)點，其中葉子結(jié)點只有1個，則該二叉樹的深度為(假設(shè)根結(jié)點在第1層)()。A、3B、4C、6D、7標(biāo)準(zhǔn)答案：D知識點解析：根據(jù)二叉樹的性質(zhì)，度為0的結(jié)點(即葉子結(jié)點)總是比度為2的結(jié)點多一個。題目中的二叉樹的葉子結(jié)點為1，因此度為2的結(jié)點的數(shù)目為O，故該二叉樹為7層，每層只有一個結(jié)點。6、某二叉樹共有12個結(jié)點，其中葉子結(jié)點只有1個。則該二叉樹的深度為(根結(jié)點在第1層)()。A、3B、6C、8D、12標(biāo)準(zhǔn)答案：D知識點解析：根據(jù)二叉樹的性質(zhì)，度為0的結(jié)點(即葉子結(jié)點)總是比度為2的結(jié)點多一個。題目中的二叉樹的葉子結(jié)點為1，因此度為2的結(jié)點的數(shù)目為0，故該二叉樹為12層，每層只有一個結(jié)點。7、設(shè)樹T的深度為4，其中度為1，2，3，4的結(jié)點個數(shù)分別為4，2，1，1。則T中的葉子結(jié)點數(shù)為()。A、8B、7C、6D、5標(biāo)準(zhǔn)答案：B知識點解析：深度為m二叉樹其總結(jié)點數(shù)為2m—1=24．1=15。總結(jié)點數(shù)減去度為l，2，3，4的結(jié)點個數(shù)就是葉子結(jié)點數(shù)。15—4—2—1—1=7。8、在深度為7的滿二叉樹中，葉子結(jié)點的個數(shù)為()。A、32B、31C、64D、63標(biāo)準(zhǔn)答案：C知識點解析：所謂滿二叉樹是指這樣的一種二叉樹：除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點。也就是在滿二叉樹中，每一層上的結(jié)點數(shù)都是最大結(jié)點數(shù)，即在滿二叉樹的第k層上有2k—1個結(jié)點，且深度為m的滿二叉樹有2m—1個結(jié)點。對于深度為7的滿二叉樹，葉子結(jié)點所在的是第7層，一共有27—1=64個葉子結(jié)點。全部結(jié)點共27—1=127個。9、對下列二叉樹進(jìn)行前序遍歷的結(jié)果是()。A、DYBEAFCZXB、YDEBFZXCAC、ABDYECFXZD、ABCDEFXYZ標(biāo)準(zhǔn)答案：C知識點解析：二叉樹前序遍歷的簡單描述：若二叉樹為空，則結(jié)束返回；否則：①訪問根結(jié)點；②前序遍歷左予樹：③前序遍歷右子樹?？梢?，前序遍歷二叉樹的過程是一個遞歸的過程。根據(jù)題目中給出的二叉樹的結(jié)構(gòu)可知前序遍歷的結(jié)果是ABDYECFXZ。10、對如下二叉樹進(jìn)行后序遍歷的結(jié)果為()。A、ABCDEFB、DBEAFCC、ABDECFD、DEBFCA標(biāo)準(zhǔn)答案：D知識點解析：所謂后序遍歷是指在訪問根據(jù)結(jié)點、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點，并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根點。因此，后序遍歷二叉樹的過程也是一個遞歸過程。其簡單描述為：若二叉樹為空，則結(jié)束返回：否則，先后序遍歷左子樹，然后后序遍歷右子樹，最后訪問根結(jié)點。對于后序遍歷，第一個訪問的結(jié)點一定是最左下的結(jié)點，最后一個訪問的結(jié)點一定是根結(jié)點，所以選項D)為正確答案。11、對長度為n的線性表進(jìn)行順序查找，在最壞情況下所需要的比較次數(shù)為()。A、log2nB、n/2C、nD、n+1標(biāo)準(zhǔn)答案：C知識點解析：在進(jìn)行順序查找過程中，如果被查的元素是線性表中的最后一個元素，或者被查元素根本不在線性表中，則為了查找這個元素需要與線性表中的所有元素進(jìn)行比較，這是順序查找的最壞情況，需要比較的次數(shù)為n次。12、在長度為64的有序線性表中進(jìn)行順序查找，最壞情況下需要比較的次數(shù)為()。A、63B、64C、6D、7標(biāo)準(zhǔn)答案：B知識點解析：順序查找又稱順序搜索。順序查找一般是指在線性表中查找指定的元素，其基本方法是：從線性表的第一元素開始，依次將線性表中的元素與被查找的元素進(jìn)行比較，若相等則表示找到(即查找成功)，若線性表中所有元素都與被查元素進(jìn)行了比較但都不相等，則表示線性表中沒有要找的元素(即查找失敗)。如果線性表中的第一個元素就是要查找的元素，則只需要做一次比較就查找成功；但如果要查找的元素是線性表中的最后一個元素，或者要查找元素不在線性表中，則需要與線性表中所有元素進(jìn)行比較，這是順序查找的最壞情況，比較次數(shù)為線性表的長度。13、下列敘述中正確的是()。A、對長度為n的有序鏈表進(jìn)行查找，最壞情況下需要的比較次數(shù)為nB、對長度為n的有序鏈表進(jìn)行對分查找，最壞情況下需要的比較次數(shù)為(n/2)C、對長度為n的有序鏈表進(jìn)行對分查找，最壞情況下需要的比較次數(shù)為(log2n)D、對長度為n的有序鏈表進(jìn)行對分查找，最壞情況下需要的比較次數(shù)為(nlog2n)標(biāo)準(zhǔn)答案：A知識點解析：本題主要考查的知識點為查找技術(shù)。順序查找的使用情況：①線性表為無序表；②表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。二分法查找只適用于順序存儲的有序表，并不適用于線性鏈表。14、在長度為n的有序線性表中進(jìn)行二分查找，最壞情況下需要比較的次數(shù)是()。A、o(n)B、o(n2)C、o(log2n)D、o(nlog2n)標(biāo)準(zhǔn)答案：C知識點解析：對于長度為n的有序線性表，在最壞情況下，二分法查找只需比較log2n次，而順序查找需要比較n次。15、下列數(shù)據(jù)結(jié)構(gòu)中，能用二分法進(jìn)行查找的是()。A、順序存儲的有序線性表B、線性鏈表C、二叉鏈表D、有序線性鏈表標(biāo)準(zhǔn)答案：A知識點解析：二分法查找只適應(yīng)于順序存儲的有序表。有序表是指線性表中的元素按值非遞減排序(即從小到大，但允許相鄰元素值相等)的表。16、對于長度為n的線性表，在最壞情況下，下列各排序法所對應(yīng)的比較次數(shù)中正確的是()。A、冒泡排序為n/2B、冒泡排序為nC、快速排序為nD、快速排序為n(n—1)/2標(biāo)準(zhǔn)答案：D知識點解析：假設(shè)線性表的長度為n，則在最壞情況下，冒泡排序需要經(jīng)過n/2遍的從前往后的掃描和n/2遍的從后往前的掃描，需要的比較次數(shù)為n(n—1)/2?？焖倥判蚍ㄒ彩且环N互換類的排序方法，但由于它比冒泡排序法的速度快，因此，稱為快速排序法。17、對長度為n的線性表作快速排序，茌最壞情況下，比較次數(shù)為()。A、nB、n—1C、n(n—1)D、n(n—1)/2標(biāo)準(zhǔn)答案：D知識點解析：假設(shè)線性表的長度為n，則在最壞情況下，冒泡排序需要經(jīng)過n，2遍的從前往后的掃描和n/2遍的從后往前的掃描，需要的比較次數(shù)為n(n—1)/2。快速排序法也是一種互換類的排序方法，但由于它比冒泡排序法的速度快，因此，稱為快速排序法。18、下列排序方法中，最壞情況下比較次數(shù)最少的是()。A、冒泡排序B、簡單選擇排序C、直接插入排序D、堆排序標(biāo)準(zhǔn)答案：D知識點解析：冒泡排序、簡單選擇排序和直接插入排序法在最壞的情況下比較次數(shù)為：n(n—1)/2。而堆排序法在最壞的情況下需要比較的次數(shù)為O(log2n)。其中堆排序的比較次數(shù)最少。國家二級C++機試（數(shù)據(jù)結(jié)構(gòu)與算法）模擬試卷第2套一、選擇題(本題共18題，每題1.0分，共18分。)1、算法的有窮性是指()。A、算法程序的運行時間是有限的B、算法程序所處理的數(shù)據(jù)量是有限的C、算法程序的長度是有限的D、算法只能被有限的用戶使用標(biāo)準(zhǔn)答案：A知識點解析：算法的有窮性，是指算法必須能在有限的時間內(nèi)做完，即算法必須能在執(zhí)行有限個步驟之后終止。2、算法的空間復(fù)雜度是指()。A、算法在執(zhí)行過程中所需要的計算機存儲空間B、算法所處理的數(shù)據(jù)量C、算法程序中的語句或指令條數(shù)D、算法在執(zhí)行過程中所需要的臨時工作單元數(shù)標(biāo)準(zhǔn)答案：A知識點解析：算法的空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。這個內(nèi)存空間包括算法程序所占的空間，輸入的初始數(shù)據(jù)所占的存儲空間以及算法執(zhí)行過程中所需要的額外空間。3、算法的時間復(fù)雜度是指()。A、算法的執(zhí)行時間B、算法所處理的數(shù)據(jù)量C、算法程序中的語句或指令條數(shù)D、算法在執(zhí)行過程中所需要的基本運算次數(shù)標(biāo)準(zhǔn)答案：D知識點解析：算法的時間復(fù)雜度，是指執(zhí)行算法所需要的計算工作量。算法的工作量可以用算法在執(zhí)行過程中所需基本運算的執(zhí)行次數(shù)來度量。4、下列敘述中正確的是()。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)標(biāo)準(zhǔn)答案：B知識點解析：算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量。算法的工作量用算法所執(zhí)行的基本運算的次數(shù)來度量，而算法所執(zhí)行的基本運算次數(shù)是問題規(guī)模的函數(shù)；算法的空間復(fù)雜度一般是指執(zhí)行這個算法所需要的內(nèi)存空間。算法的時間復(fù)雜度與空間復(fù)雜度并不相關(guān)。數(shù)據(jù)的邏輯結(jié)構(gòu)就是數(shù)據(jù)元素之間的邏輯關(guān)系，它是從邏輯上描述數(shù)據(jù)元素之間的關(guān)系，是獨立于計算機的：數(shù)據(jù)的存儲結(jié)構(gòu)是研究數(shù)據(jù)元素和數(shù)據(jù)元素之間的關(guān)系如何在計算機中表示，它們并非一一對應(yīng)。算法的執(zhí)行效率不僅與問題的規(guī)模有關(guān)，還與數(shù)據(jù)的存儲結(jié)構(gòu)有關(guān)。5、下列敘述中正確的是()。A、—個算法的空間復(fù)雜度大，則其時間復(fù)雜度也必定大B、—個算法的空間復(fù)雜度大，則其時間復(fù)雜度必定小C、一個算法的時間復(fù)雜度大，則其空間復(fù)雜度必定小D、算法的時間復(fù)雜度與空間復(fù)雜度沒有直接關(guān)系標(biāo)準(zhǔn)答案：D知識點解析：算法的復(fù)雜度主要包括時間復(fù)雜度和空間復(fù)雜度。算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量，算法的工作量用算法所執(zhí)行的基本運算次數(shù)來度量，而算法所執(zhí)行的基本運算次數(shù)是問題規(guī)模的函數(shù)，即算法的工作量=f(n)，其中n是問題的規(guī)模；算法的空間復(fù)雜度，一般是指執(zhí)行這個算法所需要的內(nèi)存空間。一個算法所占用的存儲空間包括算法程序所占用的空間、輸入的初始數(shù)據(jù)所占的存儲空間以及算法執(zhí)行過程中所需要的額外空間。根據(jù)各自的定義可知，算法的時間復(fù)雜度與空間復(fù)雜度并不相關(guān)。6、數(shù)據(jù)的存儲結(jié)構(gòu)是指()。A、存儲在外存中的數(shù)據(jù)B、數(shù)據(jù)所占的存儲空間量C、數(shù)據(jù)在計算機中的順序存儲方式D、數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示標(biāo)準(zhǔn)答案：D知識點解析：在對數(shù)據(jù)進(jìn)行處理時，各數(shù)據(jù)元素在計算機中的存儲關(guān)系，即為數(shù)據(jù)的存儲結(jié)構(gòu)。7、下列描述中正確的是()。A、數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)必定是一一對應(yīng)的B、由于計算機存儲空間是向量式的存儲結(jié)構(gòu)，因此，數(shù)據(jù)的存儲結(jié)構(gòu)一定是線性結(jié)構(gòu)C、程序設(shè)計語言中的數(shù)據(jù)一般是順序存儲結(jié)構(gòu)，因此，利用數(shù)組只能處理線性結(jié)構(gòu)D、以上三種說法都不對標(biāo)準(zhǔn)答案：D知識點解析：數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式稱為數(shù)據(jù)的存儲結(jié)構(gòu)(也稱數(shù)據(jù)的物理結(jié)構(gòu))。一般來說，一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲結(jié)構(gòu)，常用的存儲結(jié)構(gòu)有順序、鏈接、索引等。8、下列敘述中正確的是()。A、有一個以上根結(jié)點的數(shù)據(jù)結(jié)構(gòu)不一定是非線性結(jié)構(gòu)B、只有一個根結(jié)點的數(shù)據(jù)結(jié)構(gòu)不一定是線性結(jié)構(gòu)C、循環(huán)鏈表是非線性結(jié)構(gòu)D、雙向鏈表是非線性結(jié)構(gòu)標(biāo)準(zhǔn)答案：B知識點解析：在數(shù)據(jù)結(jié)構(gòu)中，樹這類的數(shù)據(jù)結(jié)構(gòu)只有一個根結(jié)點，但它不是線性結(jié)構(gòu)。9、下列數(shù)據(jù)結(jié)構(gòu)中，屬于非線性結(jié)構(gòu)的是()。A、循環(huán)隊列B、帶鏈隊列C、二叉樹D、帶鏈棧標(biāo)準(zhǔn)答案：C知識點解析：根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間的前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。循環(huán)隊列、帶鏈隊列和帶鏈棧都是線性結(jié)構(gòu)，而二叉樹是非線性結(jié)構(gòu)。10、下列描述中正確的是()。A、線性鏈表是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)B、棧與隊列是非線性結(jié)構(gòu)C、雙向鏈表是非線性結(jié)構(gòu)D、只有根結(jié)點的二叉樹是線性結(jié)構(gòu)標(biāo)準(zhǔn)答案：A知識點解析：線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表。線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)的基本單位稱為存儲結(jié)點，每個存儲結(jié)點包括數(shù)據(jù)域和指針域兩個組成部分。各數(shù)據(jù)元素之間的前后件關(guān)系是由各結(jié)點的指針域來指示的，指向線性表中第一結(jié)點的指針HEAD稱為頭指針，當(dāng)HEAD=NULL時稱為空表。棧、隊列和雙向鏈表是線性結(jié)構(gòu)，樹是一種簡單的非線性結(jié)構(gòu)。在樹這種數(shù)據(jù)結(jié)構(gòu)中，所有數(shù)據(jù)元素的關(guā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)。11、下面敘述中正確的是()。A、線性表是線性結(jié)構(gòu)B、棧與隊列是非線性結(jié)構(gòu)C、線性鏈表是非線性結(jié)構(gòu)D、二叉樹是線性結(jié)構(gòu)標(biāo)準(zhǔn)答案：A知識點解析：線性表是最簡單的、最常用的一種線性結(jié)構(gòu)。所謂線性鏈表指的是采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表。棧和隊列其實是一種特殊的線性表。樹是一種簡單的非線性結(jié)構(gòu)，二叉樹是樹的一種。12、下列關(guān)于棧的敘述正確的是()。A、棧按“先進(jìn)先出”組織數(shù)據(jù)B、棧按“先進(jìn)后出”組織數(shù)據(jù)C、只能在棧底插入數(shù)據(jù)D、不能刪除數(shù)據(jù)標(biāo)準(zhǔn)答案：B知識點解析：棧是限定在一端進(jìn)行插入和刪除的線性表，允許進(jìn)行插入和刪除元素的一端稱為棧頂，另一端稱為棧底。棧是按照“先進(jìn)后出”的原則組織數(shù)據(jù)的。13、支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是()。A、棧B、樹C、隊列D、二叉樹標(biāo)準(zhǔn)答案：A知識點解析：棧是一種限定在一端進(jìn)行插入與刪除的線性表。在主函數(shù)調(diào)用子函數(shù)時，要首先保存主函數(shù)當(dāng)前的狀態(tài)，然后轉(zhuǎn)去執(zhí)行子函數(shù)，把子函數(shù)的運行結(jié)果返回到主函數(shù)調(diào)用子函數(shù)時的位置，主函數(shù)再接著往下執(zhí)行，這種過程符合棧的特點。所以一般采用棧式存儲方式。14、下列數(shù)據(jù)結(jié)構(gòu)中，能夠按照“先進(jìn)后出”原則存取數(shù)據(jù)的是()。A、循環(huán)隊列B、棧C、隊列D、二叉樹標(biāo)準(zhǔn)答案：B知識點解析：棧按照“先進(jìn)后出”(FILO)或“后進(jìn)先出”(LIFO)組織數(shù)據(jù)；隊列是“先進(jìn)先出”(FIFO)或“后進(jìn)后出”(LILO)的線性表。15、下列關(guān)于棧敘述正確的是()。A、棧頂元素最先能被刪除B、棧頂元素最后才能被刪除C、棧底元素永遠(yuǎn)不能被刪除D、以上三種說法都不對標(biāo)準(zhǔn)答案：A知識點解析：棧是先進(jìn)后出的線性表，棧頂?shù)脑刈钕缺粍h除，棧底的元素最后被刪除。16、下列敘述中正確的是()。A、在棧中，棧中元素隨棧底指針與棧頂指針的變化而動態(tài)變化B、在棧中，棧頂指針不變，棧中元素隨棧底指針的變化而動態(tài)變化C、在棧中，棧底指針不變，棧中元素隨棧頂指針的變化而動態(tài)變化D、上述三種說法都不對標(biāo)準(zhǔn)答案：C知識點解析：在棧中，允許插入與刪除的一端稱為棧頂，而不允許插入與刪除的另一端稱為棧底。棧跟隊列不同，元素只能在棧頂壓入或彈出，棧底指針不變，棧中元素隨棧頂指針的變化而動態(tài)變化，遵循后進(jìn)先出的規(guī)則。17、一個棧的初始狀態(tài)為空?，F(xiàn)將元素1、2、3、4、5、A、B、C、D、E依次入棧，然后再依次出棧，則元素出棧的順序是()。A、12345ABCDEB、EDCBA54321C、ABCDE12345D、54321EDCBA標(biāo)準(zhǔn)答案：B知識點解析：棧是按照“先進(jìn)后出”或“后進(jìn)先出”的原則組織數(shù)據(jù)的。所以出棧順序是EDCBA54321。18、下列關(guān)于棧的描述中錯誤的是()。A、棧是先進(jìn)后出的線性表B、棧只能順序存儲C、棧具有記憶作用D、對棧的插入與刪除操作中，不需要改變棧底指針標(biāo)準(zhǔn)答案：B知識點解析：棧是限定在一端進(jìn)行插入與刪除的線性表。棧頂(top)：插入數(shù)據(jù)(即入棧)的一端：棧底(bottom)：不能入棧也不能出棧的一端。棧存儲數(shù)據(jù)的原則：“先進(jìn)后出”或“后進(jìn)先出”。棧的特性是具有記憶作用。國家二級C++機試（數(shù)據(jù)結(jié)構(gòu)與算法）模擬試卷第3套一、選擇題(本題共26題，每題1.0分，共26分。)1、設(shè)一棵完全二叉樹共有700個結(jié)點，則此二叉樹中的葉子結(jié)點數(shù)為A、85B、120C、250D、350標(biāo)準(zhǔn)答案：D知識點解析：①具有n個結(jié)點的完全二叉樹的深度為[long2n]+1，計算出該完全二叉樹的深度為10。②設(shè)度為0的結(jié)點(即葉子結(jié)點)為n0，度為1的結(jié)點為n1，度為2的結(jié)點為n2，總結(jié)點數(shù)為n，深度為k。n=n1+n2+n0，由于n0=n2+1則n2=n0—1，故n=n1+n0—1+n0=n1+2n0-1。由于完全二叉樹中度為l的結(jié)點數(shù)只有兩種可能：0或1。③假設(shè)度為1的結(jié)點數(shù)為0即滿：二叉樹，根據(jù)滿二叉樹的定義，其2m一1個結(jié)點，根據(jù)以上計算所得的深度10來計算，應(yīng)有210一1=1024—1=1023個結(jié)點，顯然與題目中700個結(jié)點不符。因此，度為1的結(jié)點數(shù)必然為1。故n=n1+2n0-1=1+2n0-1=2n0，則n0=n／2=700／2=350。2、在深度為7的滿二叉樹中，葉子結(jié)點的個數(shù)為A、32B、31C、64D、63標(biāo)準(zhǔn)答案：C知識點解析：所謂滿二叉樹是指這樣的一種二叉樹：除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點。也就是在滿二又樹中，每一層上的結(jié)點數(shù)都是最大結(jié)點數(shù)，即在滿二叉樹的第k層上有2k-1個結(jié)點，且深度為m的滿二叉樹有2m-1個結(jié)點。對于深度為7的滿二叉樹，葉子結(jié)點所在的是第7層，一共有27-1=64個葉子結(jié)點。全部結(jié)點共27-1=127個。3、對下列二叉樹進(jìn)行前序遍歷的結(jié)果是A、DYBEAFCZXB、YDEBFZXCAC、ABDYECFXZD、ABCDEFXYZ標(biāo)準(zhǔn)答案：C知識點解析：二叉樹前序遍歷的簡單描述：若二叉樹為空，則結(jié)束返回；否則：①防問根結(jié)點：②前序遍歷左子樹；③前序遍歷右子樹?？梢?，前序遍歷二叉樹的過程是一個遞歸的過程。根據(jù)題目中給出的二叉樹的結(jié)構(gòu)可知前序遍歷的結(jié)果是ABDYECFXZ。4、對如下二叉樹進(jìn)行后序遍歷的結(jié)果為A、ABCDEFB、DBEAFCC、ABDECFD、DEBFCA標(biāo)準(zhǔn)答案：D知識點解析：所謂后序遍歷是指在訪問根據(jù)結(jié)點、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點，并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根點。因此，后序遍歷二叉樹的過程也是一個遞歸過程。其簡單描述為：若二叉樹為空，則結(jié)束返回；否則，先后序遍歷左子樹，然后后序遍歷釘子樹，最后訪問根結(jié)點。對于后序遍歷，第一個訪問的結(jié)點一定是最左下的結(jié)點，最后一個訪問的結(jié)點一定足根結(jié)點，所以選項D)為正確答案。5、對長度為n的線性表進(jìn)行順序查找，在最壞情況下所需要的比較次數(shù)為A、log2nB、n／2C、nD、n+1標(biāo)準(zhǔn)答案：C知識點解析：在進(jìn)行順序查找過程中，如果被查的元素是線性表中的最后一個元素，或者被查元素根本不在線性表中，則為了查找這個元素需要與線性表中的所有元素進(jìn)行比較，這是順序查找的最壞情況，需要比較的次數(shù)為n次。6、在長度為64的有序線性表中進(jìn)行順序查找，最壞情況下需要比較的次數(shù)為A、63B、64C、6D、7標(biāo)準(zhǔn)答案：B知識點解析：順序查找又稱順序搜索。順序查找一般是指在線性表中查找指定的元素，其基本方法是：從線性表的第一元素開始，依次將線性表中的元素與被查找的元素進(jìn)行比較，若相等則表示找到(即查找成功)，若線性表中所有元素都與被查元素進(jìn)行了比較但都不相等，則表示線性表中沒有要找的元素(即查找失敗)。如果線性表中的第一個元素就是要查找的元素，則只需要做一次比較就查找成功；但如果要查找的元素是線性表中的最后一個元素，或者要查找元素不在線性表中，則需要與線性表中所有元素進(jìn)行比較，這是順序查找的最壞情況，比較次數(shù)為線性表的長度。7、下列敘述中正確的是A、對長度為n的有序鏈表進(jìn)行查找，最壞情況下需要的比較次數(shù)為nB、對長度為n的有序鏈表進(jìn)行對分查找，最壞情況下需要的比較次數(shù)為(n／2)C、對長度為n的有序鏈表進(jìn)行對分查找，最壞情況下需要的比較次數(shù)為(log2n)D、對長度為n的有序鏈表進(jìn)行對分查找，最壞情況下需要的比較次數(shù)為(nlog2n)標(biāo)準(zhǔn)答案：A知識點解析：本題主要考查的知識點為查找技術(shù)。順序查找的使用情況：①線性表為無序表：②表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。二分法查找只適用于順序存儲的有序表，并不適用于線性鏈表。8、在長度為n的有序線性表中進(jìn)行二分查找，最壞情況下需要比較的次數(shù)是A、O(n)B、O(n2)C、O(log2n)D、O(nlog2n)標(biāo)準(zhǔn)答案：C知識點解析：對于長度為n的有序線性表，在最壞情況下，二分法查找只需比較log2n次，而順序查找需要比較n次。9、T列數(shù)據(jù)結(jié)構(gòu)中，能用二分法進(jìn)行查找的是A、順序存儲的有序線性表B、線性鏈表C、二叉鏈表D、有序線性鏈表標(biāo)準(zhǔn)答案：A知識點解析：二分法查找只適應(yīng)于順序存儲的有序表。有序表是指線性表中的元素按值非遞減排序(即從小到大，但允許相鄰元素值相等)的表。10、冒泡排序在最壞情況下的比較次數(shù)是A、n(n+1)／2B、nlog2nC、n(n-1)／2D、n／2標(biāo)準(zhǔn)答案：C知識點解析：對n個結(jié)點的線性表采用冒泡排序，在最壞情況下，冒泡排序需要經(jīng)過n／2遍的從前往后的掃描和n／2遍的從后往前的掃描，需要的比較次數(shù)為n(n-1)／2。11、對長度為10的線性表進(jìn)行冒泡排序，最壞情況下需要比較的次數(shù)為A、9B、10C、45D、90標(biāo)準(zhǔn)答案：C知識點解析：線性表的長度為n，最壞情況下冒泡排序需要比較的次數(shù)為n(n-1)／2。12、對于長度為n的線性表，在最壞情況下，下列各排序法所對應(yīng)的比較次數(shù)中正確的是A、冒泡排序為n／2B、冒泡排序為nC、快速排序為nD、快速排序為n(n一1)／2標(biāo)準(zhǔn)答案：D知識點解析：假設(shè)線性表的長度為n，則在最壞情況下，冒泡排序需要經(jīng)過n／2遍的從前往后的掃描和n／2遍的從后往前的掃描，需要的比較次數(shù)為n(n-1)／2?？焖倥判蚍ㄒ彩且环N交換類的排序方法，但由于它比冒泡排序法的速度快，因此，稱為快速排序法。13、對長度為n的線性表作快速排序，在最壞情況下，比較次數(shù)為A、nB、n-1C、n(n一1)D、n(n-1)／2標(biāo)準(zhǔn)答案：D知識點解析：假設(shè)線性表的長度為n，則在最壞情況下，冒泡排序需要經(jīng)過n／2遍的從前往后的掃描和n／2遍的從后往前的掃描，需要的比較次數(shù)為n(n-1)／2?？焖倥判蚍ㄒ彩且环N互換類的排序方法，但由于它比冒泡排序法的速度快，因此，稱為快速排序法。14、對長度為n的線性表排序，在最壞情況下，比較次數(shù)不是n(n-1)／2的排序方法是A、快速排序B、冒泡排序C、直接插入排序D、堆排序標(biāo)準(zhǔn)答案：D知識點解析：各種排序方法中最壞情況下需要比較的次數(shù)分別為：冒泡排序n(n-1)／2、快速排序n(n-1)／2、簡單插入排序n(n-1)／2、希爾排序O(n1．5)、簡單選擇排序n(n-1)／2、堆排序O(nlog2n)。15、下列排序方法中，最壞情況下比較次數(shù)最少的是A、冒泡排序B、簡單選擇排序C、直接插入排序D、堆排序標(biāo)準(zhǔn)答案：D知識點解析：冒泡排序、簡單選擇排序和直接插入排序法在最壞的情況下比較次數(shù)為：n(n-1)／2。而堆排序法在最壞的情況下需要比較的次數(shù)為O(nlog2n)。其中堆排序的比較次數(shù)最少。16、下列數(shù)據(jù)結(jié)構(gòu)中，不能采用順序存儲結(jié)構(gòu)的是A、棧B、堆C、隊列D、非完全二叉樹標(biāo)準(zhǔn)答案：D知識點解析：堆中某個結(jié)點的值總是不大于或不小于其父結(jié)點的值、堆總是一棵完全二叉樹，可以以順序存儲結(jié)構(gòu)存儲；隊列的存儲結(jié)構(gòu)分為鏈?zhǔn)酱鎯?、順序存儲兩種；棧作為一種數(shù)據(jù)結(jié)構(gòu)，是一種只能在一端進(jìn)行插入和刪除操作的特殊線性表，可以以順序存儲結(jié)構(gòu)存儲。17、設(shè)二叉樹共有375個結(jié)點，其中度為2的結(jié)點有187個。則度為1的結(jié)點個數(shù)是A、0B、1C、188D、不可能有這樣的二叉樹標(biāo)準(zhǔn)答案：A知識點解析：二叉樹的每個結(jié)點至多只有二棵子樹(不存在度大于2的結(jié)點)，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2i-1個結(jié)點；深度為k的二叉樹至多有2k-1個結(jié)點；對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1。本題中，度為2的結(jié)點有187個，葉子結(jié)點應(yīng)該有187+1=188個，度為1的結(jié)點個數(shù)=375-187—188=0。18、在帶鏈隊列中，經(jīng)過一系列正常的操作后，如果front=rear，則隊列中的元素個數(shù)為A、0或1B、0C、1D、隊列滿標(biāo)準(zhǔn)答案：A知識點解析：隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端(front)進(jìn)行刪除操作，而在表的后端(rear)進(jìn)行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊尾，進(jìn)行刪除操作的端稱為隊頭。隊列的鏈?zhǔn)酱鎯σ卜Q為鏈隊列。為了便于操作，可給鏈隊列添加1個頭結(jié)點，并令頭指針指向頭結(jié)點。隊列為空的判斷條件是頭指針和尾指針的值相同，且均指向頭結(jié)點。當(dāng)隊列為空(0)或1時，front=rear。19、設(shè)一棵樹的度為3，其中沒有度為2的結(jié)點，且葉子結(jié)點數(shù)為5。該樹中度為3的結(jié)點數(shù)為A、1B、2C、3D、不可能有這樣的樹標(biāo)準(zhǔn)答案：B知識點解析：樹的度是指一棵樹中，最大的結(jié)點的度稱為樹的度。本題中樹的度為3，那么樹中最少有一個結(jié)點的度為3。而樹中沒有度為2的結(jié)點，葉子結(jié)點數(shù)為5，度為1的結(jié)點下面只有一個葉子結(jié)點。因此，該樹中含2個度為3的結(jié)點滿足題目要求。20、下列敘述中正確的是A、帶鏈棧的棧底指針是固定的B、帶鏈棧的棧底指針是隨棧的操作而動態(tài)變化的C、若帶鏈隊列的隊頭指針與隊尾指針相同，則隊列為空D、若帶鏈隊列的隊頭指針與隊尾指針相同，則隊列中至少有一個元素標(biāo)準(zhǔn)答案：B知識點解析：棧(stack)又名堆棧，它是一種運算受限的線性表。其限制是僅允許在表的一端進(jìn)行插入和刪除運算。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進(jìn)棧、入?；驂簵?，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素又稱作出?；蛲藯?，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。帶鏈棧的棧底指針是隨棧的操作而動態(tài)變化的；若帶鏈隊列的隊頭指針與隊尾指針相同，則隊列可能為0也可能為1。21、帶鏈隊列空的條件是A、front=rear=NULLB、front=rear=一1C、front=NULL且rear=一1D、front=-1且rear=NULL標(biāo)準(zhǔn)答案：A知識點解析：帶鏈隊列空的條件有兩個：一個是front=tear，一個是他們都等于空。22、設(shè)一棵樹的度為3，其中沒有度為2的結(jié)點，且葉子結(jié)點數(shù)為6。該樹中度為3的結(jié)點數(shù)為A、1B、2C、3D、不可能有這樣的樹標(biāo)準(zhǔn)答案：D知識點解析：樹的度是指一棵樹中，最大的結(jié)點的度稱為樹的度。本題中樹的度為3，也就是最少有一個度為3的結(jié)點。要求沒有度為2的結(jié)點，且葉子結(jié)點為6，如果要有度為3的結(jié)點，那么最多只有5個葉子結(jié)點，而畫不出6個葉子結(jié)點。因此這樣的樹是沒有的。23、下列敘述中正確的是A、循環(huán)隊列是線性結(jié)構(gòu)B、循環(huán)隊列是線性邏輯結(jié)構(gòu)C、循環(huán)隊列是鏈?zhǔn)酱鎯Y(jié)構(gòu)D、循環(huán)隊列是非線性存儲結(jié)構(gòu)標(biāo)準(zhǔn)答案：A知識點解析：為充分利用向量空間，克服“假溢出”現(xiàn)象的方法是：將向量空間想象為一個首尾相接的圓環(huán)，并稱這種向量為循環(huán)向量。存儲在其中的隊列稱為循環(huán)隊列(CircularQueue)。線性結(jié)構(gòu)是一個有序數(shù)據(jù)元素的集合。常用的線性結(jié)構(gòu)有：線性表，棧，隊列，雙隊列，數(shù)組，串。常見的非線性結(jié)構(gòu)有：二維數(shù)組，多維數(shù)組，廣義表，樹(二叉樹等)，圖。24、設(shè)某棵樹的度為3，其中度為3、2、1的結(jié)點個數(shù)分別為3、O、4。則該樹中的葉子結(jié)點數(shù)為A、7B、8C、6D、不可能有這樣的樹標(biāo)準(zhǔn)答案：A知識點解析：樹的度是指一棵樹中，最大的結(jié)點的度稱為“樹的度”。根據(jù)題目可知本樹中沒有度為2的結(jié)點。樹的總結(jié)點=(度1*個數(shù)+度2*個數(shù)…)+1，這里我們設(shè)總結(jié)點數(shù)為n，那么n=3*3+2*0+1*4+1=14。樹的葉子結(jié)點數(shù)等于總結(jié)點減去所有度不為0的結(jié)點，也就是14—3—4=7。25、設(shè)有一個棧與一個隊列的初始狀態(tài)均為空?，F(xiàn)有一個序列A，B，C，D，E，F(xiàn)，G，H。先分別將序列中的前4個元素依次入棧，后4個元素依次入隊；然后分別將棧中的元素依次退棧，再將隊列中的元素依次退隊。最后得到的序列為A、D，C，B，A，E，F(xiàn)，G，HB、D，C，B，A，H，G，F(xiàn)，EC、A，B，C，D，E，F(xiàn)，G，HD、A，B，C，D，H，G，F(xiàn)，E標(biāo)準(zhǔn)答案：A知識點解析：棧(stack)又名堆棧，它是一種運算受限的線性表。其限制是僅允許在表的一端進(jìn)行插入和刪除運算。因此棧的出棧順序是先入后出，所以順序是D，C，B，A。隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端(front)進(jìn)行刪除操作，而在表的后端(rear)進(jìn)行插入操作，和棧一樣，隊列足一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊尾，進(jìn)行刪除操作的端稱為隊頭。因此，隊的出隊順序是，先入先出，所以順序是E，F(xiàn)，Q，H。最后的順序是：D，C，B，A，E，F(xiàn)，G，H。26、下列敘述中錯誤的是A、具有兩個根結(jié)點的數(shù)據(jù)結(jié)構(gòu)一定屬于非線性結(jié)構(gòu)B、具有兩個以上指針域的鏈?zhǔn)浇Y(jié)構(gòu)一定屬于非線性結(jié)構(gòu)C、具有兩個以上葉子結(jié)點的數(shù)據(jù)結(jié)構(gòu)一定屬于非線性結(jié)構(gòu)D、具有一個根結(jié)點且只有一個葉子結(jié)點的數(shù)據(jù)結(jié)構(gòu)也可能是非線性結(jié)構(gòu)標(biāo)準(zhǔn)答案：B知識點解析：非線性結(jié)構(gòu)，數(shù)學(xué)用語，其邏輯特征是一個結(jié)點元素可能有多個直接前趨和多個直接后繼。常見的非線性結(jié)構(gòu)有：二維數(shù)組，多維數(shù)組，廣義表，樹(二又樹等)，圖。國家二級C++機試（數(shù)據(jù)結(jié)構(gòu)與算法）模擬試卷第4套一、選擇題(本題共24題，每題1.0分，共24分。)1、下列結(jié)構(gòu)中屬于線性結(jié)構(gòu)鏈?zhǔn)酱鎯Φ氖茿、雙向鏈表B、循環(huán)隊列C、二叉鏈表D、二維數(shù)組標(biāo)準(zhǔn)答案：A知識點解析：數(shù)據(jù)元素之間的關(guān)系有兩種不同的表示方法：順序映象和非順序映象，并由此得到兩種不同的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示。雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結(jié)點中都有兩個指針，分別指向直接后繼和直接前驅(qū)，它的存儲方式是線性結(jié)構(gòu)鏈?zhǔn)健Ｑh(huán)隊列、二叉鏈表和二維數(shù)組都是順序存儲結(jié)構(gòu)。2、下列敘述中錯誤的是A、循環(huán)鏈表中有一個表頭結(jié)點B、循環(huán)鏈表的存儲空間是連續(xù)的C、循環(huán)鏈表實現(xiàn)了空表與非空表運算的統(tǒng)一D、循環(huán)鏈表的表頭指針與循環(huán)鏈表中最后一個結(jié)點的指針均指向表頭結(jié)點標(biāo)準(zhǔn)答案：B知識點解析：循環(huán)鏈表是另一種形式的鏈?zhǔn)酱尜A結(jié)構(gòu)。它的特點是表中最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表形成一個環(huán)。循環(huán)鏈表的結(jié)點是指針指向，他個一定要是連續(xù)的存儲空間，也可以是斷開的空間。3、度為3的一棵樹共有30個結(jié)點，其中度為3、l的結(jié)點個數(shù)分別為3、4。則該樹中的葉子結(jié)點數(shù)為A、14B、15C、16D、不可能有這樣的樹標(biāo)準(zhǔn)答案：B知識點解析：根據(jù)題目可知本樹中還有度為2的結(jié)點。樹的總結(jié)點=(度1*個數(shù)+度2*個數(shù)…)+1，這里我們設(shè)度為2的結(jié)點數(shù)為x，那么30=3*3+2*x+1*4+1=2*x+14，由此可計算出x=8。樹的葉子結(jié)點數(shù)等于總結(jié)點減去所有度不為0的結(jié)點，也就是30-3-8-4=15。4、在長度為97的順序有序表中作二分查找，最多需要的比較次數(shù)為A、7B、96C、48D、6標(biāo)準(zhǔn)答案：A知識點解析：二分查找又稱折半查找，優(yōu)點是比較次數(shù)少，查找速度快，平均性能好；其缺點是要求待查表為有序表，且插入刪除困難。最多比較次數(shù)的計算方式：k=log2n。其中n代表長度，k為比較次數(shù)。本題中可以計算出k=7。5、下列結(jié)構(gòu)中屬于非線性結(jié)構(gòu)的是A、二叉鏈表B、二維數(shù)組C、循環(huán)隊列D、雙向鏈表標(biāo)準(zhǔn)答案：B知識點解析：線性結(jié)構(gòu)是一個有序數(shù)據(jù)元素的集合。常用的線性結(jié)構(gòu)有：線性表，棧，隊列，雙隊列，數(shù)組，串；常見的非線性結(jié)構(gòu)有：二維數(shù)組，多維數(shù)組，廣義表，樹(二叉樹等)，圖。循環(huán)隊列、雙向鏈表和二叉鏈表都是線性結(jié)構(gòu)，而二維數(shù)組是非線性結(jié)構(gòu)。6、從表中任何一個結(jié)點位置出發(fā)就可以不重復(fù)地訪問到表中其他所有結(jié)點的鏈表是A、循環(huán)鏈表B、雙向鏈表C、單向鏈表D、二叉鏈表標(biāo)準(zhǔn)答案：A知識點解析：循環(huán)鏈表是另一種彤式的鏈?zhǔn)酱尜A結(jié)構(gòu)。它的特點是表中最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表形成一個環(huán)，循環(huán)一圈就訪問到了表中其他所有結(jié)點而不重復(fù)。7、設(shè)二叉樹的前序序列與中序序列均為ABCDEFGH，則該二叉樹的后序序列為A、HGFEDCBAB、ABCDEFGHC、ABCDHGFED、DCBAHGFE標(biāo)準(zhǔn)答案：A知識點解析：前序遍歷(DLR)是二叉樹遍歷的一種，也叫做先根遍歷、先序遍歷、前序周游，可記做根左右；中序遍歷(LDR)是二叉樹遍歷的一種，也叫做中根遍歷、中序周游，可記做左根右；后序遍歷(LRD)是二叉樹遍歷的一種，也叫做后根遍歷、后序周游，可記做左右根。根據(jù)題中前序和中序序列均為ABCDEFGH，可畫出二叉樹，該二叉樹是一個子結(jié)點全部在右側(cè)二叉樹，然后根據(jù)后序遍歷方法，可得出后序遍歷為HGFEDCBA。8、設(shè)某棵樹的度為3，其中度為3、1、0的結(jié)點個數(shù)分別為3、4、15。則該樹中總結(jié)點數(shù)為A、22B、30C、35D、不可能有這樣的樹標(biāo)準(zhǔn)答案：B知識點解析：本題采用畫圖法來求出結(jié)果。首先先畫出包含3個度為3的結(jié)點；然后再添加4個度為1的結(jié)點，此時最大度為0的結(jié)點數(shù)為8。根據(jù)題目中描述的度為0的結(jié)點數(shù)有15個，這時要在書中添加度為2的結(jié)點，直到度為0的結(jié)點數(shù)位15。畫圖結(jié)束后，不管是什么樣的樹，總結(jié)點數(shù)都是30。9、線性表的長度為n。在最壞情況下，比較次數(shù)為n一1的算法是A、順序查找B、有序表的插入C、尋找最大項D、同時尋找最大項與最小項標(biāo)準(zhǔn)答案：C知識點解析：尋找最大項算法是，首先取出第一個數(shù)作為最大數(shù)，然后和后面的所有項進(jìn)行比較查找。因此，比較次數(shù)為n-1。10、下列敘述中錯誤的是A、向量是線性結(jié)構(gòu)B、非空線性結(jié)構(gòu)中只有一個結(jié)點沒有前件C、非空線性結(jié)構(gòu)中只有一個結(jié)點沒有后件D、只有一個根結(jié)點和一個葉子結(jié)點的結(jié)構(gòu)必定是線性結(jié)構(gòu)標(biāo)準(zhǔn)答案：D知識點解析：線性結(jié)構(gòu)是n個數(shù)據(jù)元素的有序(次序)集合。①集合中必存在唯一的一個“第一個元素”；②集合中必存在唯一的一個“最后的元素”；③除最后元素之外，其它數(shù)據(jù)元素均有唯一的“后件”；④除第一元素之外，其它數(shù)據(jù)元素均有唯一的“前件”。相對應(yīng)于線性結(jié)構(gòu)，非線性結(jié)構(gòu)的邏輯特征是一個結(jié)點元素可能對應(yīng)多個直接前驅(qū)和多個后繼。向量符合線性結(jié)構(gòu)特點。非線性結(jié)構(gòu)也會存在只有一個根結(jié)點和葉子結(jié)點的情況。11、在希爾排序法中，每經(jīng)過一次數(shù)據(jù)交換后A、能消除多個逆序B、只能消除一個逆序C、不會產(chǎn)生新的逆序D、消除的逆序個數(shù)一定比新產(chǎn)生的逆序個數(shù)多標(biāo)準(zhǔn)答案：A知識點解析：希爾排序法(縮小增量法)屬于插入類排序，是將整個無序列分割成若干小的子序列分別進(jìn)行插入排序的方法。插入排序能夠消除多個逆序，也會產(chǎn)生新的逆序。消除的逆序與新產(chǎn)生的逆序有多有少。12、設(shè)二叉樹的后序序列與中序序列均為ABCDEFGH，則該二叉樹的前序序列為A、HGFEDCBAB、ABCDEFGHC、ABCDHGFED、DCBAHGFE標(biāo)準(zhǔn)答案：A知識點解析：后序遍歷中，最后一個字母是根結(jié)點，也就是H是根結(jié)點；在中序遍歷中，根結(jié)點前面的是左子樹、后面的是右子樹，H后面沒有，因此該樹沒有右子樹。同理，可判斷出該樹是第一個完全的左子樹。由此可畫出這個二叉樹，然后根據(jù)二叉樹可的前序序列為HGFEDCBA。13、下列敘述中正確的是A、循環(huán)隊列是隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)B、能采用順序存儲的必定是線性結(jié)構(gòu)C、所有的線性結(jié)構(gòu)都可以采用順序存儲結(jié)構(gòu)D、具有兩個以上指針的鏈表必定是非線性結(jié)構(gòu)標(biāo)準(zhǔn)答案：C知識點解析：根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間的前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。有序線性表既可以采用順序存儲結(jié)構(gòu)，又可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。所有的線性結(jié)構(gòu)都可以采用順序存儲結(jié)構(gòu)。14、下列敘述中正確的是A、算法的復(fù)雜度是指算法所處理的數(shù)據(jù)量B、算法的復(fù)雜度是指算法程序中指令的數(shù)量C、算法的復(fù)雜度是指算法控制結(jié)構(gòu)的復(fù)雜程度D、算法的復(fù)雜度包括時間復(fù)雜度與空間復(fù)雜度標(biāo)準(zhǔn)答案：D知識點解析：算法分析的目的在于選擇合適算法和改進(jìn)算法。一個算法的評價主要從時間復(fù)雜度和空間復(fù)雜度來考慮。15、設(shè)二叉樹的前序序列為ABDEGHCFIJ，中序序列為DBGEHACIFJ。則按層次輸出(從上到下，同一層從左到右)的序列為A、ABCDEFGHIJB、DGHEBIJFCAC、JIHGFEDCBAD、GHIJDEFBCA標(biāo)準(zhǔn)答案：A知識點解析：前序遍歷中，第一個字母是根結(jié)點，也就是A是根結(jié)點；在中序遍歷中，根結(jié)點前面的是左子樹、后面的是右子樹。前序中，B在A的后面，中序中在左予樹中，可知B為A的左結(jié)點。中序中D在B的前面，前序中在B的后面，可知D為B的左結(jié)點，GEH為B的右子樹。前序中順序為EGH，由此可知，E為B的右結(jié)點，G為E的左結(jié)點、H為E的右結(jié)點。右子樹中，前序中C在最前，因為右子樹根結(jié)點，也就是A的右結(jié)點，根據(jù)前序中的子樹FU和中序中的WJ子樹可知F為C的右結(jié)點，I為F的左結(jié)點、J為F的右結(jié)點。由此可畫出這個二叉樹，然后根據(jù)二叉樹，可知按層次輸出(從上到下，同一層從左到右)的序列為：ABCDEFGHIJ。16、設(shè)循環(huán)隊列的存儲空間為Q(1：50)，初始狀態(tài)為from=rear=50。經(jīng)過一系列正常的操作后，front—1=rear。為了在該隊列中尋找值最大的元素，在最壞情況下需要的比較次數(shù)為A、0B、1C、48D、49標(biāo)準(zhǔn)答案：C知識點解析：front指定隊頭位置，刪除一個元素就將from順時針移動一位；rear指尾指針，指向元素要插入的位置，插入一個元素就將rear順時針移動一位；操作后，循環(huán)隊列的隊頭指針-1等于尾指針，說明出隊一位，那么總數(shù)就是49了。在該隊列中尋找最大值元素，最多比較次數(shù)是總數(shù)-1，因此是49-1=48次。17、設(shè)順序表的長度為40，對該表進(jìn)行冒泡排序。在最壞情況下需要的比較次數(shù)為A、780B、820C、40D、41標(biāo)準(zhǔn)答案：A知識點解析：冒泡排序(BubbleSort)，是一種計算機科學(xué)領(lǐng)域的較簡單的排序算法。冒泡排序算法的運作如下：比較相鄰的元素。如果第一個比第二個大，就交換他們兩個；對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。在這一點，最后的元素應(yīng)該會是最大的數(shù)；針對所有的元素重復(fù)以上的步驟，除了最后一個；持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。冒泡排序的最壞時間復(fù)雜度為(n*(n—1))／2=780。18、設(shè)表的長度為n。在下列算法中，最壞情況下時間復(fù)雜度最高的是A、堆排序B、希爾排序C、有序鏈表查找D、循環(huán)鏈表中尋找最大項標(biāo)準(zhǔn)答案：B知識點解析：希爾排序(ShellSort)是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進(jìn)版本。排序方法最壞時間復(fù)雜度：直接插入為O(n2)、簡單選擇為O(n2)、起泡排序為O(n2)、快速排序為O(n2)、堆排序為O(nlog2n)、歸并排序為O(nlog2n)。19、設(shè)循環(huán)隊列的存儲空間為Q(1：50)，初始狀態(tài)為front=rear=50。經(jīng)過一系列正常的操作后，front=rear一1。為了在該隊列中尋找值最大的元素，在最壞情況下需要的比較次數(shù)為A、0B、1C、49D、50標(biāo)準(zhǔn)答案：A知識點解析：front指定隊頭位置，刪除一個元素就將front順時針移動一位；rear指尾指針，指向元素要插入的位置，插入一個元素就將rear順時針移動一位；操作后，循環(huán)隊列的隊頭指針等于尾指針-1，說明此時隊列已經(jīng)是空隊列，那么就不用比較了。20、設(shè)二叉樹的前序序列為ABDEGHCFIJ，中序序列為DBGEHACIFJ。則后序序列為A、DGHEBIJFCAB、JIHGFEDCBAC、GHIJDEFBCAD、ABCDEFGHIJ標(biāo)準(zhǔn)答案：A知識點解析：前序遍歷中，第一個字母是根結(jié)點，也就是A是根結(jié)點；在中序遍歷中，根結(jié)點前面的是左子樹、后面的是右子樹。前序中，B在A的后面，中序中在左子樹中，可知B為A的左結(jié)點。中序中D在B的前面，前序中在B的后面，可知D為B的左結(jié)點，GEH為B的右子樹。前序中順序為EGH，由此可知，E為B的右結(jié)點，G為E的左結(jié)點、H為E的右結(jié)點。右子樹中，前序中C在最前。因為右子樹根結(jié)點，也就是A的右結(jié)點，根據(jù)前序中的子樹FU和中序中的IFJ子樹可知F為c的右結(jié)點，I為F的左結(jié)點、J為F的右結(jié)點。由此可畫出這個二叉樹，然后根據(jù)二叉樹可的后序序列為DGHEBIffCA。21、下列結(jié)構(gòu)中為非線性結(jié)構(gòu)的是A、樹B、向量C、二維表D、矩陣標(biāo)準(zhǔn)答案：A知識點解析：線性結(jié)構(gòu)是一個有序數(shù)據(jù)元素的集合。常用的線性結(jié)構(gòu)有：線性表，棧，隊列，雙隊列，數(shù)組，串。常見的非線性結(jié)構(gòu)有：二維數(shù)組，多維數(shù)組，廣義表，樹(二叉樹等)，圖。22、設(shè)表的長度為n。在下列結(jié)構(gòu)所對應(yīng)的算法中，最壞情況下時間復(fù)雜度最低的是A、堆排序B、有序鏈表查找C、希爾排序D、循環(huán)鏈表中尋找最大項標(biāo)準(zhǔn)答案：D知識點解析：在循環(huán)鏈表中尋找最大項算法是，首先取出第一個數(shù)作為最大數(shù)，然后和后面的所有項進(jìn)行比較查找。囚此，比較次數(shù)為n-1。23、設(shè)循環(huán)隊列的存儲空間為Q(1：m)，初始狀態(tài)為front=rear=m。經(jīng)過一系列正常的操作后，front=1，rear=m。為了在該隊列中尋找值最大的元素，在最壞情況下需要的比較次數(shù)為A、mB、m-1C、m-2D、1標(biāo)準(zhǔn)答案：C知識點解析：經(jīng)過一系列正常的操作后，front=1，rear=m，那么最壞情況下需要的比較次數(shù)為rear-front-1=m-1-1=m-2。24、設(shè)二叉樹的后序序列為DGHEBIJFCA，中序序列為DBGEHACIFJ。則前序序列為A、ABDEGHCFIJB、JIHGFEDCBAC、GHIJDEFBCAD、ABCDEFGHIJ標(biāo)準(zhǔn)答案：A知識點解析：后序遍歷中，最后一個字母是根結(jié)點，也就是A是根結(jié)點：在中序遍歷中，根結(jié)點前面的是左子樹、后面的是右子樹。后序中C在A前面、中序中C在A的后面，說明C是A的右結(jié)點；后序中F在C的前面、中序中在C后面，且后序和中序中，I均在F前面由此可確定，I為F的左結(jié)點，F(xiàn)為C的右結(jié)點。同C理J為F的右結(jié)點。后續(xù)中B為左子樹的根結(jié)點，因此B為A的左結(jié)點，以此劃分，在中序中B前面的D為左結(jié)點，后面的GEH為右子樹，后序中，E在最后，應(yīng)為剩下3個結(jié)點的根結(jié)點，也就是B的右子樹，再根據(jù)中序中的順序，可得出G為E的左結(jié)點．H為E的右結(jié)點。由此可畫出這個二叉樹，然后根據(jù)二叉樹可的前序序列為ABDEGHCFIJ。國家二級C++機試（數(shù)據(jù)結(jié)構(gòu)與算法）模擬試卷第5套一、選擇題(本題共19題，每題1.0分，共19分。)1、算法的空間復(fù)雜度是指()。A、算法在執(zhí)行過程中所需要的計算機存儲空間B、算法所處理的數(shù)據(jù)量C、算法程序中的語句或指令條數(shù)D、算法在執(zhí)行過程中所需要的臨時工作單元數(shù)標(biāo)準(zhǔn)答案：A知識點解析：算法的空間復(fù)雜度是指執(zhí)行這個算法所需耍的內(nèi)存空間。這個內(nèi)存空間包括算法程序所占的空問，輸入的初始數(shù)據(jù)所占的存儲空間以及算法執(zhí)行過程中所需要的額外空間。2、下列敘述中正確的是()。A、一個算法的空間復(fù)雜度大，則其時間復(fù)雜度也必定大B、一個算法的空間復(fù)雜度大，則其時間復(fù)雜度必定小C、一個算法的時間復(fù)雜度大，則其空間復(fù)雜度必定小D、算法的時間復(fù)雜度與空間復(fù)雜度沒有直接關(guān)系標(biāo)準(zhǔn)答案：D知識點解析：算法的復(fù)雜度主要包括時間復(fù)雜度和空間復(fù)雜度。算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量，算法的工作量用算法所執(zhí)行的基本運算次數(shù)來度量，而算法所執(zhí)行的基本運算次數(shù)是問題規(guī)模的函數(shù)，即算法的工作量=f(n)，其中n是問題的規(guī)模：算法的空間復(fù)雜度，一般是指執(zhí)行這個算法所需要的內(nèi)存空間。一個算法所占用的存儲空間包括算法程序所占用的空間、輸入的初始數(shù)據(jù)所占的存儲空間以及算法執(zhí)行過程中所需要的額外空間。根據(jù)各自的定義可知，算法的時間復(fù)雜度與空間復(fù)雜度并不相關(guān)。3、下列描述中正確的是()。A、線性鏈表是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)B、棧與隊列是非線性結(jié)構(gòu)C、雙向鏈表是非線性結(jié)構(gòu)D、只有根結(jié)點的二叉樹是線性結(jié)構(gòu)標(biāo)準(zhǔn)答案：A知識點解析：線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表。線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)的基本單位稱為存儲結(jié)點，每個存儲結(jié)點包括數(shù)據(jù)域和指針域兩個組成部分。各數(shù)據(jù)元素之間的前后件關(guān)系是由各結(jié)點的指針域來指示的，指向線性表中第一結(jié)點的指針HEAD稱為頭指針，當(dāng)HEAD=NULL時稱為空表。棧、隊列和雙向鏈表是線性結(jié)構(gòu)，樹是一種簡單的非線性結(jié)構(gòu)。在樹這種數(shù)據(jù)結(jié)構(gòu)中，所有數(shù)據(jù)元素的關(guā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)。4、支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是()。A、棧B、樹C、隊列D、二叉樹標(biāo)準(zhǔn)答案：A知識點解析：棧是一種限定在一端進(jìn)行插入與刪除的線性表。在主函數(shù)調(diào)用予函數(shù)時，要首先保存主函數(shù)當(dāng)前的狀態(tài)，然后轉(zhuǎn)去執(zhí)行子函數(shù)，把子函數(shù)的運行結(jié)果返回到主函數(shù)調(diào)用子函數(shù)時的位置，主函數(shù)再接著往下執(zhí)行，這種過程符合棧的特點。所以一般采用棧式存儲方式。5、下列關(guān)于棧的敘述中，正確的是()。A、棧底元素一定是最后入棧的元素B、棧頂元素一定是最先入棧的元素C、棧操作遵循先進(jìn)后出的原則D、以上三種說法都不對標(biāo)準(zhǔn)答案：C知識點解析：棧是限定只能在表的一端進(jìn)行插入和刪除操作的線性表，必須按“后進(jìn)先出”的規(guī)則操作元素。6、下列對隊列的描述中正確的是()。A、隊列屬于非線性表B、隊列按“先進(jìn)后出”原則組織數(shù)據(jù)C、隊列在隊尾刪除數(shù)據(jù)D、隊列按“先進(jìn)先出”原則組織數(shù)據(jù)標(biāo)準(zhǔn)答案：D知識點解析：隊列(queue)是指允許在一端進(jìn)行插入、而在另一端進(jìn)行刪除的線性表。允許插入的一端稱為隊尾；允許刪除的一端稱為隊頭。在隊列這種數(shù)據(jù)結(jié)構(gòu)中，最先插入的元素將最先能夠被刪除；反之，最后插入的元素將最后才能被刪除。因此。隊列又稱“先進(jìn)先出”或“后進(jìn)后出”的線性表。7、下列關(guān)于棧的描述中正確的是()。A、在棧中只能插入元素而不能刪除元素B、在棧中只能刪除元素而不能插入元素C、棧是特殊的線性表，只能在一端插入或刪除元素D、棧是特殊的線性表，只能在一端插入元素，而在另一端刪除元素標(biāo)準(zhǔn)答案：C知識點解析：棧是限定在一端進(jìn)行插入與刪除的線性表，在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。8、下列敘述中正確的是()。A、循環(huán)隊列是隊列的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)B、循環(huán)隊列是隊列的一種順序存儲結(jié)構(gòu)C、循環(huán)隊列是非線性結(jié)構(gòu)D、循環(huán)隊列是一種邏輯結(jié)構(gòu)標(biāo)準(zhǔn)答案：B知識點解析：本題主要考查循環(huán)隊列的概念，循環(huán)隊列作為隊列的一種也應(yīng)該是線性結(jié)構(gòu)。隊列是一種邏輯結(jié)構(gòu)，而循環(huán)隊列是一種順序存儲結(jié)構(gòu)的隊列。9、下列敘述中正確的是()。A、棧是一種先進(jìn)先出的線性表B、隊列是一種后進(jìn)先出的線性表C、棧與隊列都是非線性結(jié)構(gòu)D、棧與隊列都是線性結(jié)構(gòu)標(biāo)準(zhǔn)答案：D知識點解析：棧是先進(jìn)后出，隊列是先進(jìn)先出。棧和隊列都是一種線性表，屬于線性結(jié)構(gòu)。10、下列敘述中正確的是()。A、循環(huán)隊列中的元素個數(shù)隨隊頭指針與隊尾指針的變化而動態(tài)變化B、循環(huán)隊列中的元素個數(shù)隨隊頭指針的變化而動態(tài)變化C、循環(huán)隊列中的元素個數(shù)隨隊尾指針的變化而動態(tài)變化D、循環(huán)隊列中的元素個數(shù)不會變化標(biāo)準(zhǔn)答案：A知識點解析：所謂循環(huán)結(jié)構(gòu)就是將隊列存儲空間的最后一個位置繞到第一個位置上，形成邏輯上的環(huán)狀空間，循環(huán)使用。在循環(huán)隊列中，用隊尾指針rear指向隊列中的隊尾元素，用隊頭指針front指向隊頭元素的前一個位置，因此，隊列中的元素數(shù)等于從隊頭指針front指向的后一個位置與隊尾指針rear指向位置之間的元素數(shù)量。11、下列敘述中正確的是()。A、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)與順序存儲結(jié)構(gòu)所需要的存儲空間是相同的B、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)所需要的存儲空間一般要多于順序存儲結(jié)構(gòu)C、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)所需要的存儲空間一般要少于順序存儲結(jié)構(gòu)D、以上都不正確標(biāo)準(zhǔn)答案：B知識點解析：線性表的存儲分為順序存儲和鏈?zhǔn)酱鎯?。在順序存儲中，所有元素所占的存儲空間是連續(xù)的。而在鏈?zhǔn)酱鎯Φ姆绞街校瑢⒋鎯臻g的每一個存儲結(jié)點分為兩部分，一部分用于存儲數(shù)據(jù)元素的值，稱為數(shù)據(jù)域：另一部分用于存儲下一個元素的存儲序號，稱為指針域。所以線性表的鏈?zhǔn)酱鎯Ψ绞奖软樞虼鎯Ψ绞降拇鎯臻g要大一些。12、某系統(tǒng)總體結(jié)構(gòu)圖如下圖所示：該系統(tǒng)總體結(jié)構(gòu)圖的深度是()。A、7B、6C、3D、2標(biāo)準(zhǔn)答案：C知識點解析：這個系統(tǒng)總體結(jié)構(gòu)圖是一棵樹結(jié)構(gòu)，在樹結(jié)構(gòu)中，根結(jié)點在第1層，同一層上所有子結(jié)點都在下一層，由系統(tǒng)總體結(jié)構(gòu)圖可知，這棵樹共3層。在樹結(jié)構(gòu)中，樹的最大層次稱為樹的深度。所以這棵樹的深度為3。13、某二叉樹有5個度為2的結(jié)點，則該二叉樹中的葉子結(jié)點數(shù)是()。A、10B、8C、6D、4標(biāo)準(zhǔn)答案：C知識點解析：根據(jù)二叉樹的性質(zhì)，在任意二叉樹中，度為0的結(jié)點(即葉子結(jié)點)總是比度為2的結(jié)點多一個。14、一棵二叉樹中共有70個葉子結(jié)點與80個度為1的結(jié)點，則該二叉樹中的總結(jié)點數(shù)為()。A、219B、221C、229D、231標(biāo)準(zhǔn)答案：A知識點解析：在二叉樹中，葉子結(jié)點個數(shù)為n0，則度為2的結(jié)點數(shù)n2=n0－1。本題中葉子結(jié)點的個數(shù)為70，所以度為2的結(jié)點個數(shù)為69，因而總結(jié)點數(shù)=葉子結(jié)點數(shù)+度為1的結(jié)點數(shù)+度為2的結(jié)點數(shù)=70+80+69=219。15、設(shè)樹T的深度為4，其中度為1,2,3,4的結(jié)點個數(shù)分別為4,2,1,1。則T中的葉子結(jié)點數(shù)為()。A、8B、7C、6D、5標(biāo)準(zhǔn)答案：B知識點解析：深度為m二叉樹其總結(jié)點數(shù)為2m－1=24－1=15?？偨Y(jié)點數(shù)減去度為1,2,3,4的結(jié)點個數(shù)就是葉子結(jié)點數(shù)。15－4－2－1－1=7。16、對下列二叉樹進(jìn)行前序遍歷的結(jié)果是()。A、DYBEAFCZXB、YDEBFZXCAC、ABDYECFXZD、ABCDEFXYZ標(biāo)準(zhǔn)答案：C知識點解析：二叉樹前序遍歷的簡單描述：若二叉樹為空，則結(jié)束返回；否則：①訪問根結(jié)點；②前序遍歷左子樹；③前序遍歷右子樹。可見，前序遍歷二叉樹的過程是一個遞歸的過程。根據(jù)題目中給出的二叉樹的結(jié)構(gòu)可知前序遍歷的結(jié)果是ABDYECFXZ。17、在長度為64的有序線性表中進(jìn)行順序查找，最壞情況下需要比較的次數(shù)為()。A、63B、64C、6D、7標(biāo)準(zhǔn)答案：B知識點解析：順序查找又稱順序搜索。順序查找一般是指在線性表中查找指定的元素，其基本方法是：從線性表的第一元素開始，依次將線性表中的元素與被查找的元素進(jìn)行比較，若相等則表示找到(即查找成功)，若線性表中所有元素都與被查元素進(jìn)行了比較但都不相等，則表示線性表中沒有要找的元素(即查找失敗)。如果線性表中的第一個元素就是要查找的元素，則只需要做一次比較就查找成功；但如果要查找的元素是線性表中的最后一個元素，或者要查找元素不在線性表中，則需要與線性表中所有元素進(jìn)行比較，這是順序查找的最壞情況，比較次數(shù)為線性表的長度。18、對于長度為n的線性表，在最壞情況下，下列各排序法所對應(yīng)的比較次數(shù)中正確的是()。A、冒泡排序為n／2B、冒泡排序為nC、快速排序為nD、快速排序為n(n－1)／2標(biāo)準(zhǔn)答案：D知識點解析：假設(shè)線性表的長度為n，則在最壞情況下，冒泡排序需要經(jīng)過n／2遍的從前往后的掃描和n／2遍的從后往前的掃描，需要的比較次數(shù)為n(n－1)／2?？焖倥判蚍ㄒ彩且环N互換類的排序方法，但由于它比冒泡排序法的速度快，因此，稱為快速排序法。19、下列排序方法中，最壞情況下比較次數(shù)最少的是()。A、冒泡排序B、簡單選擇排序C、直接插入排序D、堆排序標(biāo)準(zhǔn)答案：D知識點解析：冒泡排序、簡單選擇排序和直接插入排序法在最壞的情況下比較次數(shù)為；n(n－1)／2。而堆排序法在最壞的情況下需要比較的次數(shù)為O(nlog2n)。其中堆排序的比較次數(shù)最少。國家二級C++機試（數(shù)據(jù)結(jié)構(gòu)與算法）模擬試卷第6套一、選擇題(本題共28題，每題1.0分，共28分。)1、下列結(jié)構(gòu)中屬于線性結(jié)構(gòu)鏈?zhǔn)酱鎯Φ氖茿、雙向鏈表B、循環(huán)隊列C、二叉鏈表D、二維數(shù)組標(biāo)準(zhǔn)答案：A知識點解析：數(shù)據(jù)元素之間的關(guān)系有兩種不同的表示方法：順序映象和非順序映象，并由此得到兩種不同的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)溝。數(shù)據(jù)韻存儲結(jié)構(gòu)是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示。雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結(jié)點中都有兩個指針，分別指向直接后繼和直接前驅(qū)，它的存儲方式是線性結(jié)構(gòu)鏈?zhǔn)?。循環(huán)隊列、二叉鏈表和二維數(shù)組都是順序存儲結(jié)構(gòu)。2、下列敘述中錯誤的是A、循環(huán)鏈表中有一個表頭結(jié)點B、循環(huán)鏈表的存儲空間是連續(xù)的C、循環(huán)鏈表實現(xiàn)了空表與非空表運算的統(tǒng)一D、循環(huán)鏈表的表頭指針與循環(huán)鏈表中最后一個結(jié)點的指針均指向表頭結(jié)點標(biāo)準(zhǔn)答案：B知識點解析：循環(huán)鏈表是另一種形式的鏈?zhǔn)酱尜A結(jié)構(gòu)。它的特點是表中最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表形成一個環(huán)。循環(huán)鏈表的結(jié)點是指針指向，他不一定要是連續(xù)的存儲空間，也可以是斷開的空間。3、度為3的一棵樹共有30個結(jié)點，其中度為3、1的結(jié)點個數(shù)分別為3、4。則該樹中的葉子結(jié)點數(shù)為A、14B、15C、16D、不可能有這樣的樹標(biāo)準(zhǔn)答案：B知識點解析：根據(jù)題目可知本樹中還有度為2的結(jié)點。樹的總結(jié)點=(度1*個數(shù)+度2*個數(shù)…)+1，這里我們設(shè)度為2的結(jié)點數(shù)為x，那么30=3*3+2*x+1*4+1=2*x+14，由此可計算出x=8。樹的葉子結(jié)點數(shù)等于總結(jié)點減去所有度不為0的結(jié)點，也就是30-3-8-4=15。4、在長度為97的順序有序表中作二分查找，最多需要的比較次數(shù)為A、7B、96C、48D、6標(biāo)準(zhǔn)答案：A知識點解析：二分查找又稱折半查找，優(yōu)點是比較次數(shù)少，查找速度快，平均性能好；其缺點是要求待查表為有序表，且插入刪除困難。最多比較次數(shù)的計算方式：k=log2n。其中n代表長度，k為比較次數(shù)。本題中可以計算出k=7。5、下列結(jié)構(gòu)中屬于非線性結(jié)構(gòu)的是A、二叉鏈表B、二維數(shù)組C、循環(huán)隊列D、雙向鏈表標(biāo)準(zhǔn)答案：B知識點解析：線性結(jié)構(gòu)是一個有序數(shù)據(jù)元素的集合。常用的線性結(jié)構(gòu)有：線性表，棧，隊列，雙隊列，數(shù)組，串；常見的非線性結(jié)構(gòu)有：二維數(shù)組，多維數(shù)組，廣義表，樹(二叉樹等)，圖。循環(huán)隊列、雙向鏈表和二叉鏈表都是線性結(jié)構(gòu)，而二維數(shù)組是非線性結(jié)構(gòu)。6、從表中任何一個結(jié)點位置出發(fā)就可以不重復(fù)地訪問到表中其他所有結(jié)點的鏈表是A、循環(huán)鏈表B、雙向鏈表C、單向鏈表D、二叉鏈表標(biāo)準(zhǔn)答案：A知識點解析：循環(huán)鏈表是另一種形式的鏈?zhǔn)酱尜A結(jié)構(gòu)。它的特點是表中最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表形成一個環(huán)，循環(huán)一圈就訪問到了表中其他所有結(jié)點而不重復(fù)。7、設(shè)二叉樹的前序序列與中序序列均為ABCDEFGH，則該二叉樹的后序序列為A、HGFEDCBAB、ABCDEFGHC、ABCDHGFED、DCBAHGFE標(biāo)準(zhǔn)答案：A知識點解析：前序遍歷(DLR)是二叉樹遍歷的一種，也叫做先根遍歷、先序遍歷、前序周游，可記做根左右；中序遍歷(LDR)是二叉樹遍歷的一種，也叫做中根遍歷、中序周游，可記做左根右；后序遍歷(LRD)是二叉樹遍歷的一種，也叫做后根遍歷、后序周游，可記做左右根。根據(jù)題中前序和中序序列均為ABCDEFGH，可畫出二叉樹，該二叉樹是一個子結(jié)點全部在右側(cè)二叉樹，然后根據(jù)后序遍歷方法，可得出后序遍歷為HGFEDCBA。8、設(shè)某棵樹的度為3，其中度為3、1、0的結(jié)點個數(shù)分別為3、4、15。則該樹中總結(jié)點數(shù)為A、22B、30C、35D、不可能有這樣的樹標(biāo)準(zhǔn)答案：B知識點解析：本題采用畫圖法來求出結(jié)果。首先先畫出包含3個度為3的結(jié)點；然后再添加4個度為1的結(jié)點，此時最大度為0的結(jié)點數(shù)為8。根據(jù)題目中描述的度為0的結(jié)點數(shù)有15個，這時要在書中添加度為2的結(jié)點，直到度為0的結(jié)點數(shù)位15。畫圖結(jié)束后，不管是什么樣的樹，總結(jié)點數(shù)都是30。9、下列敘述中正確的是A、矩陣是非線性結(jié)構(gòu)B、數(shù)組是長度固定的線性表C、對線性表只能作插入與刪除運算D、線性表中各元素的數(shù)據(jù)類型可以不同標(biāo)準(zhǔn)答案：B知識點解析：所謂數(shù)組，就是相同數(shù)據(jù)類型的元素按一定順序排列的集合，就是把有限個類型相同的變量用一個名字命名，然后用編號區(qū)分他們的變量的集合，這個名字稱為數(shù)組名，編號稱為下標(biāo)。10、在快速排序法中，每經(jīng)過一次數(shù)據(jù)交換(或移動)后A、能消除多個逆序B、只能消除一個逆序C、不會產(chǎn)生新的逆序D、消除的逆序個數(shù)一定比新產(chǎn)生的逆序個數(shù)多標(biāo)準(zhǔn)答案：A知識點解析：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個排序過程可以遞歸進(jìn)行，以此達(dá)到整個數(shù)據(jù)變成有序序列。11、線性表的長度為n。在最壞情況下，比較次數(shù)為n-1的算法是A、順序查找B、有序表的插入C、尋找最大項D、同時尋找最大項與最小項標(biāo)準(zhǔn)答案：C知識點解析：尋找最大項算法是，首先取出第一個數(shù)作為最大數(shù)，然后和后面的所有項進(jìn)行比較查找。因此，比較次數(shù)為n-1。12、設(shè)某棵樹的度為3，其中度為2、1、0的結(jié)點個數(shù)分別為3、4、15。則該樹中總結(jié)點數(shù)為A、22B、30C、35D、不可能有這樣的樹標(biāo)準(zhǔn)答案：D知識點解析：本題采用畫圖法來求出結(jié)果。首先先畫出包含3個度為2的結(jié)點；然后再添加4個度為1的結(jié)點。根據(jù)題目中描述的度為0的結(jié)點數(shù)有15個，這時要在書中添加度為3的結(jié)點，不管怎么添加都不能添加出15個度為0的結(jié)點，因此不可能有這樣的樹。13、下列敘述中錯誤的是A、向量是線性結(jié)構(gòu)B、非空線性結(jié)構(gòu)中只有一個結(jié)點沒有前件C、非空線性結(jié)構(gòu)中只有一個結(jié)點沒有后件D、只有一個根結(jié)點和一個葉子結(jié)點的結(jié)構(gòu)必定是線性結(jié)構(gòu)標(biāo)準(zhǔn)答案：D知識點解析：線性結(jié)構(gòu)是n個數(shù)據(jù)元素的有序(次序)集合。①集合中必存在唯一的一個“第一個元素”；②集合中必存在唯一的一個“最后的元素”；③除最后元素之外，其它數(shù)據(jù)元素均有唯一的“后件”；④除第一元素之外，其它數(shù)據(jù)元素均有唯一的“前件”。相對應(yīng)于線性結(jié)構(gòu)，非線性結(jié)構(gòu)的邏輯特征是一個結(jié)點元素可能對應(yīng)多個直接前驅(qū)和多個后繼。向量符合線性結(jié)構(gòu)特點。非線性結(jié)構(gòu)也會存在只有一個根結(jié)點和葉子結(jié)點的情況。14、在希爾排序法中，每經(jīng)過一次數(shù)據(jù)交換后A、能消除多個逆序B、只能消除一個逆序C、不會產(chǎn)生新的逆序D、消除的逆序個數(shù)一定比新產(chǎn)生的逆序個數(shù)多標(biāo)準(zhǔn)答案：A知識點解析：希爾排序法(縮小增量法)屬于插入類排序，是將整個無序列分割成若干小的子序列分別進(jìn)行插入排序的方法。插入排序能夠消除多個逆序，也會產(chǎn)生新的逆序。消除的逆序與新產(chǎn)生的逆序有多有少。15、設(shè)二叉樹的后序序列與中序序列均為ABCDEFGH，則該二叉樹的前序序列為A、HGFEDCBAB、ABCDEFGHC、ABCDHGFED、DCBAHGFE標(biāo)準(zhǔn)答案：A知識點解析：后序遍歷中，最后一個字母是根結(jié)點，也就是H是根結(jié)點；在中序遍歷中，根結(jié)點前面的是定子樹、后麗的是右予樹，H后面沒有，因此該樹沒：有右子樹。同理，可判斷出該樹是第一個完全的左子樹。由此可畫出這個二叉樹，然后根據(jù)二叉樹可的前序序列為HGFEDCBA。16、下列敘述中正確的是A、循環(huán)隊列是隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)B、能采用順序存儲的必定是線性結(jié)構(gòu)C、所有的線性結(jié)構(gòu)都可以采用順序存儲結(jié)構(gòu)D、具有兩個以上指針的鏈表必定是非線性結(jié)構(gòu)標(biāo)準(zhǔn)答案：C知識點解析：根據(jù)數(shù)據(jù)結(jié)溝中各數(shù)據(jù)元素之間的前后件關(guān)系的復(fù)雜程度，一收將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。有序線性表既可以采用順序存儲結(jié)構(gòu)，又可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。所有的線性結(jié)構(gòu)都可以采用順序存儲結(jié)構(gòu)。17、下列敘述中正確的是A、算法的復(fù)雜度是指算法所處理的數(shù)據(jù)量B、算法的復(fù)雜度是指算法程序中指令的數(shù)量C、算法的復(fù)雜度是指算法控制結(jié)構(gòu)的復(fù)雜程度D、算法的復(fù)雜度包括時間復(fù)雜度與空間復(fù)雜度標(biāo)準(zhǔn)答案：D知識點解析：算法分析的目的在于選擇合適算法和改進(jìn)算法。一個算法的評價主要從時間復(fù)雜度和空間復(fù)雜度來考慮。18、設(shè)二叉樹的前序序列為ABDEGHCFIJ，中序序列為DBGEHACIFJ。則按層次輸出(從上到下，同一層從左到右)的序列為A、ABCDEFGHIJB、DGHEBIJFCAC、JIHGFEDCBAD、GHIJDEFBCA標(biāo)準(zhǔn)答案：A知識點解析：前序遍歷中，第一個字母是根結(jié)點，也就是A是根結(jié)點；在中序遍歷中，根結(jié)點前面的是左子樹、后面的是右子樹。前序中，B在A的后面，中序中在左子樹中，可知B為A的左結(jié)點。中序中D在B的前面，前序中在B的后面，可知D為B的左結(jié)點，GEH為B的右子樹。前序中順序為EGH，由此可知，E為B的右結(jié)點，G為E的左結(jié)點、H為E的右結(jié)點。右子樹中，前序中C在最前，因為右子樹根結(jié)點，也就是A的右結(jié)點，根據(jù)前序中的子樹FIJ和中序中的IFJ子樹可知F為C的右結(jié)點，I為F的左結(jié)點、J為F的右結(jié)點。由此可畫出這個二叉樹，然后根據(jù)二叉樹，可知按層次輸出(從上到下，同一層從左到右)的序列為：ABCDEFGHIJ。19、設(shè)循環(huán)隊列的存儲空間為Q(1：50)，初始狀態(tài)為front=rear=50。經(jīng)過一系列正常的操作后，front-1=rear。為了在該隊列中尋找值最大的元素，在最壞情況下需要的比較次數(shù)為A、0B、1C、48D、49標(biāo)準(zhǔn)答案：C知識點解析：front指定隊頭位置，刪除一個元素就將front順時針移動一位：rear指尾指針，指向元素要插入的位置，插入一個元素就將rear順時針移動一位；操作后，循環(huán)隊列的隊頭指針-1等于尾指針，說明出隊一位，那么總數(shù)就是49了。在該隊列中尋找最大值元素，最多比較次數(shù)是總數(shù)-1，因此是49-1=48次。20、設(shè)順序表的長度為40，對該表進(jìn)行冒泡排序。在最壞情況下需要的比較次數(shù)為A、780B、820C、40D、41標(biāo)準(zhǔn)答案：A知識點解析：冒泡排序(BubbleSort)，是一種計算機科學(xué)領(lǐng)域的較簡單的排序算法。冒泡排序算法的運作如下：比較相鄰的元素。如果第一個比第二個大，就交換他們兩個；對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。在這一點，最后的元素應(yīng)該會是最大的數(shù)：針對所有的元素重復(fù)以上的步驟，除了最后一個；持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。冒泡排序的最壞時問復(fù)雜度為(n*(n-1))／2=780。21、設(shè)表的長度為n。在下列算法中，最壞情況下時間復(fù)雜度最高的是A、堆排序B、希爾排序C、有序鏈表查找D、循環(huán)鏈表中尋找最大項標(biāo)準(zhǔn)答案：B知識點解析：希爾排序(ShellSort)是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進(jìn)版本。排序方法最壞時間復(fù)雜度：直接插入為O(n2)、簡單選擇為O(n2)、起泡排序為O(n2)、快速排序為O(n2)、堆排序為O(nlog2n)、歸并排序為O(nlog2n)。22、設(shè)循環(huán)隊列的存儲空間為Q(1：50)，初始狀態(tài)為front=rear=50。經(jīng)過一系列正常的操作后，front=rear-1。為了在該隊列中尋找值最大的元素，在最壞情況下需要的比較次數(shù)為A、0B、1C、49D、50標(biāo)準(zhǔn)答案：A知識點解析：front指定隊頭位置，刪除一個元素就將front順時針移動一位；rear指尾指針，指向元素要插入的位置，插入一個元素就將rear順時針移動一位；操作后，循環(huán)隊列的隊頭指針等于尾指針-1，說明此時隊列已經(jīng)是空隊列，那么就不用比較了。23、設(shè)二叉樹的前序序列為ABDEGHCFIJ，中序序列為DBGEHACIFJ。則后序序列為A、DGHEBIJFCAB、JIHGFEDCBAC、GHIJDEFBCAD、ABCDEFGHIJ標(biāo)準(zhǔn)答案：A知識點解析：前序遍歷中，第一個字母是根結(jié)點，也就是A是根結(jié)點；在中序遍歷中，根結(jié)點前而的是左子樹、后面的是右子樹。前序中，B在A的后面，中序中在左子樹中，可知B為A的左結(jié)點。中序中D在B的前面，前序中在B的后面，可知D為B的左結(jié)點，GEH為B的右子樹。前序中順序為EGH，由此可知，E為B的右結(jié)點，G為E的左紿點、H為E的右結(jié)點。右子樹中，前序中C在最前，因為右子樹根結(jié)點，也就足A的右結(jié)點，根據(jù)前序中的子樹FIJ和中序中的lFJ子樹可知F為C的右結(jié)點，I為F的左結(jié)點、J為F的右結(jié)點。由此可畫出這個二叉樹，然后根據(jù)二叉樹可的后序序列為DGHEBIJFCA。24、設(shè)順序表的長度為16，對該表進(jìn)行簡單插入排序。在最壞情況下需要的比較次數(shù)為A、15B、30C、60D、120標(biāo)準(zhǔn)答案：D知識點解析：插入排序的基本思想是：每步將一個待排序的紀(jì)錄，按其關(guān)鍵碼值的大小插入前面已經(jīng)排序的文件中適當(dāng)位置上