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

1、數(shù)據(jù)結(jié)構(gòu)課程作業(yè)_a交卷時間：2017-08-09 10:08:51一、單選題 1. (7分)設(shè)有一個二維數(shù)組amn，假設(shè)a00存放位置在644(10)，a22存放位置在676(10)，每個元素占一個空間，問a33(10)存放在什么位置？腳注(10)表示用10進制表示。 a. 688 b. 678 c. 692 d. 696 糾錯 得分： 7 知識點： 第五章 展開解析 答案 c 解析 第五章第二節(jié)綜合題目 2. (7分)若有18個元素的有序表存放在一維數(shù)組a19中，第一個元素放a1中，現(xiàn)進行二分查找，則查找a3的比較序列的下標依次為( ) a. 1，2，3 b. 9，5，2，3 c. 9，5

2、，3 d. 9，4，2，3 糾錯 得分： 0 知識點： 第九章 展開解析 答案 d 解析 第九章第一節(jié)有序表的查找 3. (7分)設(shè)某完全無向圖中有n個頂點，則該完全無向圖中有（ ）條邊。 a. n(n-1)/2 b. n(n-1) c. n2 d. n2-1 糾錯 得分： 7 知識點： 第七章 展開解析 答案 a 解析 第七章第一節(jié)綜合題目 4. (7分)若在任意一棵二叉樹中，有n0個葉子結(jié)點，有n2個度為2的結(jié)點，則：n0=_ a. n2+1 b. n2-1 c. n2+2 d. n2-2 糾錯 得分： 7 知識點： 第六章 展開解析 答案 a 解析 第六章第二節(jié)二叉樹的性質(zhì) 5. (7分

3、)棧的插入和刪除操作在（ ）進行。 a. 棧頂 b. 棧底 c. 任意位置 d. 指定位置 糾錯 得分： 7 知識點： 第三章 展開解析 答案 a 解析 第三章第一節(jié)棧的表示和實現(xiàn) 6. (7分)設(shè)有序表中有1000個元素，則用二分查找查找元素x最多需要比較（ ）次。 a. 25 b. 10 c. 7 d. 1 糾錯 得分： 7 知識點： 第九章 展開解析 答案 b 解析 第九章第一節(jié)有序表的查找 7. (7分)設(shè)某棵二叉樹的高度為10，則該二叉樹上葉子結(jié)點最多有（ ）。 a. 20 b. 256 c. 512 d. 1024 糾錯 得分： 7 知識點： 第六章 展開解析 答案 c 解析 第六

4、章第六節(jié)二叉樹的性質(zhì) 8. (7分)線性表的順序存儲結(jié)構(gòu)是一種?的存儲結(jié)構(gòu) a. 隨機存取 b. 順序存取 c. 索引存取 d. 散列存取 糾錯 得分： 7 知識點： 第二章 展開解析 答案 a 解析 第二章第二節(jié)綜合題目 9. (7分)對完全二叉樹敘述正確的是 a. 完全二叉樹就是滿二叉樹 b. 完全二叉樹和滿二叉樹編號不對應(yīng) c. 完全二叉樹同一層上左子樹未滿不會有右子樹 d. 以上都不正確 糾錯 得分： 7 知識點： 第六章 展開解析 答案 c 解析 第六章第二節(jié)二叉樹的性質(zhì) 10. (7分)設(shè)某強連通圖中有n個頂點，則該強連通圖中至少有（ ）條邊。 a. n(n-1) b. n+1 c

5、. n d. n(n+1) 糾錯 得分： 7 知識點： 第七章 展開解析 答案 c 解析 第七章第一節(jié)綜合題目 二、判斷 1. (6分)哈希表不需要進行比較便可以直接取得所查記錄糾錯 得分： 6 知識點： 第九章 展開解析 答案 正確 解析 第九章第三節(jié)綜合題目 2. (6分)直接插入排序是一種最簡單的排序方法糾錯 得分： 6 知識點： 第十章 展開解析 答案 正確 解析 第十章第二節(jié)直接插入排序 3. (6分)分塊查找的平均查找長度不僅與索引表的長度有關(guān)，而且與塊的長度有關(guān)。（ ）糾錯 得分： 6 知識點： 第九章 展開解析 答案 正確 解析 第九章第一節(jié)索引順序表的查找 4. (6分)數(shù)據(jù)

6、的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機內(nèi)的實際的存儲形式糾錯 得分： 6 知識點： 第一章 展開解析 答案 正確 解析 第一章第二節(jié)物理結(jié)構(gòu) 5. (6分)當向二叉排序樹中插入一個結(jié)點，則該結(jié)點一定成為葉子結(jié)點。（ ）糾錯 得分： 6 知識點： 第九章 收起解析 答案 正確 解析 第九章第二節(jié)二叉排序樹和平衡二叉樹 數(shù)據(jù)結(jié)構(gòu)課程作業(yè)_b交卷時間：2017-08-09 10:25:50一、單選題 1. (7分)若有18個元素的有序表存放在一維數(shù)組a19中，第一個元素放a1中，現(xiàn)進行二分查找，則查找a3的比較序列的下標依次為( ) a. 1，2，3 b. 9，5，2，3 c. 9，5，3 d. 9，4，2，3

7、 糾錯 得分： 7 知識點： 第九章 展開解析 答案 d 解析 第九章第一節(jié)有序表的查找 2. (7分)按照二叉樹的定義，有三個結(jié)點的二叉樹有_種 a. 2 b. 3 c. 4 d. 5 糾錯 得分： 7 知識點： 第六章 展開解析 答案 d 解析 第六章第二節(jié)二叉樹的定義 3. (7分)廣義表（a）,a）的表頭是_ a. a b. b c. (a) d. (a) 糾錯 得分： 0 知識點： 第五章 展開解析 答案 c 解析 第五章第四節(jié)綜合題目 4. (7分)設(shè)某棵二叉樹的中序遍歷序列為abcd，前序遍歷序列為cabd，則后序遍歷該二叉樹得到序列為（ ）。 a. badc b. bcda c

8、. cdab d. cbda 糾錯 得分： 7 知識點： 第六章 展開解析 答案 a 解析 第六章第三節(jié)遍歷二叉樹 5. (7分)數(shù)據(jù)結(jié)構(gòu)是一門研究？的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和運算等的學科 a. 數(shù)值 b. 非數(shù)值 c. 字符 d. 數(shù)字 糾錯 得分： 0 知識點： 第一章 展開解析 答案 b 解析 第一章第一節(jié)綜合題目 6. (7分)圖的廣度優(yōu)先遍歷算法類似于二叉樹的_ a. 先序遍歷 b. 中序遍歷 c. 后序遍歷 d. 層次遍歷 糾錯 得分： 7 知識點： 第七章 展開解析 答案 d 解析 第七章第三節(jié)廣度優(yōu)先搜索 7. (7分)設(shè)一棵完全二叉樹中有65個結(jié)點，

9、則該完全二叉樹的深度為（ ）。 a. 8 b. 7 c. 6 d. 5 糾錯 得分： 7 知識點： 第六章 展開解析 答案 b 解析 第六章第六節(jié)二叉樹的性質(zhì) 8. (7分)設(shè)用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作（ ）。 a. 必須判別棧是否為滿 b. 必須判別棧是否為空 c. 判別棧元素的類型 d. 對棧不作任何判別 糾錯 得分： 7 知識點： 第三章 展開解析 答案 b 解析 第三章第一節(jié)綜合題目 9. (7分)設(shè)一組初始記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90，115，134),則利用二分法查找關(guān)鍵字90需要比較的關(guān)鍵字個數(shù)為（ ）。 a. 1 b. 2 c.

10、3 d. 4 糾錯 得分： 7 知識點： 第九章 展開解析 答案 b 解析 第九章第一節(jié)有序表的查找 10. (7分)設(shè)二叉排序樹上有n個結(jié)點，則在二叉排序樹上查找結(jié)點的平均時間復雜度為（ ）。 a. o(n) b. o(n2) c. o(nlog2n) d. o(1og2n) 糾錯 得分： 7 知識點： 第九章 展開解析 答案 d 解析 第九章第二節(jié)二叉排序樹和平衡二叉樹 二、判斷 1. (6分)設(shè)一棵樹t可以轉(zhuǎn)化成二叉樹bt，則二叉樹bt中一定沒有右子樹。（ ）糾錯 得分： 6 知識點： 第六章 展開解析 答案 正確 解析 第六章第四節(jié)森林與二叉樹的轉(zhuǎn)換 2. (6分)如果兩個關(guān)鍵字的值不

11、等但哈希函數(shù)值相等，則稱這兩個關(guān)鍵字為同義詞。（ ）糾錯 得分： 6 知識點： 第九章 展開解析 答案 正確 解析 第九章第三節(jié)什么是哈希表 3. (6分)棧是后進先出的線性表糾錯 得分： 6 知識點： 第三章 展開解析 答案 正確 解析 第三章第一節(jié)綜合題目 4. (6分)二維數(shù)組和多維數(shù)組均不是特殊的線性結(jié)構(gòu)。（ ）糾錯 得分： 6 知識點： 第五章 展開解析 答案 錯誤 解析 第五章綜合題目 5. (6分)棧和隊列都是操作受限的線性表糾錯 得分： 6 知識點： 第三章 收起解析 答案 正確 解析 第三章綜合題目 數(shù)據(jù)結(jié)構(gòu)課程作業(yè)_c交卷時間：2017-08-09 10:36:47一、單選

12、題 1. (7分)對完全二叉樹敘述正確的是 a. 完全二叉樹就是滿二叉樹 b. 完全二叉樹和滿二叉樹編號不對應(yīng) c. 完全二叉樹同一層上左子樹未滿不會有右子樹 d. 以上都不正確 糾錯 得分： 7 知識點： 第六章 展開解析 答案 c 解析 第六章第二節(jié)二叉樹的性質(zhì) 2. (7分)線性表是 a. 有限序列，可以為空 b. 有限序列，不能為空 c. 無限序列，可以為空 d. 無限序列，不能為空 糾錯 得分： 7 知識點： 第二章 展開解析 答案 a 解析 第二章第一節(jié)綜合題目 3. (7分)下面關(guān)于線性表的敘述錯誤的是（ ）。 a. 線性表采用順序存儲必須占用一片連續(xù)的存儲空間 b. 線性表采用

13、鏈式存儲不必占用一片連續(xù)的存儲空間 c. 線性表采用鏈式存儲便于插入和刪除操作的實現(xiàn) d. 線性表采用順序存儲便于插入和刪除操作的實現(xiàn) 糾錯 得分： 7 知識點： 第二章 展開解析 答案 d 解析 第二章綜合題目 4. (7分)設(shè)某有向圖中有n個頂點，則該有向圖對應(yīng)的鄰接表中有（ ）個表頭結(jié)點。 a. n-1 b. n c. n+1 d. 2n-1 糾錯 得分： 7 知識點： 第七章 展開解析 答案 b 解析 第七章第二節(jié)鄰接表 5. (7分)二路歸并排序的時間復雜度為（ ）。 a. o(n) b. o(n2) c. o(nlog2n) d. o(1og2n) 糾錯 得分： 7 知識點： 第十

14、章 展開解析 答案 c 解析 第十章第五節(jié)綜合題目 6. (7分)兩個字符串相等的充要條件是（ ）。 a. 兩個字符串的長度相等 b. 兩個字符串中對應(yīng)位置上的字符相等 c. 同時具備(a)和(b)兩個條件 d. 以上答案都不對 糾錯 得分： 0 知識點： 第四章 展開解析 答案 c 解析 第四章第一節(jié)字符串相等 7. (7分)棧的插入和刪除操作在（ ）進行。 a. 棧頂 b. 棧底 c. 任意位置 d. 指定位置 糾錯 得分： 7 知識點： 第三章 展開解析 答案 a 解析 第三章第一節(jié)棧的表示和實現(xiàn) 8. (7分)設(shè)某有向圖的鄰接表中有n個表頭結(jié)點和m個表結(jié)點，則該圖中有（ ）條有向邊。

15、a. n b. n-1 c. m d. m-1 糾錯 得分： 7 知識點： 第七章 展開解析 答案 c 解析 第七章第二節(jié)鄰接表 9. (7分)設(shè)一組初始記錄關(guān)鍵字序列為(50，40，95，20，15，70，60，45)，則以增量d=4的一趟希爾排序結(jié)束后前4條記錄關(guān)鍵字為（ ）。 a. 40，50，20，95 b. 15，40，60，20 c. 15，20，40，45 d. 45，40，15，20 糾錯 得分： 7 知識點： 第十章 展開解析 答案 b 解析 第十章第二節(jié)希爾排序 10. (7分)設(shè)有以下四種排序方法，則（ ）的空間復雜度最大。 a. 冒泡排序 b. 快速排序 c. 堆排序

16、d. 希爾排序 糾錯 得分： 7 知識點： 第十章 展開解析 答案 b 解析 第十章綜合題目 二、判斷 1. (6分)森林的先序遍歷與其對應(yīng)的二叉樹的中序遍歷對應(yīng)糾錯 得分： 0 知識點： 第六章 展開解析 答案 錯誤 解析 第六章第四節(jié)數(shù)和森林的遍歷 2. (6分)帶權(quán)無向圖的最小生成樹是唯一的。（ ）糾錯 得分： 0 知識點： 第七章 展開解析 答案 錯誤 解析 第七章第四節(jié)最小生成樹 3. (6分)算法和程序沒有區(qū)別糾錯 得分： 6 知識點： 第一章 展開解析 答案 錯誤 解析 第一章第四節(jié)綜合題目 4. (6分)設(shè)某堆中有n個結(jié)點，則在該堆中插入一個新結(jié)點的時間復雜度為o(log2n)

17、。（ ）糾錯 得分： 6 知識點： 第十章 展開解析 答案 正確 解析 第十章第四節(jié)堆排序 5. (6分)設(shè)一棵樹t可以轉(zhuǎn)化成二叉樹bt，則二叉樹bt中一定沒有右子樹。（ ）糾錯 得分： 6 知識點： 第六章 收起解析 答案 正確 解析 第六章第四節(jié)森林與二叉樹的轉(zhuǎn)換 數(shù)據(jù)結(jié)構(gòu)課程作業(yè)_a交卷時間：2017-09-08 19:21:11一、單選題1.(7分)設(shè)帶有頭結(jié)點的單向循環(huán)鏈表的頭指針變量為head，則其判空條件是（ ）。 a.head=0 b.head-next=0 c.head-next=head d.head!=0糾錯得分：7知識點：第二章展開解析2.(7分)for (j=1; j

18、=n; +j) s=s+1; a.o(n) b.o(1) c.o(n2) d.o(n3)糾錯得分：0知識點：第一章展開解析3.(7分)一個隊列的入隊序列是1、2、3、4，則隊列的首次輸出元素是_ a.1 b.2 c.3 d.4糾錯得分：0知識點：第三章展開解析4.(7分)將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復雜度為（ ） a.o(1) b.o(n) c.o(m) d.o(m+n)糾錯得分：7知識點：第二章展開解析5.(7分)設(shè)某棵二叉樹的高度為10，則該二叉樹上葉子結(jié)點最多有（ ）。 a.20 b.256 c.512 d.1024糾錯得分：7知識點：第六章展開解析6.(7分

19、)鏈式隊列q為空的判定條件 a.q.front=q.rear b.q.front=q c.q =q.rear d.沒有正確答案糾錯得分：0知識點：第三章展開解析7.(7分)數(shù)據(jù)的最小單位是（ ）。 a.數(shù)據(jù)項 b.數(shù)據(jù)類型 c.數(shù)據(jù)元素 d.數(shù)據(jù)變量糾錯得分：7知識點：第一章展開解析8.(7分)設(shè)一棵二叉樹的深度為k，則該二叉樹中最多有（ ）個結(jié)點。 a.2k-1 b.2k c.2k-1 d.2k-1糾錯得分：7知識點：第六章展開解析9.(7分)由權(quán)值分別為11，8，6，2，5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（ ） a.24 b.71 c.48 d.53糾錯得分：7知識點：第六章

20、展開解析10.(7分)設(shè)一組初始記錄關(guān)鍵字序列為(50，40，95，20，15，70，60，45)，則以增量d=4的一趟希爾排序結(jié)束后前4條記錄關(guān)鍵字為（ ）。 a.40，50，20，95 b.15，40，60，20 c.15，20，40，45 d.45，40，15，20糾錯得分：7知識點：第十章展開解析二、判斷1.(6分)線性結(jié)構(gòu)只能用順序存儲糾錯得分：6知識點：第三章展開解析2.(6分)算法和程序沒有區(qū)別糾錯得分：6知識點：第一章展開解析3.(6分)可以用隊列實現(xiàn)數(shù)值轉(zhuǎn)換算法糾錯得分：0知識點：第三章展開解析4.(6分)哈夫曼樹中沒有度數(shù)為1的結(jié)點。（ ）糾錯得分：6知識點：第六章展開解析

21、5.(6分)帶權(quán)無向圖的最小生成樹是唯一的。（ ）糾錯得分：6知識點：第七章收起解析答案錯誤解析第七章第四節(jié)最小生成樹數(shù)據(jù)結(jié)構(gòu)課程作業(yè)_b交卷時間：2017-09-08 19:51:39一、單選題1.(7分)設(shè)某無向圖有n個頂點，則該無向圖的鄰接表中有（ ）個表頭結(jié)點。 a.2n b.n c.n/2 d.n(n-1)糾錯得分：7知識點：第七章展開解析2.(7分)設(shè)某無向圖中有n個頂點e條邊，則建立該圖鄰接表的時間復雜度為（ ）。 a.o(n+e) b.o(n2) c.o(ne) d.o(n3)糾錯得分：7知識點：第七章展開解析3.(7分)下面關(guān)于線性表的敘述錯誤的是（ ）。 a.線性表采用順序

22、存儲必須占用一片連續(xù)的存儲空間 b.線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間 c.線性表采用鏈式存儲便于插入和刪除操作的實現(xiàn) d.線性表采用順序存儲便于插入和刪除操作的實現(xiàn)糾錯得分：7知識點：第二章展開解析4.(7分)設(shè)一組初始記錄關(guān)鍵字序列為(345，253，674，924，627)，則用基數(shù)排序需要進行（ ）趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。 a.3 b.4 c.5 d.8糾錯得分：7知識點：第十章展開解析5.(7分)由兩個棧共享一個向量空間的好處是：（ ） a.減少存取時間，降低下溢發(fā)生的機率 b.節(jié)省存儲空間，降低上溢發(fā)生的機率 c.減少存取時間，降低上溢發(fā)生的機率

23、 d.節(jié)省存儲空間，降低下溢發(fā)生的機率糾錯得分：7知識點：第三章展開解析6.(7分)設(shè)某有向圖的鄰接表中有n個表頭結(jié)點和m個表結(jié)點，則該圖中有（ ）條有向邊。 a.n b.n-1 c.m d.m-1糾錯得分：7知識點：第七章展開解析7.(7分)設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20，15，14，18，21，36，40，10)，則以20為基準記錄的一趟快速排序結(jié)束后的結(jié)果為( )。 a.10，15，14，18，20，36，40，21 b.10，15，14，18，20，40，36，21 c.10，15，14，20，18，40，36，2l d.15，10，14，18，20，36，40，21糾錯得分：0知

24、識點：第十章展開解析8.(7分)設(shè)某強連通圖中有n個頂點，則該強連通圖中至少有（ ）條邊。 a.n(n-1) b.n+1 c.n d.n(n+1)糾錯得分：7知識點：第七章展開解析9.(7分)設(shè)某棵二叉樹中有2000個結(jié)點，則該二叉樹的最小高度為（ ）。 a.9 b.10 c.11 d.12糾錯得分：7知識點：第六章展開解析10.(7分)在二叉排序樹中插入一個關(guān)鍵字值的平均時間復雜度為（ ）。 a.o(n) b.o(1og2n) c.o(nlog2n) d.o(n2)糾錯得分：7知識點：第九章展開解析二、判斷1.(6分)層次遍歷初始堆可以得到一個有序的序列。（ ）糾錯得分：6知識點：第十章展開

25、解析2.(6分)一個有n個頂點的有向圖的邊數(shù)e最多為e=n(n-1)糾錯得分：6知識點：第七章展開解析3.(6分)常用的圖的遍歷方法有深度優(yōu)先遍歷和廣度優(yōu)先遍歷糾錯得分：0知識點：第七章展開解析4.(6分)棧是限定在表尾進行插入或刪除操作的線性表糾錯得分：6知識點：第三章展開解析5.(6分)稀疏矩陣的壓縮存儲可以用一個三元組表來表示稀疏矩陣中的非0元素。（ ）糾錯得分：6知識點：第五章收起解析答案正確解析第五章第三節(jié)稀疏矩陣數(shù)據(jù)結(jié)構(gòu)課程作業(yè)_c交卷時間：2017-09-08 20:11:29一、單選題1.(7分)棧的插入和刪除操作在（ ）進行。 a.棧頂 b.棧底 c.任意位置 d.指定位置糾錯得分：7知識點：第三章展開解析2.(7分)堆的形狀是一棵 a.二叉排序樹 b.滿二叉樹 c.完全二叉樹 d.一般的二叉樹糾錯得分：7知識點：第十章展開解析3.(7分)時間復雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為o(nlog2n)的是（ ）。 a.堆排序