數(shù)據(jù)結(jié)構(gòu)考試題庫.doc_第1頁
數(shù)據(jù)結(jié)構(gòu)考試題庫.doc_第2頁
數(shù)據(jù)結(jié)構(gòu)考試題庫.doc_第3頁
數(shù)據(jù)結(jié)構(gòu)考試題庫.doc_第4頁
數(shù)據(jù)結(jié)構(gòu)考試題庫.doc_第5頁
已閱讀5頁,還剩19頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

緒論一、填空題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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論