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

緒論一、填空題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) )。數(shù)據(jù)項4.(數(shù)據(jù)元素)是數(shù)據(jù)的基本單位，)是數(shù)據(jù)不可分割的最小單位。(5.線性結(jié)構(gòu)中元素之間存在(一個對一個 )關(guān)系，樹形結(jié)構(gòu)中元素之間存在 (一個對多個 )關(guān)系，圖多個對多個)關(guān)系。狀結(jié)構(gòu)中元素之間存在 (數(shù)據(jù)元素關(guān)？ 6.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中：計算機的()以及它們之間的(系 )和 (運籌 )等的學(xué)科。7.算法的五個重要特性為有窮性、確定性、(輸入 )、(輸出 )和 (可行性 )。二、選擇題1.數(shù)據(jù)的不可分割的基本單位是(D)。A.元素 B.結(jié)點C.數(shù)據(jù)類型D.數(shù)據(jù)項*2. 線性表的邏輯順序與存儲順序總是一致的，這種說法(B)。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.線性結(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)一、填空題n-i1.在一個長度為 n 的線性表中刪除第 i 個元素（ 1 i n）時， 需向前移動 ()個元素。2.從循環(huán)隊列中刪除一個元素時，其操作是(先移動隊首指針，后取出元素)。p-next3.在線性表的單鏈接存儲中，若一個元素所在結(jié)點的地址為p，則其后繼結(jié)點的地址為()。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-top(-)；進棧操作時要執(zhí)行的語句序列中有 S-top(+)。9.順序表中邏輯上相鄰元素的物理位置 (一定 )緊鄰；單鏈表中 邏輯上相鄰元素的物理位置 (不一定緊鄰。10.在 (循環(huán) )鏈表中，從任何一結(jié)點出發(fā)都能訪問到表中的所有結(jié)點。11. 棧和隊列均是 ( 運算受限 ) 的線性表，棧的特點是 ( 先進后出 后進先出 ) ；隊列的特點是 ( 先進先出 后進后出 )。12.通常，在程序中使用的串可分為串常量和串變量；而串按存儲方式又可分為(定長順序存儲 )和(堆分配存儲 )。13.循環(huán)隊列頭指針front 指向隊頭元素，隊尾指針rear 指向隊尾元素后的一個空閑元素，隊列的最大空間為Queuelen 。 在 循 環(huán) 隊 列 中，隊空標志為(front=rear隊滿標志為) ，(（rear+1）%max=front)。 當 rear=front時，隊列長度為 (rear-front)，當 rearnext=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.在雙向鏈表中，每個結(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 )=()。（本人不會）二、選擇題1.在一個單鏈表中，若q 所指結(jié)點是 p 所指結(jié)點的前驅(qū)結(jié)點，若在q 與 p 之間插入一個 s 所指的結(jié)A點，則執(zhí)行 ( )。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( )。A.R-F B.n+R-F C.(R-F+1)modn D.(n+R-F)mod n3.如下陳述中正確的是(A)。A.串是一種特殊的線性表B.串的長度必須大于零C.串中元素只能是字母D.空串就是空白串4.若讓元素 1，2， 3 依次進棧，則出棧次序不可能出現(xiàn)(C)的情況。A.3， 2， 1 B.2， 1， 3C.3， 1， 2D.1，3， 25.判定一個隊列QU（最多元素為m0 ）為空的條件是(C)。A.QU-rear-QU-front=m0B.QU-rear-QU-front-1=m0C.QU-front=QU-rearD.QU-front=QU-rear+16.設(shè)目標串S= abcdef，模式串p= de，則第 (C)次匹配成功。A.1B.2C.4D.57. 設(shè) 字 符 串 s1= ABCDEFG，S2= PQRST，T ， sub1 ， sub2為 空 串。 則運算s=Concat(T ，SubString(sub1 ， s1， 2， SubLength(s2)， SubString(sub2， s1， SubLength(s2)， 2)后的串 T 值為(D)。A. BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF8.一個順序線性表第一個元素的存儲地址是100，每個元素的長度為2，則第 5個元素的地址是(B)。A.100B.108C.110D.120C9.非空的循環(huán)單鏈表 head 的尾結(jié)點（由p 所指向）滿足 ( )。A.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/2C.nD.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=“ ABCDEFG，”S2=“ PQRST，”函數(shù) StrCat(x,y)返回 x 和 y 串的連接串，函數(shù)StrSub(S， i， j)返回串 S的從序號 i 的字符開始的j 個字符組成的子串，StrLen(S)返回串 S的長度，則 StrCat(StrSub(S1，2， StrLen(S2)， StrSub(S1，StrLen (S2)， 2)的結(jié)果串是 (D)。A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF16.學(xué)生成績表是一種(C)結(jié)構(gòu)。A.圖形B.樹形C.線性D.集合17.在一個鏈隊中，假設(shè)f 和 r 分別為隊首和隊尾指針，則插入s 所指結(jié)點的運算時A.f-next=s;f=s;B.r-next=s; r=s;C.s-next=r; r=s;D.s-next=f; f=s;18.向順序表中的i 位置處插入元素，下面哪項能夠準確的表明(C)。i 的位置是合法的。(D)A.il-length+1B.i=1C.i=l-length+1D.1=ilength+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-next=s-next;s-next=p;D.p-next=s; s-next=q;20.一個棧的入棧序列為a， b， c， d， e，則出棧序列不可能的是 (C)。A.edcba B.dcbaeC.dceab D.abcdeB21.如果以鏈表作為棧的存儲結(jié)構(gòu)，則出棧操作時( )。A.必須判別棧是否滿B.必須判別棧是否為空C.必須判別棧元素類型D.可不做任何判斷22.設(shè)有兩個串p 和 q，求 q 在 p 中首次出現(xiàn)的位置的運算稱為(B)。A.連接B.模式匹配C.求子串D.求串長23.p 指向線性鏈表中的某一結(jié)點，則在線性鏈表的表尾插入結(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.向順序棧中壓入新元素時，應(yīng)當(A)。A.先移動棧頂指針，再存入元素B.先存入元素，再移動棧頂指針C.先后次序無關(guān)緊要D.同時進行25.假定一個順序隊列的隊首和隊尾指針分別為f 和 r ，則判斷隊空的條件為(D)。f+1=rB.r+1=f C.f=0D.f=r26.棧的插入和刪除操作在(A)進行。A.棧頂 B.棧底C.任意位置D.指定位置27.棧和隊列的共同點是C( )。A.都是先進后出B.都是先進先出C.只允許在端點處插入和刪除元素D.沒有共同點28.若 6 行 8 列的數(shù)組以列序為主序順序存儲，基地址為1000， 每個元素占2 個存儲單元，則第 5行第 3 列的元素 (假定無第 0行第 0列 )的地址是 (B)。A.1086 B.1032C.1068D.答案 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 中，刪除第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ū)結(jié)點；葉子結(jié)點(沒有 )后繼結(jié)點，其余每個結(jié)點都可以有(一或多個 )個后繼結(jié)點。2n-19.在最優(yōu)二叉樹中沒有度為1 的結(jié)點，則一棵有n 個葉子結(jié)點的最優(yōu)二叉樹中共有()個結(jié)點。10.深度為 4（設(shè)根的層數(shù)為4)個結(jié)點，至多有15)個結(jié)點，第2 -11）的二叉樹至少有 (i 層上至多有 ( n)個結(jié)點。6634 層上至多有11.深度為 6（設(shè)根的層數(shù)為 1）的二叉樹至少有 ( )個結(jié)點，至多有( )個結(jié)點，第(8)個結(jié)點。A.nB. N+1C.n-1D.不確定注： 1:B2:D3:A5.下面 (A)是對的。4:BA.哈夫曼樹中結(jié)點的度只可能是0 和 2。 B.二叉樹的順序存儲中，是以先序遍歷存儲結(jié)點的。C.完全二叉樹實際上就是滿二叉樹。D.一棵二叉樹第i 層的最大結(jié)點數(shù)為2i-1。6.將含 100 個結(jié)點的完全二叉樹從根這一層開始，每層上從左到右依次對結(jié)點編號，根結(jié)點的編號為 1。編號為 49 的結(jié)點 X 的右孩子編號為 (B)。 A.98 B.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.79.由權(quán)值分別為 11， 8，6， 2， 5 的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為B( )。A.24B.71C.48D.5310. 一個具有 767 個結(jié)點的完全二叉樹， 其葉子結(jié)點個數(shù)為 (B)。 A.382 B.384 C.385 D.38611. 在一棵具有 35 個結(jié)點的完全二叉樹中，該樹的深度為 (A)。A.6 B.7C.5 D.812. 由三個結(jié)點構(gòu)成的二叉樹，共有 (B)種不同的結(jié)構(gòu)。A.3B.4 C.5 D.613.深度為k 的二叉樹至多有(2K-1)個結(jié)點(k 。1)A.2kB.2k-1C.2k-1D.2k三、簡答題1.已知一棵二叉樹的先序遍歷和中序遍歷，則該二叉樹的后序遍歷是什么？先序遍歷： A，B， C， D， E，F(xiàn)， G， H，I， J中序遍歷： C，B，A， E，F(xiàn)， D， 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;帶權(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 表示空，請分別寫出二叉的先序、中序、后序遍歷序列。1234567891011121320846515300001018035解：先序序列： 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)換成森林。BAEGKCFHILJ四、論述題1.由分別帶權(quán)為 3， 12，9， 2， 5，7 的葉子結(jié)點構(gòu)造一棵哈夫曼樹，并計算該樹的帶權(quán)路徑長度。解:帶權(quán)路徑長度為 :91圖狀結(jié)構(gòu)一、填空題1.若一個圖的頂點集為a， b， c，d， e， f，邊集為 (a， b)， (a， c)， (b， c)， (d，e),則該圖含有 (3個連通分量。2.具有 10個頂點的無向圖，邊的總數(shù)最多為(45)。3.圖的廣度優(yōu)先搜索遍歷類似于樹的(按層次 )遍歷的過程。4.在無向圖 G 的鄰接矩陣 A 中，若 Aij 等于 1，則 Aji 等于 (1)。深度)優(yōu)先搜索遍歷算法是一種遞歸算法，圖的(廣度) 優(yōu)先搜索遍歷算法需要使用隊列5.圖的 (二、選擇題1.一個有 n 個頂點的無向圖最多有(C)條邊。A.n B.n(n-1)C.n(n-1)/2 D.2n2. 在一個無向圖中， 所有頂點的度數(shù)之和等于所有邊數(shù)的(B)倍。A.3 B.2 C.1 D.1/23.在一個具有n 個頂點的無向圖中，若具有e 條邊，則所有頂點的度數(shù)之為(D)。A.nB.eC.n+eD.2e三、簡答題1.給出如下圖所示的無向圖G 的鄰接矩陣存儲結(jié)構(gòu)。（答案略）2.畫出下圖的鄰接表存儲結(jié)構(gòu)。（答案略）3.給出下圖從 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.設(shè)將整數(shù)1、2、 3、 4 依次進棧，請回答下述問題：1）若入、出棧順序為 Push(1)， Pop()，Push(2)，Push(3)， Pop()， Pop()，Push(4)， Pop()，則出棧的數(shù)字序列是什么？ 2）能否得到出棧序列 1432 和 1423？并說明為什么不能得到或者如何得到？解： (1):1324(2):可以得到 1432不能得到 1423得到 1432 的過程為： Push(1),pop(),push(2),push(3),push(4),pop(),pop(),pop(), 不能得到 1423 無法執(zhí)行此操作3.求出下圖的最小生成樹。4.求出下圖的最小生成樹。（答案略）（答案略）查找一、簡答題1.關(guān)鍵字集合 19， 01， 23， 14， 55， 68， 11， 82， 36，哈希函數(shù)為： H(key)=key MOD 9 構(gòu)建哈希表，采用開放定址法解決沖突。 （答案略）2.關(guān)鍵字集合 19， 14， 23， 01， 68， 20， 84， 27， 55， 11，10，79，哈希函數(shù)為：H(key)=k