國家二級MSOffice高級應(yīng)用機(jī)試（數(shù)據(jù)結(jié)構(gòu)與算法）模擬試卷2（共103題）

國家二級MSOffice高級應(yīng)用機(jī)試（數(shù)據(jù)結(jié)構(gòu)與算法）模擬試卷2（共4套）（共103題）國家二級MSOffice高級應(yīng)用機(jī)試（數(shù)據(jù)結(jié)構(gòu)與算法）模擬試卷第1套一、選擇題(本題共24題，每題1.0分，共24分。)1、下列敘述中正確的是()。A、算法的復(fù)雜度包括時間復(fù)雜度與空間復(fù)雜度B、算法的復(fù)雜度是指算法控制結(jié)構(gòu)的復(fù)雜程度C、算法的復(fù)雜度是指算法程序中指令的數(shù)量D、算法的復(fù)雜度是指算法所處理的數(shù)據(jù)量標(biāo)準(zhǔn)答案：A知識點解析：算法復(fù)雜度是指算法在編寫成可執(zhí)行程序后，運(yùn)行時所需要的資源，資源包括時間資源和內(nèi)存資源。算法的復(fù)雜度包括時間復(fù)雜度與空間復(fù)雜度。算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量；算法的空間復(fù)雜度是指算法在執(zhí)行過程中所需要的內(nèi)存空間。2、下列敘述中正確的是()。A、解決同一個問題的不同算法的時間復(fù)雜度一般是不同的B、解決同一個問題的不同算法的時間復(fù)雜度必定是相同的C、對同一批數(shù)據(jù)作同一種處理，如果數(shù)據(jù)存儲結(jié)構(gòu)不同，不同算法的時間復(fù)雜度肯定相同D、對同一批數(shù)據(jù)作不同的處理，如果數(shù)據(jù)存儲結(jié)構(gòu)相同，不同算法的時間復(fù)雜度肯定相同標(biāo)準(zhǔn)答案：A知識點解析：解決同一個問題的不同算法的時間復(fù)雜度，可能相同也可能不相同。算法的時間復(fù)雜度與數(shù)據(jù)存儲結(jié)構(gòu)無關(guān)，對同一批數(shù)據(jù)作同一種處理或者不同處理，數(shù)據(jù)存儲結(jié)構(gòu)相同或者不同，算法的時間復(fù)雜度都可能相同或者不同。3、下列敘述中錯誤的是()。A、向量是線性結(jié)構(gòu)B、非空線性結(jié)構(gòu)中只有一個節(jié)點沒有前件C、非空線性結(jié)構(gòu)中只有一個節(jié)點沒有后件D、具有兩個以上指針域的鏈?zhǔn)浇Y(jié)構(gòu)一定屬于非線性結(jié)構(gòu)標(biāo)準(zhǔn)答案：D知識點解析：雙向鏈表每個節(jié)點有兩個指針，一個為左指針，用于指向其前件節(jié)點；一個為右指針，用于指向其后件節(jié)點，再加上頭指針，具有兩個以上的指針，但雙向鏈表屬于線性結(jié)構(gòu)。非空線性結(jié)構(gòu)中第一個節(jié)點沒有前件，最后一個節(jié)點無后件，其余節(jié)點最多有一個前件，也最多有一個后件。向量也滿足這個條件，屬于線性結(jié)構(gòu)。4、在線性表的順序存儲結(jié)構(gòu)中，其存儲空間連續(xù)，各個元素所占的字節(jié)數(shù)()。A、不同，但元素的存儲順序與邏輯順序一致B、不同，且其元素的存儲順序可以與邏輯順序不一致C、相同，元素的存儲順序與邏輯順序一致D、相同，但其元素的存儲順序可以與邏輯順序不一致標(biāo)準(zhǔn)答案：C知識點解析：在線性表的順序存儲結(jié)構(gòu)中，其存儲空間連續(xù)，各個元素所占的字節(jié)數(shù)相同，在存儲空間中是按邏輯順序依次存放的。5、設(shè)棧的順序存儲空間為S(1：m)，初始狀態(tài)為top＝m＋1，則棧中的數(shù)據(jù)元素個數(shù)為()。A、top－m＋1B、m－top＋1C、m－topD、top－m標(biāo)準(zhǔn)答案：B知識點解析：棧的初始狀態(tài)top＝m＋1，說明棧空時top＝m＋1(m在棧底，1是開口向上的)，入棧時棧頂指針是減操作(top＝top－1)，退棧時棧頂指針是加操作(top＝top＋1)。本題可以假設(shè)棧中有x個元素，當(dāng)x＝0時，也就是棧中沒有元素，則top＝m＋1；當(dāng)x＝m時，也就是棧滿，則top＝1，由此可以得出top＝m＋1－x，繼而得出x＝m－top＋1。6、設(shè)棧的存儲空間為S(1：50)，初始狀態(tài)為top＝51?，F(xiàn)經(jīng)過一系列正常的入棧與退棧操作后，top＝20，則棧中的元素個數(shù)為()。A、31B、30C、21D、20標(biāo)準(zhǔn)答案：A知識點解析：棧的初始狀態(tài)top＝51，故本棧是51在棧底，入棧時棧頂指針是減操作(top＝top－1)，退棧時棧頂指針是加操作(top＝top＋1)。當(dāng)top＝20時，元素存儲在(20：50)空間中，因此共有50－20＋1＝31個元素。7、下列敘述中正確的是()。A、循環(huán)隊列是順序存儲結(jié)構(gòu)B、循環(huán)隊列是鏈?zhǔn)酱鎯Y(jié)構(gòu)C、循環(huán)隊列空的條件是隊頭指針與隊尾指針相同D、循環(huán)隊列的插入運(yùn)算不會發(fā)生溢出現(xiàn)象標(biāo)準(zhǔn)答案：A知識點解析：循環(huán)隊列是隊列的一種順序存儲結(jié)構(gòu)。在循環(huán)隊列中，在隊列滿和隊列為空時，隊頭指針與隊尾指針均相同；當(dāng)需要插入的數(shù)據(jù)大于循環(huán)隊列的存儲長度，入隊運(yùn)算會覆蓋前面的數(shù)據(jù)，發(fā)生溢出現(xiàn)象。8、設(shè)循環(huán)隊列的存儲空間為Q(1：50)，初始狀態(tài)為front＝rear＝50。經(jīng)過一系列正常的操作后，front－1＝rear。為了在該隊列中尋找值最大的元素，在最壞情況下需要的比較次數(shù)為()。A、48B、49C、1D、0標(biāo)準(zhǔn)答案：A知識點解析：該題中rear－front＝front－1－front＜0，則該循環(huán)隊列中的元素個數(shù)為REAR－front＋50＝front－1－front＋50＝49。在該隊列中尋找值最大的元素，在最壞情況下需要的比較次數(shù)為49－1＝48。9、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)與順序存儲結(jié)構(gòu)相比，鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)點有()。A、節(jié)省存儲空間B、插入與刪除運(yùn)算效率高C、便于查找D、排序時減少元素的比較次數(shù)標(biāo)準(zhǔn)答案：B知識點解析：線性表的順序存儲結(jié)構(gòu)稱為順序表，線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈表，兩者的優(yōu)缺點如下表所示。10、下列敘述中正確的是()。A、帶鏈棧的棧底指針是隨棧的操作而動態(tài)變化的B、若帶鏈隊列的隊頭指針與隊尾指針相同，則隊列為空C、若帶鏈隊列的隊頭指針與隊尾指針相同，則隊列中至少有一個元素D、不管是順序棧還是帶鏈的棧，在操作過程中其棧底指針均是固定不變的標(biāo)準(zhǔn)答案：A知識點解析：由于帶鏈棧利用的是計算機(jī)存儲空間中的所有空閑存儲節(jié)點，因此隨棧的操作棧頂棧底指針動態(tài)變化。帶鏈的隊列中若只有一個元素，則頭指針與尾指針相同。11、某帶鏈的隊列初始狀態(tài)為front＝rear＝NULL。經(jīng)過一系列正常的入隊與退隊操作后，front＝rear＝10。該隊列中的元素個數(shù)為()。A、0B、1C、1或0D、不確定標(biāo)準(zhǔn)答案：B知識點解析：帶鏈隊列空時，頭指針和尾指針都為null；隊列中只有一個元素時，頭指針和尾指針都指向這個元素。12、某帶鏈的隊列初始狀態(tài)為。front＝rear＝NULL。經(jīng)過一系列正常的入隊與退隊操作后，front＝10，rear＝5。該隊列中的元素個數(shù)為()。A、4B、5C、6D、不確定標(biāo)準(zhǔn)答案：D知識點解析：帶鏈的隊列使用了鏈表來表示隊列，而鏈表中的元素存儲在不連續(xù)的地址中，因此當(dāng)front＝10，rear＝5時，不能確定隊列中元素的個數(shù)。13、下列結(jié)構(gòu)中為非線性結(jié)構(gòu)的是()。A、樹B、向量C、二維表D、矩陣標(biāo)準(zhǔn)答案：A知識點解析：由定義可以知道，樹為一種簡單的非線性結(jié)構(gòu)。在數(shù)這種數(shù)據(jù)結(jié)構(gòu)中，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次特性。14、設(shè)某棵樹的度為3，其中度為2，1，0的節(jié)點個數(shù)分別為3，4，15。則該樹中總節(jié)點數(shù)為()。A、不可能有這樣的樹B、30C、22D、35標(biāo)準(zhǔn)答案：A知識點解析：設(shè)樹的總節(jié)點數(shù)為n，則度為3的節(jié)點數(shù)為n－3－4－15＝n－22，根據(jù)樹中的節(jié)點數(shù)＝樹中所有節(jié)點的度之和＋1，得3×(n－22)＋2×3＋1×4＋0×15＋1＝n，則n＝27．5，求出的節(jié)點數(shù)不為整數(shù)，故不可能有這樣的樹存在。15、某二叉樹中共有350個節(jié)點，其中200個為葉子節(jié)點，則該二叉樹中度為2的節(jié)點數(shù)為()。A、不可能有這樣的二叉樹B、150C、199D、149標(biāo)準(zhǔn)答案：A知識點解析：葉子節(jié)點數(shù)為200，根據(jù)在二叉樹中度為0的節(jié)點(葉子節(jié)點)總比度為2的節(jié)點多一個，則度為2的節(jié)點數(shù)為199，199＋200＞350，故不存在這樣的二叉樹。16、度為3的一棵樹共有30個節(jié)點，其中度為3，1的節(jié)點個數(shù)分別為3，4。則該樹中的葉子節(jié)點數(shù)為()。A、14B、15C、16D、不可能有這樣的樹標(biāo)準(zhǔn)答案：B知識點解析：設(shè)葉子節(jié)點數(shù)為n，則度為2的節(jié)點數(shù)為30－3－4－n＝23－n，根據(jù)樹中的節(jié)點數(shù)＝樹中所有節(jié)點的度之和＋1，得3×3＋2×(23－n)＋1×4＋0×n＋1＝30，則n＝15。17、在具有2n個節(jié)點的完全二叉樹中，葉子節(jié)點個數(shù)為()。A、nB、n＋1C、n－1D、n/2標(biāo)準(zhǔn)答案：A知識點解析：由二叉樹的定義可知，樹中必定存在度為0的節(jié)點和度為2的節(jié)點，設(shè)度為0節(jié)點有a個，根據(jù)度為0的節(jié)點(即葉子節(jié)點)總比度為2的節(jié)點多一個，得度為2的節(jié)點有a－1個。再根據(jù)完全二叉樹的定義，度為1的節(jié)點有0個或1個，假設(shè)度1節(jié)點為0個，a＋0＋a－1＝2n，得2a＝2n－1，由于節(jié)點個數(shù)必須為整數(shù)，假設(shè)不成立；當(dāng)度為1的節(jié)點為1個時，a＋1＋a－1＝2n，得a＝n，即葉子節(jié)點個數(shù)為n。18、有二叉樹如下圖所示：則前序序列為()。A、ABDEGCFHB、DBGEAFHCC、DGEBHFCAD、ABCDEFGH標(biāo)準(zhǔn)答案：A知識點解析：前序遍歷首先訪問根節(jié)點，然后遍歷左子樹，最后遍歷右子樹；在遍歷左、右子樹時，仍然先訪問根節(jié)點，然后遍歷左子樹，最后遍歷右子樹。故本題前序序列是ABDEGCFH。中序遍歷首先遍歷左子樹，然后訪問根節(jié)點，最后遍歷右子樹；在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根節(jié)點，最后遍歷右子樹。故本題的中序序列是DBGEAFHC。后序遍歷首先遍歷左子樹，然后遍歷右子樹，最后訪問根節(jié)點；在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根節(jié)點。故本題的后序序列是DGEBHFCA。19、某二叉樹的前序序列為ABDFHCEG，中序序列為HFDBACEG。該二叉樹按層次輸出(同一層從左到右)的序列為()。A、HGFEDCBAB、HFDBGECAC、ABCDEFGHD、ACEGBDFH標(biāo)準(zhǔn)答案：C知識點解析：二叉樹的前序序列為ABDFHCEG，可以確定這個二叉樹的根節(jié)點是A；再由中序序列HFDBACEG，可以得到HFDB為根節(jié)點A的左子樹，CEG為根節(jié)點A的右子樹。同理依次對左子樹HFDB和右子樹CEG進(jìn)行同樣的推理，得到該二叉樹的結(jié)構(gòu)如下：該二叉樹按層次輸出(同一層從左到右)的序列為ABCDEFGH。20、設(shè)有序線性表的長度為n，則在有序線性表中進(jìn)行二分查找，最壞情況下的比較次數(shù)為()。A、n(n－1)/2B、nC、nlog2nD、log2n標(biāo)準(zhǔn)答案：D知識點解析：有序線性表的長度為n，設(shè)被查找元素為x，則二分查找的方法如下：將x與線性表的中間項比較：若中間項的值等于x，則說明查到，查找結(jié)束；若x小于中間項的值，則在線性表的前半部分(即中間項以前的部分)以相同的方法進(jìn)行查找；若x大于中間項的值，則在線性表的后半部分(即中間項以后的部分)以相同的方法進(jìn)行查找。這個過程一直進(jìn)行到查找成功或子表長度為0(說明線性表中沒有這個元素)為止。對于長度為n的有序線性表，在最壞情況下，二分查找只需要比較log2n次。21、在長度為n的順序表中查找一個元素，假設(shè)需要查找的元素有一半的機(jī)會在表中，并且如果元素在表中，則出現(xiàn)在表中每個位置上的可能性是相同的。則在平均情況下需要比較的次數(shù)大約為()。A、nB、3n/4C、n/2D、n/4標(biāo)準(zhǔn)答案：B知識點解析：在順序表中查找，最好情況下第一個元素就是要查找的元素，則比較次數(shù)為1；在最壞情況下，最后一個元素才是要找的元素，則比較次數(shù)為n。這是找到元素的情況。如果沒有找到元素，則要比較n次。因此，平均需要比較：找到元素的情況×1/2＋未找到元素的情況×1/2＝，大約為。22、在希爾排序法中，每經(jīng)過一次數(shù)據(jù)交換后()。A、不會產(chǎn)生新的逆序B、只能消除一個逆序C、能消除多個逆序D、消除的逆序個數(shù)一定比新產(chǎn)生的逆序個數(shù)多標(biāo)準(zhǔn)答案：C知識點解析：希爾排序法的基本思想是：將整個無序序列分割成若干小的子序列分別進(jìn)行插入排序。在子序列中每進(jìn)行一次比較就有可能移去整個線性表中的多個逆序，從而改善整個排序過程的性能。23、在快速排序法中，每經(jīng)過一次數(shù)據(jù)交換(或移動)后()。A、只能消除一個逆序B、能消除多個逆序C、不會產(chǎn)生新的逆序D、消除的逆序個數(shù)一定比新產(chǎn)生的逆序個數(shù)多標(biāo)準(zhǔn)答案：B知識點解析：在一個排列中，如果一對數(shù)的前后位置與大小順序相反，即前面的數(shù)大于后面的數(shù)，那么它們就稱為一個逆序?？焖倥判虻乃枷胧牵簭木€性表中選取一個元素，設(shè)為T，將線性表中后面小于T的元素移到前面，而前面大于T的元素移到后面，結(jié)果就將線性表分成兩部分(稱兩個子表)，T插入到其分割線的位置處，這個過程稱為線性表的分割，然后再用同樣的方法對分割出的子表再進(jìn)行同樣的分割?？焖倥判虿皇菍蓚€相鄰元素進(jìn)行比較，可以實線通過一次交換而消除多個逆序，但由于均與T(基準(zhǔn)元素)比較，也可能會產(chǎn)生新的逆序。24、在長度為97的順序有序表中作二分查找，最多需要的比較次數(shù)為()。A、48B、96C、7D、6標(biāo)準(zhǔn)答案：C知識點解析：對于長度為n的有序線性表，在最壞情況下，二分查找只需要比較log2n次。本題中n＝97，最多需要的比較次數(shù)為10g297，6＜log297＜7，故需要比較7次。國家二級MSOffice高級應(yīng)用機(jī)試（數(shù)據(jù)結(jié)構(gòu)與算法）模擬試卷第2套一、選擇題(本題共27題，每題1.0分，共27分。)1、下列敘述中正確的是A、循環(huán)隊列有隊頭和隊尾兩個指針，因此，循環(huán)隊列是非線性結(jié)構(gòu)B、在循環(huán)隊列中，只需要隊頭指針就能反映隊列中元素的動態(tài)變化情況C、在循環(huán)隊列中，只需要隊尾指針就能反映隊列中元素的動態(tài)變化情況D、循環(huán)隊列中元素的個數(shù)是由隊頭指針和隊尾指針共同決定標(biāo)準(zhǔn)答案：D知識點解析：循環(huán)隊列中元素的個數(shù)是由隊頭指針和隊尾指針共同決定的，元素的動態(tài)變化也是通過隊頭指針和隊尾指針來反映的。2、支持子程序調(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ù)的運(yùn)行結(jié)果返回到主函數(shù)調(diào)用子函數(shù)時的位置，主函數(shù)再接著往下執(zhí)行，這種過程符合棧的特點。所以一般采用棧式存儲方式。3、一棵完全二叉樹共有360個結(jié)點，則在該二叉樹中度為1的結(jié)點個數(shù)為A、0B、1C、180D、181標(biāo)準(zhǔn)答案：B知識點解析：對于一個具有n個結(jié)點的完全二叉樹，其深度為[log2n]+10本題中這個二叉樹的深度為[log2360]+1=8+1l=9。根據(jù)滿二叉樹的性質(zhì)，深度為8的滿二叉樹其結(jié)點數(shù)為28-1=256．1=255。這個完全二叉樹的第9層的結(jié)點數(shù)為360-255=105。完全二叉樹的性質(zhì)非葉子結(jié)點的子結(jié)點都為2，105除以2其商為52余數(shù)為l。因此該二叉樹中度為1的結(jié)點個數(shù)為1。選項B正確。4、下列敘述中正確的是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)。5、下列鏈表中，其邏輯結(jié)構(gòu)屬于非線性結(jié)構(gòu)的是A、二叉鏈表B、循環(huán)鏈表C、雙向鏈表D、帶鏈的棧標(biāo)準(zhǔn)答案：A知識點解析：二叉鏈表作為樹的存儲結(jié)構(gòu)。鏈表中結(jié)點的兩個鏈域分別指向該結(jié)點的第一個孩子結(jié)點和下一個兄弟結(jié)點。6、一個棧的初始狀態(tài)為空?，F(xiàn)將元素1，2，3，A，B,C依次入棧，然后再依次出棧，則元素出棧的順序是A、1，2，3，A，B，CB、C，B，A，1，2，3C、C，B，A，3，2，1D、1，2，3，C，B，A標(biāo)準(zhǔn)答案：C知識點解析：棧是按照“先進(jìn)后出”或“后進(jìn)先出”的原則組織數(shù)據(jù)的。所以出棧順序是CBA321。7、某二叉樹共有12個結(jié)點，其中葉子結(jié)點只有1個。則該二叉樹的深度為(根結(jié)點在第l層)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é)點。8、設(shè)某二二叉樹的前序序列為ABC，中序序列為CBA，則該二叉樹的后序序列為A、BCAB、CBAC、ABCD、CAB標(biāo)準(zhǔn)答案：B知識點解析：二叉樹的前序遍歷的順序為首先訪問根結(jié)點，再依次訪問左結(jié)點和右結(jié)點。中序遍歷的順序為首先訪問左結(jié)點，然后依次訪問根結(jié)點和右結(jié)點。后序遍歷的順序為首先訪問左結(jié)點，然后依次訪問右結(jié)點和根結(jié)點。根據(jù)前序可以很快確定根，然后可以查看根在中序中位置，將中序分為左右兩部分，左邊和右邊兩顆樹，在按照上述方式遞推出確定左子樹的根和右子樹。對于本題根據(jù)前序，可以確定A為根，A在中序中的位置，可以確定CB為A的左子樹上的結(jié)點，沒有右子樹。確定A之后，再看中序第二個值為B，查看B在中序中的位置，C在B左邊，確定C為B的左子樹。本題的具體二叉樹如下，因此，后序是CBA。9、在最壞情況下A、快速排序的時間復(fù)雜度比冒泡排序的時間復(fù)雜度要小B、快速排序的時間復(fù)雜度比希爾排序的時間復(fù)雜度要小C、希爾排序的時間復(fù)雜度比直接插入排序的時間復(fù)雜度要小D、快速排序的時間復(fù)雜度與希爾排序的時間復(fù)雜度是一樣的標(biāo)準(zhǔn)答案：C知識點解析：按平均時間將排序分為四類：①平方階(O(n2))排序：各類簡單排序，例如直接插入、直接選擇和冒泡排序；②線性對數(shù)階(O(nlog2n))排序：如快速排序、堆排序和歸并排序；③O(n1+§))排序：§是介于0和1之間的常數(shù)。希爾排序便是一種；④線性階(O(n))排序：本程序中的基數(shù)排序，此外還有桶、箱排序。根據(jù)以上4點，可以判斷選項C正確。10、下列敘述中錯誤的是A、算法的時間復(fù)雜度與算法所處理數(shù)據(jù)的存儲結(jié)構(gòu)有直接關(guān)系B、算法的空間復(fù)雜度與算法所處理數(shù)據(jù)的存儲結(jié)構(gòu)有直接關(guān)系C、算法的時間復(fù)雜度與空間復(fù)雜度有直接關(guān)系D、算法的時間復(fù)雜度與空間復(fù)雜度沒有必然的聯(lián)系標(biāo)準(zhǔn)答案：C知識點解析：算法的時間復(fù)雜度，是指執(zhí)行算法所需要的計算工作量。算法的空間復(fù)雜度，是指執(zhí)行這個算法所需要的內(nèi)存空間。兩者與算法所處理數(shù)據(jù)的存儲結(jié)構(gòu)都有直接關(guān)系，但兩者之間沒有直接關(guān)系，因此選項C錯誤。11、下列敘述中正確的是A、在鏈表中，如果每個結(jié)點有兩個指針域，則該鏈表一定是非線性結(jié)構(gòu)B、在鏈表中，如果有兩個結(jié)點的同一個指針域的值相等，則該鏈表一定是非線性結(jié)構(gòu)C、在鏈表中，如果每個結(jié)點有兩個指針域，則該鏈表一定是線性結(jié)構(gòu)D、在鏈表中，如果有兩個結(jié)點的同一個指針域的值相等，則該鏈表一定是線性結(jié)構(gòu)標(biāo)準(zhǔn)答案：B知識點解析：選項A敘述是錯誤的，例如在雙向鏈表中，每個結(jié)點有兩個指針域，但該鏈表是線性結(jié)構(gòu)；選項C敘述也是錯誤的，例如每個二叉樹的結(jié)點都有兩個指針域，但是其結(jié)構(gòu)是非線性結(jié)構(gòu)；選項D敘述也是錯誤的，線性結(jié)構(gòu)只有唯一的一個前驅(qū)和唯一的一個后繼(頭、尾除外)；排除法可判斷選項B正確。12、下列各序列中不是堆的是A、(91，85，53，36，47，30，24，12)B、(91，85，53，47，36，30，24，12)C、(47，91，53，85，30，12，24，36)D、(91，85，53，47，30，12，24，36)標(biāo)準(zhǔn)答案：C知識點解析：堆可以看成一棵完全二叉樹：任一根節(jié)點＞=左右孩子(或者＜=)，(大的叫大根堆，小的叫小根堆)。注意一個堆中的這種性質(zhì)有一致性，不能既有大于又有小于情況存在。此題可以這么做，把結(jié)點按照完全二叉樹畫出來就一目了然了。這個題目很明顯91是最大的根，而選項C是“左根右”的排序，那么91的左邊只有47，其他都在右邊，而右邊無法按照此順序排列，所以選項C不是堆。13、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)與順序存儲結(jié)構(gòu)相比，鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)點有A、節(jié)省存儲空間B、插入與刪除運(yùn)算效率高C、便于查找D、排序時減少元素的比較次數(shù)標(biāo)準(zhǔn)答案：B知識點解析：順序存儲時，相鄰數(shù)據(jù)元素的存放地址也相鄰(邏輯與物理統(tǒng)一)；要求內(nèi)存中可用存儲單元的地址必須是連續(xù)的。優(yōu)點是存儲密度大(=1)，存儲空間利用率高；缺點是插入或刪除元素時不方便。鏈?zhǔn)酱鎯r，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點問關(guān)系的指針優(yōu)點是插入或刪除元素時很方便效率高，使用靈活。缺點是存儲密度小(＜1)，存儲空間利用率低，故選項B正確。14、某二叉樹的前序序列為ABCD，中序序列為DCBA，則后序序列為A、BADCB、DCBAC、CDABD、ABCD標(biāo)準(zhǔn)答案：B知識點解析：在二叉樹前序遍歷中ABCD中A是根節(jié)點，而在后序遍歷中根結(jié)點位于最后，所以選項B正確。15、設(shè)非空二叉樹的所有子樹中，其左子樹上的結(jié)點值均小于根結(jié)點值，而右子樹上的結(jié)點值均不小于根結(jié)點值，則稱該二叉樹為排序二叉樹。對排序二叉樹的遍歷結(jié)果為有序序列的是A、中序序列B、前序序列C、后序序列D、前序序列或后序序列標(biāo)準(zhǔn)答案：A知識點解析：中序遍歷的次序是先遍歷左子樹，再遍歷根節(jié)點，最后遍歷右子樹。而左子樹結(jié)點值＜根節(jié)點節(jié)點值≤右子樹節(jié)點值，是有序序列，因此選項A正確。16、下列敘述中正確的是A、在循環(huán)隊列中，隊頭指針和隊尾指針的動態(tài)變化決定隊列的長度B、在循環(huán)隊列中，隊尾指針的動態(tài)變化決定隊列的長度，C、在帶鏈的隊列中，隊頭指針與隊尾指針的動態(tài)變化決定隊列的長度D、在帶鏈的棧中，棧頂指針的動態(tài)變化決定棧中元素的個數(shù)標(biāo)準(zhǔn)答案：A知識點解析：循環(huán)隊列是將順序隊列首尾相連形成的，隨著插入元素或刪除元素的進(jìn)行，其隊頭指針及隊尾指針是在不斷變化的，有時可能會出現(xiàn)隊頭指針大于隊尾指針的情況，也可能是隊尾指針大于隊頭指針。循環(huán)隊列中計算元素的個數(shù)公式為：。所以選項A正確。17、設(shè)表的長度為n。下列算法中，最壞情況下比較次數(shù)小于n的是A、二分查找法B、堆排序C、快速排序D、順序查找法標(biāo)準(zhǔn)答案：A知識點解析：二分法查找只適用于順序存儲的有序表。二分查找的基本方法是：將被查元素x與線性表的中間項進(jìn)行比較，若中間項的值等于x，則說明查到：若小于中間項的值則在線性表的前半部分；以相同的方法進(jìn)行查找；若大于中間項的值，則在線性表的后半部分以相同的方法進(jìn)行查找。在最壞情況下，二分查找需要比較log2n次。所以選項A正確。18、循環(huán)隊列的存儲空間為Q(1：200)，初始狀態(tài)為front=rear=200。經(jīng)過一系列正常的入隊與退隊操作后，front=rear=1，則循環(huán)隊列中的元素個數(shù)為A、0或200B、1C、2D、199標(biāo)準(zhǔn)答案：A知識點解析：循環(huán)隊列中，由于入隊時尾指針rear向前追趕頭指針front；出隊時頭指針front向前追趕尾指針rear，造成隊空和隊滿時頭尾指針均相等。因此，無法通過條件front=rear來判別隊列是“空”還是“滿”。對于本題來說，經(jīng)過一系列正常的入隊與退隊操作后，front=rear=1。此時，要么隊列為空(元素個數(shù)為0)，要么隊列為滿(元素個數(shù)為200)。所以選項A正確。19、某帶鏈的隊列初始狀態(tài)為front=rear=NULL。經(jīng)過一系列正常的入隊與退隊操作后，front=rear=10。該隊列中的元素個數(shù)為A、1B、0C、1或0D、不確定標(biāo)準(zhǔn)答案：A知識點解析：循環(huán)隊列用數(shù)組A[0；m－1]存放其元素值，已知其頭尾指針分別是front和rear，則當(dāng)前隊列的元素個數(shù)是(rear－front+m)％m=1，所以選項A正確。20、設(shè)表的長度為15。則在最壞情況下，快速排序所需要的比較次數(shù)為A、105B、55C、15D、75標(biāo)準(zhǔn)答案：A知識點解析：假設(shè)線性表的長度為n，在最壞情況下，快速排序法的比較次數(shù)是n(n－1)／2。題中n=15，所以15*14／2=105。所以選項A正確。21、下列敘述中錯誤的是A、算法的時間復(fù)雜度與問題規(guī)模無關(guān)B、算法的時間復(fù)雜度與計算機(jī)系統(tǒng)無關(guān)C、算法的時間復(fù)雜度與空間復(fù)雜度沒有必然的聯(lián)系D、算法的空間復(fù)雜度與算法運(yùn)行輸出結(jié)果的數(shù)據(jù)量無關(guān)標(biāo)準(zhǔn)答案：A知識點解析：一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，用T(n)表示，若有某個輔助函數(shù)f(n)，使得當(dāng)n趨近于無窮大時，T(n)／f(n)的極限值為不等于零的常數(shù)，則稱16(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=O(f(n))，稱O(f(n))為算法的漸進(jìn)時間復(fù)雜度，簡稱時間復(fù)雜度。所以選項A正確。22、設(shè)一棵度為3的樹，其中度為2，1，0的結(jié)點數(shù)分別為3，1，6。該樹中度為3的結(jié)點數(shù)為A、1B、2C、3D、不可能有這樣的樹標(biāo)準(zhǔn)答案：A知識點解析：因為任一棵樹中，結(jié)點總數(shù)=總分支數(shù)目+1，所以：6+1+3+n3=(0*6+1*1+2*3+3*n3)+1。運(yùn)算結(jié)果n3=1。其中，n3表示度為3的結(jié)點數(shù)，所以選項A正確。23、帶鏈隊列空的條件是A、front=rear=NULLB、front=rear=－1C、front=NULL且rear=－1D、front=－1且rear=NULL標(biāo)準(zhǔn)答案：A知識點解析：帶鏈隊列空的條件有兩個：一個是front=rear，一個是它們都等于空。24、下列敘述中錯誤的是A、循環(huán)鏈表中有一個表頭結(jié)點B、循環(huán)鏈表的存儲空間是連續(xù)的C、循環(huán)鏈表實現(xiàn)了空表與非空表運(yùn)算的統(tǒng)一D、循環(huán)鏈表的表頭指針與循環(huán)鏈表中最后一個結(jié)點的指針均指向表頭結(jié)點標(biāo)準(zhǔn)答案：B知識點解析：循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯Y(jié)構(gòu)。它的特點是表中最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表形成一個環(huán)。循環(huán)鏈表的結(jié)點是指針指向，它不一定要是連續(xù)的存儲空間，也可以是斷開的空間。25、下列敘述中正確的是A、矩陣是非線性結(jié)構(gòu)B、數(shù)組是長度固定的線性表C、對線性表只能作插入與刪除運(yùn)算D、線性表中各元素的數(shù)據(jù)類型可以不同標(biāo)準(zhǔn)答案：B知識點解析：所謂數(shù)組，就是相同數(shù)據(jù)類型的元素按一定順序排列的集合，就是把有限個類型相同的變量用一個名字命名，然后用編號區(qū)分它們的變量的集合，這個名字稱為數(shù)組名，編號稱為下標(biāo)。26、下列敘述中正確的是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)。27、設(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ù)前序中的子樹FIJ和中序中的IFJ子樹可知F為C的右結(jié)點，I為F的左結(jié)點、J為F的右結(jié)點。由此可畫出這個二叉樹，然后根據(jù)二叉樹可的后序序列為DGHEBIJFCA。國家二級MSOffice高級應(yīng)用機(jī)試（數(shù)據(jù)結(jié)構(gòu)與算法）模擬試卷第3套一、選擇題(本題共24題，每題1.0分，共24分。)1、下列敘述中正確的是()。A、所謂算法就是計算方法B、程序可以作為算法的一種描述方法C、算法設(shè)計只需考慮得到計算結(jié)果D、算法設(shè)計可以忽略算法的運(yùn)算時間標(biāo)準(zhǔn)答案：B知識點解析：算法是指對解題方案的準(zhǔn)確而完整的描述，算法不等于數(shù)學(xué)上的計算方法，也不等于程序。算法設(shè)計需要考慮可行性、確定性、有窮性與足夠的情報，不能只考慮計算結(jié)果。算法設(shè)計有窮性是指操作步驟有限且能在有限時間內(nèi)完成，如果一個算法執(zhí)行耗費(fèi)的時間太長，即使最終得出了正確結(jié)果，也是沒有意義的。算法在實現(xiàn)時需要用具體的程序設(shè)計語言描述，所以程序可以作為算法的一種描述方法。2、為了降低算法的空間復(fù)雜度，要求算法盡量采用原地工作(inplace)。所謂原地工作是指()。A、執(zhí)行算法時不使用額外空間B、執(zhí)行算法時不使用任何存儲空間C、執(zhí)行算法時所使用的額外空間隨算法所處理的數(shù)據(jù)空間大小的變化而變化D、執(zhí)行算法時所使用的額外空間固定(即不隨算法所處理的數(shù)據(jù)空間大小的變化而變化)標(biāo)準(zhǔn)答案：D知識點解析：對于算法的空間復(fù)雜度，如果額外空間量相對于問題規(guī)模(即輸入數(shù)據(jù)所占的存儲空間)來說是常數(shù)，即額外空間量不隨問題規(guī)模的變化而變化，則稱該算法是原地工作的。3、下列敘述中錯誤的是()。A、數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素可以是另一數(shù)據(jù)結(jié)構(gòu)B、數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素不能是另一數(shù)據(jù)結(jié)構(gòu)C、空數(shù)據(jù)結(jié)構(gòu)可以是線性結(jié)構(gòu)也可以是非線性結(jié)構(gòu)D、非空數(shù)據(jù)結(jié)構(gòu)可以沒有根節(jié)點標(biāo)準(zhǔn)答案：B知識點解析：數(shù)據(jù)元素是一個含義很廣泛的概念，它是數(shù)據(jù)的“基本單位”，在計算機(jī)中通常作為一個整體進(jìn)行考慮和處理。數(shù)據(jù)元素可以是一個數(shù)據(jù)，也可以是被抽象出的具有一定結(jié)構(gòu)的數(shù)據(jù)集合，所以數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素可以是另一數(shù)據(jù)結(jié)構(gòu)。滿足有且只有一個根節(jié)點并且每一個節(jié)點最多有一個前件，也最多有一個后件的非空的數(shù)據(jù)結(jié)構(gòu)認(rèn)為是線性結(jié)構(gòu)，不滿足條件的結(jié)構(gòu)為非線性結(jié)構(gòu)。空數(shù)據(jù)結(jié)構(gòu)可以是線性結(jié)構(gòu)也可以是非線性結(jié)構(gòu)。非空數(shù)據(jù)結(jié)構(gòu)可以沒有根節(jié)點，如非性線結(jié)構(gòu)“圖”就沒有根節(jié)點。4、下列敘述中正確的是()。A、矩陣是非線性結(jié)構(gòu)B、數(shù)組是長度固定的線性表C、對線性表只能作插入與刪除運(yùn)算D、線性表中各元素的數(shù)據(jù)類型可以不同標(biāo)準(zhǔn)答案：B知識點解析：矩陣也是線性表，只不過是比較復(fù)雜的線性表。線性表中各元素的數(shù)據(jù)類型必須相同。在線性表中，不僅可以做插入與刪除運(yùn)算，還可以進(jìn)行查找或?qū)€性表進(jìn)行排序等操作。5、設(shè)棧的存儲空間為S(1：50)，初始狀態(tài)為top＝－1?，F(xiàn)經(jīng)過一系列正常的入棧與退棧操作后，top＝30，則棧中的元素個數(shù)為()。A、20B、19C、31D、30標(biāo)準(zhǔn)答案：D知識點解析：棧的初始狀態(tài)為top＝－1表示棧為空，經(jīng)過一系列正常的入棧與退棧操作后top＝30，則空間(1：30)中插入了元素，共30個。6、設(shè)棧的存儲空間為S(1：m)，初始狀態(tài)為top＝m＋1。經(jīng)過一系列入棧與退棧操作后，top＝m?，F(xiàn)又在棧中退出一個元素后，棧頂指針top值為()。A、0B、m－1C、m＋1D、產(chǎn)生?？斟e誤標(biāo)準(zhǔn)答案：C知識點解析：棧的順序存儲空間為S(1：m)，初始狀態(tài)top＝m＋1，所以這個棧是m在棧底(也可理解為開口向下的棧)。經(jīng)過一系列入棧與退棧操作后top＝m，則棧中有1個元素，若現(xiàn)在又退出一個元素，那么棧頂指針下移一位，回到m＋1的位置。7、下列敘述中正確的是()。A、在循環(huán)隊列中，隊尾指針的動態(tài)變化決定隊列的長度B、在循環(huán)隊列中，隊頭指針和隊尾指針的動態(tài)變化決定隊列的長度C、在帶鏈的隊列中，隊頭指針與隊尾指針的動態(tài)變化決定隊列的長度D、在帶鏈的棧中，棧頂指針的動態(tài)變化決定棧中元素的個數(shù)標(biāo)準(zhǔn)答案：B知識點解析：在循環(huán)隊列中，隊頭指針和隊尾指針的動態(tài)變化決定隊列的長度。帶鏈的棧和帶鏈的隊列均采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，而在這種結(jié)構(gòu)中，各數(shù)據(jù)節(jié)點的存儲序號是不連續(xù)的，并且各節(jié)點在存儲空間中的位置關(guān)系與邏輯關(guān)系也不一致，故頭指針和尾指針或棧頂指針無法決定鏈表長度。8、設(shè)循環(huán)隊列為Q(1：m)，其初始狀態(tài)為front＝rear＝m。經(jīng)過一系列入隊與退隊運(yùn)算后，front＝30，rear＝10。現(xiàn)要在該循環(huán)隊列中作順序查找，最壞情況下需要比較的次數(shù)為()。A、19B、20C、m－19D、m－20標(biāo)準(zhǔn)答案：D知識點解析：front＝30，rear＝10，front＞rear，則隊列中有10－30＋m＝m－20個元素，在作順序查找時，最壞情況下(最后一個元素才是要找的元素或沒有要查找的元素)比較次數(shù)為m－20次。9、設(shè)循環(huán)隊列的存儲空間為Q(1：m)，初始狀態(tài)為空?，F(xiàn)經(jīng)過一系列正常的入隊與退隊操作后，front＝m，rear＝m＝1，此后從該循環(huán)隊列中刪除一個元素，則隊列中的元素個數(shù)為()。A、m－1B、m－2C、0D、1標(biāo)準(zhǔn)答案：B知識點解析：在循環(huán)隊列中，如果rear－front＞0，則隊列中的元素個數(shù)為rear－front個；如果rear－front＜0，則隊列中的元素個數(shù)為rear－front＋m。該題中m－1＜m，即rear－front＜0，則該循環(huán)隊列中的元素個數(shù)為(m—1)－m＋m＝m－1。此后從該循環(huán)隊列中刪除一個元素，則隊列中的元素個數(shù)為m－1－1＝m－2。10、帶鏈的棧與順序存儲的棧相比，其優(yōu)點是()。A、入棧與退棧操作方便B、可以省略棧底指針C、入棧操作時不會受棧存儲空間的限制而發(fā)生溢出D、所占存儲空間相同標(biāo)準(zhǔn)答案：C知識點解析：帶鏈的棧就是用一個線性鏈表來表示的棧，線性鏈表不受存儲空間大小的限制，因此入棧操作時不會受棧存儲空間的限制而發(fā)生溢出(不需考慮棧滿的問題)。11、帶鏈隊列空的條件是()。A、front＝rear＝NULLB、font＝－1且rear＝NULLC、front＝NULL且rear＝－1D、front＝rear＝－1標(biāo)準(zhǔn)答案：A知識點解析：帶鏈的隊列就是用一個單鏈表來表示的隊列，隊列中的每一個元素對應(yīng)鏈表中的一個節(jié)點。隊列空時，頭指針和尾指針都為NULL。12、某帶鏈的隊列初始狀態(tài)為front＝rear＝NULL。經(jīng)過一系列正常的入隊與退隊操作后，front＝rear＝10。該隊列中的元素個數(shù)為()。A、0B、1C、1或0D、不確定標(biāo)準(zhǔn)答案：B知識點解析：帶鏈隊列空時，頭指針和尾指針都為NULL；隊列中只有一個元素時，頭指針和尾指針都指向這個元素。13、下列敘述中錯誤的是()。A、循環(huán)鏈表中有一個表頭節(jié)點B、循環(huán)鏈表是循環(huán)隊列的存儲結(jié)構(gòu)C、循環(huán)鏈表的表頭指針與循環(huán)鏈表中最后一個節(jié)點的指針均指向表頭節(jié)點D、循環(huán)鏈表實現(xiàn)了空表與非空表運(yùn)算的統(tǒng)一標(biāo)準(zhǔn)答案：B知識點解析：循環(huán)鏈表是指在單鏈表的第一個節(jié)點前增加一個表頭節(jié)點，隊頭指針指向表頭節(jié)點，最后一個節(jié)點的指針域的值由NULL改為指向表頭節(jié)點。循環(huán)鏈表是線性表的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)，循環(huán)隊列是隊列的一種順序存儲結(jié)構(gòu)。14、設(shè)一棵樹的度為3，其中沒有度為2的節(jié)點，且葉子節(jié)點數(shù)為5。該樹中度為3的節(jié)點數(shù)為()。A、3B、1C、2D、不可能有這樣的樹標(biāo)準(zhǔn)答案：C知識點解析：設(shè)樹的節(jié)點數(shù)為m，度為3的節(jié)點數(shù)為n，則度為1的節(jié)點數(shù)為m－n－5，根據(jù)樹中的節(jié)點數(shù)＝樹中所有節(jié)點的度之和＋1，得3×n＋1×(m－n－5)＋5×0＋1＝m，則n＝2。15、某二叉樹共有730個節(jié)點，其中度為1的節(jié)點有30個，則葉子節(jié)點個數(shù)為()。A、1B、351C、350D、不存在這樣的二叉樹標(biāo)準(zhǔn)答案：D知識點解析：設(shè)葉子節(jié)點數(shù)為n，根據(jù)在二叉樹中度為0的節(jié)點(葉子節(jié)點)總比度為2的節(jié)點多一個，則度為2的節(jié)點數(shù)為n－1，n＋n－1＋30＝730，得n＝350．5。由于節(jié)點數(shù)只能為整數(shù)，所以不存在這樣的二叉樹。16、某棵樹中共有25個節(jié)點，且只有度為3的節(jié)點和葉子節(jié)點，其中葉子節(jié)點有7個，則該樹中度為3的節(jié)點數(shù)為()。A、6B、7C、8D、不存在這樣的樹標(biāo)準(zhǔn)答案：D知識點解析：根據(jù)題意，樹中只有度為3的節(jié)點和葉子節(jié)點(7個)，則度為3的節(jié)點有25－7＝18個；又根據(jù)樹中的節(jié)點數(shù)＝樹中所有節(jié)點的度之和＋1，設(shè)度為3的節(jié)點數(shù)為n，則3n＋1＝25。得n＝8。兩種方式得到的度為3的節(jié)點數(shù)不同，故不存在這樣的樹。17、某完全二叉樹共有256個節(jié)點，則該完全二叉樹的深度為()。A、7B、8C、9D、10標(biāo)準(zhǔn)答案：C知識點解析：根據(jù)完全二又樹的性質(zhì)：具有n個節(jié)點的完全二叉樹的深度為[log2n]＋1。本題中完全二叉樹共有256個節(jié)點，則深度為[log2，256]＋1＝8＋1＝9。18、設(shè)二叉樹的前序序列與中序序列均為ABCDEFGH，則該二叉樹的后序序列為()。A、ABCDHGFEB、DCBAHGFEC、EFGHABCDD、HGFEDCBA標(biāo)準(zhǔn)答案：D知識點解析：二叉樹的前序序列與中序序列均為ABCDEFGH，可知二叉樹根節(jié)點為A，且根節(jié)點A只有右子樹，沒有左子樹。同理，可以推出節(jié)點B只有右子樹無左子樹。依此類推，該二叉樹除葉子節(jié)點外，每個節(jié)點只有右子樹無左子樹。因此該二叉樹的后序序列為HGFEDCBA。19、某二叉樹的前序序列為ABCDEG，中序序列為DCBAEFG，則該二叉樹的深度(根節(jié)點在第1層)為()。A、2B、3C、4D、5標(biāo)準(zhǔn)答案：C知識點解析：二叉樹的前序序列為ABCDEFG，則A為根節(jié)點；中序序列為DCBAEFG，可知節(jié)點D、C、B位于根節(jié)點的左子樹上，節(jié)點E、F、G位于根節(jié)點的右子樹上。另外，節(jié)點B、C、D在前序序列和中序序列中順序相反，則說明這三個節(jié)點依次位于前一個節(jié)點的左子樹上；節(jié)點E、F、G順序未變，則說明這三個節(jié)點依次位于前一個節(jié)點的右子樹上。故二叉樹深度為4。20、設(shè)二叉樹中共有15個節(jié)點，其中的節(jié)點值互不相同。如果該二叉樹的前序序列與中序序列相同，則該二叉樹的深度為()。A、4B、6C、15D、不存在這樣的二叉樹標(biāo)準(zhǔn)答案：C知識點解析：在具有n個節(jié)點的二叉樹中，如果各節(jié)點值互不相同，若該二叉樹的前序序列與中序序列相同，則說明該二叉樹只有右子樹，左子樹為空，二叉樹的深度為n；若該二叉樹的后序序列與中序序列相同，則說明該二叉樹只有左子樹，右子樹為空，二叉樹的深度為n。故本題中二叉樹的深度為15。21、在長度為n的順序表中查找一個元素，假設(shè)需要查找的元素一定在表中，并且元素出現(xiàn)在表中每個位置上的可能性是相同的，則在平均情況下需要比較的次數(shù)為()。A、n/4B、nC、3n/4D、(n＋1)/2標(biāo)準(zhǔn)答案：D知識點解析：在順序表中查找，最好情況下第一個元素就是要查找的元素，則比較次數(shù)為1；在最壞情況下，最后一個元素才是要找的元素，則比較次數(shù)為n。則平均比較次數(shù)：(1＋2＋…＋n)/n＝(n(n＋1)/2)/n＝(n＋1)/2。22、下列敘述中正確的是()。A、二分查找法只適用于順序存儲的有序線性表B、二分查找法適用于任何存儲結(jié)構(gòu)的有序線性表C、二分查找法適用于有序循環(huán)鏈表D、二分查找法適用于有序雙向鏈表標(biāo)準(zhǔn)答案：A知識點解析：二分查找法(又稱對分查找法)只適用于順序存儲的有序表。在此所說的有序表是指線性表的中元素按值非遞減排列(即從小到大，但允許相鄰元素值相等)。23、下列各排序法中，最壞情況下的時間復(fù)雜度最低的是()。A、堆排序B、快速排序C、希爾排序D、冒泡排序標(biāo)準(zhǔn)答案：A知識點解析：最壞情況下，堆排序需要比較nlog2n次，希爾排序需要比較nr(1＜r＜2)次，快速排序、冒泡排序均需要比較n(n1－1)/2次。故堆排序時間復(fù)雜度最低。24、設(shè)順序表的長度為16，對該表進(jìn)行簡單插入排序。在最壞情況下需要的比較次數(shù)為()。A、120B、60C、30D、15標(biāo)準(zhǔn)答案：A知識點解析：簡單插入排序在最壞情況下，即初始排序序列是逆序的情況下，比較次數(shù)為n(n－1)/2，移動次數(shù)為n(n－1)/2。本題中n＝16，16×(16－1)÷2＝8×15＝120。國家二級MSOffice高級應(yīng)用機(jī)試（數(shù)據(jù)結(jié)構(gòu)與算法）模擬試卷第4套一、選擇題(本題共28題，每題1.0分，共28分。)1、對長度為n的線性表排序，在最壞情況下，比較次數(shù)不是n(n一1)／2的排序方法是A、快速排序B、冒泡排序C、直接插入排序D、堆排序標(biāo)準(zhǔn)答案：D知識點解析：各種排序方法中最壞情況下需要比較的次數(shù)分別為：冒泡排序nf=(n-1)／2、快速排序n(n-1)／2、簡單插入排序n(n-1)／2、希爾排序O(n1．5)、簡單選擇排序n(n-1)／2、堆排序O(nlog2n)。2、對于循環(huán)隊列，下列敘述中正確的是A、隊頭指針是固定不變的B、隊頭指針一定大于隊尾指針C、隊頭指針一定小于隊尾指針D、隊頭指針可以大于隊尾指針，也可以小于隊尾指針標(biāo)準(zhǔn)答案：D知識點解析：所謂循環(huán)隊列，就是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間，供隊列循環(huán)使用。在循環(huán)隊列中，用隊尾指針rear指向隊列中的隊尾元素，用隊頭指針front指向隊頭元素的前一個位置。循環(huán)隊列的主要操作是：入隊運(yùn)算和退隊運(yùn)算。每進(jìn)行一次入隊運(yùn)算，隊尾指針就進(jìn)一。每進(jìn)行一次退隊運(yùn)算，隊頭指針就進(jìn)一。當(dāng)rear或front等于隊列的長度加1時，就把rear或front值置為1。所以在循環(huán)隊列中，隊頭指針可以大于隊尾指針，也可以小于隊尾指針。3、下列敘述中正確的是A、棧是“先進(jìn)先出”的線性表B、隊列是“先進(jìn)后出”的線性表C、循環(huán)隊列是非線性結(jié)構(gòu)D、有序線性表既可以采用順序存儲結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)標(biāo)準(zhǔn)答案：D知識點解析：本題主要考查了棧、隊列、循環(huán)隊列的概念，棧是先進(jìn)后出的線性表，隊列是先進(jìn)先出的線性表。根據(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)。4、下列敘述中正確的是A、在棧中，棧中元素隨棧底指針與棧頂指針的變化而動態(tài)變化B、在棧中，棧頂指針不變，棧中元素隨棧底指針的變化而動態(tài)變化C、在棧中，棧底指針不變，棧中元素隨棧頂指針的變化而動態(tài)變化D、上述三種說法都不對標(biāo)準(zhǔn)答案：C知識點解析：在棧中，允許插入與刪除的一端稱為棧頂，而不允許插入與刪除的另一端稱為棧底棧跟隊列不同，元素只能在棧頂壓入或彈出，棧底指針不變，棧中元素隨棧頂指針的變化而動態(tài)變化，遵循后進(jìn)先出的規(guī)則。5、下列敘述中正確的是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)的隊列。6、設(shè)二叉樹共有150個結(jié)點，其中度為1的結(jié)點有10個，則該二叉樹中的葉子結(jié)點數(shù)為A、71B、70C、69D、不可能有這樣的二叉樹標(biāo)準(zhǔn)答案：D知識點解析：根據(jù)二叉樹的性質(zhì)3，在任意一顆二叉樹中，度為0的結(jié)點(即葉子結(jié)點)總是比度為2的結(jié)點多一個。即有n0=n2+1。對于這個題來說，總結(jié)點數(shù)150=n0+n1+n2=n2+10+n2=2n2+11，所以2n2=139，度為2個結(jié)點個數(shù)不能確定。選項D正確。7、一棵二叉樹中共有80個葉子結(jié)點與70個度為l的結(jié)點，則該二叉樹中的總結(jié)點數(shù)為A、219B、229C、230D、231標(biāo)準(zhǔn)答案：B知識點解析：根據(jù)二叉樹的性質(zhì)，在任意二叉樹中，度為O的結(jié)點(即葉子結(jié)點)總是比度為2的結(jié)點多一個，故總結(jié)點數(shù)=葉子節(jié)點數(shù)+度為2的節(jié)點數(shù)+度為1的節(jié)點數(shù)=80+79+70=229。8、下列敘述中錯誤的是A、在雙向鏈表中，可以從任何一個結(jié)點開始直接遍歷到所有結(jié)點B、在循環(huán)鏈表中，可以從任何一個結(jié)點開始直接遍歷到所有結(jié)點C、在線性單鏈表中，可以從任何一個結(jié)點開始直接遍歷到所有結(jié)點D、在二叉鏈表中，可以從根結(jié)點開始遍歷到所有結(jié)點標(biāo)準(zhǔn)答案：C知識點解析：線性隊列是一種線性單鏈表，對線性隊列的遍歷只能從隊列的頭開始，從中間的結(jié)點開始不能夠遍歷到所有的結(jié)點。選項C的描述是錯誤的。9、設(shè)某二叉樹的后序序列為CBA，中序序列為ABC，則該二叉樹的前序序列為A、BCAB、CBAC、ABCD、CAB標(biāo)準(zhǔn)答案：C知識點解析：二叉樹的前序遍歷順序為首先訪問根結(jié)點，再依次訪問左結(jié)點和右結(jié)點。中序遍歷的順序為首先訪問左結(jié)點，然后依次訪問根結(jié)點和右結(jié)點。后序遍歷首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點。根據(jù)后序可以很快確定根結(jié)點，然后可以查看根在中序中位置，將中序分為左右兩部分，左邊和右邊兩顆樹，在按照上述方式遞推出確定左子樹的根和右子樹。本題根據(jù)后序，可以確定A為根結(jié)點；根據(jù)B在中序中的位置，可以確定A沒有左子樹，BC為A的右子樹，C為B的右子樹。本題的具體二叉樹如下，因此，這棵二叉樹的前序是ABC，選項C確。10、算法空間復(fù)雜度的度量方法是A、算法程序的長度B、算法所處理的數(shù)據(jù)量C、執(zhí)行算法所需要的工作單元D、執(zhí)行算法所需要的存儲空間標(biāo)準(zhǔn)答案：D知識點解析：算法空間復(fù)雜度是對一個算法在運(yùn)行過程中臨時占用存儲空間大小的度量，因此選項D正確。11、下列敘述中正確的是A、存儲空間連續(xù)的數(shù)據(jù)結(jié)構(gòu)一定是線性結(jié)構(gòu)B、存儲空間不連續(xù)的數(shù)據(jù)結(jié)構(gòu)一定是非線性結(jié)構(gòu)C、沒有根結(jié)點的非空數(shù)據(jù)結(jié)構(gòu)一定是線性結(jié)構(gòu)D、具有兩個根結(jié)點的數(shù)據(jù)結(jié)構(gòu)一定是非線性結(jié)構(gòu)標(biāo)準(zhǔn)答案：D知識點解析：數(shù)據(jù)結(jié)構(gòu)從邏輯上來劃分，分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，一對一是線性結(jié)構(gòu)，其它的為非線性結(jié)構(gòu)。判斷一個非空的數(shù)據(jù)結(jié)構(gòu)是否為線性結(jié)構(gòu)必須滿足以下兩個條件：①有且只有一個根結(jié)點；②每一個結(jié)點最多有一個前件，也最多有一個后件。根據(jù)這兩個條件，可知選項A)、B)和C)都不能判定是否是線性結(jié)構(gòu)，選項D)正確。12、下列敘述中正確的是A、鏈表結(jié)點中具有兩個指針域的數(shù)據(jù)結(jié)構(gòu)可以是線性結(jié)構(gòu)，也可以是非線性結(jié)構(gòu)B、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，每個結(jié)點必須有指向前件和指向后件的兩個指針C、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，每個結(jié)點只能有一個指向后件的指針D、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，葉子結(jié)點的指針只能是空標(biāo)準(zhǔn)答案：A知識點解析：在鏈?zhǔn)酱鎯Ψ绞街?，每個結(jié)點由兩部分組成：數(shù)據(jù)域和指針域，指針域用于指向該節(jié)點的前一個或后一個結(jié)點，所以選項B)、C)、D)說法錯誤。選項A)中，例如雙向鏈表就具有兩個指針，也屬于線性結(jié)構(gòu)，所以選項A正確。13、下列敘述中正確的是A、循環(huán)隊列是順序存儲結(jié)構(gòu)B、循環(huán)隊列是鏈?zhǔn)酱鎯Y(jié)構(gòu)C、循環(huán)隊列是非線性結(jié)構(gòu)D、循環(huán)隊列的插入運(yùn)算不會發(fā)生溢出現(xiàn)象標(biāo)準(zhǔn)答案：A知識點解析：循環(huán)隊列屬于隊列的特例和棧同屬于線性結(jié)構(gòu)，所以選項C不正確。在順序隊列中，由于數(shù)組空間不夠而產(chǎn)生的溢出叫真溢出；川頁序隊列因多次入隊列和出隊列操作后出現(xiàn)的有存儲空間但不能進(jìn)行入隊列操作的溢出稱為假溢出：假溢出是由于隊尾rear的值和隊頭front的值不能由所定義數(shù)組下界值自動轉(zhuǎn)為數(shù)組上界值而產(chǎn)生的，解決的辦法是把順序隊列所使用的存儲空間構(gòu)造成一個邏輯上首尾相連的循環(huán)隊列。因此，順序隊列通常都采用順序循環(huán)隊列結(jié)構(gòu)；棧的存儲方式有順序存儲和鏈?zhǔn)酱鎯Γ蔬x項A正確，選項B不正確。循環(huán)隊列雖然能解決假溢出，卻不能解決在順序隊列中，由于數(shù)組空間不夠而產(chǎn)生的真溢出，故選項D不正確。14、設(shè)有二叉樹如下圖所示，則后序序列為A、ABDEGCFHB、DBGEAFHCC、DGEBHFCAD、ABCDEFGH標(biāo)準(zhǔn)答案：C知識點解析：后序遍歷(LRD)首先遍歷左子樹，然后訪問遍歷右子樹，最后訪問根結(jié)點，可知選項C正確。15、設(shè)棧的存儲空間為S(1：50)，初始狀態(tài)為top=51。現(xiàn)經(jīng)過一系列正常的入棧與退棧操作后，top=50，則棧中的元素個數(shù)為A、1B、0C、50D、49標(biāo)準(zhǔn)答案：A知識點解析：棧的存儲空間為S(1：50)，初始狀態(tài)為top=51?，F(xiàn)經(jīng)過一系列正常的入棧與退棧操作后，top=50，則棧中有51-50=1個元素，選項A正確。16、在具有2n個結(jié)點的完全二叉樹中，葉子結(jié)點個數(shù)為A、nB、n+1C、n－1D、n／2標(biāo)準(zhǔn)答案：A知識點解析：在具有2n個結(jié)點的完全二叉樹中，葉子結(jié)點個數(shù)為：(2n+1)／2取整，其值等于n。所以選項A正確。17、在長度為n的順序表中查找一個元素，假設(shè)需要查找的元素有一半的機(jī)會在表中，并且如果元素在表中，則出現(xiàn)在表中每個位置上的可能性是相同的。則在平均情況下需要比較的次數(shù)大約為A、(3+n)／4B、nC、n／2D、n／4標(biāo)準(zhǔn)答案：A知識點解析：在長度為n的順序表中查找一個元素，最好的情況是目標(biāo)在第一個，一次找到；最壞的情況是目標(biāo)在最后一個，n次找到。那么平均長度為：(1+2+…+n)／n=(n(n+1)／2)／n=(n+1)／2本題需要查找的元素有一半的機(jī)會在表中，則在平均情況下需要比較的次數(shù)大約為((1+n)／2+1)／2=(3+n)／4。所以選項A正確。18、循環(huán)隊列的存儲空間為Q(1：100)，初始狀態(tài)為front=rear=100。經(jīng)過一系列正常的入隊與退隊操作后，front=rear=99，則循環(huán)隊列中的元素個數(shù)為A、0或100B、1C、2D、99標(biāo)準(zhǔn)答案：A知識點解析：循環(huán)隊列中，由于入隊時尾指針。rear向前追趕頭指針：front；出隊時頭指針front向前追趕尾指針rear，造成隊空和隊滿時頭尾指針均相等。因此，無法通過條件front=rear來判別隊列是“空”還是“滿”。對于這個題目來說，經(jīng)過一系列正