國家電網(wǎng)（計算機類）專業(yè)知識備考題庫大全（按章節(jié)）-數(shù)據(jù)結(jié)構(gòu)與算法

PAGEPAGE1國家電網(wǎng)（計算機類）專業(yè)知識備考題庫大全（按章節(jié)）-數(shù)據(jù)結(jié)構(gòu)與算法一、單選題1.一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足()。A、所有的結(jié)點均無左孩子B、所有的結(jié)點均無右孩子C、只有一個葉子結(jié)點D、是任意一棵二叉樹答案：C解析：先序遍歷的次序為根一左一右，而后序遍歷的次序為左一右一根先序遍歷與后序遍歷相對次序可以相反的部分為根一左(對后序的左一根)，或者是根一右(對后序的右一根)，所以滿足條件的二叉樹只有一個葉子結(jié)點。2.設(shè)一條單鏈表的頭指針為head且該鏈表沒有頭節(jié)點，則其判空條件是()。A、head==NULLB、head-＞next==NULLC、head！=NULLD、head-＞next==head答案：A解析：因為單鏈表沒有頭節(jié)點，所以當頭指針為空時證明鏈表為空。3.某二叉樹中序序列為A，B，C，D，E，F(xiàn)，G，后序序列為B，D，C，A，F(xiàn)，G，E，則前序序列是()。A.E，G，F(xiàn)，A，C，D，BB.E，A，C.A、B、C、FD、以上都不對答案：B解析：由后序序列知E為根節(jié)點，再由中序序列知A，B，C，D為E的左子樹1，F(xiàn)，G，E為右子樹1；由后序序列知A為左子樹l的根節(jié)點，B，C，D為A的右子樹2。依次類推可得到該數(shù)，其前序序列也可自然而然的得到。4.二叉樹的先序遍歷和中序遍歷如下：先序遍歷：EFHIGJK；中序遍歷：HFIEJKG。該二叉樹根的右子樹的根是()A、EB、FC、GD、H答案：C解析：5.設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個記錄關(guān)鍵字5為基準進行一趟快速排序的結(jié)果為()A、3，2，5，8，6B、2，3，5，8，6C、3，2，5，6，8D、2，3，6，5，8答案：C解析：快速排序的每趟排序在待排序列中選取一個數(shù)為基準，將序列劃分為兩段，一段的值比基準值小，另一段大于或等于基準值。6.一趟排序結(jié)束后不一定能夠選出一個元素放在其最終位置上的是()。A、冒泡排序B、堆排序C、快速排序D、希爾排序答案：D解析：冒泡排序每趟選出一個最值移至序列的一端。快速排序的一趟排序可以使選出的基準值移至最終位置。7.二叉樹的第k層的結(jié)點數(shù)最多為()。A、2K-1B、2K+1C、2KD、2答案：A解析：二叉樹第k層最多有2k-1個結(jié)點。8.下列關(guān)于AOE網(wǎng)的敘述中，不正確的是()。A、關(guān)鍵活動不按期完成就會影響整個工程的完成時間B、任何一個關(guān)鍵活動提前完成。那么整個工程將會提前完成C、所有的關(guān)鍵活動提前完成，那么整個工程將會提前完成D、某些關(guān)鍵活動提前完成，那么整個工程將會提前完成答案：B解析：關(guān)鍵路徑是指從有向圖的源點到匯點的最長路徑。某些關(guān)鍵活動提前完成，那么整個工程將會提前完成，但不是任何一個關(guān)鍵活動提前完成，就能保證整個工程將會提前完咸。9.若對序列(tang，deng，an，wang，shi，bai，fang，liu)采用選擇排序法按字典順序進行排序，下面給出的四個序列中，()是第三趟的結(jié)果。A、an.bai，deng，wang，tang，fang，shi，huB、an，bai，deng，wang，shi，tang，fang，liuC、an.bai，deng，wang，shi，fang，tang，liuD、an.bai，deng，wang，shi，liu，tang，fang答案：B解析：選擇排序是指每一趟從待排序的數(shù)據(jù)元素中選出最小(或最大)的一個元素，順序地放在已排好序的數(shù)列的最后，直到待排序數(shù)據(jù)元素全部排完。按字典順序排序的排序過程如下:第一趟:an,deng,tang,wang，shi,bai,fang,liu;.第二趟，an,bai,tang,wang，shi，deng,fang,liu;第三趟:an,bai，deng,wang，shi,tang,fang,liup第四趟:an,bai,deng,fang，shi,tang,wang,liu;第五趟，an,bai，deng,fang，liu,tang,wang，shi;第六趟:an,bai,deng,fang,liu,slu,wang,tang;第七趟:an.bai,deng,fang,liu,shi,tang,中ang。10.A、AB、BC、CD、D答案：A解析：11.用直接選擇排序方法分別對序列S1=(1，2，3，4，5，6，7)和序列S2=(7，5，3，2，4，1，6)進行排序，關(guān)鍵字比較次數(shù)()。A、相同B、前者大于后者C、前者小于后者D、無法比較答案：A解析：直接選擇排序的比較次數(shù)與序列的初始狀態(tài)無關(guān)，因此，對于給定兩個序列進行排序的關(guān)鍵字比較次數(shù)是相同的。12.設(shè)有一組記錄的關(guān)鍵字為{19，14，23，1，68，20，84，27，55，11，10，79}，用鏈地址法構(gòu)造散列表，散列函數(shù)為H(key)=keyMOD13，散列地址為1的鏈中有()個記錄。A、1B、2C、3D、4答案：D解析：由散列函數(shù)H(key)=keyMOD13計算每個記錄的散列地址，散列地址為1的關(guān)鍵字有14，1，27，79，共4個記錄。13.以下屬于邏輯結(jié)構(gòu)的是()。A、順序表B、哈希表C、有序表D、單鏈表答案：C解析：數(shù)據(jù)結(jié)構(gòu)分別為邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)(物理結(jié)構(gòu))和數(shù)據(jù)的運算。數(shù)據(jù)的邏輯結(jié)構(gòu)是對數(shù)據(jù)之間關(guān)系的描述，與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、所含結(jié)點個數(shù)都無關(guān)。順序表、哈希表、單鏈表都涉及到數(shù)據(jù)的存儲結(jié)構(gòu)，有序表是指表中數(shù)據(jù)有序，與邏輯結(jié)構(gòu)無關(guān)。14.A[N，N]是對稱矩陣，將下三角(包括對角線)以行序存儲到一維數(shù)組T[N(N+l)/2]q中，則對任一上三角元素A[i][j]對應T[k]的下標k是()。A、i(1-1)/2+jB、j(j-1)/2+iC、i(j-i)/2+1D、j(1-1)/2+1答案：B解析：將對稱矩陣A[N，N]下三角以行序存儲到一維數(shù)組T[N(N+1)/2]中。對應的A[i][j]啪與T[k]的下標k的關(guān)系為k=i(i-1)/2+j；但題目中是求任一上三角元素A[i][j]對應T[k]的下標k，在對稱矩陣中A[i][D]=A[i][i]，即上三角中的元素的A[i][j]存儲位置對應下三角A[i][j]的存儲位置，所以k=j(j-1)/2+i。15.如果節(jié)點A有3個兄弟，B是A的雙親，則節(jié)點B的度是()。A、3B、4C、1D、2答案：B解析：節(jié)點A有3個兄弟，B是A的雙親，則節(jié)點B的度是4。16.在圖采用鄰接表存儲時，求最小生成樹的Prim算法的時間復雜度為()。A、AB、BC、CD、D答案：B解析：Prim算法的時間復雜度：當圖采用鄰接矩陣存儲時，時間復雜度為0(r12)，采用鄰接表存儲時，時間復雜度為O(n+e)。17.已知有向圖G=(V，A)，其中V={a，b，C，d，e}，A={＜a，b＞，＜a，c＞，＜d，c＞，＜d，e＞，＜b，e＞，＜c，e＞}，對該圖進行拓撲排序，下面序列中()不是拓撲排序A、a，d，c，b，eB、d，a，b，c，eC、a，b，d，c，eD、a，b，c，d，e答案：D解析：18.無向圖的鄰接矩陣是一個()。A、對稱矩陣B、無規(guī)律C、上三角矩陣D、下三角矩陣答案：A解析：兩個頂點鄰接是相互的，1和2鄰接，2和1也就鄰接了。19.一棵有n個結(jié)點的二叉樹，按層次從上到下，同一層從左到右順序存儲在一維數(shù)組A[1.n]中，則二叉樹中第i個結(jié)點(i從1開始用上述方法編號)的右孩子在數(shù)組A中的位置是()。A、A[2i](2i＜=n)B、A[2i+1](2i+1＜=n)C、A[i-2]D、條件不充分，無法確定答案：D解析：本題目并未明確所給二叉樹的形狀，因此不能根據(jù)第i個結(jié)點在數(shù)組A中的存儲位置確定其右孩子在數(shù)組A中的位置。20.在二叉排序樹中插入一個關(guān)鍵字值的平均時間復雜度為()。A、AB、BC、CD、D答案：B解析：在二叉排序樹中插入節(jié)點的時間復雜度等于查找失敗的時間復雜度，即在查找失敗的位置插入節(jié)點，時間復雜度為0(1og2n)。21.有n個記錄的文件，若關(guān)鍵字位數(shù)為d，基數(shù)為r，則基數(shù)排序共需進行()遍分配與收集。A、nB、rC、dD、d+r答案：C解析：22.棧在()中應用。A.遞歸調(diào)用B.子程序調(diào)用A、表達式求值B、C、D、C答案：D解析：棧的特點是先入后出。A項，遞歸調(diào)用的特點是最外層的調(diào)用最后執(zhí)行，最內(nèi)層的調(diào)用最先執(zhí)行，遞歸調(diào)用符合棧的特點，即先將外層的調(diào)用依次入棧，然后從最內(nèi)層調(diào)用出棧執(zhí)行；B項，子程序的調(diào)用與遞歸調(diào)用的特點類似；C項，表達式求值將數(shù)據(jù)入棧，遇到運算符時與棧頂?shù)倪\算符比較優(yōu)先級，級別高則數(shù)據(jù)出棧，進行運算。23.下列排序算法中，在待排序數(shù)據(jù)已有序時，花費時間反而最多的排序是()。A、冒泡B、希爾C、快速D、堆答案：C解析：在待排序數(shù)據(jù)已有序時，快速排序會退化為冒泡排序，時間復雜度為O(n)。24.若允許表達式內(nèi)多種括號混合嵌套，則為檢查表達式中括號是否正確配對的算法，通常選用的輔助結(jié)構(gòu)是()。A、棧B、線性表C、隊列D、二叉排序樹答案：A解析：棧(stack)又稱為堆棧，它是一種運算受限的線性表。其限制是僅允許在表的一端進行插入和刪除運算，這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素稱作進棧、入?；驂簵?，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素稱作出?；蛲藯＃前褩ｍ斣貏h除，使其相鄰的元素成為新的棧頂元素。25.()在其最好情況下的算法時間復雜度為O(n)。A、插入排序B、歸并排序C、快速排序D、堆排序答案：A解析：26.下面()不屬于特殊矩陣。A、對角矩陣B、三角矩陣C、稀疏矩陣D、對稱矩陣答案：C解析：稀疏矩陣不屬于特殊矩陣。27.某高度為k的完全二叉樹中，所含葉子結(jié)點的個數(shù)最少為()。A、AB、BC、CD、D答案：C解析：28.設(shè)單循環(huán)鏈表中結(jié)點的結(jié)構(gòu)為(data，link)，且rear是指向非空的帶表頭結(jié)點的單循環(huán)鏈表的尾結(jié)點的指針。若想刪除鏈表第一個結(jié)點，則應執(zhí)行下列哪一個操作()。A、s=rear；rear=rear-＞link；deletes；B、rear=rear-＞link；deleterear；C、rear=rear-＞link-＞link；deleterear；D、s=rear-＞link-＞link；rear-＞link-＞link=s-＞link；deletes；s為第一個結(jié)點硫答案：D解析：若要刪除結(jié)點需要改變尾指針的指向。29.A、{(1，4)，(2，3)，(2，5)}B、{(3，5)，(3，4)，(4，5)}C、{(1，3)，(3，4)，(3，5)}D、{(2，3)，(3，4)，(2，5)}答案：A解析：30.對于完全二叉樹中的任一結(jié)點，若其右分支下的子孫的最大層次為h，則其左分支下的子孫的最大層次為()。A、h或h+1B、任意C、hD、h+1答案：A解析：葉子結(jié)點只可能在層次最大的兩層上出現(xiàn)；對任一結(jié)點，若其右分支下子孫的最大層次為l，則其左分支下子孫的最大層次必為1或1+1滿二叉樹：一棵深度為k.且有2的(k)次方－1個節(jié)點的二叉樹特點：每一層上的結(jié)點數(shù)都是最大結(jié)點數(shù)。31.已知一個線性表為(38，25，74，63，52，48)，假定采用H(K)=Kmod7計算散列地址進行散列存儲，若利用線性探測的開放定址法處理沖突，則在該散列表上進行查找的平均查找長度為()；若利用鏈地址法處理沖突，則在該散列上進行查找的平均查找長度為()。A、1.5，1B、1.7，3/2C、2，4/3D、2.3，7/6答案：C解析：若用開放定址法處理沖突，發(fā)生0次沖突的關(guān)鍵字有3個，1次沖突的1個，2次沖突的1個，3次沖突的1個，因而在該散列表上進行查找的平均查找長度為ASL-(3*1+1*2+1*3+1*4)/6=2；若用鏈地址法處理沖突，同一鏈表上有1個元素的線性鏈表有2個，有2個元素的線性鏈表有2個，因此ASL=(4*1+2*2)/6=4/3。32.若線性表最常用的運算是查找第i個元素及其前驅(qū)的值，則下列存儲方式最節(jié)省時間的是()。A、單鏈表B、雙鏈表C、單循環(huán)鏈表D、順序表答案：D解析：在順序表中查找第i個元素的前驅(qū)很方便。雙鏈表雖然能快速查找第i個元素的前驅(qū)，但不能實現(xiàn)隨機存取。單鏈表和單循環(huán)鏈表既不能實現(xiàn)隨機存取，查找第i個元素的前驅(qū)也不方便。33.下列說法不正確的是()。A、圖的遍歷是從給定的源點出發(fā)每一個頂點僅被訪問一次B、遍歷的基本算法有兩種：深度遍歷和廣度遍歷C、圖的深度遍歷不適用于有向圖D、圖的深度遍歷是一個遞歸過程答案：C解析：圖的遍歷是指從給定圖中任意指定的頂點出發(fā)，按照某種搜索方法沿著圖的邊訪問圖中的所有頂點，便每個丁貞點僅被訪問一次。遍歷的基本算法有兩種：深度遍歷和廠度遍歷。圖的深度遍歷是一個遞歸過程，既適用于無向圖，也適用于有向圖。34.設(shè)有向無環(huán)圖G中的有向邊集合E={＜1，2＞，＜2，3＞，＜3，4＞，＜1，4＞}，則下列屬于該有向圖G的一種拓撲排序序列的是()。A、1，2，3，4B、2，3，4，1C、1，2，4，3D、1，4，2，3答案：A解析：35.以下排序方法中，在初始序列已基本有序的情況下，排序效率最高的是()。A、歸并排序B、直接插入排序C、快速排序D、堆排序答案：B解析：直接插入排序?qū)τ诨居行虻男蛄羞M行排序效率最高。36.設(shè)指針q指向單鏈表中結(jié)點A，指針p指向單鏈表中結(jié)點A的后繼結(jié)點B，指針s指向被插入的結(jié)點X，則在結(jié)點A和結(jié)點B插入結(jié)點X的操作序列為()。A、p-＞next=s；s-＞next=q；B、q-＞next=s；s-＞next=p；C、p-＞next=s-＞next；s-＞next=p；D、s-＞next=p-＞next；p-＞next=-s；答案：B解析：插入s結(jié)點，應使s的next指針指向p結(jié)點，使q結(jié)點的next指針指向s。37.設(shè)有13個值，用它們組成一棵哈夫曼樹，則該哈夫曼樹共有()個結(jié)點。A、13B、12C、26D、25答案：D解析：哈夫曼樹的特點：具有n個葉子結(jié)點的哈夫曼樹共有2×n-1個結(jié)點。38.設(shè)一組初始記錄關(guān)鍵字的長度為8，則最多經(jīng)過()趟插入排序可以得到有序序列。A、8B、7C、9D、6答案：B解析：插入排序的每一趟在待排元素中取出第一個元素，移至有序序列的適當?shù)奈恢?，所以共八個關(guān)鍵字的序列，最多經(jīng)過7趟插入排序就可以得到一個有序序列。39.已知一算術(shù)表達式的中綴形式為A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為()。A、-A+B*C/DEB、-A+B*CD/EC、-+*ABC/DED、-+A*BC/DE答案：D解析：將算術(shù)表達式的前綴形式、中綴形式和后綴形式分別看成二叉樹的前序遍歷、中序遍歷和后序遍歷，本題可轉(zhuǎn)化成已知二叉樹的中序遍歷和后序遍歷序列，如何求出其前序遍歷序列。前序遍歷的順序是根結(jié)點，左子樹，右子樹；中序遍歷的順序是左子樹，根結(jié)點，右子樹；后序遍歷的順序是左子樹，右子樹，根結(jié)點；因此后序遍歷中最后訪問的結(jié)點是根結(jié)點，該結(jié)點將中序遍歷分成兩個子序列，分別為其左右子樹的中序序列，之后遞歸應用這個過程，構(gòu)造出一個二叉樹，前序遍歷該序列，即可得到表達式的前綴形式。40.在一個有向圖中，所有頂點的入度之和等于所有頂點出度之和的()倍：A、1/2B、2C、1D、4答案：C解析：在有向圖中每個頂點的入度就是另外一個頂點的出度，因此所有頂點的入度之和等于所有頂點出度之和，等于有向圖中所有的邊數(shù)。41.設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20，15，14，18，21，36，40，10)，則以20為基準記錄的一趟快速排序結(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解析：快速排序的每趟排序在待排序列中選取一個數(shù)為基準，將序列劃分為兩段，一段的值比基準值小，另一段大于或等于基準值。在快速排序中通常有兩個指針分別為i和j，j從后向前遍歷，找第一個小于基準值的節(jié)點，將值交換，i從前向后遍歷，找到第一個大于或等于基準值的節(jié)點，將值交換，重復此過程，直至i和j指向同一節(jié)點，一趟排序結(jié)束。42.A、AB、BC、CD、D答案：A解析：由森林轉(zhuǎn)換為二叉樹，利用的是樹轉(zhuǎn)為二叉樹時，二叉樹的右子樹始終為空的特點，所以，從第二棵樹開始，每棵樹都成為了B的右子樹，即B的左子樹的結(jié)點個數(shù)為N1-1個。43.若對27個元素只進行三趟多路歸并排序，則選取的歸并路數(shù)為()。A、2B、3C、4D、5答案：B解析：44.下列各種排序算法中平均時間復雜度為O(n)是()。A、快速排序B、堆排序C、歸并排序D、冒泡排序答案：D解析：45.在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是()。A、希爾排序B、起泡排序C、插入排序D、選擇排序答案：D解析：每一趟從待排序的數(shù)據(jù)元素中選出最小(或最大)的一個元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。46.設(shè)用鄰接矩陣A表示有向圖G的存儲結(jié)構(gòu)，則有向圖G中頂點i的入度為()。A、第i列0元素的個數(shù)之和B、第i列非0元素的個數(shù)之和C、第i行0元素的個數(shù)之和D、第i行非0元素的個數(shù)之和答案：B解析：考察圖的鄰接矩陣的特點，在有向圖的鄰接矩陣中，第i列非0元素的個數(shù)之和即為第i個節(jié)點的入度。47.求解Hanoi問題時，若初始有5個圓盤，則移動圓盤的次數(shù)是()。A、7B、15C、31D、5答案：C解析：48.在一個雙鏈表中，刪除P結(jié)點之后的一個結(jié)點的操作是()。A、AB、BC、CD、D答案：C解析：考查雙鏈表中插入操作，要注意保存后繼節(jié)點。49.A、4B、5C、6D、7答案：C解析：右節(jié)點均為原來森林的樹。將T2還原為森林T1，其中有6棵樹：C、D、F、G，I和J是葉子結(jié)點。50.一棵m階非空B-樹，每個結(jié)點最多有()棵子樹。A、m/2B、m-1C、mD、m+1答案：C解析：B-樹中每個結(jié)點之多有m棵子樹，m就是B-樹的階。51.二維數(shù)組A的每個元素是由6個字符組成的串，行下標的范圍從0～8，列下標的范圍是從0～9，則存放A至少需要()個字節(jié)。A、240B、540C、90D、180答案：B解析：數(shù)組A為9行10列，共有90個元素，所以，存放A至少需要90×6=540個存儲單元。52.下列排序方法中，屬于不穩(wěn)定的排序方法的是()。A、直接插入排序法B、冒泡排序法C、基數(shù)排序法D、堆排序法答案：D解析：本題選項所述的四種排序方法中，只有堆排序是不穩(wěn)定的。53.對于棧操作數(shù)據(jù)的原則是()。A、先進先出B、后進先出C、后進后出D、不分順序答案：B解析：棧的特點就是后進先出，入棧和出棧的操作只能在棧頇進行.而隊列的特點是先進先出，這兩點容易混淆，要注意區(qū)分。54.下面關(guān)于圖的遍歷說法不正確的是()。A、遍歷圖的過程實質(zhì)上是對每個頂點查找其鄰接點的過程B、深度優(yōu)先搜索和廣度優(yōu)先搜索對無向圖和有向圖都適用C、深度優(yōu)先搜索和廣度優(yōu)先搜索對頂點訪問的順序不同，它們的時間復雜度也不相同D、深度優(yōu)先搜索是一個遞歸的過程，廣度優(yōu)先搜索的過程中需附設(shè)隊列答案：C解析：深度優(yōu)先搜索和廣度優(yōu)先搜索的時間算雜度相同，均為O(n+e)。55.若用冒泡排序方法對序列{10、14、26、29、41、52}從大到小排序，需要進行幾次比較()。A、3B、10C、15D、25答案：C解析：冒泡排序法比較排序的時候，第一個10要進行5次比較，第二個要進行4次比較，依次類推，3次，2次，1次，總共是15次比較。56.設(shè)n、m為一棵二叉樹上的兩個結(jié)點，在中序遍歷時，n在m前的條件是()。A、n在m右方B、n是m祖先C、n在m左方D、n是m子孫答案：C解析：中序遍歷時，先訪問左子樹，再訪問根結(jié)點。n在m前，則n必須在m的左子樹中。57.對于一個長度為n的任憊表進行排序，至少需要進行的比較次數(shù)是()。A、AB、BC、CD、D答案：D解析：58.設(shè)結(jié)點x和y是二叉樹中任意的兩個結(jié)點，在該二叉樹的前序遍歷序列中x在y之前，而在其后序遍歷序列中x在y之后，則x和y的關(guān)系是()。A、x是y的左兄弟B、x是y的右兄弟C、x是y的祖先D、x是y的后裔答案：C解析：前序遍歷序列中x在y之前，有兩種情況，即x是y的祖先，或者x、y有某個共同祖先，并且x在其左子樹中，y在其右子樹中。而第二種情況在后序遍歷序列中，x必定在y之前，所以只能是x是y的祖先。59.下列命題正確的是()。A、一個圖的鄰接矩陣表示不唯一的，鄰接表表示也不唯一B、一個圖的鄰接矩陣表示是唯一的，鄰接表表示也唯一C、一個圖的鄰接矩陣表示是唯一的，鄰接表表示不唯一D、一個圖的鄰接矩陣表示不唯一的，鄰接表表示是唯一答案：C解析：一個圖的鄰接矩陣表示是唯一的，鄰接表表示不唯一。60.以數(shù)組Data[m+1]作為循環(huán)隊列SQ的存儲空間，front為頭指針，rear為隊尾指針，則執(zhí)行出隊操作的語句是()。A、front=front+1B、front=(front+1)%mC、front=(front+1)%(m+1)D、rear=(rear+1)%m答案：C解析：循環(huán)隊列的出隊操作是：front=(front+1)%(m+l)。61.()的鄰接矩陣是對稱矩陣。A、有向圖B、無向圖C、AOV網(wǎng)D、AOF網(wǎng)答案：B向圖的鄰接矩陣一定是一個對稱矩陣。62.下面給出的四種排序方法中，輔助空間為O(n)的是()。A、希爾選擇B、冒泡排序C、歸并排序D、堆排序答案：C解析：希爾選擇、冒泡排序、堆排序的輔助空間都為0(1)；而歸并排序中，由于每一趟都要一個TR數(shù)組來復制，因此需要與待排記錄等量的輔助空間O(n)。63.對長度為n的有序單鏈表，若搜索每個元素的概率相等，則順序搜索到表中任一元素的平均搜索長度為()。A、n/2B、(n+1)/2C、(n-1)/2D、n/4答案：B解析：所有元素的搜索長度之和為1+2+…+n=n(n+1)/2。搜索每個元素的概率都是1/n，所以平均搜索長度為：n(n+1)，2×(1/n)=(n+1)/2。64.算法指的是()。A、計算機程序B、解決問題的計算方法C、排序算法D、解決問題的有限運算序列答案：D解析：算法是精確定義的一系列規(guī)則，它指出怎樣從給定的輸入信息經(jīng)過有限步驟產(chǎn)生所求的輸出信息。它既不是計算機程序，也不是某種算術(shù)運算。65.下列與數(shù)據(jù)元素有關(guān)的敘述中，哪一項是不正確的()。A、數(shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個體B、數(shù)據(jù)元素是由獨立含義的數(shù)據(jù)最小單位C、數(shù)據(jù)元素又稱為節(jié)點D、數(shù)據(jù)元素又稱為記錄答案：B解析：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個體。有些情況下也把數(shù)據(jù)元素稱為節(jié)點、記錄、表目等。一個數(shù)據(jù)元素可由一個或多個數(shù)據(jù)項組成，數(shù)據(jù)項是由獨立含義的數(shù)據(jù)最小單位。66.線索化的二叉樹中，某結(jié)點*P沒有孩子的充要條件是()。A、p-＞lchild=NULLB、p-＞ltag=l&&p-＞rtag=1C、p-＞ltag=0D、p-＞lchild=NULL&&p-＞ltag=1答案：B解析：考查線索二叉樹。67.一個隊列的入隊順序是a，b，c，d，則出隊順序是()。A.a，b，C，dB.b，C，d，aA、d，B、b，aC、D、d，a，b答案：A解析：隊列的特點是先進先出，因此出隊的序列于入隊的序列完全相同，這點與棧不同。68.設(shè)有序表中有1000個元素，則用二分查找元素X最多需要比較()次。A、15B、10C、17D、25答案：B解析：二分查找每趟都使用序列的中間值與關(guān)鍵字比較，直至查找成功或失敗。69.若一個棧的輸入序列為1，2，3…，n，輸出序列的第一個元素是i，則第j個輸出元素是()。A、i-j-1B、i-jC、j-i+lD、不確定答案：D解析：棧是一種后進先出的線性表結(jié)構(gòu)，但本題無法確定輸入和輸出的時間順序，即不一定是在所有元素輸入棧后再進行輸出。70.設(shè)有關(guān)鍵字序列F={Q，G，M，Z，A，N，P，X，H}，下面()序列是從上述序列出發(fā)建堆的結(jié)果。A.A，G，H，M，N，P，Q，X，ZB.A，G，M，H，Q，N，P，X，ZC.G，M，Q，A，N，P，X，A、ZB、C、0，M，P，D、N，Q.X.Z答案：B解析：本題考查堆建立算法。71.一個循環(huán)隊列Q最多可存儲m個元素，已知其頭尾指針分別是front和rear，則判定該循環(huán)隊列為滿的條件是()。A、Q.rear-Q.front==mB、Q.real！==Q.frontC、Q.front==(Q.real+1)%mD、Q.front==Q.rear%m+1答案：C解析：少用一個元素空間和空隊區(qū)別開：每次入隊前測試入隊后頭尾指針是否會重合，如果會重合就認為隊列已滿，這種情況下隊滿的條件是：(Q.rear+1)%MAXSIZE==Q.front。72.由圈權(quán)值為9.2.5.7的四個葉子結(jié)點構(gòu)造一顆哈夫曼樹，該樹的帶權(quán)路徑長度為()。A、23B、37C、44D、46答案：C解析：73.設(shè)某有向圖的鄰接表中有n個表頭結(jié)點和m個表結(jié)點，則該圖中有()條有向邊。A、n-1B、nC、m-1D、m答案：B解析：鄰接表的表頭結(jié)點個數(shù)即為圖中結(jié)點的個數(shù)。74.下面的說法中，不正確的是()。A、對角矩陣只需存放非零元素即可B、稀疏矩陣中值為零的元素較多，因此可以采用三元組表方法存儲C、稀疏矩陣中大量值為零的元素分布有規(guī)律，因此可以采用三元組表方法存儲D、對稱矩陣只需存放包括主對角線元素在內(nèi)的下(或上)三角的元素即可答案：C解析：稀疏矩陣中大量值為零的元素分布沒有規(guī)律，因此采用三元組表存儲。如果零元素的分布有規(guī)律，就沒有必要存儲非零元素的行號和列號，而需要按其壓縮規(guī)律找出相應的映象函數(shù)。75.以下數(shù)據(jù)結(jié)構(gòu)中，屬于非線性數(shù)據(jù)結(jié)構(gòu)的是()，A、樹B、隊列C、棧D、字符串答案：A解析：線性結(jié)構(gòu)是一個數(shù)據(jù)元素的有序(次序)集合。它有四個基本特征：(1)集合中必存在唯一的一個“第一個元素”；(2)集合中必存在唯一的一個“最后的元素”；(3)除最后元素之外，其它數(shù)據(jù)元素均有唯一的“后繼”；(4)除第一元素之外，其它數(shù)據(jù)元素均有唯一的“前撲”。數(shù)據(jù)結(jié)構(gòu)中線性結(jié)構(gòu)指的是數(shù)據(jù)元素之間存在著“一對一”的線性關(guān)系的數(shù)據(jù)結(jié)構(gòu)。線性結(jié)構(gòu)包括線性表(如結(jié)構(gòu)體數(shù)組，結(jié)構(gòu)體鏈表)、一維數(shù)組、字符串、堆棧、隊列。76.在單鏈表指針為P的結(jié)點之后插入指針為s的結(jié)點，正確的操作是()。A、AB、BC、CD、D答案：B解析：在單鏈表結(jié)點P后插入結(jié)點s，要先改變s結(jié)點的指針域，指向p的后繼結(jié)點。然后將s的地址賦給P的指針域。具體的操作語句為s—＞next=P—＞next；p—＞next=s。77.用鏈接方式存儲的隊列，在進行刪除運算時()。A、僅修改頭指針B、僅修改尾指針C、頭、尾指針都要修改D、頭、尾指針可能都要修改答案：D解析：鏈接方式存儲隊列的刪除運算仍要保持鏈式隊列結(jié)構(gòu)。當隊列中僅包含一個元素結(jié)點時，頭尾指針均指向該結(jié)點，刪除該結(jié)點后頭尾指針均要修改；當隊列中有多個結(jié)點時，隊列的刪除運算僅針對頭結(jié)點，修改頭指針即可。78.()不是算法的基本特性。A、可行性B、長度有限C、在規(guī)定的時間內(nèi)完成D、確定性答案：B解析：算法的5個重要特性：①確定性；②有窮性；③可行性；④輸入；⑤輸出。C項指的是有窮性，而有窮性并不是指長度有限，而是指執(zhí)行的時間是有限的。79.若某線性表中最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點和刪除最后一個結(jié)點，則下面最合適的存儲方式是()。A、單鏈表B、循環(huán)雙鏈表C、單循環(huán)鏈表D、帶有尾指針的單循環(huán)鏈表答案：B解析：在鏈表中的最后一個結(jié)點之后插入個結(jié)點要知道終端結(jié)點的地址，所以，單鏈表、單循環(huán)鏈表都不合適，刪除最后一個結(jié)點要知道終端結(jié)點的前驅(qū)結(jié)點的地址，所以，帶有尾指針的單循環(huán)鏈表不合適，而循環(huán)雙鏈表滿足條件。80.有一個長度為12的有序表，按二分查找法對該表進行查找，在表內(nèi)各元素等概率情況下，查找成功所需的平均比較次數(shù)為()。A、37/12B、35/12C、39/12D、43/12答案：A解析：用二分法查找有序表，相當于在一個完全二叉樹中查找元素，查找成功的比較次數(shù)相當于到查找結(jié)點的路徑長度加1。12個結(jié)點的完全二叉樹前三層是滿二叉樹，第四層有5個結(jié)點。整棵樹的查找次數(shù)總和為：1+22+4×3+5×4=37。查找某個元素的概率是37/12。81.以下各種存儲結(jié)構(gòu)中，最適合用作鏈隊的鏈表是()。A、帶隊首指針和隊尾指針的循環(huán)單鏈表B、帶隊首指針和隊尾指針的非循環(huán)單鏈表C、只帶隊首指針的非循環(huán)單鏈表D、只帶隊首指針的循環(huán)單鏈表答案：B解析：因為隊列的入隊和出隊操作都在端點進行。即在隊首和隊尾進行。所以帶隊首指針和隊尾指針的非循環(huán)單鏈表最適合用作鏈隊的鏈表。82.將一個a[100][100]的三對角矩陣以行主序存入一維數(shù)組B[298]中，元素a[65][64]在B數(shù)組中的位置等于()。A、198B、197C、196D、195答案：D解析：將三對角矩陣a[i][j]存入b[k]中，矩陣壓縮地址計算公式為k=2i十j。所以a[65][64]對應的k=2×65+64=194，194是一維數(shù)組b的下標，而數(shù)組下標是從0開始計數(shù)的.所以元素的位置應該是195。83.采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于樹的()。A、中根遍歷B、先根遍歷C、后根遍歷D、按層次遍歷答案：D解析：圖的廣度優(yōu)先遍歷算法思想是，對于某個結(jié)點，首先遍歷該結(jié)點，而后遍歷其相鄰的所有結(jié)點，而樹的層次遍歷中，對于某個結(jié)點，首先遍歷該結(jié)點，然后遍歷其所有的子結(jié)點。84.采用開放定址法處理散列表的沖突時，其平均查找長度()。A、與鏈接法處理沖突相同B、高于二分查找C、低于鏈接法處理沖突D、高于鏈接法處理沖突答案：D解析：開放定址法處理沖突的平均查找長度高于鏈接法。85.如果結(jié)點A有3個兄弟，B是A的雙親，則結(jié)點B的度是()A、3B、4C、1D、2答案：B解析：結(jié)點A有3個兄弟，B是A的雙親，則結(jié)點B的度是4。86.以下說法正確的是()。A、數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關(guān)系。B、數(shù)據(jù)元素是數(shù)據(jù)結(jié)構(gòu)的最小單位。C、數(shù)據(jù)結(jié)構(gòu)的基本操作的設(shè)置的最重要的準則是，實現(xiàn)應用程序與存儲結(jié)構(gòu)的獨立。D、判斷某個算法是否容易閱讀是算法分析的任務之一。答案：C解析：A項，數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)元素之間的邏輯關(guān)系，而不是數(shù)據(jù)項之間的邏輯關(guān)系。B項，數(shù)據(jù)元素是數(shù)據(jù)結(jié)構(gòu)的基本單位，數(shù)據(jù)結(jié)構(gòu)的最小單位是數(shù)據(jù)項。D項，算法分析是一個軟件的驗證確認任務，用于保證選擇的算法是正確的、合適的和穩(wěn)定的，并且滿足所有精確性、規(guī)模和時間方面的要求，保證產(chǎn)品高質(zhì)量高效率的運行。容易閱讀是增加算法的可讀性，不是算法分析的任務。87.A、AB、BC、CD、D答案：B解析：88.用P代表入棧，O代表出棧。棧的初始狀態(tài)和最終狀態(tài)都為空，則下列棧操作正確的是()。A、POOPOOPPB、POPOPOOPC、PPPOOOPPD、PPPOOPOO答案：D解析：AB兩項，均會出現(xiàn)下溢，即出棧時棧為空。C項，導致出現(xiàn)最終狀態(tài)不為空。89.設(shè)棧S和隊列Q的初始狀態(tài)均為空，元素abcdefg依次進入棧S。若每個元素出棧后立即進入隊列Q，且7個元素出隊的順序是bdcfeag，則棧S的容量至少是()。A、1B、2C、3D、4答案：C解析：出隊的順序也是出棧的順序，由此順序可以推出棧的容量最小值。90.在順序表(3，6，8，10，12，15，16，18，21，25，30)中，用二分法查找關(guān)鍵值11，所需的關(guān)鍵碼比較次數(shù)為()。A、2B、3C、4D、5答案：C解析：用二分法查找關(guān)鍵值11比較的元素依次是15，12，10，8，共比較4次。91.A、AB、BC、CD、D答案：D解析：92.若二叉樹的前序序列為DABCEFG，中序序列為BACDFGE，則其層次序列為()。A、BCAGFEDB、DAEBCFGC、ABCDEFGD、BCAEFGD答案：B解析：由前序序列和中序序列先構(gòu)造出二叉樹，然后按層次序列進行訪問。93.執(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é)果為基準值的左邊節(jié)點的值全部小于基準值，基準右邊的節(jié)點的值全部不小于基準值。94.對任意7個關(guān)鍵字進行排序，至少要進行()次關(guān)鍵字之間的兩兩比較。A、13B、14C、15D、16答案：C解析：95.A、AB、BC、CD、D答案：C解析：96.將長度為n的單鏈表接在長度為m的單鏈表之后的算法時間復雜度為()。A、O(n)B、0(1)C、O(m)D、O(m+n)答案：C解析：要將長度為n的單鏈表接在長度為m的單鏈表之后，必須從單鏈表的頭結(jié)點沿鏈找到長度為m的單鏈表的最后一個結(jié)點，所以時間復雜度為O(m)。97.棧和隊列的共同點是()。A、都是先進先出B、都是先進后出C、只允許在端點處插入和刪除元素D、沒有共同點答案：C解析：棧和隊列都是運算受限的線性表，只允許在表端點處進行操作。98.如果要求一個線性表既能較快的查找，又能適應動態(tài)變化的要求，則可采用的查找法是()。A、分塊查找B、順序查找C、折半查找D、基于屬性答案：A解析：分塊查找又稱索引順序查找，是一種性能介于順序查找和二分查找之間的查找方法。其基本思想是：(1)首先查找索引表：索引表是有序表，可采用二分查找或順序查找，以確定待查的結(jié)點在哪一塊。(2)然后在已確定的塊中進行順序查找：由于塊內(nèi)無序，只能用順序查找。分塊查找既能較快的查找，又能適應動態(tài)變化的要求。99.設(shè)有兩個串S1和S2，求S2在S1中首次出現(xiàn)的位置的運算稱作()。A、求子串B、判斷是否相等C、模式匹配D、連接答案：C解析：A項，求子串操作是從字符串S中截取第i個字符開始后的長度1的子串。BD明顯不對。100.A、3B、6C、9D、以上答案均不正確答案：A解析：鄰接矩陣是表示頂點之間相鄰關(guān)系的矩陣。設(shè)G=(V，E)是具有n個頂點的圖，頂點序號依次為1，2，……，n，則G的鄰接矩陣是n階方陣，所以該圖有3個頂點。101.如果以鏈表作為棧的存儲結(jié)構(gòu)，則退鏈棧操作時()A、必須判斷鏈棧是否滿B、判斷鏈棧元素的類型C、必須判斷鏈棧是否空D、對鏈棧不做任何判斷答案：C解析：在鏈表的退鏈棧操作時，如果棧已空.就沒有元素可供退棧，返回退棧失敗信息，所以必須判斷鏈棧是否空。102.用遞歸算法實現(xiàn)n個相異元素構(gòu)成的有序序列的二分查找，采用一個遞歸工作棧時，該棧的最小容量應為()。A、AB、BC、CD、D答案：D解析：103.建立一個長度為n的有序單鏈表的時間復雜度為()A、AB、BC、CD、D答案：C解析：建立有序單鏈表的時間復雜度是O(n)，對單鏈表插入節(jié)點時，先遍歷單鏈表，找到插入位置，將節(jié)點插入。104.A、(1)B、(1)、(2)C、(1)、(4)D、(3)答案：C解析：(1)項，原地工作不是不需要額外空間，而是額外空間相對于問題的規(guī)模(輸入數(shù)據(jù)量)來說是個常數(shù)，那么我們就稱之為原地工作。(4)項，這個結(jié)論不是絕對的，要看具體情況而定，一般情況下是這樣的。105.在由4棵樹組成的森林中，第一、第二、第三和第四棵樹中的結(jié)點個數(shù)分別為30，10，20，5，當把森林轉(zhuǎn)換成二叉樹后，對應的二叉樹中根結(jié)點的左子樹中結(jié)點個數(shù)為()。A、20B、29C、30D、35答案：B解析：當把森林轉(zhuǎn)換成二叉樹后，第二、第三和第四棵樹均在第一棵樹的根結(jié)點的右子樹上。106.在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，而且還要存儲()。A、數(shù)據(jù)的處理方法B、數(shù)據(jù)元素的類型C、數(shù)據(jù)元素之間的關(guān)系D、數(shù)據(jù)的存儲方法答案：C解析：在存儲數(shù)據(jù)時，需要存儲數(shù)據(jù)元素的值和數(shù)據(jù)元素之間的關(guān)系。107.已知串S=′aaab′，其next數(shù)組值為()。A、0123B、0213C、0231D、1211答案：A解析：108.若用單鏈表來表示隊列，則應該選用()。A、帶尾指針的非循環(huán)鏈表B、帶尾指針的循環(huán)鏈表C、帶頭指針的非循環(huán)鏈表D、帶頭指針的循環(huán)鏈表答案：B解析：假設(shè)尾指針為TAIL，則通過TAIL可訪問隊尾，通過TAIL—＞next可訪問隊頭。109.設(shè)鏈式棧中節(jié)點的結(jié)構(gòu)為(data，link)，且top是指向棧頂?shù)闹羔?。若想摘除鏈式棧的棧頂?jié)點，并將被摘除節(jié)點的值保存到x中，則應執(zhí)行下列()操作。A、x=top-＞data；top=top-＞link；B、top=top-＞link；x=top-＞data；C、x=top；top=top-＞link；D、x=top-＞data；答案：A解析：若想摘除鏈式棧的棧頂節(jié)點，并將被摘除節(jié)點的值保存到x中，則應執(zhí)行x=top-＞data；top=top-＞link.110.下列序列中，滿足堆定義的是()。A、(100，86，48，73，35，39，42，57，66，21)B、(12，70，33，65，24，56，48，92，86，33)C、(103，97，56，38，66，23，42，12，30，52，6，26)D、(5，56，20，23，40，38，29，61，36，76，28，100)答案：A解析：n個元素的序列{K1，K2，…，Kn}當且僅當滿足下面關(guān)系：Ki＜=K2i和Ki＜=K(2i+1)或者Ki＞=K2i和Ki＞K(2i+1)時，稱之為堆。B項，其構(gòu)成的是小頂堆，70和24之間不滿足小頂堆性質(zhì)；C項，其構(gòu)成的是大頂堆，23和26不滿足大頂堆性質(zhì)；D項，其構(gòu)成的是小頂堆，56和23，40和28不滿足小頂堆性質(zhì)。A項對應的是大頂堆，滿足大頂堆性質(zhì)。111.將數(shù)組稱為隨機存取結(jié)構(gòu)是因為()。A、數(shù)組的存儲結(jié)構(gòu)是不定的B、數(shù)組元素是隨機的C、對數(shù)組任一元素的存取時間是相等的D、隨時可以對數(shù)組進行訪問答案：C解析：將數(shù)組稱為隨機存取結(jié)構(gòu)是因為對數(shù)組任一元素的存取時間是相等的。112.設(shè)順序表的長度為n，則順序查找的平均比較次數(shù)為()。A、(n-1)/2nB、n/2C、(n+1)/2D、n答案：C解析：順序查找是順序遍歷查找表，直至找到或查找失敗，所以最好的情況是第一個節(jié)點即想找的元素，最壞的情況是查找失敗，所以平均查找次數(shù)為(n+1)/2。113.若一組記錄的關(guān)鍵碼為(46，79，56，38，40，84)，則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結(jié)果為()。A、38，40，46，56，79，84B、40，38，46，79，56，84C、40，38，46，56，79，84D、40，38，46，84，56，79答案：C解析：由于選擇第一個記錄為基準，第一次排序即對整個序列進行一趟快速排序。使得位于基準左側(cè)的關(guān)鍵碼均小于基準，位于基準右側(cè)的關(guān)鍵碼均大于基準。114.二叉排序樹中左子樹上所有結(jié)點的值均()根結(jié)點的值。A、＜B、=C、＞D、！=答案：A解析：二叉排序樹的左子樹的結(jié)點的值全部小于根結(jié)點的值，并且根結(jié)點的值小于右子樹左右結(jié)點的值。115.在采用線性探測法處理沖突所構(gòu)成的散列表上進行查找，可能要探測多個位置，在查找成功的情況下，所探測的這些位置的鍵值()。A、一定都是同義詞B、一定都不是同義詞C、不一定都是同義詞D、都相同答案：C解析：采用線性探測法處理沖突會產(chǎn)生堆積，即非同義詞爭奪同一個后繼地址。116.設(shè)散列表中有m個存儲單元，散列函數(shù)H(key)=key%p，則p最好選擇()。A、小于等于m的最大偶數(shù)B、小于等于m的最大合數(shù)C、小于等于m的最大奇數(shù)D、小于等于m的最大素數(shù)答案：D解析：p最好選擇小于等于m的最大素數(shù)。117.如果一棵二叉樹結(jié)點的先根遍歷序列是A、B、C，后根遍歷序列是C、B、A，則該二叉樹結(jié)點的中根遍歷序列()。A.必為A、B、CB.必為A、C、BA、必為B、C、AD、不能確定答案：D解析：118.A、6B、4C、3D、2答案：C解析：119.若用一個大小為6的一維數(shù)組來實現(xiàn)循環(huán)隊列，且當前front和rear的值分別為3，0，當從隊列中刪除一個元素，再加入兩個元素后，front和rear的值分別為()。A、5，1B、4，2C、2，4D、1，5答案：B解析：刪除front=(front+1)mod6，加入：rear=(rear+1)mod6。120.使用雙鏈表存儲線性表，其優(yōu)點是()。Ⅰ.提高查找速度Ⅱ.更方便數(shù)據(jù)的插入和刪除Ⅲ，節(jié)約存儲空間Ⅳ.很快回收存儲空間A、Ⅰ、ⅡB、Ⅰ、ⅣC、僅ⅡD、Ⅱ、Ⅲ、Ⅳ答案：C解析：在鏈表中一般只能進行順序查找，所以雙鏈表并不能提高查找速度，因為雙鏈表中有兩個指針域，對于動態(tài)存儲分配，回收存儲空間的速度是一樣的。由于雙鏈表具有對稱性，其插入和刪除操作更加方便。121.一棵完全二叉樹上有1001個結(jié)點.其中葉子結(jié)點的個數(shù)是()。A、250B、500C、505D、501答案：D解析：122.分別以下列序列構(gòu)造=叉排序樹，與用其他三個序列所構(gòu)造的結(jié)果不同的是()。A、(100，80，90，60，120，110，130)B、(100，120，110，130，80，60，90)C、(100，60，80，90，120，110，130)D、(100，80，60，90，120，130，110)答案：C解析：二叉排序樹的特點：左子樹的結(jié)點小于根結(jié)點，右子樹的結(jié)點大于根結(jié)點。由其特點得C得到的結(jié)果與其他三個序列構(gòu)造的結(jié)果不同。123.設(shè)無向圖G中的邊的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點a出發(fā)進行深度優(yōu)先遍歷可以得到的一種頂點序列為()。A、aedfcbB、aedfbcC、aebcfdD、acfebd答案：A解析：124.快速排序最易發(fā)揮其長處的情況是()。A、被排序的數(shù)據(jù)中含有多個相同排序碼B、被排序的數(shù)據(jù)已基本有序C、被排序的數(shù)據(jù)完全無序D、被排序的數(shù)據(jù)中的最大值和最小值相差懸殊答案：C解析：125.假設(shè)以S和X分別表示進棧和出棧操作，則對輸入序列a，B，c，d，E進行一系列棧操作SSXSXSSXXX之后，得到的輸出序列為()。A.B，c，E，d，aB.B，E，c，a，dC.E，c，A、d，aB、c，C、D、a，d答案：A解析：a，B進棧(SS)，B出棧(X)，輸出“B”，c進棧(S)，c出棧(X)，輸出“c”，d，E進棧(SS)，E，d，a出棧(XXX)，輸出“E，d，a”，所以結(jié)果為B，c，E，d，a。126.在有n個結(jié)點的二叉鏈表中，值為非空的鏈域的個數(shù)為()。A、n-1B、2n-1C、n+1D、2n+1答案：A解析：本題考查的是二叉樹的鏈式存儲。由于在有n個結(jié)點的二叉鏈表中，值為空的鏈域的個數(shù)為n+1個，而總的鏈域為2n(在二叉樹中每個結(jié)點頭2個鏈域)。所以，非空的鏈域的個數(shù)為2n-(n+1)=n-1。127.循環(huán)隊列qu的隊空條件是()。A、(qu.rear+1)%MaxSize==(qu.front+1)%MaxSizeB、(qu.rear+1)%MaxSize-=qu.front+1C、(qu.rear+1)%MaxSize==qu.frontD、qu.rear==qu.front答案：D解析：循環(huán)隊列為空，當且僅當隊尾指針等于隊尾指針.具體的操作語句為qu.rear==qu.front。128.設(shè)有n個元素進棧序列是P1，P2，P3，…，Pn，其輸出序列是1，2，3，…，n，若P3=3，則P1的值()。A、可能是2B、一定是2C、不可能是1D、一定是1答案：A解析：進棧序列是P1，P2，P3，…，Pn，當P3=3時，由輸出序列可知，只有以下兩種情況：P1進棧后出棧，P2進棧后出棧，或P1、P2都進棧然后出棧，因此P1的值可能為1，也可能為2。129.設(shè)森林F對應的二叉樹為B，它有m個結(jié)點，B的根為p，p的右子樹結(jié)點個數(shù)為n，森林F中，第一棵樹的結(jié)點個數(shù)是()。A、m-nB、m-n-1C、n+1D、條件不足，無法確定答案：A解析：森林轉(zhuǎn)換成二叉樹的原則：將第一棵樹的根結(jié)點作為根結(jié)點，所有結(jié)點的第一個左孩子作為左孩子，下一個兄弟結(jié)點作為右孩子，其它樹作為第一棵樹的右孩子。所以森林F中第一棵樹的結(jié)點個數(shù)是m-n。130.A、AB、BC、CD、D答案：C解析：131.前序遍歷和中序遍歷結(jié)果相同的二叉樹是()。A、所有節(jié)點只有左子樹的二叉樹B、所有節(jié)點只有右子樹的二叉樹C、根節(jié)點無左孩子的二叉樹D、根節(jié)點無右孩子的二叉樹答案：B解析：前序遍歷是首先訪問根節(jié)點，然后前序遍歷左子樹，最后前序遍歷右子樹。中序遍歷是首先中序遍歷左子樹，然后訪問根節(jié)點，最后中序遍歷右子樹。當所有節(jié)點都沒有左子樹時，前序遍歷和中序遍歷的遍歷結(jié)果相同。132.算法分析的目的是()。A、找出數(shù)據(jù)結(jié)構(gòu)的合理性B、研究算法中輸入和輸出的關(guān)系C、分析算法的效率以求改進D、分析算法的易懂性和文檔性答案：C解析：算法分析的目的是分析算法的效率以求改進。133.順序查找不論在順序線性表中還是在鏈式線性表中的時間復雜度為()。A、AB、BC、CD、D答案：B論是順序存儲還是鏈式存儲，使用順序查找法的時間復雜度相同。134.棧S最多只能容納4個元素，現(xiàn)在6個元素按A，B，C，D，E，F(xiàn)的順序進棧，下列哪一個序列是可能的出棧序列()。A、EDCBAFB、BCEFADC、CBEDAFD、ADFEBC答案：C解析：一次進棧最多4個，即ABCD同時在棧中，則EDCBAF不可能，A項中，E和F還沒有進棧就已經(jīng)出棧；B項中，D元素不可能出棧在A的后面；D項中，最后兩個元素出棧順序也有誤。135.已知10個數(shù)據(jù)元素為(54，28，16，34，73，62，95，60，23，43)，按照依次插入結(jié)點的方法生成一棵二叉排序樹后，查找值為62的結(jié)點所需比較的次數(shù)為()。A、2B、3C、4D、5答案：B解析：將這10個元素按照依次插入結(jié)點的方法生成一棵二叉排序樹后，62位于這棵二叉排序樹的第三層，查找值為62的結(jié)點所需要的次數(shù)恰好是從二叉排序樹的根到被查結(jié)點的樹的深度。136.二叉排序樹中，最小值結(jié)點的()。A、左、右指針均為空B、左、右指針均不為空C、左指針一定為空D、右指針一定為空答案：C解析：在二叉排序樹中，值最小的結(jié)點一定是中序遍歷序列中第一個被訪問的結(jié)點，即二叉樹的最左下結(jié)點。137.在一個順序表的表尾插入一個元素的時間復雜性的量級為()。A、AB、BC、CD、D答案：C解析：在一個順序表的表尾插入一個元素移動次數(shù)為1次。138.以數(shù)組Q[0…m-1]存放循環(huán)隊列中的元素，若變量front和qulen分別指示循環(huán)隊列中隊頭元素的實際位置和當前隊列的長度，則隊尾元素的實際位置是()。A、front+qulen-1B、(front+qulen)modmC、(front+qulen-1)modmD、front+qulen答案：C解析：循環(huán)隊列的元素順序存儲在數(shù)組Q中，已知循環(huán)隊列中隊頭元素的存儲位置為front。當前隊列的長度為qulen，隊尾元素的位置要在front上加上qulen，然后減l(第一個元素存儲在front的位置上)，對于循環(huán)隊列求隊尾的位置還要對總長度求余，所以隊尾元素的實際位置為(front+qulen-1)modm。139.設(shè)一個順序有序表A[1：14]中有14個元素，則采用二分法查找元素A[4]的過程中比較元素的順序為()。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解析：二分查找法的每次比較都與中間值進行比較，第一次與位置7的元素比較，依次類推。140.在二叉排序樹中插入一個結(jié)點的時間復雜度為()。A、AB、BC、CD、D答案：B解析：在二叉排序樹中進行插入時最壞情況下時間復雜度是O(n)。141.非空的循環(huán)單鏈表FIRST的尾結(jié)點(由P所指向)滿足：()。A、P—＞EXT=NULL；B、P=NULL；C、P—NEXT-FIRST；D、P=FIRST；答案：C解析：循環(huán)單鏈表是單鏈表的一種特殊形式，其結(jié)構(gòu)特點是鏈表中最后一個結(jié)點的指針域不再是結(jié)束標記(NULL)，而是指向鏈表中的第一個結(jié)點，從而使鏈表形成一個環(huán)。在本題中，F(xiàn)IRST指向循環(huán)單鏈表的首結(jié)點，P指向尾結(jié)點，可知P—＞NEXI=FIRST。142.已知某二叉樹的中序、層序序列分別為DBAFCE、FDEBCA，則該二叉樹的后序序列為()。A、DBACEFB、DABECFC、BCDEAFD、ABDCEF答案：D解析：按照遍歷左子樹要在遍歷右子樹之前進行的原則，根據(jù)訪問根節(jié)點位置的不同，可得到二叉樹的前序，中序和后序3種遍歷方法。層序遍歷是從根節(jié)點(第1層)出發(fā)，首先訪問第1層的樹根節(jié)點，然后從左到右依次訪問第2層上的節(jié)點，其次是第3層上的節(jié)點，依此類推，自上而下，自左向右逐層訪問各層上的節(jié)點。對于二叉樹來說，第n層節(jié)點最多為2m1。由層序序列可得:F是樹根節(jié)點，D.E是第2層節(jié)點:結(jié)合中序序列有DBA構(gòu)成F的左子樹，CE構(gòu)成F的右子樹，進-一步有C是E的左節(jié)點、B無右節(jié)點:這樣A是第4層節(jié)點，據(jù)DBA序列有B是D的右節(jié)點.A是B的右節(jié)點。易知后序序列為ABDCEF.143.設(shè)指針變量p指向雙向鏈表中節(jié)點A，指針變量s指向被插入的節(jié)點X，則在節(jié)點A的后面插入節(jié)點X的操作序列為()A、p-＞right=s；s-＞left=p；p-＞right-＞left=s；s-＞right=p-＞right；B、p-＞right=s；p-＞right-＞left=s；s-＞left=p；s-＞right=p-＞right；C、s-＞left=p；s-＞right=p-＞right；p-＞right=s；p-＞right-＞left=s；D、s-＞left=p；s-＞right=p-＞right；p-＞right-＞left=s；p-＞right=s；答案：D解析：為了防止在插入節(jié)點時鏈表斷裂，在修改指針時，需要先使s的后繼指針指向p原來的后繼節(jié)點，然后修改p的后繼指針。144.設(shè)散列表表長m=14，散列函數(shù)H(k)=kmod11。表中已有15，38，61，84四個元素，如果用線性探測法處理沖突，則元素49的存儲地址是()。A、8B、3C、5D、9答案：A解析：元素15，38，61，84分別存儲在4，5，6，7單元，而元素49的散列地址為5，發(fā)生沖突，向后探測3個單元，其存儲地址為8。145.由權(quán)值分別為11，8，6，2，5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為()。A、53B、73C、48D、24答案：B解析：根據(jù)赫夫曼樹的構(gòu)造方法可構(gòu)造出赫夫曼樹，經(jīng)計算可得帶權(quán)路徑長度為73。146.m階B+樹中除根節(jié)點外，其他節(jié)點的關(guān)鍵字個數(shù)至少為()。A、[m/2]B、[m/2]-1C、[m/2]+1D、任意答案：A解析：這是B+樹的定義。147.設(shè)二叉排序樹上有n個結(jié)點，則在二叉排序樹上查找結(jié)點的平均時間復雜度為()。A、AB、BC、CD、D答案：D解析：148.若有18個元素的有序表存放在一維數(shù)組A[19]中，第一個元素放A[1]中，現(xiàn)進行二分查找，則查找A[3]的比較序列的下標依次為()。A、9，5，3B、9，5，2，3C、1，2，3D、9，4，2，3答案：D解析：二分查找的基本思想是將n個元素分成大致相等的兩部分，取中間位置的節(jié)點值與關(guān)鍵字做比較，如果相等，則查找成功；如果關(guān)鍵字的值小于中間節(jié)點，則只要在數(shù)組的左半部分繼續(xù)搜索，重復與中間值進行比較，直至查找成功或失??；如果關(guān)鍵字大于中間值，則只要在數(shù)組的右半部搜索即可。149.在一裸m階的B+樹中，每個非葉結(jié)點的兒子數(shù)S應滿足()。A、AB、BC、CD、D答案：A解析：m階B+樹包含如下兩個特點：(1)每個分支結(jié)點至多有m棵子樹。(2)除根結(jié)點外的所有非終端結(jié)點每個結(jié)點至少有1(m+1)/21棵子樹。150.兩個字符串相等的充要條件是()。A.兩個字符串中對應位置上的字符相等B.兩個字符串的長度相等A、同時具備B、和C、兩個條件D、兩個字符串的大小相等答案：C解析：兩個字符串相等是指兩個字符串不僅長度相等，而且在對應位置上的字符也要相等。151.在平衡二叉樹中，()。A、任意結(jié)點的左右子樹結(jié)點數(shù)目相同B、任意結(jié)點的左右子樹高度相同C、任意結(jié)點的左右子樹高度之差的絕對值不大于1D、不存在度為1的結(jié)點答案：C解析：該題考查考生對平衡二叉樹的理解，形態(tài)勻稱的二叉樹稱為平衡二叉樹，其嚴格定義是：一棵空樹是平衡二叉樹；T是一棵非空二叉樹，其左、右子樹為TL和TR，令h1和hr分別為左、右子樹的深度，當且僅當TL、TR都是平衡=叉樹且丨h(huán)1-hr丨≤1時，T是平衡二叉樹152.下列敘述中，不符合m階B樹定義要求的是()。A、根節(jié)點最多有m棵子樹B、所有葉結(jié)點都在同一層上C、各結(jié)點內(nèi)關(guān)鍵字均升序或降序排列D、葉結(jié)點之間通過指針鏈接答案：D解析：B樹的定義。153.數(shù)據(jù)的存儲結(jié)構(gòu)是指()。A、數(shù)組類型B、指針類型C、數(shù)據(jù)之間的邏輯關(guān)系D、數(shù)據(jù)之間的物理關(guān)系答案：D解析：數(shù)據(jù)的存儲結(jié)構(gòu)就是物理結(jié)構(gòu)，指數(shù)據(jù)之間的物理關(guān)系。154.假設(shè)執(zhí)行語句S的時間為0(1)，則執(zhí)行下列程序段的時間為()。for(i=l;k=n;it+)for(j=l;jA、0(n)B、0(n^2)C、O(n×i)D、0(n+1)答案：B解析：觀察可知，程序段S的執(zhí)行頻度為T(n)=n^2，得時間復雜度T(n)=O(n^2)。155.鏈表不具有的特點是()。A、不必事先估計存儲空間B、可隨機訪問任一元素C、插入刪除不需要移動元素D、所需空間與線性表長度成正比答案：B解析：鏈表采用的是鏈式存儲結(jié)構(gòu)，它克服了順序存儲結(jié)構(gòu)的缺點：①它的結(jié)點空間可以動態(tài)申請和釋放；②它的數(shù)據(jù)元素的邏輯次序靠結(jié)點的指針來指示，不需要移動數(shù)據(jù)元素。但是鏈式存儲結(jié)構(gòu)也有不足之處：①每個結(jié)點中的指針域需額外占用存儲空間；②鏈式存儲結(jié)構(gòu)是一種非隨機存儲結(jié)構(gòu)。156.以下敘述不正確的是()。A、后序線索二叉樹是不完善的，要對它進行遍歷，不需使用棧B、任何一棵二叉樹的后序線索樹進行后序遍歷時都必須使用棧C、任何一棵二叉樹都可以不用棧實現(xiàn)先序線索樹的先序遍歷D、任何一棵二叉樹都可以不用棧實現(xiàn)中序線索樹的中序遍歷答案：B解析：遍歷后序線索二叉樹不需要使用棧。157.設(shè)有n個待排序的記錄關(guān)鍵字，則在堆排序中需要()個輔助記錄單元。A、AB、BC、CD、D答案：A解析：堆排序的輔助空間為0(1)。158.時間復雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為0(nlog2n)的是()。A、堆排序B、快速排序C、希爾排序D、冒泡排序答案：A解析：堆排序無論是最好情況還是最壞情況，時間復雜度都是相等的。159.在二叉樹的順序存儲中，每個結(jié)點的存儲位置與其父結(jié)點、左右子樹結(jié)點的位置都存在一個簡單的映射關(guān)系，因此可與三叉鏈表對應。若某二叉樹共有n個結(jié)點，采用三叉鏈表存儲時，每個結(jié)點的數(shù)據(jù)域需要d個字節(jié)，每個指針域占用4個字節(jié)，若采用順序存儲，則最后一個結(jié)點下標為k(起始下標為1)，采用順序存儲更節(jié)省空間的情況是()。A、d＜12n/(k-n)B、d＞12n/(k-n)C、d＜12n/(k+n)D、d＞12n/(k+n)答案：A解析：160.如下陳述中正確的是()。A、串是一種特殊的線性表B、串的長度必須大于零C、串中元素只能是字母D、空串就是空白串答案：A解析：串的長度可以等于0，等于0時叫作空串?？沾涂瞻状遣煌模纾篠trings=“”，是空串；Strings=NULL，是空白串。串中的元素只能是字符，但不僅僅是字母。161.關(guān)于哈夫曼樹，下列說法正確的是()。A、在哈夫曼樹中，權(quán)值相同的葉子結(jié)點都在同一層上B、在哈夫曼樹中，權(quán)值較大的葉子結(jié)點一般離根結(jié)點較遠C、哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點離根較近D、在哈夫曼編碼中，當兩個字符出現(xiàn)頻率相同時，其編碼也相同，對于這種情況應作特殊外理答案：C解析：哈弗曼編碼中不允許出現(xiàn)兩個字符編碼相同的情況。162.中綴表達式A-(B+C/D)*E的后綴形式是()。A、AB-C+D/E*B、ABC+D/-E*C、ABCD/E*+-D、ABCD/+E*-答案：D解析：將中綴表達式表示成二叉樹的形狀，則這棵二叉樹的后序遍歷序列即為表達式的后綴形式。163.用鄰接矩陣A表示圖，判定任意兩個頂點Vi和Vj之間是否有長度m路徑相連，則只要檢查()的第i行和第j列的元素是否為零即可。A、mAB、AC、AmD、Am-1答案：C解析：要判斷相鄰矩陣A中任意兩個頂點Vi和Vj之間是否有長度為m的路徑相連，只要檢查Am的第i行第j的元素是否為0即可，若為0則無，否則就存在。164.下面關(guān)于工程計劃的AOE網(wǎng)的敘述中，不正確的是()。A、某些關(guān)鍵活動若提前完成，那么整個工程將會提前完B、關(guān)鍵活動不按期完成就會影響整個工程的完成時間C、任何一個關(guān)鍵活動提前完成，那么整個工程將會提前完成D、所有的關(guān)鍵活動都提前完成，那么整個工程將會提前完成答案：C解析：AOE網(wǎng)中的關(guān)鍵路徑可能不止一條，如果某一個關(guān)鍵活動提前完成，還不能提前整個工程，則必須同時提高在幾條關(guān)鍵路徑上的關(guān)鍵活動。165.已知一棵完全二叉樹的第6層(設(shè)根為第1層)有8個葉結(jié)點，則完全二叉樹的結(jié)點個數(shù)最多是()。A、39B、52C、111D、119答案：C解析：根據(jù)完全二查處定義，前6層應該是滿二叉樹，共有2^6-1=63個結(jié)點。第6層有8個葉節(jié)點。說明有32-8=24個結(jié)點不是葉節(jié)點，因此最多時共有63+24*2=111個。166.下列敘述正確的個數(shù)是()。(1)向二叉排序樹中插入一個結(jié)點，所需比較的次數(shù)可能大于此二叉排序樹的高度。(2)對B-樹中任一非葉子結(jié)點中的某關(guān)鍵字K，比K小的最大關(guān)鍵字和比K大的最小關(guān)鍵字一定都在葉子結(jié)點中。(3)所謂平衡二叉樹是指左、右子樹的高度差的絕對值不大于1的二叉樹。(4)刪除二叉排序樹中的一個結(jié)點，再重新插入，一定能得到原來的二又排序樹。A、4B、3C、2D、1答案：D解析：只有第3項是正確的。167.下列說法正確的是()。A、任何有向網(wǎng)絡(luò)(AOV-網(wǎng))拓撲排序的結(jié)果是唯一的B、有回路的圖不能進行拓撲排序C、在AOE網(wǎng)中一定只有一條關(guān)鍵路徑D、一個正常的AOE網(wǎng)中只能有一個源點、一小匯點和一條關(guān)鍵路徑答案：B解析：拓撲排序的結(jié)果不一定是唯一的；在AOE網(wǎng)中，關(guān)鍵路徑不止一條。168.設(shè)有一個二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每個元素占一個空間，問A[3][3]存放在什么位置？腳注(10)表示用10進制表示。()A、678B、688C、692D、696答案：C解析：A[2][2]是A[0][0]后面的第2n+2個元素，即2n+2=676-644，解得n=15。A[3][3]是A[2][2]后面的第n+1個元素，676+n+1=692，則A[3][3]存放位置是692。169.n個結(jié)點的線索二叉樹上含有的線索數(shù)為()。A、nB、2nC、n-1D、n+1答案：D解析：對于有n個結(jié)點的二叉樹，采用二叉鏈存儲結(jié)構(gòu)時，每個結(jié)點有兩個指針域，總共有2n個指針域，由于只有n-1個結(jié)點被有效指針所指向.則共有2n-(n-1)=n+1個空鏈域。用這些空鏈域存放指向結(jié)點的前驅(qū)和后繼結(jié)點的指針，這些指針稱作線索。170.已知輸入序列為abcd，經(jīng)過輸出受限的雙端隊列后，能得到的輸出序列是()。A、dacbB、cadbC、dbcaD、以上答案都不對答案：B解析：輸出受限的雙端隊列是指刪除限制在一端進行，而插入允許在兩端進行的隊列。A項，輸入序列為abcd，輸出序列為dacb，由輸出受限性質(zhì)可知以da開頭的結(jié)果只有dabc。B項，輸入序列為abcd，輸出序列為cadb，其輸入輸出順序為：先在輸出端輸入a，然后在非輸出端輸入b，這時隊列中的序列為ba，再在輸出端輸入c，這時隊列中的序列為bac；輸出c，再輸出a；再在輸出端輸入d，這時隊列中的序列為bd；輸出d，再輸出b。最后得到輸出序列為cadb。C項，輸入序列為abcd，輸出序列為dbca，由輸出受限性質(zhì)可知以db開頭的結(jié)果只有dbac。171.有種關(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)A、B、Y)C、D、T)答案：B解析：由題可得如下推導：(H，S)+R，(H，R)+C，C--4T，(H，T)--4R，故可知(H，S)為關(guān)系模式的碼。172.在雙向循環(huán)鏈表中，在p所指的結(jié)點之后插入指針f所指的新結(jié)點，其操作步驟是()。A、AB、BC、CD、D答案：D解析：在雙向循環(huán)鏈表中。在p所指的結(jié)點之后插入指針f所指的新結(jié)點的操作步驟為：改變f的前驅(qū)指針域，使其指向p；然后改變f的后繼指針域，使其指向p的后繼；接下來修改p的后繼結(jié)點得前驅(qū)指針域，指向f，最后將f的地址付給p的后繼指針。具體操作為：f—＞pnor=p；f—＞next=p—＞next；p—＞next—＞prior=f；P—＞next=f。173.當各邊上的權(quán)值滿足()的條件時，BFS算法可用來解決單源最短路徑問題。A、均相等B、均互不相等C、不一定相等D、其他答案：A解析：單源最短路徑問題是指：從已知圖G=(V，E)中找出某給定的源結(jié)點S∈V到V中的每個結(jié)點的最短路徑。當各邊上的權(quán)值均相等時，BFS算法可用來解決單源最短路徑問題。174.A、LRNB、NRLC、RLND、RNL答案：D解析：由7，5，6的順序可知遍歷順序為RNL。175.字符串的長度是指()。A、串中不同字母的個數(shù)B、串中字符不同的個數(shù)C、串中不同數(shù)字的個數(shù)D、串中所含字符的個數(shù)答案：D解析：字符串的長度是指串中所含的字符的個數(shù)。176.由元素序列(27，16，75，38，51)構(gòu)造平衡二叉樹，則首次出現(xiàn)的最小不平衡子樹的根(即離插入結(jié)點最近且平衡因子的絕對值為2的結(jié)點)為()。A、27B、38C、51D、75答案：D解析：177.在長度為n(Il＞1)的()上，刪除第一個元素.其時間復雜度為O(n)。A、只有首結(jié)點指針的不帶頭結(jié)點的循環(huán)單鏈表B、只有尾結(jié)點指針的不帶頭結(jié)點的循環(huán)單鏈表C、只有尾結(jié)點指針的帶頭結(jié)點的循環(huán)單鏈表D、只有頭結(jié)點的循環(huán)單鏈表答案：A解析：只有首結(jié)點指針的不帶頭結(jié)點的循環(huán)單鏈表刪除第一個元素，需要遍歷整個鏈表，因此A項的時間復雜度為O(n)，BCD三項的時間復雜度都為O(1)。178.引入二叉線索樹的目的是()。A、加快查找結(jié)點的前驅(qū)或后繼的速度B、為了能在二叉樹中方便地進行插入與刪除C、為了能方便地找到雙親D、使二叉樹的遍歷結(jié)果唯一答案：A解析：當以二叉鏈表作為存儲結(jié)構(gòu)存儲非線索化的二叉樹時，只能找到結(jié)點的左、右孩子信息，而不能直接得到結(jié)點在任一遍歷序列中的直接前驅(qū)和直接后繼的結(jié)點信息，這種信息只有在遍歷的動態(tài)過程中才能得到。二叉線索樹利用空鏈域存放結(jié)點的前驅(qū)和后繼結(jié)點的信息，這樣能保存遍歷過程中得到的信息。可見，引入二叉線索樹的目的是方便查找結(jié)點的前驅(qū)或后繼結(jié)點的速度。179.如果一棵完全二叉樹共有26個結(jié)點，則必定有()個結(jié)點的度為1。A、0B、1C、3D、13答案：B解析：26個結(jié)點，可知該二叉樹有5層。由于前4層組成一棵滿二叉樹，共15個結(jié)點，則共有11個葉子結(jié)點，可知只有1個結(jié)點的度為1。180.在平衡二叉樹中插入一個結(jié)點后造成了不平衡，設(shè)最低的不平衡結(jié)點為A，并已知A的左孩子的平衡因子為0，右孩子的平衡因子為1，則應作()型調(diào)整以使其平衡。A、LLB、LRC、RLD、RR答案：C解析：平衡二叉樹是在構(gòu)造=叉排序樹的過程中，每當插入一個新結(jié)點時，首先檢查是否因插入新結(jié)點而破壞了二叉排序樹的平衡性，若是，則找出其中的最小不平衡子樹，在保持二叉排序樹特性的前提下，調(diào)整最小不平衡子樹中各結(jié)點之間的鏈接關(guān)系。進行相應的旋轉(zhuǎn)，使之成為新的平衡子樹。具體步驟如下：(1)每當插入一個新結(jié)點，從該結(jié)點開始向上計算各結(jié)點的平衡因子，即計算該結(jié)點的祖先結(jié)點的平衡因子，若該結(jié)點的祖先結(jié)點的平衡因子的絕對值均不超過1，則平衡=叉樹沒有失去平衡，繼續(xù)插入、結(jié)點；(2)若插入結(jié)點的某祖先結(jié)點的平衡因子的絕對值大于1，則找出其中最小不平衡子樹的根結(jié)點；(3)判斷新插入的結(jié)點與最小不平衡子樹的根結(jié)點的關(guān)系，確定是哪種類型的調(diào)整；(4)如果是LL型或RR型，只需應用扁擔原理旋轉(zhuǎn)一次，在旋轉(zhuǎn)過程中，如果出現(xiàn)沖突，應用旋轉(zhuǎn)優(yōu)先原則調(diào)整沖突；如果是LR型或LR型，則需應用扁擔原理旋轉(zhuǎn)兩次，第一次最小不平衡子樹的根結(jié)點先不動，調(diào)整插入結(jié)點所在子樹，第二次再調(diào)整最小不平衡子樹。在旋轉(zhuǎn)過程中，如果出現(xiàn)沖突，應用旋轉(zhuǎn)優(yōu)先原則調(diào)整沖突；(5)計算調(diào)整后的平衡二叉樹中各結(jié)點的平衡因子，檢驗是否因為旋轉(zhuǎn)而破壞其他結(jié)點的平衡因子，以及調(diào)整后的平衡二叉樹中是否存在平衡因子大于1的結(jié)點。結(jié)合上面的知識點，對于題目中的情況應該選擇RL型調(diào)整。181.串′ababaaababaa′的next數(shù)組值為()。A、01