b春北交《數(shù)據(jù)結(jié)構(gòu)》在線作業(yè)二.

1、精品文檔北交數(shù)據(jù)結(jié)構(gòu)在線作業(yè)二一、單選題（共38 道試題，共95 分。 ）1. 設(shè)循環(huán)隊(duì)列Q1.N-1 的頭尾指針為F， R，當(dāng)插入元素時(shí)尾指針R加 1，頭指針F 總是指在隊(duì)列中第一個(gè)元素的前一個(gè)位置，則隊(duì)列中元素計(jì)數(shù)為（）。. R-F. N- （ R-F）. （ R-F+N） %N. （ F-R+N） %N正確答案：2. 由兩個(gè)棧共享一個(gè)向量空間的好處是（） 。. 減少存取時(shí)間，降低下溢發(fā)生的機(jī)率. 節(jié)省存儲空間，降低上溢發(fā)生的機(jī)率. 減少存取時(shí)間，降低上溢發(fā)生的機(jī)率. 節(jié)省存儲空間，降低下溢發(fā)生的機(jī)率正確答案：3. 向一個(gè)有127 個(gè)元素的順序表中插入一個(gè)新元素并保持原來順序不變，平均要移

2、動(dòng)（）個(gè)元素。. 8. 63.5. 64 正確答案：4. 為了最快地對線性結(jié)構(gòu)的數(shù)據(jù)進(jìn)行某數(shù)據(jù)元素的讀取操作，則其數(shù)據(jù)存儲結(jié)構(gòu)宜采用（ ）順序存儲 鏈?zhǔn)酱鎯?索引存儲. 散列存儲正確答案：5. 鄰接表是圖的一種（） 。順序存儲結(jié)構(gòu) 鏈?zhǔn)酱鎯Y(jié)構(gòu) 索引存儲結(jié)構(gòu). 列存儲結(jié)構(gòu)正確答案：6. 具有 2000 個(gè)節(jié)點(diǎn)的二叉樹，其高度至少為（） . 9 . 10. 11. 12 正確答案：7. 具有 65 個(gè)結(jié)點(diǎn)的完全二叉樹其深度為（）正確答案：8. 當(dāng)利用大小為N 的數(shù)組順序存儲一個(gè)棧時(shí)，假定用top = = N 表示?？?，則退棧時(shí)，用（ ）語句修改top 指針。. top+ . top=0 . to

3、p-. top=N 正確答案：9. Sustring（'T STRUTUR' ， 5， 9）=（） 。. 'STRUTUR'. 'STUTUR' . 'T STRUTRU' . 'T' 正確答案：10. 數(shù)組中，每個(gè)元素的長度為3 個(gè)字節(jié)，行下標(biāo)I 從 1 到 8, 列下標(biāo) j 從 1 到 10，從首地址 S 開始連續(xù)存放在存儲器內(nèi)，存放該數(shù)組至少需要的單元數(shù)為（） 。. 80 . 100 . 240 . 270 正確答案： 11. 廣義表（ （）, ）的表頭是（）。. (). () 正確答案：12. 設(shè)無向圖的頂

4、點(diǎn)個(gè)數(shù)為n，則該圖最多有（）條邊。. n-1. n（n-1）/2. n（n+1）/2. 0正確答案：13. 對下面四個(gè)序列用快速排序的方法進(jìn)行排序，以序列的第一個(gè)元素為基礎(chǔ)進(jìn)行劃分在第一趟劃分過程中，元素移動(dòng)次數(shù)最多的序列是（） 。. 82 ， 75， 70， 16， 10， 90， 68， 2323 ， 10，16，70，82，75，68，9070 ， 75，68，23，10，16，90，8270 ， 75，82，90，23，16，10，68正確答案：14. 無向圖的鄰接矩陣是一個(gè)( ) 。. 對稱矩陣. 零矩陣. 上三角矩陣. 對角矩陣正確答案：15. 設(shè) F 是一個(gè)森林，是由F轉(zhuǎn)換得到的

5、二叉樹，F(xiàn) 中有 n 個(gè)非葉結(jié)點(diǎn)，則中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有()個(gè)。. n-1. n. n+1. n+2正確答案：16. 向二叉排序樹中插入一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為( ) 。. O(log 以 2 為底的 n). O(n). O(1). O(n*log2n)正確答案：17. 一個(gè)隊(duì)的入隊(duì)序列是1， 2， 3， 4 ，則隊(duì)列的輸出序列是() 。. 4，3，2，1. 1，2，3，4. 1，4，3，2. 3，2，1，4正確答案：18. 如果待排序序列中兩個(gè)數(shù)據(jù)元素具有相同的值，在排序后它們的位置發(fā)生顛倒，則稱該排序是不穩(wěn)定的。下列選項(xiàng)中，()就是不穩(wěn)定的排序方法。. 起泡排序. 歸并排序. 直接

6、插入法排序. 簡單選擇排序正確答案：19. 在線性表的散列存儲中，若用m表示散列表的長度，n 表示待散列存儲的元素的個(gè)數(shù)，則裝填因子等于()。. n/m. m/n. n/(n+m). m/(n+m)正確答案：20. 順序表中邏輯上相鄰的節(jié)點(diǎn)其物理位置也() 。. 一定相鄰. 不必相鄰. 按某種規(guī)律排列. 無要求正確答案：21. 計(jì)算機(jī)的算法是（） 。. 計(jì)算方法. 排序方法. 對特定問題求解步驟的一種描述. 調(diào)度算法正確答案：22. 每次從無序表中取出一個(gè)元素，把它插入到有序表中的適當(dāng)位置，此種排序方法叫做（）排序 . 插入. 交換. 選擇. 歸并正確答案：23. 算法分析的目的是（） 。.

7、找出數(shù)據(jù)結(jié)構(gòu)的合理性. 研究算法中的輸入和輸出的關(guān)系. 分析算法的效率以求改進(jìn). 分析算法的易讀性和文檔性正確答案：24. 二叉樹第i 層上至多有（）結(jié)點(diǎn)。. 2i. 2 的i 次方. 2i-1. 2 的i-1 次方正確答案：25. 鏈表不具有的特點(diǎn)是（） 。. 不必事先估計(jì)存儲空間. 可隨機(jī)訪問任一元素. 插入刪除不需要移動(dòng)元素. 所需空間與線性表長度成正比正確答案：26. 判定一個(gè)順序棧（最多元素為m個(gè)）為空的條件是（） 。. top 0. top m. top! 0. top! m正確答案：27. 采用順序查找方法查找長度為n 的線性表時(shí)，每個(gè)元素的平均長度為（ ） 。. n. n/2.

8、 (n+1)/2. (n-1)/2正確答案：28. 圖的深度優(yōu)先遍歷類似于二叉樹的() 。. 先序遍歷. 中序遍歷. 后序遍歷. 層次遍歷正確答案：29. 對 n 個(gè)記錄的文件進(jìn)行堆排序，最壞情況下的執(zhí)行時(shí)間為( ) 。. O(log2n). O(nlogn). O(n). O(n*n)正確答案：30. 在一個(gè)長度為n 的順序存儲的線性表中，向第i 個(gè)元素(1 i n+1 )之前插入一個(gè)新元素時(shí)，需要從前向后依次后移()個(gè)元素。. n-i. n-i+1. n-i-1. i正確答案：31. 串的邏輯結(jié)構(gòu)與()的邏輯結(jié)構(gòu)不同。. 線性表. 棧. 隊(duì)列. 樹正確答案：32. 若讓元素1， 2， 3

9、依次進(jìn)棧，則出棧次序不可能出現(xiàn)()種情況。. 3 ， 2， 1. 2 ， 1， 3. 3 ， 1， 2. 1 ， 3， 2正確答案：33. 一個(gè)有順序表有255 個(gè)對象，采用順序搜索法查表，平均搜索長度為() 。. 128. 127. 126. 255正確答案：34. 向順序棧中壓入新元素時(shí)，應(yīng)當(dāng)() 。. 先移動(dòng)棧頂指針，再存入元素. 先存入元素，再移動(dòng)棧頂指針. 先后次序無關(guān)緊要. 同時(shí)進(jìn)行正確答案：35. 下列數(shù)據(jù)組織形式中，（ ）的各個(gè)結(jié)點(diǎn)可以任意鄰接。. 集合. 樹形結(jié)構(gòu). 線性結(jié)構(gòu). 圖狀結(jié)構(gòu)正確答案：36. 順序查找法適合于存儲結(jié)構(gòu)為（）的線性表。. 散列表. 順序存儲或鏈接存儲

10、. 壓縮存儲. 索引存儲正確答案：37. 關(guān)于有向圖的鄰接表和逆鄰接表表示法，下列結(jié)論正確的是（）。. 用鄰接表表示法計(jì)算入度比較方便. 用鄰接表表示法計(jì)算入度和出度都方便. 用逆鄰接表表示法計(jì)算入度和出度都不方便. 用逆鄰接表表示法計(jì)算入度比計(jì)算出度方便正確答案：38. 計(jì)算機(jī)的算法必須具備輸入，輸出和（）五個(gè)特性。. 可行性，可移植性和可擴(kuò)充性. 可行性，確定性和有窮性. 確定性，有窮性和穩(wěn)定性. 易讀性，穩(wěn)定性和安全性正確答案：北交數(shù)據(jù)結(jié)構(gòu)在線作業(yè)二二、判斷題（共2 道試題，共5 分。 ）1. 線性表的順序存儲表示優(yōu)于鏈?zhǔn)酱鎯Ρ硎? 錯(cuò)誤. 正確正確答案：2. 線性表的邏輯順序與物理順序

11、總是一致的. 錯(cuò)誤. 正確正確答案：北交數(shù)據(jù)結(jié)構(gòu)在線作業(yè)二一、單選題（共38 道試題，共95 分。 ）1. 帶頭節(jié)點(diǎn)的單鏈表h 為空的判定條件（） 。. h=NULL. h->nxt=NULL. h->nxt=h. h!=h正確答案：2. 二叉樹上葉結(jié)點(diǎn)數(shù)等于（）。. 分支結(jié)點(diǎn)數(shù)加1.單分支結(jié)點(diǎn)數(shù)加1.雙分支結(jié)點(diǎn)數(shù)加1.雙分支結(jié)點(diǎn)數(shù)減1正確答案：3. 隊(duì)列的插入操作是在（）進(jìn)行。. 隊(duì)首. 隊(duì)尾. 隊(duì)前. 隊(duì)后正確答案：4. 鄰接表是圖的一種（） 。. 順序存儲結(jié)構(gòu). 鏈?zhǔn)酱鎯Y(jié)構(gòu). 索引存儲結(jié)構(gòu). 列存儲結(jié)構(gòu)正確答案：5. 由權(quán)值分別為3,6,7,2,5 的葉子結(jié)點(diǎn)生成一棵哈夫曼

12、樹，它的帶權(quán)路徑長度為（）. 23. 51. 53. 74正確答案：6. 順序查找法適合于存儲結(jié)構(gòu)為（）的線性表。. 散列表. 順序存儲或鏈接存儲. 壓縮存儲. 索引存儲正確答案：7. 在一個(gè)長度為n 的順序存儲的線性表中，向第 i 個(gè)元素 （ 1 i n+1 ） 之前插入一個(gè)新元素時(shí)，需要從前向后依次后移（）個(gè)元素。. n-i. n-i+1. n-i-1. i正確答案：8. 設(shè)有 50 行 60 列的二維數(shù)組5060 ，其元素長度為4 字節(jié)，按行優(yōu)先順序存儲，基地址為200，則元素1825 的存儲地址為（）。. 3700. 4376. 3900. 4620正確答案：9. 當(dāng)利用大小為N 的數(shù)

13、組順序存儲一個(gè)棧時(shí)，假定用top = = N 表示?？?，則退棧時(shí)，用（ ）語句修改top 指針。. top+. top=0. top-. top=N正確答案：10. 一個(gè)有順序表有255 個(gè)對象，采用順序搜索法查表，平均搜索長度為（） 。. 128. 127. 126. 255正確答案：11. 用某種排序方法隊(duì)線性表（25，84，21，47，15，27，68，35，20）進(jìn)行排序，元素序列變化如下：（1）25，84，21，47，15，27，68，35，20 （2）20，15，21，25，47，27，68，35，84 （3）15，20，21，25，35，27，47，68，84 （4）15，20，

14、21，25，27，35，47， 68， 84 所采用的排序方法是（） 。. 選擇排序. Shll 排序. 歸并排序. 快速排序正確答案：12. 在稀疏矩陣的帶行指針向量的鏈接存儲中，每個(gè)行單鏈表中的結(jié)點(diǎn)都具有相同的（）。. 行號. 列號. 元素值. 地址正確答案：13. 如果一個(gè)樹中，結(jié)點(diǎn)有3 個(gè)兄弟，而且為的雙親，則的度為（） 。. 1. 3. 4. 5正確答案：14. 鏈表不具有的特點(diǎn)是（） 。. 不必事先估計(jì)存儲空間. 可隨機(jī)訪問任一元素. 插入刪除不需要移動(dòng)元素. 所需空間與線性表長度成正比正確答案：）。則稱該15. 從一棵_樹刪除元素的過程中，若最終引起樹根結(jié)點(diǎn)的合并，則新樹高度是（

15、. 原樹高度加1. 原樹高度減1. 原樹高度. 不確定正確答案：16. 如果待排序序列中兩個(gè)數(shù)據(jù)元素具有相同的值，在排序后它們的位置發(fā)生顛倒，排序是不穩(wěn)定的。下列選項(xiàng)中，（）就是不穩(wěn)定的排序方法。. 起泡排序. 歸并排序. 直接插入法排序. 簡單選擇排序正確答案：17. 算法分析的兩個(gè)主要方面是（） 。. 空間復(fù)雜度和時(shí)間復(fù)雜度. 正確性和簡明性. 可讀性和文檔性. 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性正確答案：18. 線索化二叉樹中某結(jié)點(diǎn)，沒有左孩子的主要條件是（）。. ->Lhil=Null. ->ltg=1. ->Rhil=Null. ->ltg=0正確答案：19. 一個(gè)隊(duì)的入

16、隊(duì)序列是1， 2， 3， 4 ，則隊(duì)列的輸出序列是（） 。. 4，3，2，1. 1，2，3，4. 1，4，3，2. 3，2，1，4正確答案：20. 兩個(gè)串相等的充分必要條件是（） 。. 兩個(gè)串的長度相等. 兩個(gè)串對應(yīng)位置的字符相等. 兩個(gè)串的長度相等且對應(yīng)位置的字符相同. 以上條件都不正確正確答案：21. 深度為 5 的二叉樹至多有（）個(gè)節(jié)點(diǎn)。. 16. 32. 31. 10正確答案：22. 在含 n 個(gè)頂點(diǎn)和條邊的無向圖的鄰接矩陣中, 零元素的個(gè)數(shù)為（） 。. 2. n*n . n*n 2正確答案：23. 下列關(guān)于棧的敘述正確的是（） 。. 棧是非線性結(jié)構(gòu). 棧是一種樹狀結(jié)構(gòu). 棧具有先進(jìn)先

17、出的特征. 棧具有后進(jìn)先出的特征正確答案：24. 若給定的關(guān)鍵字集合為20 ， 15， 14， 18， 21， 36， 40， 10，一趟快速排序結(jié)束時(shí)，鍵值的排列為（ ） 。. 10 ，15，14，18，20，36，40，21. 10 ，15，14，18，20，40，36，21. 10 ，15，14，20，18，40，36，21. 15 ，10，14，18，20，36，40，21正確答案：25. 若某線性表中最常用的操作是取第I 個(gè)元素和找第I 個(gè)元素的前趨元素，則采用（ ） 存儲方式最節(jié)省時(shí)間。. 順序表. 單鏈表. 雙鏈表. 單循環(huán)鏈表正確答案：26. 順序表中邏輯上相鄰的節(jié)點(diǎn)其物理位置

18、也（） 。. 一定相鄰. 不必相鄰. 按某種規(guī)律排列. 無要求正確答案：27. 二叉樹第i 層上至多有（）結(jié)點(diǎn)。. 2i. 2 的i 次方. 2i-1. 2 的i-1 次方正確答案：28. 設(shè)單鏈表中指針p 指著結(jié)點(diǎn)，若要?jiǎng)h除之后的結(jié)點(diǎn)（若存在），則需要修改指針操作為（）。. P 一nxt p 一 nxt 一 nxt. p P 一nxt. p P 一nxt 一 nxt. p 一nxt p正確答案：29. 若從二叉樹的任一節(jié)點(diǎn)出發(fā)到根的路徑上所經(jīng)過的節(jié)點(diǎn)序列按其關(guān)鍵字有序，則該二叉樹是（ ） 。. 二叉排序樹. 哈夫曼樹. 堆. VL 樹正確答案：30. 對于一個(gè)具有n 個(gè)頂點(diǎn)的無向圖，若采用鄰

19、接矩陣表示，則該矩陣的大小是（） 。. n. （n-1）（n-1）. n-1. n*n正確答案：31. 下列數(shù)據(jù)組織形式中，（ ）的各個(gè)結(jié)點(diǎn)可以任意鄰接。. 集合. 樹形結(jié)構(gòu). 線性結(jié)構(gòu). 圖狀結(jié)構(gòu)正確答案：32. 計(jì)算機(jī)的算法必須具備輸入，輸出和（）五個(gè)特性。. 可行性，可移植性和可擴(kuò)充性. 可行性，確定性和有窮性. 確定性，有窮性和穩(wěn)定性. 易讀性，穩(wěn)定性和安全性正確答案：33. 無向圖的鄰接矩陣是一個(gè)（ ） 。. 對稱矩陣. 零矩陣. 上三角矩陣. 對角矩陣正確答案：34. 圖的深度優(yōu)先遍歷類似于二叉樹的（） 。. 先序遍歷. 中序遍歷. 后序遍歷. 層次遍歷正確答案：35. 一個(gè)棧的入

20、棧序列是, 則棧的不可能的輸出序列是（）正確答案：36. 由兩個(gè)棧共享一個(gè)向量空間的好處是（） 。. 減少存取時(shí)間，降低下溢發(fā)生的機(jī)率. 節(jié)省存儲空間，降低上溢發(fā)生的機(jī)率. 減少存取時(shí)間，降低上溢發(fā)生的機(jī)率. 節(jié)省存儲空間，降低下溢發(fā)生的機(jī)率正確答案：37. 若由森林轉(zhuǎn)化得到的二叉樹是非空的二叉樹，則二叉樹形狀是（）。. 根結(jié)點(diǎn)無右子樹的二叉樹. 根結(jié)點(diǎn)無左子樹的二叉樹. 根結(jié)點(diǎn)可能有左二叉樹和右二叉樹. 各結(jié)點(diǎn)只有一個(gè)兒子的二叉樹正確答案：38. 計(jì)算機(jī)的算法是（） 。. 計(jì)算方法. 排序方法. 對特定問題求解步驟的一種描述. 調(diào)度算法正確答案：北交數(shù)據(jù)結(jié)構(gòu)在線作業(yè)二二、判斷題（共2 道試題

21、，共5 分。 ）1. 線性表若采用鏈?zhǔn)酱鎯Ρ硎緯r(shí)所有結(jié)點(diǎn)之間的存儲單元地址可連續(xù)可不連續(xù). 錯(cuò)誤. 正確正確答案：2. 線性表的順序存儲表示優(yōu)于鏈?zhǔn)酱鎯Ρ硎? 錯(cuò)誤. 正確正確答案：北交數(shù)據(jù)結(jié)構(gòu)在線作業(yè)二38 道試題，共95 分。 ）1. 順序表中邏輯上相鄰的節(jié)點(diǎn)其物理位置也（） 。. 一定相鄰. 不必相鄰. 按某種規(guī)律排列. 無要求正確答案：2. 在有 n 個(gè)葉子結(jié)點(diǎn)的哈夫曼樹中，其結(jié)點(diǎn)總數(shù)為（） 。. 不確定. 2n. 2n+1. 2n-1正確答案：3. 在稀疏矩陣的帶行指針向量的鏈接存儲中，每個(gè)行單鏈表中的結(jié)點(diǎn)都具有相同的（）. 行號. 列號. 元素值. 地址正確答案：4. 按照二叉樹的

22、定義，具有3 個(gè)結(jié)點(diǎn)的二叉樹有（）種。. 3. 4. 5. 6正確答案：5. 一個(gè)隊(duì)的入隊(duì)序列是1 ， 2， 3， 4 ，則隊(duì)列的輸出序列是（） 。. 4，3，2，1. 1，2，3，4. 1，4，3，2. 3，2，1，4正確答案：6. 算法的時(shí)間復(fù)雜度是指（） 。. 執(zhí)行算法程序所需要的時(shí)間. 算法程序的長度. 算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù). 算法程序中的指令條數(shù)正確答案：7. 線性表是一個(gè)具有n 個(gè)（）的有限序列。. 表元素. 字符. 數(shù)據(jù)元素. 數(shù)據(jù)項(xiàng)正確答案：8. 在含 n 個(gè)頂點(diǎn)和條邊的無向圖的鄰接矩陣中, 零元素的個(gè)數(shù)為（） 。. 2. n*n . n*n 2正確答案：9. 向

23、一個(gè)有127 個(gè)元素的順序表中插入一個(gè)新元素并保持原來順序不變，平均要移動(dòng)（）個(gè)元素。. 8. 63.5. 64. 7正確答案：10. 一個(gè)棧的入棧序列是, 則棧的不可能的輸出序列是（）。正確答案：11. 設(shè) F 是一個(gè)森林，是由F轉(zhuǎn)換得到的二叉樹，F(xiàn) 中有 n 個(gè)非葉結(jié)點(diǎn)，則中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有（）個(gè)。 . n-1 . n . n+1 . n+2 正確答案：12. 由權(quán)值分別為3,6,7,2,5 的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（）。. 23 . 51 . 53 . 74 正確答案：13. 設(shè)循環(huán)隊(duì)列Q1.N-1 的頭尾指針為F， R，當(dāng)插入元素時(shí)尾指針R加 1，頭指針F 總

24、是指在隊(duì)列中第一個(gè)元素的前一個(gè)位置，則隊(duì)列中元素計(jì)數(shù)為（）。. R-F. N- （ R-F）. （ R-F+N） %N. （ F-R+N） %N正確答案：14. 帶頭節(jié)點(diǎn)的單鏈表h 為空的判定條件（） 。. h=NULL. h->nxt=NULL. h->nxt=h. h!=h正確答案：15. 設(shè)有一個(gè)二元數(shù)組mn ，假設(shè) 00 存放位置在644（10） ， 22 存放位置在676（10） ，每個(gè)元素占一個(gè)空間，則45 在（ ）位置，（10） 表明用 10 進(jìn)數(shù)表示。. 692（10）. 626（10）. 709（10）. 724（10）正確答案：16. 如果待排序序列中兩個(gè)數(shù)據(jù)元素具有相同的值，在排序后它們的位置發(fā)生顛倒，則稱該排序是不穩(wěn)定的。下列選項(xiàng)中，（）就是不穩(wěn)定的排序方法。.