12月數(shù)據(jù)結(jié)構(gòu)與算法測(cè)試題（含答案）一、單選題（共60題，每題1分，共60分）1.題目：T(n)表示當(dāng)輸入規(guī)模為n時(shí)的算法效率，以下算法中效率最優(yōu)的是()。選項(xiàng)【A】T(n)=2n2選項(xiàng)【B】T(n)=T(n/2)+1,T(1)=1選項(xiàng)【C】T(n)=3nlog2n選項(xiàng)【D】T(n)=T(n-1)+1,T(1)=1答案：B2.題目：下列哪個(gè)函數(shù)是O(N)的？選項(xiàng)【A】N2/1000選項(xiàng)【B】(logN)2選項(xiàng)【C】N(logN)2選項(xiàng)【D】(NlogN)/1000答案：B答案說(shuō)明：對(duì)于時(shí)間復(fù)雜度為O(N)的函數(shù)，其增長(zhǎng)速度應(yīng)該與N成正比。選項(xiàng)A中(logN)2增長(zhǎng)速度遠(yuǎn)遠(yuǎn)慢于N，所以它是O(N)；選項(xiàng)B中NlogN增長(zhǎng)速度快于N，不是O(N)；選項(xiàng)C中N(logN)2增長(zhǎng)速度也快于N，不是O(N)；選項(xiàng)D中N2/1000增長(zhǎng)速度更快，不是O(N)。3.題目：利用大小為n的數(shù)組（下標(biāo)從0到n-1）存儲(chǔ)一個(gè)棧時(shí)，假定棧從數(shù)組另一頭開(kāi)始且top==n表示棧空，則向這個(gè)棧插入一個(gè)元素時(shí)，修改top指針應(yīng)當(dāng)執(zhí)行：選項(xiàng)【A】top++選項(xiàng)【B】top=0選項(xiàng)【C】top不變選項(xiàng)【D】top--答案：D答案說(shuō)明：棧從數(shù)組另一頭開(kāi)始且top==n表示?？眨迦朐貢r(shí)棧頂位置應(yīng)該減小，所以執(zhí)行top--。4.題目：對(duì)于一個(gè)具有N個(gè)頂點(diǎn)的無(wú)向圖，要連通所有頂點(diǎn)至少需要多少條邊？選項(xiàng)【A】N?1選項(xiàng)【B】N+1選項(xiàng)【C】N選項(xiàng)【D】N/2答案：A答案說(shuō)明：對(duì)于一個(gè)具有N個(gè)頂點(diǎn)的無(wú)向圖，要連通所有頂點(diǎn)至少需要N-1條邊。這是因?yàn)樵谝粋€(gè)連通圖中，邊的數(shù)量至少要比頂點(diǎn)數(shù)少1才能確保所有頂點(diǎn)都相互連接。例如，當(dāng)有2個(gè)頂點(diǎn)時(shí)，至少需要1條邊來(lái)連通；有3個(gè)頂點(diǎn)時(shí)，至少需要2條邊來(lái)連通，以此類(lèi)推。所以連通所有頂點(diǎn)至少需要N-1條邊，大于N-1條邊能更好地保證圖的連通性。5.題目：若結(jié)點(diǎn)p與q在二叉樹(shù)T的中序遍歷序列中相鄰，且p在q之前，則下列p與q的關(guān)系中，不可能的是I.q是p的雙親II.q是p的右孩子III.q是p的右兄弟IV.q是p的雙親的雙親選項(xiàng)【A】?jī)HII、III選項(xiàng)【B】?jī)HIII選項(xiàng)【C】?jī)HII、IV選項(xiàng)【D】?jī)HI答案：B答案說(shuō)明：1.首先分析選項(xiàng)I：-若q是p的雙親，在中序遍歷中，雙親節(jié)點(diǎn)會(huì)在其左子樹(shù)節(jié)點(diǎn)之后被訪問(wèn)，所以p和q不可能在中序遍歷序列中相鄰且p在q之前，該選項(xiàng)不可能。2.接著看選項(xiàng)II：-若q是p的右孩子，那么在中序遍歷中，p會(huì)先被訪問(wèn)，然后是p的左子樹(shù)節(jié)點(diǎn)，最后才是q，所以p和q可能在中序遍歷序列中相鄰且p在q之前，該選項(xiàng)可能。3.再看選項(xiàng)III：-二叉樹(shù)節(jié)點(diǎn)之間的兄弟關(guān)系與中序遍歷順序無(wú)關(guān)，因?yàn)橹行虮闅v是按照左子樹(shù)、根節(jié)點(diǎn)、右子樹(shù)的順序訪問(wèn)，所以q是p的右兄弟不影響中序遍歷中p和q的相鄰順序，該選項(xiàng)可能。4.最后看選項(xiàng)IV：-若q是p的雙親的雙親，那么在中序遍歷中，q會(huì)在p之前被訪問(wèn)，不符合p在q之前的條件，該選項(xiàng)不可能。-所以不可能的是選項(xiàng)I和IV，而選項(xiàng)III是可能的，答案選B。6.題目：在用鄰接表表示有N個(gè)結(jié)點(diǎn)E條邊的圖時(shí)，深度優(yōu)先遍歷算法的時(shí)間復(fù)雜度為：選項(xiàng)【A】O(N2)選項(xiàng)【B】O(N2×E)選項(xiàng)【C】O(N)選項(xiàng)【D】O(N+E)答案：D答案說(shuō)明：深度優(yōu)先遍歷算法在鄰接表表示的圖中，每個(gè)頂點(diǎn)會(huì)被訪問(wèn)一次，時(shí)間復(fù)雜度為O(N)，對(duì)于每條邊，在遍歷過(guò)程中最多被檢查兩次（正向和反向），時(shí)間復(fù)雜度為O(E)，所以總的時(shí)間復(fù)雜度為O(N+E)。7.題目：在具有N個(gè)結(jié)點(diǎn)的單鏈表中，實(shí)現(xiàn)下列哪個(gè)操作，其算法的時(shí)間復(fù)雜度是O(N)？選項(xiàng)【A】刪除開(kāi)始結(jié)點(diǎn)選項(xiàng)【B】遍歷鏈表和求鏈表的第i個(gè)結(jié)點(diǎn)選項(xiàng)【C】刪除地址為p的結(jié)點(diǎn)的后繼結(jié)點(diǎn)選項(xiàng)【D】在地址為p的結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)答案：B答案說(shuō)明：選項(xiàng)A：在地址為p的結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)，只需修改指針，時(shí)間復(fù)雜度為O(1)；選項(xiàng)B：刪除開(kāi)始結(jié)點(diǎn)，修改頭指針即可，時(shí)間復(fù)雜度為O(1)；選項(xiàng)C：遍歷鏈表需要從頭遍歷到尾，求鏈表的第i個(gè)結(jié)點(diǎn)也需要遍歷到第i個(gè)位置，時(shí)間復(fù)雜度為O(N)；選項(xiàng)D：刪除地址為p的結(jié)點(diǎn)的后繼結(jié)點(diǎn)，找到p的后繼并修改指針，時(shí)間復(fù)雜度為O(1)。8.題目：若一個(gè)棧的入棧序列為1、2、3、…、N，其輸出序列為p1、p2、p3、…、pN。若p1=N，則pi為：選項(xiàng)【A】n?i選項(xiàng)【B】i選項(xiàng)【C】n?i+1選項(xiàng)【D】不確定答案：C9.題目：現(xiàn)有長(zhǎng)度為7、初始為空的散列表HT，散列函數(shù)H(k)=k%7，用線性探測(cè)再散列法解決沖突。將關(guān)鍵字22,43,15依次插入到HT后，查找成功的平均查找長(zhǎng)度是：選項(xiàng)【A】3選項(xiàng)【B】1.6選項(xiàng)【C】1.5選項(xiàng)【D】2答案：D答案說(shuō)明：1.首先插入關(guān)鍵字22：-計(jì)算散列地址：\(H(22)=22\%7=1\)，此時(shí)\(HT[1]\)為空，所以\(22\)插入到\(HT[1]\)。2.接著插入關(guān)鍵字43：-計(jì)算散列地址：\(H(43)=43\%7=1\)，此時(shí)\(HT[1]\)已被\(22\)占用，發(fā)生沖突。-采用線性探測(cè)再散列法，計(jì)算下一個(gè)地址：\(H_1=(1+1)\%7=2\)，\(HT[2]\)為空，所以\(43\)插入到\(HT[2]\)。3.然后插入關(guān)鍵字15：-計(jì)算散列地址：\(H(15)=15\%7=1\)，\(HT[1]\)被占用。-計(jì)算下一個(gè)地址：\(H_1=(1+1)\%7=2\)，\(HT[2]\)被占用。-計(jì)算下一個(gè)地址：\(H_2=(1+2)\%7=3\)，\(HT[3]\)為空，所以\(15\)插入到\(HT[3]\)。4.計(jì)算查找成功的平均查找長(zhǎng)度：-查找22時(shí)，比較1次就找到，查找長(zhǎng)度為1。-查找43時(shí)，比較2次找到，查找長(zhǎng)度為2。-查找15時(shí)，比較3次找到，查找長(zhǎng)度為3。-平均查找長(zhǎng)度\(ASL=(1+2+3)/3=2\)。所以查找成功的平均查找長(zhǎng)度大于2，答案選[C]。10.題目：已知二維數(shù)組A按行優(yōu)先方式存儲(chǔ)，每個(gè)元素占用1個(gè)存儲(chǔ)單元。若元素A[0][0]的存儲(chǔ)地址是100，A[3][3]的存儲(chǔ)地址是220，則元素A[5][5]的存儲(chǔ)地址是：選項(xiàng)【A】301選項(xiàng)【B】300選項(xiàng)【C】295選項(xiàng)【D】306答案：B11.題目：某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用什么存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間？選項(xiàng)【A】?jī)H有頭指針的單循環(huán)鏈表選項(xiàng)【B】?jī)H有尾指針的單循環(huán)鏈表選項(xiàng)【C】單鏈表選項(xiàng)【D】雙鏈表答案：B答案說(shuō)明：在僅有尾指針的單循環(huán)鏈表中，插入操作可直接在尾指針?biāo)腹?jié)點(diǎn)后插入，時(shí)間復(fù)雜度為O(1)；刪除第一個(gè)元素時(shí)，需要遍歷鏈表找到尾節(jié)點(diǎn)，使其指向原第二個(gè)節(jié)點(diǎn)，時(shí)間復(fù)雜度為O(n)。但整體對(duì)于題目中最常用的這兩個(gè)操作，相對(duì)其他選項(xiàng)更節(jié)省運(yùn)算時(shí)間。單鏈表插入最后一個(gè)元素時(shí)間復(fù)雜度為O(n)；僅有頭指針的單循環(huán)鏈表刪除第一個(gè)元素時(shí)間復(fù)雜度為O(n)；雙鏈表插入最后一個(gè)元素時(shí)間復(fù)雜度為O(n)，刪除第一個(gè)元素時(shí)間復(fù)雜度也為O(n)。12.題目：被計(jì)算機(jī)加工的數(shù)據(jù)元素不是孤立的，它們彼此之間一般存在某種關(guān)系，通常把數(shù)據(jù)元素之間的這種關(guān)系稱(chēng)為選項(xiàng)【A】集合選項(xiàng)【B】結(jié)構(gòu)選項(xiàng)【C】規(guī)則選項(xiàng)【D】運(yùn)算答案：B答案說(shuō)明：數(shù)據(jù)元素之間的關(guān)系稱(chēng)為結(jié)構(gòu)。結(jié)構(gòu)描述了數(shù)據(jù)元素之間的邏輯關(guān)系，它決定了數(shù)據(jù)的組織方式和訪問(wèn)方式等。規(guī)則通常是關(guān)于行為、操作等方面的規(guī)定；集合是具有某種特定性質(zhì)的具體的或抽象的對(duì)象匯總成的集體；運(yùn)算則是對(duì)數(shù)據(jù)進(jìn)行的操作。所以數(shù)據(jù)元素之間的關(guān)系用結(jié)構(gòu)來(lái)描述更為合適。13.題目：設(shè)一個(gè)堆棧的入棧順序是1、2、3、4、5。若第一個(gè)出棧的元素是4，則最后一個(gè)出棧的元素必定是：選項(xiàng)【A】1選項(xiàng)【B】5選項(xiàng)【C】1或者5選項(xiàng)【D】3答案：C14.題目：采用遞歸方式對(duì)順序表進(jìn)行快速排序，下列關(guān)于遞歸次數(shù)的敘述中，正確的是：選項(xiàng)【A】遞歸次數(shù)與每次劃分后得到的分區(qū)處理順序無(wú)關(guān)選項(xiàng)【B】每次劃分后，先處理較短的分區(qū)可以減少遞歸次數(shù)選項(xiàng)【C】每次劃分后，先處理較長(zhǎng)的分區(qū)可以減少遞歸次數(shù)選項(xiàng)【D】遞歸次數(shù)與初始數(shù)據(jù)的排列次序無(wú)關(guān)答案：A答案說(shuō)明：快速排序的遞歸次數(shù)取決于遞歸樹(shù)的深度，而遞歸樹(shù)的深度主要由每次劃分后兩個(gè)分區(qū)的長(zhǎng)度差異決定。每次劃分都是將數(shù)組分為兩個(gè)子數(shù)組，無(wú)論先處理哪個(gè)分區(qū)，最終遞歸樹(shù)的深度是固定的，即遞歸次數(shù)與每次劃分后得到的分區(qū)處理順序無(wú)關(guān)。對(duì)于選項(xiàng)A和B，先處理較長(zhǎng)或較短的分區(qū)并不能改變遞歸樹(shù)的深度，所以不能減少遞歸次數(shù)。選項(xiàng)D，初始數(shù)據(jù)的排列次序會(huì)影響每次劃分的結(jié)果，進(jìn)而影響遞歸樹(shù)的深度，也就是影響遞歸次數(shù)。15.題目：如果A和B都是二叉樹(shù)的葉結(jié)點(diǎn)，那么下面判斷中哪個(gè)是對(duì)的？選項(xiàng)【A】存在一種二叉樹(shù)結(jié)構(gòu)，其前序遍歷結(jié)果是…A…B…，而后序遍歷結(jié)果是…B…A…選項(xiàng)【B】以上三種都是錯(cuò)的選項(xiàng)【C】存在一種二叉樹(shù)結(jié)構(gòu)，其中序遍歷結(jié)果是…A…B…，而后序遍歷結(jié)果是…B…A…選項(xiàng)【D】存在一種二叉樹(shù)結(jié)構(gòu)，其前序遍歷結(jié)果是…A…B…，而中序遍歷結(jié)果是…B…A…答案：B答案說(shuō)明：前序遍歷是根左右，中序遍歷是左根右，后序遍歷是左右根。對(duì)于葉節(jié)點(diǎn)A和B，若前序遍歷結(jié)果是…A…B…，那么A是根節(jié)點(diǎn)或者A的父節(jié)點(diǎn)是根節(jié)點(diǎn)，若中序遍歷結(jié)果是…B…A…，那么B是根節(jié)點(diǎn)或者B的父節(jié)點(diǎn)是根節(jié)點(diǎn)，二者矛盾，所以A選項(xiàng)錯(cuò)誤；同理，若中序遍歷結(jié)果是…A…B…，而后序遍歷結(jié)果是…B…A…，也會(huì)產(chǎn)生矛盾，B選項(xiàng)錯(cuò)誤；若前序遍歷結(jié)果是…A…B…，而后序遍歷結(jié)果是…B…A…，同樣會(huì)產(chǎn)生矛盾，C選項(xiàng)錯(cuò)誤。所以以上三種都是錯(cuò)的，選D。16.題目：有組記錄的排序碼為{46，79，56，38，40，84}，采用快速排序（以位于最左位置的對(duì)象為基準(zhǔn)而）得到的第一次劃分結(jié)果為：選項(xiàng)【A】{38,79,56,46,40,84}選項(xiàng)【B】{38,46,56,79,40,84}選項(xiàng)【C】{38,46,79,56,40,84}選項(xiàng)【D】{40,38,46,56,79,84}答案：D17.題目：下列幾組概念中，那一組不完全跟搜索引擎有關(guān)？選項(xiàng)【A】停用詞，倒排表，動(dòng)態(tài)索引選項(xiàng)【B】閾值設(shè)置，動(dòng)態(tài)規(guī)劃，準(zhǔn)確率選項(xiàng)【C】詞干提取，壓縮，召回率選項(xiàng)【D】分布式索引，哈希散列，倒排文件索引答案：B答案說(shuō)明：閾值設(shè)置、動(dòng)態(tài)規(guī)劃主要是算法和技術(shù)概念，與搜索引擎沒(méi)有直接關(guān)聯(lián)；準(zhǔn)確率是評(píng)估搜索引擎等信息檢索系統(tǒng)性能的指標(biāo)之一，但前兩者與搜索引擎不完全相關(guān)。而詞干提取、停用詞處理等是搜索引擎文本處理的常見(jiàn)操作；分布式索引、倒排文件索引等是搜索引擎索引構(gòu)建的關(guān)鍵技術(shù)；所以答案是[A]18.題目：為解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問(wèn)題，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫(xiě)入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是？選項(xiàng)【A】樹(shù)選項(xiàng)【B】隊(duì)列選項(xiàng)【C】圖選項(xiàng)【D】堆棧答案：B答案說(shuō)明：隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，主機(jī)將要輸出的數(shù)據(jù)依次寫(xiě)入緩沖區(qū)，符合先進(jìn)先出的特點(diǎn)；打印機(jī)依次從緩沖區(qū)中取出數(shù)據(jù)，也符合先進(jìn)先出的特點(diǎn)，所以該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是隊(duì)列。而堆棧是后進(jìn)先出，樹(shù)和圖不符合這種數(shù)據(jù)處理的邏輯。19.題目：以下數(shù)據(jù)結(jié)構(gòu)中，（）是非線性數(shù)據(jù)結(jié)構(gòu)。選項(xiàng)【A】棧選項(xiàng)【B】樹(shù)選項(xiàng)【C】字符串選項(xiàng)【D】隊(duì)列答案：B答案說(shuō)明：樹(shù)是一種非線性數(shù)據(jù)結(jié)構(gòu)，它具有層次結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)可以有多個(gè)子節(jié)點(diǎn)。字符串是線性的數(shù)據(jù)序列。隊(duì)列是一種線性數(shù)據(jù)結(jié)構(gòu)，遵循先進(jìn)先出的原則。棧也是一種線性數(shù)據(jù)結(jié)構(gòu)，遵循后進(jìn)先出的原則。20.題目：對(duì)二叉搜索樹(shù)進(jìn)行什么遍歷可以得到從小到大的排序序列？選項(xiàng)【A】前序遍歷選項(xiàng)【B】中序遍歷選項(xiàng)【C】后序遍歷選項(xiàng)【D】層次遍歷答案：B答案說(shuō)明：二叉搜索樹(shù)的特點(diǎn)是左子樹(shù)所有節(jié)點(diǎn)的值小于根節(jié)點(diǎn)的值，右子樹(shù)所有節(jié)點(diǎn)的值大于根節(jié)點(diǎn)的值。中序遍歷的順序是先遍歷左子樹(shù)，再訪問(wèn)根節(jié)點(diǎn)，最后遍歷右子樹(shù)。因此，對(duì)二叉搜索樹(shù)進(jìn)行中序遍歷可以得到從小到大的排序序列。前序遍歷是先訪問(wèn)根節(jié)點(diǎn)，再遍歷左子樹(shù)和右子樹(shù)；后序遍歷是先遍歷左子樹(shù)和右子樹(shù)，最后訪問(wèn)根節(jié)點(diǎn)；層次遍歷是按照層次依次訪問(wèn)節(jié)點(diǎn)，它們都不能直接得到從小到大的排序序列。21.題目：某二叉樹(shù)的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹(shù)一定是（）選項(xiàng)【A】二叉排序樹(shù)選項(xiàng)【B】高度等于其節(jié)點(diǎn)數(shù)選項(xiàng)【C】空或只有一個(gè)節(jié)點(diǎn)選項(xiàng)【D】完全二叉樹(shù)答案：B答案說(shuō)明：對(duì)于先序遍歷序列和后序遍歷序列正好相反的二叉樹(shù)，其特點(diǎn)是每層只有一個(gè)節(jié)點(diǎn)，所以高度等于其節(jié)點(diǎn)數(shù)?？諛?shù)或只有一個(gè)節(jié)點(diǎn)時(shí)先序和后序序列相同；完全二叉樹(shù)不滿足先序和后序相反的條件；二叉排序樹(shù)也不一定先序和后序相反。22.題目：將M個(gè)元素存入用長(zhǎng)度為S的數(shù)組表示的散列表，則該表的裝填因子為：選項(xiàng)【A】M?S選項(xiàng)【B】M×S選項(xiàng)【C】S+M選項(xiàng)【D】M/S答案：D答案說(shuō)明：裝填因子的定義是散列表中已存入元素的個(gè)數(shù)與散列表長(zhǎng)度的比值。題目中已存入元素個(gè)數(shù)為M，散列表長(zhǎng)度為S，所以裝填因子為M/S。23.題目：下面描述中正確的為()。選項(xiàng)【A】線性表的邏輯順序與物理順序總是一致的選項(xiàng)【B】線性表若采用鏈?zhǔn)酱鎯?chǔ)表示時(shí)所有結(jié)點(diǎn)之間的存儲(chǔ)單元地址可連續(xù)可不連續(xù)。選項(xiàng)【C】二維數(shù)組是其數(shù)組元素為線性表的線性表。選項(xiàng)【D】線性表的順序存儲(chǔ)表示優(yōu)于鏈?zhǔn)酱鎯?chǔ)表示。答案：B24.題目：下列排序算法中，哪種算法可能出現(xiàn)：在最后一趟開(kāi)始之前，所有的元素都不在其最終的位置上？（設(shè)待排元素個(gè)數(shù)N>2）選項(xiàng)【A】冒泡排序選項(xiàng)【B】堆排序選項(xiàng)【C】插入排序選項(xiàng)【D】快速排序答案：C25.題目：如果G是一個(gè)有28條邊的非連通無(wú)向圖，那么該圖頂點(diǎn)個(gè)數(shù)最少為多少？選項(xiàng)【A】10選項(xiàng)【B】9選項(xiàng)【C】7選項(xiàng)【D】8答案：B26.題目：WhichoneofthefollowingisthelowestupperboundofT(n)forthefollowingrecursionT(n)=2T(n/2)+nlogn?選項(xiàng)【A】O(nlogn)選項(xiàng)【B】O(n2)選項(xiàng)【C】O(n2logn)選項(xiàng)【D】O(nlog2n)答案：D答案說(shuō)明：1.Applythemastertheoremfortherecurrencerelation\(T(n)=2T(n/2)+n\logn\).-Themastertheoremstatesthatforarecurrencerelationoftheform\(T(n)=aT(n/b)+f(n)\),where\(a\geq1\),\(b>1\),and\(f(n)\)isanasymptoticallynon-negativefunction.-Here,\(a=2\),\(b=2\),and\(f(n)=n\logn\).-Calculate\(n^{\log_ba}=n^{\log_22}=n\).-Now,compare\(f(n)\)with\(n^{\log_ba}\).-Weneedtochecktherelationshipbetween\(f(n)=n\logn\)and\(n^{\log_ba}=n\).-Weknowthat\(\lim_{n\rightarrow\infty}\frac{n\logn}{n}=\lim_{n\rightarrow\infty}\logn=\infty\).So,\(f(n)=\Omega(n^{\log_ba+\epsilon})\)forsome\(\epsilon>0\).-Accordingtothemastertheorem,when\(f(n)=\Omega(n^{\log_ba+\epsilon})\)forsome\(\epsilon>0\),then\(T(n)=\Theta(f(n))\).-Since\(f(n)=n\logn\),thecomplexityof\(T(n)\)is\(\Theta(n\logn)\).-Amongthegivenoptions,thelowestupperboundgreaterthan\(T(n)\)is\(O(n\log^2n)\).SotheanswerisB.27.題目：設(shè)T是非空二叉樹(shù)，若T的先序遍歷和后序遍歷序列相同，則T的形態(tài)是選項(xiàng)【A】只有一個(gè)根結(jié)點(diǎn)選項(xiàng)【B】所有結(jié)點(diǎn)只有左孩子選項(xiàng)【C】沒(méi)有度為1的結(jié)點(diǎn)選項(xiàng)【D】所有結(jié)點(diǎn)只有右孩子答案：A答案說(shuō)明：先序遍歷順序是根左右，后序遍歷順序是左右根。若先序遍歷和后序遍歷序列相同，對(duì)于非空二叉樹(shù)，只有當(dāng)二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)時(shí)才會(huì)出現(xiàn)這種情況，因?yàn)橐粋€(gè)根結(jié)點(diǎn)的先序遍歷和后序遍歷都是它自身。而對(duì)于有多個(gè)結(jié)點(diǎn)的二叉樹(shù)，左右子樹(shù)的存在會(huì)導(dǎo)致先序遍歷和后序遍歷序列不同。選項(xiàng)B沒(méi)有度為1的結(jié)點(diǎn)，與先序遍歷和后序遍歷序列相同沒(méi)有直接關(guān)系；選項(xiàng)C所有結(jié)點(diǎn)只有左孩子，先序遍歷是根左右，后序遍歷是左右根，序列不同；選項(xiàng)D所有結(jié)點(diǎn)只有右孩子，同樣先序遍歷和后序遍歷序列也不同。28.題目：程序P1和P2時(shí)間復(fù)雜度的遞推公式：P1:T(1)=1,T(N)=T(N/2)+1;P2:T(1)=1,T(N)=2T(N/2)+1;則下列關(guān)于兩程序時(shí)間復(fù)雜度的結(jié)論中最準(zhǔn)確的是：選項(xiàng)【A】均為O(N)選項(xiàng)【B】P1是O(logN)，P2是O(N)選項(xiàng)【C】均為O(logN)選項(xiàng)【D】P1是O(logN)，P2是O(NlogN)答案：B答案說(shuō)明：對(duì)于程序P1：設(shè)\(N=2^k\)，則\(T(2^k)=T(2^{k-1})+1\)。依次類(lèi)推可得\(T(2^k)=k+T(1)\)，因?yàn)閈(k=\log_2N\)，所以\(T(N)=\log_2N+1\)，時(shí)間復(fù)雜度為\(O(\logN)\)。對(duì)于程序P2：設(shè)\(N=2^k\)，則\(T(2^k)=2T(2^{k-1})+1\)。通過(guò)迭代可得\(T(2^k)=2^k-1+T(1)\)，即\(T(N)=N-1\)，時(shí)間復(fù)雜度為\(O(N)\)。29.題目：在有n（>1）個(gè)元素的最大堆（大根堆）中，最小元的數(shù)組下標(biāo)可以是：選項(xiàng)【A】?n/2??1選項(xiàng)【B】?n/2?+2選項(xiàng)【C】1選項(xiàng)【D】?n/2?答案：B30.題目：深度為5的二叉樹(shù)至多有（）個(gè)節(jié)點(diǎn)選項(xiàng)【A】32選項(xiàng)【B】10選項(xiàng)【C】16選項(xiàng)【D】31答案：D答案說(shuō)明：深度為\(k\)的二叉樹(shù)，節(jié)點(diǎn)數(shù)最多時(shí)為滿二叉樹(shù)。對(duì)于深度為\(5\)的滿二叉樹(shù)，其節(jié)點(diǎn)數(shù)計(jì)算公式為\(2^k-1\)，即\(2^5-1=31\)，所以深度為\(5\)的二叉樹(shù)至多有\(zhòng)(31\)個(gè)節(jié)點(diǎn)。31.題目：給定一個(gè)堆棧的入棧序列為{1,2,?,n}，出棧序列為{p1,p2,?,pn}。如果p2=n，則存在多少種不同的出棧序列？選項(xiàng)【A】2選項(xiàng)【B】n選項(xiàng)【C】1選項(xiàng)【D】n?1答案：D答案說(shuō)明：當(dāng)\(p2=n\)時(shí)，意味著\(n\)是第二個(gè)出棧的元素。那么在\(n\)入棧之前，必須有一個(gè)元素先入棧，且這個(gè)元素在\(n\)入棧之后緊接著就出棧了，所以第一個(gè)出棧的元素有\(zhòng)(n-1\)種可能（可以是\(1\)到\(n-1\)中的任意一個(gè)）。而對(duì)于剩下的\(n-2\)個(gè)元素，它們的出棧順序是一個(gè)標(biāo)準(zhǔn)的\(n-2\)個(gè)元素的堆棧出棧序列問(wèn)題。根據(jù)卡特蘭數(shù)公式\(C(n)=\frac{1}{n+1}C_{2n}^n\)，這里\(n\)變?yōu)閈(n-2\)，其出棧序列的種類(lèi)數(shù)是固定的。所以總的出棧序列數(shù)為\(n-1\)種。因此，存在\(n-1\)種不同的出棧序列，答案選C。32.題目：下面的程序段違反了算法的（）原則。voidsam(){intn=2;while(n%2==0)n+=2;printf(“%d”,n);}選項(xiàng)【A】可行性選項(xiàng)【B】健壯性選項(xiàng)【C】確定性選項(xiàng)【D】有窮性答案：D答案說(shuō)明：有窮性是指算法必須能在執(zhí)行有限個(gè)步驟之后終止。在這個(gè)程序段中，當(dāng)n初始值為2時(shí)，n%2==0始終成立，會(huì)進(jìn)入無(wú)限循環(huán)，無(wú)法在有限步驟后結(jié)束，違反了有窮性原則。確定性是指算法的每一步驟都有明確的定義?？尚行允侵杆惴ǖ拿恳徊襟E都可以通過(guò)有限的時(shí)間完成。健壯性是指算法對(duì)非法輸入的處理能力。該程序段主要問(wèn)題是無(wú)法終止，即違反有窮性原則。33.題目：若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)。則采用哪種存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間？選項(xiàng)【A】帶頭結(jié)點(diǎn)的雙循環(huán)鏈表選項(xiàng)【B】雙鏈表選項(xiàng)【C】單鏈表選項(xiàng)【D】單循環(huán)鏈表答案：A答案說(shuō)明：在帶頭結(jié)點(diǎn)的雙循環(huán)鏈表中，插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度均為O(1)。插入操作只需要修改幾個(gè)指針即可，刪除操作同樣如此。而單鏈表插入操作時(shí)間復(fù)雜度為O(1)，但刪除最后一個(gè)結(jié)點(diǎn)時(shí)需要遍歷到倒數(shù)第二個(gè)結(jié)點(diǎn)，時(shí)間復(fù)雜度為O(n)；雙鏈表插入操作時(shí)間復(fù)雜度為O(1)，刪除最后一個(gè)結(jié)點(diǎn)也需要遍歷找到倒數(shù)第二個(gè)結(jié)點(diǎn)，時(shí)間復(fù)雜度為O(n)；單循環(huán)鏈表插入操作時(shí)間復(fù)雜度為O(1)，刪除最后一個(gè)結(jié)點(diǎn)同樣需要遍歷找到倒數(shù)第二個(gè)結(jié)點(diǎn)，時(shí)間復(fù)雜度為O(n)。所以帶頭結(jié)點(diǎn)的雙循環(huán)鏈表最節(jié)省運(yùn)算時(shí)間。34.題目：在一個(gè)不帶頭結(jié)點(diǎn)的非空鏈?zhǔn)疥?duì)列中,假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針,則插入s所指的結(jié)點(diǎn)運(yùn)算是()。選項(xiàng)【A】s->next=s;r=s;選項(xiàng)【B】r->next=s;r=s;選項(xiàng)【C】s->next=f;f=s;選項(xiàng)【D】f->next=s;f=s;答案：B答案說(shuō)明：對(duì)于不帶頭結(jié)點(diǎn)的非空鏈?zhǔn)疥?duì)列，插入操作是在隊(duì)尾進(jìn)行。首先將新節(jié)點(diǎn)s的next指針指向當(dāng)前隊(duì)尾節(jié)點(diǎn)r的next，即r->next=s，然后將隊(duì)尾指針r指向新節(jié)點(diǎn)s，即r=s。選項(xiàng)A是在隊(duì)頭插入，不符合要求；選項(xiàng)C邏輯錯(cuò)誤；選項(xiàng)D也是在隊(duì)頭插入，不符合在隊(duì)尾插入的操作。35.題目：將兩個(gè)結(jié)點(diǎn)數(shù)都為N且都從小到大有序的單向鏈表合并成一個(gè)從小到大有序的單向鏈表，那么可能的最少比較次數(shù)是：選項(xiàng)【A】NlogN選項(xiàng)【B】1選項(xiàng)【C】N選項(xiàng)【D】2N答案：C答案說(shuō)明：為了使比較次數(shù)最少，我們可以采用遞歸的方式合并兩個(gè)有序鏈表。在合并過(guò)程中，我們從兩個(gè)鏈表的頭節(jié)點(diǎn)開(kāi)始比較，每次比較一個(gè)節(jié)點(diǎn)，直到其中一個(gè)鏈表為空。因?yàn)槊總€(gè)鏈表都有N個(gè)節(jié)點(diǎn)，所以最少的比較次數(shù)就是N次。具體過(guò)程如下：1.比較兩個(gè)鏈表的頭節(jié)點(diǎn)，將較小的節(jié)點(diǎn)作為合并后鏈表的頭節(jié)點(diǎn)。2.遞歸地合并剩余的節(jié)點(diǎn)。3.重復(fù)上述步驟，直到其中一個(gè)鏈表為空。4.將另一個(gè)鏈表的剩余節(jié)點(diǎn)直接連接到合并后鏈表的末尾。因此，最少比較次數(shù)是N次，答案選B。36.題目：一棵滿二叉樹(shù)中127個(gè)節(jié)點(diǎn)，其中葉子節(jié)點(diǎn)的個(gè)數(shù)是（）選項(xiàng)【A】65選項(xiàng)【B】64選項(xiàng)【C】63選項(xiàng)【D】不確定答案：B37.題目：采用多項(xiàng)式的非零項(xiàng)鏈?zhǔn)酱鎯?chǔ)表示法，如果兩個(gè)多項(xiàng)式的非零項(xiàng)分別為N1和N2個(gè)，最高項(xiàng)指數(shù)分別為M1和M2，則實(shí)現(xiàn)兩個(gè)多項(xiàng)式相乘的時(shí)間復(fù)雜度是：選項(xiàng)【A】O(N1×N2)選項(xiàng)【B】O(M1×M2)選項(xiàng)【C】O(M1+M2)選項(xiàng)【D】O(N1+N2)答案：A答案說(shuō)明：多項(xiàng)式相乘的時(shí)間復(fù)雜度主要取決于兩個(gè)多項(xiàng)式的項(xiàng)數(shù)。在非零項(xiàng)鏈?zhǔn)酱鎯?chǔ)表示法下，相乘時(shí)需要對(duì)第一個(gè)多項(xiàng)式的每一項(xiàng)與第二個(gè)多項(xiàng)式的每一項(xiàng)相乘。第一個(gè)多項(xiàng)式有N1個(gè)非零項(xiàng)，第二個(gè)多項(xiàng)式有N2個(gè)非零項(xiàng)，所以總共的乘法次數(shù)為N1×N2次，時(shí)間復(fù)雜度為O(N1×N2)。38.題目：數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理相對(duì)位置和邏輯相對(duì)位置相同并且是連續(xù)的，稱(chēng)之為（）。選項(xiàng)【A】邏輯結(jié)構(gòu)選項(xiàng)【B】鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)選項(xiàng)【C】以上都不對(duì)選項(xiàng)【D】順序存儲(chǔ)結(jié)構(gòu)答案：D答案說(shuō)明：順序存儲(chǔ)結(jié)構(gòu)是把數(shù)據(jù)元素存放在地址連續(xù)的存儲(chǔ)單元里，其數(shù)據(jù)間的邏輯關(guān)系和物理關(guān)系是一致的，并且數(shù)據(jù)元素在存儲(chǔ)器內(nèi)是連續(xù)存放的，符合題目描述。而邏輯結(jié)構(gòu)是數(shù)據(jù)元素之間的邏輯關(guān)系，與物理存儲(chǔ)位置無(wú)關(guān)；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中數(shù)據(jù)元素的存儲(chǔ)位置是任意的，不要求連續(xù)。39.題目：樹(shù)最適合于用來(lái)表示選項(xiàng)【A】元素之間具有分支層次關(guān)系的數(shù)據(jù)選項(xiàng)【B】有序數(shù)據(jù)元素選項(xiàng)【C】元素之間無(wú)聯(lián)系的數(shù)據(jù)選項(xiàng)【D】無(wú)序數(shù)據(jù)元素答案：A答案說(shuō)明：樹(shù)是一種非線性數(shù)據(jù)結(jié)構(gòu)，它的每個(gè)節(jié)點(diǎn)可以有多個(gè)子節(jié)點(diǎn)，這種結(jié)構(gòu)非常適合用來(lái)表示元素之間具有分支層次關(guān)系的數(shù)據(jù)。例如家族樹(shù)、文件目錄結(jié)構(gòu)等都是典型的具有分支層次關(guān)系的數(shù)據(jù)，用樹(shù)來(lái)表示非常直觀和方便。而有序數(shù)據(jù)元素可以用數(shù)組或鏈表等線性結(jié)構(gòu)來(lái)表示；無(wú)序數(shù)據(jù)元素同樣可以用合適的線性結(jié)構(gòu)表示；元素之間無(wú)聯(lián)系的數(shù)據(jù)不適合用樹(shù)來(lái)表示，樹(shù)強(qiáng)調(diào)元素之間的層次關(guān)系。40.題目：給定A[]={46,23,8,99,31,12,85}，調(diào)用非遞歸的歸并排序加表排序執(zhí)行第1趟后，表元素的結(jié)果是：選項(xiàng)【A】3,6,1,5,2,7,4選項(xiàng)【B】1,2,3,4,5,6,7選項(xiàng)【C】0,2,1,4,3,5,6選項(xiàng)【D】1,0,2,3,5,4,6答案：D41.題目：以下說(shuō)法正確的是（）。選項(xiàng)【A】數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項(xiàng)的集合選項(xiàng)【B】數(shù)據(jù)元素是數(shù)據(jù)的最小單位選項(xiàng)【C】數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位選項(xiàng)【D】一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)答案：D答案說(shuō)明：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位，數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合，邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系，一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)。42.題目：設(shè)一段文本中包含4個(gè)對(duì)象{a,b,c,d}，其出現(xiàn)次數(shù)相應(yīng)為{4,2,5,1}，則該段文本的哈夫曼編碼比采用等長(zhǎng)方式的編碼節(jié)省了多少位數(shù)？選項(xiàng)【A】5選項(xiàng)【B】0選項(xiàng)【C】4選項(xiàng)【D】2答案：D43.題目：若用大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前front和rear的值分別為0和4。當(dāng)從隊(duì)列中刪除兩個(gè)元素，再加入兩個(gè)元素后，front和rear的值分別為多少？選項(xiàng)【A】2和0選項(xiàng)【B】2和6選項(xiàng)【C】2和2選項(xiàng)【D】2和4答案：A44.題目：任何一棵二叉樹(shù)的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序選項(xiàng)【A】發(fā)生改變選項(xiàng)【B】以上都不對(duì)選項(xiàng)【C】不能確定選項(xiàng)【D】不發(fā)生改變答案：D答案說(shuō)明：在二叉樹(shù)的遍歷中，葉結(jié)點(diǎn)的相對(duì)次序是不變的。先序遍歷是根左右，中序遍歷是左根右，后序遍歷是左右根，只是根的訪問(wèn)順序不同，葉結(jié)點(diǎn)之間的相對(duì)順序始終保持一致。45.題目：具有N（N>0）個(gè)頂點(diǎn)的無(wú)向圖至多有多少個(gè)連通分量？選項(xiàng)【A】N選項(xiàng)【B】N?1選項(xiàng)【C】0選項(xiàng)【D】1答案：A46.題目：設(shè)棧S和隊(duì)列Q的初始狀態(tài)均為空，元素{1,2,3,4,5,6,7}依次進(jìn)入棧S。若每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q，且7個(gè)元素出隊(duì)的順序是{2,5,6,4,7,3,1}，則棧S的容量至少是：選項(xiàng)【A】3選項(xiàng)【B】4選項(xiàng)【C】2選項(xiàng)【D】1答案：B47.題目：對(duì)N個(gè)記錄進(jìn)行堆排序，需要的額外空間為：選項(xiàng)【A】O(1)選項(xiàng)【B】O(NlogN)選項(xiàng)【C】O(N)選項(xiàng)【D】O(logN)答案：A答案說(shuō)明：堆排序是一種原地排序算法，它在排序過(guò)程中只需要常數(shù)級(jí)別的額外空間，即O(1)。在堆排序過(guò)程中，通過(guò)不斷調(diào)整堆結(jié)構(gòu)來(lái)進(jìn)行排序，不需要額外開(kāi)辟與記錄數(shù)N相關(guān)的大量空間。所以對(duì)N個(gè)記錄進(jìn)行堆排序，需要的額外空間為O(1)，答案選A。48.題目：設(shè)散列表的地址區(qū)間為[0,16]，散列函數(shù)為H(Key)=Key%17。采用線性探測(cè)法處理沖突，并將關(guān)鍵字序列{26，25，72，38，8，18，59}依次存儲(chǔ)到散列表中。元素59存放在散列表中的地址是：選項(xiàng)【A】11選項(xiàng)【B】9選項(xiàng)【C】10選項(xiàng)【D】8答案：A49.題目：對(duì)N個(gè)不同的數(shù)據(jù)采用冒泡算法進(jìn)行從大到小的排序，下面哪種情況下肯定交換元素次數(shù)最多？選項(xiàng)【A】元素?zé)o序選項(xiàng)【B】從小到大排好的選項(xiàng)【C】元素基本有序選項(xiàng)【D】從大到小排好的答案：B50.題目：Forthefollowingpieceofcodefor(i=0;i<n;i++)for(j=i;j>0;j/=2)printf(“%d\n”,j);thetimecomplexityis:選項(xiàng)【A】O(NlogN)選項(xiàng)【B】O(N2)選項(xiàng)【C】O(N×i)選項(xiàng)【D】O(N)答案：A51.題目：若AVL樹(shù)的深度是6（空樹(shù)的深度定義為-1），則該樹(shù)的最少結(jié)點(diǎn)數(shù)是：選項(xiàng)【A】33選項(xiàng)【B】13選項(xiàng)【C】20選項(xiàng)【D】17答案：A52.題目：在單鏈表中，若p所指的結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行選項(xiàng)【A】s->next=p->next;p=s;選項(xiàng)【B】s->next=p->next;p->next=s;選項(xiàng)【C】s->next=p;p->next=s;選項(xiàng)【D】p->next=s;s->next=p;答案：B53.題目：AVL樹(shù)是一種平衡的二叉搜索樹(shù)，樹(shù)中任一結(jié)點(diǎn)具有下列哪一特性：選項(xiàng)【A】左、右子樹(shù)高度差的絕對(duì)值不超過(guò)1選項(xiàng)【B】左、右子樹(shù)的高度均相同選項(xiàng)【C】左子樹(shù)的高度均小于右子樹(shù)的高度選項(xiàng)【D】左子樹(shù)的高度均大于右子樹(shù)的高度答案：A答案說(shuō)明：AVL樹(shù)的定義是：樹(shù)中任一結(jié)點(diǎn)的左、右子樹(shù)高度差的絕對(duì)值不超過(guò)1，并且左、右子樹(shù)都是一棵平衡二叉樹(shù)。選項(xiàng)A，左右子樹(shù)高度均相同不是AVL樹(shù)的特性；選項(xiàng)C左子樹(shù)高度均大于右子樹(shù)高度以及選項(xiàng)D左子樹(shù)高度均小于右子樹(shù)高度都不符合AVL樹(shù)平衡的要求。54.題目：在快速排序的一趟劃分過(guò)程中，當(dāng)遇到與基準(zhǔn)數(shù)相等的元素時(shí)，如果左指針停止移動(dòng)，而右指針在同樣情況下卻不停止移動(dòng)，那么當(dāng)所有元素都相等時(shí)，算法的時(shí)間復(fù)雜度是多少？選項(xiàng)【A】O(N)選項(xiàng)【B】O(N2)選項(xiàng)【C】O(NlogN)選項(xiàng)【D】O(logN)答案：B答案說(shuō)明：當(dāng)所有元素都相等時(shí)，在快速排序的一趟劃分過(guò)程中，由于左指針停止移動(dòng)，右指針會(huì)一直移動(dòng)到數(shù)組末尾，每次劃分只能將數(shù)組分成兩部分，一部分為空，另一部分為整個(gè)數(shù)組，這樣就相當(dāng)于對(duì)一個(gè)有序數(shù)組進(jìn)行排序，其時(shí)間復(fù)雜度會(huì)退化到O(N^2)。55.題目：度量結(jié)果集相關(guān)性時(shí)，如果準(zhǔn)確率很高而召回率很低，則說(shuō)明：選項(xiàng)【A】大部分相關(guān)文件被檢索到，但很多不相關(guān)的文件也在檢索結(jié)果里選項(xiàng)【B】大部分相關(guān)文件被檢索到，但基準(zhǔn)數(shù)據(jù)集不夠大選項(xiàng)【C】大部分檢索出的文件都是相關(guān)的，但基準(zhǔn)數(shù)據(jù)集不夠大選項(xiàng)【D】大部分檢索出的文件都是相關(guān)的，但還有很多相關(guān)文件沒(méi)有被檢索出來(lái)答案：D答案說(shuō)明：準(zhǔn)確率很高說(shuō)明大部分檢索出的文件都是相關(guān)的，召回率很低說(shuō)明還有很多相關(guān)文件沒(méi)有被檢索出來(lái)。56.題目：在下述結(jié)論中，正確的是：①只有一個(gè)結(jié)點(diǎn)的二叉樹(shù)的度為0;②二叉樹(shù)的度為2；③二叉樹(shù)的左右子樹(shù)可任意交換；④深度為K的完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹(shù)。選項(xiàng)【A】②④選項(xiàng)【B】①④選項(xiàng)【C】②③④選項(xiàng)【D】①②③答案：B答案說(shuō)明：①只有一個(gè)結(jié)點(diǎn)的二叉樹(shù)的度為0，正確；②二叉樹(shù)的度最大為2，不是一定為2，錯(cuò)誤；③二叉樹(shù)的左右子樹(shù)有順序之分，不能任意交換，錯(cuò)誤；④深度為K的完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹(shù)，正確。所以①④正確，答案選A。57.題目：設(shè)主串T=abaabaabcabaabc，模式串S=abaabc，采用KMP算法進(jìn)行模式匹配，到匹配成功時(shí)為止，在匹配過(guò)程中進(jìn)行的單個(gè)字符間的比較次數(shù)是：選項(xiàng)【A】12選項(xiàng)【B】10選項(xiàng)【C】15選項(xiàng)【D】9答案：B58.題目：二叉樹(shù)中第5層（根的層號(hào)為1）上的結(jié)點(diǎn)個(gè)數(shù)最多為：選項(xiàng)【A】8選項(xiàng)【B】15選項(xiàng)【C】32選