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

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

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

4、解析第十章第三節(jié)綜合題目9 .（7分）設(shè)一組初始記錄關(guān)鍵字序列（5，2，6，3，8），以第一個(gè)記錄關(guān)鍵字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知識(shí)點(diǎn)：第十章解析第十章第三節(jié)綜合題目10 .（7分）設(shè)指針變量p指向單鏈表結(jié)點(diǎn)A,則刪除結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B需要的操作為（A）。A. p->next=p->next->nextB. p=p->nextC. p=p->next->nextD. p->next=p知識(shí)點(diǎn)：第二章解析第二章第三節(jié)線性鏈表二、判斷。1 .（6

5、分）棧和隊(duì)列都是操作受限的線性表。答案：正確。解析第三章綜合題目2 .（6分）分塊查找的平均查找長(zhǎng)度不僅與索引表的長(zhǎng)度有關(guān)，而且與塊的長(zhǎng)度有關(guān)。答案：正確。解析第九章第一節(jié)索引順序表的查找3 .（6分）數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位。答案：錯(cuò)誤。解析第一章第二節(jié)數(shù)據(jù)項(xiàng)4 .（6分）希爾排序是一種穩(wěn)定的排序方法。答案：錯(cuò)誤。解析第十章第二節(jié)希爾排序5 .（6分）二叉排序樹(shù)上左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值。答案：正確。解析第九章第二節(jié)二叉排序樹(shù)和平衡二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)課程作業(yè)_BC ）條邊。一"、單選題。1.（7分）設(shè)某強(qiáng)連通圖中有n個(gè)頂點(diǎn)，則該強(qiáng)連通圖中至少有（A. n(n-1)B. n

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

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

8、部分連續(xù)C. 一定不連續(xù)D. 可連續(xù)可不連續(xù)知識(shí)點(diǎn)：第二章解析第二章第三節(jié)綜合題目9 .（7分）設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)，則該無(wú)向圖的最小生成樹(shù)上有（B）條邊。A. nB. n-1C. 2nD. 2n-1知識(shí)點(diǎn)：第七章解析第七章第四節(jié)最小生成樹(shù)10 .(7分)設(shè)數(shù)組datam作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作后其頭指針front值為(D)。A. front=front+1B. front=(front+1)%(m-1)C. front=(front-1)%mD. front=(front+1)%m知識(shí)點(diǎn)：第三章解析第三章第四節(jié)隊(duì)列的順序表示和實(shí)現(xiàn)

9、二、判斷。1 .(6分)二叉排序樹(shù)上左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值。答案：正確。解析第九章第二節(jié)二叉排序樹(shù)和平衡二叉樹(shù)2 .(6分)常用的圖的遍歷方法有深度優(yōu)先遍歷和廣度優(yōu)先遍歷。答案：正確。解析第七章第三節(jié)綜合題目3 .（6分）數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位。答案：錯(cuò)誤。解析第一章第二節(jié)數(shù)據(jù)項(xiàng)4 .（6分）二維數(shù)組和多維數(shù)組均不是特殊的線性結(jié)構(gòu)。答案：錯(cuò)誤。解析第五章綜合題目5 .（6分）分塊查找的平均查找長(zhǎng)度不僅與索引表的長(zhǎng)度有關(guān)，而且與塊的長(zhǎng)度有關(guān)。答案：正確。解析第九章第一節(jié)索引順序表的查找數(shù)據(jù)結(jié)構(gòu)課程作業(yè)_C一"、單選題。1 .（7分）設(shè)按照從上到下、從左到右的順序從1開(kāi)

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

11、（7分）設(shè)有序表中有1000個(gè)元素，則用二分查找查找元素X最多需要比較（B）次。A.25B. 10C. 7D. 1知識(shí)點(diǎn)：第九章解析第九章第一節(jié)有序表的查找5 .（7分）單鏈表的結(jié)點(diǎn)包含和。（D）A. 結(jié)點(diǎn)域，符號(hào)域B. 數(shù)據(jù)域，符號(hào)域C. 結(jié)點(diǎn)域，指針域D. 數(shù)據(jù)域，指針域知識(shí)點(diǎn)：第二章解析第二章第三節(jié)線性鏈表則后序遍歷該6 .（7分）設(shè)某棵二叉樹(shù)的中序遍歷序列為ABCD，前序遍歷序列為CABD叉樹(shù)得到序列為（A）。A. BADCB. BCDAC. CDABD. CBDA知識(shí)點(diǎn)：第六章解析第六章第三節(jié)遍歷二叉樹(shù)A）7 .（7分）序列278、109、930經(jīng)過(guò)一趟基數(shù)排序后結(jié)果為（A. 930

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