數(shù)據(jù)結(jié)構(gòu)與算法在線作業(yè)-2015

1、單選題 1.【第1章第2節(jié)】數(shù)據(jù)結(jié)構(gòu)課程主要研究以下三方面的內(nèi)容，它們是_D_。 A 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型 B 數(shù)據(jù)元素、數(shù)據(jù)類型、算法實(shí)現(xiàn) C 數(shù)據(jù)元素、數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu) D 數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算 單選題 2.【第1章第2節(jié)】在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的_C_結(jié)構(gòu)。 A 存儲 B 物理 C 邏輯 D 物理與存儲 判斷題 3.【第1章第2節(jié)】邏輯結(jié)構(gòu)相同時物理結(jié)構(gòu)也應(yīng)該相同。 正確 錯誤 單選題 4.【第1章第3節(jié)】設(shè)某二維數(shù)組A1.n，1.n，則在該數(shù)組中用順序查找法查找一個元素的時間復(fù)雜性的量級為_D_。 A O（log2n） B O

2、(n) C O(nlog2n) D O(n2) 單選題 D5.【第1章第3節(jié)】計(jì)算機(jī)算法是指_D_。 A 計(jì)算方法 B 排序方法 C 調(diào)度方法 D 解決問題的有限運(yùn)算序列 判斷題 6.【第1章第3節(jié)】所謂時間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時間的一個上界 正確 錯誤 單選題 7.【第3章第2節(jié)】向一個有115個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動_C_個元素。 A 115 B 114 C 58 D 57 單選題 8.【第3章第2節(jié)】在長度為n 的雙鏈表中某結(jié)點(diǎn)（已知其地址）之前，插入一個新結(jié)點(diǎn)的時間復(fù)雜度是_C_ 。 A O(n) B O(log2n) C O(1) D

3、 O(n2) 單選題 9.【第3章第2節(jié)】在一個長度為n的順序表中，在第i個元素（1<=i<=n）之前插入一個新元素時需向后移動_D_個元素。 A 1 B n-i C n-i-1 D n-i+1 單選題 10.【第3章第2節(jié)】在一個具有n個結(jié)點(diǎn)的有序單鏈表中，插入一個新的結(jié)點(diǎn)并使之仍然有序的時間復(fù)雜度是_A_。 A O(n) B O(log2n) C O(1) D O(n2) 單選題 11.【第3章第2節(jié)】線性表按鏈?zhǔn)椒绞酱鎯r，每個結(jié)點(diǎn)的存儲包括_B_兩部分。 A 數(shù)據(jù)值與符號 B 數(shù)據(jù)與指針 C 數(shù)據(jù)與表名 D 數(shù)據(jù)項(xiàng)與符號 單選題 B12.【第3章第2節(jié)】線性表采用鏈?zhǔn)酱鎯r

4、，其地址_C_。 A 必須是連續(xù)的 B 必須是不連續(xù)的 C 連續(xù)與否均可 D 部分地址必須是連續(xù)的 單選題 13.【第3章第2節(jié)】若要求能快速地實(shí)現(xiàn)在鏈表的末尾插入和刪除結(jié)點(diǎn)的運(yùn)算，則選擇_B_最合適。 A 單鏈表 B 帶尾指針的單循環(huán)鏈表 C 雙鏈表 D 雙循環(huán)鏈表 單選題 14.【第3章第2節(jié)】順序表的特點(diǎn)是_B_。 A 邏輯上相鄰的結(jié)點(diǎn)其物理位置不相鄰 B 邏輯上相鄰的結(jié)點(diǎn)其物理位置亦相鄰 C 順序表不是隨機(jī)存儲結(jié)構(gòu) D 在順序表中插入和刪除操作比在鏈表上方便 單選題 15.【第3章第2節(jié)】鏈表不具有的特點(diǎn)是_A_。 A 可隨機(jī)訪問任一元素 B 插入和刪除不需要移動元素 C 不必事先估計(jì)

5、存儲空間 D 所需空間和線性表長度成正比 單選題 16.【第3章第2節(jié)】對順序存儲的線性表，設(shè)其長度為n，且在任何位置上插入或刪除操作都是等概率的。則插入一個元素時平均要移動表中的_A_個元素。 A n/2 B (n+1)/2 C (n-1)/2 D n 單選題 17.【第3章第2節(jié)】帶頭結(jié)點(diǎn)的單鏈表Head為空表的判定條件是_B_。 A Head->next=Head B Head->next=NULL C Head!=NULL D Head=NULL 判斷題 18.【第3章第2節(jié)】在n個元素的順序表中刪除第i個元素，需要移動n-i個元素。 正確 錯誤 單選題 19.【第3章第3

6、節(jié)】若某堆棧的輸入序列為1，2，3，n-1，n，輸出序列的第1個元素為n，則第i個輸出元素為_A_。 A n-i+l B n-i C i D 哪個元素?zé)o所謂 單選題 20.【第3章第3節(jié)】作進(jìn)棧操作時，應(yīng)先判斷棧是否為_B_。 A 空 B 滿 C 上溢 D 下溢 單選題 B21.【第3章第3節(jié)】當(dāng)字符序列 x5y 作為字符堆棧的輸入時，輸出長度為3的且可以作為C語言標(biāo)識符的個數(shù)是_A_。 A 3個 B 4個 C 5個 D 6個 單選題 22.【第3章第3節(jié)】棧結(jié)構(gòu)通常采用的兩種存儲結(jié)構(gòu)是_D_。 A 線性存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu) B 散列方式和索引方式 C 鏈表存儲結(jié)構(gòu)和數(shù)組 D 線性存儲結(jié)構(gòu)和

7、非線性存儲結(jié)構(gòu) 單選題 23.【第3章第3節(jié)】一個棧的進(jìn)棧序列是a,b,c,d,e, 則棧的不可能的出棧序列是_B_。 A edcba B dceab C decba D abcde 單選題 24.【第3章第3節(jié)】采用不帶尾指針的單鏈表方式表示一個棧，便于結(jié)點(diǎn)的插入與刪除。棧頂結(jié)點(diǎn)的插入與刪除通常在鏈表的_C_進(jìn)行。 A 任意位置 B 鏈表頭尾兩端 C 鏈表頭一端 D 鏈表尾一端 單選題 25.【第3章第3節(jié)】一個棧的入棧序列是a,b,c,d, 則下列序列中不可能的輸出序列是_D_。 A acbd B dcba C acdb D dbac 判斷題 D26.【第3章第3節(jié)】判斷順序儲存下堆棧s是

8、空的條件是s.top=0。 正確 錯誤 單選題 27.【第3章第4節(jié)】隊(duì)列的操作原則是_A_。 A 先進(jìn)先出 B 先進(jìn)后出 C 只能進(jìn)行插入 D 只能進(jìn)行刪除 單選題 28.【第3章第4節(jié)】判斷一個循環(huán)隊(duì)列是空隊(duì)列的條件是_A_。 A Q.rear=Q.front B Q.front=0 C Q.rear=0 D (Q.rear+1)%maxsize=Q.front 判斷題 A29.【第3章第4節(jié)】判斷順序儲存下隊(duì)列q是空的條件是q.front=q.rear。 正確 錯誤 單選題 30.【第4章第1節(jié)】在順序表2、5、7、10、14、15、18、23、35、41、52中，用二分法查找關(guān)鍵碼12

9、需做_C_次關(guān)鍵碼比較。 A 2 B 3 C 4 D 5 單選題 31.【第4章第1節(jié)】若用二分查找法取得的中間位置元素鍵值大于被查找值，說明被查找值位于中間值的前面，下次的查找區(qū)間為從原開始位置至_B_。 A 該中間位置 B 該中間位置1 C 該中間位置1 D 該中間位置2 單選題 32.【第4章第1節(jié)】對線性表進(jìn)行二分查找時，要求線性表必須_B_。 A 以順序方式存儲 B 以順序方式存儲且元素有序 C 以鏈?zhǔn)椒绞酱鎯?D 以鏈?zhǔn)椒绞酱鎯η以赜行?單選題 33.【第4章第2節(jié)】若由森林轉(zhuǎn)化得到的二叉樹是非空的二叉樹，則二叉樹形狀是_C_。 A 根結(jié)點(diǎn)無右子樹的二叉樹 B 根結(jié)點(diǎn)無左子樹的二

10、叉樹 C 根節(jié)點(diǎn)可能有左子樹和右子樹的二叉樹 D 各結(jié)點(diǎn)只有一個兒子的二叉樹 單選題 34.【第4章第2節(jié)】樹最適合用來表示_C_。 A 有序數(shù)據(jù)元素 B 無序數(shù)據(jù)元素 C 元素之間具有分支層次關(guān)系的數(shù)據(jù) D 元素之間無聯(lián)系的數(shù)據(jù) 判斷題 35.【第4章第2節(jié)】任何一個森林都可以唯一地與一棵二叉樹對應(yīng)。 正確 錯誤 判斷題 36.【第4章第2節(jié)】n(n>0)個結(jié)點(diǎn)的樹有n-1條邊。 正確 錯誤 單選題 37.【第4章第3節(jié)】設(shè)深度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至多為_A_(注意C和D中h是指數(shù))。 A 2h-1 B 2(h-1) C 2*h-1 D

11、2*h 單選題 38.【第4章第3節(jié)】在某棵二叉樹的一種序列中，如果發(fā)現(xiàn)其中每一結(jié)點(diǎn)的左孩子均是其前趨，則可判斷定這種序列為中序序列。A A 正確 B 不正確 單選題 A39.【第4章第3節(jié)】設(shè)a,b為一棵二叉樹上的兩個結(jié)點(diǎn)，在中序遍歷時，a在b前的條件是_C_。 A a是b祖先 B a是b子孫 C a在b左方 D a在b右方 單選題 40.【第4章第3節(jié)】關(guān)于二叉樹的三種遍歷，下列說法正確的是_D_。 A 任意兩種遍歷序列都不可以唯一決定該二叉樹 B 任意兩種遍歷序列都可以唯一決定該二叉樹 C 先序遍歷序列和后序遍歷序列可以唯一決定該二叉樹 D 先序遍歷序列和中序遍歷序列可以唯一決定該二叉樹

12、 單選題 41.【第4章第3節(jié)】某非空二叉樹的前序序列和后序序列正好相反，則二叉樹一定是_A_的二叉樹。 A 空或只有一個結(jié)點(diǎn) B 高度等于其結(jié)點(diǎn)數(shù) C .任一結(jié)點(diǎn)無左孩子 D 任一結(jié)點(diǎn)無右孩子 單選題 42.【第4章第3節(jié)】如果某二叉樹的先序遍歷序列是abdcef，中序遍歷序列是dbaefc，則其后序遍歷序列是_D_。 A dbafec B fecdba C efcdba D dbfeca 單選題 43.【第4章第3節(jié)】樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵樹對應(yīng)的二叉樹。那么以下結(jié)論中_A_是

13、正確的。 A 樹的先根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同 B 樹的后根遍歷序列與其對應(yīng)的二叉樹的后序遍歷序列相同 C 樹的先根遍歷序列與其對應(yīng)的二叉樹的中序遍歷序列相同 D 以上都不對 單選題 A44.【第4章第3節(jié)】已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列是_D_。 A acbed B decab C deabc D cedba 單選題 45.【第4章第3節(jié)】設(shè)二叉樹根結(jié)點(diǎn)的層次為1，所有含有15個結(jié)點(diǎn)的二叉樹中，最小高度是_C_。 A 6 B 5 C 4 D 3 單選題 46.【第4章第3節(jié)】任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷的序

14、列中的相對次序_A_。 A 不發(fā)生變化 B 發(fā)生變化 C 不能確定 D 以上都不對 單選題 A47.【第4章第3節(jié)】設(shè)深度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為_A_(注意C和D中h為指數(shù))。 A 2h-1 B 2(h-1) C 2*h-1 D 2*h 判斷題 48.【第4章第3節(jié)】滿二叉樹一定是完全二叉樹，反之不然。 正確 錯誤 判斷題 49.【第4章第3節(jié)】任何二叉樹的葉子數(shù)都要比度為2的結(jié)點(diǎn)數(shù)多。 正確 錯誤 判斷題 50.【第4章第3節(jié)】由二叉樹的前序和中序遍歷序列可惟一構(gòu)造這棵二叉樹。 正確 錯誤 單選題 51.【第4章第4節(jié)】若構(gòu)造一棵具有n個結(jié)

15、點(diǎn)的二叉排序樹，最壞的情況下其深度不會超過_B_。 A n/2 B n C (n+1)/2 D n+1 判斷題 52.【第4章第4節(jié)】二叉排序樹一般用于查找某個元素。 正確 錯誤 判斷題 53.【第4章第4節(jié)】如果某二叉樹的左右子樹的高度差的絕對值不大于1，則一定是平衡二叉樹。 正確 錯誤 單選題 54.【第4章第6節(jié)】有m個葉子結(jié)點(diǎn)的Huffman樹所具有的結(jié)點(diǎn)總數(shù)為_B_。 A m+1 B 2m-1 C 2m D 2m+1 判斷題 55.【第4章第6節(jié)】序列12, 23, 15, 24, 22, 18, 16, 30, 27是一個堆。 正確 錯誤 判斷題 56.【第4章第6節(jié)】哈夫曼編碼使

16、一串文字的編碼長度最短。 正確 錯誤 判斷題 57.【第5章第1節(jié)】哈希表是用于查找的技術(shù)之一。 正確 錯誤 單選題 58.【第5章第2節(jié)】將10個元素散列到100000個單元的散列表中，則_C_產(chǎn)生沖突。 A 一定會 B 一定不會 C 仍可能會 判斷題 59.【第5章第2節(jié)】若散列表的裝載因子<1，則可避免沖突的產(chǎn)生。 正確 錯誤 單選題 60.【第5章第3節(jié)】設(shè)散列表長為14，散列函數(shù)是H(key)=key%11,表中已有數(shù)據(jù)的關(guān)鍵字為15，38，61，84共四個，現(xiàn)要將關(guān)鍵字為49的結(jié)點(diǎn)加到表中，用二次探測法解決沖突，則放入的位置是_D_。 A 8 B 3 C 5 D 9 單選題

17、61.【第6章第2節(jié)】具有5個頂點(diǎn)的有向完全圖有_C_條弧。 A 10 B 16 C 20 D 25 單選題 62.【第6章第2節(jié)】在一個無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的_C_倍。 A 1/2 B 1 C 2 D 4 判斷題 63.【第6章第2節(jié)】有向圖各頂點(diǎn)入度之和就等于邊的數(shù)量。 正確 錯誤 判斷題 64.【第6章第2節(jié)】無向圖各頂點(diǎn)度之和就等于邊的數(shù)量。 正確 錯誤 判斷題 65.【第6章第2節(jié)】樹可以看成是連通的圖。 正確 錯誤 判斷題 66.【第6章第2節(jié)】5個頂點(diǎn)的無向圖，若不連通，則最多可能有6條邊。 正確 錯誤 單選題 67.【第6章第3節(jié)】下面關(guān)于圖的存儲的敘述中，

18、哪一個是正確的？A A 用相鄰矩陣法存儲圖,占用的存儲空間數(shù)只與圖中結(jié)點(diǎn)個數(shù)有關(guān),而與邊數(shù)無關(guān) B 用相鄰矩陣法存儲圖,占用的存儲空間數(shù)只與圖中邊數(shù)有關(guān),而與結(jié)點(diǎn)個數(shù)無關(guān) C 用鄰接表法存儲圖，占用的存儲空間數(shù)只與圖中結(jié)點(diǎn)個數(shù)有關(guān)，而與邊數(shù)無關(guān) D 用鄰接表法存儲圖，占用的存儲空間數(shù)只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個數(shù)無關(guān) 單選題 68.【第6章第3節(jié)】鄰接表是圖的一種_B_。 A 順序存儲結(jié)構(gòu) B 鏈?zhǔn)酱鎯Y(jié)構(gòu) C 索引存儲結(jié)構(gòu) D 散列存儲結(jié)構(gòu) 單選題 69.【第6章第3節(jié)】對于一個具有n個頂點(diǎn)和e 條邊的無向圖，若采用鄰接表表示，鄰接表中所有結(jié)點(diǎn)總數(shù)是_B_。 A e/2 B 2e C e D

19、 n+e 單選題 70.【第6章第3節(jié)】設(shè)n個頂點(diǎn)e條邊的圖 G 用鄰接表存儲，則求每個頂點(diǎn)入度的時間復(fù)雜度為_B_。 A O(n) B O(n+e) C O(n*n) D O(n*e) 判斷題 71.【第6章第3節(jié)】用鄰接矩陣表示圖所用的存儲空間大小與圖的邊數(shù)成正比。 正確 錯誤 單選題 72.【第6章第4節(jié)】 如果無向圖G必須進(jìn)行二次廣度優(yōu)先搜索才能訪問其所有頂點(diǎn)，則下列說法中不正確的是_C_。 A G肯定不是完全圖 B G一定不是連通圖 C G中一定有回路 D G有2個連通分量 判斷題 73.【第6章第4節(jié)】連通圖的廣度優(yōu)先搜索中一般要采用隊(duì)列 來暫存剛訪問過的頂點(diǎn)。 正確 錯誤 判斷題

20、 74.【第6章第4節(jié)】圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷都包含了圖的全部頂點(diǎn)。 正確 錯誤 單選題 75.【第6章第5節(jié)】下列關(guān)于圖的生成樹的唯一性，正確的是_C_。 A 生成樹是唯一的 B 生成樹是不唯一的 C 生成樹是唯一性不確定 D 圖的生成樹有兩棵 單選題 C76.【第6章第5節(jié)】關(guān)于無向連通圖的最小生成樹的個數(shù)_B_。 A 一定有多棵 B 一定只有一棵 C 有一棵或多棵 D 可能不存在 單選題 77.【第7章第2節(jié)】一組記錄的排序碼為（20,29,11,74,35,3,8,56），則利用堆排序方法建立的初始(小頂)堆為_B_。 A 20,29,11,74,35,3,8,56 B 3,2

21、9,8,56,35,20,11,74 C 3,8,11,20,29,35,56,74 D 20,29,3,8,11,35,74,56 單選題 78.【第7章第3節(jié)】用某種排序方法對線性表(25,84,21,47,15,27,68,35,20)進(jìn)行排序時,元素序列的變化情況如下(1)20,15,21,25,47,27,68,35,84 (2)15,20,21,25,35,27,47,68,84 (3)15,20,21,25,27,35,47,68,84 則所采用的排序方法是_D_ 。 A 選擇排序 B 希爾排序 C 歸并排序 D 快速排序 判斷題 79.【第7章第3節(jié)】在某個實(shí)例的排序結(jié)果看出，值相同的兩個