數(shù)據(jù)結(jié)構(gòu)考試題庫

1、緒論一、填空題1. 數(shù)據(jù)的邏輯結(jié)構(gòu)被分為集合、 （ 線性結(jié)構(gòu) ） 、 （ 樹形結(jié)構(gòu) ） 和 （ 圖狀結(jié)構(gòu) ） 四種。2. 物理結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計算機中的表示，又稱為 （ 存儲結(jié)構(gòu) ） 。3. 數(shù)據(jù)元素的邏輯結(jié)構(gòu)包括（ 線性） 、 （樹）和圖狀結(jié)構(gòu)3 種類 型， 樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱為 （ 非線性結(jié)構(gòu)） 。4. （ 數(shù)據(jù)元素 ） 是數(shù)據(jù)的基本單位， （ 數(shù)據(jù)項 ）是數(shù)據(jù)不可分割的最小單位。5. 線性結(jié)構(gòu)中元素之間存在 （ 一個對一個） 關(guān)系，樹形結(jié)構(gòu)中元素之間 存在 （ 一個對多個 ） 關(guān)系，圖狀結(jié)構(gòu)中元素之間存在（ 多個對多個） 關(guān)系。6. 6. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中

2、：計算機的 （ 數(shù)據(jù)元素 ） 以及它們之間的 （關(guān)系 ）和（運籌 ）等的學(xué)科。7. 算法的五個重要特性為有窮性、確定性、 （輸入 ）、 （輸出 ）和（可行性 ）。二、選擇題1. 數(shù)據(jù)的不可分割的基本單位是（ D） 。A.元素 B.結(jié)點C.數(shù)據(jù)類型 D.數(shù)據(jù)項( B) 。*2. 線性表的邏輯順序與存儲順序總是一致的，這種說法A. 正確B.不正確C.不確定D. 無法選擇3. 線性結(jié)構(gòu)是指數(shù)據(jù)元素之間存在一種 ( D) 。A. 一對多關(guān)系 B. 多對多關(guān)系 C. 多對一關(guān)系 D. 一對一關(guān)系4. 在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成(A) 。A. 動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B. 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.

3、 線性結(jié)構(gòu)和非線性結(jié)構(gòu)D. 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)5. 線性表若采用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址 ( D) 。A. 必須是連續(xù)的 B. 部分地址必須是連續(xù)的 C. 一定是不連續(xù)的 D. 連 續(xù) 不 連續(xù)都可以三、簡答題1. 算法的特性是什么。答：有窮性 確定性 可行性 有 0 或多個輸入 有 1 或多個輸出線性結(jié)構(gòu)、填空題1 .在一個長度為n的線性表中刪除第i個元素（1&i & n）時，需向前移動（n-i ） 個元素。2. 從循環(huán)隊列中刪除一個元素時，其操作是（ 先移動隊首指針，后取出元素 ） 。3. 在線性表的單鏈接存儲中，若一個元素所在結(jié)點的地址為p,則其后繼結(jié)

4、點的地址為 （ p->next ） 。4. 在一個單鏈表中指針p 所指向結(jié)點的后面插入一個指針 q 所指向的結(jié)點時，首先把 （ p->next ） 的值賦給 q->next ，然后 （ q->date ） 的值賦給 p->next 。5. 從一個棧刪除元素時，首先取出 （棧頂元素 ） ，然后再使（棧頂指針 ） 減 1。6. 子串的定位操作通常稱做串的 （ 模式匹配 ） 。7. 設(shè)目標T= 'abccdcdccbaa',模式 P= 'cdcc'則第（六）次匹配成功。8. 順序棧 S 中 ， 出 棧操作時 要執(zhí)行的 語句序列 中有 S-

5、>top（ - ） ； 進棧 操作時要執(zhí)行的語句序列中有S->top（ +） 。9. 順序表中邏輯上相鄰元素的物理位置（ 一定 ） 緊鄰； 單鏈表中 邏輯上相鄰元素的物理位置（ 不一定 ） 緊鄰。10. 在（循環(huán) ）鏈表中，從任何一結(jié)點出發(fā)都能訪問到表中的所有結(jié)點。11. 棧和隊列均是（運算受限 ）的線性表，棧的特點是（先進后出 后進先出 ） ；隊列的特點是 （ 先進先出 后進后出 ） 。12. 通常， 在程序中使用的串可分為串常量和串變量； 而串按存儲方式又可分為( 定長順序存儲 ) 和 ( 堆分配存儲) 。13. 循環(huán)隊列頭指針 front 指向隊頭元素， 隊尾指針 rear

6、指向隊 尾元素后的一 個 空 閑 元 素 ， 隊 列 的 最 大 空 間 為 Queuelen 。 在 循 環(huán) 隊 列 中 ， 隊 空 標 志 為 ( front=rear ) ， 隊滿標志為 ( ( rear+1 ) %max=front) 。當 rear>=front 時，隊列長度為 ( rear-front ) ，當 rear<front 時，隊列 長度為 ( rear-front+max ) 。14. 在一個長度為n的線性表中的第i個元素(1&i&n)之前插入一個元素時， 需向后移動( n-i+1 )個元素。15. 在具有 n 個單元的循環(huán)隊列中，隊滿時共有

7、( n-1 ) 個元素。16. 帶有一個頭結(jié)點的單鏈表Head為空的條件是(Head->next=null )。17. 在 一 個 單 鏈 表 中 刪 除 指 針 p 所 指 向 結(jié) 點 的 后 繼 結(jié) 點 時 ， 需 要 把 ( p->next->next ) 值賦給 p->next 指針域。18. 一個順序循環(huán)隊列存于 aM 中， 假定隊首和隊尾指針分別 為 front 和 rear ， 則 判 斷 隊 空 的 條 件 為 ( a.front=a.rear ) ， 判 斷 隊 滿 的 條 件 為 ( ( a.rear+1 ) %M=a.front ) 。19. 在雙

8、向鏈表中，每個結(jié)點有兩個指針域，一個指向其( 前驅(qū) ) 結(jié)點，另一個 指向其 ( 后繼 ) 結(jié)點，最后一個結(jié)點的 ( 后繼結(jié)點 ) 指針域為空。*20. 若 D=(a ， (b ， c)， e ， a) ， 則 Head( D )=()，Tail( D )=() ， Head(Tail( D )=() 。(本人不會)21. 在循環(huán)鏈表中，每個結(jié)點有( 一個 ) 個指針域，指向其( 后繼 ) 結(jié)點，最后一個結(jié)點的指針域 ( 為空 ) 。*22. 若 S=(a ， (b ， c) ， e ， d) ， 則 Head( S )=( )， Tail( S)=() ， Head(Tail( S )=()

9、 。(本人不會)二、選擇題1. 在一個單鏈表中，若q 所指結(jié)點是 p 所指結(jié)點的前驅(qū)結(jié)點，若在 q 與 p 之間插入一個 s 所指的結(jié)點，則執(zhí)行( A) 。A.s->link=p->link; p->link=s; B.p->link=s; s->link=q;C.p->link=s->link; s->link=p; D.q->link=s; s->link=p;2. 對于順序存儲的隊列，存儲空間大小為n,頭指針為F,尾指針為R。若在邏輯上看一個環(huán)，則隊列中元素的個數(shù) (A) oA.R-F B.n+R-F C.(R-F+1)mod

10、n D.(n+R-F)mod n3. 如下陳述中正確的是(A) 。A. 串是一種特殊的線性表B. 串的長度必須大于零C. 串中元素只能是字母D.空串就是空白串4. 若讓元素 1， 2， 3 依次進棧，則出棧次序不可能出現(xiàn)( C)的情況。A.3， 2， 1B.2 ， 1 ， 3 C.3， 1， 2 D.1 ， 3， 25. 判定一個隊列QU (最多元素為m。為空的條件是(C)。A.QU->rear-QU->front=m0 B.QU->rear-QU->front-1=m0C.QU->front=QU->rear D.QU->front=QU->r

11、ear+16. 設(shè)目標串S= 'abcdef',模式串p= 'de',則第(C)次匹配成功。A.1B.2C.4D.57. 設(shè)字符串 s1=ABCDEF，G S2=PQRS，TT， sub1 ， sub2 為空串 。 則運算 s=Concat(T ， SubString(sub1 ， s1 ， 2 ， SubLength(s2) ， SubString(sub2 ， si, SubLength(s2) , 2)后的串 T 值為(D)。A. BCDEFB. BCDEFGC. BCPQRSTD. BCDEFEF8. 一個順序線性表第一個元素的存儲地址是100，每個元素

12、的長度為2，則第5 個元素的地址是( B) 。A.100 B.108C.110D.1209.非空的循環(huán)單鏈表head的尾結(jié)點(由p所指向)滿足(QA.p->next=NULLB.p=NULLC.p->next=headD.p=head10. 在一個鏈隊中，假設(shè)f 和 r 分別為隊首和隊尾指針，則刪除一個結(jié)點的運算時( C) 。A.r=f->next; B.r=r->next;C.f=f->next; D.f=r->next;11. 在一個長度為 n 的線性表中，刪除值為 x 的元素時，需要比較元素和移動元素的總次數(shù)為 ( C) 。A.(n+1)/2B.n/2

13、 C.n D.n+112. 在一個單鏈表中，若要在p 所指向的結(jié)點之后插入一個新結(jié) 點，則需要相繼修改 ( B) 個指針域的值。A.1B.2C.3D.413. 線性結(jié)構(gòu)中，每個結(jié)點 ( C) 。A. 無直接前驅(qū)B. 只有一個直接前驅(qū)和個數(shù)不受限制的直接后繼C. 只有一個直接前驅(qū)和后繼 D. 有個數(shù)不受限制的直接前驅(qū)和后繼14. 隊列是限定在( D) 進行操作的線性表。A.中間B.隊頭C.隊尾D.端點15. 設(shè)串 S1=“ABCDEF”，G S2=“PQRS”，T函數(shù) StrCat(x,y) 返回 x 和 y 串的連接串，函數(shù)StrSub(S ， i ， j) 返回串 S 的從序號 i 的字符開

14、始的 j 個字符組成的子串，StrLen(S)返回串 S的長度，貝U StrCat(StrSub(S1 ,2,StrLen(S2) ,StrSub(S1 ,StrLen (S2) ， 2) 的結(jié)果串是(D) 。A.BCDEF B.BCDEFGC.BCPQRST D.BCDEFEF16. 學(xué)生成績表是一種 (C) 結(jié)構(gòu)。A.圖形B.樹形 C. Wt D.集合17. 在一個鏈隊中，假設(shè)f 和 r 分別為隊首和隊尾指針，則插入 s 所指結(jié)點的運算時 ( C) 。A.f->next=s; f=s; B.r->next=s; r=s; C.s->next=r;r=s; D.s->

15、next=f;f=s;18. 向順序表中的 i 位置處插入元素，下面哪項能夠準確的表明( D)i 的位置是合法的。A.i<=1|i>l->length+1 B.i>=1C.i>=l->length+1D.1<=i<=l->length+119. 設(shè)線性鏈表中結(jié)點的結(jié)構(gòu)為( data ， next )，已知指針 q 所 指結(jié)點是指針p所指結(jié)點的直接后繼，若在*q和*p之間插入結(jié)點*s,則應(yīng)執(zhí)行(A)操作。A.s->next=p->next;p->next=s;B.q->next=s; s->next=p;C.p-

16、>next=s->next;s->next=p;D.p->next=s;s->next=q;20. 一個棧的入棧序列為 a， b， c， d， e ，則出棧序列不可能的是( C) 。A.edcba B.dcbaeC.dceabD.abcde21. 如果以鏈表作為棧的存儲結(jié)構(gòu)，則出棧操作時( B) 。A. 必須判別棧是否滿B. 必須判別棧是否為空C. 必須判別棧元素類型D. 可不做任何判斷22. 設(shè)有兩個串p和q,求q在p中首次出現(xiàn)的位置的運算稱為(B)。A. 連接 B. 模式匹配C. 求子串 D. 求串長23. p 指向線性鏈表中的某一結(jié)點，則在線性鏈表的表尾插入

17、結(jié)點 S 的語句序列是(A)A.while(p->next!=NULL) p=p->next; p->next=s; s->next=N ULL;B.while(p!=NULL) p=p->next; p->next=s; s->next=NULL;C.while(p->next!=NULL) p=p->next; s->next=p;p->next=NULL;D.while(p!=NULL) p=p->next->next;->next;p->next=s;s->next=p24. 向順序棧中壓入

18、新元素時，應(yīng)當 ( A) 。A. 先移動棧頂指針，再存入元素 B. 先存入元素，再移動棧頂指針C. 先后次序無關(guān)緊要D. 同時進行(D)。25. 假定一個順序隊列的隊首和隊尾指針分別為 f 和 r ， 則判斷隊空的條件為f+1=r B.r+1=fC.f=0 D.f=r26. 棧的插入和刪除操作在( A) 進行。A.棧頂 B.棧底C.任意位置D.指定位置27. 棧和隊列的共同點是( C) 。A. 都是先進后出 B. 都是先進先出C. 只允許在端點處插入和刪除元素D. 沒有共同點28. 若 6 行 8 列的數(shù)組以列序為主序順序存儲，基地址為 1000， 每個元素占 2個存儲單元，則第5 行第 3

19、列的元素 （假定無第 0行第 0 列） 的地址是 （ B） 。A.1086B.1032 C.1068 D.答案 A, B, C 都不對29. 設(shè)有 50 行的二維數(shù)組A5060 ，其元素長度為 2 字節(jié)，按 行優(yōu)先順序存儲，基地址為100,則元素A1825的存儲地址 為（D）。A.1850B.2188C.1950D.2310三、論述題1. 寫出線性表的插入算法、刪除算法。解：太麻煩略略略*2.畫出主串為ababcabcacbab',子串為abc'的模式匹配過程。解：四、算法設(shè)計題1. 在帶頭結(jié)點的單鏈線性表L 中第 i 個位置之前插入新的元素e。略2. 在帶頭結(jié)點的單鏈線性表L

20、 中，刪除第 i 個元素，并由 e 返回 其值。樹形結(jié)構(gòu)一、填空題1. 赫夫曼樹，又稱最優(yōu)樹，是一類( 帶權(quán)路徑 ) 長度最短的樹。2. 在一棵二叉樹中，第 5 層上的結(jié)點數(shù)最多為 ( 16)個。3. 一棵高度為 5 的二叉樹中最少含有( 5)個結(jié)點，最多含有(31)個結(jié)點。4. 若一棵二叉樹中有8 個度為 2 的結(jié)點，則它有( 9) 個葉子。5. 一棵深度為 6 的滿二叉樹有( 31)個非終端結(jié)點。6. 樹中結(jié)點A的(子樹數(shù))稱為結(jié)點A的度。7. 對一棵二叉排序樹進行中序遍歷時，得到的結(jié)點序列是一個( 升序序列 ) 。8. 在樹型結(jié)構(gòu)中，根結(jié)點沒有前驅(qū)結(jié)點，其余每個結(jié)點有且僅有(一) 個前驅(qū)

21、結(jié)點；葉子結(jié)點 ( 沒有 ) 后繼結(jié)點，其余每個結(jié)點都可以有( 一或多個 ) 個后繼結(jié)點。9. 在最優(yōu)二叉樹中沒有度為 1 的結(jié)點，則一棵有n 個葉子結(jié)點的最優(yōu)二叉樹中共有 ( 2n-1 ) 個結(jié)點。10. 深度為4(設(shè)根的層數(shù)為1) 的二叉樹至少有(4) 個結(jié)點， 至多有 ( 15)個結(jié)點，第 i 層上至多有( 2n-1 ) 個結(jié)點。11.深度為6 （設(shè)根的層數(shù)為1）的二叉樹至少有（6）個結(jié)點，至多有（63）個結(jié)點，電4層扁逸#8）個結(jié)點。1 .具有65個結(jié)點的完全二叉樹的高度為（）。A. 8B.7C, 6D,52 .有n（n>0）個結(jié)點的完全二叉樹的深度是（）0A. log2（n）B

22、. log2（n） + 1C log式九 + 1）|D. log2（n）J + 13 .在一棵完全二叉樹中，若編號為i的的結(jié)點存在左孩子 左孩子結(jié)點的編號為（）。A.2iB.2i-1C. 2i+1D+ 2i+24 . 一棵n個結(jié)點的二叉樹，其空指針域的個數(shù)為（）。A. nB, n+1C, n-1D.不確定A.n B. N+1 C.n-1 D.不確定注： 1:B 2:D 3:A 4:B5 . 下面 (A) 是對的。A. 哈夫曼樹中結(jié)點的度只可能是0 和 2 。 B. 二叉樹的順序存儲中，是以先序遍歷存儲結(jié)點的。C. 完全二叉樹實際上就是滿二叉樹。 D. 一棵二叉樹第 i 層的最大結(jié)點數(shù)為 2i-

23、1 。6 . 將含 100 個結(jié)點的完全二叉樹從根這一層開始，每層上從左到右依次對結(jié)點編號，根結(jié)點的編號為 1 。編號為 49 的結(jié)點 X 的右孩子編號為 ( B) 。A.98B.99 C.24 D. 無法確定7 .先序為A, B, C且后序為C, B, A的二叉樹共有(B)種。A.3B.4C.5D.68. 在一棵度為 3 的樹中，度為 3 的結(jié)點個數(shù)為 2 ，度為 2 的結(jié)點個數(shù)為 1，則度為 0 的結(jié)點個數(shù)為 ( C) 。A.4B.5C.6D.7它的帶權(quán)路徑長度為 ( B) 。9. 由權(quán)值分別為 11， 8， 6， 2， 5 的葉子結(jié)點生成一棵哈夫曼樹，A.24B.71C.48D.5310

24、. 一個具有 767 個結(jié)點的完全二叉樹， 其葉子結(jié)點個數(shù)為 ( B)A.382 B.384C.385D.38611. 在一棵具有35 個結(jié)點的完全二叉樹中， 該樹的深度為 ( A) 。A.6B.7C.5D.812. 由三個結(jié)點構(gòu)成的二叉樹，共有( B) 種不同的結(jié)構(gòu)。A.3B.4C.5 D.613. 深度為k的二叉樹至多有（211）個結(jié)點（1<>1）。A.2k B.2k-1C.2k-1 D.2k三、簡答題1,已知一棵二叉樹的先序遍歷和中序遍歷，則該二叉樹的后序遍歷是什么？先序遍歷：A, B, C, D, E, F, G, H, I , J中序遍歷：C, B, A, E, F, D

25、, I , H, J, G解：后序遍歷：C.B.F,E,I,J,H,G.D.A2.如下圖的森林轉(zhuǎn)化為二叉樹。解：此題沒法寫 略略略3 .已知某二叉樹的前序序列為EBADCFHGI,中序序列為ABCDEFGHI請給出二叉樹且寫出二叉樹的后序 序列。解：二叉樹略后序序列 :A,C,D,B,G,I,H,F,E4 . 試用權(quán)集合6 ， 4， 8， 3， 7， 5， 10， 8， 2， 1 ， 11 ，構(gòu)造 哈夫曼 (Huffman) 樹。(1) 畫出這棵哈夫曼樹； (2) 分別計算該哈夫曼樹的路徑長度和帶權(quán)路徑長度。解： (1) 略(2) 路徑長度為： 1x2+2x4+3x8+4x3+5x2=60;帶

26、權(quán)路徑長度為： 3x(6+7+8+8+10+11)+4x(3+4+5)+5x(1+2)=2135 .試按表(10, 18, 9, 2, 20, 5, 6, 15, 19, 25)中元素的排 列次序，將所有元素插入一棵初始為空的二叉排序樹中，使 之仍是一棵二叉排序樹。(1)試畫出插入完成之后的二叉排序樹；(2)若查找元素2,它將依次與二叉排序樹中哪些元素比較大小？ (3)對該樹進行中序遍歷，試寫出中序遍歷序列。解：(1)略(2)10,9,2(3)2,5,6,9,10,15,18,19,20,256 .已知一棵二叉樹的順序存儲表示如下，其中 0表示空，請分別寫出二叉的先序、中序、后序遍歷序列。12

27、34567891011121320846515300001018035解：先序序列：20,8,5,15,10,18,46,30,35中序序歹5,8,10,15,18,20,30,35,46后序序列：5,10,18,15,8,35,30,46,207 .將如下圖的一般樹轉(zhuǎn)化為二叉樹。8.將下圖中的二叉樹轉(zhuǎn)換成森林四、論述題1 .由分別帶權(quán)為3, 12, 9, 2, 5, 7的葉子結(jié)點構(gòu)造一棵哈夫曼樹，并計算該樹的帶權(quán)路徑長度。解：帶權(quán)路徑長度為：91圖狀結(jié)構(gòu)一、填空題2 .若一個圖的頂點集為a, b, c, d, e, f,邊集為(a , b)3 .具有10個頂點的無向圖，邊的總數(shù)最多為(45)

28、 o4 .圖的廣度優(yōu)先搜索遍歷類似于樹的(按層次)遍歷的過程。5 .在無向圖G的鄰接矩陣A中，若Aij 等于1,則Aji,(a , c) , (b , c) , (d , e),則該圖含有(3)個連通分量等于（1）6 . 圖的 ( 深度 ) 優(yōu)先搜索遍歷算法是一種遞歸算法，圖的 ( 廣度 ) 優(yōu)先搜索遍歷算法需要使用隊列二、選擇題1. 一個有n個頂點的無向圖最多有(C)條邊。A.n B.n(n-1)C.n(n-1)/2 D.2n2. 在一個無向圖中， 所有頂點的度數(shù)之和等于所有邊數(shù)的 ( B) 倍。A.3B.2C.1D.1/23. 在一個具有n 個頂點的無向圖中，若具有e 條邊，則所有頂點的度

29、數(shù)之為 ( D)A.n B.e C.n+e D.2e三、簡答題2.畫出下圖的鄰接表存儲結(jié)構(gòu)（答案略）0 1 01 0 00 0 00 I 11 0 10 11 01 10 11 03.給出下圖從A點出發(fā)的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的頂點 序列。解：深度優(yōu)先遍歷：AECDB廣度優(yōu)先遍歷：AEBDC5.給出從V1點出發(fā)的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的頂點序列解:深度優(yōu)先遍歷；v1 v2 v3 v4 v5 v6 v7 v8 v9廣度優(yōu)先遍歷；v1 v2 v3 v4 v7 v5 v6 v8 v9四、論述題1 .寫出下面帶權(quán)有向圖的的關(guān)鍵路徑解：(1)1->2->5->8->92

30、.設(shè)將整數(shù)1、2、3、4依次進棧，請回答下述問題:1)若入、出棧順序為 Push(1) , Pop() , Push(2) , Push(3),Pop()Pop() , Push(4) , Pop(),則出棧的數(shù)字序列是什么?2)能否得到出棧序列1432和1423?并說明為什么不能得到或者如何得至U?解： (1):1324(2): 可以得到 1432 不能得到 1423得到 1432 的過程為： Push(1),pop(),push(2),push(3),push(4),pop(),pop(),pop(),不能得到 1423 無法執(zhí)行此操作（答案略）（答案略）3.求出下圖的最小生成樹4.求出下圖的最小生成樹。查找一、簡答題MOD91. 關(guān)鍵字集合19 ， 01 ， 23， 14， 55， 68， 11， 82， 36 ，