數(shù)據(jù)結(jié)構(gòu)習(xí)題

1、一、 單項選擇題1. 下面程序段的時間復(fù)雜度為( C ) 。  for(int i=0; i<m; i+)   for(int j=0; j<n; j+)             aij=i*j;   A O(m2)        B O(n2)&

2、#160;        C O(m*n)         D O(m+n)2. 設(shè)有一個遞歸算法如下 int fact(int n)/n大于等于0 if(n<=0) return 1； else return n*fact(-n)； 則計算fact(n)需要調(diào)用該函數(shù)的次數(shù)為( D )次，不計fact(n)。 An Bn+1 Cn+2 Dn-l3. 評價排序算法好壞的標準主要是(D)。  A執(zhí)行時間 

3、0; B輔助空間  C算法本身的復(fù)雜度   D執(zhí)行時間和所需的輔助空間4. 在需要經(jīng)常查找結(jié)點的前驅(qū)與后繼的場合中，使用(   B   )比較合適。 A單鏈表           B雙鏈表           C順序表         &#

4、160; D循環(huán)鏈表5. 在一個單鏈表HL中，若要刪除由指針q所指向結(jié)點的后繼結(jié)點，則執(zhí)行（ C ）。    Ap = q->next   p->next = q->next;    Bp = q->next   q->next = p;    Cp = q->next &

5、#160; q->next = p->next;    Dq->next = q->next->next;  q->next = q;6. 已知單鏈表A長度為m，單鏈表B長度為n，若將B聯(lián)接在A的末尾，其時間復(fù)雜度應(yīng)為( B ) 。 AO(1) BO(m) CO(n) DO(m+n)7. 鏈表不具有的特點是（ A ）。 A可隨機訪問任一元素 B插入刪除不需要移動元素 C不必事先估計存儲空間 D所需空間與線性表長度成正比8. 若要在

6、單鏈表中的結(jié)點*p之后插入一個結(jié)點*s，則應(yīng)執(zhí)行的語句是( A )。As->next=p->next; p->next=s; Bp->next=s; s->next=p->next;Cp->next=s->next; s->next=p; Ds->next=p; p->next=s->next;9. 假定一個鏈式隊列的隊頭和隊尾指針分別為front和rear，則判斷隊空的條件為 ( D )。 Afront=NULL Bfront!=NULLCrear!=NULL Dfront= =rear10. 棧和隊列都是（C）。A鏈式

7、存儲的線性結(jié)構(gòu) B順序存儲的線性結(jié)構(gòu)C限制存取位置的線性結(jié)構(gòu) D限制存取位置的非線性結(jié)構(gòu)11. 對于給定的結(jié)點序列abcdef，規(guī)定進棧只能從序列的左端開始。通過棧的操作，能得到的序列為（ A ）。Aabcfed Bcabfed Cabcfde Dcbafde12. 隊列通常采用兩種存儲結(jié)構(gòu)是(    A  )。 A順序存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)    B散列方式和索引方式 C鏈表存儲結(jié)構(gòu)和數(shù)組          

8、60; D線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)13. 若讓元素1，2，3依次進棧，則出棧次序不可能出現(xiàn)（ C ）種情況。A3，2，1 B2，1，3 C3，1，2 D1，3，214. 若一個串非空，子串的定位操作通常稱為( C )。A. 串的長度 B.原串的子串 C.串的模式匹配 D.串的連接15. 設(shè)有一個n×n的對稱矩陣A，將其上三角部分按行存放在一個一維數(shù)組B中，A00存放于B0中，那么第i行的對角元素Aii存放于B中( C )處。A(i+3)*i2 B(i+1)*i2 C(2n-i+1)*i2 D(2n-i-1)*i216. 在( C )運算中，使用順序表比鏈表好。  A插入

9、   B刪除   C根據(jù)序號查找  D根據(jù)元素值查找17. 帶頭結(jié)點的單鏈表head為空的判斷條件是(  C   )。 Ahead= =NULL   Bhead->next= =NULLChead->next=head  Dhead!=NULL 18. 設(shè)一個鏈表最常用的操作是在末尾插入結(jié)點和刪除尾結(jié)點，則選用（ C ）最節(jié)省時間。A）單鏈表  B）循環(huán)鏈單表  C）帶尾指針的循環(huán)鏈單表 D）帶頭結(jié)點的雙循環(huán)鏈表19. 棧的插入與刪除

10、操作在（ A ）進行。A棧頂          B棧底          C任意位置      D指定位置20. 設(shè)一個棧的輸入序列為A、B、C、D，則借助一個棧所能得到的輸出序列不可能是（ D ）。 AABCD BDCBA CACDB DDABC21. 在一個鏈隊中，假設(shè)F和R分別是隊首和隊尾指針，則刪除一個結(jié)點的運算是( C )。 &

11、#160;AR=F->next;   BR=R->next;   CF=F->next;  DF=R->next;22. 串是一種特殊的線性表，其特殊性體現(xiàn)在( B )。  A可以順序存儲   B數(shù)據(jù)元素是一個字符  C可以鏈接存儲   D數(shù)據(jù)元素可以是多個字符 23. 以下說法正確的是（ C ）。A）空串與空格串是相同的 B）“fox”是“FoxBase”的子串C）空串是零個字符組成的串 D）空串長度等于124. 若n為主串長，m為子串長（m<n），則用簡單模式匹配算法最壞情況下，需要比較字符

12、總數(shù)是（ C ）。Am         Bm(n-m+1)       Cn*m       D(n-m)*(m-1)25. 將一個A1.100,1.100的三對角矩陣，按行優(yōu)先存入一維數(shù)組B1.298中，A中元素A66，65在B數(shù)組中的位置k為（ B ）。A）198 B）195 C）19726. 一個稀疏矩陣的轉(zhuǎn)置矩陣應(yīng)是（ B ）。A.下三角矩陣 B稀疏矩陣C非稀疏矩陣 D有時為稀疏矩陣27. 廣義表（e）的表頭

13、是（ C ）。A）e B）( ) C）(e) D）(e) 28. 深度為5的二叉樹至多有(   C  )個結(jié)點。 A16           B32           C31          D1029. 具有10個葉子結(jié)點的二叉樹中有（B）個度為2的結(jié)點。A8 B9 C10 D113

14、0. 在二叉樹的中序遍歷遞歸算法中，順著搜索路徑，在第( B )次經(jīng)過結(jié)點時作訪問操作。  A1   B2   C3   D431. 在中序線索二叉樹中，若某結(jié)點有右孩子，則該結(jié)點的直接后繼是( D )。  A 左子樹的最右下結(jié)點   B 右子樹的最右下結(jié)點  C 左子樹的最左下結(jié)點   D 右子樹的最左下結(jié)點 32. 按照二叉樹的定義，具有3個結(jié)點的二叉樹有( C   )種形態(tài)。 A3         &

15、#160; B4           C5          D633. 某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是（B）的二叉樹。 A空或只有一個結(jié)點 B高度等于其結(jié)點數(shù) C任一結(jié)點無左孩子 D任一結(jié)點無右孩子34. 圖的廣度優(yōu)先搜索類似于樹的( D )次序遍歷。A先根 B中根 C后根 D層次 35. n個頂點的強連通圖中至少含有( B )。An-l條有向邊 Bn條有向邊 Cn(n-1)/2條有向邊 D

16、n(n-1)條有向邊36. 任何一個無向連通圖的最小生成樹（B）。 A只有一棵 B有一棵或多棵 C一定有多棵D可能不存在37. 設(shè)G1=(V1,E1)和G2=(V2,E2)為兩個圖，如果V2包含V1，E2包含E1，則稱( A )。  AG1是G2的子圖   BG1是G2的連通分量  CG2是G1的連通分量   DG2是G1的子圖 38. 下面關(guān)于圖的存儲的敘述中，哪一個是正確的。 ( A )  A用鄰接矩陣法存儲圖,占用的存儲空間數(shù)只與圖中結(jié)點個數(shù)有關(guān),與邊數(shù)無關(guān)  B用鄰接矩陣法存儲圖,占用的存儲空間數(shù)只與圖中邊數(shù)有關(guān),與結(jié)點個數(shù)無

17、關(guān)  C用鄰接表存儲圖，占用的存儲空間數(shù)只與圖中結(jié)點個數(shù)有關(guān)，與邊數(shù)無關(guān)  D用鄰接表存儲圖，占用的存儲空間數(shù)只與圖中邊數(shù)有關(guān)，與結(jié)點個數(shù)無關(guān) 39. ( D )適合用鄰接表表示。  A稠密圖   B有向完全圖  C無向完全圖   D稀疏圖 40. 一般，圖的DFS生成樹的高度( C )BFS生成樹的高度。  A小于   B等于   C大于   D小于或等于 41. 從一棵二叉排序樹中查找一個元素時，其平均時間復(fù)雜度為( C )。 AO(1) BO(n) CO(1og2n) DO(n2)42.

18、二分查找法要求查找表中各元素的鍵值必須是( A )排列。 A遞增或遞減 B遞增 C遞減 D無序43. 向具有n個結(jié)點的、結(jié)構(gòu)均衡的二叉排序樹中插入一個元素的時間復(fù)雜度為 ( B )。 AO(1) BO(log2n) CO(n) DO(nlog2n)44. 線性表必須是( D )，才能進行二分查找。  A用向量存儲的線性表   B用鏈表存儲的有序表  C用鏈表存儲的線性表   D用向量存儲的有序表45. 按照不同的順序輸入4，5，6三個關(guān)鍵字，能建立（ B ）棵不同的二叉排序樹。A）6 B）5 C）4 D）346. 在一棵m階B-樹中，若在某結(jié)點中插入一個

19、新關(guān)鍵字而引起該結(jié)點的分裂，則該結(jié)點中原有（ D ）個關(guān)鍵字。A）ëm/2û B）ëm/2û - 1 C）m D）m-1 E）ém/2ù F）ém/2ù - 1 47. 設(shè)有5000個無序的元素，希望用最快的速度挑選出其中前50個最大的元素，最好選用(    C  )法。 A冒泡排序                &#

20、160;    B快速排序 C堆排序                        D基數(shù)排序48. 下列序列中( B )是執(zhí)行第一趟快速排序后得到的序列（排序的關(guān)鍵字類型是字符串）。 Ada,ax,eb,de,bbffba,gc Bcd,eb,ax,da,bbffha,gc Cgc,ax,cb,cd,bbffda,ba Dax,bb,c

21、d,daffeb,gc,ba49. 在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然有序的時間復(fù)雜度是( B )。  AO(1)   B O(n)   C O(n2)   D O(log2n)50. 以下排序方法中，穩(wěn)定的排序方法是( B )。  A直接插入排序和希爾排序   B直接插入排序和冒泡排序  C希爾排序和快速排序   D冒泡排序和快速排序 51. 在快速排序中，每次劃分選擇的基準元素為該區(qū)間的( D )時，得到的兩個子區(qū)間是均勻的。  A最大值   B最小值   C任意

22、值   D中間值 52. 若從二叉樹的任一結(jié)點出發(fā)到根的路徑上所經(jīng)過的結(jié)點序列按關(guān)鍵字有序，則該二叉樹是下列樹中的哪種?（ C ）A. 二叉排序樹 B. 哈夫曼樹 C. 堆。二、 填空題1. 在一個長度為n的順序表中刪除第i個元素，要移動_n-i_個元素。 2. 在順序表中插入或刪除一個元素，需要平均移動 表長的一半 元素，具體移動元素的個數(shù)與 元素所在的位置 有關(guān)。3. 若線性表采用順序存儲結(jié)構(gòu)存放，那么在長度為n的線性表中刪除第i（1in）個數(shù)據(jù)元素需要移動 n-i 個數(shù)據(jù)元素，在長度為n的線性表中第i（1in）個數(shù)據(jù)元素之前插入一個新的數(shù)據(jù)元素需要移動 n-i+1 個數(shù)據(jù)元素。

23、4. 在非空的單循環(huán)鏈表h中，某個結(jié)點p為尾結(jié)點的條件是 p->next = h 。5. 一個隊列的入隊序列是a、b、c、d，則隊列的輸出序列為_abcd_。6. 棧結(jié)構(gòu)通常采用的兩種存儲結(jié)構(gòu)是_順序棧_和_鏈棧_。7. 設(shè)棧S和隊列Q的初始狀態(tài)為空，元素a、b、c、d、e、f依次通過棧S，一個元素出棧后即進入隊列Q。若這6個元素出隊列的順序是b、d、c、f、e、a，則棧S的容量至少應(yīng)該是 3 。8. 設(shè)有一個n×n的對稱矩陣A，將其上三角部分按行存放在一個一維數(shù)組B中，A00存放于B0中，那么第i行的對角元素Aii存放于B中 (2n-i+1)*i2 處。9. 設(shè)有5對角矩陣A

24、 = (aij)20*20，按特殊矩陣壓縮存儲的方式將其5條對角線上的元素存于數(shù)組B0：m中，計算元素A10,10的存儲位置 44 。10. 已知廣義表L=（a,( ),b),(e)），利用取表頭和取表尾的操作分離出原子e的運算是 GetHead(GetHead(GetHead(GetTail(GetTail(L) 。11. 設(shè)廣義表B=( ) ,(a, (b, c), (e,f)，( )，表頭為 ( ) ，表尾為 (a, (b, c), (e,f)，( ) 。12. 在空串和空格串中，長度不為0的是_空格串_。 13. 有n個結(jié)點的二叉鏈表中，其中空的指針域為n+1.指向孩子的指針個數(shù)為_n

25、-1_。 14. 中綴算術(shù)表達式5+6/(23-(6+15)*8 所對應(yīng)的后綴算術(shù)表達式為_5,6,23,6,15,+,-,/,8,*,+_。15. 假定一棵二叉樹的結(jié)點個數(shù)為50，則它的最小深度為_6_，最大深度為_50_。16. 一棵樹的后根序列與其轉(zhuǎn)換的二叉樹的 中 序列相同,先根序列與其轉(zhuǎn)換的二叉樹的 先 序列相同。17. 具有400個結(jié)點的完全二叉樹的深度為_9_。18. 一棵二叉樹有67個結(jié)點，這些結(jié)點的度要么是0，要么是2。這棵二叉樹中度為2的結(jié)點有_33_個。 19. 已知森林的先序訪問序列為ABCDEFGHIJKL；中序訪問序列為CBEFDGAJIKLH。則該森林有

26、_2_棵樹。20. 當(dāng)對字符集進行編碼時，字符集中任一字符的編碼都不是其他字符的編碼的前綴，這種編碼稱_二進制前綴編碼_。21. 高度為h的二叉樹只有度為0和2的結(jié)點，則此類二叉樹的結(jié)點數(shù)至少為 2h-1+1 個結(jié)點，至多為 2h-1 個結(jié)點。22. 深度為k的完全二叉樹至少有 2k-1 個結(jié)點，至多有 2k-1 個結(jié)點。23. 一個有30個結(jié)點的完全二叉樹有 15 個葉子結(jié)點；有 14 個度為2的結(jié)點。24. 高度為i(i1)的完全二叉樹按自上而下，從左到右的次序給結(jié)點編號（從1開始），則可能的編號最小的葉子結(jié)點的編號為 2k-2+1 。25. 設(shè)圖G(V，E)，V1，2，3，4，E<

27、l，2>，<1，3>，<2，4>，<3，4>，從頂點1出發(fā)，對圖G進行廣度優(yōu)先搜索的序列有_2_種。26. 有向圖G用鄰接矩陣A1.n,1.n存儲，矩陣中元素值1代表有弧，0代表無弧，其第i行的所有元素之和等于頂點i的_出度_度。27. 一個連通圖的生成樹是該圖的 極小 連通子圖。若這個連通圖有n個頂點，則它的生成樹有_n-1_條邊。28. n個頂點的無向連通圖的鄰接矩陣中至少有_2(n-1)_個非零元素，至多有_n(n-1)_個非零元素。29. PRIM算法與圖的邊數(shù)無關(guān)，適合求解 稠密圖 的最小生成樹。30. 一棵3階B-樹中每個結(jié)點最多有 3 棵

28、子樹，每個結(jié)點最多有 2 個關(guān)鍵字。含有9個葉子結(jié)點的3階B-樹至少有 4 個非葉結(jié)點，至多有 7 個非葉結(jié)點。31. 從有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素時，其查找長度分別為_1_和_3_。32. 向一棵二叉排序樹中插入一個元素時，若元素的值小于根結(jié)點的值，則應(yīng)把它插入到根結(jié)點的_左 子樹上。33. 分別采用堆排序、快速排序、插入排序和歸并排序算法對初始狀態(tài)遞增序列按遞增順序排序，最省時間的是算法 插入排序 ，最費時間的是算法 快速排序 。三、 簡答及圖示說明題1. 廣義表的基本概念，如A = (a,b),c,(d,e,f)，用GetGead和GetTail操作取元素d2. 根據(jù)給定二叉樹的先序和中序序列，構(gòu)造二叉樹3. 根據(jù)給定樹的先序和后序序列，構(gòu)造樹4. 已知二叉樹，畫出中序的線索。5. 森林和二叉樹的相互轉(zhuǎn)換6. 有7個帶權(quán)結(jié)點