計算機導論-第四章-算法與數據結構期末測試習題與答案計算機導論-第四章-算法與數據結構期末測試習題與答案計算機導論-第四章-算法與數據結構期末測試習題與答案V:1.0精細整理，僅供參考計算機導論-第四章-算法與數據結構期末測試習題與答案日期：20xx年X月一、選擇題1、算法的時間復雜度是指（）。A.算法執行過程中所需要的基本運算次數B.執行算法程序所需要的時間C.算法程序的長度D.算法程序中的指令條數正確答案：A2、算法的空間復雜度是指（）。A.算法程序的長度B.算法程序所占的存儲空間C.算法執行過程中所需要的存儲空間D.算法程序中的指令條數正確答案：C3、線性表采用鏈式存儲的優點是（）。A.花費的存儲空間較順序儲存少B.數據元素的物理順序與邏輯順序相同C.便于隨機存取D.便于插入和刪除操作正確答案：D4、下列敘述中正確的是（）。A.二叉樹是線性結構B.線性鏈表是非線性結構C.線性表是線性結構D.棧與隊列是非線性結構正確答案：C5、數據結構中，與所使用的計算機無關的是數據的（）。A.邏輯結構B.物理結構C.物理和存儲結構D.存儲結構正確答案：A6、存儲結構是指（）。A.邏輯結構在計算機中的表示B.數據所占的存儲空間量C.存儲在外存中的數據D.數據在計算機中的順序存儲方式正確答案：A7、下列關于隊列的敘述中，正確的是（）。A.隊列是先進后出B.隊列是先進先出C.在隊列中只能插入數據D.在隊列中只能刪除數據正確答案：B8、下列關于棧的敘述中，正確的是（）。A.棧只能采用順序存儲B.棧可以采用鏈式存儲，采用鏈式存儲時不會產生棧溢出現象。C.在棧中只能刪除數據D.在棧中只能插入數據正確答案：B9、對長度為n的線性表進行順序查找，查找成功時，最壞情況下所需要的比較次數為（）。A.n/2B.(n+1)/2C.n+lD.n正確答案：D10、下列敘述中，正確的是（）。A.以上三種說法都不對B.算法就是程序C.設計算法時只需要考慮結果的可靠性D.設計算法時只需要考慮數據結構的設計正確答案：A二、多選題1、如果進棧的順序為e1,e2,e3,e4，則可能的出棧序列是（）。A.e3,e1,e4,e2B.e4,e3,e2,e1C.e1,e2,e3,e4D.e2,e4,e3,e1正確答案：B、C、D2、已知二叉樹后序編歷序列是dabec，中續遍歷序列是debac，不是其前序編歷序列是（）。A.acbedB.cedbaC.deabcD.ceabd正確答案：A、C、D3、關于查找，說法正確的是（）。A.衡量查找算法性能時，平均比較次數是一個非常關鍵的指標。B.在鏈式存儲中，也可以使用二分查找。C.采用索引表查找時，需要為查找表建立索引表，且索引表中關鍵字有序。D.順序查找又稱順序搜索。一般是在線性表中查找指定的元素。正確答案：A、C、D4、關于二叉樹，說法正確的是（）。A.二叉樹是樹型結構的特例B.二叉樹及可以采用順序存儲，也可以采用鏈式存儲C.對任意一棵二叉樹T，若葉子結點數為n0，度數為2的結點數為n2，則n0=n2+1D.二叉樹是一種非線性結構正確答案：B、C、D三、判斷題1、數據結構包括三個方面的內容：數據的邏輯結構、數據的存儲結構和數據的運算。（對）2、同一種邏輯結構可以采用不同的存儲結構。（對）3、常見的存儲結構有4種，分別是順序存儲結構、鏈式存儲結構、索引存儲結構和散列存儲結構。（對）4、線性表、棧和隊列中，元素的關系都是線性關系。（對）5、可以將棧理解為是操作位置受限的線性表，僅能在一端插入，在另一端刪除。（錯）6、冒泡排序法和快速排序法都屬于交換類的排序方法。（對）7、樹的后序遍歷序列等同于該樹對應的二叉樹的中序遍歷序列。（對）8、在深度為5的滿二叉樹中，葉子結點的個數為15。（錯）9、樹是節點的集合，根節點數目是有且只有1個。（錯）10、通過哈夫曼樹可以求取哈夫曼編碼。（對）四、填空題1、（）是指解決問題的方法，而程序是該方法具體的實現。正確答案：算法2、順序存儲方法是把邏輯上相鄰的節點存儲在物理位置（）的存儲單元中。正確答案：連續3、數據的邏輯結構有線性和（）兩大類。正確答案：非線性4、在算法正確的前提下，評價一個算法的兩個標準是時間復雜度和（）。正確