數(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

2、. 線性表D. 二叉樹知識點：第一章解析第一章第二節(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為基準而得到一趟快速排序的結(jié)果是（C）。A. 40，42，45

3、，55，80，83B. 42，40，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為基準記錄的一趟快速排序結(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知識點：第十章

4、解析第十章第三節(jié)綜合題目9 .（7分）設(shè)一組初始記錄關(guān)鍵字序列（5，2，6，3，8），以第一個記錄關(guān)鍵字5為基準進行一趟快速排序的結(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

5、分）棧和隊列都是操作受限的線性表。答案：正確。解析第三章綜合題目2 .（6分）分塊查找的平均查找長度不僅與索引表的長度有關(guān)，而且與塊的長度有關(guān)。答案：正確。解析第九章第一節(jié)索引順序表的查找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è)_BC ）條邊。一"、單選題。1.（7分）設(shè)某強連通圖中有n個頂點，則該強連通圖中至少有（A. n(n-1)B. n

6、+1C. nD. n(n+1)知識點：第七章解析第七章第一節(jié)綜合題目2 .(7分)鏈式隊列Q為空的判定條件(A)。A. Q.front=Q.rearB. Q.front=QC. Q=Q.rearD. 沒有正確答案知識點：第三章解析第三章第四節(jié)隊列的鏈式表示和實現(xiàn)3 .(7分)設(shè)某無向圖中有n個頂點e條邊，則建立該圖鄰接表的時間復(fù)雜度為(A)。A. O(n+e)B. O(n2)C. O(ne)D. O(n3)知識點：第七章解析第七章第二節(jié)鄰接表D）4 .（7分）圖的廣度優(yōu)先遍歷算法類似于二叉樹的（A. 先序遍歷B. 中序遍歷C. 后序遍歷D. 層次遍歷知識點：第七章解析第七章第三節(jié)廣度優(yōu)先搜索5

7、 .（7分）圖的鄰接矩陣表示法適用于表示（C）。A. 有向圖B. 無向圖C. 稠密圖D. 稀疏圖知識點：第七章解析第七章第二節(jié)數(shù)組表示法6 .（7分）設(shè)輸入序列是1、2、3、n,經(jīng)過棧的作用后輸出序列的第一個元素是n,則輸出序列中第i個輸出元素是（C）。A. n-IB. n-1-IC. n+1-ID.不能確定知識點：第三章解析第三章第一節(jié)棧的表示和實現(xiàn)7 .（7分）順序查找適用于存儲結(jié)構(gòu)為（B）的線性表。A. 散列B. 順序或者鏈式C. 壓縮D. 索引知識點：第九章解析第九章第一節(jié)順序表的查找8 .（7分）線性表若采用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中的可用存儲單元的地址?（D）。A. 必須連續(xù)B.

8、部分連續(xù)C. 一定不連續(xù)D. 可連續(xù)可不連續(xù)知識點：第二章解析第二章第三節(jié)綜合題目9 .（7分）設(shè)無向圖G中有n個頂點，則該無向圖的最小生成樹上有（B）條邊。A. nB. n-1C. 2nD. 2n-1知識點：第七章解析第七章第四節(jié)最小生成樹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)

9、二、判斷。1 .(6分)二叉排序樹上左子樹上所有結(jié)點的值均小于它的根結(jié)點的值。答案：正確。解析第九章第二節(jié)二叉排序樹和平衡二叉樹2 .(6分)常用的圖的遍歷方法有深度優(yōu)先遍歷和廣度優(yōu)先遍歷。答案：正確。解析第七章第三節(jié)綜合題目3 .（6分）數(shù)據(jù)項是數(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開

10、始對完全二叉樹進行順序編號，則編號為i結(jié)點的左孩子結(jié)點的編號為（B）。A. 2i+1B. 2iC. i/2D.2i-1知識點：第六章解析第六章第六節(jié)二叉樹的性質(zhì)2 .（7分）若采用孩子兄弟鏈表作為樹的存儲結(jié)構(gòu)，則樹的先根遍歷應(yīng)采用二叉樹的（B）。A. 層次遍歷B. 先序遍歷C. 中序遍歷D. 后序遍歷知識點：第六章解析第六章第四節(jié)樹的存儲結(jié)構(gòu)3 .（7分）若有18個元素的有序表存放在一維數(shù)組A19中，第一個元素放A1中，現(xiàn)進行二分查找，則查找A3的比較序列的下標依次為（D）。A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，3知識點：第九章解析第九章第一節(jié)有序表的查找4 .

11、（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ù)域，指針域知識點：第二章解析第二章第三節(jié)線性鏈表則后序遍歷該6 .（7分）設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD叉樹得到序列為（A）。A. BADCB. BCDAC. CDABD. CBDA知識點：第六章解析第六章第三節(jié)遍歷二叉樹A）7 .（7分）序列278、109、930經(jīng)過一趟基數(shù)排序后結(jié)果為（A. 930

12、、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分）已知一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。答案：錯誤。解析第六章第三