2021年全國(guó)計(jì)算機(jī)二級(jí)考試數(shù)據(jù)結(jié)構(gòu)與算法

全國(guó)計(jì)算機(jī)二級(jí)考試

第一章數(shù)據(jù)構(gòu)造與算法.一種算法普通都可以用、、三種控制構(gòu)造組合完畢。［解析］順序、選?。ǚ种В⒀h(huán)（重復(fù)）一種算法普通由兩種基本要素構(gòu)成：一是對(duì)數(shù)據(jù)對(duì)象運(yùn)算和操作，二是.［解析］算法控制構(gòu)造在普通計(jì)算機(jī)系統(tǒng)中，有算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算和四類基本操作和運(yùn)算。［解析〉數(shù)據(jù)傳播.慣用于解決“與否存在”或“有多少種也許”等類型問(wèn)題（例如求解不定方程問(wèn)題）算法涉及基本辦法是（）A.列舉法 B.歸納法 C.遞歸法 D.減半遞推法［解析］列舉就是列舉出所有也許性，將所有也許性統(tǒng)統(tǒng)列舉出來(lái)，然后解決問(wèn)題辦法。因此A.依照提出問(wèn)題，列舉所有也許狀況，并用問(wèn)題中給定條件檢查哪些是需要，哪些是不需要，這是算法設(shè)計(jì)基本辦法中.［解析］列舉法.通過(guò)列舉少量特殊狀況，通過(guò)度析，最后找出普通關(guān)系算法設(shè)計(jì)思想是。A.列舉法 B.歸納法 C.遞歸法 D.減半遞推法［解析］B.在用二分法求解方程在一種閉區(qū)間實(shí)根時(shí)，采用算法設(shè)計(jì)技術(shù)是。A.列舉法B.A.列舉法B.歸納法 C.遞歸法D.減半遞推法［解析］二分法就是從一半處比較，減半遞推技術(shù)也稱分治法，將問(wèn)題減半。因此D.將一種復(fù)雜問(wèn)題歸結(jié)為若干個(gè)簡(jiǎn)樸問(wèn)題，然后將這些較簡(jiǎn)樸問(wèn)題再歸結(jié)為更簡(jiǎn)樸問(wèn)題，這個(gè)過(guò)程可以始終做下去，直到最簡(jiǎn)樸問(wèn)題為止，這是算法設(shè)計(jì)基本辦法中—,如果一種算法P顯式地調(diào)用自己則稱為_。如果算法P調(diào)用另一種算法Q而算法Q又調(diào)用算法P,則稱為.［解析］遞歸法 直接遞歸間接遞歸調(diào)用.算法中各操作之間執(zhí)行順序稱為。描述算法工具普通有、、。［解析］控制構(gòu)造 老式流程圖、N-S構(gòu)造化流程圖、算法描述語(yǔ)言.從已知初始條件出發(fā)，逐漸推出所規(guī)定各中間成果和最后成果，這是算法設(shè)計(jì)基本辦法中()［解析］遞推法.將問(wèn)題規(guī)模減半，而問(wèn)題性質(zhì)不變，再重復(fù)“減半”過(guò)程，這是算法設(shè)計(jì)基本辦法中()［解析］減半遞推技術(shù).通過(guò)對(duì)問(wèn)題分析，找出一種解決問(wèn)題線索，然后沿著這個(gè)線索逐漸試探，對(duì)于每一步試探，若試探成功，就得到問(wèn)題解，若試探失敗，就逐漸回退，換別路線再試探，這是算法設(shè)計(jì)基本辦法中［解析］回溯法1.下列論述中對(duì)的是A.順序存儲(chǔ)構(gòu)造存儲(chǔ)一定是持續(xù)，鏈?zhǔn)酱鎯?chǔ)構(gòu)造存儲(chǔ)空間不一定是持續(xù)B.順序存儲(chǔ)構(gòu)造只針對(duì)線性構(gòu)造，鏈?zhǔn)酱鎯?chǔ)構(gòu)造只針對(duì)非線性構(gòu)造C.順序存儲(chǔ)構(gòu)造能存儲(chǔ)有序表，鏈?zhǔn)酱鎯?chǔ)構(gòu)造不能存儲(chǔ)有序表D.鏈?zhǔn)酱鎯?chǔ)構(gòu)造比順序存儲(chǔ)構(gòu)造節(jié)約存儲(chǔ)空間［解析］順序存儲(chǔ)構(gòu)造中各數(shù)據(jù)元素在存儲(chǔ)空間中是按照邏輯順序依次持續(xù)存儲(chǔ)，在鏈?zhǔn)酱鎯?chǔ)構(gòu)造中元素之間關(guān)系通過(guò)指針來(lái)連接，因此不規(guī)定存儲(chǔ)空間一定是持續(xù)；順序存儲(chǔ)構(gòu)造（或鏈?zhǔn)酱鎯?chǔ)構(gòu)造）既可以針對(duì)線性構(gòu)造，也可以針對(duì)非線性構(gòu)造，但像棧、隊(duì)列這樣線性構(gòu)造普通采用順序存儲(chǔ)構(gòu)造（但也可以采用鏈?zhǔn)綐?gòu)造）；樹、二叉樹這樣非線性構(gòu)造普通采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造（但也可以采用順序存儲(chǔ)構(gòu)造）；鏈?zhǔn)酱鎯?chǔ)構(gòu)造既可以存儲(chǔ)無(wú)序表，也可以存儲(chǔ)有序表，注意，鏈?zhǔn)酱鎯?chǔ)構(gòu)造存儲(chǔ)雖然是有序表，也不能進(jìn)行二分查找；鏈?zhǔn)酱鎯?chǔ)構(gòu)造比順序存儲(chǔ)構(gòu)造要多使用存儲(chǔ)空間，由于鏈?zhǔn)酱鎯?chǔ)構(gòu)造中要用額外空間來(lái)保存指針。因此A順序存儲(chǔ)方式重要用于線性數(shù)據(jù)構(gòu)造，它把邏輯上相鄰數(shù)據(jù)元素存儲(chǔ)在物理上相鄰存儲(chǔ)單元里，結(jié)點(diǎn)之間關(guān)系由存儲(chǔ)單元鄰接關(guān)系來(lái)體現(xiàn)。而鏈?zhǔn)酱鎯?chǔ)構(gòu)造存儲(chǔ)空間不一定是持續(xù)。.數(shù)據(jù)存儲(chǔ)構(gòu)造是指。A.存儲(chǔ)在外存中數(shù)據(jù) B.數(shù)據(jù)所占存儲(chǔ)空間量C.數(shù)據(jù)在計(jì)算機(jī)中順序存儲(chǔ)方式 D.數(shù)據(jù)邏輯構(gòu)造在計(jì)算機(jī)中體現(xiàn)［解析］數(shù)據(jù)邏輯構(gòu)造是指數(shù)據(jù)元素之間邏輯關(guān)系數(shù)據(jù)構(gòu)造。數(shù)據(jù)存儲(chǔ)構(gòu)造則是數(shù)據(jù)邏輯構(gòu)造在計(jì)算機(jī)中物理實(shí)現(xiàn)，有時(shí)也稱作數(shù)據(jù)物理構(gòu)造.兩者區(qū)別是數(shù)據(jù)邏輯構(gòu)造只涉及到數(shù)據(jù)之間抽象數(shù)學(xué)關(guān)系，存儲(chǔ)構(gòu)造則涉及到如何在計(jì)算機(jī)中通過(guò)對(duì)數(shù)據(jù)物理存儲(chǔ)進(jìn)行組織來(lái)表達(dá)數(shù)據(jù)元素之間邏輯關(guān)系。例如在線性表順序存儲(chǔ)中是運(yùn)用物理存儲(chǔ)空間上持續(xù)性來(lái)表達(dá)線性表中數(shù)據(jù)先后件關(guān)系；在線性表鏈?zhǔn)酱鎯?chǔ)中是通過(guò)指針域構(gòu)成邏輯鏈條來(lái)表達(dá)數(shù)據(jù)先后件關(guān)系。普通，一種數(shù)據(jù)邏輯機(jī)構(gòu)相應(yīng)物理實(shí)現(xiàn)，即數(shù)據(jù)存儲(chǔ)構(gòu)造不止一種。因此D.在長(zhǎng)度為n順序存儲(chǔ)構(gòu)造線性表中，要在第i（iWWn）個(gè)元素之前插入一種新元素，則需要移動(dòng)表中（）個(gè)元素，表長(zhǎng)度變?yōu)椋ǎ蝗魟h除表中第i（iWiWn）個(gè)元素，則需要移動(dòng)表中（）個(gè)元素，表長(zhǎng)度變?yōu)椋ǎ?。［解析］n-i+1；n+1；n-i；n-1.一種棧初始狀態(tài)為空?，F(xiàn)將元素1、2、3、4、5、A、B、C、D、E依次入棧，然后再依次出棧，則元素出棧順序是。A.12345ABCDEB.EDCBA54321 C.ABCDE12345D.54321EDCBA［解析］棧是按照“先進(jìn)后出（FILO）”或“后進(jìn)先出（UFO）”原則組織數(shù)據(jù)，棧職能在棧頂插入數(shù)據(jù)（稱為入棧）和刪除數(shù)據(jù)（稱為出棧％現(xiàn)將元素1、2、3、4、5、A、B、C、D、E依次入棧，然后再依次出棧，則元素出棧順序是EDCBA54321。因此B.下列關(guān)于棧描述中錯(cuò)誤是（）A.棧是先進(jìn)后出線性表 B.棧職能順序存儲(chǔ)C.棧具備記憶作用 D.對(duì)棧插入與刪除操作中，不需要變化棧底指針［解析］棧是一種先進(jìn)后出線性表；棧既可以順序存儲(chǔ)，也可以鏈?zhǔn)酱鎯?chǔ)；棧可以用開保護(hù)斷點(diǎn)信息，具備記憶作用；只容許在棧頂插入和刪除元素，因此對(duì)棧插入與刪除操作，不要用變化棧底指針.線性表存儲(chǔ)構(gòu)造重要分為順序存儲(chǔ)構(gòu)造和鏈?zhǔn)酱鎯?chǔ)構(gòu)造。隊(duì)列是一種特殊是線性表，循環(huán)隊(duì)列是隊(duì)列存儲(chǔ)構(gòu)造。［解析］順序.數(shù)據(jù)構(gòu)造分為線性構(gòu)造和非線性構(gòu)造，帶鏈隊(duì)列屬于［解析］線性總結(jié)：慣用數(shù)據(jù)構(gòu)造例如：線性表、棧、隊(duì)列是線性構(gòu)造（不論是采用順序存儲(chǔ)還是鏈?zhǔn)酱鎯?chǔ)構(gòu)造）；樹、二叉樹、圖都是非線性構(gòu)造（不論是采用順序存儲(chǔ)構(gòu)造還是鏈?zhǔn)酱鎯?chǔ)構(gòu)造）.已知元素入棧順序?yàn)閍bcde,則下列哪種出棧順序是不也許？。A.edcbaB.cabdeC.dcbaeD.bcdea［解析］abcde依次入棧，再再次出棧，得到出棧順序edcba,因此選項(xiàng)A也許：選項(xiàng)B,第一種出棧是C,可以必定棧中有b、a,等待入棧是d、e,此時(shí)出棧也許是b或d（d入棧立即出棧），不也許是a,因此選項(xiàng)B不也許；選項(xiàng)C,第一種出棧是d,可以必定棧中有c、b、a,等待入棧是e,此時(shí)出棧也許是c或e,若c、b、a依次出棧，e入棧立即出棧，剛好得到出棧順序dcbae,因而選項(xiàng)C也許；選項(xiàng)D,第一種出棧是b,可以必定棧中有a.等待入棧是c、d、e,c、d、e分別入棧又出棧得到出棧順序bcde,最后a出棧，行號(hào)得到出棧順序bcdea,因此選項(xiàng)D也許。因而本題對(duì)的答案是B。.如果剛開始時(shí)棧為空，依次有A、B、C、D四個(gè)元素入棧，此時(shí)棧底指針指向元素，棧頂指針值為_（如果每個(gè)元素長(zhǎng)度為1）.執(zhí)行四次出棧操作后把E、F、G壓入棧，問(wèn)此時(shí)棧底指針指向元素，此時(shí)棧長(zhǎng)度為.［解析］A;4;E;3.下列論述中對(duì)的是A.循環(huán)隊(duì)列有對(duì)頭和隊(duì)尾兩個(gè)指針，因而，循環(huán)隊(duì)列是非線性構(gòu)造B.在循環(huán)隊(duì)列中，只需要對(duì)頭指針就能反映隊(duì)列中元素動(dòng)態(tài)變化狀況C.在循環(huán)隊(duì)列中，只需要隊(duì)尾指針就能反映隊(duì)列中元素動(dòng)態(tài)變化狀況D.循環(huán)隊(duì)列中元素個(gè)數(shù)是由對(duì)頭指針和隊(duì)尾指針共同決定［解析］所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲(chǔ)空間最后一種位置繞到第一種位置，形成邏輯上環(huán)狀空間，供隊(duì)列循環(huán)使用。在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中隊(duì)尾元素，用排頭指針front指向排頭元素前一種位置，因而，從排頭指針front指向后一種位置直到隊(duì)尾指針real指向位置之間所有元素均為隊(duì)列中元素。求解隊(duì)列中元素個(gè)數(shù)辦法是：若front>rear,隊(duì)列中有n-front+rear個(gè)元素（其中n為循環(huán)隊(duì)列容量）;若frontVrear,隊(duì)列中有real-front個(gè)元素；若front=rear,隊(duì)列中有n個(gè)或。個(gè)元素。循環(huán)隊(duì)列是線性構(gòu)造。因此D.在一種容量為15循環(huán)隊(duì)列中，若頭指針front=6,尾指針rear=4,則該循環(huán)隊(duì)列中共有個(gè)元素；若front=4,rear=6,則該循環(huán)隊(duì)列中有個(gè)元素；若front=6,rear=6,則該循環(huán)隊(duì)列中共有個(gè)元素。［解析］本題重要考核對(duì)循環(huán)隊(duì)列存儲(chǔ)形式和入隊(duì)運(yùn)算、出隊(duì)運(yùn)算理解。求解隊(duì)列中元素個(gè)數(shù)辦法是：.若front>rear,隊(duì)列中有n-front+rear個(gè)元素(其中n為循環(huán)隊(duì)列容量)；.若front<rear,隊(duì)列中有real-front個(gè)元素：.若front=rear,隊(duì)列中有n個(gè)或0個(gè)元素。循環(huán)隊(duì)列是線性構(gòu)造。因此13；2；0或151.下列對(duì)于線性鏈表描述中對(duì)的是()A.存儲(chǔ)空間不一定是持續(xù)，且各元素存儲(chǔ)順序是任意B.存儲(chǔ)空間不一定是持續(xù)，且前件元素一定存儲(chǔ)在后件元素前面C.存儲(chǔ)空間必要持續(xù)，且前件元素一定存儲(chǔ)在后件元素前面D.存儲(chǔ)空間必要持續(xù)，且各元素存儲(chǔ)順序是任意［解析］線性鏈表是通過(guò)增長(zhǎng)一種指針域來(lái)把相鄰數(shù)據(jù)元素鏈接成一種線性序列。線性鏈表這種構(gòu)造使得它存儲(chǔ)數(shù)據(jù)空間可以是離散，并不像順序表那樣一定規(guī)定物理上持續(xù)空間。因此A.在線性鏈表插入算法中，若要把結(jié)點(diǎn)q插在結(jié)點(diǎn)p背面，下列操作對(duì)的是()A使結(jié)點(diǎn)p指向結(jié)點(diǎn)q,再使結(jié)點(diǎn)q指向結(jié)點(diǎn)p后件結(jié)點(diǎn)B使結(jié)點(diǎn)q指向p后件結(jié)點(diǎn)，再使結(jié)點(diǎn)p指向結(jié)點(diǎn)qC使結(jié)點(diǎn)q指向結(jié)點(diǎn)P,再使結(jié)點(diǎn)P指向結(jié)點(diǎn)q后件結(jié)點(diǎn)D使結(jié)點(diǎn)P指向q后件結(jié)點(diǎn)，再使結(jié)點(diǎn)q指向結(jié)點(diǎn)P［解析］在修改結(jié)點(diǎn)指針域操作中，有一種操作順序問(wèn)題。比較選項(xiàng)A和B只是操作順序顛倒了一下。A中先使結(jié)點(diǎn)p指向q后，q就稱為p新后件結(jié)點(diǎn)了，原先通過(guò)結(jié)點(diǎn)p指向后件結(jié)點(diǎn)與結(jié)點(diǎn)p脫節(jié)了那么背面一步操作沒有任何意義。使結(jié)點(diǎn)q指向p后件結(jié)點(diǎn)雖然結(jié)點(diǎn)q成為自己后件結(jié)點(diǎn).按照B指定順序操作就不會(huì)浮現(xiàn)引用結(jié)點(diǎn)p指針域之前已經(jīng)把它值修改了情形。至于C和D是命題者設(shè)計(jì)干擾項(xiàng)想讓考生把p和d順序搞混?？偨Y(jié)，做這種類型試題，最佳畫圖。插入結(jié)點(diǎn)：若結(jié)點(diǎn)p背面是結(jié)點(diǎn)S,要在p和S之間插入結(jié)點(diǎn)q,普通先將結(jié)點(diǎn)q指向結(jié)點(diǎn)s,再講結(jié)點(diǎn)p指向q,順序不能顛倒。 刪除結(jié)點(diǎn)：若結(jié)點(diǎn)p背面是結(jié)點(diǎn)q,結(jié)點(diǎn)q背面是結(jié)點(diǎn)s,若要?jiǎng)h除結(jié)點(diǎn)q,只需將結(jié)點(diǎn)p指向s即可。.在長(zhǎng)度為64有序線性表中進(jìn)行順序查找，最壞狀況下需要比較次數(shù)為()A.63 B.64 C.6 D.7［解析］只要是順序查找(不論線性表是有序還是無(wú)序)，都是從表頭到表尾逐個(gè)比較，若相似則結(jié)束查找，否則始終繼續(xù)比較下一種表中元素，指引整個(gè)表都遍歷完。對(duì)于長(zhǎng)度為64線性表，平均要進(jìn)行64/2=321次比較，在最壞狀況下要進(jìn)行64次比較。若采用二分(折半)查找，則最壞狀況下需要比較次數(shù)為log夕4=6次，彈藥注意采用二分(折半)查找條件，必要是線性表采用順序存儲(chǔ)構(gòu)造，并且線性表中元素要有序，這兩個(gè)條件缺一不可。若對(duì)線性鏈表進(jìn)行查找，則不論線性鏈表中元素是有序還是無(wú)序職能采用順序查找。因而本題B..在一種nXm二維線性表中順序查找一種數(shù)據(jù)元素算法時(shí)間復(fù)雜度是()A.O(n+m) B.O(nXm) C.O(n) C.O(m)2 2［解析］在一維線性表中順序查找一種數(shù)據(jù)元素算法時(shí)間復(fù)雜度是O(n),其中n是線性表長(zhǎng)度，二維線性表順序查找辦法和一維線性表相似，只但是是多了一維罷了。在二維表中進(jìn)行順序查找有兩個(gè)辦法：一是把二維線性表當(dāng)作是n個(gè)長(zhǎng)度為m一維線性表，順序查找就是對(duì)這n個(gè)一維線性表依次實(shí)行順序查找，因而它算法時(shí)間復(fù)雜度是0(n)X0(m)=O(nXm)；二是直接把nXm二維線性當(dāng)作一種nXm一維線性表，那么在它當(dāng)中用順序查找法查找一種元素算法時(shí)間復(fù)雜度是。(nXm)。5..下列論述中對(duì)的是。A.線性鏈表是線性鏈?zhǔn)酱鎯?chǔ)構(gòu)造 B.棧與隊(duì)列是非線性構(gòu)造C.雙向鏈表是非線性構(gòu)造 D.只有根結(jié)點(diǎn)二叉樹是線性構(gòu)造［解析］線性表鏈?zhǔn)酱鎯?chǔ)構(gòu)造稱為線性鏈表；棧、隊(duì)列、雙向鏈表都是線性構(gòu)造；樹、二叉樹(不論它有多少個(gè)結(jié)點(diǎn))都是非線性構(gòu)造。因此A6.下列關(guān)于鏈表構(gòu)造論述對(duì)的是。A.線性鏈表、帶鏈棧和帶鏈隊(duì)列結(jié)點(diǎn)構(gòu)造都是相似B.雙向鏈表也就是循環(huán)鏈表C.線性鏈表與帶鏈結(jié)點(diǎn)構(gòu)造是不同D.在循環(huán)鏈表中通過(guò)任意一種結(jié)點(diǎn)可以找到鏈表中其她所有結(jié)點(diǎn)，而在雙向鏈表中做不到這一點(diǎn)［解析］A、C線性鏈表、帶鏈棧和帶鏈隊(duì)列：結(jié)點(diǎn)（表達(dá)數(shù)據(jù)元素）=數(shù)據(jù)域（數(shù)據(jù)元素映像）+指針域（批示后繼元素存儲(chǔ)位置）。B、D雙向鏈表：也叫雙鏈表，是鏈表一種，它每個(gè)數(shù)據(jù)結(jié)點(diǎn)中均有兩個(gè)指針，分表指向直接后繼和直接前驅(qū)。循環(huán)鏈表：循環(huán)鏈表是另一種形式鏈?zhǔn)酱鎯?chǔ)構(gòu)造，它特點(diǎn)是表中最后一種結(jié)點(diǎn)指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一種環(huán)。1-棵度數(shù)為4樹，它4度結(jié)點(diǎn)有1個(gè)，3度結(jié)點(diǎn)有2個(gè)，2度結(jié)點(diǎn)有3個(gè)，1度結(jié)點(diǎn)4個(gè)，問(wèn)它葉子結(jié)點(diǎn)有多少個(gè)？A.5 B.6 C.9 D.11［解析］如果注意觀測(cè)樹構(gòu)造，你會(huì)發(fā)現(xiàn)樹中結(jié)點(diǎn)數(shù)總是比樹中分支數(shù)多，其實(shí)也可以這樣理解：如果在根結(jié)點(diǎn)前面加一條分支線，那么分支數(shù)和結(jié)點(diǎn)數(shù)就同樣多了。在樹結(jié)點(diǎn)里，n度結(jié)點(diǎn)可以射出條分支，葉子結(jié)點(diǎn)是0度結(jié)點(diǎn)，因而它射出分支數(shù)為Oo此題中指引了1到4度結(jié)點(diǎn)個(gè)數(shù)，就可以計(jì)算出樹總分支數(shù)：4X1+3X2+2X3+1X4=20.因而樹總結(jié)點(diǎn)數(shù)是21,減去其她讀書結(jié)點(diǎn)數(shù)10就得到0度結(jié)點(diǎn)（葉子結(jié)點(diǎn)）個(gè)數(shù)11了。因此D.在深度為7滿二叉樹中，葉子結(jié)點(diǎn)個(gè)數(shù)為（）A.32 B.31 C.64 D.63［解析］在滿二叉樹中每層結(jié)點(diǎn)數(shù)都達(dá)到最大值，并且葉子結(jié)點(diǎn)所有出當(dāng)前最底層。第1層（根結(jié)點(diǎn)所在層）有20個(gè)結(jié)點(diǎn)，第2層有21個(gè)結(jié)點(diǎn)，……第n層有2n.i個(gè)結(jié)點(diǎn)。在深度為7滿二叉樹中，第7層有27-1=64個(gè)結(jié)點(diǎn)（所有是葉子結(jié)點(diǎn)），在深度為7滿二叉樹中，共有27.1=64個(gè)結(jié)點(diǎn)，本題為C.某二叉樹有5個(gè)度為2結(jié)點(diǎn)，則該項(xiàng)樹中葉子結(jié)點(diǎn)數(shù)是（）A.10 B.8 C.6 D.4［解析］依照二叉樹性質(zhì)，在任意二叉樹中，度為0結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）數(shù)總是比度為2結(jié)點(diǎn)數(shù)多一種。因此C.某二叉樹中有n個(gè)度為2結(jié)點(diǎn)，則該二叉樹中葉子結(jié)點(diǎn)為。A.n+1 B.n-1 C.2n D.n/2［解析］二叉樹具備這樣一種性質(zhì)：在任意一棵二叉樹中，度為0結(jié)點(diǎn)（葉子結(jié)點(diǎn)）總是比度為2結(jié)點(diǎn)多一種。因此某二叉樹中共有n個(gè)度為2結(jié)點(diǎn)，則該二叉樹葉子結(jié)點(diǎn)數(shù)為n+1。因此本題為A.一科二叉樹中共有70個(gè)葉子結(jié)點(diǎn)和80個(gè)度為1結(jié)點(diǎn)，該二叉樹總結(jié)點(diǎn)數(shù)為（）A.219 B.221 C.229 D.231［解析］二叉樹具備這樣一種性質(zhì)：在任意一棵二叉樹中，度為0結(jié)點(diǎn)（葉子結(jié)點(diǎn)）總是比度為2結(jié)點(diǎn)多一種。本題告知，葉子結(jié)點(diǎn)有70個(gè)，那度為2結(jié)點(diǎn)既有69個(gè)，度為1結(jié)點(diǎn)有80個(gè)，這顆二叉樹共有70+69+80=219個(gè)結(jié)點(diǎn)。因此A.在深度為7滿二叉樹中，度為2結(jié)點(diǎn)個(gè)數(shù)為。［解析］滿二叉樹定義是除最后一層外，每一層所有結(jié)點(diǎn)均有兩個(gè)子結(jié)點(diǎn)（即每一層上結(jié)點(diǎn)數(shù)均達(dá)到最大值）。第1層（根結(jié)點(diǎn)在第1層）擁有結(jié)點(diǎn)數(shù)是2o=l,第2層擁有結(jié)點(diǎn)數(shù)是21=2,第3層擁有結(jié)點(diǎn)數(shù)是22=4,……，第n層擁有結(jié)點(diǎn)數(shù)是2n-l。在深度為7滿二叉樹中，葉子結(jié)點(diǎn)所有在第7層，別的結(jié)點(diǎn)都是2度結(jié)點(diǎn)。在滿二叉樹中，第7層擁有結(jié)點(diǎn)數(shù)是27.1=64。二叉樹具備這樣一種性質(zhì)：在任意一棵二叉樹中，度為0結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2結(jié)點(diǎn)多一種，因此度為2結(jié)點(diǎn)個(gè)數(shù)為64-1=63o.具備8個(gè)結(jié)點(diǎn)完全二叉樹中編號(hào)為4結(jié)點(diǎn)右子結(jié)點(diǎn)編號(hào)為。

A.8B.9A.8B.9C.無(wú)此結(jié)點(diǎn)D.8或9［解析］設(shè)完全二叉樹共有n個(gè)結(jié)點(diǎn)，如果從根結(jié)點(diǎn)開始，按層序（每一層從左到右）用自然數(shù)1,2, n給結(jié)點(diǎn)進(jìn)行編號(hào)（i=l,2, n）,有如下結(jié)論：.若i=l,則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒有父結(jié)點(diǎn)；若i>l,則該結(jié)點(diǎn)父結(jié)點(diǎn)編號(hào)為［i/2］；其中［i/2］表達(dá)取i/2整數(shù)某些。.若2i>n,該結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn)（也無(wú)右子結(jié)點(diǎn)】若2i〈n,則編號(hào)為i結(jié)點(diǎn)左子結(jié)點(diǎn)編號(hào)為2i；.若2i+l>n,該結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn)；若2i+lWn,則編號(hào)為i結(jié)點(diǎn)右子結(jié)點(diǎn)編號(hào)為2i+l。因此本題為C.設(shè)一棵二叉樹中序遍歷成果為DBEACF,前序遍歷成果為ABDECF,則后續(xù)遍歷成果為（）［解析］咱們可以依照前序遍歷成果ABDECF,擬定第一種元素A是根結(jié)點(diǎn)，再看中序遍歷成果DBEACF,A前面DBE應(yīng)當(dāng)在左子樹，A背面FC應(yīng)當(dāng)在右子樹。依照前序遍歷成果和中序遍歷成果，咱們可以推導(dǎo)出：A是根結(jié)點(diǎn)，B是A左結(jié)點(diǎn)，D是B左結(jié)點(diǎn)，E是B右結(jié)點(diǎn)，C是A右結(jié)點(diǎn)，F(xiàn)是C右結(jié)點(diǎn)。畫出二叉圖，對(duì)后續(xù)遍歷成果為DEBFCA..樹是一種簡(jiǎn)樸構(gòu)造，在樹中，所有數(shù)據(jù)元素之間關(guān)系具備明顯特性。［解析］於線性；層次.擁有奇數(shù)個(gè)結(jié)點(diǎn)完全二叉樹中有4個(gè)內(nèi)部結(jié)點(diǎn)（非葉子結(jié)點(diǎn)），請(qǐng)問(wèn)它葉子結(jié)點(diǎn)數(shù)是［解析］5［分析］由于完全二叉樹是自上而下、自左而右從1開始持續(xù)編碼，因而完全二叉樹要么不存在一度結(jié)點(diǎn)（當(dāng)結(jié)點(diǎn)個(gè)數(shù)為奇數(shù)個(gè)數(shù)時(shí)），要么存在一種一度結(jié)點(diǎn)，并且唯一一種一度結(jié)點(diǎn)就是最后編號(hào)為n（n為偶數(shù)）葉子結(jié)點(diǎn)父結(jié)點(diǎn)。而在二叉樹中零度結(jié)點(diǎn)個(gè)數(shù)總比二度結(jié)點(diǎn)個(gè)數(shù)多1,因而擁有4個(gè)二度結(jié)點(diǎn)二叉樹葉子結(jié)點(diǎn)個(gè)數(shù)是4+1=5.總結(jié)，設(shè)n為完全二叉樹結(jié)點(diǎn)數(shù)，n0為葉子結(jié)點(diǎn)數(shù)，,為度為1結(jié)點(diǎn)數(shù)，%為度為2結(jié)點(diǎn)數(shù)，貝I］n=n+n+n,n=n+1。若n為奇數(shù)，則n=0；若n為偶數(shù)，則n=1（注意一定要是完全二叉樹)。.設(shè)一棵完全二叉樹共有700個(gè)結(jié)點(diǎn)，則在該二叉樹中有()個(gè)葉子結(jié)點(diǎn)。［解析］完全二叉樹特點(diǎn)：如果結(jié)點(diǎn)總數(shù)是偶數(shù)則(度為1結(jié)點(diǎn))N斗：如果結(jié)點(diǎn)總數(shù)為奇數(shù)，則N=0；二叉樹始終n=n+l,n=n-1,結(jié)點(diǎn)總數(shù)=11+口+n(將n=n-1,n=l代入公式)；1 0 2 2 0 0 1 2 2 0 1則有700=n+l+n-1,因此n3500 0 0=.具備16個(gè)結(jié)點(diǎn)完全二叉樹深度為()［解析］5；二叉樹特點(diǎn)：具備n個(gè)結(jié)點(diǎn)完全二叉樹深度為［logE+1,因此具備16個(gè)結(jié)點(diǎn)完全二叉樹深度為［log'6］+l=5.在長(zhǎng)度為n有序線性表中進(jìn)行二分查找，最壞狀況下需要比較次數(shù)是A.0(n) B.O(n) C.O(logn) D.Ofnlogn)2 2 2［解析］對(duì)于長(zhǎng)度為n線性表進(jìn)行順序查找，平均要進(jìn)行n/2次比較，在最壞狀況下要進(jìn)行n次比較；對(duì)于長(zhǎng)度為n線性表進(jìn)行二分查找，在最壞狀況下要進(jìn)行l(wèi)og2n次比較(但二分查找規(guī)定線性表是順序存儲(chǔ)有序表)。因而本題答案為C7.請(qǐng)寫出用二分查找法在有序順序表｛1,2,3,4,6,8,9,11｝中查找3比較序列()［解析］4,2,3；可采用擦去法做此類二分法查找序列題：每次從序列中找出中間元素，剛開始時(shí)是4,由于3比4小，只能存在在4之前序列中，于是把4后來(lái)序列擦去，只剩余序列｛1,2,3),在重復(fù)以上過(guò)程直到查找元素或是序列為空。.通過(guò)相鄰數(shù)據(jù)元素互換逐漸使線性表變成有序排序辦法是()A.冒泡排序法 B.簡(jiǎn)樸選取排序法 C.簡(jiǎn)樸插入排序法 D.希爾排序法［解析］冒泡排序法是一種最簡(jiǎn)樸互換類排序辦法，它是通過(guò)相鄰數(shù)據(jù)元素互換逐漸將線性表變成有序，每次只能消除一種逆序。簡(jiǎn)樸插入排序法，是將無(wú)序序列中元素插入有序線性表中，并依次與前面元素進(jìn)行比較，直到不不大于前面元素為止，最多需要比較n(n-1)/2次。希爾排序法是簡(jiǎn)樸插入排序法優(yōu)化，每進(jìn)行依次可以消除各種逆序。簡(jiǎn)樸選取排序法是指掃描整個(gè)線性表，從中選出最小元素，將它互換到表最前面，然后對(duì)剩余子表采用同樣辦法，直到子表空為止。.冒泡排序在最壞狀況下比較次數(shù)是()A.n(n+1)/2 B.nlog2n C.n(n-l)/2 D.n/2［解析］對(duì)于長(zhǎng)度為n線性表，在最壞狀況下，冒泡排序需要進(jìn)行比較次數(shù)是n(n-1)/2.本題答案為C.迅速排序法屬于。A.選取類排序法 B.互換類排序法 C.插入類排序法 D.歸并類排序法［解析］互換類排序法涉及冒泡和迅速排序法；插入類排序法涉及簡(jiǎn)樸插入和希爾排序法；選取類排序法涉及簡(jiǎn)樸選取和堆排序法。本題為B.下列排序辦法中，最壞狀況下比較次數(shù)至少是。A.冒泡排序 B.簡(jiǎn)樸選取排序 C.直接插入排序 D.堆排序［解析］冒泡排序、簡(jiǎn)樸選取排序和直接插入排序法在最壞狀況下比較次數(shù)為n(n-1)/2?而堆排序法在最壞狀況下比較次數(shù)為O(nlogn)±本題為D.長(zhǎng)度為10順序表首地址是1023開始，順序表中每個(gè)元素長(zhǎng)度為2,在第4個(gè)元素前面插入一種元素和刪除第7個(gè)元素后，順序表總長(zhǎng)度還是不變。問(wèn)順序表中第5個(gè)元素在執(zhí)行插入和刪除操作后在順序表中存儲(chǔ)地址是()A.1028 B.1029 C.1031 D.1033［解析］由于問(wèn)是本來(lái)順序表中第5個(gè)元素，它在插入操作后變成了第6個(gè)元素(由于插入元素在它前面)。由于刪除第7個(gè)元素在它背面，不會(huì)影響它在順序表中排位。因而在執(zhí)行插入和刪除操作后原先順序表中第5個(gè)元素變成了新順序表中第6個(gè)元素。再按照線性表隨機(jī)存取地址計(jì)算公式ADD(ai)=ADD(al)+(i-1)Xk計(jì)算ADD(a6)=ADD(al)+(6-1)X2=1023+5X2=1033,因此選D.是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序規(guī)則，并且每一種規(guī)則都是有效，且是明確，此順序?qū)⒃谟邢薮螖?shù)下終結(jié)。［解析］算法.在最壞狀況下，冒泡排序時(shí)間復(fù)雜度為,簡(jiǎn)樸插入排序時(shí)間復(fù)雜度為,希爾排序時(shí)間復(fù)雜度為,簡(jiǎn)樸選取排序時(shí)間復(fù)雜度為,堆排序時(shí)間復(fù)雜度為O［解析］O(n(n-1)/2)；O(n(n-1)/2)；O(ni.s)；0(n(n-1)/2)；O(nlog2n)；.如下排序技術(shù)中屬于互換類排序法有，屬于插入類排序法有,屬于選取類排序法有。A.簡(jiǎn)樸插入排序B.冒泡排序C.希爾排序D.堆排序E.迅速排序F.簡(jiǎn)樸選取排序［解析］BE；AC；DF.算法中各操作之間執(zhí)行順序稱為()。描述算法工具普通有()、()、()［解析］算法控制構(gòu)造；老式流程圖；N-S構(gòu)造化流程圖、算法描述語(yǔ)言.請(qǐng)寫出冒泡排序法對(duì)序列｛5,1,7,3,1,6,9,3,2,7,6)進(jìn)行第一遍掃描后排序成果是.

［解析］｛1,1,5,3,2,6,7,3,6,7,9｝［分析］冒泡排序法基本過(guò)程：一方面，從表頭開始往后掃描線性表，在掃描過(guò)程中逐次比較相鄰兩個(gè)元素大小，若前面元素不不大于背面元素，則將她們互換，這樣最大者互換到了表最背面；然后，從后往前掃描剩余線性表，同樣，在掃描過(guò)程中逐次比較相鄰兩個(gè)元素大小若背面元素不大于前面元素，則將她們互換看，這樣最小者互換到了表最前面;從前去后和從后往前掃描一種來(lái)回稱為一遍；對(duì)剩余線性表重復(fù)上述過(guò)程，直到剩余線性表變?yōu)榭諡橹?，這樣線性表就變?yōu)橛行蛄?。?dāng)前咱們來(lái)看看對(duì)線性表｛5,1,7,3,1,6,9,3,2,716｝從前去后進(jìn)行掃描過(guò)程:5>1,5和1互換位置得到｛1,5,7,3,1,6,9,3,2,7,6)5<7不論，繼續(xù)往后掃描，掃描到71,6,9,3,2,7,6)7>3,7和31,6,9,3,2,7,6)7>1,7和7>1,7和1互換位置得到7>6,77>6,7和6互換位置得到｛1,5,3,1,6,7,9,3,2,7,6)7<9不論，繼續(xù)往后掃描，掃描到99>3,9和39>3,9和3互換位置得到｛1,5,3,1,6,7,3,9,2,7,6)9>2,9和2互換位置得到｛1,5,3,1,6,7,3,2,9,7,6)6,7,3,2,7,9,6｝9>7,9和7互換位置得到｛1,5,3,1,9>6,9和6互換位置得到6,7,3,2,7,9,6｝從前去后掃描結(jié)束，9互換到了線性表最后。當(dāng)前咱們來(lái)看看對(duì)剩余線性表｛1,5,3,1,6,7,3,2,7,6,9｝從后往邁進(jìn)行掃描過(guò)程6<7,6和7互換位置得到｛1,5,3,1,6,7,3,2,6,7,9)6>2不論，繼續(xù)往前掃描，掃描到22<3,2和3互換位置得到｛1,5,3,1,6,7,2,3,6,7,9)2<7,2和7互換位置得到｛1,5,3,1,6,2,7,3,6,7,9)2<6,2和6互換位置得到{1,5,3,1,2,6,7,3,6,7,9)2>1不論，繼續(xù)往前掃描，掃描到11<3,1和3互換位置得到｛1,5,1,3,2,6,7,3,6,7,9｝1<5,1和5互換位置得到｛1,1,5,3,2,6,7,3,6,7,9）.請(qǐng)寫出用希爾排序法對(duì)序列｛5,1,7,3,1,6,9,3,2,7,6）進(jìn)行第一遍掃描后排序成果是.［解析］｛5,1,3,2,1,6,9,7,3,7,6｝希爾排序法基本思想：將整個(gè)無(wú)序序列分割成若干子序列分別進(jìn)行插入排序（插入排序：開始線性表中只有第1個(gè)元素，然后從線性表第2個(gè)元素開始指引最后一種元素，逐次將其中每一種元素插入到前面已有序子表中）子序列分割辦法：將相隔某個(gè)增量h（h=n/2k（k=l,2,3…［logp］n為待排序線性表長(zhǎng)度））元素構(gòu)成一種子序列。在排序過(guò)程中，逐次減小這個(gè)增量，最后當(dāng)h減到1時(shí)進(jìn)行一次插入排序，排序完畢。按以上分析，第1次分割子序列h=nZ2=ll/2=5,構(gòu)成子序列有｛5,6｝、｛1,9｝、｛7,3｝、｛3,2）、｛1,7｝、6（最后一種元素6成單），每一種序列進(jìn)