數(shù)據(jù)結(jié)構(gòu)課程三套作業(yè)及答案

1、數(shù)據(jù)結(jié)構(gòu)課程作業(yè)_A一、單選題。1.(7分)對完全二叉樹敘述正確的是（ C ）。A.完全二叉樹就是滿二叉樹B.完全二叉樹和滿二叉樹編號不對應(yīng)C.完全二叉樹同一層上左子樹未滿不會有右子樹D.以上都不正確知識點：第六章解析第六章第二節(jié)二叉樹的性質(zhì)2.(7分)堆的形狀是一棵（ C ）。A.二叉排序樹B.滿二叉樹C.完全二叉樹D.一般的二叉樹知識點：第十章解析第十章第四節(jié)堆排序3.(7分)設(shè)一棵完全二叉樹中有65個結(jié)點，則該完全二叉樹的深度為（ B ）。A.8B.7C.6D.5知識點：第六章解析第六章第六節(jié)二叉樹的性質(zhì)4.(7分)以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)？（ D ）A.隊列B.棧C.線性表D.

2、二叉樹知識點：第一章解析第一章第二節(jié)綜合題目5.(7分)線性表的順序存儲結(jié)構(gòu)是一種?的存儲結(jié)構(gòu)（ A ）。A.隨機存取B.順序存取C.索引存取D.散列存取知識點：第二章解析第二章第二節(jié)綜合題目6.(7分)帶頭節(jié)點的單鏈表L為空的判定條件是（ C ）。A.L = =nullB.L-data= =nullC.L-next= =nullD.L-next= =data知識點：第二章解析第二章第三節(jié)線性鏈表7.(7分)設(shè)一組初始記錄關(guān)鍵字序列為(45，80，55，40，42，85)，則以第一個記錄關(guān)鍵字45為基準(zhǔn)而得到一趟快速排序的結(jié)果是（ C ）。A.40，42，45，55，80，83B.42，40，

3、45，80，85，88C.42，40，45，55，80，85D.42，40，45，85，55，80知識點：第十章解析第十章第三節(jié)綜合題目8.(7分)設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20，15，14，18，21，36，40，10)，則以20為基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為（ A ）。A.10，15，14，18，20，36，40，21B.10，15，14，18，20，40，36，21C.10，15，14，20，18，40，36，2lD.15，10，14，18，20，36，40，21知識點：第十章解析第十章第三節(jié)綜合題目9.(7分)設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個記錄關(guān)鍵

4、字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為（ C ）。A.2，3，5，8，6B.3，2，5，8，6C.3，2，5，6，8D.2，3，6，5，8知識點：第十章解析第十章第三節(jié)綜合題目10.(7分)設(shè)指針變量p指向單鏈表結(jié)點A，則刪除結(jié)點A的后繼結(jié)點B需要的操作為（ A ）。A.p-next=p-next-nextB.p=p-nextC.p=p-next-nextD.p-next=p知識點：第二章解析第二章第三節(jié)線性鏈表二、判斷。1.(6分)棧和隊列都是操作受限的線性表。答案：正確。解析第三章綜合題目2.(6分)分塊查找的平均查找長度不僅與索引表的長度有關(guān)，而且與塊的長度有關(guān)。答案：正確。解析第九章第一節(jié)

5、索引順序表的查找3.(6分)數(shù)據(jù)項是數(shù)據(jù)的基本單位。答案：錯誤。解析第一章第二節(jié)數(shù)據(jù)項4.(6分)希爾排序是一種穩(wěn)定的排序方法。答案：錯誤。解析第十章第二節(jié)希爾排序5.(6分)二叉排序樹上左子樹上所有結(jié)點的值均小于它的根結(jié)點的值。答案：正確。解析第九章第二節(jié)二叉排序樹和平衡二叉樹數(shù)據(jù)結(jié)構(gòu)課程作業(yè)_B一、單選題。1.(7分)設(shè)某強連通圖中有n個頂點，則該強連通圖中至少有（ C ）條邊。A.n(n-1)B.n+1C.nD.n(n+1)知識點：第七章解析第七章第一節(jié)綜合題目2.(7分)鏈?zhǔn)疥犃蠶為空的判定條件（ A ）。A.Q.front=Q.rearB.Q.front=QC.Q =Q.rearD.

6、沒有正確答案知識點：第三章解析第三章第四節(jié)隊列的鏈?zhǔn)奖硎竞蛯崿F(xiàn)3.(7分)設(shè)某無向圖中有n個頂點e條邊，則建立該圖鄰接表的時間復(fù)雜度為（ A ）。A.O(n+e)B.O(n2)C.O(ne)D.O(n3)知識點：第七章解析第七章第二節(jié)鄰接表4.(7分)圖的廣度優(yōu)先遍歷算法類似于二叉樹的（ D ）。A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷知識點：第七章解析第七章第三節(jié)廣度優(yōu)先搜索5.(7分)圖的鄰接矩陣表示法適用于表示（ C ）。A.有向圖B.無向圖C.稠密圖D.稀疏圖知識點：第七章解析第七章第二節(jié)數(shù)組表示法6.(7分)設(shè)輸入序列是1、2、3、n，經(jīng)過棧的作用后輸出序列的第一個元素是n，

7、則輸出序列中第i個輸出元素是（ C ）。A.n-IB.n-1-IC.n+1-ID.不能確定知識點：第三章解析第三章第一節(jié)棧的表示和實現(xiàn)7.(7分)順序查找適用于存儲結(jié)構(gòu)為（ B ）的線性表。A.散列B.順序或者鏈?zhǔn)紺.壓縮D.索引知識點：第九章解析第九章第一節(jié)順序表的查找8.(7分)線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，要求內(nèi)存中的可用存儲單元的地址? （ D ）。A.必須連續(xù)B.部分連續(xù)C.一定不連續(xù)D.可連續(xù)可不連續(xù)知識點：第二章解析第二章第三節(jié)綜合題目9.(7分)設(shè)無向圖G中有n個頂點，則該無向圖的最小生成樹上有（ B ）條邊。A.nB.n-1C.2nD.2n-1知識點：第七章解析第七章第四節(jié)最小

8、生成樹10.(7分)設(shè)數(shù)組datam作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作后其頭指針front值為（ D ）。A.front=front+1B.front=(front+1)%(m-1)C.front=(front-1)%mD.front=(front+1)%m知識點：第三章解析第三章第四節(jié)隊列的順序表示和實現(xiàn)二、判斷。1.(6分)二叉排序樹上左子樹上所有結(jié)點的值均小于它的根結(jié)點的值。答案：正確。解析第九章第二節(jié)二叉排序樹和平衡二叉樹2.(6分)常用的圖的遍歷方法有深度優(yōu)先遍歷和廣度優(yōu)先遍歷。答案：正確。解析第七章第三節(jié)綜合題目3.(6分)數(shù)據(jù)項是

9、數(shù)據(jù)的基本單位。答案：錯誤。解析第一章第二節(jié)數(shù)據(jù)項4.(6分)二維數(shù)組和多維數(shù)組均不是特殊的線性結(jié)構(gòu)。答案：錯誤。解析第五章綜合題目5.(6分)分塊查找的平均查找長度不僅與索引表的長度有關(guān)，而且與塊的長度有關(guān)。答案：正確。解析第九章第一節(jié)索引順序表的查找數(shù)據(jù)結(jié)構(gòu)課程作業(yè)_C一、單選題。1.(7分)設(shè)按照從上到下、從左到右的順序從1開始對完全二叉樹進(jìn)行順序編號，則編號為i結(jié)點的左孩子結(jié)點的編號為（ B ）。A.2i+1B.2iC.i/2D.2i-1知識點：第六章解析第六章第六節(jié)二叉樹的性質(zhì)2.(7分)若采用孩子兄弟鏈表作為樹的存儲結(jié)構(gòu)，則樹的先根遍歷應(yīng)采用二叉樹的（ B ）。A.層次遍歷B.先序

10、遍歷C.中序遍歷D.后序遍歷知識點：第六章解析第六章第四節(jié)樹的存儲結(jié)構(gòu)3.(7分)若有18個元素的有序表存放在一維數(shù)組A19中，第一個元素放A1中，現(xiàn)進(jìn)行二分查找，則查找A3的比較序列的下標(biāo)依次為（ D ）。A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，3知識點：第九章解析第九章第一節(jié)有序表的查找4.(7分)設(shè)有序表中有1000個元素，則用二分查找查找元素X最多需要比較（ B ）次。A.25B.10C.7D.1知識點：第九章解析第九章第一節(jié)有序表的查找5.(7分)單鏈表的結(jié)點包含_和_。（ D ）A.結(jié)點域，符號域B.數(shù)據(jù)域，符號域C.結(jié)點域，指針域D.數(shù)據(jù)域，指針域知識點：第

11、二章解析第二章第三節(jié)線性鏈表6.(7分)設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（ A ）。A.BADCB.BCDAC.CDABD.CBDA知識點：第六章解析第六章第三節(jié)遍歷二叉樹7.(7分)序列278、109、930經(jīng)過一趟基數(shù)排序后結(jié)果為（ A ）。A.930、278、109B.109、930、278C.109、278、930D.278、109、930知識點：第十章解析第十章第六節(jié)多關(guān)鍵字的排序8.(7分)設(shè)某有向圖中有n個頂點，則該有向圖對應(yīng)的鄰接表中有（ B ）個表頭結(jié)點。A.n-1B.nC.n+1D.2n-1知識點：第七章解析第七章第二節(jié)鄰接表9.(7分)設(shè)一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時間復(fù)雜度為（ C ）。A.O(n)B.O(nlog2n)C.O(1)D.O(n2)知識點：第五章解析第五章第二節(jié)綜合題目10.(7分)一個棧的入棧序列是A、B、C、D、E，五個元素都入棧后，首次出棧的元素是（ B ）。A.AB.EC.BD.D知識點：第三章解析第三章第一節(jié)綜合題目二、判斷。1.(6分)已知一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。答案：錯誤。解析第六章第三節(jié)遍歷二叉