大學計算機第四章-練習題答案

1、第四章練習題答案(1) 下面表達正確的選項是 。 (C)A算法的執(zhí)行效率與數(shù)據(jù)的存儲結構無關B算法的空間復雜度是指算法程序中指令或語句的條數(shù)C算法的有窮性是指算法必須能在執(zhí)行有限個步驟之后終止D以上三種描述都不對(2) 算法的時間復雜度是指 。(C)A. 執(zhí)行算法程序所需要的時間B. 算法程序的長度C. 算法執(zhí)行過程中所需要的根本運算次數(shù)D. 算法程序中的指令條數(shù)(3) 算法的空間復雜度是指 。(D)A. 算法程序的長度B. 算法程序中的指令條數(shù)C. 算法程序所占的存儲空間D. 算法執(zhí)行過程中所需要的存儲空間(4) 以下表達中正確的選項是 。 (B)A) 算法的效率只與問題的規(guī)模有關，而與數(shù)據(jù)

2、的存儲結構無關B) 算法的時間復雜度是指執(zhí)行算法所需要的計算工作量C) 數(shù)據(jù)的邏輯結構與存儲結構是一一對應的D) 算法的時間復雜度與空間復雜度一定相關(5丨算法的有窮性是指 。( A )A算法程序的運行時間是有限的B算法程序所處理的數(shù)據(jù)量是有限的C算法程序的長度是有限的D算法只能被有限的用戶使用(6) 數(shù)據(jù)的存儲結構是指。 ( B )A. 數(shù)據(jù)所占的存儲空間量B.數(shù)據(jù)的邏輯結構在電腦中的表示C.數(shù)據(jù)在電腦中的順序存儲方式D.存儲在外存中的數(shù)據(jù)(7) 下面描述線性表的鏈式存儲結構錯誤的選項是 。(A)A線性表順序存儲B線性表隨機存儲C線性表的鏈式存儲結構也稱為線性鏈表D線性表的鏈式存儲結構只能順

3、序存取(8數(shù)據(jù)的存儲結構是指 。 BA. 數(shù)據(jù)所占的存儲空間量B. 數(shù)據(jù)的邏輯結構在電腦中的表示C. 數(shù)據(jù)在電腦中的順序存儲方式(9)以下表達中正確的選項是 。 DA一個邏輯數(shù)據(jù)結構只能有一種存儲結構B數(shù)據(jù)的邏輯結構屬于線性結構，存儲結構屬于非線性結構C一個邏輯數(shù)據(jù)結構可以有多種存儲結構，且各種存儲結構不影響數(shù)據(jù)處理的效率 D一個邏輯數(shù)據(jù)結構可以有多種存儲結構，且各種存儲結構影響數(shù)據(jù)處理的效率(10丨以下表達中正確的選項是 。 AA線性鏈表是線性表的鏈式存儲結構B) 棧與隊列是非線性結構C) 雙向鏈表是非線性結構D) 只有根結點的二叉樹是線性結構(13) 鏈表不具有的特點是 A。A.可隨機訪問

4、任一元素BC.不必事先估計存儲空間D(14) 以下關于隊列的表達中正確的選項是A.在隊列中只能插入數(shù)據(jù)B.C.隊列是先進先出的線性表D.(15) 用鏈表表示線性表的優(yōu)點是 <A.便于插入和刪除操作B.插入和刪除不需要移動元素 所需空間與線性表長度成正比。(C)在隊列中只能刪除數(shù)據(jù)隊列是先進后出的線性表(A)數(shù)據(jù)元素的物理順序與邏輯順序相同(11)數(shù)據(jù)結構中，與所使用的電腦無關的是數(shù)據(jù)的。C。A.存儲結構B.物理結構C.邏輯結構D.物理和存儲結構(12)以下表達中正確的選項是。(A)A. 線性表是線性結構B. 棧與隊列是非線性結構C. 線性鏈表是非線性結構D. 二叉樹是線性結構C.花費的存

5、儲空間較順序存儲少D.便于隨機存取(16) 按照后進先出原那么組織數(shù)據(jù)的數(shù)據(jù)結構是 。 BA) 隊列B)棧C)雙向鏈表D)二叉樹(17) 以下數(shù)據(jù)結構中不屬于線性數(shù)據(jù)結構的是 。(C)A.隊列 B.線性表C.二叉樹D.棧(18) 以下關于棧的描述中錯誤的選項是 。 BA) 棧是先進后出的線性表B) 棧必須鏈式存儲C) 棧具有記憶作用D) 對棧的插入與刪除操作中，不需要改變棧底指針(19丨以下關于棧的描述正確的選項是 。 CA在棧中只能插入元素而不能刪除元素B在棧中只能刪除元素而不能插入元素C棧是特殊的線性表，只能在一端插入或刪除元素D棧是特殊的線性表，只能在一端插入元素，而在另一端刪除元素 2

6、0丨以下關于棧的表達正確的選項是 。 BA棧按“先進先出組織數(shù)據(jù)B) 棧按“先進后出組織數(shù)據(jù)C只能在棧底插入數(shù)據(jù)D不能刪除數(shù)據(jù)(21) 以下表達中正確的選項是 。 DA 棧是“先進先出的線性表B丨隊列是“先進后出的線性表C丨循環(huán)隊列是非線性結構D丨有序線性表既可以采用順序存儲結構，也可以采用鏈式存儲結構(22) 以下對列的表達正確的選項是 。 ( D )A隊列屬于非線性表B) 隊列按“先進后出原那么組織數(shù)據(jù)C) 隊列在隊尾刪除數(shù)據(jù)D) 隊列按“先進先出原那么組織數(shù)據(jù)(23) 一個棧的初始狀態(tài)為空?，F(xiàn)將元素1、2、3、4、5、A、B、C、D、E依次入棧，然后再依次出棧，那么元素出棧的順序是BED

7、CBA54321D54321EDCBAA123456ABCDECABCDE12345(24) 按“先進后出原那么組織數(shù)據(jù)的結構是 。 B 。A.有序表 B 棧 C 隊列 D 二叉樹(25) 棧底至棧頂依次存放元素 A、B C、D,在第五個元素 E入棧前，棧中元素可以出棧，那么出棧序列可能是。(D)A. ABCEDB. DBCEAC. CDABED. DCBEA(26)假設進棧序列為1 , 2, 3,4,那么C不可能是出棧序夕列。A. 1 , 2, 3, 4B 4, 3, 2, 1C. 3, 4, 1, 2D 2, 4, 3, 1(27某二叉樹有5個度為2的結點，那么該二叉樹中的葉子結點數(shù)是 。

8、 CA10B8C6(28丨一棵二叉樹中共有D470個葉子結點與80個度為1的結點，那么該二叉樹中的總結點數(shù)為(29)(30)AOA219在深度為A)32 在深度為A. 32221 C 229B的滿二叉樹中，葉子結點的個數(shù)為_B)31C)64的滿二叉樹中，葉子結點的個數(shù)為 _B. 31D 231D)63。(C)某二叉樹中有n個度為A) n+1 B) n-1 C) 2n 設一棵完全二叉樹共有A. 349B. 350C.255D. 351(33丨對如下二叉樹進行后序遍歷的結果為(31)(32)C. 16 D.152的結點，那么該二叉樹中的葉子結點為_D) n/2699個結點，那么在該二叉樹中的葉子結

9、點數(shù)為OODD) DEBFCAAA. DBEGACFC. DGEBFCAB. ABDEGCFD. DEGBFCA35丨對以下二叉樹:進行中序遍歷的結果是AA、ACBDFEG B、ACBDFGEC 、ABDCGEFD 、FCADBEG(36)對以下二叉樹進行后序遍歷的結果A. ABCDEFG B. DBEGACFC. DGEBFCA D. DEGBFCA*(37)二叉樹后序遍歷序列是dabec,中序遍歷序列是debac，它的前序遍歷序列是。 A 。A. cedbaB . acbedC. decabD. cdeab(38)對于長度為n的線性表進行順序查找，在最壞情況下所需要的比擬次數(shù)為 。 CA)

10、 Iog2 n B) n/2 C) n D) n+1(39丨以下數(shù)據(jù)結構中，能用二分法進行查找的是 。 AA順序存儲的有序線性表B丨線性鏈表C二叉鏈表D有序線性鏈表(40)在長為64的有序線性表中進行順序查找，最壞情況下需要比擬的次數(shù)為。_B。A、63 B 、64 C 、6 D 、7二、填空題(1) 算法的復雜度主要包括復雜度和空間復雜度。答：時間(2) 數(shù)據(jù)結構包括數(shù)據(jù)的邏輯結構、數(shù)據(jù)的 以及對數(shù)據(jù)的操作運算。答：存儲結構(3) 順序存儲方法是把邏輯上相鄰的結點存儲在物理位置 的存儲單元中。答：相鄰(4) 棧的根本運算有三種：、退棧和讀棧頂元素。答：入棧(5) 在深度為5的完全二叉樹中，度為

11、2的結點數(shù)最多為 個?！?5】(6) 某二叉樹中度為2的結點有18個，那么該二叉樹中有 個葉子結點。19(7丨一棵二叉樹第六層根結點為第一層的結點數(shù)最多為個。32 (8在深度為7的滿二叉樹中，度為 2的結點個數(shù)為 63。(9)在深度為7的滿二叉樹中，葉子結點的個數(shù)為64。(10深度為5的滿二叉樹有【】個葉子結點。答：16(11) 設一棵二叉樹中有 3個葉子結點，有6個度為1的結點，那么該二叉樹中總的結點數(shù)為 個。 【11】(12) 設一棵完全二叉樹共有 500個結點，那么在該二叉樹中有 個葉子結點。答：250(13) 在最壞情況下，冒泡排序所需要的比擬次數(shù)為丨。n(n-1)/2(14) 對于線

12、性表(5,8,3,2 , 7 , 1 )，冒泡排序第一趟掃描的結果為 ；答：(5,3,2,7,1 ,8)(15) 對于線性表(12,8,9 , 17 , 5,3 )，冒泡排序第一趟掃描的結果為 :答：(8,9 , 12,5,3 ,17 )(16當線性表為無序表，那么無論其采用順序存儲結構或鏈式存儲結構，均可采用順序查找；順序查找的比擬次數(shù)最少 次。(1 )(17) 當線性表為無序表，那么無論其采用順序存儲結構或鏈式存儲結構，均可采用順序查找；順序查找的比擬次數(shù)最多 次。(n )(18) 在長度為N的線性表中進行二分查找，在最快的情況下，需要比擬的次數(shù)為?！?】。(19) 在長度為n的有序線性表中進行二分查找，最多比擬次數(shù)為 。LOG2(N +1)(20對于長度為n的線性表，冒泡排序最多需要對表掃描 遍；(n-1)(21) 選擇排序的算法第一步，掃描整個線性表，從中找出最小的元素，與元素交換；(第一個)(22) 對于線性表(5, 8,3,2 , 7 , 1 )，選擇排序最多需要對表掃描 遍答: