數(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)包括（線，性）、（林f）和圖狀結(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.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中：計算機的（數(shù)據(jù)元素）以及它們之間的（關(guān)系 和（運籌）等的學科。7.算法的五個

2、重要特性為有窮性、確定性、（輸入）、（輸出）和（可行性）。二、選擇題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.

3、 一定是不連續(xù)的D.連續(xù)不連續(xù)都可以三、簡答題1.算法的特性是什么。答：有窮性確定性可行性有0或多個輸入有1或多個輸出線性結(jié)構(gòu)一、填空題1 在一個長度為n的線性表中刪除第i個元素（1< i產(chǎn)時，需向前移動（n-i）個元素。2 .從循環(huán)隊列中刪除一個元素時，其操作是（先移動隊首指針，后取出元素）。3在線性表的單鏈接存儲中，若一個元素所在結(jié)點的地址為P,則其后繼結(jié)點的地址為（p-> next）。4 .在一個單鏈表中指針p所指向結(jié)點的后面插入一個指針q所指向的結(jié)點時，首先把（p，next）的值賦 給 q->next，然后（q->date）的值賦給 p->next 05

4、.從一個棧刪除元素時，首先取出（棧頂元素），然后再使（棧頂指針）減1。6 .子串的定位操作通常稱做串的（模式匹配）。7 .設(shè)目標丁= ' abccdcdccba,模式P= ' cdc則第（六）次匹配成功。8 .順序棧S中，出棧操作時要執(zhí)行的語句序列中有S->top （-）；進棧操作時要執(zhí)行的語句序列中 有 S->top （+）。9 .順序表中邏輯上相鄰元素的物理位置（一定）緊鄰；單鏈表中邏輯上相鄰元素的物理位置（不一定） 緊鄰。10 .在（循環(huán)）鏈表中，從任何一結(jié)點出發(fā)都能訪問到表中的所有結(jié)點。11 .棧和隊列均是（運算受限）的線性表，棧的特點是（先進后出后進先出）

5、；隊列的特點是（先進先 出后進后出）。12 .通常，在程序中使用的串可分為串常量和串變量；而串按存儲方式又可分為（定長順序存儲）和（堆分配存儲）。13 .循環(huán)隊列頭指針front指向隊頭元素，隊尾指針rear指向隊尾元素后的一個空閑元素，隊列的最大空 間為Queuelen。在循環(huán)隊列中，隊空標志為（front二二rear），隊滿標志為（rear+1 ） %max=front）。當 rear>=front 時，隊列長度為 （rear-front ），當 rearvfront 時，隊列 長度為（rear-front+max ）。14 .在一個長度為n的線性表中的第i個元素（1< i產(chǎn)之

6、前插入一個元素時，需向后移動（n-i+1）個元 素。15 .在具有n個單元的循環(huán)隊列中，隊滿時共有 （n-1）個元素。16 .帶有一個頭結(jié)點的單鏈表Head為空的條件是（Head->next=null）。17 .在一個單鏈表中刪除指針P所指向結(jié)點的后繼結(jié)點時，需要把（p->next->next）值賦給p->next指 針 域。18 .一個順序循環(huán)隊列存于aM中，假定隊首和隊尾指針分別為front和rear，則判斷隊空的條件為(=，判斷隊滿的條件為(+ 1 ) %M=。19 .在雙向鏈表中，每個結(jié)點有兩個指針域，一個指向其(前驅(qū))結(jié)點，另一個指向其(后繼)結(jié)點，最后 一個

7、結(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é)點，則 執(zhí)行(A)。A.s->link=p->link; p-&g

8、t;link=s; >link=s; s->link=q;>link=s->link; s->link=p; >link=s; s->link=p;2 .對于順序存儲的隊列，存儲空間大小為n,頭指針為F,尾指針為R。若在邏輯上看一個環(huán)，則隊列中元素的個數(shù)(A)。+R-F C.(R-F+1)mod n D.(n+R-F)mod n3 .如下陳述中正確的是(A) °A.串是一種特殊的線性表B.串的長度必須大于零C串中兀素只能是字母D.空串就是空白串4 .若讓元素1，2，3依次進棧，則出棧次序不可能出現(xiàn)(C)的情況。，2，1，1，3，1，2，3，2

9、5判定一個隊列QU (最多元素為mO)為空的條件是(C)。>rear-QU->front=mO >rear-QU->front-1 =m0 >front=QU->rear >front=QU->rear+16 .設(shè)目標串S= 'abcdef模式串p= ' de則第(C)次匹配成功。7 .設(shè)字符串 s1= 'ABCDEF，G，S2= 'PQRS，T，sub1，sub2 為空串。則運算 s=Concat(T， SubString(sub1 f s1 f 2 f SubLength(s2)fSubString(sub2f

10、s1fSubLength(s2)f2)后的串 T 值為(D) °A. ' BCDEF B. ' BCDEFG C. ' BCPQRST D. ' BCDEFEF8 .一個順序線性表第一個元素的存儲地址是100，每個元素的長度為2,則第5個元素的地址是(B)o9 .非空的循環(huán)單鏈表head的尾結(jié)點(由p所指向)滿足(C)。>next=NULL =NULL>next=head =head10 .在一個鏈隊中，假設(shè)f和r分別為隊首和隊尾指針，則刪除一個結(jié)點的運算時(C)。=f->next; =r->next;=f->next;

11、=r->next;11 .在一個長度為n的線性表中，刪除值為x的元素時，需要比較元素和移動元素的總次數(shù)為(C)。A.(n+1)/22+112 .在一個單鏈表中，若要在p所指向的結(jié)點之后插入一個新結(jié)點，則需要相繼修改(B)個指針域的13 .線性結(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= " PQRS，函數(shù) StrCat(x,y)返回 x 和 y 串的連接串

12、，函數(shù) StrSub(S, i，j) 返回串S的從序號i的字符開始的j個字符組成的子串，StrLen(S)返回串S的長度， 則StrCat(StrSub(S1, 2， StrLen(S2)， StrSub(S1 » StrLen (S2)， 2)的結(jié)果串是(D) °16 .學生成績表是一種(C)結(jié)構(gòu)。A.圖形B樹形 C線性 D.集合17 .在一個鏈隊中，假設(shè)f和r分別為隊首和隊尾指針，則插入s所指結(jié)點的運算時(C)。>next=s; f=s; >next=s; r=s; >next=r; r=s; >next=f; f=s;18 .向順序表中的i位置

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

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

15、;next=s; s->next=NULL;（p->next!=NULL） p=p->next; s->next=p;p->next=NULL; （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 =r+1 =f =0=r26 .棧的插入和刪除操作在（A）進行。A.棧

16、頂B.棧底C.任意位置D.指定位置27 .棧和隊列的共同點是（C）。A.都是先進后出B.都是先進先出C只允許在端點處插入和刪除元素D.沒有共同點28 .若6行8列的數(shù)組以列序為主序順序存儲，基地址為1000，每個元素占2個存儲單元，則第5行第3列的元素（假定無第0行第。列）的地址是（B）。D.答案A，B，C都不對100 ，則29 .設(shè)有50行的二維數(shù)組A5060，其元素長度為2字節(jié)，按行優(yōu)先順序存儲，基地址為 元素A1825的存儲地址為（D）。三、論述題1 .寫出線性表的插入算法、刪除算法。解：太麻煩略略略*2.畫出主串為ababcabcacbab子串為ab的模式匹配過程。解：四、算法設(shè)計題1

17、 .在帶頭結(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é)點有且僅有（一

18、）個前驅(qū)結(jié)點；葉子結(jié)點（沒有） 后繼結(jié)點，其余每個結(jié)點都可以有（一或多個）個后繼結(jié)點。9在最優(yōu)二叉樹中沒有度為1的結(jié)點，則一棵有n個葉子結(jié)點的最優(yōu)二叉樹中共有（2PI-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é)點的完全二叉樹的高度為（）。B. N+1D.不確定注：1:B 2:D 3:A4:B5 .下面（A）是對的。A.哈夫曼樹中結(jié)點的度只可能是 。和2。B.二叉樹的

19、順序存儲中，是以先序遍歷存儲結(jié)點的。C完全二叉樹實際上就是滿二叉樹。D.一棵二叉樹第i層的最大結(jié)點數(shù)為2i-1。6 .將含100個結(jié)點的完全二叉樹從根這一層開始，每層上從左到右依次對結(jié)點編號，根結(jié)點的編號為1。編 號為49的結(jié)點X的右孩子編號為（B）。D.無法確定7 .先序為A，B，C且后序為C，B，A的二叉樹共有（B）種。8 .在一棵度為3的樹中，度為3的結(jié)點個數(shù)為2，度為2的結(jié)點個數(shù)為1，則度為o的結(jié)點個數(shù)為（C）。9 .由權(quán)值分別為11，8，6，2，5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（B）10 . 一個具有767個結(jié)點的完全二叉樹，其葉子結(jié)點個數(shù)為（B）。11 .在一棵具有

20、35個結(jié)點的完全二叉樹中，該樹的深度為（A） °12 .由三個結(jié)點構(gòu)成的二叉樹，共有（B）種不同的結(jié)構(gòu)。13 .深度為k的二叉樹至多有（2K-1）個結(jié)點（k 。二、簡答題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)化為二叉樹。解：此題沒法寫略略略中序序列為ABCDEFGH，I請給出二叉樹3 .已知某二叉樹的前序序列為EBADCFHGI， 且與出«叉樹的后序序列。解：二叉樹略后序

21、序列：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）樹畫出這棵哈夫曼 樹；（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，它將

22、依次與二叉排序樹中哪些元素比較大 ??？對該樹進行中序遍歷，試寫出中序遍歷序列。解：略(2) 10,9,2(3) 2,5,6,9,10,15,18,19,20,256已知一棵二叉樹的順序存儲表示如下，其中0表示空，請分別寫出二叉的先序、中序、后序遍歷序列。1232084645678910111213515300001018035解：先序序列：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.由分別帶

23、權(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),則該圖含有 個連通分 量。2 .具有10個頂點的無向圖，邊的總數(shù)最多為(45) °3 .圖的廣度優(yōu)先搜索遍歷類似于樹的(按層次)遍歷的過程。4 在無向圖G的鄰接矩陣A中，若等于1，則A皿i等于。5.圖的(深度)優(yōu)先搜索遍歷算法是一種遞歸算法，圖的(廣度)優(yōu)先搜索遍歷算法需要使用隊列二、選擇題1 . 一個有n個頂點的無向圖最多有(C)條邊。(

24、n-1)(n-1)/22 .在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的(B)倍。3在一個具有n個頂點的無向圖中，若具有e條邊， +e三、簡答題1 給出如下圖所示的無向圖G的鄰接矩陣存儲結(jié)構(gòu),2 .畫出下圖的鄰接表存儲結(jié)構(gòu)。（答案略）則所有頂點的度數(shù)之為（D）（答案略）V5V2V5V60 10 0 110 0 1000 0 1 10 I 10 110 1103.給出下圖從A點出發(fā)的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的頂點序列。解：深度優(yōu)先遍歷：AECDB廣度優(yōu)先遍歷：AEBDC5給出從V1點出發(fā)的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的頂點序列v9解：深度優(yōu)先遍歷;v1 v2 v3 v4 v5 v6 v7 v

25、廣度優(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，Pop()，Push，Push，Pop()，Pop()，Push，Pop()，則出棧的數(shù)字 序列是什么？2)能否得到出棧序列1432和1423?并說明為什么不能得到或者如何得到?解：(1):1324 :可以得到1432不能得到1423得至J 1432 的過程為：Push(1)3pop(),push(2),push(3)3push(4),pop()3pop(),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 9 14