數(shù)據(jù)結(jié)構(gòu)(第2版)-在線作業(yè)_C 答案

1、數(shù)據(jù)結(jié)構(gòu)（第2版）-在線作業(yè)_C 用戶名：W7最終成績：100.0 一 單項(xiàng)選擇題1. 設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)為：line=(D,R);D=d1,d2,d3,d4,d5,d6,d7,d8,d9,d10R=,試分析該數(shù)據(jù)結(jié)構(gòu)屬于哪種邏輯結(jié)構(gòu)？（ ）樹結(jié)構(gòu)線型邏輯結(jié)構(gòu)非線性邏輯結(jié)構(gòu)網(wǎng)絡(luò)結(jié)構(gòu)本題分值：5.0 用戶得分：5.0 用戶解答：線型邏輯結(jié)構(gòu) 知識(shí)點(diǎn)：1.2 基本概念和術(shù)語 2. 下面（ ）的時(shí)間復(fù)雜度最好。O(nlg(n)O(lg(n)O(n)O(n2)本題分值：5.0 用戶得分：5.0 用戶解答：O(lg(n) 知識(shí)點(diǎn)：1.3 C程序與例題 3. 在一個(gè)長度為n的順序存儲(chǔ)線性表中，當(dāng)在任何位置插

2、入或刪除一個(gè)元素的概率相等時(shí)，插入一個(gè)元素所需要移動(dòng)元素的平均個(gè)數(shù)為（ ），刪除一個(gè)元素需要移動(dòng)元素的平均個(gè)數(shù)為（ ）。n/2， (n-1)/2n， (n-2)/2n+1， n/2n-1， (n+1)/2本題分值：5.0 用戶得分：5.0 用戶解答：n/2， (n-1)/2 知識(shí)點(diǎn)：2.2 順序存儲(chǔ)結(jié)構(gòu)線性表 4. 設(shè)鏈表中指針p指向結(jié)點(diǎn)ai，指針q指向?qū)⒁迦氲男陆Y(jié)點(diǎn)x，若要將新結(jié)點(diǎn)插入到ai與ai+1之間，所需要進(jìn)行的操作順序?yàn)椋?），（ ）。q-next=p，p-next = qq-next=NULL，p-next = qq-next=p-next，p-next = qq-next=p-

3、next，p-next =p-next-next本題分值：5.0 用戶得分：5.0 用戶解答：q-next=p-next，p-next = q 知識(shí)點(diǎn)：2.3 鏈接存儲(chǔ)結(jié)構(gòu)線性表 5. 一個(gè)隊(duì)列的入隊(duì)序列為 1,2,3,4，則隊(duì)列的輸出序列是（ ）。1432123443213241本題分值：5.0 用戶得分：5.0 用戶解答：1234 知識(shí)點(diǎn)：3.1 順序存儲(chǔ)結(jié)構(gòu)隊(duì)列 6. 假設(shè)以I和O分別表示入棧和出棧操作，棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由I和O組成的序列。指出合法的序列（ ）。IOOIOIIOIIIOIOIOIIIOOIOOIIOIOIIOIOIIOIIO本題分值：5

4、.0 用戶得分：5.0 用戶解答：IIIOOIOO 知識(shí)點(diǎn)：3.2 堆棧 7. 兩個(gè)具有n結(jié)點(diǎn)的（n1）二叉樹的先序遍歷序列和后序遍歷序列的結(jié)點(diǎn)順序正好相反，則該二叉樹除葉子結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)（ ）。僅有左子樹都有左右兩個(gè)子樹僅有右子樹僅有一個(gè)子樹本題分值：5.0 用戶得分：5.0 用戶解答：僅有右子樹 知識(shí)點(diǎn)：4.2 二叉樹 8. 利用3,7,5,4這四個(gè)值，作為葉子結(jié)點(diǎn)的權(quán)重，生成一棵Huffman樹，該樹的帶權(quán)路徑長度為（ ）。38553236本題分值：5.0 用戶得分：5.0 用戶解答：38 知識(shí)點(diǎn)：4.4 Huffman樹及應(yīng)用 9. G是一個(gè)非連通無向圖，共有28條邊，則該圖至少有（

5、 ）個(gè)頂點(diǎn)。8796本題分值：5.0 用戶得分：5.0 用戶解答：9 知識(shí)點(diǎn)：5.1 圖的基本術(shù)語與定義 10. 已知圖如下，若從頂點(diǎn)a出發(fā)，按深度優(yōu)先進(jìn)行遍歷，可能得到（ ）序列。a-b-c-d-e-fa-d-f-c-b-ea-c-e-f-d-ba-f-d-b-c-e本題分值：5.0 用戶得分：5.0 用戶解答：a-c-e-f-d-b 知識(shí)點(diǎn)：5.3 圖的遍歷 11. 采用分塊查找時(shí)，若線性表內(nèi)共有625個(gè)數(shù)據(jù)元素，查找每個(gè)元素的概率相同，假設(shè)采用順序查找來確定結(jié)點(diǎn)所在的數(shù)據(jù)塊，每塊設(shè)定的數(shù)據(jù)元素總數(shù)為（ ）最佳。62562510本題分值：5.0 用戶得分：5.0 用戶解答：25 知識(shí)點(diǎn)：6

6、.2 查找算法 12. 從二叉樹任意結(jié)點(diǎn)出發(fā)到根結(jié)點(diǎn)的路徑上所經(jīng)過的結(jié)點(diǎn)序列按其關(guān)鍵字有序，則該二叉樹是（ ）。Huffman樹堆二叉排序樹本題分值：5.0 用戶得分：5.0 用戶解答：堆 知識(shí)點(diǎn)：7 排序 13. 下列數(shù)據(jù)序列對(duì)中，（ ）是進(jìn)行一趟快速排序的結(jié)果。50,36,10,81,85,30,92,9530,50,36,10,85,92,81,9530,50,36,10,81,85,92,9536,10,81,85,30,50,92,95本題分值：5.0 用戶得分：5.0 用戶解答：30,50,36,10,81,85,92,95 知識(shí)點(diǎn)：7.4 快速排序 14. 不帶頭結(jié)點(diǎn)的鏈表L為空

7、的判定條件為（ ）。L！=NULLL=NULLL-next=NULLL-next=L本題分值：5.0 用戶得分：5.0 用戶解答：L=NULL 知識(shí)點(diǎn)：2.3 鏈接存儲(chǔ)結(jié)構(gòu)線性表 15. 在規(guī)定順序循環(huán)隊(duì)列一般狀態(tài)隊(duì)首指針指向第一個(gè)數(shù)據(jù)元素之前的空位，隊(duì)尾指針指向末尾元素的前提下，從一個(gè)順序循環(huán)隊(duì)列中出隊(duì)元素時(shí)，首先需要（ ）。后移隊(duì)首指針取出隊(duì)尾指針指定的元素前移隊(duì)首指針取出隊(duì)首指針指定的元素本題分值：5.0 用戶得分：5.0 用戶解答：后移隊(duì)首指針 知識(shí)點(diǎn)：3.1 順序存儲(chǔ)結(jié)構(gòu)隊(duì)列 16. 堆棧通常采用的兩種存儲(chǔ)結(jié)構(gòu)是（ ）。鏈表與集合方式順序與連接方式散列與索引方式線性與非線性結(jié)構(gòu)本題分

8、值：5.0 用戶得分：5.0 用戶解答：順序與連接方式 知識(shí)點(diǎn)：3.2 堆棧 17. 下述的二叉樹中只有（ ）不是完全二叉樹。本題分值：5.0 用戶得分：5.0 用戶解答： 知識(shí)點(diǎn)：4.2 二叉樹 18. 利用3,6,8,12,5,7作為葉子結(jié)點(diǎn)的權(quán)重，生成一棵Huffman樹，該樹的深度為（ ）。5436本題分值：5.0 用戶得分：5.0 用戶解答：4 知識(shí)點(diǎn)：4.4 Huffman樹及應(yīng)用 19. 從鄰接矩陣A= 可以看出，該圖共有（ ）個(gè)頂點(diǎn)，如果是有向圖則共有（ ）條邊，如果是無向圖則共有（ ）條邊。6，4，21，3，29，5，33，4，2本題分值：5.0 用戶得分：5.0 用戶解答：3，4，2 知識(shí)點(diǎn)：5.1 圖的基本術(shù)語與定義 20. 下列說法不正確的是（ ）。圖的深度優(yōu)先遍