二級Visual FoxPro-公共基礎(chǔ)知識-第1章數(shù)據(jù)結(jié)構(gòu)與算法

二級VisualFoxPro-公共基礎(chǔ)知識-第1章數(shù)據(jù)結(jié)構(gòu)與算法[單選題]1.下列敘述中正確的是()。A.所謂算法就是計算方法B.程序可以作為算法的一種描述方法C.算法設(shè)計只需考慮得到計算結(jié)果D.算（江南博哥）法設(shè)計可以忽略算法的運算時間正確答案：B參考解析：A項錯誤，算法并不等同于計算方法，是指對解題方案的準(zhǔn)確而完整的描述；C項錯誤，算法設(shè)計需要考慮可行性、確定性、有窮性與足夠的情報；D項錯誤，算法設(shè)計有窮性要求操作步驟有限且必須在有限時間內(nèi)完成，耗費太長時間得到的正確結(jié)果是沒有意義的。B項正確，程序可以作為算法的一種描述方法,算法在實現(xiàn)時需要用具體的程序設(shè)計語言描述。答案選擇B選項。[單選題]2.算法的有窮性是指()。A.算法程序的運行時間是有限的B.算法程序所處理的數(shù)據(jù)量是有限的C.算法程序的長度是有限的D.算法只能被有限的用戶使用正確答案：A參考解析：算法設(shè)計有窮性要求操作步驟有限且必須在有限時間內(nèi)完成，耗費太長時間得到的正確結(jié)果是沒有意義的。答案選擇A選項。[單選題]3.算法應(yīng)當(dāng)具有的特性不包括()。A.可行性B.有窮性C.確定性D.美觀性正確答案：D參考解析：一個算法應(yīng)該具有以下五個重要的特征：有窮性，確定性，輸入（零個或多個），輸出（至少一個）以及可行性，不包括美觀性。答案選擇D選項。[單選題]4.算法的時間復(fù)雜度是指()。A.算法的執(zhí)行時間B.算法所處理的數(shù)據(jù)量C.算法程序中的語句或指令條數(shù)D.算法在執(zhí)行過程中所需要的基本運算次數(shù)正確答案：D參考解析：算法的復(fù)雜度主要包括時間復(fù)雜度和空間復(fù)雜度。算法的時間復(fù)雜度，是指執(zhí)行算法所需要的計算工作量，即基本運算次數(shù)；算法的空間復(fù)雜度，一般是指執(zhí)行這個算法所需要的內(nèi)存空間。答案選擇D選項。[單選題]5.算法時間復(fù)雜度的度量方法是()。A.算法程序的長度B.執(zhí)行算法所需要的基本運算次數(shù)C.執(zhí)行算法所需要的所有運算次數(shù)D.執(zhí)行算法所需要的時間正確答案：B參考解析：算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量，即算法所執(zhí)行的基本運算次數(shù)來度量的。答案選擇B選項。[單選題]6.算法的空間復(fù)雜度是指()。A.算法程序的長度B.算法程序中的指令條數(shù)C.算法程序所占的存儲空間D.算法執(zhí)行過程中所需要的存儲空間正確答案：D參考解析：算法的空間復(fù)雜度是指算法在執(zhí)行過程中所需要的計算機存儲空間。包括算法程序所占空間，輸入的初始數(shù)據(jù)所占空間和執(zhí)行過程中所需要的額外空間。答案選擇D選項。[單選題]7.算法的空間復(fù)雜度是指()。A.算法在執(zhí)行過程中所需要的計算機存儲空間B.算法所處理的數(shù)據(jù)量C.算法程序中的語句或指令條數(shù)D.算法在執(zhí)行過程中所需要的臨時工作單元數(shù)正確答案：A參考解析：算法的空間復(fù)雜度是指算法在執(zhí)行過程中所需要的計算機存儲空間。包括算法程序所占空間，輸入的初始數(shù)據(jù)所占空間和執(zhí)行過程中所需要的額外空間。答案選擇A選項。[單選題]8.算法空間復(fù)雜度的度量方法是()。A.算法程序的長度B.算法所處理的數(shù)據(jù)量C.執(zhí)行算法所需要的工作單元D.執(zhí)行算法所需要的存儲空間正確答案：D參考解析：算法的空間復(fù)雜度是指算法在執(zhí)行過程中所需要的計算機存儲空間。包括算法程序所占空間，輸入的初始數(shù)據(jù)所占空間和執(zhí)行過程中所需要的額外空間。答案選擇D選項。[單選題]9.下列敘述中錯誤的是()。A.算法的時間復(fù)雜度與算法所處理數(shù)據(jù)的存儲結(jié)構(gòu)有直接關(guān)系B.算法的空間復(fù)雜度與算法所處理數(shù)據(jù)的存儲結(jié)構(gòu)有直接關(guān)系C.算法的時間復(fù)雜度與空間復(fù)雜度有直接關(guān)系D.算法的時間復(fù)雜度與算法程序執(zhí)行的具體時間是不一致的正確答案：C參考解析：算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量。數(shù)據(jù)的存儲結(jié)構(gòu)直接決定數(shù)據(jù)輸入，因此會影響算法所執(zhí)行的基本運算次數(shù)，A項正確；算法的空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間，其中包括輸入數(shù)據(jù)所占的存儲空間，B項正確；算法的時間復(fù)雜度與空間復(fù)雜度沒有直接關(guān)系，C項錯誤；算法程序執(zhí)行的具體時間受到所使用的計算機、程序設(shè)計語言以及算法實現(xiàn)過程中的許多細(xì)節(jié)影響，而算法的時間復(fù)雜度與這些因素?zé)o關(guān)，所以算法的時間復(fù)雜度與算法程序執(zhí)行的具體時間是不一致的，D項正確。答案選擇C選項。[單選題]10.下列關(guān)于算法復(fù)雜度敘述正確的是()。A.最壞情況下的時間復(fù)雜度一定高于平均情況的時間復(fù)雜度B.時間復(fù)雜度與所用的計算工具無關(guān)C.對同一個問題，采用不同的算法，則它們的時間復(fù)雜度是相同的D.時間復(fù)雜度與采用的算法描述語言有關(guān)正確答案：B參考解析：A項錯誤，最壞情況下的時間復(fù)雜度有可能與平均情況的時間復(fù)雜度相同；C項錯誤，對同一個問題，不同的算法時間復(fù)雜度有時可能差距很大；D項錯誤，算法的時間復(fù)雜度與實現(xiàn)算法的描述語言、運行環(huán)境無關(guān)，算法的時間復(fù)雜度是對算法執(zhí)行時所花時間的度量。答案選擇B選項。[單選題]11.下面關(guān)于算法的敘述中，正確的是()。A.算法的執(zhí)行效率與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)B.算法的有窮性是指算法必須能在執(zhí)行有限個步驟之后終止C.算法的空間復(fù)雜度是指算法程序中指令（或語句）的條數(shù)D.算法所執(zhí)行的基本運算次數(shù)與問題的規(guī)模無關(guān)正確答案：B參考解析：A項錯誤，不同的數(shù)據(jù)存儲結(jié)構(gòu)有不同的數(shù)據(jù)讀取效率，會影響到算法的執(zhí)行；C項錯誤，算法的空間復(fù)雜度是對這個算法所需要的內(nèi)存空間的量度，包括：①算法程序所占的空間；②輸入的初始數(shù)據(jù)所占的存儲空間；③算法執(zhí)行中所需要的額外空間；D項錯誤，算法所執(zhí)行的基本運算次數(shù)與問題的規(guī)模有關(guān)。答案選擇B選項。[單選題]12.下列關(guān)于算法的描述中錯誤的是()。A.算法強調(diào)動態(tài)的執(zhí)行過程，不同于靜態(tài)的計算公式B.算法必須能在有限個步驟之后終止C.算法設(shè)計必須考慮算法的復(fù)雜度D.算法的優(yōu)劣取決于運行算法程序的環(huán)境正確答案：D參考解析：算法是指對解題方案的準(zhǔn)確而完整的描述。A項正確，算法強調(diào)實現(xiàn)，不同于數(shù)學(xué)上的計算方法；B項正確，算法的有窮性是指，算法中的操作步驟為有限個，且每個步驟都能在有限時間內(nèi)完成；C項正確，算法設(shè)計必須考慮執(zhí)行算法所需要的資源，即時間復(fù)雜度與空間復(fù)雜度；D項錯誤，算法的優(yōu)劣取決于算法復(fù)雜度，只有當(dāng)算法被編程實現(xiàn)運行時才會受到運行環(huán)境影響。答案選擇D選項。[單選題]13.線性表常采用的兩種存儲結(jié)構(gòu)是()。A.散列方法和索引方式B.鏈表存儲結(jié)構(gòu)和數(shù)組C.順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)D.線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)正確答案：C參考解析：線性表常用的存儲結(jié)構(gòu)為：①順序存儲結(jié)構(gòu)，物理上連續(xù)存儲，空間位置隱含邏輯位置；②鏈?zhǔn)酱鎯Y(jié)構(gòu)，各元素物理存儲上不連續(xù)，通過指針相連。答案選擇C選項。[單選題]14.下列數(shù)據(jù)結(jié)構(gòu)中，屬于非線性結(jié)構(gòu)的是()。A.雙向鏈表B.循環(huán)鏈表C.二叉鏈表D.循環(huán)隊列正確答案：C參考解析：線性結(jié)構(gòu)要滿足兩個條件：①有且僅有一個根結(jié)點；②每個結(jié)點最多有一個前驅(qū)，也最多有一個后繼。線性表、棧、隊列都是線性結(jié)構(gòu)，循環(huán)鏈表和雙向鏈表是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，屬于線性結(jié)構(gòu)，只是存儲結(jié)構(gòu)不連續(xù)；循環(huán)隊列是一個頭結(jié)點和尾結(jié)點互為前驅(qū)結(jié)點和后繼結(jié)點的特殊的隊列，屬于線性結(jié)構(gòu)；二叉鏈表是二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)，因為二叉樹有些結(jié)點有兩個后繼結(jié)點，不符合線性結(jié)構(gòu)的定義，所以二叉鏈表是非線性結(jié)構(gòu)。答案選擇C選項。[單選題]15.以下數(shù)據(jù)結(jié)構(gòu)中，屬于非線性數(shù)據(jù)結(jié)構(gòu)的是()。A.棧B.線性表C.隊列D.二叉樹正確答案：D參考解析：線性結(jié)構(gòu)必須滿足下列兩個條件：①有且只有一個根結(jié)點；②每一個結(jié)點最多有一個前件，也最多有一個后件。如果一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)。二叉樹中的結(jié)點后繼不惟一，屬于非線性結(jié)構(gòu)，棧和隊列都是操作受限的線性表，是線性結(jié)構(gòu)。答案選擇D選項。[單選題]16.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的()。A.存儲結(jié)構(gòu)B.物理結(jié)構(gòu)C.邏輯結(jié)構(gòu)D.線性結(jié)構(gòu)正確答案：C參考解析：數(shù)據(jù)結(jié)構(gòu)研究數(shù)據(jù)邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)以及數(shù)據(jù)運算，其中邏輯結(jié)構(gòu)反映的是數(shù)據(jù)元素之間的邏輯關(guān)系，與使用的計算機無關(guān)。答案選擇C選項。[單選題]17.數(shù)據(jù)結(jié)構(gòu)主要研究的是數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的運算和()。A.數(shù)據(jù)的方法B.數(shù)據(jù)的存儲結(jié)構(gòu)C.數(shù)據(jù)的對象D.數(shù)據(jù)的邏輯存儲正確答案：B參考解析：數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，主要研究數(shù)據(jù)元素及其之間的相互關(guān)系和數(shù)據(jù)運算，包括：①數(shù)據(jù)的邏輯結(jié)構(gòu)；②數(shù)據(jù)的存儲結(jié)構(gòu)；③數(shù)據(jù)的運算。其中邏輯結(jié)構(gòu)反映的是數(shù)據(jù)元素之間的邏輯關(guān)系，與使用的計算機無關(guān)。答案選擇B選項。[單選題]18.下列描述中，正確的是()。A.線性鏈表是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)B.棧與隊列是非線性結(jié)構(gòu)C.雙向鏈表是非線性結(jié)構(gòu)D.只有根結(jié)點的二叉樹是線性結(jié)構(gòu)正確答案：A參考解析：線性結(jié)構(gòu)是指如果一個非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個條件：①有且只有一個根結(jié)點；②每個結(jié)點最多有一個前件，也最多有一個后件。B項錯誤，棧和隊列都是操作受限的線性表；C項錯誤，雙向鏈表是線性結(jié)構(gòu)；D項錯誤，二叉樹中的結(jié)點后繼不唯一，屬于非線性結(jié)構(gòu)。答案選擇A選項。[單選題]19.下列關(guān)于線性表的敘述中，不正確的是()。A.線性表可以是空表B.線性表是一種線性結(jié)構(gòu)C.線性表的所有結(jié)點有且僅有一個前件和后件D.線性表是由n個元素組成的一個有限序列正確答案：C參考解析：線性表是由n個元素組成的一種線性結(jié)構(gòu)，當(dāng)n=0時線性表為空表。C項錯誤，線性表中，第一個結(jié)點沒有前件，最后一個結(jié)點沒有后件。答案選擇C選項。[單選題]20.以下描述中，不是線性表順序存儲結(jié)構(gòu)特征的是()。A.可隨機訪問B.需要連續(xù)的存儲空間C.不便于插入和刪除D.邏輯相鄰的數(shù)據(jù)物理位置上不相鄰正確答案：D參考解析：在計算機中用一組地址連續(xù)的存儲單元依次存儲線性表的各個數(shù)據(jù)元素稱為順序存儲，其中邏輯上相鄰的元素在物理位置上也相鄰。順序存儲結(jié)構(gòu)中可以隨機訪問元素，但插入和刪除需要移動大量數(shù)據(jù)，耗費資源。答案選擇D選項。[單選題]21.下列敘述中正確的是()。A.所有數(shù)據(jù)結(jié)構(gòu)必須有根結(jié)點B.所有數(shù)據(jù)結(jié)構(gòu)必須有終端結(jié)點（即葉子結(jié)點）C.只有一個根結(jié)點，且只有一個葉子結(jié)點的數(shù)據(jù)結(jié)構(gòu)一定是線性結(jié)構(gòu)D.沒有根結(jié)點或沒有葉子結(jié)點的數(shù)據(jù)結(jié)構(gòu)一定是非線性結(jié)構(gòu)正確答案：D參考解析：D項正確，線性結(jié)構(gòu)的特點是：①集合中必存在“第一個元素”且惟一；②集合中必存在“最后一個元素”且惟一；③除最后一個元素外，其他數(shù)據(jù)元素均有惟一的“后繼”；④除第一個元素外，其他數(shù)據(jù)元素均有惟一的“前驅(qū)”。所以沒有根結(jié)點或沒有葉子結(jié)點的數(shù)據(jù)結(jié)構(gòu)一定是非線性結(jié)構(gòu)。AB兩項錯誤，不是所有數(shù)據(jù)結(jié)構(gòu)都必須有根結(jié)點和葉子結(jié)點；C項錯誤，數(shù)據(jù)結(jié)構(gòu)中若有中間結(jié)點不滿足只有一個前件或者后件的條件，就不是線性結(jié)構(gòu)。答案選擇D選項。[單選題]22.設(shè)數(shù)據(jù)元素的集合D={1,2,3,4,5}，則滿足下列關(guān)系R的數(shù)據(jù)結(jié)構(gòu)中為線性結(jié)構(gòu)的是()。A.R={(1,2),(3,4),(5,1),(1,2)}B.R={(1,3),(4,1),(3,2),(5,4)}C.R={(1,2),(2,3),(4,5),(2,3)}D.R={(1,3),(2,4),(3,5),(1,2)}正確答案：B參考解析：一個非空的數(shù)據(jù)結(jié)構(gòu)如果滿足以下兩個條件：有且只有一個根結(jié)點；每一個結(jié)點最多有一個前件，也最多有一個后件，稱為線性結(jié)構(gòu)。不同時滿足以上兩個條件的數(shù)據(jù)結(jié)構(gòu)就稱為非線性結(jié)構(gòu)。A選項，5是1的前件，1是2的前件，3是4的前件，則關(guān)系R中含有兩個結(jié)構(gòu)，即34和512，其中3和5均為根結(jié)點，故A項錯誤。B選項根結(jié)點為5，排列順序為54132，B選項正確。C選項有兩個根結(jié)點1和4，故錯誤。D選項有兩個根結(jié)點1和2，故錯誤。答案選擇B選項。[單選題]23.設(shè)數(shù)據(jù)集合為D={1,3,5,7,9}，D上的關(guān)系為R，下列數(shù)據(jù)結(jié)構(gòu)B=(D,R)中為非線性結(jié)構(gòu)的是()。A.R={(5,1),(7,9),(1,7),(9,3)}B.R={(9,7),(1,3),(7,1),(3,5)}C.R={(1,9),(9,7),(7,5),(5,3)}D.R={(1,3),(3,5),(5,9),(7,3)}正確答案：D參考解析：A項中，5為根結(jié)點，線性表為51793。B項中，9為根結(jié)點，線性表為97135。C項中，1為根結(jié)點，線性表為19753。D項中，結(jié)點1與7都是根結(jié)點，屬于非線性結(jié)構(gòu)，D項正確。答案選擇D選項。[單選題]24.在線性表的順序存儲結(jié)構(gòu)中，其存儲空間連續(xù)，各個元素所占的字節(jié)數(shù)()。A.相同，元素的存儲順序與邏輯順序一致B.相同，但其元素的存儲順序可以與邏輯順序不一致C.不同，但元素的存儲順序與邏輯順序一致D.不同，且其元素的存儲順序可以與邏輯順序不一致正確答案：A參考解析：在順序表中，每個元素占有相同的存儲單元。順序表具有特征：①線性表中所有元素所占的存儲空間是連續(xù)的；②線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。答案選擇A選項。[單選題]25.下列與棧結(jié)構(gòu)有關(guān)聯(lián)的是()。A.數(shù)組的定義域使用B.操作系統(tǒng)的進程調(diào)度C.函數(shù)的遞歸調(diào)用D.選擇結(jié)構(gòu)的執(zhí)行正確答案：C參考解析：函數(shù)的遞歸調(diào)用是指函數(shù)調(diào)用函數(shù)本身，直到滿足特定條件時終止，然后從最后被遞歸調(diào)用處返回。遞歸函數(shù)是通過棧來實現(xiàn)的，所以調(diào)用原則和棧的實現(xiàn)相一致。所以遞歸函數(shù)是通過棧來實現(xiàn)的。答案選擇C選項。[單選題]26.下列關(guān)于棧的敘述中，正確的是()。A.棧底元素一定是最后入棧的元素B.棧頂元素一定是最先入棧的元素C.棧操作遵循先進后出的原則D.以上三種說法都不對正確答案：C參考解析：棧是一種“先進后出”的線性表，最先入棧的元素最后出棧，最后入棧的元素最先出棧，所以棧底元素一定是最先入棧最后出棧的元素，而棧頂元素一定是最后入棧最先出棧的元素。答案選擇C選項。[單選題]27.下列敘述中正確的是()。A.循環(huán)隊列是隊列的一種順序存儲結(jié)構(gòu)B.循環(huán)隊列是隊列的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)C.循環(huán)隊列是非線性結(jié)構(gòu)D.循環(huán)隊列是一種邏輯結(jié)構(gòu)正確答案：A參考解析：隊列是一種“先進先出”的特殊線性表。循環(huán)隊列是在順序存儲結(jié)構(gòu)中將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間，定義兩個游標(biāo)：指向隊頭的游標(biāo)（front）、指向隊尾的游標(biāo)（rear）。答案選擇A選項。[單選題]28.下列敘述中正確的是()。A.棧是一種先進先出的線性表B.隊列是一種后進先出的線性表C.棧和隊列都是非線性結(jié)構(gòu)D.以上三種說法都不對正確答案：D參考解析：A項錯誤，棧是一種“先進后出”的特殊線性表；B項錯誤，隊列則是一種“先進先出”的特殊線性表；C項錯誤，棧和隊列都是線性結(jié)構(gòu)。答案選擇D選項。[單選題]29.下列關(guān)于棧的敘述中正確的是()。A.棧頂元素最先能被刪除B.棧頂元素最后才能被刪除C.棧底元素永遠(yuǎn)不能被刪除D.以上三種說法都不對正確答案：A參考解析：棧是一種“先進后出”的線性表，最先入棧的元素最后出棧，最后入棧的元素最先出棧，所以棧底元素一定是最先入棧最后出棧的元素，而棧頂元素一定是最后入棧最先出棧的元素。答案選擇A選項。[單選題]30.下列關(guān)于棧敘述正確的是()。A.棧頂元素最先能被刪除B.棧頂元素最后才能被刪除C.棧底元素永遠(yuǎn)不能被刪除D.棧底元素最先能被刪除正確答案：A參考解析：棧是先進后出的數(shù)據(jù)結(jié)構(gòu)，因此棧頂元素最后入棧卻最先被刪除，棧底元素最先入棧卻最后被刪除。答案選擇A選項。[單選題]31.下列敘述中正確的是()。A.在棧中，棧中的元素隨棧底指針與棧頂指針的變化而動態(tài)變化B.在棧中，棧頂指針不變，棧中元素隨棧底指針的變化而動態(tài)變化C.在棧中，棧底指針不變，棧中元素隨棧頂指針的變化而動態(tài)變化D.上述三種說法都不對正確答案：C參考解析：棧中元素遵循“先進后出”的原則。入棧和出棧都是對棧頂指針操作，因此，棧底指針不變，棧中元素隨棧頂指針的變化而動態(tài)變化。答案選擇C選項。[單選題]32.下列敘述中正確的是()。A.在棧中，棧中元素隨棧底指針與棧頂指針的變化而動態(tài)變化B.在棧中，棧頂指針不變，棧中元素隨棧底指針的變化而動態(tài)變化C.在棧中，棧底指針不變，棧中元素隨棧頂指針的變化而動態(tài)變化D.在棧中，棧中元素不會隨棧底指針與棧頂指針的變化而動態(tài)變化正確答案：C參考解析：棧中元素遵循“先進后出”的原則。入棧和出棧都是對棧頂指針操作，因此，棧底指針不變，棧中元素隨棧頂指針的變化而動態(tài)變化。答案選擇C選項。[單選題]33.下列數(shù)據(jù)結(jié)構(gòu)中，能夠按照“先進后出”原則存取數(shù)據(jù)的是()。A.循環(huán)隊列B.棧C.隊列D.二叉樹正確答案：B參考解析：棧和隊列都是操作受限的線性表：棧只能在棧頂插入和刪除元素，按照“先進后出”的原則組織數(shù)據(jù)；隊列只能在隊頭刪除元素，在隊尾插入元素，按照“先進先出”的原則組織數(shù)據(jù)。B項，棧，按照“先進后出”的原則組織數(shù)據(jù)。A項，循環(huán)隊列是隊列的一種特殊形式，按照“先進先出”的原則組織數(shù)據(jù)；C項，隊列，按照“先進先出”的原則組織數(shù)據(jù)。D項，二叉樹屬于非線性結(jié)構(gòu)。答案選擇B選項。[單選題]34.對于循環(huán)隊列，下列敘述中正確的是()。A.隊頭指針是固定不變的B.隊頭指針一定大于隊尾指針C.隊頭指針一定小于隊尾指針D.隊頭指針可以大于隊尾指針，也可以小于隊尾指針正確答案：D參考解析：在循環(huán)隊列中，用隊尾指針（rear）指向隊列中的隊尾元素，用隊頭指針（front）指向隊頭元素的前一個位置。在循環(huán)隊列中，一般情況下rear>front，當(dāng)存儲空間的最后一個位置被使用，而新元素要入隊時，如果存儲空間的第一個位置空閑，便可將元素插入到第一個位置，此時存儲空間的第一個位置作為隊尾，便有front>rear。所以答案選擇D選項。[單選題]35.下列敘述中正確的是()。A.棧是“先進先出”的線性表B.隊列是“先進后出”的線性表C.循環(huán)隊列是非線性結(jié)構(gòu)D.有序線性表既可以采用順序存儲結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)正確答案：D參考解析：有序的線性表既可采用順序存儲結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。A項錯誤，棧是“先進后出”的線性表；B項錯誤，隊列是“先進先出”的線性表；C項錯誤，循環(huán)隊列是線性結(jié)構(gòu)的，有序的線性表既可采用順序存儲結(jié)構(gòu)，也可采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。答案選擇D選項。[單選題]36.支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是()。A.棧B.樹C.隊列D.二叉樹正確答案：A參考解析：在高級語言中，函數(shù)的調(diào)用是通過棧來實現(xiàn)的。在進行函數(shù)調(diào)用時，系統(tǒng)將所需的信息壓入棧中，如函數(shù)的局部變量、返回值等。每個函數(shù)的狀態(tài)是由函數(shù)中的局部變量、函數(shù)參數(shù)值、函數(shù)的返回值地址決定的，存儲這些信息的數(shù)據(jù)區(qū)域稱為活動記錄，或叫做棧幀，它是運行時系統(tǒng)棧上分配的空間。答案選擇A選項。[單選題]37.一個棧的初始狀態(tài)為空?，F(xiàn)將元素1、2、3、4、5、A、B、C、D、E依次入棧，然后再依次出棧，則元素出的順序是()。A.12345ABCDEB.EDCBA54321C.ABCDE12345D.54321EDCBA正確答案：B參考解析：棧是按照“先進后出”的原則組織數(shù)據(jù)的，入棧的順序為12345ABCDE，則依次出棧的順序應(yīng)為其逆序，即EDCBA54321。答案選擇B選項。[單選題]38.下列敘述中正確的是()。A.循環(huán)隊列有隊頭和隊尾兩個指針，因此，循環(huán)隊列是非線性結(jié)構(gòu)B.在循環(huán)隊列中，只需要隊頭指針就能反映隊列中元素的動態(tài)變化C.在循環(huán)隊列中，只需要隊尾指針就能反映隊列中元素的動態(tài)變化D.循環(huán)隊列中元素的個數(shù)由隊頭指針和隊尾指針共同決定正確答案：D參考解析：循環(huán)隊列是順序存儲的線性結(jié)構(gòu)，是隊列常采用的形式，故A項錯誤。循環(huán)隊列中的元素是動態(tài)變化的：每一次入隊，隊尾指針就進一；每一次出隊，隊頭指針就進一，所以隊頭指針和隊尾指針一起反映了隊列中元素的動態(tài)變化情況，BC兩項錯誤。從隊頭指針指向的后一個位置與隊尾指針指向的位置之間的元素即為隊列中所有的元素，答案選擇D選項。[單選題]39.下列關(guān)于棧的敘述正確的是()。A.棧按“先進先出”組織數(shù)據(jù)B.棧按“先進后出”組織數(shù)據(jù)C.只能在棧底插入數(shù)據(jù)D.不能刪除數(shù)據(jù)正確答案：B參考解析：棧是只允許在棧頂進行插入和刪除運算的線性表，按“先進后出”組織數(shù)據(jù)。答案選擇B選項。[單選題]40.棧和隊列的共同點是()。A.都是先進后出B.都是先進先出C.只允許在端點處插入和刪除元素D.沒有共同點正確答案：C參考解析：棧和隊列都是操作受限的線性表，只允許在端點處進行插入和刪除。二者的區(qū)別是：棧只允許在表的一端進行插入或刪除操作，是一種“后進先出”的線性表；而隊列只允許在表的一端進行插入操作，在另一端進行刪除操作，是一種“先進先出”的線性表。答案選擇C選項。[單選題]41.下列關(guān)于隊列的敘述中正確的是()。A.在隊列中只能插入數(shù)據(jù)B.在隊列中只能刪除數(shù)據(jù)C.隊列是先進先出的線性表D.隊列是先進后出的線性表正確答案：C參考解析：隊列是一種操作受限的線性表。它只允許在線性表的一端進行插入操作，另一端進行刪除操作。其中，允許插入的一端稱為隊尾（rear），允許刪除的一端稱為隊首（front）。隊列是按“先進先出”的原則組織數(shù)據(jù)的。答案選擇C選項。[單選題]42.下列關(guān)于棧和隊列的描述中，正確的是()。A.棧是先進先出B.隊列是先進后出C.隊列允許在隊尾刪除元素D.棧在棧頂刪除元素正確答案：D參考解析：線性表是由n個元素組成的一種線性結(jié)構(gòu)，棧和隊列都是操作受限的線性表：棧只能在棧頂插入和刪除元素，按照“先進后出”的原則組織數(shù)據(jù)；隊列是指允許在一端進行插入、而在另一端進行刪除的線性表，按照“先進先出”的原則組織數(shù)據(jù)。答案選擇D選項。[單選題]43.如果進棧序列為A，B，C，D，則可能的出棧序列是()。A.C，A，D，BB.B，D，C，AC.C，D，A，BD.D，B，C，A正確答案：B參考解析：棧按后進先出的原則組織數(shù)據(jù)。B項，當(dāng)棧的操作順序為“A進，B進，B出，C進，D進，D出，C出，A出”可以實現(xiàn)。A項，C首先出棧，棧中肯定有A和B，如果接下來A、B有元素要出棧，只能是B，故A選項錯誤；C項，C首先出棧，棧中肯定有A和B，D元素進棧，緊接著出棧，剩下的A、B有元素要出棧，只能是先B后A，故C選項錯誤；D項，D首先出棧，棧中肯定有A、B和C，如果接下來有元素要出棧，只能是C，故D選項錯誤。答案選擇B選項。[單選題]44.下列關(guān)于棧的描述中，正確的是()。A.在棧中只能插入元素B.在棧中只能刪除元素C.只能在一端插入或刪除元素D.只能在一端插入元素，而在另一端刪除元素正確答案：C參考解析：棧是一種操作受限的線性表：棧只能在棧頂插入和刪除元素。答案選擇C選項。[單選題]45.下列隊列的描述中，正確的是()。A.隊列屬于非線性表B.隊列在隊尾刪除數(shù)據(jù)C.隊列按“先進后出”進行數(shù)據(jù)操作D.隊列按“先進先出”進行數(shù)據(jù)操作正確答案：D參考解析：隊列是操作受限的線性表：隊列只能在隊頭刪除元素，在隊尾插入元素，按照“先進先出”的原則組織數(shù)據(jù)。答案選擇D選項。[單選題]46.設(shè)棧的順序存儲空間為S（0：49），棧底指針bottom=49，棧頂指針top=30（指向棧頂元素）。則棧中的元素個數(shù)為()。A.30B.29C.20D.19正確答案：C參考解析：棧是一種特殊的線性表，它所有的插入與刪除操作都限定在表的同一端進行。入棧運算即在棧頂位置插入一個新元素，退棧運算即取出棧頂元素賦予指定變量。在內(nèi)存中，棧的增大方向是地址遞減，元素依次存儲在單元30：49中，個數(shù)為：49-30+1=20個。答案選擇C選項。[單選題]47.設(shè)棧的順序存儲空間為S（1：m），初始狀態(tài)為top=m+1。現(xiàn)經(jīng)過一系列入棧與退棧運算后，top=20，則當(dāng)前棧中的元素個數(shù)為()。A.30B.20C.m-19D.m-20正確答案：C參考解析：初始狀態(tài)為棧頂指針指向高地址，top＝m+1，每次入棧top-1。那么當(dāng)?shù)趚個元素入棧時，top=m+1-x=20，解得x=m+1-20=m-19。答案選擇C選項。[單選題]48.設(shè)循環(huán)隊列的存儲空間為Q（1：35），初始狀態(tài)為front=rear=35。現(xiàn)經(jīng)過一系列入隊與退隊運算后，front=15，rear=15，則循環(huán)隊列的元素個數(shù)為()。A.15B.16C.20D.0或35正確答案：D參考解析：在循環(huán)隊列中，front為隊首指針，指向隊首元素的前一個位置；rear為隊尾指針，指向隊尾元素。front=rear=15時，①循環(huán)隊列可能為空，隊首和隊尾指針都指向空元素，此時循環(huán)隊列的元素個數(shù)為0；②循環(huán)隊列可能為滿，此時循環(huán)隊列的元素個數(shù)為35。答案選擇D選項。[單選題]49.設(shè)循環(huán)隊列為Q（1：m），初始狀態(tài)為front=rear=m?，F(xiàn)經(jīng)過一系列的入隊與退隊運算后，front=rear=1，則該循環(huán)隊列中的元素個數(shù)為()。A.1B.2C.m-1D.0或m正確答案：D參考解析：在循環(huán)隊列中，front為隊首指針，指向隊首元素的前一個位置；rear為隊尾指針，指向隊尾元素。front=rear=1時，①循環(huán)隊列可能為空，隊首和隊尾指針都指向空元素，此時循環(huán)隊列的元素個數(shù)為0；②循環(huán)隊列可能為滿，此時循環(huán)隊列的元素個數(shù)為m。答案選擇D選項。[單選題]50.設(shè)循環(huán)隊列為Q（1：m），其初始狀態(tài)為front=rear=m。經(jīng)過一系列入隊與退隊運算后，front=15，rear=20?，F(xiàn)要在該循環(huán)隊列中尋找最大值的元素，最壞情況下需要比較的次數(shù)為()。A.4B.6C.m-5D.m-6正確答案：A參考解析：循環(huán)隊列順序存儲結(jié)構(gòu)隊列。循環(huán)隊列中，rear指向隊列中的隊尾元素，front指向隊頭元素的前一個位置，本題中，在front指向的后一個位置和rear指向的位置之間，所有的元素均為隊列中的元素。隊列初始狀態(tài)為front=rear=m，當(dāng)front=15，rear=20時，隊列中共有20-15（尾指針-頭指針）=5個元素，尋找其中最大值的最壞情況是逐項比較，所以需比較4次。答案選擇A選項。[單選題]51.設(shè)循環(huán)隊列為Q（1：m），其初始狀態(tài)為front=rear=m。經(jīng)過一系列入隊與退隊運算后，front=20，rear=15，要在該循環(huán)隊列中尋找最小值的元素，最壞情況下需要比較的次數(shù)為()。A.5B.6C.m-5D.m-6正確答案：D參考解析：循環(huán)隊列是隊列的一種順序存儲結(jié)構(gòu)，用隊尾指針rear指向隊列中的隊尾元素，用隊首指針指向隊首元素的前一個位置，因此，從隊首指針front指向的后一個位置直到隊尾指針rear指向的位置之間所有的元素均為隊列中的元素，隊列初始狀態(tài)為front=rear=m，當(dāng)front=20，rear=15時，隊列中有m-20+15=m-5個元素，最壞情況下需要比較次數(shù)為m-6次。答案選擇D選項。[單選題]52.設(shè)循環(huán)隊列為Q（1：m），其初始狀態(tài)為front=rear=m。經(jīng)過一系列入隊與退隊運算后，front=30，rear=10?，F(xiàn)要在該循環(huán)隊列中作順序查找，最壞情況下需要比較的次數(shù)為()。A.19B.20C.m-19D.m-20正確答案：C參考解析：循環(huán)隊列是隊列的一種順序存儲結(jié)構(gòu)，用隊尾指針rear指向隊列中的隊尾元素，用隊首指針指向隊首元素的前一個位置，因此，從隊首指針front指向的后一個位置直到隊尾指針rear指向的位置之間所有的元素均為隊列中的元素，隊列初始狀態(tài)為front=rear=m，當(dāng)front=30，rear=10時，隊列中有m-30+10=m-20個元素，最壞情況下需要比較次數(shù)為m-19次。答案選擇D選項。[單選題]53.下列敘述中正確的是()。A.循環(huán)隊列是順序存儲結(jié)構(gòu)B.循環(huán)隊列是鏈?zhǔn)酱鎯Y(jié)構(gòu)C.循環(huán)隊列是非線性結(jié)構(gòu)D.循環(huán)隊列的插入運算不會發(fā)生溢出現(xiàn)象正確答案：A參考解析：B項錯誤，循環(huán)隊列是一種順序存儲結(jié)構(gòu)的隊列；C項錯誤，線性結(jié)構(gòu)是一個非空序列：除第一個元素外，每個元素，有且只有一個前件；除最后一個元素外，每個元素有且只有一個后件，所以循環(huán)隊列是線性結(jié)構(gòu)；D項錯誤，當(dāng)循環(huán)隊列的元素個數(shù)等于存儲長度后，入隊會發(fā)生溢出現(xiàn)象，覆蓋前面的數(shù)據(jù)。答案選擇A選項。[單選題]54.一個棧的初始狀態(tài)為空。現(xiàn)將元素A，B，C，D，E依次入棧，然后依次退棧三次，并將退棧的三個元素依次入隊（原隊列為空），最后將隊列中的元素全部退出。則元素退隊的順序為()。A.ABCB.CBAC.EDCD.CDE正確答案：C參考解析：棧具有先進后出的特點，要求插入和刪除都只能在表的同一端進行；隊列具有先進先出的特點，在表的一端進行插入，另一端進行刪除。元素入棧后為ABCDE，出棧并入隊后，隊中元素為EDC，因此出隊順序為EDC。答案選擇Ｃ選項。[單選題]55.設(shè)有棧S和隊列Q，初始狀態(tài)均為空。首先依次將A，B，C，D，E，F(xiàn)入棧，然后從棧中退出三個元素依次入隊，再將X，Y，Z入棧后，將棧中所有元素退出并依次入隊，最后將隊列中所有元素退出，則退隊元素的順序為()。A.DEFXYZABCB.FEDZYXCBAC.FEDXYZCBAD.DEFZYXABC正確答案：B參考解析：棧是所有的插入與刪除都在同一端進行的線性表。隊列是只允許在一端進行插入，而在另一端進行刪除的線性表。將A，B，C，D，E，F(xiàn)入棧后，棧中元素為ABCDEF，退出三個元素入隊，隊列元素為FED，將X，Y，Z入棧后棧中元素為ABCXYZ，全部入隊后，隊列元素為FEDZYXCBA，隊列的出隊順序與入隊順序一致。答案選擇B選項。[單選題]56.在下列鏈表中，能夠從任意一個結(jié)點出發(fā)遍歷訪問到所有結(jié)點的是()。A.單鏈表B.循環(huán)鏈表C.雙向鏈表D.二叉鏈表正確答案：B參考解析：循環(huán)鏈表的最后一個結(jié)點的指針域指向表頭結(jié)點，所有結(jié)點的指針構(gòu)成了一個環(huán)狀鏈，只要指出表中任何一個結(jié)點的位置，就可以從它出發(fā)訪問到表中其他所有的結(jié)點。A項，線性單鏈表的每個結(jié)點只有一個指針域，由這個指針只能找到其后繼結(jié)點，但不能找到其前驅(qū)結(jié)點。也就是說，只能順著指針向鏈尾方向進行掃描，因此必須從頭指針開始，才能訪問到所有的結(jié)點；C項，雙向鏈表中的每個結(jié)點設(shè)置有兩個指針，一個指向其前驅(qū)，一個指向其后繼，這樣從任意一個結(jié)點開始，既可以向前查找，也可以向后查找。在結(jié)點的訪問過程中一般從當(dāng)前結(jié)點向鏈尾方向掃描，如果沒有找到，則從鏈尾向頭結(jié)點方向掃描。這樣，部分結(jié)點就要被遍歷兩次；D項，二叉鏈表是二叉樹的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)，每個結(jié)點有兩個指針域，分別指向左右子結(jié)點，可見，二叉鏈表只能由根結(jié)點向葉子結(jié)點的方向遍歷，其他部分的結(jié)點無法訪問。答案選擇B選項。[單選題]57.下列鏈表中，其邏輯結(jié)構(gòu)屬于非線性結(jié)構(gòu)的是()。A.二叉鏈表B.循環(huán)鏈表C.雙向鏈表D.帶鏈的棧正確答案：A參考解析：一個非空的數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)需要滿足兩個條件：①有且只有一個根結(jié)點；②每一個結(jié)點最多有一個前件，也最多有一個后件。不是線性結(jié)構(gòu)的就是非線性結(jié)構(gòu)。二叉鏈表是二叉樹的存儲結(jié)構(gòu)，每個結(jié)點都可以有兩個后繼結(jié)點，是非線性結(jié)構(gòu)。BCD三項均滿足線性結(jié)構(gòu)的要求。答案選擇A選項。[單選題]58.下列線性鏈表的敘述中，正確的是()。A.各數(shù)據(jù)結(jié)點的存儲空間可以不連續(xù)，但它們的存儲順序與邏輯順序必須一致B.各數(shù)據(jù)結(jié)點的存儲順序與邏輯順序可以不一致，但它們的存儲空間必須連續(xù)C.進行插入與刪除時，不需要移動表中的元素D.以上三種說法都不對正確答案：C參考解析：AB兩項錯誤，在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù)，各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。線性鏈表在插入與刪除過程中不發(fā)生數(shù)據(jù)元素移動的現(xiàn)象，只需改變有關(guān)結(jié)點的指針，選項C正確。答案選擇C選項。[單選題]59.下列敘述中正確的是()。A.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)與順序存儲結(jié)構(gòu)所需要的存儲空間是相同的B.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)所需要的存儲空間一般要多于順序存儲結(jié)構(gòu)C.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)所需要的存儲空間一般要少于順序存儲結(jié)構(gòu)D.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)與順序存儲結(jié)構(gòu)在存儲空間的需求上沒有可比性正確答案：B參考解析：線性結(jié)構(gòu)常用存儲結(jié)構(gòu)為：①順序存儲結(jié)構(gòu)，物理上連續(xù)存儲，空間位置隱含邏輯位置；②鏈?zhǔn)酱鎯Y(jié)構(gòu)，存儲上不連續(xù)，通過指針相連。在鏈?zhǔn)酱鎯Ψ绞街校總€結(jié)點包含存放數(shù)據(jù)的數(shù)據(jù)域和存放指針的指針域。所以鏈?zhǔn)酱鎯Y(jié)構(gòu)所需的存儲空間一般要多于順序存儲結(jié)構(gòu)。答案選擇B選項。[單選題]60.下列敘述中正確的是()。A.順序存儲結(jié)構(gòu)的存儲空間一定是連續(xù)的，鏈?zhǔn)酱鎯Y(jié)構(gòu)的存儲空間不一定是連續(xù)的B.順序存儲結(jié)構(gòu)只針對線性結(jié)構(gòu)，鏈?zhǔn)酱鎯Y(jié)構(gòu)只針對非線性結(jié)構(gòu)C.順序存儲結(jié)構(gòu)能存儲有序表，鏈?zhǔn)酱鎯Y(jié)構(gòu)不能存儲有序表D.鏈?zhǔn)酱鎯Y(jié)構(gòu)比順序存儲結(jié)構(gòu)節(jié)省存儲空間正確答案：A參考解析：A項正確，在順序存儲結(jié)構(gòu)中，所有元素所占的存儲空間是連續(xù)的，而在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù)。BC兩項錯誤，線性表在計算機中的存放可以采用順序存儲結(jié)構(gòu)，也可采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都是既可用于線性結(jié)構(gòu)，也可以用于非線性結(jié)構(gòu)；D項錯誤，順序存儲時元素間的關(guān)系隱藏在物理結(jié)構(gòu)中，采用鏈?zhǔn)酱鎯Y(jié)構(gòu)不僅要存儲元素的值，元素間的邏輯關(guān)系還需要通過附設(shè)的指針字段來表示，因此，鏈?zhǔn)酱鎯Y(jié)構(gòu)需要更多的存儲空間。答案選擇A選項。[單選題]61.下列敘述中正確的是()。A.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)與順序存儲結(jié)構(gòu)所需要的存儲空間是相同的B.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)所需要的存儲空間一般要多于順序存儲結(jié)構(gòu)C.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)所需要的存儲空問一般要少于順序存儲結(jié)構(gòu)D.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)所需要的存儲空問與順序存儲結(jié)構(gòu)沒有任何關(guān)系正確答案：B參考解析：線性結(jié)構(gòu)常用存儲結(jié)構(gòu)為：①順序存儲結(jié)構(gòu)，物理上連續(xù)存儲，空間位置隱含邏輯位置；②鏈?zhǔn)酱鎯Y(jié)構(gòu)，存儲上不連續(xù)，通過指針相連。在鏈?zhǔn)酱鎯Ψ绞街?，每個結(jié)點包含存放數(shù)據(jù)的數(shù)據(jù)域和存放指針的指針域。所以鏈?zhǔn)酱鎯Y(jié)構(gòu)所需的存儲空間一般要多于順序存儲結(jié)構(gòu)。答案選擇B選項。[單選題]62.下列關(guān)于線性鏈表的敘述中，正確的是()。A.各數(shù)據(jù)結(jié)點的存儲空間可以不連續(xù)，但它們的存儲順序與邏輯順序必須一致B.各數(shù)據(jù)結(jié)點的存儲順序與邏輯順序可以不一致，但它們的存儲空間必須連續(xù)C.進行插入與刪除時，不需要移動表中的元素D.以上說法均不正確正確答案：C參考解析：線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表。線性鏈表的存儲空間可以不連續(xù)，其存儲順序和邏輯順序也不一定一致。線性鏈表一般用結(jié)點描述：結(jié)點=數(shù)據(jù)域+指針域。進行插入和刪除時，只需改變指針的指向，而不需要移動表中元素。答案選擇C選項。[單選題]63.下列敘述中正確的是()。A.結(jié)點中具有兩個指針域的鏈表一定是二叉鏈表B.結(jié)點中具有兩個指針域的鏈表可以是線性結(jié)構(gòu)，也可以是非線性結(jié)構(gòu)C.二叉樹只能采用鏈?zhǔn)酱鎯Y(jié)構(gòu)D.循環(huán)鏈表是非線性結(jié)構(gòu)正確答案：B參考解析：A項錯誤，具有兩個指針域的鏈表可能是雙向鏈表，也可能是二叉鏈表，其中雙向鏈表是線性結(jié)構(gòu)，二叉樹為非線性結(jié)構(gòu)；B項正確，如雙向鏈表是線性結(jié)構(gòu)，二叉樹為非線性結(jié)構(gòu)，兩者結(jié)點中均有兩個指針域；C項錯誤，二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，也可采用其他結(jié)構(gòu)；D項錯誤，循環(huán)鏈表是線性結(jié)構(gòu)，邏輯概念線性非線性與實際存儲結(jié)構(gòu)無關(guān)。答案選擇B選項。[單選題]64.下列關(guān)于線性鏈表的描述中，正確的是()。Ⅰ.只含有一個指針域來存放下一個元素地址Ⅱ.指針域中的指針用于指向該結(jié)點的前一個或后一個結(jié)點（即前件或后件）Ⅲ.結(jié)點由兩部分組成：數(shù)據(jù)域和指針域。A.僅Ⅰ、ⅡB.僅Ⅰ、ⅢC.僅Ⅱ、ⅢD.全部正確答案：C參考解析：在鏈?zhǔn)酱鎯Ψ绞街?，雙向鏈表有兩個指針域，故Ⅰ錯誤。每個結(jié)點包含存放數(shù)據(jù)的數(shù)據(jù)域和存放指針的指針域，故Ⅲ正確。指針用于表示線性邏輯關(guān)系，指向該結(jié)點的前驅(qū)、后繼或者兩者都有，故Ⅱ正確。答案選擇C選項。[單選題]65.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)與順序存儲結(jié)構(gòu)相比，鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)點有()。A.節(jié)省存儲空間B.插入與刪除運算效率高C.便于查找D.排序時減少元素的比較次數(shù)正確答案：B參考解析：順序表可以隨機存取，元素間關(guān)系隱藏于存儲關(guān)系中，但插入與刪除操作需要移動大量元素，降低了效率；鏈表查找時需要沿鏈依次比較，效率低，為了表示元素間關(guān)系需要額外的指針域，但插入與刪除操作僅需改變指針，比順序表快。答案選擇B選項。[單選題]66.下列敘述中錯誤的是()。A.在鏈表中，如果每個結(jié)點有兩個指針域，則該鏈表一定是非線性結(jié)構(gòu)B.在鏈表中，如果有兩個結(jié)點的同一個指針域的值相等，則該鏈表一定是非線性結(jié)構(gòu)C.在鏈表中，如果每個結(jié)點有兩個指針域，則該鏈表不一定是線性結(jié)構(gòu)D.在鏈表中，如果有兩個結(jié)點的同一個指針域的值相等，則該鏈表一定不是線性結(jié)構(gòu)正確答案：A參考解析：非空的線性結(jié)構(gòu)是一個滿足：①有且只有一個根結(jié)點；②每一個結(jié)點最多有一個前件，也最多有一個后件，A項錯誤，雙向鏈表中結(jié)點的兩個指針域分別指向其前后結(jié)點，它是線性結(jié)構(gòu)。答案選擇A選項。[單選題]67.下列敘述中正確的是()。A.存儲空間不連續(xù)的所有鏈表一定是非線性結(jié)構(gòu)B.結(jié)點中有多個指針域的所有鏈表一定是非線性結(jié)構(gòu)C.能順序存儲的數(shù)據(jù)結(jié)構(gòu)一定是線性結(jié)構(gòu)D.帶鏈的棧與隊列是線性結(jié)構(gòu)正確答案：D參考解析：一個有且只有一個根結(jié)點；每一個結(jié)點最多有一個前件，也最多有一個后件的非空的數(shù)據(jù)結(jié)構(gòu)被稱為線性結(jié)構(gòu)，棧和隊列是受限的線性表。A項錯誤，線性表采用鏈?zhǔn)酱鎯r空間不連續(xù)；B項錯誤，雙向鏈表結(jié)點有兩個指針域，但它是線性結(jié)構(gòu)；C項錯誤，二叉樹也可以采用順序存儲結(jié)構(gòu)，樹是非線性結(jié)構(gòu)。答案選擇D選項。[單選題]68.下列敘述中正確的是()。A.鏈表結(jié)點中具有兩個指針域的數(shù)據(jù)結(jié)構(gòu)可以是線性結(jié)構(gòu)，也可以是非線性結(jié)構(gòu)B.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，每個結(jié)點必須有指向前件和指向后件的兩個指針C.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，每個結(jié)點只能有一個指向后件的指針D.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，葉子結(jié)點的指針只能是空正確答案：A參考解析：雙向鏈表具有兩個指針域，是線性結(jié)構(gòu)；二叉樹具有兩個指針域，是非線性結(jié)構(gòu)；A項正確。B項錯誤，線性表可以以單鏈表形式存儲，只有一個指針；C項錯誤，雙向鏈表每個結(jié)點可以同時包含指向前件和后件的指針；D項錯誤，線性表中不包含葉子結(jié)點。答案選擇A選項。[單選題]69.下列敘述中正確的是()。A.有兩個指針域的鏈表稱為二叉鏈表B.循環(huán)鏈表是循環(huán)隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)C.帶鏈的棧有棧頂指針和棧底指針，因此又稱為雙重鏈表D.結(jié)點中具有多個指針域的鏈表稱為多重鏈表正確答案：D參考解析：A項錯誤，雙向鏈表不是二叉鏈表，但也是有兩個指針域；B項錯誤，循環(huán)鏈表與循環(huán)隊列是不同的存儲結(jié)構(gòu)，循環(huán)隊列是一種順序存儲結(jié)構(gòu)。C項錯誤，帶鏈的棧是單鏈表，結(jié)點只有一個指針域。答案選擇D選項。[單選題]70.下列敘述中正確的是()。A.帶鏈隊列的存儲空間可以不連續(xù)，但隊頭指針必須大于隊尾指針B.帶鏈隊列的存儲空間可以不連續(xù)，但隊頭指針必須小于隊尾指針C.帶鏈隊列的存儲空間可以不連續(xù)，且隊頭指針可以大于也可以小于隊尾指針D.帶鏈隊列的存儲空間一定是不連續(xù)的正確答案：C參考解析：帶鏈的隊列就是用一個單鏈表來表示隊列，它既可以采用空間連續(xù)的順序存儲也可以采用空間不連續(xù)的鏈接存儲。在循環(huán)鏈隊中，隊頭指針可以大于也可以小于隊尾指針。答案選擇C選項。[單選題]71.下列敘述中錯誤的是()。A.在帶鏈隊列中，隊頭指針和隊尾指針都是在動態(tài)變化的B.在帶鏈棧中，棧頂指針和棧底指針都是在動態(tài)變化的C.在帶鏈棧中，棧頂指針是在動態(tài)變化的，但棧底指針是不變的D.在帶鏈隊列中，隊頭指針和隊尾指針可以指向同一個位置正確答案：B參考解析：帶鏈的隊列就是用一個單鏈表來表示隊列，隊列中的每一個元素對應(yīng)鏈表中的一個結(jié)點，在入隊和退隊過程中，隊頭指針和隊尾指針都是在動態(tài)變化的，A項正確；棧的入棧和退棧操作只在棧頂進行，所以棧頂指針變化，棧底指針不變，B項錯誤；帶鏈的棧在入棧和退棧過程中棧底指針不變，棧頂指針隨之變化，C項正確；循環(huán)隊列中當(dāng)隊列滿或者空時，隊頭指針和隊尾指針指向同一個位置，D項正確，因為帶鏈隊列為空時，隊頭指針和隊尾指針指向同一個位置。答案選擇B選項。[單選題]72.下列敘述中正確的是()。A.棧與隊列都只能順序存儲B.循環(huán)隊列是隊列的順序存儲結(jié)構(gòu)C.循環(huán)鏈表是循環(huán)隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)D.棧是順序存儲結(jié)構(gòu)而隊列是鏈?zhǔn)酱鎯Y(jié)構(gòu)正確答案：B參考解析：棧是所有的插入與刪除都限定在表的同一端進行的線性表；隊列是指允許在一端進行插入，而在另一端進行刪除的線性表，二者既可以順序存儲也可以鏈?zhǔn)酱鎯?。為了充分地利用?shù)組的存儲空間，把數(shù)組的前端和后端連接起來，形成一個環(huán)形的表，稱為循環(huán)隊列，因此循環(huán)隊列是隊列的一種順序存儲結(jié)構(gòu)。答案選擇B選項。[單選題]73.下列敘述中正確的是()。A.循環(huán)隊列屬于隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)B.雙向鏈表是二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)C.非線性結(jié)構(gòu)只能采用鏈?zhǔn)酱鎯Y(jié)構(gòu)D.有的非線性結(jié)構(gòu)也可以采用順序存儲結(jié)構(gòu)正確答案：D參考解析：循環(huán)隊列是隊列的一種順序存儲結(jié)構(gòu)，A項錯誤。雙向鏈表為順序存儲結(jié)構(gòu)，二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，B項錯誤。完全二叉樹是屬于非線性結(jié)構(gòu)，但其最佳存儲方式是順序存儲方式，C項錯誤。答案選擇D選項。[單選題]74.下列敘述中正確的是()。A.每一個結(jié)點有兩個指針域的鏈表一定是非線性結(jié)構(gòu)B.所有結(jié)點的指針域都為非空的鏈表一定是非線性結(jié)構(gòu)C.循環(huán)鏈表是循環(huán)隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)D.線性結(jié)構(gòu)的存儲結(jié)點也可以有多個指針正確答案：D參考解析：D項正確，雙向鏈表結(jié)點具有多個指針域。A項錯誤，雙向鏈表結(jié)點具有兩個指針域，屬于線性結(jié)構(gòu)；B項錯誤，循環(huán)鏈表所有結(jié)點的指針域都為非空，屬于線性結(jié)構(gòu)；C項錯誤，循環(huán)鏈表是鏈表，循環(huán)隊列屬于隊列，隊列只能在隊尾入隊，在隊頭出隊，鏈表可以在任何位置插入、刪除。答案選擇D選項。[單選題]75.某系統(tǒng)總體結(jié)構(gòu)如下圖所示：該系統(tǒng)總體結(jié)構(gòu)圖的深度是()。A.7B.6C.3D.2正確答案：C參考解析：這個系統(tǒng)總體結(jié)構(gòu)圖是一棵樹結(jié)構(gòu)，在樹結(jié)構(gòu)中，根結(jié)點在第1層，同一層上所有子結(jié)點都在下一層。由系統(tǒng)總體結(jié)構(gòu)圖可知，這棵樹共3層。在樹結(jié)構(gòu)中，樹的最大層次稱為樹的深度，故該系統(tǒng)的深度為3。答案選擇C選項。[單選題]76.下列關(guān)于二叉樹的敘述中，正確的是()。A.葉子結(jié)點總是比度為2的結(jié)點少一個B.葉子結(jié)點總是比度為2的結(jié)點多一個C.葉子結(jié)點數(shù)是度為2的結(jié)點數(shù)的兩倍D.度為2的結(jié)點數(shù)是度為1的結(jié)點數(shù)的兩倍正確答案：B參考解析：根據(jù)二叉樹的基本性質(zhì)，在任意一棵二叉樹中，度為0的結(jié)點（即葉子結(jié)點）總是比度為2的結(jié)點多一個。答案選擇B選項。[單選題]77.一棵二叉樹共有25個結(jié)點，其中5個葉子結(jié)點，那么度為1的結(jié)點數(shù)為()。A.4B.6C.10D.16正確答案：D參考解析：根據(jù)二叉樹的性質(zhì)3：在任意一棵二叉樹中，度為0的葉子結(jié)點總是比度為2的結(jié)點多一個，所以度為2的結(jié)點數(shù)為4個，那么25-5-4=16即為度為1的結(jié)點數(shù)。答案選擇D選項。[單選題]78.某二叉樹共有7個結(jié)點，其中葉子結(jié)點只有1個，則該二叉樹的深度為()。（假設(shè)根結(jié)點在第1層）A.3B.4C.6D.7正確答案：D參考解析：在任意一個二叉樹中，度為0的葉子結(jié)點總比度為2的結(jié)點多一個，所以本題中度為2的結(jié)點為1-1=0個，即二叉樹的每一個結(jié)點都只有一個孩子，7個結(jié)點共7層。答案選擇D選項。[單選題]79.某二叉樹有5個度為2的結(jié)點，則該二叉樹中的葉子結(jié)點數(shù)是()。A.10B.8C.6D.4正確答案：C參考解析：由二叉樹的性質(zhì)可知，對于任何一棵二叉樹，其終端結(jié)點（葉子結(jié)點）數(shù)等于度為2的結(jié)點數(shù)加1。所以該二叉樹的葉子結(jié)點數(shù)為5+1=6。答案選擇C選項。[單選題]80.具有3個結(jié)點的二叉樹有()。A.2種形態(tài)B.4種形態(tài)C.7種形態(tài)D.5種形態(tài)正確答案：D參考解析：具有3個結(jié)點的二叉樹有以下幾種形態(tài)：[單選題]81.在一棵二叉樹上，第5層的結(jié)點數(shù)最多是()。A.8B.9C.15D.16正確答案：D參考解析：二叉樹中，第i層上至多有2i-1個結(jié)點，所以第5層的結(jié)點數(shù)最多為25-1=16。答案選擇D選項。[單選題]82.下列二叉樹描述中，正確的是()。A.任何一棵二叉樹必須有一個度為2的結(jié)點B.二叉樹的度可以小于2C.非空二叉樹有0個或1個根結(jié)點D.至少有2個根結(jié)點正確答案：B參考解析：空樹度為0，斜二叉樹度為1，故A項錯誤，B項正確。空二叉樹沒有結(jié)點，非空二叉樹的定義中要求有且只有一個結(jié)點是該樹的根結(jié)點，故C和D項錯誤。答案選擇B選項。[單選題]83.某二叉樹中度為2的結(jié)點有10個，則該二叉樹中有()個葉子結(jié)點。A.9B.10C.11D.12正確答案：C參考解析：對任何一棵二叉樹，度為0的葉子結(jié)點總是比度為2的結(jié)點多一個。當(dāng)度為2的結(jié)點為10時，葉子結(jié)點數(shù)為10+1=11。答案選擇C選項。[單選題]84.設(shè)一棵滿二叉樹共有15個結(jié)點，則在該滿二叉樹中的葉子結(jié)點數(shù)為()。A.7B.8C.9D.10正確答案：B參考解析：滿二叉樹是除了葉子結(jié)點外所有結(jié)點度都為2的二叉樹，當(dāng)其有n個結(jié)點時，非葉子結(jié)點數(shù)為int(n/2)。本題n=15，故非葉子結(jié)點數(shù)等于int(15/2)=7，葉子結(jié)點數(shù)等于15-7=8。答案選擇B選項。[單選題]85.在一棵二叉樹中，葉子結(jié)點共有30個，度為1的結(jié)點共有40個，則該二叉樹中的總結(jié)點數(shù)共有()個。A.89B.93C.99D.100正確答案：C參考解析：對任何一棵二叉樹，度為0的葉子結(jié)點總是比度為2的結(jié)點多一個。在該二叉樹中，度為2的結(jié)點有29個，所以葉子結(jié)點有30個，結(jié)點總數(shù)共30+29+40=99。答案選擇C選項。[單選題]86.一棵二叉樹中共有70個葉子結(jié)點與80個度為1的結(jié)點，則該二叉樹中的總結(jié)點數(shù)為()。A.219B.221C.229D.231正確答案：A參考解析：任意二叉樹中，度為0的葉子結(jié)點個數(shù)總比度為2的結(jié)點數(shù)多1，所以度為2的結(jié)點的個數(shù)為70-1=69?？偨Y(jié)點數(shù)=70+80+69=219。答案選擇A選項。[單選題]87.某二叉樹中有n個度為2的結(jié)點，則該二叉樹中的葉子結(jié)點數(shù)為()。A.n+1B.n-1C.2nD.n/2正確答案：A參考解析：在任意的二叉樹中，度為0的葉子結(jié)點總是比度為2的結(jié)點多一個。所以本題中葉子結(jié)點數(shù)為n+1。答案選擇A選項。[單選題]88.某二叉樹中有n個葉子結(jié)點，則該二叉樹中度為2的結(jié)點數(shù)為()。A.n+1B.n-1C.2nD.n/2正確答案：B參考解析：任何一棵二叉樹的葉子結(jié)點總是比度為2的結(jié)點多一個。答案選擇B選項。[單選題]89.在深度為7的滿二叉樹中，度為2的結(jié)點個數(shù)為()。A.64B.63C.32D.31正確答案：B參考解析：根據(jù)滿二叉樹的性質(zhì)可得，除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點，葉子結(jié)點總是比度為2的結(jié)點多一個，第7層上的葉子結(jié)點數(shù)最多為27-1＝64個，所以度為2的結(jié)點個數(shù)為64-1=63。答案選擇B選項。[單選題]90.深度為7的完全二叉樹中共有125個結(jié)點，則該完全二叉樹中的葉子結(jié)點數(shù)為()。A.62B.63C.64D.65正確答案：B參考解析：定義一棵樹的根結(jié)點所在的層次為1，其他結(jié)點所在的層次等于它的父結(jié)點所在的層次加1，樹的最大層次稱為樹的深度。完全二叉樹指除最后一層外，每一層上的結(jié)點數(shù)均達到最大值，在最后一層上只缺少右邊的若干結(jié)點。本題中，前6層是滿二叉樹，結(jié)點個數(shù)為26-1=63，所以第7層有125-63=62個葉子結(jié)點，分別掛在第6層的左邊62個結(jié)點上，所以第6層的最后1個結(jié)點為葉子結(jié)點，該完全二叉樹共有62+1=63個葉子結(jié)點。答案選擇B選項。[單選題]91.深度為7的二叉樹共有127個結(jié)點，則下列說法中錯誤的是()。A.該二叉樹有一個度為1的結(jié)點B.該二叉樹是滿二叉樹C.該二叉樹是完全二叉樹D.該二叉樹有64個葉子結(jié)點正確答案：A參考解析：深度為7的二叉樹，前6層共有結(jié)點個數(shù)為26-1=63，則第7層有127-63=64個結(jié)點，即第7層結(jié)點數(shù)達到最大值，故此二叉樹為滿二叉樹，也是完全二叉樹，該二叉樹沒有度為1的結(jié)點，有64個葉子結(jié)點。答案選擇A選項。[單選題]92.某二叉樹中有15個度為1的結(jié)點，16個度為2的結(jié)點，則該二叉樹中總的結(jié)點數(shù)為()。A.32B.46C.48D.49正確答案：C參考解析：在樹結(jié)構(gòu)中，一個結(jié)點所擁有的后繼個數(shù)稱為該結(jié)點的度。由二叉樹的基本性質(zhì)可得，對于任何的二叉樹，葉子結(jié)點總是比度為2的結(jié)點多一個。因為度為2的結(jié)點有16個，所以葉子結(jié)點個數(shù)為17，因此結(jié)點總數(shù)為16+17+15=48。答案選擇C選項。[單選題]93.深度為5的完全二叉樹的結(jié)點數(shù)不可能是()。A.15B.16C.17D.18正確答案：A參考解析：深度為n的完全二叉樹的結(jié)點數(shù)范圍為：2n-1－1＋1～2n－1，本題中的范圍即為24－1＋1～25－1，即為16～31之間。所以節(jié)點數(shù)不可能是15，選A。[單選題]94.某二叉樹中共有935個結(jié)點，其中葉子結(jié)點有435個，則該二叉己樹中度為2的結(jié)點個數(shù)為()。A.64B.66C.436D.434正確答案：D參考解析：在樹結(jié)構(gòu)中，一個結(jié)點所擁有的后件個數(shù)稱為該結(jié)點的度。對于任何一棵二叉樹來說，度為0的結(jié)點總是比度為2的結(jié)點多一個。葉子結(jié)點有435個，則度為2的結(jié)點為434。答案選擇D選項。[單選題]95.某二叉樹共有845個結(jié)點，其中葉子結(jié)點有45個，則度為1的結(jié)點數(shù)為()。A.400B.754C.756D.不確定正確答案：C參考解析：在二叉樹中，度為0的結(jié)點總是比度為2的結(jié)點多一個，那么，結(jié)點共有845個，度為0的結(jié)點有45個，度為2的結(jié)點數(shù)有44個，所以度為1的結(jié)點數(shù)有756個。答案選擇C選項。[單選題]96.設(shè)有下列二叉樹：對此二叉樹前序遍歷的結(jié)果為()。A.ZBTYCPXAB.ATBZXCYPC.ZBTACYXPD.ATBZXCPY正確答案：B參考解析：二叉樹的前序遍歷是指首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹，并且，在遍歷左右子樹時，上述規(guī)則同樣適用，故該二叉樹的前序遍歷結(jié)果為：ATBZXCYP。答案選擇B選項。[單選題]97.設(shè)二叉樹如下：則前序遍歷為()。A.ABDEGCFHB.DBGEAFHCC.DGEBHFCAD.ABCDEFGH正確答案：A參考解析：前序遍歷，即訪問根結(jié)點在訪問左子樹和訪問右子樹之前。根結(jié)點A最先訪問，在BDEG四個節(jié)點根結(jié)點前面訪問，CHF三個節(jié)點在根結(jié)點后面訪問，很容易排除BCD選項，答案選擇A選項。另外，可以復(fù)習(xí)一下三種遍歷方式的規(guī)則，本題中前序遍歷為ABDEGCFH，中序遍歷為DBGEAFHC，后序遍歷為DGEBHFCA。[單選題]98.設(shè)二叉樹如下：則中序遍歷為()。A.ABDEGCFHB.DBGEAFHCC.DGEBHFCAD.ABCDEFGH正確答案：B參考解析：中序遍歷，即訪問根結(jié)點在訪問左子樹和訪問右子樹兩者之間。根結(jié)點A在BDEG四個節(jié)點后面訪問，CHF三個節(jié)點前面訪問，很容易排除ACD選項，選B。另外，可以復(fù)習(xí)一下三種遍歷方式的規(guī)則，本題中前序遍歷為ABDEGCFH，中序遍歷為DBGEAFHC，后序遍歷為DGEBHFCA。答案選擇B選項。[單選題]99.設(shè)二叉樹如下：則后序序列為()。A.ABDEGCFHB.DBGEAFHCC.DGEBHFCAD.ABCDEFGH正確答案：C參考解析：后序遍歷，先訪問左子樹，再訪問右子樹，最后訪問根結(jié)點。法一：本題中，樹不為空，所以先后序遍歷左子樹，得DGEB，再后序遍歷右子樹，得HFC，最后訪問根結(jié)點。所以該二叉樹的后序序列為DGEBHFCA。法二：由后序遍歷的過程知，樹的根結(jié)點一定是最后遍歷到，即A結(jié)點一定在遍歷序列的最后，答案選擇C選項。[單選題]100.設(shè)某二叉樹的前序遍歷為ABC，中序遍歷為CBA，則該二叉樹的后序遍歷為()。A.BCAB.CBAC.ABCD.CAB正確答案：B參考解析：因為前序遍歷為ABC，所以A為根結(jié)點；因為中序遍歷為CBA，所以C和B均為左子樹結(jié)點，且B是C的父結(jié)點，由此可知整棵樹結(jié)點的關(guān)系，得后序遍歷為CBA。答案選擇B選項。[單選題]101.設(shè)某二叉樹的后序遍歷為CBA，中序遍歷為ABC，則該二叉樹的前序遍歷為()。A.BCAB.CBAC.ABCD.CAB正確答案：C參考解析：因為后序遍歷為CBA，所以A為根結(jié)點。因為中序遍歷為ABC，所以B和C均為右子樹結(jié)點，且B為C父結(jié)點，可知前序遍歷為ABC。答案選擇C選項。[單選題]102.某二叉樹的前序序列為ABCD，中序序列為DCBA，則后序序列為()。A.BADCB.DCBAC.CDABD.ABCD正確答案：B參考解析：由前序序列ABCD得A為根結(jié)點，又因為中序序列為DCBA，所以DCB是A的左子樹。同理可得B是CD的根結(jié)點，DC是B的左子樹，C是D的根結(jié)點，所以可以確定二叉樹的形狀，得后序序列為DCBA。答案選擇B選項。[單選題]103.二叉樹的中序序列為BDCA，后序序列為DCBA，則前序序列為()。A.DCBAB.BDCAC.ABCDD.BADC正確答案：C參考解析：本題中中序序列為BDCA，后序序列為DCBA，可知A為根節(jié)點，BDC為左側(cè)節(jié)點，C是B右子節(jié)點，D是C左子節(jié)點，故前序序列為ABCD，答案選擇C選項。[單選題]104.己知二叉樹后序遍歷序列是CDABE，中序遍歷序列是CADEB，它的前序遍歷序列是()。A.ABCDEB.ECABDC.EACDBD.CDEAB正確答案：C參考解析：后序遍歷最后遍歷到根結(jié)點，所以E為根結(jié)點。中序遍歷根結(jié)點在左右子樹之間，所以B為二叉樹的右子樹，CAD為左子樹。同理，在CAD分支中，A為CD的父結(jié)點，C為A的左孩子，D為A的右孩子。根據(jù)所得樹的形狀，可得前序遍歷為EACDB。答案選擇C選項。[單選題]105.一棵二叉樹的前序遍歷結(jié)果是ABCEDF，中序遍歷結(jié)果是CBAEDF，則其后序遍歷的結(jié)果是()。A.DBACEFB.CBFDEAC.FDAEBCD.DFABEC正確答案：B參考解析：本題前序遍歷結(jié)果是ABCEDF，所以A為根結(jié)點。中序遍歷根結(jié)點在左右子樹之間，所以CB和EDF分別為左右子樹的中序遍歷結(jié)果。同理，在CB子樹中，B為父結(jié)點，C為左子樹，在EDF子樹中，E為父結(jié)點，DF為右子樹，DF中D為父結(jié)點，F(xiàn)為右子樹。所以后續(xù)遍歷結(jié)果為CBFDEA。答案選擇B選項。[單選題]106.某二叉樹的前序序列為ABCDEFG，中序序列為DCBAEFG，則該二叉樹的后序序列為()。A.EFGDCBAB.DCBEFGAC.BCDGFEAD.DCBGFEA正確答案：D參考解析：二叉樹的前序序列為ABCDEFG，A為根結(jié)點。中序序列為DCBAEFG，可知DCB為左子樹結(jié)點，EFG為右子樹結(jié)點。依此類推，畫出該二叉樹，二叉樹的后序序列為DCBGFEA。答案選擇D選項。[單選題]107.某二叉樹的前序遍歷為ABCDEFG，中序遍歷為DCBAEFG，則該二叉樹的深度（根結(jié)點在第1層）為()。A.2B.3C.4D.5正確答案：C參考解析：一棵樹的根結(jié)點所在的層次為1，其他結(jié)點所在的層次等于它的父結(jié)點所在的層次加1，樹的最大層次稱為樹的深度。本題中二叉樹的前序遍歷序列為ABCDEFG，所以A為根結(jié)點；中序遍歷序列為DCBAEFG，所以DCB為左子樹結(jié)點，EFG為右子樹結(jié)點。同理，在左子樹DCB中，依據(jù)前序遍歷序列可知B為根結(jié)點，由中序遍歷序列可知B結(jié)點只有左子樹，沒有右子樹，由前序遍歷序列和中序遍歷序列可知C是B的左子樹，D是C的右子樹。同理E為F根結(jié)點，F(xiàn)為G根結(jié)點，二叉樹深度為4層。答案選擇C選項。[單選題]108.某二叉樹的中序遍歷為DCBAEFG，后序遍歷為DCBGFEA，則該二叉樹的深度（根結(jié)點在第1層）為()。A.5B.4C.3D.2正確答案：B參考解析：定義一棵樹的根結(jié)點所在的層次為1，其他結(jié)點所在的層次等于它的父結(jié)點所在的層次加1，樹的最大層次稱為樹的深度。本題中，后序遍歷為DCBGFEA，所以A為根結(jié)點；中序遍歷為DCBAEFG，可知DCB為左子樹結(jié)點，EFG為右子樹結(jié)點。同理B為C父結(jié)點，C為D父結(jié)點，E為F根結(jié)點，F(xiàn)為G根結(jié)點。所以二叉樹深度為4層。答案選擇B選項。[單選題]109.對下二叉樹進行中序遍歷的結(jié)果是()。A.ABCDEFGHB.ABDGEHCFC.GDBEHACFD.GDHEBFCA正確答案：C參考解析：二叉樹的中序遍歷過程：先中序遍歷左子樹，再訪問根結(jié)點，最后中序遍歷右子樹。答案選擇C選項。[單選題]110.對下列二叉樹進行前序遍歷的結(jié)果為()。A.ABCDEFGHB.ABDGEHCFC.GDBEHACFD.GDHEBFCA正確答案：B參考解析：遍二叉樹的前序遍歷過程：先訪問根結(jié)點，再前序遍歷左子樹，最后前序遍歷右子樹。答案選擇B選項。[單選題]111.下列敘述中正確的是()。A.對長度為n的有序鏈表進行查找，最壞情況下需要的比較次數(shù)為nB.對長度為n的有序鏈表進行對分查找，最壞情況下需要的比較次數(shù)為（n/2）C.對長度為n的有序鏈表進行對分查找，最壞情況下需要的比較次數(shù)為（log2n）D.對長度為n的有序鏈表進行對分查找，最壞情況下需要的比較次數(shù)為（nlog2n）正確答案：A參考解析：對于順序查找，在最壞的情況下查找的是鏈表的最后一個元素，或者查找的元素不在表中，此時需要比較n次，A項正確。對分查找只適用于順序存儲的有序表，對于長度為n的有序線性表，最壞情況只需比較log2n次，BCD三項錯誤。答案選擇A選項。[單選題]112.在長度為n的有序線性表中進行二分查找，最壞情況下需要比較的次數(shù)是()。A.O（n）B.O（n2）C.O（log2n）D.O（nlog2n）正確答案：C參考解析：二分查找的最壞情況是不斷的二分直至無法再分時，仍然沒有查找成功。對于有序的線性表，二分查找法只需比較log2n次。答案選擇C選項。[單選題]113.為了對有序表進行二分查找，則要求有序表()。A.只能順序存儲B.只能鏈?zhǔn)酱鎯.可以順序存儲也可以鏈?zhǔn)酱鎯.任何存儲方式正確答案：A參考解析：二分法查找也稱折半查找，用順序存儲結(jié)構(gòu)存儲的線性有序表適用二分法查找。答案選擇A選項。[單選題]114.下列數(shù)據(jù)結(jié)構(gòu)中，能用二分法進行查找的是()。A.順序存儲的有序線性表B.線性鏈表C.二叉鏈表D.有序線性鏈表正確答案：A參考解析：二分查找只適用于順序存儲的有序表。此處所說的有序表是指線性表中的元素按值非遞減排列或非遞增排列。答案選擇A選項。[單選題]115.對有序線性表（23，29，34，55，60，70，78）用二分法查找值為60的元素時，需要比較次數(shù)為()。A.1B.2C.3D.4正確答案：C參考解析：二分法查找法不斷的將序列分為可能包含和必然不包含的兩部分，本題流程為：①將60與中間的元素55進行比較，60>55，所以60不可能在前4個元素中；②第二次將60與中間的元素70進行比較，60<70，所以60不可能在后2個元素中；③第三次將60與中間元素60比較，這時查找成功。答案選擇C選項。[單選題]116.下列敘述中正確的是()。A.所謂有序表是指在順序存儲空間內(nèi)連續(xù)存放的元素序列B.有序表只能順序存儲在連續(xù)的存儲空間內(nèi)C.有序表可以用鏈接存儲方式存儲在不連續(xù)的存儲空間內(nèi)D.任何存儲方式的有序表均能采用二分法進行查找正確答案：C參考解析：“有序”是指線性表中的元素按照升序或降序（允許相鄰元素相同）的方式排列。有序是一個邏輯概念，與物理存儲無關(guān)。二分法查找時涉及下標(biāo)運算，要求有序表必須順序存儲。答案選擇C選項。[單選題]117.設(shè)序列長度為n，在最壞情況下，時間復(fù)雜度為O（1og2n）的算法是()。A.二分法查找B.順序查找C.分塊查找D.哈希查找正確答案：A參考解析：對長度為n的線性表排序，最壞情況下時間復(fù)雜度，二分法查找為O（1og2n）；順序查找法為O（n）；分塊查找時間復(fù)雜度與分塊規(guī)則有關(guān)；哈希查找時間復(fù)雜度為O（1），因其通過計算哈希函數(shù)來定位元素位置，所以只需一次即可。答案選擇A選項。[單選題]118.下列排序方法中，最壞情況下比較次數(shù)最少的是()。A.冒泡排序B.簡單選擇排序C.直接插入排序D.堆排序正確答案：D參考解析：冒泡排序，簡單選擇排序和直接插入排序在最壞情況下的比較次數(shù)都是O（n2），而堆排序為O（nlog2n）。答案選擇D選項。[單選題]119.下列排序方法中，最壞情況下時間復(fù)雜度最小的是()。A.冒泡排序B.快速排序C.堆排序D.直接插入排序正確答案：C參考解析：在最壞情況下，當(dāng)線性表長度為n時，冒泡排序、快速排序、直接插入排序的最壞情況時間復(fù)雜度均為O（n2），而堆排序時間復(fù)雜度為O（nlog2n），復(fù)雜度最小。答案選擇C選項。[單選題]120.對長度為n的線性表排序，在最壞情況下，比較次數(shù)不是n（n-1）/2的排序方法是()。A.快速排序B.冒泡排序C.直接插入排序D.堆排序正確答案：D參考解析：在最壞情況下，冒泡排序、直接插入排序與簡單選擇排序法均需要比較n（n-1）/2次。希爾排序需要比較n1.5次，堆排序需要比較的次數(shù)最少，為nlog2n。答案選擇D選項。[單選題]121.待排序的關(guān)鍵碼序列為（15，20，9，30，67，65，45，90），要按關(guān)鍵碼值遞增的順序排序，采取簡單選擇排序法，第一趟排序后關(guān)鍵碼15被放到第()個位置。。A.2B.3C.4D.5正確答案：B參考解析：簡單選擇排序的算法可以描述為：將整個待排序序列分為有序和無序兩部分，初始時有序部分為空；每一趟排序時掃描無序序列，找到最小的元素，將它與無序序列的首元素交換位置，直到無序序列為空。所以第一趟排序后，將選出的最小元素9與15交換，15被放在第3個位置。答案選擇B選項。[單選題]122.設(shè)有關(guān)鍵碼序列（Q，G，M，Z，A，N，B，P，X，H，Y，S，T，L，K，E），采用堆排序法進行排序，經(jīng)過初始建堆后關(guān)鍵碼值B在序列中的序號是()。A.1B.3C.7D.9正確答案：B參考解析：堆排序是一種選擇排序的算法，首先將要排序的所有關(guān)鍵碼放到一棵完全二叉樹的各個結(jié)點中（這時的二叉樹不具備堆的特性），然后，從i=[n/2]（n為結(jié)點的個數(shù)）的結(jié)點Ki開始，逐步把以K[n/2]，K[n/2]-1，K[n/2]-2，…為根的子樹排成堆，直到以K1為根的樹排成堆，就完成了建堆過程。此題中，n=16，i=[16/2]=8，即從第8個結(jié)點開始。建堆完成后，如下圖所示：關(guān)鍵碼值B在序列中的序號是3。答案選擇B選項。[單選題]123.設(shè)有關(guān)鍵碼序列（66，13，51，76，81，26，57，69，23），要按關(guān)鍵碼值遞增的次序排序，若采用快速排序法，并以第一個元素為劃分的基準(zhǔn)，那么第一趟劃分后的結(jié)果為()。A.23，13，51，57，66，26，81，69，76B.13，23，26，51，57，56，81，76，69C.23，13，51，57，26，66，81，69，76D.23，13，51，57，81，26，66，69，76正確答案：C參考解析：設(shè)要排序的序列是A[0]……A[8]，設(shè)置兩個變量i、j，開始的時候：i=0，j=8。先從后向前遍歷，發(fā)現(xiàn)j=8時，指向23＜66，需要交換A[0]與A[8]，得到：（23，13，51，76，81，26，57，69，66），j=8，i=0，A[j]=66；然后從前往后遍歷，發(fā)現(xiàn)i=3時，指向76＞66，需要交換A[3]與A[8]，得到：（23，13，51，66，81，26，57，69，76），j=8，i=3；第二次從后向前遍歷，發(fā)現(xiàn)j=6時，指向57＜66，需要交換A[3]與A[6]，得到：（23，13，51，57，81，26，66，69，66），j=6，i=3；第二次從前往后遍歷，發(fā)現(xiàn)i=4時，指向81＞66，需要交換A[4]與A[6]，得到：（23，13，51，57，66，26，81，69，66），j=4，i=6；第三次從后向前遍歷，發(fā)現(xiàn)j=5時，A[5]=26＜66、需要交換A[5]與A[6]，得到：（23，13，51，57，26，66，81，69，66），j=5，i=5；第三次從前往后遍歷，A[5]=66，i+1=j，第一趟排序結(jié)束，即所求為（23，13，51，57，26，66，81，69，66），答案選擇C選項。[單選題]124.對于長度為n的線性表，在最壞情況下，下列各排序法所對應(yīng)的比較次數(shù)中正確的是()。A.冒泡排序為n(n-1)/2B.簡單插入排序為nC.希爾排序為nD.快速排序為n/2正確答案：A參考解析：在最壞情況下