軍隊(duì)文職-計(jì)算機(jī)-數(shù)據(jù)結(jié)構(gòu)與算法-強(qiáng)化練習(xí)一

軍隊(duì)文職-計(jì)算機(jī)-數(shù)據(jù)結(jié)構(gòu)與算法-強(qiáng)化練習(xí)一[單選題]1.采用順序搜索方法查找長度為n的順序表時(shí)，搜索成功的平均搜索長度為()。A.（n-1）/2B.（n+1）/2C.nD.n/2（江南博哥）正確答案：B參考解析：搜索的最好情況是第一個(gè)元素即想要查找的元素，最壞的情況是最后一個(gè)元素即想要查找的元素，所以平均查找長度是（n+l）/2。[單選題]2.將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法，其時(shí)間復(fù)雜度為()。A.O（m）B.O（m+n）C.O（1）D.O（n）正確答案：A參考解析：將長度為n的單鏈表接在長度為m的單鏈表之后，需先遍歷長度m的單鏈表，找到最后一個(gè)節(jié)點(diǎn)，然后將n連接在m之后。[單選題]3.設(shè)一棵二叉樹的深度為k，則該二叉樹中最多有()個(gè)節(jié)點(diǎn)。A.1B.C.2D.正確答案：D參考解析：[單選題]4.設(shè)輸入序列是1，2，3，……，n，經(jīng)過棧的作用后輸出序列的第一個(gè)元素是n，則輸出序列中第i個(gè)輸出元素是()。A.n-1-iB.n-iC.n+1-iD.不能確定正確答案：C參考解析：經(jīng)過棧后的輸出序列中第一個(gè)元素為n，代表從1至n是一次性全部入棧的，所以出棧序列剛好是入棧序列的倒序。[單選題]5.由圈權(quán)值為9.2.5.7的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一顆哈夫曼樹，該樹的帶權(quán)路徑長度為()。A.23B.37C.44D.46正確答案：C參考解析：[單選題]6.二叉排序樹中左子樹上所有節(jié)點(diǎn)的值均()根節(jié)點(diǎn)的值。A.＜B.=C.＞D.！=正確答案：A參考解析：二叉排序樹的左子樹的節(jié)點(diǎn)的值全部小于根節(jié)點(diǎn)的值，并且根節(jié)點(diǎn)的值小于右子樹左右節(jié)點(diǎn)的值。[單選題]7.在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是()。A.希爾排序B.起泡排序C.插入排序D.選擇排序正確答案：D參考解析：每一趟從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個(gè)元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。[單選題]8.對(duì)特殊矩陣采用壓縮存儲(chǔ)的目的主要是為了()。A.去掉矩陣中的多余元素B.減少不必要的存儲(chǔ)空間C.表達(dá)變得簡單D.對(duì)矩陣元素的存取變得簡單正確答案：B參考解析：在特殊矩陣中，有很多值相同的元素并且他們的分布有規(guī)律，沒有必要為值相同的元素重復(fù)存儲(chǔ)。[單選題]9.設(shè)指針變量p指向單鏈表中節(jié)點(diǎn)A，若刪除單鏈表中節(jié)點(diǎn)A，則需要修改指針的操作序列為()。A.q=p-＞next；p-＞data=q-＞data；p-＞next=q-＞next；free（q）；B.q=p-＞next；p-＞data=q-＞data；free（q）；C.q=p-＞next；p-＞next=q-＞next；free（q）；D.q=p-＞next；q-＞data=p-＞data；p-＞next=q-＞next；free（q）；正確答案：A參考解析：應(yīng)先使指針q指向節(jié)點(diǎn)A之后的節(jié)點(diǎn)，以防鏈表斷裂，然后刪除節(jié)點(diǎn)q，最后將刪除的節(jié)點(diǎn)q的存儲(chǔ)空間釋放。[單選題]10.算法分析的目的是()。A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中輸入和輸出的關(guān)系C.分析算法的效率以求改進(jìn)D.分析算法的易懂性和文檔性正確答案：C參考解析：算法分析的目的是分析算法的效率以求改進(jìn)。[單選題]11.設(shè)無向圖G中有n個(gè)頂點(diǎn)e條邊，則其對(duì)應(yīng)的鄰接表中的表頭節(jié)點(diǎn)和表節(jié)點(diǎn)的個(gè)數(shù)分別為()。A.e，nB.n.eC.2n，eD.n，2e正確答案：D參考解析：使用鄰接表存儲(chǔ)圖，圖有多少節(jié)點(diǎn)，鄰接表就有多少個(gè)表頭，無向圖的表節(jié)點(diǎn)個(gè)數(shù)為2e。[單選題]12.在向下生成的堆棧中，如果入棧指令PUSHX的操作定義為：SP←（SP）+1，M（SP）←M（X），則出棧指令POPX應(yīng)定義為()。A.SP←（SP）-1，M（X）←M（SP）B.SP←（SP）+1，M（X）←M（SP）C.M（X）←M（SP），SP←（SP）-1D.M（X）←M（SP），SP←（SP）+1正確答案：C參考解析：入棧是先定位棧頂指針然后存儲(chǔ)數(shù)據(jù)，出棧是先出數(shù)據(jù)，然后再定位棧頂指針。[單選題]13.下列說法中不正確的是()。A.圖的遍歷過程中每一頂點(diǎn)僅被訪問一次B.遍歷圖的基本方法有深度優(yōu)先搜索和廣度優(yōu)先搜索兩種C.圖的深度優(yōu)先搜索的方法不適用于有向圖D.圖的深度優(yōu)先搜索是一個(gè)遞歸過程正確答案：C參考解析：圖的深度優(yōu)先搜索的方法對(duì)于有向圖和無向圖都適用。[單選題]14.樹最適合用來表示()。A.元素之間無聯(lián)系的數(shù)據(jù)B.無序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.有序數(shù)據(jù)元素正確答案：C參考解析：樹是一種具有層次結(jié)構(gòu)的非線性結(jié)構(gòu)，所以樹適合用來存儲(chǔ)元素之間具有分支層次關(guān)系的數(shù)據(jù)。[單選題]15.設(shè)二叉排序樹上有n個(gè)節(jié)點(diǎn)，則在二叉排序樹上查找節(jié)點(diǎn)的平均時(shí)間復(fù)雜度為()，A.O（n-1）B.O（n）C.D.正確答案：D參考解析：[單選題]16.從一個(gè)具有N個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于X結(jié)點(diǎn)時(shí)，查找成功的情況下，需平均比較()結(jié)點(diǎn)。A.NB.N/2C.（N-1）/2D.（N+1）/2正確答案：D參考解析：[單選題]17.設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為（20，15，14，18，21，36，40，10），則以20為基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為()。A.10，15，14，18，20，36，40，21B.15，10，14，18，20，36，40，21C.10，15，14，20，18，40，36，21D.10，15，14，18，20，40，36，21正確答案：A參考解析：快速排序的每趟排序在待排序列中選取一個(gè)數(shù)為基準(zhǔn)，將序列劃分為兩段，一段的值比基準(zhǔn)值小，另一段大于或等于基準(zhǔn)值。在快速排序中通常有兩個(gè)指針分別為i和j，j從后向前遍歷，找第一個(gè)小于基準(zhǔn)值的節(jié)點(diǎn)，將值交換，i從前向后遍歷，找到第一個(gè)大于或等于基準(zhǔn)值的節(jié)點(diǎn)，將值交換，重復(fù)此過程，直至i和j指向同一節(jié)點(diǎn)，一趟排序結(jié)束。[單選題]18.設(shè)一組初始記錄關(guān)鍵字的長度為8，則最多經(jīng)過()趟插入排序可以得到有序序列。A.8B.7C.9D.6正確答案：B參考解析：插入排序的每一趟在待排元素中取出第一個(gè)元素，移至有序序列的適當(dāng)?shù)奈恢?，所以共八個(gè)關(guān)鍵字的序列，最多經(jīng)過7趟插入排序就可以得到一個(gè)有序序列。[單選題]19.雙向鏈表中有兩個(gè)指針域llink和rlink，分別指向前驅(qū)和后繼，設(shè)β指向表中的一個(gè)結(jié)點(diǎn)，q指向一待插入結(jié)點(diǎn)，現(xiàn)要求在p前插入q，則正確的插人為()。A.B.C.D.正確答案：D參考解析：p→llink→rlink=q；q→rlink=p；q→llink=p→llink；p→llink=q[單選題]20.設(shè)指針變量front表示鏈?zhǔn)疥?duì)列的隊(duì)頭指針，指針變量rear表示鏈?zhǔn)疥?duì)列的隊(duì)尾指針，指針變量s指向?qū)⒁腙?duì)列的節(jié)點(diǎn)X，則入隊(duì)列的操作序列為()。A.s-＞next=rear；rear=s；B.front-＞next=s；front=s；C.rear-＞next=s；rear=s；D.s-＞next=front；front=s；正確答案：C參考解析：向隊(duì)列插入元素，即入隊(duì)操作，應(yīng)該在隊(duì)尾進(jìn)行，所以需要修改尾指針，實(shí)現(xiàn)新節(jié)點(diǎn)的入隊(duì)。[單選題]21.在一個(gè)單鏈表中，若p所指的結(jié)點(diǎn)不是最后結(jié)點(diǎn)，則刪除p所指的結(jié)點(diǎn)的后繼結(jié)點(diǎn)的正確操作是()。A.p=p-＞nextB.p-＞next=p-＞nextC.p-＞next=p-＞next-＞nextD.p-＞next=p正確答案：C參考解析：本題考查的是單鏈表的刪除操作。在已知鏈表中元素插入或刪除確切位置的情況下，在單鏈表中插入或刪除一個(gè)結(jié)點(diǎn)時(shí)，僅需修改指針而無須移動(dòng)元素。[單選題]22.設(shè)一組初始記錄關(guān)鍵字序列為（Q，H，C，Y，P，A，M，S，R，D，F(xiàn)，X），則按字母升序的第一趟冒泡排序結(jié)束后的結(jié)果是()。A.A，D，C，R，F(xiàn)，Q，M，S，Y，P，H，XB.P，A，C，S，Q，D，F(xiàn)，X，R，H，M，YC.F，H，C，D，P，A，M，Q，R，S，Y，XD.H，C，Q，P，A，M，S，R，D，F(xiàn)，X，Y正確答案：D參考解析：每一趟冒泡排序從第一個(gè)元素開始，相鄰的兩個(gè)元素進(jìn)行比較，若是降序則進(jìn)行交換，一趟排序完成后，值最大的元素被移至序列的末尾。[單選題]23.無向圖G=（V，E），其中V={a，b，c，d，e，f}，E={（a，b），（a，e），（a，c），（b，e），（c，f），（e，d）}，對(duì)該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是()。A.a，b，e，c，d，fB.a，c，f，e，b，dC.a，e，b，c，f，dD.a，e，d，f，c，b正確答案：C參考解析：假設(shè)給定圖G的初態(tài)是所有頂點(diǎn)均未曾訪問過。在G中任選一頂點(diǎn)v為初始出發(fā)點(diǎn)（源點(diǎn)），則深度優(yōu)先遍歷可定義如下：首先訪問出發(fā)點(diǎn)v，并將其標(biāo)記為已訪問過：然后依次從v出發(fā)搜索v的每個(gè)鄰接點(diǎn)w。若w未曾訪問過，則以w為新的出發(fā)點(diǎn)繼續(xù)進(jìn)行深度優(yōu)先遍歷，直至圖中所有和源點(diǎn)v有路徑相通的頂點(diǎn)（亦稱為從源點(diǎn)可達(dá)的頂點(diǎn)）均已被訪問為止。若此時(shí)圖中仍有未訪問的頂點(diǎn)，則另選一個(gè)尚未訪問的頂點(diǎn)作為新的源點(diǎn)重復(fù)上述過程，直至圖中所有頂點(diǎn)均已被訪問為止。[單選題]24.算法指的是()。A.計(jì)算機(jī)程序B.解決問題的計(jì)算方法C.排序算法D.解決問題的有限運(yùn)算序列正確答案：D參考解析：算法是精確定義的一系列規(guī)則，它指出怎樣從給定的輸入信息經(jīng)過有限步驟產(chǎn)生所求的輸出信息。它既不是計(jì)算機(jī)程序，也不是某種算術(shù)運(yùn)算。[單選題]25.若允許表達(dá)式內(nèi)多種括號(hào)混合嵌套，則為檢查表達(dá)式中括號(hào)是否正確配對(duì)的算法，通常選用的輔助結(jié)構(gòu)是()。A.棧B.線性表C.隊(duì)列D.二叉排序樹正確答案：A參考解析：棧（stack）又稱為堆棧，它是一種運(yùn)算受限的線性表。其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算，這一端被稱為棧頂，相對(duì)地，把另一端稱為棧底。向一個(gè)棧插入新元素稱作進(jìn)棧、入?；驂簵?，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個(gè)棧刪除元素稱作出棧或退棧，它是把棧頂元素刪除，使其相鄰的元素成為新的棧頂元素。[單選題]26.含n個(gè)頂點(diǎn)的連通圖中的任意一條簡單路徑，其長度不可能超過()。A.n-1B.nC.1D.n/2正確答案：A參考解析：若超過n-l，則路徑中必存在重復(fù)的頂點(diǎn)。[單選題]27.判定一個(gè)棧ST（最多元素為m0）為滿的條件是()。A.ST-＞top=m0-1B.ST-＞top=0C.ST-＞top＜＞m0D.ST-＞top＜＞0正確答案：A參考解析：如果一個(gè)棧的棧頂指針為m0-1，則該棧為滿。[單選題]28.A.推排序B.快速排序C.并列排序D.直接選擇排序正確答案：A參考解析：[單選題]29.當(dāng)利用大小為n的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定top=n表示?？眨瑒t向這個(gè)棧插入一個(gè)元素時(shí)，首先應(yīng)該執(zhí)行下列哪個(gè)語句修改的top指針()。A.top++1B.top--C.top=0D.top正確答案：B[單選題]30.設(shè)一棵三叉樹中有2個(gè)度數(shù)為1的節(jié)點(diǎn)，2個(gè)度數(shù)為2的節(jié)點(diǎn)，2個(gè)度數(shù)為3的節(jié)點(diǎn)，則該三叉鏈樹中有()個(gè)度數(shù)為0的節(jié)點(diǎn)。A.8B.6C.7D.5正確答案：C參考解析：度為0的節(jié)點(diǎn)個(gè)數(shù)為1+2×1+2×2+2×3-2-2-2=7。[單選題]31.下列文件的物理結(jié)構(gòu)中，不利于文件長度動(dòng)態(tài)增長的文件物理結(jié)構(gòu)是()。A.順序結(jié)構(gòu)B.鏈?zhǔn)浇Y(jié)構(gòu)C.索引結(jié)構(gòu)D.Hash結(jié)構(gòu)正確答案：A參考解析：順序結(jié)構(gòu)又稱連續(xù)結(jié)構(gòu)。這是一種最簡單的物理結(jié)構(gòu)，它把邏輯上連續(xù)的文件信息依次存放在連續(xù)編號(hào)的物理塊中，只要知道文件在存儲(chǔ)設(shè)備上的起始地址（首塊號(hào)）和文件長度（總塊數(shù)），就能很快地進(jìn)行存取。這種結(jié)構(gòu)的優(yōu)點(diǎn)是訪問速度快，缺點(diǎn)是文件長度增加困難。因此，順序結(jié)構(gòu)的磁盤空間利用率不高，不利于文件長度動(dòng)態(tài)增長。[單選題]32.樹形結(jié)構(gòu)的特點(diǎn)是：一個(gè)結(jié)點(diǎn)可以有()。A.多個(gè)直接前驅(qū)B.多個(gè)直接后繼C.多個(gè)前驅(qū)D.一個(gè)后繼正確答案：B參考解析：樹的唯一根節(jié)點(diǎn)無前驅(qū)，葉子結(jié)點(diǎn)可以有多個(gè)且無后繼，樹的其他結(jié)點(diǎn)可以有多個(gè)后繼但只能有一個(gè)前驅(qū)。[單選題]33.執(zhí)行一趟快速排序能夠得到的序列是()。A.[41，12，34，45，27]55[72，63]B.[12，27，45，41]55[34，63，72]C.[63，12，34，45，27]55[41，72]D.[45，34，12，41]55[72，63，27]正確答案：A參考解析：一趟快速排序的結(jié)果為基準(zhǔn)值的左邊節(jié)點(diǎn)的值全部小于基準(zhǔn)值，基準(zhǔn)右邊的節(jié)點(diǎn)的值全部不小于基準(zhǔn)值。[單選題]34.假設(shè)以S和X分別表示進(jìn)棧和出棧操作，則對(duì)輸入序列a，B，c，d，E進(jìn)行一系列棧操作SSXSXSSXXX之后，得到的輸出序列為()。A.B，c，E，d，aB.B，E，c，a，dC.E，c，B，d，aD.c，E，B，a，d正確答案：A參考解析：a，B進(jìn)棧（SS），B出棧（X），輸出“B”，c進(jìn)棧（S），c出棧（X），輸出“c”，d，E進(jìn)棧（SS），E，d，a出棧（XXX），輸出“E，d，a”，所以結(jié)果為B，c，E，d，a。[單選題]35.設(shè)循環(huán)隊(duì)列的存儲(chǔ)空間為Q（1：30），初始狀態(tài)front=rear=30，先經(jīng)過一系列入隊(duì)和退隊(duì)運(yùn)算后，front=10，rear=10，則循環(huán)隊(duì)列中的元素個(gè)數(shù)為()。A.30B.0C.29D.0或30正確答案：D參考解析：當(dāng)frontrear時(shí)，循環(huán)隊(duì)列中的元素個(gè)數(shù)為N-front+rear（N為循環(huán)隊(duì)列容量）。當(dāng)front=rear時(shí)，循環(huán)隊(duì)列中的元素個(gè)數(shù)可能為空，也可能為滿。[單選題]36.對(duì)n個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助存儲(chǔ)空間大致為()。A.O（n）B.O（1）C.D.正確答案：C參考解析：[單選題]37.A.0（n）B.0（n^2）C.O（n*i）D.0（n+1）正確答案：B參考解析：觀察可知，程序段S的執(zhí)行頻度為T（n）=n^2，得時(shí)間復(fù)雜度T（n）=O（n^2）。[單選題]38.下面敘述正確的是()。A.二叉樹是特殊的樹B.二叉樹等價(jià)于度為2的樹C.完全二叉樹必為滿二叉樹D.二叉樹的左右子樹有次序之分正確答案：D參考解析：二叉樹是一類與樹不同的數(shù)據(jù)結(jié)構(gòu)。兩者的區(qū)別在于：二叉樹可以是空集；二叉樹的任一結(jié)點(diǎn)都有兩棵子樹，并且這兩棵子樹之間有次序關(guān)系，也就是說，它們的位置不能交換。[單選題]39.設(shè)有5000個(gè)元素，希望用最快的速度挑選出前10個(gè)最大的，采用()方法最好。A.希爾排序B.歸并排序C.快速排序D.堆排序正確答案：D參考解析：堆排序不必將整個(gè)序列排序即可確定前若干個(gè)最大（或最?。┰?。[單選題]40.如果節(jié)點(diǎn)A有3個(gè)兄弟，B是A的雙親，則節(jié)點(diǎn)B的度是()。A.3B.4C.1D.2正確答案：B參考解析：節(jié)點(diǎn)A有3個(gè)兄弟，B是A的雙親，則節(jié)點(diǎn)B的度是4。[單選題]41.n個(gè)頂點(diǎn)的連通圖至少有多少條邊()。A.n-1B.nC.n+1D.0正確答案：A參考解析：至少要有（n-1）條邊（也就是樹）才能保證圖為連通圖。[單選題]42.散列技術(shù)中的沖突指的是()。A.兩個(gè)元素具有相同的序號(hào)B.數(shù)據(jù)元素過多C.兩個(gè)元素的鍵值不同，而其他屬性相同D.不同鍵值的元素對(duì)應(yīng)于相同的存儲(chǔ)地址正確答案：D參考解析：散列技術(shù)中的沖突指的是不同鍵值的元素對(duì)應(yīng)于相同的存儲(chǔ)地址。[單選題]43.討論樹、森林和二叉樹的關(guān)系，目的是為了()。A.借助二叉樹上的運(yùn)算方法去實(shí)現(xiàn)對(duì)樹的一些運(yùn)算B.將樹、森林轉(zhuǎn)換成二叉樹C.體現(xiàn)一種技巧，沒有什么實(shí)際意義D.將樹、森林按二叉樹的存儲(chǔ)方式進(jìn)行存儲(chǔ)并利用二叉樹的算法解決樹的有關(guān)問題正確答案：D參考解析：討論樹、森林和二叉樹的關(guān)系，目的是為了將樹、森林按二叉樹的存儲(chǔ)方式進(jìn)行存儲(chǔ)并利用二叉樹的算法解決樹的有關(guān)問題。[單選題]44.若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為()。A.1和5B.2和4C.4和2D.5和1正確答案：B參考解析：循環(huán)隊(duì)列是解決假溢出的問題，通常把一維數(shù)組看成首尾相接。在循環(huán)意義下的加1運(yùn)算通常用求模運(yùn)算來實(shí)現(xiàn)。所以入隊(duì)和出隊(duì)時(shí)的操作分別為：rear=（rear+1）%m，front=（front+1）%m。[單選題]45.在平衡二叉樹中()。A.不存在度為1的節(jié)點(diǎn)B.任意節(jié)點(diǎn)的左、右子樹節(jié)點(diǎn)數(shù)目相同C.任意節(jié)點(diǎn)的左、右子樹高度相同D.任意節(jié)點(diǎn)的左右子樹高度之差的絕對(duì)值不大于1正確答案：D參考解析：平衡二叉樹又稱AVL樹，它或者是一棵空樹，或具有下列性質(zhì)的二叉樹：（1）左子樹和右子樹都是平衡二叉樹：（2）左子樹和右子樹的高度之差的絕對(duì)值不超過1。二叉樹上節(jié)點(diǎn)的平衡因子定義為該節(jié)點(diǎn)的右子樹的高度減去它的左子樹的高度。可見，平衡二叉樹上所有節(jié)點(diǎn)的平衡因子只可能是-1，0，1。只要二叉樹上有一個(gè)節(jié)點(diǎn)的平衡因子的絕對(duì)值大于1，則該二叉樹就是不平衡的。[單選題]46.設(shè)某完全無向圖中有n個(gè)頂點(diǎn)，則該完全無向圖中有()條邊。A.n（n-1）/2B.n（n-1）C.n+1D.n正確答案：A參考解析：因?yàn)闊o向圖的邊是沒有方向的，所以完全無向圖有n（n-l）/2條邊。[單選題]47.設(shè)二叉排序樹中有n個(gè)節(jié)點(diǎn)，則在二叉排序樹的平均查找長度為()。A.O（n）B.C.O（1）D.O（n-1）正確答案：B參考解析：[單選題]48.以下哪一個(gè)不是棧的基本運(yùn)算()。A.刪除棧頂元素B.刪除棧底元素C.判斷棧是否為空D.將棧置為空棧正確答案：B參考解析：棧的基本運(yùn)算有入棧、出棧（刪除棧頂元素）、初始化、置空、判斷是否為空或滿、提取棧頂元素等，對(duì)棧元素的操作都是在棧頂進(jìn)行的。[單選題]49.設(shè)森林F中有三棵樹，第一、第二、第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為M1、M2、和M3，與森林F對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是多少()。A.M1B.M1+M2C.M3D.M2+M3正確答案：D參考解析：第一棵樹構(gòu)成根和左子樹，因此右子樹上的結(jié)點(diǎn)個(gè)數(shù)就是M2+M3，故D為正確答案。[單選題]50.以下的算法設(shè)計(jì)中，哪一個(gè)是以獲取問題最大優(yōu)解為目標(biāo)？()A.回溯法B.分治法C.動(dòng)態(tài)規(guī)則D.逆推正確答案：C[單選題]51.在二叉排序樹中插入一個(gè)節(jié)點(diǎn)的時(shí)間復(fù)雜度為()。A.O（1）B.O（n）C.D.O（n-1）正確答案：B參考解析：在二叉排序樹中進(jìn)行插入時(shí)最壞情況下時(shí)間復(fù)雜度是O（n）。[單選題]52.隊(duì)列是一種()的線性表。A.先進(jìn)先出B.只能插入C.先進(jìn)后出D.只能刪除正確答案：A參考解析：隊(duì)列的特點(diǎn)是先進(jìn)先出、后進(jìn)后出。[單選題]53.如果一棵二叉樹結(jié)點(diǎn)的先根遍歷序列是A、B、C，后根遍歷序列是C、B、A，則該二叉樹結(jié)點(diǎn)的中根遍歷序列()。A.必為A、B、CB.必為A、C、BC.必為B、C、AD.不能確定正確答案：D參考解析：[單選題]54.AOV網(wǎng)是一種()。A.有向圖B.無向無環(huán)圖C.無向圖D.有向無環(huán)圖正確答案：D參考解析：AOV網(wǎng)是一種有向無環(huán)圖，即沒有回路。[單選題]55.對(duì)于長度為m（m＞1）的指定序列，通過初始為空的一個(gè)棧、一個(gè)隊(duì)列后，錯(cuò)誤的敘述是()。A.入棧序列與出棧序列關(guān)系為1：1，而入隊(duì)序列與出隊(duì)序列關(guān)系是1：n（n≥1）B.若入棧和入隊(duì)的序列相同，則出棧序列和出隊(duì)序列可以互為逆序C.入隊(duì)序列與出隊(duì)序列關(guān)系為1：1，而入棧序列與出棧序列關(guān)系是1：n（n≥1）D.若入棧和入隊(duì)的序列相同，則出棧序列和出隊(duì)序列可能相同正確答案：A參考解析：隊(duì)列的元素按特點(diǎn)是先進(jìn)先出。對(duì)于隊(duì)列，元素的進(jìn)入次序和出隊(duì)的次序相同，例如，入隊(duì)的序列為a、b、c，則出隊(duì)的序列也為a、b、c。對(duì)于棧則不同，棧的運(yùn)算特點(diǎn)是后進(jìn)先出。若入棧序列為a、b、c，則出棧序列可能為a、b、c，a、c、b，b、a、c，b、c、a或者c、b、a，而c、a、b則不行，因此，入棧序列與出棧序列關(guān)系為1：1，而入隊(duì)序列與出隊(duì)序列關(guān)系為1：n（n≥1）。[單選題]56.鏈表不具有的特點(diǎn)是()。A.不必事先估計(jì)存儲(chǔ)空間B.可隨機(jī)訪問任一元素C.插入刪除不需要移動(dòng)元素D.所需空間與線性表長度成正比正確答案：B參考解析：鏈表采用的是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，它克服了順序存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)：①它的結(jié)點(diǎn)空間可以動(dòng)態(tài)申請(qǐng)和釋放；②它的數(shù)據(jù)元素的邏輯次序靠結(jié)點(diǎn)的指針來指示，不需要移動(dòng)數(shù)據(jù)元素。但是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也有不足之處：①每個(gè)結(jié)點(diǎn)中的指針域需額外占用存儲(chǔ)空間；②鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種非隨機(jī)存儲(chǔ)結(jié)構(gòu)。[單選題]57.對(duì)于只在表的首尾兩端進(jìn)行插入操作的線性表，宜采用的存儲(chǔ)結(jié)構(gòu)是()。A.順序表B.用頭指針表示的單循環(huán)鏈表C.用尾指針表示的單循環(huán)鏈表D.單鏈表正確答案：C參考解析：本題考查的是線性表的插入與刪除操作。當(dāng)線性表用尾指針表示的單循環(huán)鏈表存儲(chǔ)時(shí)，很容易找到線性表的首、尾元素。此時(shí)，尾指針的后繼即是線性表的首端。[單選題]58.已知某二叉樹的中序、層序序列分別為DBAFCE、FDEBCA，則該二叉樹的后序序列為()。A.DBACEFB.DABECFC.BCDEAFD.ABDCEF正確答案：D參考解析：[單選題]59.在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端（即下標(biāo)為0的單元）作為棧底，以top作為棧頂指針，當(dāng)出棧時(shí)，top的變化為()。A.top=top-1；B.top=top+1；C.不變D.top=0；正確答案：A參考解析：以top作為棧頂指針，當(dāng)出棧時(shí)，top的變化為top=top-1。[單選題]60.若一個(gè)棧以向量V[1..n]存儲(chǔ)，初始棧頂指針top為n+1，則下面x進(jìn)棧的正確操作是()。A.top=top+1；V[top]=xB.V[top]=x；top=top+1C.top=top-1；V[top]=xD.V[top]=x；top=top-1正確答案：C參考解析：棧是運(yùn)算受限的線性表，只允許在棧頂進(jìn)行插入和刪除操作。本題中棧頂指針為n+1，該數(shù)組將棧頂放在了下標(biāo)大的一端，所以在進(jìn)行入棧操作時(shí)top指針應(yīng)該進(jìn)行減1操作。通常元素進(jìn)棧的操作為：先移動(dòng)棧頂指針后存入元素。[單選題]61.有種關(guān)系模式R=＜U，F(xiàn)＞，U={C，T，H，X，S}，F(xiàn)={C→T，（H，X）→C，（H，T）→YC，（H，S）→Y}則表示模式R的碼是()。A.CB.（H，S）C.（H，Y）D.（H，T）正確答案：B參考解析：由題可得如下推導(dǎo)：（H，S）+R，（H，R）+C，C--4T，（H，T）--4R，故可知（H，S）為關(guān)系模式的碼。[單選題]62.在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的數(shù)據(jù)結(jié)構(gòu)是()。A.邏輯B.存儲(chǔ)C.邏輯和存儲(chǔ)D.物理正確答案：A參考解析：存儲(chǔ)結(jié)構(gòu)、物理結(jié)構(gòu)是同一概念的兩個(gè)術(shù)語，都是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示，邏輯結(jié)構(gòu)是數(shù)據(jù)元素間關(guān)系的描述，與所用的計(jì)算機(jī)無關(guān)。[單選題]63.設(shè)一個(gè)順序有序表A[1：14]中有14個(gè)元素，則采用二分法查找元素A[4]的過程中比較元素的順序?yàn)?)。A.A[7]，A[5]，A[3]，A[4]B.A[1]，A[14]，A[7]，A[4]C.A[7]，A[3]，A[5]，A[4]D.A[1]，A[2]，A[3]，A[4]正確答案：C參考解析：二分查找法的每次比較都與中間值進(jìn)行比較，第一次與位置7的元素比較，依次類推。[多選題]1.數(shù)據(jù)結(jié)構(gòu)中()。A.有四類基本結(jié)構(gòu)B.數(shù)據(jù)元素是孤立存在的C.數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組D.數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的組合正確答案：ACD參考解析：在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)元素之間是有關(guān)系的。[多選題]2.下列哪些是圖的遍歷()。A.中根遍歷B.廣度優(yōu)先搜索C.先根遍歷D.深度優(yōu)先搜索正確答案：BD參考解析：圖的遍歷算法有深度優(yōu)先遍歷算法和廣度優(yōu)先遍歷算法兩種。[多選題]3.計(jì)算機(jī)算法必須具備()等特性。A.可行性、可移植性B.易讀性C.可行性、確定性D.有窮性E.輸入、輸出F.穩(wěn)定性正確答案：CDE參考解析：算法的特征包括確定性、可行性、有窮性、輸入和輸出。[多選題]4.線性表的順序存儲(chǔ)結(jié)構(gòu)是一種()的存儲(chǔ)結(jié)構(gòu)。A.散列存取B.順序存取C.索引存取D.隨機(jī)存取正確答案：BD參考解析：線性表的順序存儲(chǔ)結(jié)構(gòu)是一種順序存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)，順序存儲(chǔ)結(jié)構(gòu)又稱為隨機(jī)存取結(jié)構(gòu)。[多選題]5.()屬于特殊矩陣。A.對(duì)角矩陣B.上三角矩陣C.稀疏矩陣D.下三角矩陣E.對(duì)稱矩陣正確答案：ABDE參考解析：稀疏矩陣不屬于特殊矩陣。特殊矩陣指的是具有一定特點(diǎn)或規(guī)律的矩陣。[多選題]6.如下陳述中錯(cuò)誤的是()。A.串的長度必須大于零B.串是一種特殊的線性表C.串中元素只能是字母D.空串就是空白串正確答案：ACD參考解析：串的長度可以為0，此時(shí)是空串，空串和空白串是不同的。[多選題]7.樹的表示方法有以下哪幾種()。A.直觀表示法B.廣義表表示法C.凹入表示法D.嵌套集合表示法正確答案：ABCD參考解析：樹的表示法包括直觀表示法、凹入表示法、嵌套集合表示法、廣義表表示法。[多選題]8.線性結(jié)構(gòu)的特點(diǎn)是()。A.除最后元素在外，均有唯一的后繼B.除第一元素之外，均有唯一的前驅(qū)C.集合中必存在唯一的一個(gè)“第一元素”D.集合中必存在唯一的一個(gè)“最后元素”正確答案：ABCD參考解析：在線性結(jié)構(gòu)中必存在一個(gè)第一元素和最后元素，除第一個(gè)元素外，都有一個(gè)直接前驅(qū)，除最后元素外，都有直接后繼。[多選題]9.下列存儲(chǔ)形式中，()是樹的存儲(chǔ)形式。A.雙親表示法B.順序表示法C.廣義表表示法D.左子女右兄弟表示法正確答案：ABD參考解析：樹的存儲(chǔ)形式有雙親表示法、左子女右兄弟表示法和順序表示法。[多選題]10.依據(jù)所有數(shù)據(jù)成員之間的邏輯關(guān)系的不同，數(shù)據(jù)結(jié)構(gòu)分為()。A.非線性結(jié)構(gòu)B.邏輯結(jié)構(gòu)C.線性結(jié)構(gòu)D.物理結(jié)構(gòu)正確答案：AC參考解析：根據(jù)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)的不同，分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，其中非線性結(jié)構(gòu)包括圖、樹等。[多選題]11.算法設(shè)計(jì)的要求包括()。A.健壯性B.確定性C.正確性D.可讀性正確答案：ACD參考解析：“確定性”屬于算法特性而非要求。[多選題]12.對(duì)廣義表來說，下面哪些是正確的()。A.廣義表是一種多層次的結(jié)構(gòu)B.廣義表是一種共享結(jié)構(gòu)C.廣義表是一種非線性結(jié)構(gòu)D.廣義表是一種單鏈表結(jié)構(gòu)E.廣義表是一種遞歸表正確答案：ABCDE參考解析：廣義表是一種多層次的結(jié)構(gòu)，并且是一種遞歸表。[多選題]13.抽象數(shù)據(jù)類型按其值的不同特性可分為()。A.分子類型B.固定聚合類型C.離子類型D.可變聚合類型E.原子類型正確答案：BDE參考解析：抽象數(shù)據(jù)類型按其值的不同特性可分為固定聚合類型、可變聚合類型、原子類型。[判斷題]1.線性表的邏輯順序總是與其物理順序一致。()A.正確B.錯(cuò)誤正確答案：B參考解析：只有順序存儲(chǔ)情況下才一致，鏈?zhǔn)酱鎯?chǔ)因?yàn)槭请S機(jī)選擇物理存儲(chǔ)單元，所以不一致。[判斷題]2.棧和隊(duì)列的存儲(chǔ)方式既可以是順序存儲(chǔ)，也可以是鏈?zhǔn)酱鎯?chǔ)。()A.正確B.錯(cuò)誤正確答案：A參考解析：棧和隊(duì)列的存儲(chǔ)方式都有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種。[判斷題]3.中序遍歷二叉排序樹可以得到一個(gè)有序的序列。()A.正確B.錯(cuò)誤正確答案：A參考解析：二叉排序樹的左子樹一定小于根節(jié)點(diǎn)，右子樹一定大于根節(jié)點(diǎn)，中序遍歷的順序是首先中序遍歷左子樹，然后訪問根節(jié)點(diǎn)，最后中序遍歷右子樹