數(shù)據(jù)結構復習題

1、數(shù)據(jù)結構與算法一、選擇題1. 組成數(shù)據(jù)的基本單位是( )。(A) 數(shù)據(jù)項 (B)數(shù)據(jù)類型 (C)數(shù)據(jù)元素 (D)數(shù)據(jù)變量2. 線性表的鏈接實現(xiàn)有利于( )運算。(A) 插入 (B)讀表元 (C)查找 (D)定位3. 串的邏輯結構與( )的邏輯結構不同。(A) 線性表 (B)棧 (C)隊列 (D)樹4. 二叉樹第i（i1）層最多有( )個結點。(A) 2i (B)2i (C) 2i-1 (D) 2i-15. 設單鏈表中指針p指向結點A，若要刪除A后結點（若存在），則需要修改指針的操作為( )(A) p-next = p-next-next (B)p=p-next (C)p=p-next-next

2、 (D)p-next=p6. 設一數(shù)列的輸入順序為1,2,3,4,5,6，通過棧操作不可能排成的輸出序列為( )(A) 3,2,5,6,4,1 (B) 1,5,4,6,2,3(C) 2,4,3,5,1,6 (D) 4,5,3,6,2,17. 設字符串S1=ABCDEFG，S2=PQRST，則運算S=CONCAT(SUB(S1,2,LENGTH(S2)，SUB(S1,LENGTH(S2),2)的結果為( )(A) BCQR (B) BCDEF (C) BCDEFG (D) BCDEFEF8. 有一個10階的對稱矩陣A,采用壓縮存儲方式，以行序為主存儲，a11為第一元素，其存儲地址為1，每個元素占

3、1個地址空間，則a85地址為( )(A)13 (B) 33 (C) 18 (D) 409. 如果結點A有3個兄弟，而且B為A的雙親，則B的度為( )(A) 3 (B) 4 (C) 5 (D) 110. 線索化二叉樹中某結點D沒有左孩子的必要條件是( )(A) D-Lchild=Null (B) D-ltag=1 (C) D-Rchild=Null (D) D-ltag=0 10. 數(shù)據(jù)結構是研究數(shù)據(jù)的( )以及它們之間的相互關系。(A) 理想結構、物理結構 (B) 理想結構、抽象結構(C) 物理結構、邏輯結構 (D) 抽象結構、邏輯結構11. 線性表采用鏈式存儲時，其地址( )。(A) 必須是

4、連續(xù)的 (B) 部分地址必須是連續(xù)的(C) 一定是不連續(xù)的 (D) 連續(xù)與否均可以12. 設循環(huán)隊列Q1.N-1的頭尾指針為F，R，當插入元素時尾指針R加1，頭指針F總是指向隊列中第一個元素的前一個位置，則隊列中元素計數(shù)為( )。(A) R-F (B) N-(R-F) (C) (R-F+N)%N (D) (F-R+N)%N13. 完成堆排序的全過程需要( )個記錄大小的輔助空間。(A) 1 (B) n (C) nlog2n (D) n214. 若給定關鍵字集合為20,15,14,18,21,36,40,10，一趟快速排序結束時，鍵值的排列為( )(A) 10,15,14,18,20,36,40

5、,21 (B) 10,15,14,18,20,40,36,21 (C) 10,15,14,20,18,40,36,21 (D) 15,10,14,18,20,36,40,2115. 有一棵二叉樹如圖1所示，該樹是( )。圖1(A) 二叉平衡樹 (B) 二叉排序樹(C) 堆的形狀 (D) 以上都不是16. 對于含有n個頂點e條邊的無向連通圖，利用Prim算法生成最小代價生成樹其時間復雜度為( ),利用Kruskal的時間復雜度為( )。(A) O(log2n) (B) O(n2) (C) O(ne) (D) O(elog2e)17. 具有n個頂點的完全有向圖的邊數(shù)為( )。(A) n(n-1)/

6、2 (B) n(n-1) (C) n2 (D) n2-118. 設有100個元素，用二分法查找時，最大比較次數(shù)是( )，最小比較次數(shù)是( )。(A) 25 (B) 7 (C) 10 (D) 119. 在內部排序中，排序時不穩(wěn)定的有( )。(A) 插入排序 (B) 冒泡排序 (C) 快速排序 (D) 歸并排序20. 中序遍歷一棵二叉排序樹所得的結點訪問序列是鍵值的( )序列。(A) 遞增或遞減 (B) 遞減 (C) 遞增 (D) 無序21. Substr(DATA STRUCTURE,5,9) = ( )。(A) STRUCTURE (B) DATA (C) ASTRUCTUR (D) DATA

7、 STRUCTURE22. 下列哪種形態(tài)不是樹( )。 （A） （B） （C） （D）23. 下列哪種排序需要的附加存儲開銷最大( )。(A) 快速排序 (B) 堆排序 (C) 歸并排序 (D) 插入排序24. 對任何一棵樹T，設n0,n1,n2,nm分別是0,1,2,m的結點，則n0=( )。(A) n1+n2+nm (B) 1+n2+2n3+（m-1）nm (C) n2+2n3+3n4+（m-1）nm (D) 2n1+3n2+（m+1）nm 圖 125. 在圖1中，V4的度為( )。(A) 1 (B) 2 (C) 3 (D) 426. n個頂點的無向圖的鄰接表中結點總數(shù)最多有( )個。(A

8、) 2n (B) n (C) n/2 (D) n(n-1)27. 設連通圖G的頂點數(shù)為n，則G的生成樹的邊數(shù)為( )。(A) n (B) n-1 (C) 2n (D) 2n-128. 下列哪種排序需要的附加存儲開銷最小( )。(A) 快速排序 (B) 堆排序 (C) 歸并排序 (D) 計數(shù)排序29. 若按 ( )列出二叉搜索樹中所存儲的元素，則恰好是集合中所有元素從小到大的排序。(A) 先序 (B) 中序 (C) 后序 (D) 按層次30. 在圖1所示的4棵樹中，哪一棵是完全二叉樹( )。 （A） （B） （C） （D）圖131. 下面程序段的時間復雜度為( )。s=s0;for(i =1 ;

9、i=n-1;j-) s = s+1; (A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(n3/2)32. 采用鏈結構存儲線性表時，其地址( )。(A) 必須是連續(xù)的 （B）連續(xù)不連續(xù)都可以（C）部分地址必須是連續(xù)的 (D) 必須是不連續(xù)的33. 具有2000個結點的二叉樹，其高度至少為( )。(A) 9 (B) 10 (C) 11 (D) 1234. 下列程序的時間復雜度為( )。for(i=0;im;i+) for(j =0;jt;j+) cij=0; for(i=0;im;i+)for(j=0;jt;j+)for(k=0;k0) (D) 串中所含字符的個數(shù)n(n

10、0)38. 若有一個棧的輸入序列是1,2,3,n，輸出序列的第一個元素是n，則第i個輸出元素是( )(A) n-i (B) n-i-1 (C) n-i+1 (D) 不確定39. 設有一個棧，元素的進棧次序A，B，C，D，E，下列( )是不可能的出棧序列。(A) A,B,C,D,E （B）B,C,D,E,A(C) E,A,B,C,D （D）E,D,C,B,A40. 在一棵度為3的樹中，度為3的結點數(shù)為2個，度為2的結點數(shù)為1個，度為1的結點數(shù)為2個，那么度為0的結點數(shù)有( )個。(A) 4 (B) 5 (C) 6 (D) 741. 在一個具有n個結點的無向完全圖中，包含有( )條邊。(A) n(

11、n-1)/2 (B) n(n-1) (C) n(n+1)/2 (D) n242. 采用順序檢索的方法檢索長度為n的線性表，則檢索每個元素的平均比較次數(shù)為( )。(A) n (B) n/2 (C) (n+1)/2 (D) (n-1)/243. 已知一個有序表為（13,18,24,35,47,50,62,83,90,115,134），當二分檢索值為90的元素時，需要( )次比較可檢索成功。44. 已知8個元素（34,76,45,18,26,54,92,65），按照依次插入結點的方法生成一棵二叉排序樹，該樹的深度為( )。(A) 4 (B) 5 (C) 6 (D) 745、如某數(shù)據(jù)結構的數(shù)據(jù)元素的集

12、合為S=A,B,C,D,E,F,G,數(shù)據(jù)元素之間的關系為R=,則該數(shù)據(jù)結構是一種 。(A)線性結構(B)樹結構(C)圖結構(D)鏈表結構46、具有20個結點的二叉樹，其深度最多為 。(A)4(B)5(C)6(D)2047、在具有N個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊頭指針和隊尾指針，則判斷隊空的條件為 。(A)front=rear(B)（rear+1）%MAXSIZE=front(C)front-rear=1(D)rear%MAXSIZE=front48、一個55的對稱矩陣采用壓縮存儲，需要存儲 個元素。(A)5(B)10(C)15(D)2049、一個無向連通圖有5個

13、頂點、8條邊，則其生成樹將要去掉 條邊。(A)3(B)4(C)5(D)650、設一顆二叉樹共有50個葉子結點（終端結點），則共有 個度為2的結點。(A)25(B)49(C)50(D)5151、設一棵二叉樹共有20個度為2的結點，則葉子結點共有 個。(A)40(B)19(C)20(D)2152、一個元素進入隊列的時間復雜度是 。(A)O(1)(B) O(n)(C) O(n2)(D) O(log2n)53、設一顆完全二叉樹中根結點的編號為1，而且23號結點有左孩子但沒有右孩子，則完全二叉樹總共有 個結點。(A)24(B)45(C)46(D)4754、二叉樹的第3層最少有 個結點。(A)0(B)1(

14、C)2(D)355、已知某算法的執(zhí)行時間為（n+n2）+log2(n+2)，n代表問題規(guī)模，則該算法的時間復雜是 。(A)O(n)(B)O(n2)(C)O(log2n)(D)O(nlog2n)56、如果一棵樹有10個葉子結點，則該樹至少有 個結點。(A)10(B)11(C)19(D)2157、設有一個10階的對稱矩陣a，采用壓縮存儲方式，以行序為主存儲，a00的存儲地址為100，每元素占1個地址空間，則a32的地址為 。(A)102(B)105(C)106(D)10858、總共3層的完全二叉樹，其結點數(shù)至少有_個。(A)3(B)4(C)7(D)859、隊列操作的原則是_。(A)先進先出 (B)

15、后進先出(C)只能進行插入(D)只能進行刪除60、在有n個結點的二叉鏈表中，值為非空的鏈域的個數(shù)為_.(A)n-1(B)2n-1(C)n+1(D)2n+161、在具有n個結點且為完全二叉樹的二叉排序樹中查找一個關鍵值，其平均比較次數(shù)的數(shù)量級為_。（A）O(n) (B)O(log2n) (C)O(nlog2n) (D)O(n2)62、下列排序算法中，時間復雜度不受數(shù)據(jù)初始狀態(tài)影響，恒為O（log2n）的是_。(A)堆排序(B)冒泡排序(C)簡單選擇排序(D)快速排序63快速排序的記錄移動次數(shù)（ ）比較次數(shù)，其總執(zhí)行時間為O(nlog2n)。 大于 大于等于 小于等于 小于64棧操作的原則是（）

16、先進先出后進先出棧頂插入棧頂刪除65設矩陣A是一對稱矩陣(aij=aji,1=i,j=8)，若每個矩陣元素占3個單元，將其上三角部分（包括對角線）按行序為主序存放在數(shù)組B中，B的首地址為1000，則矩陣元素a67的地址為（） 1031 1093 1096 103266、設數(shù)組Data0.m作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作的語句為（ ）front=front+1 front=(front+1)% mrear=(rear+1)%m front=(front+1)%(m+1)67、深度為6（根的層次為1）的二叉樹至多有（ ）結點。i. 64 32

17、31 6368、將含100個結點的完全二叉樹從根這一層開始，每層上從左到右依次對結點編號，根結點的編號為1。編號為49的結點X的雙親編號為（ ）24 25 23 無法確定69、堆是一個鍵值序列k1,k2, kn,對i=1,2,|_n/2_|,滿足( )kik2ik2i+1 kik2i+1next=p-next; p-next=s; Bq-next=s; s-next=p;Cp-next=s-next; s-next=p; Dp-next=s; s-next=q;80、一棵深度為k的滿二叉樹有（ ）個結點。 A2k -1 B2k-1 C2k D2k81、在一個單鏈表HL中，若要向表頭插入一個由指

18、針p指向的結點，則執(zhí)行 。 A、HL = p; p-next = HL; B、p-next = HL; HL = p; C、p-next = HL; p = HL; D、p-next = HL-next; HL-next = p;82、在一個單鏈表HL中，若要刪除由指針q所指向結點的后繼結點，則執(zhí)行 。 A、p = q-next ; p-next = q-next; B、p = q-next ; q-next = p; C、p = q-next ; q-next = p-next; D、q-next = q-next-next; q-next = q;83、棧的插入與刪除操作在 進行。 A、棧

19、頂 B、棧底 C、任意位置 D、指定位置84、在一個循環(huán)順序隊列中，隊首指針指向隊首元素的 位置。 A、前一個 B、后一個 C、當前 D、后面85、由權值分別為3,8,6,2,5的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為_。 A、 24 B、 48 C、 72 D、 5386、當利用大小為N的一維數(shù)組順序存儲一個棧時，假定用top=1表示?？?，則向這個棧插入一個元素時，首先應執(zhí)行 語句修改top指針。 Atop+； Btop-； Ctop=NULL ； Dtop；87、線性表采用鏈式存儲時，其地址 。 A必須是連續(xù)的 B部分地址必須是連續(xù)的 C一定是不連續(xù)的 D連續(xù)與否均可以88、設有一個

20、廣義表為A(a)，其表尾為（ ）。A: a B: ( ) C: （） D: (a)89、與鄰接矩陣相比，鄰接表更適合于存儲 ( )。A: 無向圖 B: 連通圖 C: 稀疏圖 D: 稠密圖 90、帶頭結點的單鏈表first為空的判定條件是：A. first = NULL; B. first-link = NULL;C. first-link = first; D. first != NULL;91、在一棵樹中，（ ）沒有前驅結點。 A. 分支結點 B. 葉結點 C. 樹根結點 D. 空結點92、在有向圖中每個頂點的度等于該頂點的（ ）。A. 入度 B. 出度C. 入度與出度之和D. 入度與出度之

21、差93、已知一個圖如下所示，從頂點a出發(fā)進行廣度優(yōu)先遍歷可能得到的序列為（）A a c e f b d B a c b d f e C a c b d e f D a c d b f e 94、已知一組關鍵字為25，48，36，72，79，82，23，40，16，35，其中每相鄰兩個為有序子序列。對這些子序列進行一躺兩兩歸并的結果是（）A 25，36，48，72，23，40，79，82，16，35B 25，36，48，72，16，23，40，79，82，35C 25，36，48，72，16，23，35，40，79，82D 16，23，25，35，36，40，48，72，79，82 第 1 頁（

22、共 5 頁）95、折半查找的時間復雜性為（ ）A. O（n2） B. O（n） C. O（nlog n） D. O（log n）96、按照二叉樹的定義，具有3個結點的二叉樹有( )種。A3 B4 C5 D6. 97、一個隊列的入列序列是，則隊列的輸出序列是（）A、4,3,2,1B、1,2,3,4C、1,4,3,2D、3,2,1,498、按照二叉樹的定義，具有3個結點的二叉樹有（ ）種A、3 B、4 C、5 D、699.如圖所示的有向無環(huán)圖可以得到的不同拓撲序列的個數(shù)為（）A.1 B.2C.3 D.4100.下列排序方法中，穩(wěn)定的排序方法為（） A.希爾排序 B.堆排序C.快速排序 D.直接插入

23、排序101、算法設計中，在生成當前結點的孩子結點時，通過一些限界條件即限界函數(shù)，幫助避免生成不包含答案結點子樹的狀態(tài)空間的檢索方法是（ ）A、分枝界限法B、回溯法C、窮舉法 D、遞歸102、算法設計中，將問題的候選解按某種順序逐一枚舉和檢驗，直到候選解滿足所有要求的檢索方法是（ ）A、分枝界限法B、回溯法C、窮舉法D、遞歸法103、算法設計中，不重復，不遺漏地比較所有元素，直到找到需要元素為止，該方法稱為( )A、分枝界限法B、回溯法C、窮舉法D、遞歸法二、填空題1. 對于一個以順序實現(xiàn)的循環(huán)隊列Q0.m_1，隊頭、隊尾指針分別為f,r,其判空的條件是 ，判滿的條件是 。2. 循環(huán)鏈表的主要優(yōu)

24、點是 。3. 一個n*n的對稱矩陣，如果以行或列為主序存入內存，則其容量為 。4. 具有64個結點的完全二叉樹的深度為 。5. 設有一個空棧，現(xiàn)輸入序列為1,2,3,4,5,經過Push,Push,Pop,Push,Pop,Push,Pop,Push后，輸出序列為 。6. 一個具有n個頂點的有向完全圖的弧數(shù)為 。7. 設一棵二叉樹共用50個葉結點（終端結點），則共有 個度為2的結點 。8. 高度為h（h0）的二叉樹，最少有 個結點，最多有 個結點。9、已知某算法的執(zhí)行時間為（n+n2）/2+log2(2n+1)，n代表問題規(guī)模，則該算法的時間復雜度是 。10、數(shù)據(jù)結構有線性結構、樹結構、 、

25、等幾種邏輯結構。11、一個無向連通圖有6個頂點7條邊，則其生成樹有 條邊。12、在一個長度為n的順序表中插入一個元素，最少需要移動 個元素，最多需要移動 個元素。13、如果指針p指向一棵二叉樹的一個結點，則判斷p沒有左孩子的邏輯表達式為 。14、一個55的對稱矩陣采用壓縮存儲，需要存儲_個元素。15、設單鏈表中指針P指向結點A，若要刪除A之后的結點（假設存在），則需要修改指針的操作為_。16、已知二叉樹中葉子數(shù)為50，僅有一個孩子的結點數(shù)為30，則總結點數(shù)_。17、圖1中v3的入度和出度分別為_。18在帶有頭結點的單鏈表L中，若要刪除第一個結點，則需執(zhí)行下列三條語句：；L-next=U-nex

26、t；free(U)；19深度為8（根的層次號為1）的滿二叉樹有個葉子結點。20將一棵有100個結點的完全二叉樹按層編號，則編號為49的結點X，其雙親PARENT（X）的編號為。21設有一個鏈隊，結點結構為data|next，front為隊頭指針，rear為隊尾指針，當執(zhí)行入隊操作時需執(zhí)行下列語句：malloc(p)；p-data=x; p-next=NULL；22、設r指向單鏈表的最后一個結點，要在最后一個結點之后插入s所指的結點，需執(zhí)行的三條語句是_；r=s; r-next=null;。23、已知一棵度為3的樹有2個度為1的結點，3個度為2的結點，4個度為3的結點，則該樹中有_ 個葉子的結點

27、。24、樹有三種常用的存儲結構，即孩子鏈表法、孩子兄弟鏈表法和_ .25在一個帶頭結點的單向循環(huán)鏈表中，p指向尾結點的直接前驅，則指向頭結點的指針head可用p表示為head 。26在有序表（12，24，36，48，60，72，84）中二分查找關鍵字72時所需進行的關鍵字比較次數(shù)為 。27. 若一個算法中的語句頻度之和為T(n)=3720n+4nlogn，則算法的時間復雜度為 。28. 假設以S和X分別表示進棧和退棧操作，則對輸入序列a,b,c,d,e進行一系列棧操作SSXSXSSXXX之后，得到的輸出序列為 。29. 串S=“I am a worker”的長度是 。30.在含100個結點的完

28、全二叉樹中，葉子結點的個數(shù)為 。31.如果排序過程不改變 之間的相對次序，則稱該排序方法是穩(wěn)定的。32算法有五個特征它們是 、 、可行性、輸入和輸出。33棧是限定僅在 進行插入和刪除的線性表。34具有64個結點的完全二叉樹的深度為 。35數(shù)據(jù)結構講述的三大關系是 、 、 。36已知二叉樹中的葉子樹為50，僅有一個孩子的結點數(shù)為30，則總結點數(shù)為 。37隊列的原則是 。38已知某算法的執(zhí)行時間為n+n2,n代表問題規(guī)模，則該算法的時間復雜度是 。39數(shù)據(jù)結構有線性結構、樹結構、 、 等幾種邏輯結構。40棧的原則是 。41順序存儲的隊列如果不采用循環(huán)方式，則會出現(xiàn) 問題。42設一顆完全二叉樹共有5

29、0個葉子結點，則它共有_個度為2的結點。43對于一個順序棧作進棧運算時，應先判斷棧是否為 ，判斷的條件是 ，作出棧運算時，應先判斷棧是否為 ，判斷的條件是 。44在一棵二叉樹上第5層的結點數(shù)最多為 。45.將指向單鏈表中的某個結點的指針p移動到該結點的后繼結點表示為 。46. 總共三層的完全二叉樹，其結點數(shù)至少有 個，至多有 個。47. 二叉樹的遍歷方法有 、 、 。48、鏈表對于數(shù)據(jù)元素的插入和刪除不需移動結點，只需改變相關結點的_域的值。49、一棵樹的廣義表表示為a (b (c, d (e, f), g (h) ), i (j, k (x, y) ) )，結點f的層數(shù)為_。假定根結點的層數(shù)

30、為0。50、n (n0) 個頂點的無向圖最多有_條邊，最少有_條邊。51、在隊列中，允許進行插入操作的一端稱為，允許進行刪除操作的一端稱為。52、設”good”,S2=”book”,則，和依次聯(lián)接后的結果是。53、若按層次順序將一棵有n個結點的完全二叉樹的所有結點從1到n編號，那么當2in,則結點i無 ；若2i+1n，則結點i無 。54、在有序表（12，24，36，48，60，72，84）中二分查找關鍵字72時所需進行的關鍵字比較次數(shù)為 。55在單鏈表中設置頭結點的作用是_。56設廣義表L=（a），則該廣義表的長度是 ，深度是 。57若一個二叉樹含有n個結點，則它的二叉鏈表中必有 個空的鏈域。

31、58、在雙鏈表中，存儲一個結點有三個域，一個是數(shù)據(jù)域；另兩個是指針域，分別指向 _和_。 59、在循環(huán)列隊中，設隊頭指針front指向隊頭元素前一個空閑元素，隊尾指針指向隊尾元素，那么，隊空標志為_，隊滿標志為_。60、設廣義表C=( (x,(a,b) ),y ) ), 則C的長度為_,深度為_61、在一棵具有n個結點的完全二叉樹中，從樹跟起，自上而下、自左而右地給所有結點編號。設跟結點編號為1。若編號為i的結點，有右孩子，那么其右孩子的編號為_；若編號為i的結點，有父結點，那么其父結點的編號為_。62、有一稠密圖G，則G采用_存儲較省空間。設有一稀疏圖G，則采用_存儲較省空間。63、數(shù)據(jù)結構的存儲結構包括順序、_、索引和散列等四種。64、在鏈表中進行插入和 操作的效率比在順序存儲結構中進行相同操作的效率高。65、對于隊列，只能在插入元素，在刪除元素。66、當線性表很少做插入刪除操作時，應采用存儲結構為好。67在二叉樹第h層上最多有個結點。68關鍵路徑的長度是完成整個工程所需要的最_時間。69、下面樹的先序、中序、后續(xù)遍歷的結果依次為_、_、_abcfdeea70、cf 將左邊的森林轉換為二叉樹為b_ 71、線性結構中元素之間