數(shù)據(jù)結構-選擇題

1、數(shù)據(jù)結構-選擇題1. 通常要求同一邏輯結構中的所有數(shù)據(jù)元素具有相同的特性，這意味著(  )。 單選題 *A.數(shù)據(jù)元素具有同一特點B.不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，而且對應數(shù)據(jù)項的類型要一致(正確答案)C.每個數(shù)據(jù)元素都一樣D.數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等2. 對順序存儲的線性表，設其長度為n，且在任何位置上插入或刪除操作都是等概率的。則插入一個元素時平均要移動表中的( )個元素。 單選題 *A.n/2(正確答案)B.(n+1)/2C.(n-1)/2D.n3. 數(shù)據(jù)的基本單位是( )。 單選題 *A.數(shù)據(jù)元素(正確答案)B.數(shù)據(jù)結構C.數(shù)據(jù)項D.數(shù)據(jù)對象4. 算法在發(fā)生

2、非法操作時可以做出處理的特性稱為( )。 單選題 *A.健壯性(正確答案)B.確定性C.可行性D.正確性5. 在一個長度為n的順序表中向第i個元素（0in）位置插入一個新元素時，需要從后向前依次后移( )個元素。 單選題 *A.n-iB.n-i+1(正確答案)C.n-i-1D.i6. 棧和隊列的共同之處在于它們具有相同的( ) 單選題 *A.邏輯特性(正確答案)B.物理特性C.運算方法D.元素類型7. 某隊列初始為空，若它的輸入序列為a，b，c，d，它的輸出序列應為( ) 單選題 *A.a，b，c，d(正確答案)B.d，c，b，aC.a，c，b，dD.d，a，c，b8. 下列關于鏈棧的敘述中正

3、確的是( ) 單選題 *A.鏈棧和順序棧相比，缺點是不能隨機訪問棧中的元素B.鏈棧在進棧操作時一般不需要考慮上溢出(正確答案)C.鏈棧在出棧操作時一般不需要考慮下溢出D.以上都不對9. 設串s1abcdefg，s2pqrst，函數(shù)CON(X，Y)返回X和Y的連接串，SUB(S，I，J)返回串S的從序號I的字符開始的J個字符組成的子串，LEN(S)返回串S的長度，則CON(SUB(s1,2，LEN(s2),SUB(s1,LEN(s2),2)）的結果串是( )。 單選題 *A.bcdefB.bcdefgC.bcpqrstD.bcdefef(正確答案)10. 深度為6的二叉樹最多有( )個結點。 單

4、選題 *A.64B.63(正確答案)C.32D.3111. 設有5個元素的進棧序列為a、b、c、d、e，1，其輸出序列是c、e、d、b、a，則該棧的容量至少是( )。 單選題 *A. 1B. 2C. 3D. 4(正確答案)12. 當4個元素的進棧序列給定以后，由這4個元素組成的可能的出棧序列應該有( )。 單選題 *A.24種B.17種C.16種D.14種(正確答案)13. 以下說法錯誤的是( )。 單選題 *A.二叉樹可以是空集B.二叉樹的任一結點都有兩棵子樹(正確答案)C.二叉樹與樹具有相同的樹形結構D.二叉樹中任一結點的兩棵子樹有次序之分14. 設二叉樹有n個結點，則其深度為( )。 單

5、選題 *A.n-1B.nC.1D.無法確定(正確答案)15. 設深度為k的二叉樹上只有度為0和度為0的節(jié)點，則這類二叉樹上所含結點總數(shù)最少( )個 單選題 *A.k+1B.2kC.2k-1(正確答案)D.2k+116. 某二叉樹的先序遍歷結點訪問順序是abdgcefh，中序遍歷的結點訪問順序是dgbaechf，則其后序遍歷的結點訪問順序是( )。 單選題 *A.bdgcefhaB.gdbecfhaC. bdgechfaD. gdbehfca(正確答案)17. 對n個不同的排序碼進行冒泡排序，在元素無序的情況下比較的次數(shù)為( ) 單選題 *A. n+1B. nC. n-1D. n(n-1)/2(

6、正確答案)18. 若一組記錄的排序碼為（46, 79, 56, 38, 40, 84），則利用堆排序的方法建立的初始堆為( )。 單選題 *A. 79, 46, 56, 38, 40, 84B. 84, 79, 56, 38, 40, 46(正確答案)C. 84, 79, 56, 46, 40, 38D. 84, 56, 79, 40, 46, 3819. 堆的形狀是一棵( )。 單選題 *A.二叉排序樹B.滿二叉樹C.完全二叉樹(正確答案)D.平衡二叉樹20. 下述幾種排序方法中，平均查找長度（ASL）最小的是( )。 單選題 *A.插入排序B.快速排序(正確答案)C.歸并排序D.選擇排序2

7、1. 已知某二叉樹的后續(xù)遍歷序列是dabec，中序遍歷序列是deabc，它的先序遍歷序列是( )。 單選題 *A.acbedB.deabcC.decabD.cedba(正確答案)22. 將5個不同的數(shù)據(jù)進行排序，至多需要比較( )次。 單選題 *A. 8B. 9C. 10(正確答案)D. 2523. 若一組記錄的排序碼為（46, 79, 56, 38, 40, 84），則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結果為( )。 單選題 *A.38, 40, 46, 56, 79, 84B.40, 38, 46, 79, 56, 84C.40, 38, 46, 56, 79, 84(正

8、確答案)D.40, 38, 46, 84, 56, 7924. 下列關鍵字序列中，( )是堆。 單選題 *A. 16,72,31,23,94,53B. 94,23,31,72,16,53C. 16,53,23,94,31,72D. 16,23,53,31,94,72(正確答案)25. 具有32個結點的完全二叉樹的深度為( )。 單選題 *A. 5B.6(正確答案)C.7D.826. 對序列(15，9，7，8，20，-1，4)進行排序，進行一趟排序后，數(shù)據(jù)的排列變?yōu)椋?，9，-1，8，20，7，15），則采用的是( )排序。 單選題 *A.選擇B.快速C.希爾(正確答案)D.冒泡27. 下列陳述

9、正確的是( )。 單選題 *A.二叉樹是度為2的有序樹B.二叉樹中最多只有二棵樹,且有左右子樹之分(正確答案)C.二叉樹必有度為2的結點D. 二叉樹中結點只有一個孩子時無左右之分28. 由帶權為9、2、5、7的四個葉子結點構造一棵哈夫曼樹，該樹的帶權路徑長度為( )。 單選題 *A.23B.37C.46D.44(正確答案)29. 任何一棵二叉樹的葉結點在先序、中序和后序遍歷的序列中的相對次序( ) 單選題 *A.不發(fā)生變化(正確答案)B.發(fā)生變化C.不能確定D.以上都不對30. 設深度為h的二叉樹上只有度為0和度為2的結點，則此類二叉樹中所包含的結點數(shù)至少為( )。(注意C和D中h為指數(shù)) 單

10、選題 *A.2h-1B.2(h-1)C.2*h-1(正確答案)D.2*h31. 在順序表2、5、7、10、14、15、18、23、35、41、52中，用二分法查找關鍵碼12需做( )次關鍵碼比較。 單選題 *A.2B.3C.4(正確答案)D.532. 樹最適合用來表示( )。 單選題 *A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間具有分支層次關系的數(shù)據(jù)(正確答案)D.元素之間無聯(lián)系的數(shù)據(jù)33. 某非空二叉樹的前序序列和后序序列正好相反，則二叉樹一定是( )的二叉樹。 單選題 *A.空或只有一個結點B.高度等于其結點數(shù)(正確答案)C.任一結點無左孩子D.任一結點無右孩子34. 關于二叉樹的三種遍

11、歷，下列說法正確的是( )。 單選題 *A.任意兩種遍歷序列都不可以唯一決定該二叉樹B.任意兩種遍歷序列都可以唯一決定該二叉樹C.先序遍歷序列和后序遍歷序列可以唯一決定該二叉樹D.先序遍歷序列和中序遍歷序列可以唯一決定該二叉樹(正確答案)35. 設a,b為一棵二叉樹上的兩個結點，在中序遍歷時，a在b前的條件是( )。 單選題 *A. a是b祖先B. a是b子孫C. a在b左方(正確答案)D. a在b右方36. 設二叉樹根結點的層次為1，所有含有15個結點的二叉樹中，最小高度是( ) 單選題 *A.6B.5C.4(正確答案)D.337. 有m個葉子結點的Huffman樹所具有的結點總數(shù)為( )。

12、 單選題 *A.m+1B.2m-1(正確答案)C.2mD.2m+138. 設有1000個無序的元素,希望用最快的速度挑選出其中前10個最大的元素,最好采用( )排序法。 單選題 *A.冒泡排序B.快速排序C.堆排序(正確答案)D.插入排序39. 設森林中有4棵樹，樹中結點的個數(shù)依次為n1、n2、n3、n4，則把森林轉換成二叉樹后，根結點的左子樹上有( )個結點。 單選題 *A.n1-1(正確答案)B.n1C.n1+n2+n3D.n2+n3+n440. 若構造一棵具有n個結點的二叉排序樹，最壞的情況下其深度不會超過( )。 單選題 *A.n/2B.n(正確答案)C.(n+1)/2D.n+141. 下列排序算法的時間復雜度最小的是( )。 單選題 *A.冒泡排序B