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

國家二級(jí)MSOffice高級(jí)應(yīng)用機(jī)試（數(shù)據(jù)結(jié)構(gòu)與算法）模擬試卷1（共9套）（共238題）國家二級(jí)MSOffice高級(jí)應(yīng)用機(jī)試（數(shù)據(jù)結(jié)構(gòu)與算法）模擬試卷第1套一、選擇題(本題共23題，每題1.0分，共23分。)1、下列敘述中正確的是()。A、算法的時(shí)間復(fù)雜度與計(jì)算機(jī)的運(yùn)行速度有關(guān)B、算法的時(shí)間復(fù)雜度與運(yùn)行算法時(shí)特定的輸入有關(guān)C、算法的時(shí)間復(fù)雜度與算法程序中的語句條數(shù)成正比D、算法的時(shí)間復(fù)雜度與算法程序編制者的水平有關(guān)標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：為了能夠比較客觀地反映出一個(gè)算法的效率，在度量一個(gè)算法的工作量時(shí)，不僅應(yīng)該與所使用的計(jì)算機(jī)、程序設(shè)計(jì)語言以及程序編制者無關(guān)，而且還應(yīng)該與算法實(shí)現(xiàn)過程中的許多細(xì)節(jié)無關(guān)。為此，可以用算法在執(zhí)行過程中所需基本運(yùn)算的執(zhí)行次數(shù)來度量算法的工作量。算法所執(zhí)行的基本運(yùn)算次數(shù)還與問題的規(guī)模有關(guān)；對(duì)應(yīng)一個(gè)固定的規(guī)模，算法所執(zhí)行的基本運(yùn)算次數(shù)還可能與特定的輸入有關(guān)。2、下列敘述中正確的是()。A、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)會(huì)影響算法的效率B、算法設(shè)計(jì)只需考慮結(jié)果的可靠性C、算法復(fù)雜度是指算法控制結(jié)構(gòu)的復(fù)雜程度D、算法復(fù)雜度是用算法中指令的條數(shù)來度量的標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：采用不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。因此，在進(jìn)行數(shù)據(jù)處理時(shí)，選擇合適的存儲(chǔ)結(jié)構(gòu)很重要。3、設(shè)數(shù)據(jù)集合為D＝{1，2，3，4，5}。下列數(shù)據(jù)結(jié)構(gòu)B＝(D，R)中為非線性結(jié)構(gòu)的是()。A、R＝{(2，5)，(5，4)，(3，1)，(4，3)}B、R＝{(1，2)，(2，3)，(3，4)，(4，5)}C、R＝{(1，2)，(2，3)，(4，3)，(3，5)}D、R＝{(5，4)，(4，3)，(3，2)，(2，1)}標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：A項(xiàng)中，R＝｜(2，5)，(5，4)，(3，1)，(4，3)｜，2為根節(jié)點(diǎn)，元素順序?yàn)?→5→4→3→1，屬于線性結(jié)構(gòu)；同理B項(xiàng)1為根節(jié)點(diǎn)，元素順序?yàn)?→2→3→4→5，D項(xiàng)5為跟節(jié)點(diǎn)，元素順序?yàn)?→4→3→2→1。均為線性結(jié)構(gòu)。C項(xiàng)中，元素3有兩個(gè)前件，屬于非線性結(jié)構(gòu)。4、下列敘述中正確的是()。A、能采用順序存儲(chǔ)的必定是線性結(jié)構(gòu)B、所有的線性結(jié)構(gòu)都可以采用順序存儲(chǔ)結(jié)構(gòu)C、具有兩個(gè)以上指針的鏈表必定是非線性結(jié)構(gòu)D、循環(huán)隊(duì)列是隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：所有的線性結(jié)構(gòu)都可以用數(shù)組保存，即都可以采用順序存儲(chǔ)結(jié)構(gòu)。而反過來不可以，完全二叉樹也能用數(shù)組保存(按層次依次存放到數(shù)據(jù)元素中)，但完全二叉樹屬于非線性結(jié)構(gòu)。雙向鏈表具有兩個(gè)以上白勺指針，但屬于線性結(jié)構(gòu)。循環(huán)隊(duì)列是隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)。5、設(shè)棧的存儲(chǔ)空間為S(1：m)，初始狀態(tài)為top＝m＋1。經(jīng)過一系列入棧與退棧操作后，top＝1?，F(xiàn)又要將一個(gè)元素進(jìn)棧，棧頂指針top值變?yōu)?)。A、0B、發(fā)生棧滿的錯(cuò)誤C、mD、2標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：棧的初始狀態(tài)為top＝m＋1，說明棧空時(shí)top＝m＋1，入棧時(shí)棧頂指針是減操作(top＝top－1)，退棧時(shí)棧頂指針足加操作(top＝top＋1)。棧滿時(shí)top＝1，說明棧中不能再進(jìn)行入棧操作(“上溢”錯(cuò)誤)。6、下列處理中與隊(duì)列有關(guān)的是()。A、二叉樹的遍歷B、操作系統(tǒng)中的作業(yè)調(diào)度C、執(zhí)行程序中的過程調(diào)用D、執(zhí)行程序中的循環(huán)控制標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：隊(duì)列是指允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表。由于最先進(jìn)入隊(duì)列的元素將最先出隊(duì)，所以隊(duì)列具有“先進(jìn)先出”的特性，體現(xiàn)了“先來先服務(wù)”的原則。操作系統(tǒng)中的作業(yè)調(diào)度是指根據(jù)一定信息，按照一定的算法，從外存的后備隊(duì)列中選取某些作業(yè)調(diào)入內(nèi)存分配資源并將新創(chuàng)建的進(jìn)程插入就緒隊(duì)列的過程。7、循環(huán)隊(duì)列的存儲(chǔ)空間為Q(1：50)，初始狀態(tài)為front＝rear＝50。經(jīng)過一系列正常的入隊(duì)與退隊(duì)操作后，front＝rear＝25，此后又插入一個(gè)元素，則循環(huán)隊(duì)列中的元素個(gè)數(shù)為()。A、1，或50且產(chǎn)生上溢錯(cuò)誤B、51C、26D、2標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：在循環(huán)隊(duì)列運(yùn)轉(zhuǎn)起來后，當(dāng)front＝rear＝25時(shí)可知隊(duì)列空或者隊(duì)列滿，此后又插入了一個(gè)元素，如果之前隊(duì)列為空，插入操作之后隊(duì)列里只有一個(gè)元素；如果插入之前隊(duì)列已滿(50個(gè)元素)，執(zhí)行插入則會(huì)產(chǎn)生溢出錯(cuò)誤。8、設(shè)循環(huán)隊(duì)列的存儲(chǔ)空間為Q(1：50)，初始狀態(tài)為front＝rear＝50?，F(xiàn)經(jīng)過一系列入隊(duì)與退隊(duì)操作后，front＝rear＝1，此后又正常地插入了兩個(gè)元素。最后該隊(duì)列中的元素個(gè)數(shù)為()。A、3B、1C、2D、52標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：由初始狀態(tài)為front＝rear＝50可知此時(shí)循環(huán)隊(duì)列為空。經(jīng)過一系列正常的入隊(duì)和退隊(duì)操作，由front＝rear＝1可知隊(duì)列空或者隊(duì)列滿，此后又可以正常地插入了兩個(gè)元素，說明插入前隊(duì)列為空，則插入后隊(duì)列元素個(gè)數(shù)為2。9、在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，其存儲(chǔ)空間一般是不連續(xù)的，并且()。A、前件節(jié)點(diǎn)的存儲(chǔ)序號(hào)小于后件節(jié)點(diǎn)的存儲(chǔ)序號(hào)B、前件節(jié)點(diǎn)的存儲(chǔ)序號(hào)大于后件節(jié)點(diǎn)的存儲(chǔ)序號(hào)C、前件節(jié)點(diǎn)的存儲(chǔ)序號(hào)可以小于也可以大于后件節(jié)點(diǎn)的存儲(chǔ)序號(hào)D、以上三種說法均不正確標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，各數(shù)據(jù)節(jié)點(diǎn)的存儲(chǔ)序號(hào)是不連續(xù)的，并且各節(jié)點(diǎn)在存儲(chǔ)空間中的位置關(guān)系與邏輯關(guān)系也不一致，因此前件節(jié)點(diǎn)的存儲(chǔ)序號(hào)與后件節(jié)點(diǎn)的存儲(chǔ)序號(hào)之間不存在大小關(guān)系。10、下列結(jié)構(gòu)中屬于線性結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)的是()。A、雙向鏈表B、循環(huán)隊(duì)列C、二叉鏈表D、二維數(shù)組標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：雙向鏈表也叫雙鏈表，是鏈表(采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu))的一種，它的每個(gè)數(shù)據(jù)節(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)。循環(huán)隊(duì)列是隊(duì)列的一種順序存儲(chǔ)結(jié)構(gòu)。二叉鏈表和二維數(shù)組屬于非線性結(jié)構(gòu)。11、某帶鏈棧的初始狀態(tài)為top＝bottom＝NULL，經(jīng)過一系列正常的入棧與退棧操作后，top＝bottom＝20。該棧中的元素個(gè)數(shù)為()。A、0B、1C、20D、不確定標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：帶鏈的棧就是用一個(gè)單鏈表來表示的棧，棧中的每一個(gè)元素對(duì)應(yīng)鏈表中的一個(gè)節(jié)點(diǎn)。棧為空時(shí)，頭指針和尾指針都為NULL；棧中只有一個(gè)元素時(shí)，頭指針和尾指針都指向這個(gè)元素。12、從表中任何一個(gè)節(jié)點(diǎn)位置出發(fā)就可以不重復(fù)地訪問到表中其他所有節(jié)點(diǎn)的鏈表是()。A、循環(huán)鏈表B、雙向鏈表C、單向鏈表D、二叉鏈表標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：在循環(huán)鏈表中，所有節(jié)點(diǎn)的指針構(gòu)成了一個(gè)環(huán)狀鏈，只要指出表中任何一個(gè)節(jié)點(diǎn)的位置，就可以從它出發(fā)不重復(fù)地訪問到表中其他所有節(jié)點(diǎn)。13、某棵樹的度為4，且度為4、3、2、1的節(jié)點(diǎn)個(gè)數(shù)分別為1、2、3、4，則該樹中的葉子節(jié)點(diǎn)數(shù)為()。A、11B、9C、10D、8標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：根據(jù)樹中的節(jié)點(diǎn)數(shù)＝樹中所有節(jié)點(diǎn)的度之和＋1，設(shè)葉子節(jié)點(diǎn)數(shù)為n，得4×1＋3×2＋2×3＋1×4＋n×0＋1＝21，則n＝21－1－2－3－4＝11。14、某二叉樹共有845個(gè)節(jié)點(diǎn)，其中葉子節(jié)點(diǎn)有45個(gè)，則度為1的節(jié)點(diǎn)數(shù)為()。A、400B、754C、756D、不確定標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：葉子節(jié)點(diǎn)有45個(gè)，根據(jù)在二叉樹中度為0的節(jié)點(diǎn)(葉子節(jié)點(diǎn))總比度為2的節(jié)點(diǎn)多一個(gè)，則度為2的節(jié)點(diǎn)數(shù)為44個(gè)，因此度為1的節(jié)點(diǎn)數(shù)為845－45－44＝756個(gè)。15、某二叉樹的深度為7，其中有64個(gè)葉子節(jié)點(diǎn)，則該二叉樹中度為1的節(jié)點(diǎn)數(shù)為()。A、0B、1C、2D、63標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：葉子節(jié)點(diǎn)有64個(gè)，根據(jù)在二叉樹中度為0的節(jié)點(diǎn)(葉子節(jié)點(diǎn))總比度為2的節(jié)點(diǎn)多一個(gè)，則度為2的節(jié)點(diǎn)數(shù)為63個(gè)；又深度為m的二叉樹最多有2m－1個(gè)節(jié)點(diǎn)，則該二叉樹最多有27－1＝127個(gè)節(jié)點(diǎn)。64＋63＝127，因此該樹不存在度為1的節(jié)點(diǎn)。16、深度為7的二叉樹共有127個(gè)節(jié)點(diǎn)，則下列說法中錯(cuò)誤的是()。A、該二叉樹是滿二叉樹B、該二叉樹有一個(gè)度為1的節(jié)點(diǎn)C、該二叉樹是完全二叉樹D、該二叉樹有64個(gè)葉子節(jié)點(diǎn)標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：滿二叉樹滿足深度為m的二叉樹最多有2m－1個(gè)節(jié)點(diǎn)，本題中二叉樹深度為7且有127個(gè)節(jié)點(diǎn)，滿足27－1＝127，達(dá)到最大值，故此二叉樹為滿二叉樹，也是完全二叉樹。滿二叉樹第k層上有2k－1節(jié)點(diǎn)，則該二叉樹的葉子節(jié)點(diǎn)數(shù)為27－1＝64個(gè)。滿二叉樹不存在度為1的節(jié)點(diǎn)。17、下列數(shù)據(jù)結(jié)構(gòu)中為非線性結(jié)構(gòu)的是()。A、二叉鏈表B、循環(huán)隊(duì)列C、循環(huán)鏈表D、雙向鏈表標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也稱為二叉鏈表，二叉樹是樹的一種，屬于非線性結(jié)構(gòu)。18、設(shè)二叉樹的前序序列為ABDEGHCFIJ，中序序列為DBGEHACIFJ。則后序序列為()。A、JIHGFEDCBAB、DGHEBIJFCAC、GHIJDEFBCAD、ABCDEFGHIJ標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：二叉樹的前序序列為ABDEGHCFIJ，由于前序遍歷首先訪問根節(jié)點(diǎn)，可以確定該二叉樹的根節(jié)點(diǎn)是A。再由中序序列為DBGEHACIFJ，可以得到節(jié)點(diǎn)D、B、G、E、H位于根節(jié)點(diǎn)的左子樹上，節(jié)點(diǎn)C、I、F、J位于根節(jié)點(diǎn)的右子樹上。由于中序遍歷和后序遍歷都是先遍歷左子樹，故本題后序遍歷首先訪問D節(jié)點(diǎn)；再由后序遍歷是最后訪問根節(jié)點(diǎn)，故本題后序遍歷最后訪問的節(jié)點(diǎn)是根節(jié)點(diǎn)A。采用排除法可知，后續(xù)序列為DGHEBIJFCA。19、某完全二叉樹按層次輸出(同一層從左到右)的序列為ABCDEFGH。該完全二叉樹的前序序列為()。A、ABCDEFGHB、ABDHECFGC、HDBEAFCGD、HDEBFGCA標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：完全二叉樹的特點(diǎn)是除最后一層外，每一層上的節(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干節(jié)點(diǎn)。根據(jù)這一特點(diǎn)，再根據(jù)題意輸出序列為ABCDEFGH，可以得到該二叉樹的結(jié)構(gòu)如下：故此完全二叉樹的前序序列為ABDHECFG。20、設(shè)表的長度為n。下列查找算法中，在最壞情況下，比較次數(shù)最少的是()。A、順序查找B、尋找最大項(xiàng)C、尋找最小項(xiàng)D、有序表的二分查找標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：在最壞情況下的比較次數(shù)：順序查找為n，尋找最大項(xiàng)和最小項(xiàng)均為n－1，有序表的二分查找為log2n。21、下列算法中均以比較作為基本運(yùn)算，則平均情況與最壞情況下的時(shí)間復(fù)雜度相同的是()。A、在順序存儲(chǔ)的線性表中尋找最大項(xiàng)B、在順序存儲(chǔ)的線性表中進(jìn)行順序查找C、在順序存儲(chǔ)的有序表中進(jìn)行對(duì)分查找D、在鏈?zhǔn)酱鎯?chǔ)的有序表中進(jìn)行查找標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：尋找最大項(xiàng)，無論如何都要查看所有的數(shù)據(jù)，與數(shù)據(jù)原始排列順序沒有多大關(guān)系，無所謂最壞情況和最好情況，或者說平均情況與最壞情況下的時(shí)間復(fù)雜度是相同的。而查找無論是對(duì)分查找還是順序查找，都與要找的數(shù)據(jù)和原始的數(shù)據(jù)排列情況有關(guān)，最好情況是第1次查看的一個(gè)數(shù)據(jù)恰好是要找的數(shù)據(jù)，只需要比較1次；如果沒有找到再查看下一個(gè)數(shù)據(jù)，直到找到為止，最壞情況下是最后一次查看的數(shù)據(jù)才是要找的，順序查找和對(duì)分查找在最壞情況下比較次數(shù)分別是n和log2n，平均情況則是“1－最壞情況”的平均，因而是不同的。22、設(shè)順序表的長度為n。下列算法中，最壞情況下比較次數(shù)等于n(n－1)/2的是()。A、快速排序B、堆排序C、順序查找D、尋找最大項(xiàng)標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：對(duì)于長度為n的線性表，最壞情況下查找或排序的次數(shù)如下表：23、下列序列中不滿足堆條件的是()。A、(98，95，93，94，89，90，76，80，55，49)B、(98，95，93，94，89，85，76，64，55，49)C、(98，95，93，94，89，90，76，64，55，49)D、(98，95，93，96，89，85，76，64，55，49)標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：根據(jù)堆的定義，n個(gè)元素的序列(h1，h1，…，hn)，當(dāng)且僅當(dāng)hi≤h2i且hi≤h2i＋1時(shí)為小頂堆，當(dāng)且僅當(dāng)hi≥h2i且hi≥h2i＋1時(shí)為大頂堆。D項(xiàng)中，h2＝95，h4＝96，h2＜h4，但h5＝89，h2＞h5，不滿足小頂堆和大頂堆條件。國家二級(jí)MSOffice高級(jí)應(yīng)用機(jī)試（數(shù)據(jù)結(jié)構(gòu)與算法）模擬試卷第2套一、選擇題(本題共27題，每題1.0分，共27分。)1、在長度為n的有序線性表中進(jìn)行二分查找，最壞情況下需要比較的次數(shù)是A、O(n)B、O(n2)C、O(log2n)D、O(nlog2n)標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：對(duì)于長度為n的有序線性表，在最壞情況下，二分法查找只需比較log2n次，而順序查找需要比較n次。2、算法的有窮性是指A、算法程序的運(yùn)行時(shí)間是有限的B、算法程序所處理的數(shù)據(jù)量是有限的C、算法程序的長度是有限的D、算法只能被有限的用戶使用標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：算法的有窮性，是指算法必須能在有限的時(shí)間內(nèi)做完，即算法必須能在執(zhí)行有限個(gè)步驟之后終止。3、算法的時(shí)間復(fù)雜度是指A、設(shè)計(jì)該算法所需的工作量B、執(zhí)行該算法所需要的時(shí)間C、執(zhí)行該算法時(shí)所需要的基本運(yùn)算次數(shù)D、算法中指令的條數(shù)標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：算法的時(shí)間復(fù)雜度，是指執(zhí)行算法所需要的計(jì)算工作量。算法的工作量可以用算法在執(zhí)行過程中所需基本運(yùn)算的執(zhí)行次數(shù)來度量。4、下列關(guān)于二叉樹的敘述中，正確的是A、葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)少一個(gè)B、葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多一個(gè)C、葉子結(jié)點(diǎn)數(shù)是度為2的結(jié)點(diǎn)數(shù)的兩倍D、度為2的結(jié)點(diǎn)數(shù)是度為1的結(jié)點(diǎn)數(shù)的兩倍標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：由二叉樹的性質(zhì)可以知道在二叉樹中葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多一個(gè)。5、設(shè)循環(huán)隊(duì)列的存儲(chǔ)空間為Q(1：35)，初始狀態(tài)為front=rear=35?，F(xiàn)經(jīng)過一系列入隊(duì)與退隊(duì)運(yùn)算后，front=15，rear=15，則循環(huán)隊(duì)列中的元素個(gè)數(shù)為A、15B、16C、20D、0或35標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：循環(huán)隊(duì)列的隊(duì)頭指針和尾指針都等于15，此循環(huán)隊(duì)列中元素的個(gè)數(shù)有兩種情況，第一種情況是隊(duì)頭指針和尾指針都是第一次到達(dá)15，此時(shí)元素個(gè)數(shù)為0；第二種情況是隊(duì)頭指針第一次到達(dá)15，而尾指針第二次到達(dá)15，此時(shí)元素個(gè)數(shù)為35。6、下列敘述中正確的是A、一個(gè)算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度也必定大B、一個(gè)算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度必定小C、一個(gè)算法的時(shí)間復(fù)雜度大，則其空間復(fù)雜度必定小D、算法的時(shí)間復(fù)雜度與空間復(fù)雜度沒有直接關(guān)系標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：算法的復(fù)雜度主要包括時(shí)間復(fù)雜度和空間復(fù)雜度。算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量，算法的工作量用算法所執(zhí)行的基本運(yùn)算次數(shù)來度量，而算法所執(zhí)行的基本運(yùn)算次數(shù)是問題規(guī)模的函數(shù)，即算法的工作量=f(n)，其中n是問題的規(guī)模；算法的空間復(fù)雜度，一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。一個(gè)算法所占用的存儲(chǔ)空間包括算法程序所占用的空間、輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間以及算法執(zhí)行過程中所需要的額外空間。根據(jù)各自的定義可知，算法的時(shí)間復(fù)雜度與空間復(fù)雜度并不相關(guān)。7、對(duì)長度為n的線性表作快速排序，在最壞情況下，比較次數(shù)為A、nB、n－1C、n(n－1)D、n(n－1)／2標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：假設(shè)線性表的長度為n，則在最壞情況下，冒泡排序需要經(jīng)過n／2遍的從前往后的掃描和n／2遍的從后往前的掃描，需要的比較次數(shù)為n(n-1)／2?？焖倥判蚍ㄒ彩且环N互換類的排序方法，但由于它比冒泡排序法的速度快，因此，稱為快速排序法。8、下列排序方法中，最壞情況下時(shí)間復(fù)雜度最小的是A、冒泡排序B、快速排序C、堆排序D、直接插入排序標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：排序方法中最壞情況下時(shí)間復(fù)雜度的大小如下表，根據(jù)下表可知選項(xiàng)C正確。9、在深度為7的滿二叉樹中，度為2的結(jié)點(diǎn)個(gè)數(shù)為A、64B、63C、32D、31標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：因?yàn)樵谌我獾亩鏄渲校葹?的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總比度為2的結(jié)點(diǎn)的個(gè)數(shù)多1個(gè)，而度為0的結(jié)點(diǎn)數(shù)n0=2m-1(其中m為二叉樹的深度)。本題的度為0的結(jié)點(diǎn)個(gè)數(shù)n0=27-1=26=64。因此，度為2的結(jié)點(diǎn)數(shù)n2=n0-1=63。所以選項(xiàng)B正確。10、設(shè)棧的順序存儲(chǔ)空間為S(0：49)，棧底指針bottom=49，棧頂指針top=30(指向棧頂元素)。則棧中的元素個(gè)數(shù)為A、30B、29C、20D、19標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：在操作系統(tǒng)中，棧是向下生長的，如下圖如示。所以，當(dāng)棧底指針bottom=49，棧頂指針top=30時(shí)，棧中的元素個(gè)數(shù)為：棧底-棧頂+1=49-30+1=20。因此選項(xiàng)C正確。11、下列敘述中錯(cuò)誤的是A、在帶鏈隊(duì)列中，隊(duì)頭指針和隊(duì)尾指針都是在動(dòng)態(tài)變化的B、在帶鏈棧中，棧頂指針和棧底指針都是在動(dòng)態(tài)變化的C、在帶鏈棧中，棧頂指針是在動(dòng)態(tài)變化的，但棧底指針是不變的D、以上三項(xiàng)都錯(cuò)誤標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：棧是只在一端進(jìn)行增加和刪除的線性表，進(jìn)行操作的那端稱為棧頂，另一端稱為棧底。所以在帶鏈棧中，棧頂指針是在動(dòng)態(tài)變化的，但棧底指針是不變的，選項(xiàng)C的說法正確，選項(xiàng)B的說法是錯(cuò)誤的。隊(duì)列是允許在隊(duì)列的頭和尾都可以進(jìn)行操作的線性表，所以在帶鏈隊(duì)列中，隊(duì)頭指針和隊(duì)尾指針都是在動(dòng)態(tài)變化的選項(xiàng)A這一說法是正確的。12、深度為5的完全二叉樹的結(jié)點(diǎn)數(shù)不可能是A、15B、16C、17D、18標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：對(duì)于滿二叉樹，葉子結(jié)點(diǎn)的數(shù)目等于2(n-1)為深度，這里就是2的5-1=4次方，就是16。所以選項(xiàng)A為正確答案。13、深度為7的完全二叉樹中共有125個(gè)結(jié)點(diǎn)，則該完全二叉樹中的葉子結(jié)點(diǎn)數(shù)為A、62B、63C、64D、65標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：對(duì)于滿二叉樹，結(jié)點(diǎn)的數(shù)目等于2n-1，葉子結(jié)點(diǎn)數(shù)目為2n-1，n為深度，這里就是2的7次方-1，就是127個(gè)結(jié)點(diǎn)，葉子結(jié)點(diǎn)是64個(gè)。然而題目中只有125個(gè)結(jié)點(diǎn)，說明少了兩個(gè)結(jié)點(diǎn)，那么就少了一個(gè)葉子結(jié)點(diǎn)，即63個(gè)。14、下列敘述中正確的是A、算法的時(shí)間復(fù)雜度與運(yùn)行算法時(shí)特定的輸入有關(guān)B、算法的時(shí)間復(fù)雜度與計(jì)算機(jī)的運(yùn)行速度有關(guān)C、算法的時(shí)間復(fù)雜度與算法程序中的語句條數(shù)成正比D、算法的時(shí)間復(fù)雜度與算法程序編制者的水平有關(guān)標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：算法的時(shí)間復(fù)雜度，是指執(zhí)行算法所需要的計(jì)算工作量，算法的工作量用算法所執(zhí)行的基本運(yùn)行次數(shù)來度量，所以與運(yùn)行算法時(shí)特定的輸入有關(guān)，選項(xiàng)A正確。15、循環(huán)隊(duì)列的存儲(chǔ)空間為Q(1：50)，初始狀態(tài)為front=rear=50。經(jīng)過一系列正常的入隊(duì)與退隊(duì)操作后，front=rear=25，此后又插入一個(gè)元素，則循環(huán)隊(duì)列中的元素個(gè)數(shù)為A、1，或50且產(chǎn)生上溢錯(cuò)誤B、51C、26D、2標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：循環(huán)隊(duì)列初始狀態(tài)front=rear=50，經(jīng)過一系列入隊(duì)和出隊(duì)操作后，結(jié)束狀態(tài)還是front=rear=25，這說明入隊(duì)元素個(gè)數(shù)和出隊(duì)元素個(gè)數(shù)一樣多。這樣一來最后的元素個(gè)數(shù)就和原來的元素個(gè)數(shù)一樣多，明顯不是0就是50，即要么隊(duì)空(0個(gè)元素)，要么隊(duì)滿(50個(gè)元素)。這時(shí)進(jìn)行入隊(duì)操作，如果是隊(duì)空(0個(gè)元素)的情況，此時(shí)元素個(gè)數(shù)為1；如果是隊(duì)滿(50個(gè)元素)的情況，就會(huì)產(chǎn)生上溢錯(cuò)誤。16、設(shè)棧的存儲(chǔ)空間為S(1：60)，初始狀態(tài)為top=61?，F(xiàn)經(jīng)過一系列正常的入棧與退棧操作后，top=1，則棧中的元素個(gè)數(shù)為A、60B、59C、0D、1標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：棧是向上增長的，每次壓入一個(gè)元素，棧的TOP指針向上移動(dòng)一位，即top－1。當(dāng)壓入第一個(gè)元素時(shí)，TOP指針指向60+1－1=60；當(dāng)壓入第二個(gè)元素時(shí)，TOP指針指向60+1－2=59；……；以此類推，當(dāng)壓入第N個(gè)元素時(shí)，TOP指針指向60+1－N=1，則N=60。所以選項(xiàng)A正確。17、下列敘述中錯(cuò)誤的是A、循環(huán)鏈表是循環(huán)隊(duì)列的存儲(chǔ)結(jié)構(gòu)B、二叉鏈表是二叉樹的存儲(chǔ)結(jié)構(gòu)C、棧是線性結(jié)構(gòu)D、循環(huán)隊(duì)列是隊(duì)列的存儲(chǔ)結(jié)構(gòu)標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：循環(huán)隊(duì)列屬于邏輯結(jié)構(gòu)，其實(shí)質(zhì)還是順序存儲(chǔ)，只是使用指針進(jìn)行首尾的聯(lián)結(jié)，其實(shí)現(xiàn)的存儲(chǔ)方式可分為：分散的鏈表和連續(xù)的線性表，與其邏輯結(jié)構(gòu)實(shí)現(xiàn)功能無關(guān)。所以選項(xiàng)A正確。18、設(shè)棧的順序存儲(chǔ)空間為S(1：m)，初始狀態(tài)為top=0?，F(xiàn)經(jīng)過一系列正常的入棧與退棧操作后，top=m+1，則棧中的元素個(gè)數(shù)為A、不可能B、m+1C、0D、m標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：棧是向上增長的，每次壓入一個(gè)元素，棧的TOP指針向上移動(dòng)一位，即top－1。對(duì)于這個(gè)題目，由于top初始值等于0，此時(shí)入棧一個(gè)元素，top值減1，即0－1=－1，出現(xiàn)下溢錯(cuò)誤，所以選項(xiàng)A正確。19、某完全二叉樹按層次輸出(同一層從左到右)的序列為ABCDEFGH。該完全二叉樹的前序序列為A、ABDHECFGB、ABCDEFGHC、HDBEAFCGD、HDEBFGCA標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：完全二叉樹的特點(diǎn)是除最后一層外，每一層上的節(jié)點(diǎn)數(shù)均達(dá)到最大值：在最后一層上只缺少右邊的若干結(jié)點(diǎn)。根據(jù)上述的特點(diǎn)，完全二叉樹按層次輸出(同一層從左到右)的序列為ABCDEFGH，可以得到其結(jié)構(gòu)如下，所以此完全二叉樹的前序序列是ABDHECFG，選項(xiàng)A正確。20、設(shè)循環(huán)隊(duì)列的存儲(chǔ)空間為Q(1：100)，初始狀態(tài)為空?，F(xiàn)經(jīng)過一系列正常操作后，front=49，則循環(huán)隊(duì)列中的元素個(gè)數(shù)為A、不確定B、49C、51D、50標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：循環(huán)隊(duì)列用數(shù)組Q[1：100]存放其元素值，已知其頭尾指針分別是front和rear，則當(dāng)前隊(duì)列的元素個(gè)數(shù)是(rear－front+100)％100，題目中首指針rear的值未知，所以循環(huán)隊(duì)列中的元素個(gè)數(shù)不能確定。所以選項(xiàng)A正確。21、設(shè)表的長度為20。則在最壞情況下，冒泡排序的比較次數(shù)為A、90B、20C、19D、190標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：假設(shè)線性表的長度為n，則在最壞情況下，冒泡排序的比較次數(shù)為n(n－1)／2。本題中，n=20，所以20*19／2=190。所以選項(xiàng)D正確。22、下列數(shù)據(jù)結(jié)構(gòu)中，不能采用順序存儲(chǔ)結(jié)構(gòu)的是A、棧B、堆C、隊(duì)列D、非完全二叉樹標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：堆中某個(gè)結(jié)點(diǎn)的值總是不大于或不小于其父結(jié)點(diǎn)的值、堆總是一棵完全二叉樹，可以以順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)；隊(duì)列的存儲(chǔ)結(jié)構(gòu)分為鏈?zhǔn)酱鎯?chǔ)、順序存儲(chǔ)兩種；棧作為一種數(shù)據(jù)結(jié)構(gòu)，是一種只能在一端進(jìn)行插入和刪除操作的特殊線性表，可以以順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。23、設(shè)一棵樹的度為3，其中沒有度為2的結(jié)點(diǎn)，且葉子結(jié)點(diǎn)數(shù)為6。該樹中度為3的結(jié)點(diǎn)數(shù)為A、1B、2C、3D、不可能有這樣的樹標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：樹的度是指一棵樹中，最大的結(jié)點(diǎn)的度稱為樹的度。本題中樹的度為3，也就是最少有一個(gè)度為3的結(jié)點(diǎn)。要求沒有度為2的結(jié)點(diǎn)，且葉子結(jié)點(diǎn)為6，如果要有度為3的結(jié)點(diǎn)，那么最多只有5個(gè)葉子結(jié)點(diǎn)，而畫不出6個(gè)葉子結(jié)點(diǎn)。因此這樣的樹是沒有的。24、度為3的一棵樹共有30個(gè)結(jié)點(diǎn)，其中度為3、1的結(jié)點(diǎn)個(gè)數(shù)分別為3、4。則該樹中的葉子結(jié)點(diǎn)數(shù)為A、14B、15C、16D、不可能有這樣的樹標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：根據(jù)題目可知本樹中還有度為2的結(jié)點(diǎn)。樹的總結(jié)點(diǎn)=(度1*個(gè)數(shù)+度2*個(gè)數(shù)…)+1，這里我們?cè)O(shè)度為2的結(jié)點(diǎn)數(shù)為x，那么30=3*3+2*x+1*4+1=2*x+14，由此可計(jì)算出x=8。樹的葉子結(jié)點(diǎn)數(shù)等于總結(jié)點(diǎn)減去所有度不為0的結(jié)點(diǎn)，也就是30－3－8－4=15。25、在快速排序法中，每經(jīng)過一次數(shù)據(jù)交換(或移動(dòng))后A、能消除多個(gè)逆序B、只能消除一個(gè)逆序C、不會(huì)產(chǎn)生新的逆序D、消除的逆序個(gè)數(shù)一定比新產(chǎn)生的逆序個(gè)數(shù)多標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。26、下列敘述中正確的是A、算法的復(fù)雜度是指算法所處理的數(shù)據(jù)量B、算法的復(fù)雜度是指算法程序中指令的數(shù)量C、算法的復(fù)雜度是指算法控制結(jié)構(gòu)的復(fù)雜程度D、算法的復(fù)雜度包括時(shí)間復(fù)雜度與空間復(fù)雜度標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：算法分析的目的在于選擇合適算法和改進(jìn)算法。一個(gè)算法的評(píng)價(jià)主要從時(shí)間復(fù)雜度和空間復(fù)雜度來考慮。27、設(shè)順序表的長度為16，對(duì)該表進(jìn)行簡單插入排序。在最壞情況下需要的比較次數(shù)為A、15B、30C、60D、120標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：插入排序的基本思想是：每步將一個(gè)待排序的記錄，按其關(guān)鍵碼值的大小插入前面已經(jīng)排序的文件中適當(dāng)位置上，直到全部插入完為止。最壞情況計(jì)算方法(n*(n－1))／2=16*15／2=120。國家二級(jí)MSOffice高級(jí)應(yīng)用機(jī)試（數(shù)據(jù)結(jié)構(gòu)與算法）模擬試卷第3套一、選擇題(本題共28題，每題1.0分，共28分。)1、下列敘述中正確的是()。A、所謂算法就是計(jì)算方法B、程序可以作為算法的一種描述方法C、算法設(shè)計(jì)只需考慮得到計(jì)算結(jié)果D、算法設(shè)計(jì)可以忽略算法的運(yùn)算時(shí)間標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：算法是指對(duì)解題方案的準(zhǔn)確而完整的描述，算法不等于數(shù)學(xué)上的計(jì)算方法，也不等于程序。算法設(shè)計(jì)需要考慮可行性、確定性、有窮性與足夠的情報(bào)，不能只考慮計(jì)算結(jié)果。算法設(shè)計(jì)有窮性是指操作步驟有限且能在有限時(shí)間內(nèi)完成，如果一個(gè)算法執(zhí)行耗費(fèi)的時(shí)間太長，即使最終得出了正確結(jié)果，也是沒有意義的。算法在實(shí)現(xiàn)時(shí)需要用具體的程序設(shè)計(jì)語言描述，所以程序可以作為算法的一種描述方法。2、下列敘述中正確的是()。A、算法的時(shí)間復(fù)雜度與計(jì)算機(jī)的運(yùn)行速度有關(guān)B、算法的時(shí)間復(fù)雜度與運(yùn)行算法時(shí)特定的輸入有關(guān)C、算法的時(shí)間復(fù)雜度與算法程序中的語句條數(shù)成正比D、算法的時(shí)間復(fù)雜度與算法程序編制者的水平有關(guān)標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：為了能夠比較客觀地反映出一個(gè)算法的效率，在度量一個(gè)算法的工作量時(shí)，不僅應(yīng)該與所使用的計(jì)算機(jī)、程序設(shè)計(jì)語言以及程序編制者無關(guān)，而且還應(yīng)該與算法實(shí)現(xiàn)過程中的許多細(xì)節(jié)無關(guān)。為此，可以用算法在執(zhí)行過程中所需基本運(yùn)算的執(zhí)行次數(shù)來度量算法的工作量。算法所執(zhí)行的基本運(yùn)算次數(shù)還與問題的規(guī)模有關(guān)；對(duì)應(yīng)一個(gè)固定的規(guī)模，算法所執(zhí)行的基本運(yùn)算次數(shù)還可能與特定的輸入有關(guān)。3、為了降低算法的空間復(fù)雜度，要求算法盡量采用原地工作(inplace)。所謂原地工作是指()A、執(zhí)行算法時(shí)不使用額外空間B、執(zhí)行算法時(shí)不使用任何存儲(chǔ)空間C、執(zhí)行算法時(shí)所使用的額外空間隨算法所處理的數(shù)據(jù)空間大小的變化而變化D、執(zhí)行算法時(shí)所使用的額外空間固定(即不隨算法所處理的數(shù)據(jù)空間大小的變化而變化)標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：對(duì)于算法的空間復(fù)雜度，如果額外空間量相對(duì)于問題規(guī)模(即輸入數(shù)據(jù)所占的存儲(chǔ)空間)來說是常數(shù)，即額外空間量不隨問題規(guī)模的變化而變化，則稱該算法是原地工作的。4、設(shè)數(shù)據(jù)結(jié)構(gòu)B=(D，R)，其中D={a，b，c，d，e，f}R={(f，a)，(d，b)，(e，d)，(c，e)，(a，c)}該數(shù)據(jù)結(jié)構(gòu)為()。A、線性結(jié)構(gòu)B、循環(huán)隊(duì)列C、循環(huán)鏈表D、非線性結(jié)構(gòu)標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個(gè)要素：一是數(shù)據(jù)元素的集合，通常記為D；二是D上的關(guān)系，它反映了D中各數(shù)據(jù)元素之間的前后件關(guān)系，通常記為R。即一個(gè)數(shù)據(jù)結(jié)構(gòu)可以表示成B=(D，R)。其中B表示數(shù)據(jù)結(jié)構(gòu)。為了反映D中各數(shù)據(jù)元素之間的前后件關(guān)系，一般用二元組來表示。例如，假設(shè)a與b是D中的兩個(gè)數(shù)據(jù)，則二元組(a，b)表示a是b的前件，b是a的后件。本題中R中的根節(jié)點(diǎn)為f，元素順序?yàn)閒→a→c→e→d→b，滿足線性結(jié)構(gòu)的條件。5、在線性表的順序存儲(chǔ)結(jié)構(gòu)中，其存儲(chǔ)空間連續(xù)，各個(gè)元素所占的字節(jié)數(shù)()。A、不同，但元素的存儲(chǔ)順序與邏輯順序一致B、不同，且其元素的存儲(chǔ)順序可以與邏輯順序不一致C、相同，元素的存儲(chǔ)順序與邏輯順序一致D、相同，但其元素的存儲(chǔ)順序可以與邏輯順序不一致標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：在線性表的順序存儲(chǔ)結(jié)構(gòu)中，其存儲(chǔ)空間連續(xù)，各個(gè)元素所占的字節(jié)數(shù)相同，在存儲(chǔ)空間中是按邏輯順序依次存放的。6、下列敘述中正確的是()。A、在棧中，棧頂指針的動(dòng)態(tài)變化決定棧中元素的個(gè)數(shù)B、在循環(huán)隊(duì)列中，隊(duì)尾指針的動(dòng)態(tài)變化決定隊(duì)列的長度C、在循環(huán)鏈表中，頭指針和鏈尾指針的動(dòng)態(tài)變化決定鏈表的長度D、在線性鏈表中，頭指針和鏈尾指針的動(dòng)態(tài)變化決定鏈表的長度標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：在棧中，通常用指針top來指示棧頂?shù)奈恢?，用指針bottom指向棧底。棧頂指針top動(dòng)態(tài)反映了棧中元素的變化情況。在循環(huán)隊(duì)列中，隊(duì)頭指針和隊(duì)尾指針的動(dòng)態(tài)變化決定隊(duì)列的長度。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，各數(shù)據(jù)節(jié)點(diǎn)的存儲(chǔ)序號(hào)是不連續(xù)的，并且各節(jié)點(diǎn)在存儲(chǔ)空間中的位置關(guān)系與邏輯關(guān)系也不一致，故頭指針和尾指針或棧頂指針無法決定鏈表長度。7、設(shè)棧的存儲(chǔ)空間為S(1：m)，初始狀態(tài)為top=m+1。經(jīng)過一系列入棧與退棧操作后，top=m。現(xiàn)又在棧中退出一個(gè)元素后，棧頂指針top值為()。A、0B、m－1C、m+1D、產(chǎn)生棧空錯(cuò)誤標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：棧的順序存儲(chǔ)空間為S(1：m)，初始狀態(tài)top=m+1，所以這個(gè)棧是m在棧底(也可理解為開口向下的棧)。經(jīng)過一系列入棧與退棧操作后top=m，則棧中有1個(gè)元素，若現(xiàn)在又退出一個(gè)元素，那么棧頂指針下移一位，回到m+1的位置。8、下列處理中與隊(duì)列有關(guān)的是()。A、二叉樹的遍歷B、操作系統(tǒng)中的作業(yè)調(diào)度C、執(zhí)行程序中的過程調(diào)用D、執(zhí)行程序中的循環(huán)控制標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：隊(duì)列是指允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表。由于最先進(jìn)入隊(duì)列的元素將最先出隊(duì)，所以隊(duì)列具有“先進(jìn)先出”的特性，體現(xiàn)了“先來先服務(wù)”的原則。操作系統(tǒng)中的作業(yè)調(diào)度是指根據(jù)一定信息，按照一定的算法，從外存的后備隊(duì)列中選取某些作業(yè)調(diào)入內(nèi)存分配資源并將新創(chuàng)建的進(jìn)程插入就緒隊(duì)列的過程。9、下列敘述中正確的是()。A、循環(huán)隊(duì)列是順序存儲(chǔ)結(jié)構(gòu)B、循環(huán)隊(duì)列是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C、循環(huán)隊(duì)列空的條件是隊(duì)頭指針與隊(duì)尾指針相同D、循環(huán)隊(duì)列的插入運(yùn)算不會(huì)發(fā)生溢出現(xiàn)象標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：循環(huán)隊(duì)列是隊(duì)列的一種順序存儲(chǔ)結(jié)構(gòu)。在循環(huán)隊(duì)列中，在隊(duì)列滿和隊(duì)列為空時(shí)，隊(duì)頭指針與隊(duì)尾指針均相同；當(dāng)需要插入的數(shù)據(jù)大于循環(huán)隊(duì)列的存儲(chǔ)長度，入隊(duì)運(yùn)算會(huì)覆蓋前面的數(shù)據(jù)，發(fā)生溢出現(xiàn)象。10、循環(huán)隊(duì)列的存儲(chǔ)空間為Q(1：40)，初始狀態(tài)為front=rear=40。經(jīng)過一系列正常的入隊(duì)與退隊(duì)操作后，front=rear=15，此后又退出一個(gè)元素，則循環(huán)隊(duì)列中的元素個(gè)數(shù)為()。A、14B、15C、40D、39，或0且產(chǎn)生下溢錯(cuò)誤標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：當(dāng)front=rear=15時(shí)可知隊(duì)列空或者隊(duì)列滿，此后又退出一個(gè)元素，如果之前隊(duì)列為空，退出操作會(huì)產(chǎn)生錯(cuò)誤，隊(duì)列里有0個(gè)元素；如果退出之前隊(duì)列已滿(40個(gè)元素)，執(zhí)行退出后，隊(duì)列里還有39個(gè)元素。11、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)相比，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)有()。A、節(jié)省存儲(chǔ)空間B、插入與刪除運(yùn)算效率高C、便于查找D、排序時(shí)減少元素的比較次數(shù)標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：線性表的順序存儲(chǔ)結(jié)構(gòu)稱為順序表，線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈表，兩者的優(yōu)缺點(diǎn)如下表所示。12、下列敘述中正確的是()。A、節(jié)點(diǎn)中具有兩個(gè)指針域的鏈表一定是二叉鏈表B、節(jié)點(diǎn)中具有兩個(gè)指針域的鏈表可以是線性結(jié)構(gòu)，也可以是非線性結(jié)構(gòu)C、循環(huán)鏈表是循環(huán)隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D、循環(huán)鏈表是非線性結(jié)構(gòu)標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：節(jié)點(diǎn)中具有兩個(gè)指針域的鏈表既可以是雙向鏈表也可以是二叉鏈表，雙向鏈表是線性結(jié)構(gòu)，二叉鏈表屬于非線性結(jié)構(gòu)。循環(huán)鏈表是線性鏈表的一種形式，屬于線性結(jié)構(gòu)，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，而循環(huán)隊(duì)列是隊(duì)列的一種順序存儲(chǔ)結(jié)構(gòu)。13、下列敘述中正確的是()。A、帶鏈棧的棧底指針是隨棧的操作而動(dòng)態(tài)變化的B、若帶鏈隊(duì)列的隊(duì)頭指針與隊(duì)尾指針相同，則隊(duì)列為空C、若帶鏈隊(duì)列的隊(duì)頭指針與隊(duì)尾指針相同，則隊(duì)列中至少有一個(gè)元素D、不管是順序棧還是帶鏈的棧，在操作過程中其棧底指針均是固定不變的標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：由于帶鏈棧利用的是計(jì)算機(jī)存儲(chǔ)空間中的所有空閑存儲(chǔ)節(jié)點(diǎn)，因此隨棧的操作棧頂棧底指針動(dòng)態(tài)變化。帶鏈的隊(duì)列中若只有一個(gè)元素，則頭指針與尾指針相同。14、某帶鏈棧的初始狀態(tài)為top=bottom=NULL，經(jīng)過一系列正常的入棧與退棧操作后，top=10，bottom=20。該棧中的元素個(gè)數(shù)為()。A、0B、1C、10D、不確定標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：帶鏈的棧使用了鏈表來表示棧，而鏈表中的元素存儲(chǔ)在不連續(xù)的地址中，因此當(dāng)top=10，bottom=20時(shí)，不能確定棧中元素的個(gè)數(shù)。15、某帶鏈的隊(duì)列初始狀態(tài)為front=rear=NULL。經(jīng)過一系列正常的人隊(duì)與退隊(duì)操作后，front=10，rear=5。該隊(duì)列中的元素個(gè)數(shù)為()。A、4B、5C、6D、不確定標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：帶鏈的隊(duì)列使用了鏈表來表示隊(duì)列，而鏈表中的元素存儲(chǔ)在不連續(xù)的地址中，因此當(dāng)front=10，rear=5時(shí)，不能確定隊(duì)列中元素的個(gè)數(shù)。16、某棵樹中共有25個(gè)節(jié)點(diǎn)，且只有度為3的節(jié)點(diǎn)和葉子節(jié)點(diǎn)，其中葉子節(jié)點(diǎn)有7個(gè)，則該樹中度為3的節(jié)點(diǎn)數(shù)為()。A、6B、7C、8D、不存在這樣的樹標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：根據(jù)題意，樹中只有度為3的節(jié)點(diǎn)和葉子節(jié)點(diǎn)(7個(gè))，則度為3的節(jié)點(diǎn)有25－7=18個(gè)；又根據(jù)樹中的節(jié)點(diǎn)數(shù)=樹中所有節(jié)點(diǎn)的度之和+l，設(shè)度為3的節(jié)點(diǎn)數(shù)為n，則3n+1=25，得n=8。兩種方式得到的度為3的節(jié)點(diǎn)數(shù)不同，故不存在這樣的樹。17、深度為7的二叉樹共有127個(gè)節(jié)點(diǎn)，則下列說法中錯(cuò)誤的是()。A、該二叉樹是滿二叉樹B、該二叉樹有一個(gè)度為l的節(jié)點(diǎn)C、該二叉樹是完全二叉樹D、該二叉樹有64個(gè)葉子節(jié)點(diǎn)標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：滿二叉樹滿足深度為m的二叉樹最多有2m－1個(gè)節(jié)點(diǎn)，本題中二叉樹深度為7且有127個(gè)節(jié)點(diǎn)，滿足27－1=127，達(dá)到最大值，故此二叉樹為滿二叉樹，也是完全二叉樹。滿二叉樹第k層上有2k－1節(jié)點(diǎn)，則該二叉樹的葉子節(jié)點(diǎn)數(shù)為27－1=64個(gè)。滿二叉樹不存在度為1的節(jié)點(diǎn)。18、某完全二叉樹共有256個(gè)節(jié)點(diǎn)，則該完全二叉樹的深度為()。A、7B、8C、9D、10標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：根據(jù)完全二叉樹的性質(zhì)：具有n個(gè)節(jié)點(diǎn)的完全二叉樹的深度為[log2n]+1。本題中完全二叉樹共有256個(gè)節(jié)點(diǎn)，則深度為[log2256]+1=8+1=9。19、下列敘述中正確的是()。A、非完全二叉樹可以采用順序存儲(chǔ)結(jié)構(gòu)B、有兩個(gè)指針域的鏈表就是二叉鏈表C、有的二叉樹也能用順序存儲(chǔ)結(jié)構(gòu)表示D、順序存儲(chǔ)結(jié)構(gòu)一定是線性結(jié)構(gòu)標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：在計(jì)算機(jī)中，二叉樹為非線性結(jié)構(gòu)，通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，但對(duì)于滿二叉樹和完全二叉樹來說，可以按層進(jìn)行順序存儲(chǔ)。因此A項(xiàng)錯(cuò)誤，C項(xiàng)正確。雖然滿二叉樹和完全二叉樹可以采用順序存儲(chǔ)結(jié)構(gòu)，但仍是一種非線性結(jié)構(gòu)，因此D項(xiàng)錯(cuò)誤。雙向鏈表也有兩個(gè)指針域，因此B項(xiàng)錯(cuò)誤。20、設(shè)二叉樹的前序序列為ABDEGHCFH，中序序列為DBGEHACIFJ。則后序序列為()。A、JIHGFEDCBAB、DGHEBIJFCAC、GHIJDEFBCAD、ABCDEFGHU標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：二叉樹的前序序列為ABDEGHCFIJ，由于前序遍歷首先訪問根節(jié)點(diǎn)，可以確定該二叉樹的根節(jié)點(diǎn)是A。再由中序序列為DBGEHACIFJ，可以得到節(jié)點(diǎn)D、B、G、E、H位于根節(jié)點(diǎn)的左子樹上，節(jié)點(diǎn)C、I、F、J位于根節(jié)點(diǎn)的右子樹上。由于中序遍歷和后序遍歷都是先遍歷左子樹，故本題后序遍歷首先訪問D節(jié)點(diǎn)；再由后序遍歷是最后訪問根節(jié)點(diǎn)，故本題后序遍歷最后訪問的節(jié)點(diǎn)是根節(jié)點(diǎn)A。采用排除法可知，后續(xù)序列為DGHEBIJFCA。21、某二叉樹的前序序列為ABCDEFG，中序序列為DCBAEFG，則該二叉樹的深度(根節(jié)點(diǎn)在第l層)為()。A、2B、3C、4D、5標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：二叉樹的前序序列為AB(3DEFG，則A為根節(jié)點(diǎn)；中序序列為DCBAEFG，可知節(jié)點(diǎn)D、c、B位于根節(jié)點(diǎn)的左子樹上，節(jié)點(diǎn)E、F、G位于根節(jié)點(diǎn)的右子樹上。另外，節(jié)點(diǎn)B、C、D在前序序列和中序序列中順序相反，則說明這三個(gè)節(jié)點(diǎn)依次位于前一個(gè)節(jié)點(diǎn)的左子樹上；節(jié)點(diǎn)E、F、G順序未變，則說明這三個(gè)節(jié)點(diǎn)依次位于前一個(gè)節(jié)點(diǎn)的右子樹上。故二叉樹深度為4。22、某完全二叉樹按層次輸出(同一層從左到右)的序列為ABCI)EFGH。該完全二叉樹的前序序列為()。A、ABCDEFGHB、ABDHECFGC、HDBEAFCGD、HDEBFGCA標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：完全二叉樹的特點(diǎn)是除最后一層外，每一層上的節(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干節(jié)點(diǎn)。根據(jù)這一特點(diǎn)，再根據(jù)題意輸出序列為ABCDEFGH，可以得到該二叉樹的結(jié)構(gòu)如下：故此完全二叉樹的前序序列為ABDHECFG。23、設(shè)二叉樹中共有15個(gè)節(jié)點(diǎn)，其中的節(jié)點(diǎn)值互不相同。如果該二叉樹的前序序列與中序序列相同，則該二叉樹的深度為()。A、4B、6C、15D、不存在這樣的二叉樹標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：在具有n個(gè)節(jié)點(diǎn)的二叉樹中，如果各節(jié)點(diǎn)值互不相同，若該二叉樹的前序序列與中序序列相同，則說明該二叉樹只有右子樹，左子樹為空，二叉樹的深度為n；若該二叉樹的后序序列與中序序列相同，則說明該二叉樹只有左子樹，右子樹為空，二叉樹的深度為n。故本題中二叉樹的深度為15。24、在長度為n的順序表中查找一個(gè)元素，假設(shè)需要查找的元素有一半的機(jī)會(huì)在表中，并且如果元素在表中，則出現(xiàn)在表中每個(gè)位置上的可能性是相同的。則在平均情況下需要比較的次數(shù)大約為()。A、nB、3n／4C、n／2D、n／4標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：在順序表中查找，最好情況下第一個(gè)元素就是要查找的元素，則比較次數(shù)為1；在最壞情況下，最后一個(gè)元素才是要找的元素，則比較次數(shù)為n。這是找到元素的情況。如果沒有找到元素，則要比較n次。因此，平均需要比較：找到元素的情況×25、線性表的長度為n。在最壞情況下，比較次數(shù)為n－1的算法是()。A、順序查找B、同時(shí)尋找最大項(xiàng)與最小項(xiàng)C、尋找最大項(xiàng)D、有序表的插入標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：順序查找要逐個(gè)查看所有元素，會(huì)比較n次。在最壞情況下，尋找最大項(xiàng)無論如何需要查看表中的所有元素，n個(gè)元素比較次數(shù)為n－1。同時(shí)尋找最大項(xiàng)和最小項(xiàng)，需要為判斷較大值和較小值分別進(jìn)行比較，會(huì)有更多的比較次數(shù)。有序表的插入最壞情況下是插入到表中的最后一個(gè)元素的后面位置，則會(huì)比較n次。26、在快速排序法中，每經(jīng)過一次數(shù)據(jù)交換(或移動(dòng))后()。A、只能消除一個(gè)逆序B、能消除多個(gè)逆序C、不會(huì)產(chǎn)生新的逆序D、消除的逆序個(gè)數(shù)一定比新產(chǎn)生的逆序個(gè)數(shù)多標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：在一個(gè)排列中，如果一對(duì)數(shù)的前后位置與大小順序相反，即前面的數(shù)大于后面的數(shù)，那么它們就稱為一個(gè)逆序?？焖倥判虻乃枷胧牵簭木€性表中選取一個(gè)元素，設(shè)為T，將線性表中后面小于T的元素移到前面，而前面大于T的元素移到后面，結(jié)果就將線性表分成兩部分(稱兩個(gè)子表)，T插入到其分割線的位置處，這個(gè)過程稱為線性表的分割，然后再用同樣的方法對(duì)分割出的子表再進(jìn)行同樣的分割?？焖倥判虿皇菍?duì)兩個(gè)相鄰元素進(jìn)行比較，可以實(shí)線通過一次交換而消除多個(gè)逆序，但由于均與T(基準(zhǔn)元素)比較，也可能會(huì)產(chǎn)生新的逆序。27、下列各組排序法中，最壞情況下比較次數(shù)相同的是()。A、簡單選擇排序與堆排序B、簡單插入排序與希爾排序C、冒泡排序與快速排序D、希爾排序與堆排序標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：對(duì)于長度為n的線性表，最壞情況下查找或排序的次數(shù)如下表：28、在長度為97的順序有序表中作二分查找，最多需要的比較次數(shù)為()。A、48B、96C、7D、6標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：對(duì)于長度為n的有序線性表，在最壞情況下，二分查找只需要比較log2n次。本題中n=97，最多需要的比較次數(shù)為log297，6＜log297＜7，故需要比較7次。國家二級(jí)MSOffice高級(jí)應(yīng)用機(jī)試（數(shù)據(jù)結(jié)構(gòu)與算法）模擬試卷第4套一、選擇題(本題共23題，每題1.0分，共23分。)1、下列敘述中正確的是()。A、算法的空間復(fù)雜度是指算法程序中指令的條數(shù)B、壓縮數(shù)據(jù)存儲(chǔ)空間不會(huì)降低算法的空間復(fù)雜度C、算法的空間復(fù)雜度與算法所處理的數(shù)據(jù)存儲(chǔ)空間有關(guān)D、算法的空間復(fù)雜度是指算法程序控制結(jié)構(gòu)的復(fù)雜程度標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：算法的空間復(fù)雜度是指算法在執(zhí)行過程中所需要的內(nèi)存空間。算法執(zhí)行期間所需的存儲(chǔ)空間包括3個(gè)部分：輸入數(shù)據(jù)所占的存儲(chǔ)空間；程序本身所占的存儲(chǔ)空間；算法執(zhí)行過程中所需要的額外空間。在許多實(shí)際問題中，為了減少算法所占的存儲(chǔ)空間，通常采用壓縮存儲(chǔ)技術(shù)，以便盡量減少不必要的額外空間。2、下列敘述中正確的是()。A、非線性結(jié)構(gòu)可以為空B、只有一個(gè)根節(jié)點(diǎn)和一個(gè)葉子節(jié)點(diǎn)的必定是線性結(jié)構(gòu)C、只有一個(gè)根節(jié)點(diǎn)的必定是線性結(jié)構(gòu)或二叉樹D、沒有根節(jié)點(diǎn)的一定是非線性結(jié)構(gòu)標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個(gè)條件：①有且只有一個(gè)根節(jié)點(diǎn)；②每一個(gè)節(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)。線性結(jié)構(gòu)和非線性結(jié)構(gòu)都可以是空的數(shù)據(jù)結(jié)構(gòu)。樹只有一個(gè)根節(jié)點(diǎn)，但不論有幾個(gè)葉子節(jié)點(diǎn)，樹都是非線性結(jié)構(gòu)。3、設(shè)數(shù)據(jù)結(jié)構(gòu)B＝(D，R)，其中D：{a，b，c，d，e，f}R＝{(f，a)，(d，b)，(e，d)，(c，e)，(a，c)}該數(shù)據(jù)結(jié)構(gòu)為()。A、線性結(jié)構(gòu)B、循環(huán)隊(duì)列C、循環(huán)鏈表D、非線性結(jié)構(gòu)標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個(gè)要素：一是數(shù)據(jù)元素的集合，通常記為D；二是D上的關(guān)系，它反映了D中各數(shù)據(jù)元素之間的前后件關(guān)系，通常記為R。即一個(gè)數(shù)據(jù)結(jié)構(gòu)可以表示成B＝(D，R)。其中B表示數(shù)據(jù)結(jié)構(gòu)。為了反映D中各數(shù)據(jù)元素之間的前后件關(guān)系，一般用二元組來表示。例如，假設(shè)a與b是D中的兩個(gè)數(shù)據(jù)，則二元組(a，b)表示a是b的前件，b是a的后件。本題中R中的根節(jié)點(diǎn)為f，元素順序?yàn)閒→a→c→e→d→b，滿足線性結(jié)構(gòu)的條件。4、下列敘述中正確的是()。A、在棧中，棧頂指針的動(dòng)態(tài)變化決定棧中元素的個(gè)數(shù)B、在循環(huán)隊(duì)列中，隊(duì)尾指針的動(dòng)態(tài)變化決定隊(duì)列的長度C、在循環(huán)鏈表中，頭指針和鏈尾指針的動(dòng)態(tài)變化決定鏈表的長度D、在線性鏈表中，頭指針和鏈尾指針的動(dòng)態(tài)變化決定鏈表的長度標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：在棧中，通常用指針top來指示棧頂?shù)奈恢茫弥羔榖ottom指向棧底。棧頂指針top動(dòng)態(tài)反映了棧中元素的變化情況。在循環(huán)隊(duì)列中，隊(duì)頭指針和隊(duì)尾指針的動(dòng)態(tài)變化決定隊(duì)列的長度。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，備數(shù)據(jù)節(jié)點(diǎn)的存儲(chǔ)序號(hào)是不連續(xù)的，并且各節(jié)點(diǎn)在存儲(chǔ)空間中的位置關(guān)系與邏輯關(guān)系也不一致，故頭指針和尾指針或棧頂指針無法決定鏈表長度。5、設(shè)棧的順序存儲(chǔ)空間為S(1：m)，初始狀態(tài)為top＝0?，F(xiàn)經(jīng)過一系列正常的入棧與退棧操作后，top＝m＋1，則棧中的元素個(gè)數(shù)為()。A、0B、mC、不可能D、m＋1標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：棧為空時(shí)，棧頂指針top＝0，經(jīng)過入棧和退棧運(yùn)算，指針始終指向棧頂元素。初始狀態(tài)為top＝0，當(dāng)棧滿top＝m，無法繼續(xù)入棧，top值不可能為m＋1。6、設(shè)有棧S和隊(duì)列Q，初始狀態(tài)均為空。首先依次將A，B，C，D，E，F(xiàn)入棧，然后從棧中退出三個(gè)元素依次入隊(duì)，再將X，Y，Z入棧后，將棧中所有元素退出并依次入隊(duì)，最后將隊(duì)列中所有元素退出，則退隊(duì)元素的順序?yàn)?)。A、DEFXYZABCB、FEDZYXCBAC、FEDXYZCBAD、DEFZYXABC標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：棧是一種特殊的線性表，它所有的插入與刪除都限定在表的同一端進(jìn)行。隊(duì)列是指允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表。將A，B，C，D，E，F(xiàn)入棧后，棧中元素為ABCDEF，退出三個(gè)元素入隊(duì)，隊(duì)列元素為FED，將X，Y，Z入棧后棧中元素為ABCXYZ，退棧全部入隊(duì)后，隊(duì)列元素為FEDZYXCBA。7、設(shè)循環(huán)隊(duì)列的存儲(chǔ)空間為Q(1：m)，初始狀態(tài)為空?，F(xiàn)經(jīng)過一系列正常的入隊(duì)與退隊(duì)操作后，front＝m－1，rear＝m，此后再向該循環(huán)隊(duì)列中插入一個(gè)元素，則隊(duì)列中的元素個(gè)數(shù)為()。A、mB、m－1C、1D、2標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：該題中m－1＜m，即rear－front＞0，則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為m－(m－1)＝1。此后從該循環(huán)隊(duì)列中插入一個(gè)元素，則隊(duì)列中的元素個(gè)數(shù)為1＋1＝2。8、循環(huán)隊(duì)列的存儲(chǔ)空間為Q(1：40)，初始狀態(tài)為front＝rear＝40。經(jīng)過一系列正常的入隊(duì)與退隊(duì)操作后，front＝rear＝15，此后又退出一個(gè)元素，則循環(huán)隊(duì)列中的元素個(gè)數(shù)為()。A、14B、15C、40D、39，或0且產(chǎn)生下溢錯(cuò)誤標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：當(dāng)front＝rear＝15時(shí)可知隊(duì)列空或者隊(duì)列滿，此后又退出一個(gè)元素，如果之前隊(duì)列為空，退出操作會(huì)產(chǎn)生錯(cuò)誤。隊(duì)列里有0個(gè)元素；如果退出之前隊(duì)列已滿(40個(gè)元素)，執(zhí)行退出后，隊(duì)列里還有39個(gè)元素。9、下列敘述中正確的是()。A、節(jié)點(diǎn)中具有兩個(gè)指針域的鏈表一定是二叉鏈表B、節(jié)點(diǎn)中具有兩個(gè)指針域的鏈表可以是線性結(jié)構(gòu)，也可以是非線性結(jié)構(gòu)C、循環(huán)鏈表是循環(huán)隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D、循環(huán)鏈表是非線性結(jié)構(gòu)標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：節(jié)點(diǎn)中具有兩個(gè)指針域的鏈表既可以是雙向鏈表也可以是二叉鏈表，雙向鏈表是線性結(jié)構(gòu)，二叉鏈表屬于非線性結(jié)構(gòu)。循環(huán)鏈表是線性鏈表的一種形式，屬于線性結(jié)構(gòu)，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，而循環(huán)隊(duì)列是隊(duì)列的一種順序存儲(chǔ)結(jié)構(gòu)。10、帶鏈棧空的條件是()。A、top＝bottom＝NULLB、top＝－1且bottom＝NULLC、top＝NULL且bottom＝－1D、top＝bottom＝－1標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：在帶鏈的棧中，只會(huì)出現(xiàn)棧空和非空兩種狀態(tài)。當(dāng)棧為空時(shí)，有top＝bottom＝NULL；當(dāng)棧非空時(shí)，top指向鏈表的第一個(gè)節(jié)點(diǎn)(棧頂)。11、某帶鏈棧的初始狀態(tài)為top＝bottom＝NULL，經(jīng)過一系列正常的入棧與退棧操作后，top＝10，bottom＝20。該棧中的元素個(gè)數(shù)為()。A、0B、1C、10D、不確定標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：帶鏈的棧使用了鏈表來表示棧，而鏈表中的元素存儲(chǔ)在不連續(xù)的地址中，因此當(dāng)top＝10，bottom＝20時(shí)，不能確定棧中元素的個(gè)數(shù)。12、非空循環(huán)鏈表所表示的數(shù)據(jù)結(jié)構(gòu)()。A、有根節(jié)點(diǎn)也有葉子節(jié)點(diǎn)B、沒有根節(jié)點(diǎn)但有葉子節(jié)點(diǎn)C、有根節(jié)點(diǎn)但沒有葉子節(jié)點(diǎn)D、沒有根節(jié)點(diǎn)也沒有葉子節(jié)點(diǎn)標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：循環(huán)鏈表表頭節(jié)點(diǎn)為根節(jié)點(diǎn)，鏈表的最后一個(gè)節(jié)點(diǎn)為葉子節(jié)點(diǎn)，雖然它含有一個(gè)指向表頭節(jié)點(diǎn)的指針，但是表頭節(jié)點(diǎn)并不是它的一個(gè)后件。13、設(shè)一棵度為3的樹，其中度為2，1，0的節(jié)點(diǎn)數(shù)分別為3，1，6。該樹中度為3的節(jié)點(diǎn)數(shù)為()。A、1B、2C、3D、不可能有這樣的樹標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：設(shè)樹的節(jié)點(diǎn)數(shù)為n，則度為3的節(jié)點(diǎn)數(shù)為n－3－1－6＝n－10，根據(jù)樹中的節(jié)點(diǎn)數(shù)＝樹中所有節(jié)點(diǎn)的度之和＋1，得3×(n－10)＋2×3＋1×1＋0×6＋1＝n，解得n＝11，則度為3的節(jié)點(diǎn)數(shù)為n－10＝11－10＝1。14、某二叉樹中有15個(gè)度為1的節(jié)點(diǎn)，16個(gè)度為2的節(jié)點(diǎn)，則該二叉樹中總的節(jié)點(diǎn)數(shù)為()。A、32B、46C、48D、49標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：根據(jù)在二叉樹中度為0的節(jié)點(diǎn)(葉子節(jié)點(diǎn))總比度為2的節(jié)點(diǎn)多一個(gè)，得度為0的節(jié)點(diǎn)數(shù)為16＋1＝17個(gè)，故總的節(jié)點(diǎn)數(shù)：17＋15＋16＝48個(gè)。15、深度為7的完全二又樹中共有125個(gè)節(jié)點(diǎn)，則該完全二叉樹中的葉子節(jié)點(diǎn)數(shù)為()。A、62B、63C、64D、65標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：在滿二叉樹的第k層上有2k－1個(gè)節(jié)點(diǎn)、且深度為m的滿二叉樹有2m－1個(gè)節(jié)點(diǎn)，則深度為6的滿二叉樹共有26－1＝63個(gè)節(jié)點(diǎn)，第6層上有26－1＝32個(gè)節(jié)點(diǎn)。本題是深度為7的完全二叉樹，則前6層共有63個(gè)節(jié)點(diǎn)，第7層的節(jié)點(diǎn)數(shù)為125－63＝62個(gè)且全為葉子節(jié)點(diǎn)。由于第6層上有32個(gè)節(jié)點(diǎn)，第7層上有62個(gè)節(jié)點(diǎn)，則第6層上有1個(gè)節(jié)點(diǎn)無左右子樹(該節(jié)點(diǎn)為葉子節(jié)點(diǎn))。因此，該完全二叉樹中共有葉子節(jié)點(diǎn)62＋1＝63個(gè)。16、深度為5的完全二叉樹的節(jié)點(diǎn)數(shù)不可能是()。A、15B、16C、17D、18標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：設(shè)完全二叉樹的節(jié)點(diǎn)數(shù)為n，根據(jù)深度為k的二叉樹至多有2k－1個(gè)節(jié)點(diǎn)，再根據(jù)完全二叉樹的定義可知，2k－1－1＜n≤2k－1。本題中完全二叉樹的深度為5，則25－1－1＜n≤25－1，15＜n≤31。因此，節(jié)點(diǎn)數(shù)不能為15。17、下列敘述中正確的是()。A、非完全二叉樹可以采用順序存儲(chǔ)結(jié)構(gòu)B、有兩個(gè)指針域的鏈表就是二叉鏈表C、有的二叉樹也能用順序存儲(chǔ)結(jié)構(gòu)表示D、順序存儲(chǔ)結(jié)構(gòu)一定是線性結(jié)構(gòu)標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：在計(jì)算機(jī)中，二叉樹為非線性結(jié)構(gòu)，通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，但對(duì)于滿二叉樹和完全二叉樹來說，可以按層進(jìn)行順序存儲(chǔ)。因此A項(xiàng)錯(cuò)誤，C項(xiàng)正確。雖然滿二叉樹和完全二叉樹可以采用順序存儲(chǔ)結(jié)構(gòu)，但仍是一種非線性結(jié)構(gòu)，因此D項(xiàng)錯(cuò)誤。雙向鏈表也有兩個(gè)指針域，因此B項(xiàng)錯(cuò)誤。18、某二叉樹的中序遍歷序列為CBADE，后序遍歷序列為CBEDA，則前序遍歷序列為()。A、CBADEB、CBEDAC、ABCDED、EDCBA標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：二叉樹的后序遍歷序列為CBEDA，由于后序遍歷最后訪問根節(jié)點(diǎn)，可以確定該二叉樹的根節(jié)點(diǎn)是A。再由中序遍歷序列為CBADE，可以得到子序列(CB)一定在左子樹中，子序列(DE)一定在右子樹中。節(jié)點(diǎn)C、B在中序序列和后序序列中順序未變，說明節(jié)點(diǎn)B是節(jié)點(diǎn)C的父節(jié)點(diǎn)；節(jié)點(diǎn)D、E在中序序列和后序序列中順序相反，說明節(jié)點(diǎn)D是節(jié)點(diǎn)E的父節(jié)點(diǎn)。因此該二叉樹的前序遍歷序列為ABCDE。19、設(shè)非空二叉樹的所有子樹中，其左子樹上的節(jié)點(diǎn)值均小于根節(jié)點(diǎn)值，而右子樹上的節(jié)點(diǎn)值均不小于根節(jié)點(diǎn)值，則稱該二叉樹為排序二叉樹。對(duì)排序二叉樹的遍歷結(jié)果為有序序列的是()。A、前序序列B、中序序列C、后序序列D、前序序列或后序序列標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：中序遍歷的次序是先遍歷左子樹，再遍歷根節(jié)點(diǎn)，最后遍歷右子樹。而在排序二叉樹中，左子樹節(jié)點(diǎn)值＜根節(jié)點(diǎn)值≤右子樹節(jié)點(diǎn)值，要使對(duì)排序二叉樹的遍歷結(jié)果為有序序列，只能采用中序遍歷。20、設(shè)順序表的長度為40，對(duì)該表進(jìn)行冒泡排序。在最壞情況下需要的比較次數(shù)為()。A、40B、41C、780D、820標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：對(duì)長度為n的線性表排序，在最壞情況下，冒泡排序需要經(jīng)過n/2遍的從前住后的掃描和n/2遍的從后住前的掃描，需要比較的次數(shù)為n(n－1)/2。本題中n＝40，故比較次數(shù)為40×(40－1)÷2＝780。21、線性表的長度為n。在最壞情況下，比較次數(shù)為n－1的算法是()。A、順序查找B、同時(shí)尋找最大項(xiàng)與最小項(xiàng)C、尋找最大項(xiàng)D、有序表的插入標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：順序查找要逐個(gè)查看所有元素，會(huì)比較n次。在最壞情況下，尋找最大項(xiàng)無論如何需要查看表中的所有元素，n個(gè)元素比較次數(shù)為n－1。同時(shí)尋找最大項(xiàng)和最小項(xiàng)，需要為判斷較大值和較小值分別進(jìn)行比較，會(huì)有更多的比較次數(shù)。有序表的插入最壞情況下是插入到表中的最后一個(gè)元素的后面位置，則會(huì)比較n次。22、下列排序方法中，最壞情況下時(shí)間復(fù)雜度(即比較次數(shù))最低的是()。A、快速排序B、希爾排序C、簡單插入排序D、冒泡排序標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：最壞情況下，希爾排序需要比較nr(1＜r＜2)次，快速排序、簡單插入排序、冒泡排序均需要比較n(n－1)/2次，故希爾排序時(shí)間復(fù)雜度最低。23、下列各組排序法中，最壞情況下比較次數(shù)相同的是()。A、簡單選擇排序與堆排序B、簡單插入排序與希爾排序C、冒泡排序與快速排序D、希爾排序與堆排序標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：對(duì)于長度為n的線性表，最壞情況下查找或排序的次數(shù)如下表：國家二級(jí)MSOffice高級(jí)應(yīng)用機(jī)試（數(shù)據(jù)結(jié)構(gòu)與算法）模擬試卷第5套一、選擇題(本題共28題，每題1.0分，共28分。)1、下列關(guān)于棧的敘述正確的是A、棧按“先進(jìn)先出”組織數(shù)據(jù)B、棧按“先進(jìn)后出”組織數(shù)據(jù)C、只能在棧底插入數(shù)據(jù)D、不能刪除數(shù)據(jù)標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：棧是限定在一端進(jìn)行插入和刪除的線性表，允許進(jìn)行插入和刪除元素的一端稱為棧頂，另一端稱為棧底。棧是按照“先進(jìn)后出”的原則組織數(shù)據(jù)的。2、算法的空間復(fù)雜度是指A、算法在執(zhí)行過程中所需要的計(jì)算機(jī)存儲(chǔ)空間B、算法所處理的數(shù)據(jù)量C、算法程序中的語句或指令條數(shù)D、算法在執(zhí)行過程中所需要的臨時(shí)工作單元數(shù)標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：算法的空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。這個(gè)內(nèi)存空間包括算法程序所占的空間，輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間以及算法執(zhí)行過程中所需要的額外空間。3、下列數(shù)據(jù)結(jié)構(gòu)中，能夠按照“先進(jìn)后出”原則存取數(shù)據(jù)的是A、循環(huán)隊(duì)列B、棧C、隊(duì)列D、二叉樹標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：棧按照“先進(jìn)后出”(FILO)或“后進(jìn)先出”(LIFO)組織數(shù)據(jù)；隊(duì)列是“先進(jìn)先出”(FIFO)或“后進(jìn)后出”(LILO)的線性表。4、某二叉樹共有7個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)只有1個(gè)，則該二叉樹的深度為(假設(shè)根結(jié)點(diǎn)在第1層)A、3B、4C、6D、7標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：根據(jù)二叉樹的性質(zhì)，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)。題目中的二叉樹的葉子結(jié)點(diǎn)為1，因此度為2的結(jié)點(diǎn)的數(shù)目為0，故該二叉樹為7層，每層只有一個(gè)結(jié)點(diǎn)。5、下列關(guān)于線性鏈表的敘述中，正確的是A、各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)空間可以不連續(xù)，但它們的存儲(chǔ)順序與邏輯JII頁序必須一致B、各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與邏輯順序可以不一致，但它們的存儲(chǔ)空間必須連續(xù)C、進(jìn)行插入與刪除時(shí)，不需要移動(dòng)表中的元素D、以上都不正確標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致。而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。6、下列敘述中正確的是A、程序執(zhí)行的效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)密切相關(guān)B、程序執(zhí)行的效率只取決于程序的控制結(jié)構(gòu)C、程序執(zhí)行的效率只取決于所處理的數(shù)據(jù)量D、以上都不正確標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：影響程序執(zhí)行效率的因素有很多，如數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、程序處理的數(shù)據(jù)量、程序的算法等。順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在數(shù)據(jù)插入和刪除操作上的效率就存在差別。其中，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的效率要高一些。7、對(duì)長度為10的線性表進(jìn)行冒泡排序，最壞情況下需要比較的次數(shù)為A、9B、10C、45D、90標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：線性表的長度為n，最壞情況下冒泡排序需要比較的次數(shù)為n(n．1)／2。8、某二叉樹共有13個(gè)結(jié)點(diǎn)，其中有4個(gè)度為1的結(jié)點(diǎn)，則葉子結(jié)點(diǎn)數(shù)為A、5B、4C、3D、2標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：根據(jù)二叉樹的性質(zhì)3，在任意一顆二叉樹中，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)，即有n0=n2+1。本題總結(jié)點(diǎn)數(shù)：13=n0+n1+n2=n2+1+4+n2=2n2+5，n2=4，所以葉子結(jié)點(diǎn)數(shù)等于4+1=5，選項(xiàng)A正確。9、下列敘述中正確的是A、存儲(chǔ)空間不連續(xù)的所有鏈表一定是非線性結(jié)構(gòu)B、結(jié)點(diǎn)中有多個(gè)指針域的所有鏈表一定是非線性結(jié)構(gòu)C、能順序存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)一定是線性結(jié)構(gòu)D、帶鏈的棧與隊(duì)列是線性結(jié)構(gòu)標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：計(jì)算機(jī)中數(shù)據(jù)按照其數(shù)據(jù)邏輯結(jié)構(gòu)，可以分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。而數(shù)據(jù)在內(nèi)存或磁盤中的存儲(chǔ)，可以分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)之間沒有對(duì)應(yīng)的關(guān)系。所以選項(xiàng)ABC都是錯(cuò)誤的，棧和隊(duì)列按照數(shù)據(jù)的邏輯劃分都是線性結(jié)構(gòu)。10、設(shè)循環(huán)隊(duì)列為Q(1：m)，其初始狀態(tài)為front=rear=m。經(jīng)過一系列入隊(duì)與退隊(duì)運(yùn)算后，front=15，rear=20?，F(xiàn)要在該循環(huán)隊(duì)列中尋找最大值的元素，最壞情況下需要比較的次數(shù)為A、4B、6C、m－5D、m－6標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：初始狀態(tài)為front=rear=m，rear-front=0，此時(shí)隊(duì)列為空。經(jīng)過一系列入隊(duì)與退隊(duì)運(yùn)算后，front=15，rear=20。隊(duì)尾大于隊(duì)頭，則隊(duì)尾rear減隊(duì)頭front等于5個(gè)元素。此時(shí)隊(duì)列中有5個(gè)元素，而查找最大項(xiàng)至少要比較n-1次，就是4次。因此選項(xiàng)A正確。11、下列敘述中正確的是A、帶鏈隊(duì)列的存儲(chǔ)空間可以不連續(xù)，但隊(duì)頭指針必須大于隊(duì)尾指針B、帶鏈隊(duì)列的存儲(chǔ)空間可以不連續(xù)，但隊(duì)頭指針必須小于隊(duì)尾指針C、帶鏈隊(duì)列的存儲(chǔ)空間可以不連續(xù)，且隊(duì)頭指針可以大于也可以小于隊(duì)尾指針D、以上三項(xiàng)都錯(cuò)誤標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：帶鏈隊(duì)列的存儲(chǔ)空問可以不連續(xù)，且隊(duì)頭指針與隊(duì)尾指針大小沒有可比性，選項(xiàng)C正確。12、一個(gè)棧的初始狀態(tài)為空，現(xiàn)將元素A、B、C、D、E依次入棧，然后依次退棧三次，并將退棧的三個(gè)元素依次入隊(duì)(原隊(duì)列為空)，最后將隊(duì)列中的元素全部退出。則元素退隊(duì)的順序?yàn)锳、ABCB、CBAC、EDCD、CDE標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：棧是根據(jù)先進(jìn)后出的原則組織數(shù)據(jù)，所以退棧三次的元素依次為E、D、C；隊(duì)列是根據(jù)先進(jìn)先出的原則組織數(shù)據(jù)的，所以退隊(duì)的順序依次為E、D、C，所以選項(xiàng)C正確。13、下列敘述中正確的是A、所有數(shù)據(jù)結(jié)構(gòu)必須有根結(jié)點(diǎn)B、所有數(shù)據(jù)結(jié)構(gòu)必須有終端結(jié)點(diǎn)(即葉子結(jié)點(diǎn))C、只有一個(gè)根結(jié)點(diǎn)，且只有一個(gè)葉子結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)一定是線性結(jié)構(gòu)D、沒有根結(jié)點(diǎn)或沒有葉子結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)一定是非線性結(jié)構(gòu)標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：只有一個(gè)空節(jié)點(diǎn)的結(jié)構(gòu)也屬數(shù)據(jù)結(jié)構(gòu)，所以選項(xiàng)A和選項(xiàng)B不正確；有且只有一個(gè)根結(jié)點(diǎn)，每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件的數(shù)據(jù)結(jié)構(gòu)才屬于線性結(jié)構(gòu)，其它的都屬于非線性結(jié)構(gòu)，故選項(xiàng)C不正確，選項(xiàng)D正確。14、下列敘述中正確的是A、結(jié)點(diǎn)中具有兩個(gè)指針域的鏈表一定是二叉鏈表B、結(jié)點(diǎn)中具有兩個(gè)指針域的鏈表可以是線性結(jié)構(gòu)，也可以是非線性結(jié)構(gòu)C、二叉樹只能采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D、循環(huán)鏈表是非線性結(jié)構(gòu)標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：結(jié)點(diǎn)中盡管有兩個(gè)指針域但沒有分別指向兩個(gè)不同的結(jié)點(diǎn)就不是二叉鏈表，故選項(xiàng)A不正確；二叉樹是非線性結(jié)構(gòu)，即每個(gè)數(shù)據(jù)結(jié)點(diǎn)至多只有一個(gè)前驅(qū)，但可以有多個(gè)后繼。它可采用順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，故選項(xiàng)C不正確；循環(huán)鏈表是在單鏈表中，將終端結(jié)點(diǎn)的指針域NULL改為指向表頭結(jié)點(diǎn)或開始結(jié)點(diǎn)的線性結(jié)構(gòu)，故選項(xiàng)D不正確；當(dāng)結(jié)點(diǎn)中兩個(gè)指針分別指向前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)時(shí)為線性結(jié)構(gòu)，當(dāng)指向兩個(gè)不同的前驅(qū)或后繼結(jié)點(diǎn)時(shí)為非線性結(jié)構(gòu)，故選項(xiàng)B正確。15、某二叉樹共有399個(gè)結(jié)點(diǎn)，其中有199個(gè)度為2的結(jié)點(diǎn)，則該二叉樹中的葉子結(jié)點(diǎn)數(shù)為A、不存在這樣的二叉樹B、200C、198D、199標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：在二叉樹中，設(shè)葉子結(jié)點(diǎn)個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，葉子結(jié)點(diǎn)的個(gè)數(shù)計(jì)算方法n0=n2+1=199+1=200，所以選項(xiàng)B正確。16、下列敘述中正確的是A、在棧中，棧項(xiàng)指針的動(dòng)態(tài)變化決定棧中元素的個(gè)數(shù)B、在循環(huán)隊(duì)列中，隊(duì)尾指針的動(dòng)態(tài)變化決定隊(duì)列的長度C、在循環(huán)鏈表中，頭指針和鏈尾指針的動(dòng)態(tài)變化決定鏈表的長度D、在線性鏈表中，頭指針和鏈尾指針的動(dòng)態(tài)變化決定鏈表的長度標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：棧是一種特殊的線性表，是一種只允許在表的一端進(jìn)行插入或刪除操作的線性表。表中允許進(jìn)行插入、刪除操作的一端稱為棧頂；表的另一端稱為棧底。棧項(xiàng)的當(dāng)前位置是動(dòng)態(tài)的，對(duì)棧頂當(dāng)前位置的標(biāo)記稱為棧頂指針。在棧中，棧頂指針動(dòng)態(tài)反映了棧中元素的變化情況。所以選項(xiàng)A正確。17、設(shè)一棵樹的度為3，其中度為3，2，1的結(jié)點(diǎn)個(gè)數(shù)分別為4，1，3。則該棵樹中的葉子結(jié)點(diǎn)數(shù)為A、10B、11C、12D、不可能有這樣的樹標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：因?yàn)槿我豢脴渲?，結(jié)點(diǎn)總數(shù)=總分支數(shù)目+1，所以：n0+4+1+3=(n0*0+3*4+2*1+1*3)+1。計(jì)算結(jié)果n0=10。其中，no表示葉子結(jié)點(diǎn)。所以選項(xiàng)A正確。18、設(shè)順序表的長度為n。下列算法中，最壞情況下比較次數(shù)小于n的是A、尋找最大項(xiàng)B、堆排序C、快速排序D、順序查找法標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：如果順序表是線性存儲(chǔ)的(不包括線性的鏈?zhǔn)奖?，那么元素要不就是從大到小。要不就是小到大的順序，假設(shè)第一個(gè)數(shù)就是最大值，那么需要比較1次，n－1應(yīng)該是最壞情況下要比較的次數(shù)，所以選項(xiàng)A正確。19、下列敘述中正確的是A、對(duì)數(shù)據(jù)進(jìn)行壓縮存儲(chǔ)會(huì)降低算法的空間復(fù)雜度B、算法的優(yōu)化主要通過程序的編制技巧來實(shí)現(xiàn)C、算法的復(fù)雜度與問題的規(guī)模無關(guān)D、數(shù)值型算法只需考慮計(jì)算結(jié)果的可靠性標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：算法的空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間，包括3個(gè)部分：輸入數(shù)據(jù)所占的存儲(chǔ)空間；程序本身所占的存儲(chǔ)空間；算法執(zhí)行過程中所需要的額外空間。為了降低算法的空間復(fù)雜度，主要應(yīng)減少輸入數(shù)據(jù)所占的存儲(chǔ)空間以及額外空間，通常采用壓縮存儲(chǔ)技術(shù)，A選項(xiàng)正確。20、某帶鏈隊(duì)列初始狀態(tài)為front=rear=NULL。經(jīng)過一系列正常入隊(duì)與退隊(duì)操作后，front=10，rear=5。該隊(duì)列中的元素個(gè)數(shù)為A、不確定B、5C、4D、6標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：循環(huán)隊(duì)列用數(shù)組A[0：m．1]存放其元素值，已知其頭尾指針分別是front和rear，則當(dāng)前隊(duì)列的元素個(gè)數(shù)是(rear－front+m)％m=(5－10+m)％m=(m－5)％m。因?yàn)楸绢}中的m值不確定，所以(m－5)％m的值不能確定。所以選項(xiàng)A正確。21、設(shè)表的長度為n。下列查找算法中，在最壞情況下，比較次數(shù)最少的是A、有序表的二分查找B、順序查找C、尋找最大項(xiàng)D、尋找最小項(xiàng)標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：有序表的二分法查找只適用于順序存儲(chǔ)的有序表。二分查找的基本方法是：將被查元素x與線性表的中間項(xiàng)進(jìn)行比較，若中間項(xiàng)的值等于x，則說明查到；若小于中間項(xiàng)的值則在線性表的前半部分以相同的方法進(jìn)行查找；若大于中間項(xiàng)的值則在線性表的后半部分以相同的方法進(jìn)行查找。在最壞情況下，二分查找需要比較。log2n次。順序查找、尋找最大項(xiàng)、尋找最小項(xiàng)，在最壞情況下，比較次數(shù)都是n次。所以選項(xiàng)A正確。22、設(shè)數(shù)據(jù)結(jié)構(gòu)B=(D，R)，其中D={a,b,c,d,e,f}R={(e,a),(d,b),(e,d),(c,e),(a,c)}該數(shù)據(jù)結(jié)構(gòu)為A、線性結(jié)構(gòu)B、循環(huán)隊(duì)列C、循環(huán)鏈表D、非線性結(jié)構(gòu)標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：由結(jié)點(diǎn)之間的關(guān)系R={(f,a)，(d,b)，(e,d)，(c,e)，(a,c)}可以得到，該數(shù)據(jù)結(jié)構(gòu)為：“f－a－c－e－d－b”。由此可知結(jié)點(diǎn)f沒有前驅(qū)，結(jié)點(diǎn)b沒有后繼結(jié)點(diǎn)，并且其它的結(jié)點(diǎn)只有一個(gè)前驅(qū)結(jié)點(diǎn)和一個(gè)后繼結(jié)點(diǎn)，所以該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。所以應(yīng)選A選項(xiàng)。23、設(shè)一棵樹的度為3，其中沒有度為2的結(jié)點(diǎn)，且葉子結(jié)點(diǎn)數(shù)為5。該樹中度為3的結(jié)點(diǎn)數(shù)為A、1B、2C、3D、不可能有這樣的樹標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：樹的度是指一棵樹中，最大的結(jié)點(diǎn)的度稱為樹的度。本題中樹的度為3，那么樹中最少有一個(gè)結(jié)點(diǎn)的度為3。而樹中沒有度為2的結(jié)點(diǎn)，葉子結(jié)點(diǎn)數(shù)為5，度為1的結(jié)點(diǎn)下面只有一個(gè)葉子結(jié)點(diǎn)。因此，該樹中含2個(gè)度為3的結(jié)點(diǎn)滿足題目要求。24、設(shè)有一個(gè)棧與一個(gè)隊(duì)列的初始狀態(tài)均為空。現(xiàn)有一個(gè)序列A，B，C，D,E,F,G，H。先分別將序列中的前4個(gè)元素依次入棧，后4個(gè)元素依次入隊(duì)；然后分別將棧中的元素依次退棧，再將隊(duì)列中的元素依次退隊(duì)。最后得到的序列為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知識(shí)點(diǎn)解析：棧(stack)又名堆棧，它是一種運(yùn)算受限的線性表。其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算。因此棧的出棧順序是先入后出，所以順序是D，C，B，A。隊(duì)列是一種特殊的線性表，特殊之處在于它只允許在表的前端(front)進(jìn)行刪除操作，而在表的后端(rear)進(jìn)行插入操作，和棧一樣，隊(duì)列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。因此，隊(duì)的出隊(duì)順序是，先入先出，所以順序是E，F(xiàn)，G，H。最后的順序是：D，C，B，A，E，F(xiàn)，G，H。25、從表中任何一個(gè)結(jié)點(diǎn)位置出發(fā)就可以不重復(fù)地訪問到表中其他所有結(jié)點(diǎn)的鏈表是A、循環(huán)鏈表B、雙向鏈表C、單向鏈表D、二叉鏈表標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。它的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)，循環(huán)一圈就訪問到了表中其它所有結(jié)點(diǎn)而不重復(fù)。26、下列敘述中錯(cuò)誤的是A、向量是線性結(jié)構(gòu)B、非空線性結(jié)構(gòu)中只有一個(gè)結(jié)點(diǎn)沒有前件C、非空線性結(jié)構(gòu)中只有一個(gè)結(jié)點(diǎn)沒有后件D、只有一個(gè)根結(jié)點(diǎn)和一個(gè)葉子結(jié)點(diǎn)的結(jié)構(gòu)必定是線性結(jié)構(gòu)標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：線性結(jié)構(gòu)是n個(gè)數(shù)據(jù)元素的有序(次序)集合。①集合中必存在唯一的一個(gè)“第一個(gè)元素”；②集合中必存在唯一的一個(gè)“最后的元素”；③除最后元素之外，其它數(shù)據(jù)元素均有唯一的“后件”；④除第一元素之外，其它數(shù)據(jù)元素均有唯一的“前件”。相對(duì)應(yīng)于線性結(jié)構(gòu)，非線性結(jié)構(gòu)的邏輯特征是一個(gè)結(jié)點(diǎn)元素可能對(duì)應(yīng)多個(gè)直接前驅(qū)和多個(gè)后繼。向量符合線性結(jié)構(gòu)特點(diǎn)。非線性結(jié)構(gòu)也會(huì)存在只有一個(gè)根結(jié)點(diǎn)和葉子結(jié)點(diǎn)的情況。27、設(shè)順序表的長度為40，對(duì)該表進(jìn)行冒泡排序。在最壞情況下需要的比較次數(shù)為A、780B、820C、40D、41標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：冒泡排序(BubbleSort)，是一種計(jì)算機(jī)科學(xué)領(lǐng)域的較簡單的排序算法。冒泡排序算法的運(yùn)作如下：比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換它們兩個(gè)；對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)；針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)；持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。冒泡排序的最壞時(shí)間復(fù)雜度為(n*(n－1))／2=780。28、設(shè)循環(huán)隊(duì)列的存儲(chǔ)空間為Q(1：m)，初始狀態(tài)為front=rear=m。經(jīng)過一系列正常的操作后，front=1，rear=m為了在該隊(duì)列中尋找值最大的元素，在最壞情況下需要的比較次數(shù)為A、mB、m－1C、m－2D、1標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：經(jīng)過一系列正常的操作后，front=1，rear=m，那么最壞情況下需要的比較次數(shù)為rear－front－1=m－1－1=m－2。國家二級(jí)MSOff