數(shù)據(jù)結(jié)構(gòu)與算法1.

關(guān)于算法的描述，以下選項(xiàng)中正確的是A、以上三種描述都不對(duì)B、算法的空間復(fù)雜度是指算法程序中指令（或語(yǔ)句）的條數(shù)C、算法的有窮性是指算法必須能在執(zhí)行有限個(gè)步驟之后終止D、算法的執(zhí)行效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)2.

以下選項(xiàng)中不屬于線性數(shù)據(jù)結(jié)構(gòu)的是A、線性表B、棧C、隊(duì)列D、二叉樹3.

某棵二叉樹上第五層的最大節(jié)點(diǎn)數(shù)是A、15B、32C、8D、164.

以下選項(xiàng)中描述正確的是A、線性表是線性結(jié)構(gòu)B、樹是線性結(jié)構(gòu)C、線性鏈表是非線性結(jié)構(gòu)D、棧與隊(duì)列是非線性結(jié)構(gòu)5.

設(shè)一顆完全二叉樹共有699個(gè)結(jié)點(diǎn)，則該節(jié)點(diǎn)的葉子結(jié)點(diǎn)數(shù)是A、349B、255C、351D、3506.

關(guān)于算法的空間復(fù)雜度，以下選項(xiàng)中描述正確的是A、算法執(zhí)行過程中所需要的存儲(chǔ)空間B、算法程序所占的存儲(chǔ)空間C、算法程序的長(zhǎng)度D、算法程序中的指令條數(shù)7.

關(guān)于棧的描述，以下選項(xiàng)中能夠正確的是A、在棧中只能插入數(shù)據(jù)B、在棧中只能刪除數(shù)據(jù)C、棧是先進(jìn)后出的線性表D、棧是先進(jìn)先出的線性表8.

在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成A、線性結(jié)構(gòu)和非線性結(jié)構(gòu)B、動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)C、內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)D、緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)9.

關(guān)于算法的控制結(jié)構(gòu)組合，以下描述正確的是A、順序，選擇，循環(huán)B、循環(huán)，分支，遞歸C、順序，循環(huán)，嵌套D、循環(huán)，遞歸，選擇10.

設(shè)有一個(gè)已按各元素的值排好序的線性表（長(zhǎng)度大于2），對(duì)給定的值k，分別用順序查找法和二分查找法查找，比較的次數(shù)分別是s和b，在查找不成功的情況下，s和b的關(guān)系是A、s>bB、s<bC、s=bD、s<=b11.

一個(gè)算法一般應(yīng)該具有的基本特征不包括A、確定性B、可行性C、無(wú)窮性D、擁有足夠多的情報(bào)12.

關(guān)于希爾排序，以下描述正確的是A、希爾排序?qū)儆诮粨Q類排序法B、希爾排序法屬于建堆排序法C、希爾排序法屬于插入類排序法D、希爾排序法屬于選擇類排序法13.

關(guān)于隊(duì)列的描述中，以下描述正確的是A、在隊(duì)列中只能插入數(shù)據(jù)B、在隊(duì)列中只能刪除數(shù)據(jù)C、隊(duì)列是先進(jìn)后出的線性表D、隊(duì)列是先進(jìn)先出的線性表14.

關(guān)于計(jì)算機(jī)算法的描述，以下選項(xiàng)中描述正確的是A、查詢方法B、排序方法C、加工方法D、解題方案的準(zhǔn)確而完整的描述15.

棧和隊(duì)列的共同點(diǎn)是A、都是先進(jìn)后出B、都是先進(jìn)先出C、沒有共同點(diǎn)D、只允許在端點(diǎn)處插入和刪除數(shù)據(jù)16.

設(shè)二叉樹后序遍歷序列是dabec，中序遍歷是debac，則其前序遍歷是A、deabcB、acbedC、cedbaD、decab17.

在下列幾種排序方法中，要求內(nèi)存量最大的是A、選擇排序B、歸并排序C、插入排序D、快速排序18.

在數(shù)據(jù)結(jié)構(gòu)中，所使用的計(jì)算機(jī)無(wú)關(guān)的是A、數(shù)據(jù)的物理結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)B、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C、數(shù)據(jù)的邏輯結(jié)構(gòu)D、數(shù)據(jù)的物理結(jié)構(gòu)19.

關(guān)于線性表的順序存儲(chǔ)結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，以下選項(xiàng)中描述正確的是A、順序存取的存儲(chǔ)結(jié)構(gòu)、順序存取的存儲(chǔ)結(jié)構(gòu)B、隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)、隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)C、任意存取的存儲(chǔ)結(jié)構(gòu)、任意存取的存儲(chǔ)結(jié)構(gòu)D、隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)、順序存取的存儲(chǔ)結(jié)構(gòu)20.

棧底至棧頂已存放存放元素A、B、C、D，在第五個(gè)元素E入棧前，棧中元素可以出棧，可能的出棧序列是A、DCBEAB、DBCEAC、CDABED、ABCED21.

在單鏈表中，增加表頭節(jié)點(diǎn)的目的是A、說明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)B、表示表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置C、方便運(yùn)算的實(shí)現(xiàn)D、使單鏈表至少有一個(gè)結(jié)點(diǎn)22.

算法分析的目的是A、找出數(shù)據(jù)結(jié)構(gòu)的合理性B、分析算法的易懂性和可靠性C、找出算法中輸入和輸出之間的關(guān)系D、分析算法的效率以求改進(jìn)23.

已知數(shù)據(jù)表A中每個(gè)元素距其位置不遠(yuǎn)，為節(jié)省時(shí)間，宜采用的算法是A、堆排序B、快速排序C、直接選擇排序D、直接插入排序24.

用鏈表表示線性表的優(yōu)點(diǎn)是A、便于插入和刪除操作B、便于隨機(jī)存儲(chǔ)C、花費(fèi)的存儲(chǔ)空間較順序存儲(chǔ)少D、數(shù)據(jù)元素的物理結(jié)構(gòu)和邏輯結(jié)構(gòu)相同25.

支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是A、樹B、棧C、隊(duì)列D、二叉樹26.

以下選項(xiàng)中，描述了算法的時(shí)間復(fù)雜度的是A、算法的時(shí)間復(fù)雜度是指算法程序的長(zhǎng)度B、算法的時(shí)間復(fù)雜度是指算法程序中的指令條數(shù)C、算法的時(shí)間復(fù)雜度是指執(zhí)行算法程序所需要的時(shí)間D、算法的時(shí)間復(fù)雜度是指算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù)27.

某二叉樹共有12個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)只有1個(gè)，則該二叉樹的深度為（根結(jié)點(diǎn)在第1層）A、6B、12C、3D、828.

對(duì)長(zhǎng)度為n的線性表作快速排序，在最壞情況下，比較次數(shù)為A、nB、n(n–1)/2C、n-1D、n(n–1)29.

關(guān)于算法的有窮性，以下選項(xiàng)中描述正確的是A、算法的長(zhǎng)度是有限的B、算法程序的運(yùn)行時(shí)間是有限的C、算法只能被有限的用戶使用D、算法程序所處理的數(shù)據(jù)量是有限的30.

下列數(shù)據(jù)結(jié)構(gòu)中，能夠按照“先進(jìn)后出”原則存取數(shù)據(jù)的是A、二叉樹B、隊(duì)列C、循環(huán)隊(duì)列D、棧參考答案1. C 算法的空間復(fù)雜度，一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。算法的基本特征主要包括以下四個(gè)方面：a、可行性：針對(duì)實(shí)際問題而設(shè)計(jì)的算法，執(zhí)行后能夠得到滿意的結(jié)果。b、確定性：算法中的每一個(gè)步驟都必須有明確的定義，不允許有模棱兩可的解釋和多義性。c、有窮性：算法必需在有限時(shí)間內(nèi)做完，即算法必需能在執(zhí)行有限個(gè)步驟之后終止。算法的執(zhí)行效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有關(guān)2. D 二叉樹屬于非線性數(shù)據(jù)結(jié)構(gòu)3. D 二叉樹中每一層的最大結(jié)點(diǎn)數(shù)為2m-1個(gè)結(jié)點(diǎn)4. A 樹屬于非線性結(jié)構(gòu)；線性鏈表是線性結(jié)構(gòu)；棧與隊(duì)列也是線性結(jié)構(gòu)。5. D 在完全二叉樹中，度為1的結(jié)點(diǎn)個(gè)數(shù)最多只有1個(gè)最少0個(gè)，其余的結(jié)點(diǎn)度全部為0或2。而根據(jù)二叉樹的基本性質(zhì)：度為0的結(jié)點(diǎn)(葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)。因此根據(jù)這兩個(gè)條件，我們可以知道度為0的結(jié)點(diǎn)個(gè)數(shù)+度為1的結(jié)點(diǎn)個(gè)數(shù)+度為2的結(jié)點(diǎn)個(gè)數(shù)=699。而度的個(gè)數(shù)一定是整數(shù)。因此很容易通過條件解出葉子結(jié)點(diǎn)數(shù)是3506. A 一個(gè)算法的空間復(fù)雜度，一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間以及算法執(zhí)行過程中所需要的額外空間。7. C 棧既可以插入數(shù)據(jù)也可以刪除數(shù)據(jù)，棧是先進(jìn)后出的線性表。8. A 在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成線性結(jié)構(gòu)和非線性結(jié)構(gòu)9. A 順序，選擇，循環(huán)是算法的控制結(jié)構(gòu)10. A在最壞的情況下，順序查找法和二分查找法查找的次數(shù)分別是n次和log2n次，在本題中可以看出s>b。11. C 算法的基本特征，具體如下：1、確定性：每一步指令必須有確定的含義。不可存在二義性，且算法只有一個(gè)入口和出口；2、有窮性：是指算法有有窮個(gè)步驟，并且執(zhí)行需有窮時(shí)間；3、可行性：算法原則上能夠精確地運(yùn)行，而且人們用筆和紙做有限次運(yùn)算后即可完成；4、擁有足夠的情報(bào)。12 C 希爾排序法屬于插入類排序法,實(shí)在簡(jiǎn)單插入排序法的基礎(chǔ)上改進(jìn)的。13. D 在隊(duì)列中可以插入數(shù)據(jù)和刪除數(shù)據(jù)，隊(duì)列是先進(jìn)先出的線性表14. D 所謂算法是指解題方案的準(zhǔn)確而完整的描述15. D 棧和隊(duì)列的共同點(diǎn)是只允許在端點(diǎn)處插入和刪除數(shù)據(jù)16. C 請(qǐng)查考26集視頻中的方法。17. B 歸并排序存在大量的數(shù)據(jù)拷貝，因此占用內(nèi)存量最大。18. C 在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)元素之間的前后件關(guān)系是邏輯結(jié)構(gòu)，而與它們?cè)谟?jì)算機(jī)中的存儲(chǔ)位置無(wú)關(guān)。19. D 順序存儲(chǔ)結(jié)構(gòu)的地址在內(nèi)存中是連續(xù)的所以可以通過計(jì)算地址實(shí)現(xiàn)隨機(jī)存取，而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)地址不一定連續(xù)，只能通過第1個(gè)結(jié)點(diǎn)的指針順序存?。?0. A棧的元素存取規(guī)則為：先進(jìn)后出，后進(jìn)先出。在本題中已經(jīng)存放了ABCD四個(gè)元素，因此出棧的可能性只能是D在C的前面，C在B的前面，B在A的前面，而符合這個(gè)順序的只有A選項(xiàng)。21. C 線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算，頭結(jié)點(diǎn)不僅標(biāo)識(shí)了表中首結(jié)點(diǎn)的位置，而且根據(jù)單鏈表(包含頭結(jié)點(diǎn))的結(jié)構(gòu)，只要掌握了表頭，就能夠訪問整個(gè)鏈表，因此增加頭結(jié)點(diǎn)目的是為了便于運(yùn)算的實(shí)現(xiàn)。22. D 算法分析是指對(duì)一個(gè)算法的運(yùn)行時(shí)間和占用空間做定量的分析，計(jì)算相應(yīng)的數(shù)量級(jí)。分析算法的目的就是要降低算法的時(shí)間復(fù)雜度和空間復(fù)雜度，提高算法的執(zhí)行效率。23. D 數(shù)據(jù)表A中每個(gè)元素距其位置不遠(yuǎn)，代表其數(shù)據(jù)大體是符合順序的，因此采用直接插入排序既可以節(jié)省時(shí)間。24. A 用鏈表表示線性表的優(yōu)點(diǎn)是便于插入和刪除操作25. B 在教學(xué)視頻中講過主程序與子程序之間的調(diào)用關(guān)系是通過棧的形式來(lái)保存每一次調(diào)用。26. D 算法的時(shí)間復(fù)雜度是指算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù)27. B 二叉樹的深度為12。因?yàn)槿~子節(jié)點(diǎn)為1個(gè)，按二叉樹理論得出（任意一