計(jì)算機(jī)導(dǎo)論第四章算法與數(shù)據(jù)結(jié)構(gòu)期末測(cè)試習(xí)題與答案

1、、選擇題1、算法的時(shí)間復(fù)雜度是指（ ）。A. 算法執(zhí)行過(guò)程中所需要的基本運(yùn)算次數(shù)B. 執(zhí)行算法程序所需要的時(shí)間C. 算法程序的長(zhǎng)度D. 算法程序中的指令條數(shù)正確答案： A2、 算法的空間復(fù)雜度是指（）。A. 算法程序的長(zhǎng)度B. 算法程序所占的存儲(chǔ)空間C. 算法執(zhí)行過(guò)程中所需要的存儲(chǔ)空間D. 算法程序中的指令條數(shù)正確答案： C3、 線性表采用鏈?zhǔn)酱鎯?chǔ)的優(yōu)點(diǎn)是（）A. 花費(fèi)的存儲(chǔ)空間較順序儲(chǔ)存少B. 數(shù)據(jù)元素的物理順序與邏輯順序相同C. 便于隨機(jī)存取D .便于插入和刪除操作正確答案： D4、 下列敘述中正確的是（）。A. 二叉樹(shù)是線性結(jié)構(gòu)B. 線性鏈表是非線性結(jié)構(gòu)C. 線性表是線性結(jié)構(gòu)D .棧與隊(duì)

2、列是非線性結(jié)構(gòu)正確答案： C5、數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的（ ）A. 邏輯結(jié)構(gòu)B. 物理結(jié)構(gòu)C. 物理和存儲(chǔ)結(jié)構(gòu)D. 存儲(chǔ)結(jié)構(gòu)正確答案： A6、 存儲(chǔ)結(jié)構(gòu)是指（）。A. 邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示B. 數(shù)據(jù)所占的存儲(chǔ)空間量C. 存儲(chǔ)在外存中的數(shù)據(jù)D. 數(shù)據(jù)在計(jì)算機(jī)中的順序存儲(chǔ)方式正確答案： A7、 下列關(guān)于隊(duì)列的敘述中，正確的是（）。A. 隊(duì)列是先進(jìn)后出B. 隊(duì)列是先進(jìn)先出C. 在隊(duì)列中只能插入數(shù)據(jù)D. 在隊(duì)列中只能刪除數(shù)據(jù)正確答案： B8、 下列關(guān)于棧的敘述中，正確的是（）。A. 棧只能采用順序存儲(chǔ)B. 棧可以采用鏈?zhǔn)酱鎯?chǔ)，采用鏈?zhǔn)酱鎯?chǔ)時(shí)不會(huì)產(chǎn)生棧溢出現(xiàn)象。C. 在棧中只能刪除

3、數(shù)據(jù)D.在棧中只能插入數(shù)據(jù)正確答案： B 9 、對(duì)長(zhǎng)度為 n 的線性表進(jìn)行順序查找，查找成功時(shí)，最壞情況下所需要的比較次數(shù)為 （ ）。A. n/2B. （n+1）/2C. n+lD. n正確答案： D10 、下列敘述中，正確的是（ ）。A. 以上三種說(shuō)法都不對(duì)B. 算法就是程序C. 設(shè)計(jì)算法時(shí)只需要考慮結(jié)果的可靠性D. 設(shè)計(jì)算法時(shí)只需要考慮數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)正確答案： A二、多選題1、如果進(jìn)棧的順序?yàn)?e1,e2,e3,e4 ，則可能的出棧序列是（ ）。A. e3,e1,e4,e2B. e4,e3,e2,e1C. e1,e2,e3,e4D. e2,e4,e3,e1正確答案： B、C、D2、 已知二

4、叉樹(shù)后序編歷序列是dabec,中續(xù)遍歷序列是 debac,不是其前序編歷序列 是（ ）。A. acbedB. cedbaC. deabcD. ceabd正確答案： A、 C、D3、關(guān)于查找，說(shuō)法正確的是（）。A. 衡量查找算法性能時(shí)，平均比較次數(shù)是一個(gè)非常關(guān)鍵的指標(biāo)。B. 在鏈?zhǔn)酱鎯?chǔ)中，也可以使用二分查找。C. 采用索引表查找時(shí)，需要為查找表建立索引表，且索引表中關(guān)鍵字有序。D. 順序查找又稱順序搜索。一般是在線性表中查找指定的元素。正確答案： A、 C、D4、關(guān)于二叉樹(shù)，說(shuō)法正確的是（）。A. 二叉樹(shù)是樹(shù)型結(jié)構(gòu)的特例B. 二叉樹(shù)及可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)C. 對(duì)任意一棵二叉樹(shù) T

5、,若葉子結(jié)點(diǎn)數(shù)為n0 ,度數(shù)為2的結(jié)點(diǎn)數(shù)為n2 ,則nO=n2+1D. 二叉樹(shù)是一種非線性結(jié)構(gòu)正確答案： B、C、D三、判斷題1 、數(shù)據(jù)結(jié)構(gòu)包括三個(gè)方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算。 （對(duì)）2、同一種邏輯結(jié)構(gòu)可以采用不同的存儲(chǔ)結(jié)構(gòu)。（對(duì)）3、常見(jiàn)的存儲(chǔ)結(jié)構(gòu)有 4 種，分別是順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、索引存儲(chǔ)結(jié)構(gòu)和散 列存儲(chǔ)結(jié)構(gòu)。（對(duì)）4、線性表、棧和隊(duì)列中，元素的關(guān)系都是線性關(guān)系。（對(duì)）5、可以將棧理解為是操作位置受限的線性表，僅能在一端插入，在另一端刪除。（錯(cuò)）6、冒泡排序法和快速排序法都屬于交換類的排序方法。（對(duì)）7、樹(shù)的后序遍歷序列等同于該樹(shù)對(duì)應(yīng)的二叉樹(shù)的中序遍歷序列。（對(duì)）8、 在深度為 5 的滿二叉樹(shù)中，葉子結(jié)點(diǎn)的個(gè)數(shù)為15。（錯(cuò)） 9、樹(shù)是節(jié)點(diǎn)的集合，根節(jié)點(diǎn)數(shù)目是有且只有 1 個(gè)。（錯(cuò)）10 、通過(guò)哈夫曼樹(shù)可以求取哈夫曼編碼。（對(duì)） 四、填空題1、（）是指解決問(wèn)題的方法，而程序是該方法具體的實(shí)現(xiàn)。正確答案：算法2、順序存儲(chǔ)方法是把邏輯上相鄰的節(jié)點(diǎn)存儲(chǔ)在物理位置（ 正確答案：連續(xù)3、數(shù)據(jù)的邏輯結(jié)構(gòu)有線性和（）兩大類。正確答案：非線性4、在算法正確的前提下，評(píng)價(jià)一個(gè)算法的兩個(gè)標(biāo)準(zhǔn)是時(shí)間復(fù)雜度和 正確答案：