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

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

2、 (D)p-next=p6. 設(shè)一數(shù)列的輸入順序?yàn)?,2,3,4,5,6，通過(guò)棧操作不可能排成的輸出序列為( )(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. 設(shè)字符串S1=ABCDEFG，S2=PQRST，則運(yùn)算S=CONCAT(SUB(S1,2,LENGTH(S2)，SUB(S1,LENGTH(S2),2)的結(jié)果為( )(A) BCQR (B) BCDEF (C) BCDEFG (D) BCDEFEF8. 有一個(gè)10階的對(duì)稱矩陣A,采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一元素，其存儲(chǔ)地址為1，每個(gè)元素占

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

4、連續(xù)的 (B) 部分地址必須是連續(xù)的(C) 一定是不連續(xù)的 (D) 連續(xù)與否均可以12. 設(shè)循環(huán)隊(duì)列Q1.N-1的頭尾指針為F，R，當(dāng)插入元素時(shí)尾指針R加1，頭指針F總是指向隊(duì)列中第一個(gè)元素的前一個(gè)位置，則隊(duì)列中元素計(jì)數(shù)為( )。(A) R-F (B) N-(R-F) (C) (R-F+N)%N (D) (F-R+N)%N13. 完成堆排序的全過(guò)程需要( )個(gè)記錄大小的輔助空間。(A) 1 (B) n (C) nlog2n (D) n214. 若給定關(guān)鍵字集合為20,15,14,18,21,36,40,10，一趟快速排序結(jié)束時(shí)，鍵值的排列為( )(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. 對(duì)于含有n個(gè)頂點(diǎn)e條邊的無(wú)向連通圖，利用Prim算法生成最小代價(jià)生成樹其時(shí)間復(fù)雜度為( ),利用Kruskal的時(shí)間復(fù)雜度為( )。(A) O(log2n) (B) O(n2) (C) O(ne) (D) O(elog2e)17. 具有n個(gè)頂點(diǎn)的完全有向圖的邊數(shù)為( )。(A) n(n-1)/

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

7、 STRUCTURE22. 下列哪種形態(tài)不是樹( )。 （A） （B） （C） （D）23. 下列哪種排序需要的附加存儲(chǔ)開銷最大( )。(A) 快速排序 (B) 堆排序 (C) 歸并排序 (D) 插入排序24. 對(duì)任何一棵樹T，設(shè)n0,n1,n2,nm分別是0,1,2,m的結(jié)點(diǎn)，則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個(gè)頂點(diǎn)的無(wú)向圖的鄰接表中結(jié)點(diǎn)總數(shù)最多有( )個(gè)。(A

8、) 2n (B) n (C) n/2 (D) n(n-1)27. 設(shè)連通圖G的頂點(diǎn)數(shù)為n，則G的生成樹的邊數(shù)為( )。(A) n (B) n-1 (C) 2n (D) 2n-128. 下列哪種排序需要的附加存儲(chǔ)開銷最小( )。(A) 快速排序 (B) 堆排序 (C) 歸并排序 (D) 計(jì)數(shù)排序29. 若按 ( )列出二叉搜索樹中所存儲(chǔ)的元素，則恰好是集合中所有元素從小到大的排序。(A) 先序 (B) 中序 (C) 后序 (D) 按層次30. 在圖1所示的4棵樹中，哪一棵是完全二叉樹( )。 （A） （B） （C） （D）圖131. 下面程序段的時(shí)間復(fù)雜度為( )。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. 采用鏈結(jié)構(gòu)存儲(chǔ)線性表時(shí)，其地址( )。(A) 必須是連續(xù)的 （B）連續(xù)不連續(xù)都可以（C）部分地址必須是連續(xù)的 (D) 必須是不連續(xù)的33. 具有2000個(gè)結(jié)點(diǎn)的二叉樹，其高度至少為( )。(A) 9 (B) 10 (C) 11 (D) 1234. 下列程序的時(shí)間復(fù)雜度為( )。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) 串中所含字符的個(gè)數(shù)n(n

10、0)38. 若有一個(gè)棧的輸入序列是1,2,3,n，輸出序列的第一個(gè)元素是n，則第i個(gè)輸出元素是( )(A) n-i (B) n-i-1 (C) n-i+1 (D) 不確定39. 設(shè)有一個(gè)棧，元素的進(jìn)棧次序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的結(jié)點(diǎn)數(shù)為2個(gè)，度為2的結(jié)點(diǎn)數(shù)為1個(gè)，度為1的結(jié)點(diǎn)數(shù)為2個(gè)，那么度為0的結(jié)點(diǎn)數(shù)有( )個(gè)。(A) 4 (B) 5 (C) 6 (D) 741. 在一個(gè)具有n個(gè)結(jié)點(diǎn)的無(wú)向完全圖中，包含有( )條邊。(A) n(

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

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

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

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

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

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

17、31 6368、將含100個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每層上從左到右依次對(duì)結(jié)點(diǎn)編號(hào)，根結(jié)點(diǎn)的編號(hào)為1。編號(hào)為49的結(jié)點(diǎn)X的雙親編號(hào)為（ ）24 25 23 無(wú)法確定69、堆是一個(gè)鍵值序列k1,k2, kn,對(duì)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的滿二叉樹有（ ）個(gè)結(jié)點(diǎn)。 A2k -1 B2k-1 C2k D2k81、在一個(gè)單鏈表HL中，若要向表頭插入一個(gè)由指

18、針p指向的結(jié)點(diǎn)，則執(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、在一個(gè)單鏈表HL中，若要?jiǎng)h除由指針q所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(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、棧的插入與刪除操作在 進(jìn)行。 A、棧

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

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

21、差93、已知一個(gè)圖如下所示，從頂點(diǎn)a出發(fā)進(jìn)行廣度優(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、已知一組關(guān)鍵字為25，48，36，72，79，82，23，40，16，35，其中每相鄰兩個(gè)為有序子序列。對(duì)這些子序列進(jìn)行一躺兩兩歸并的結(jié)果是（）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 頁(yè)（

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

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

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

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

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

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

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

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

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

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