1、WORD格式緒論一、填空題1.數(shù)據(jù)的邏輯構(gòu)造被分為集合、(線性構(gòu)造樹(shù)形構(gòu)造)和(圖狀構(gòu)造)四種。)、 (2.物理構(gòu)造是數(shù)據(jù)構(gòu)造在計(jì)算機(jī)中的表示，又稱(chēng)為(存儲(chǔ)構(gòu)造)。非線3.數(shù)據(jù)元素的邏輯構(gòu)造包括(線性樹(shù))、 ( )和圖狀構(gòu)造 3 種類(lèi) 型，樹(shù)形構(gòu)造和圖狀構(gòu)造合稱(chēng)為 (性構(gòu)造 )。數(shù)據(jù)項(xiàng)4.(數(shù)據(jù)元素)是數(shù)據(jù)的根本單位，)是數(shù)據(jù)不可分割的最小單位。(5.線性構(gòu)造中元素之間存在(一個(gè)對(duì)一個(gè) )關(guān)系，樹(shù)形構(gòu)造中元素之間存在 (一個(gè)對(duì)多個(gè) )關(guān)系，圖多個(gè)對(duì)多個(gè))關(guān)系。狀構(gòu)造中元素之間存在 (數(shù)據(jù)元素關(guān)？ 6.數(shù)據(jù)構(gòu)造是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中：計(jì)算機(jī)的()以及它們之間的(系 )和 (運(yùn)籌 )

2、等的學(xué)科。7.算法的五個(gè)重要特性為有窮性、確定性、(輸入 )、(輸出 )和 (可行性 )。二、選擇題1.數(shù)據(jù)的不可分割的根本單位是(D)。A.元素 B.結(jié)點(diǎn)C.數(shù)據(jù)類(lèi)型D.數(shù)據(jù)項(xiàng)*2. 線性表的邏輯順序與存儲(chǔ)順序總是一致的，這種說(shuō)法(B)。A.正確B.不正確C.不確定D.無(wú)法選擇3.線性構(gòu)造是指數(shù)據(jù)元素之間存在一種(D)。A.一對(duì)多關(guān)系 B.多對(duì)多關(guān)系C.多對(duì)一關(guān)系D.一對(duì)一關(guān)系專(zhuān)業(yè)資料整理WORD格式4.在數(shù)據(jù)構(gòu)造中，從邏輯上可以把數(shù)據(jù)構(gòu)造分成(A)。A.動(dòng)態(tài)構(gòu)造和靜態(tài)構(gòu)造B.緊湊構(gòu)造和非緊湊構(gòu)造C.線性構(gòu)造和非線性構(gòu)造D.內(nèi)部構(gòu)造和外部構(gòu)造5.線性表假設(shè)采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造時(shí)，要求內(nèi)存中可用存

3、儲(chǔ)單元的地址 ( D)。A.必須是連續(xù)的 B.局部地址必須是連續(xù)的 C.一定是不連續(xù)的 D.連續(xù)不連續(xù)都可以三、簡(jiǎn)答題1.算法的特性是什么。答：有窮性確定性可行性有 0 或多個(gè)輸入有 1 或多個(gè)輸出線性構(gòu)造一、填空題1.在一個(gè)長(zhǎng)度為 n 的線性表中刪除第 i 個(gè)元素 1 i n時(shí)，需向前移動(dòng) ( )個(gè)元素。n-i2.從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是(先移動(dòng)隊(duì)首指針，后取出元素 )。3.在線性表的單存儲(chǔ)中，假設(shè)一個(gè)元素所在結(jié)點(diǎn)的地址為p，那么其后繼結(jié)點(diǎn)的地址為()。p->next4.在一個(gè)單鏈表中指針 p 所指向結(jié)點(diǎn)的后面插入一個(gè)指針q 所指向的結(jié)點(diǎn)時(shí)，首先把 ()的值賦給 q->

4、;next ，然后 (q->date)的值賦給 p->next 。p->next5.從一個(gè)棧刪除元素時(shí)，首先取出(棧頂元素 )，然后再使 (棧頂指針 )減 1。6.子串的定位操作通常稱(chēng)做串的(模式匹配 )。7.設(shè)目標(biāo) T= abccdcdccbaa，模式 P= cdcc那么第 (六)次匹配成功。8. 順序棧 S 中 ， 出 棧操作時(shí) 要執(zhí)行的語(yǔ)句序列中有 S->top(-)；進(jìn)棧操作時(shí)要執(zhí)行的語(yǔ)句專(zhuān)業(yè)資料整理WORD格式序列中有 S->top(+)。9.順序表中邏輯上相鄰元素的物理位置 (一定 )緊鄰；單鏈表中 邏輯上相鄰元素的物理位置 (不一定緊鄰。10.在 (

5、循環(huán) )鏈表中，從任何一結(jié)點(diǎn)出發(fā)都能訪問(wèn)到表中的所有結(jié)點(diǎn)。11. 棧和隊(duì)列均是 ( 運(yùn)算受限 ) 的線性表，棧的特點(diǎn)是 ( 先進(jìn)后出 后進(jìn)先出 ) ；隊(duì)列的特點(diǎn)是 ( 先進(jìn)先出 后進(jìn)后出 )。12.通常，在程序中使用的串可分為串常量和串變量；而串按存儲(chǔ)方式又可分為(定長(zhǎng)順序存儲(chǔ) )和(堆分配存儲(chǔ) )。13.循環(huán)隊(duì)列頭指針front 指向隊(duì)頭元素，隊(duì)尾指針rear 指向隊(duì)尾元素后的一個(gè)空閑元素，隊(duì)列的最大空間為Queuelen 。在 循 環(huán) 隊(duì) 列 中，隊(duì)空標(biāo)志為(front=rear隊(duì)滿標(biāo)志為) ，(rear+1%max=front)。當(dāng) rear>=front時(shí)，隊(duì)列長(zhǎng)度為 (rear

6、-front)，當(dāng) rear<front 時(shí)，隊(duì)列長(zhǎng)度為()。rear-front+max14.在一個(gè)長(zhǎng)度為n 的線性表中的第i 個(gè)元素 1 i n之前插入一個(gè)元素時(shí)，需向后移動(dòng)(n-i+1)個(gè)元素。15.在具有 n 個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有(n-1)個(gè)元素。16.帶有一個(gè)頭結(jié)點(diǎn)的單鏈表Head 為空的條件是(Head->next=null)。17.在一個(gè)單鏈表中刪除指針p 所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)時(shí)，需要把(p->next->next指)值賦給 p->next針域。18.一個(gè)順序循環(huán)隊(duì)列存于aM 中，假定隊(duì)首和隊(duì)尾指針?lè)謩e為 front和 rear ，那么判斷

7、隊(duì)空的條件為( a.front=a.rear)，判斷隊(duì)滿的條件為(a.rear+1%M=a.front)。專(zhuān)業(yè)資料整理WORD格式19.在雙向鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向其 (前驅(qū) ) 結(jié)點(diǎn)，另一個(gè)指向其 (后繼 )結(jié)點(diǎn)，最后一個(gè)結(jié)點(diǎn)的 (后繼結(jié)點(diǎn) )指針域?yàn)榭铡?20. 假設(shè) D=(a ， (b， c) ， e ， a)， 那么 Head( D )=() ，Tail( D )=( )， Head(Tail( D )=()。本人不會(huì)21.在循環(huán)鏈表中，每個(gè)結(jié)點(diǎn)有( 一個(gè) )個(gè)指針域，指向其 (后繼 )結(jié)點(diǎn)，最后一個(gè)結(jié)點(diǎn)的指針域(為空)。*22. 假設(shè) S=(a ， (b， c) ，

8、e ， d) ， 那么 Head( S )=()， Tail( S )=()，Head(Tail( S )=()。本人不會(huì)二、選擇題1.在一個(gè)單鏈表中，假設(shè)q 所指結(jié)點(diǎn)是 p 所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，假設(shè)在q 與 p 之間插入一個(gè) s 所指的結(jié)A點(diǎn)，那么執(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.對(duì)于順序存儲(chǔ)的隊(duì)列，存儲(chǔ)空間大小為n，頭指針為 F，尾指針為

9、 R。假設(shè)在邏輯上看一個(gè)環(huán)，那么隊(duì)列中元素的個(gè)數(shù)A( )。A.R-F B.n+R-F C.(R-F+1)modn D.(n+R-F)mod n3.如下陳述中正確的選項(xiàng)是(A)。A.串是一種特殊的線性表B.串的長(zhǎng)度必須大于零C.串中元素只能是字母D.空串就是空白串4.假設(shè)讓元素 1，2， 3 依次進(jìn)棧，那么出棧次序不可能出現(xiàn)(C)的情況。專(zhuān)業(yè)資料整理WORD格式A.3， 2， 1 B.2， 1， 3C.3， 1， 2D.1，3， 25.判定一個(gè)隊(duì)列QU最多元素為m0 為空的條件是(C)。A.QU->rear-QU->front=m0B.QU->rear-QU->front

10、-1=m0C.QU->front=QU->rearD.QU->front=QU->rear+16.設(shè)目標(biāo)串S= abcdef，模式串p= de，那么第 (C)次匹配成功。A.1B.2C.4D.57. 設(shè) 字 符 串 s1= ABCDEFG，S2= PQRST，T ， sub1 ， sub2為 空 串。 那么運(yùn)算s=Concat(T ，SubString(sub1 ， s1， 2， SubLength(s2)， SubString(sub2， s1， SubLength(s2)， 2)后的串 T 值為(D)。A. BCDEF B. BCDEFG C. BCPQRST D.

11、 BCDEFEF8.一個(gè)順序線性表第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，那么第 5個(gè)元素的地址是(B)。A.100B.108C.110D.120C9.非空的循環(huán)單鏈表 head 的尾結(jié)點(diǎn)由p 所指向滿足 ( )。A.p->next=NULLB.p=NULLC.p->next=headD.p=head10.在一個(gè)鏈隊(duì)中，假設(shè) f 和 r 分別為隊(duì)首和隊(duì)尾指針，那么刪除一個(gè)結(jié)點(diǎn)的運(yùn)算時(shí) (C)。A.r=f->next;B.r=r->next;C.f=f->next;D.f=r->next;11.在一個(gè)長(zhǎng)度為n 的線性表中，刪除值為x 的元素時(shí)，需要比

12、較元素和移動(dòng)元素的總次數(shù)為(C)。專(zhuān)業(yè)資料整理WORD格式A.(n+1)/2B.n/2C.nD.n+112.在一個(gè)單鏈表中，假設(shè)要在p 所指向的結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)，那么需要相繼修改(B)個(gè)指針域的值。A.1B.2C.3D.413.線性構(gòu)造中，每個(gè)結(jié)點(diǎn)(C)。A.無(wú)直接前驅(qū)B.只有一個(gè)直接前驅(qū)和個(gè)數(shù)不受限制的直接后繼C.只有一個(gè)直接前驅(qū)和后繼 D.有個(gè)數(shù)不受限制的直接前驅(qū)和后繼14.隊(duì)列是限定在 (D)進(jìn)展操作的線性表。A.中間B.隊(duì)頭C.隊(duì)尾D.端點(diǎn)15.設(shè)串 S1=“ ABCDEFG，S2=“ PQRST，函數(shù) StrCat(x,y)返回 x 和 y 串的連接串，函數(shù)StrSub(S，

13、i， j)返回串 S的從序號(hào) i 的字符開(kāi)場(chǎng)的j 個(gè)字符組成的子串，StrLen(S)返回串 S的長(zhǎng)度，那么StrCat(StrSub(S1，2， StrLen(S2)， StrSub(S1，StrLen (S2)， 2)的結(jié)果串是 (D)。專(zhuān)業(yè)資料整理WORD格式A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF專(zhuān)業(yè)資料整理WORD格式16.學(xué)生成績(jī)表是一種(C)構(gòu)造。A.圖形B.樹(shù)形C.線性D.集合17.在一個(gè)鏈隊(duì)中，假設(shè)f 和 r 分別為隊(duì)首和隊(duì)尾指針，那么插入s 所指結(jié)點(diǎn)的運(yùn)算時(shí)A.f->next=s;f=s;B.r->next=s; r=s;C.s->

14、;next=r; r=s;D.s->next=f; f=s;18.向順序表中的i 位置處插入元素，下面哪項(xiàng)能夠準(zhǔn)確的說(shuō)明(C)。專(zhuān)業(yè)資料整理WORD格式i 的位置是合法的。(D)A.i<=1|i>l->length+1B.i>=1專(zhuān)業(yè)資料整理WORD格式C.i>=l->length+1D.1<=i<=l->length+119.設(shè)線性鏈表中結(jié)點(diǎn)的構(gòu)造為 data， next ，指針 q 所 指結(jié)點(diǎn)是指針 p 所指結(jié)點(diǎn)的直接后繼，假設(shè)在 *q 和 *p 之間插入結(jié)點(diǎn) *s，那么應(yīng)執(zhí)行 (A)操作。A.s->next=p->n

15、ext;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.一個(gè)棧的入棧序列為a， b， c， d， e，那么出棧序列不可能的是 (C)。A.edcba B.dcbaeC.dceab D.abcdeB21.如果以鏈表作為棧的存儲(chǔ)構(gòu)造，那么出棧操作時(shí)( )。A.必須判別棧是否滿B.必須判別棧是否為空C.必須判別棧元素類(lèi)型D.可不做任何判斷22.設(shè)有兩個(gè)串p 和 q，求 q 在 p 中首次出現(xiàn)的位置的運(yùn)算稱(chēng)為(B)。A.連接B.模式

16、匹配C.求子串D.求串長(zhǎng)23.p 指向線性鏈表中的某一結(jié)點(diǎn)，那么在線性鏈表的表尾插入結(jié)點(diǎn) S 的語(yǔ)句序列是 (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

17、;->next;p->next=s;s->next=p24.向順序棧中壓入新元素時(shí)，應(yīng)當(dāng)(A)。A.先移動(dòng)棧頂指針，再存入元素B.先存入元素，再移動(dòng)棧頂指針C.先后次序無(wú)關(guān)緊要D.同時(shí)進(jìn)展專(zhuān)業(yè)資料整理WORD格式25.假定一個(gè)順序隊(duì)列的隊(duì)首和隊(duì)尾指針?lè)謩e為f 和 r ，那么判斷隊(duì)空的條件為(D)。f+1=rB.r+1=f C.f=0D.f=r26.棧的插入和刪除操作在(A)進(jìn)展。A.棧頂 B.棧底C.任意位置D.指定位置27.棧和隊(duì)列的共同點(diǎn)是C( )。A.都是先進(jìn)后出B.都是先進(jìn)先出C.只允許在端點(diǎn)處插入和刪除元素D.沒(méi)有共同點(diǎn)28.假設(shè) 6 行 8 列的數(shù)組以列序?yàn)橹餍蝽?/p>

18、序存儲(chǔ)，基地址為1000， 每個(gè)元素占2 個(gè)存儲(chǔ)單元，那么第 5行第 3 列的元素 (假定無(wú)第 0行第 0列 )的地址是 (B)。A.1086 B.1032C.1068D.答案 A， B，C 都不對(duì)29.設(shè)有 50 行的二維數(shù)組A5060 ，其元素長(zhǎng)度為 2字節(jié)，按 行優(yōu)先順序存儲(chǔ)，基地址為100，那么元素 A1825 的存儲(chǔ)地址 為(D)。A.1850B.2188C.1950D.2310三、論述題1.寫(xiě)出線性表的插入算法、刪除算法。解：太麻煩略略略*2. 畫(huà)出主串為 ababcabcacbab，子串為 abc的模式匹配過(guò)程。解：四、算法設(shè)計(jì)題1.在帶頭結(jié)點(diǎn)的單鏈線性表L 中第 i 個(gè)位置之前

19、插入新的元素e。專(zhuān)業(yè)資料整理WORD格式略2.在帶頭結(jié)點(diǎn)的單鏈線性表L 中，刪除第i 個(gè)元素，并由e 返回其值。略樹(shù)形構(gòu)造一、填空題1.赫夫曼樹(shù)，又稱(chēng)最優(yōu)樹(shù)，是一類(lèi)(帶權(quán)路徑 )長(zhǎng)度最短的樹(shù)。2.在一棵二叉樹(shù)中，第5 層上的結(jié)點(diǎn)數(shù)最多為(16)個(gè)。3.一棵高度為5 的二叉樹(shù)中最少含有(5)個(gè)結(jié)點(diǎn)，最多含有(31)個(gè)結(jié)點(diǎn)。4.假設(shè)一棵二叉樹(shù)中有8 個(gè)度為 2 的結(jié)點(diǎn)，那么它有(9)個(gè)葉子。5.一棵深度為6 的滿二叉樹(shù)有 (31)個(gè)非終端結(jié)點(diǎn)。6.樹(shù)中結(jié)點(diǎn)A 的 (子樹(shù)數(shù) )稱(chēng)為結(jié)點(diǎn) A 的度。7.對(duì)一棵二叉排序樹(shù)進(jìn)展中序遍歷時(shí)，得到的結(jié)點(diǎn)序列是一個(gè)(升序序列 )。8.在樹(shù)型構(gòu)造中，根結(jié)點(diǎn)沒(méi)有前驅(qū)

20、結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且僅有(一 )個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)(沒(méi)有 )后繼結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)都可以有(一或多個(gè) )個(gè)后繼結(jié)點(diǎn)。2n-19.在最優(yōu)二叉樹(shù)中沒(méi)有度為1 的結(jié)點(diǎn)，那么一棵有n 個(gè)葉子結(jié)點(diǎn)的最優(yōu)二叉樹(shù)中共有()個(gè)結(jié)點(diǎn)。10.深度為 4設(shè)根的層數(shù)為4)個(gè)結(jié)點(diǎn)，至多有15)個(gè)結(jié)點(diǎn)，第2 -11的二叉樹(shù)至少有 (i 層上至多有 ( n)個(gè)結(jié)點(diǎn)。6634 層上至多有11.深度為 6設(shè)根的層數(shù)為 1的二叉樹(shù)至少有 ( )個(gè)結(jié)點(diǎn)，至多有( )個(gè)結(jié)點(diǎn)，第(8)個(gè)結(jié)點(diǎn)。專(zhuān)業(yè)資料整理WORD格式A.nB. N+1C.n-1D.不確定專(zhuān)業(yè)資料整理WORD格式注： 1:B2:D3:A5.下面 (A)是對(duì)的。4:B

21、專(zhuān)業(yè)資料整理WORD格式A.哈夫曼樹(shù)中結(jié)點(diǎn)的度只可能是0 和 2。 B.二叉樹(shù)的順序存儲(chǔ)中，是以先序遍歷存儲(chǔ)結(jié)點(diǎn)的。C.完全二叉樹(shù)實(shí)際上就是滿二叉樹(shù)。D.一棵二叉樹(shù)第i 層的最大結(jié)點(diǎn)數(shù)為2i-1。6.將含 100 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根這一層開(kāi)場(chǎng)，每層上從左到右依次對(duì)結(jié)點(diǎn)編號(hào)，根結(jié)點(diǎn)的編號(hào)為 1。編號(hào)為 49 的結(jié)點(diǎn) X 的右孩子編號(hào)為 (B)。 A.98 B.99 C.24 D.無(wú)法確定7.先序?yàn)?A， B，C 且后序?yàn)?C， B， A 的二叉樹(shù)共有 (B)種。A.3B.4C.5D.68.在一棵度為 3 的樹(shù)中，度為 3 的結(jié)點(diǎn)個(gè)數(shù)為 2，度為 2 的結(jié)點(diǎn)個(gè)數(shù)為 1，那么度為 0 的結(jié)點(diǎn)個(gè)數(shù)

22、為 (C)。A.4B.5C.6D.79.由權(quán)值分別為 11， 8，6， 2， 5 的葉子結(jié)點(diǎn)生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為B( )。A.24B.71C.48D.5310. 一個(gè)具有 767 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)， 其葉子結(jié)點(diǎn)個(gè)數(shù)為 (B)。 A.382 B.384 C.385 D.38611. 在一棵具有 35 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中，該樹(shù)的深度為 (A)。A.6 B.7C.5 D.812. 由三個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹(shù)，共有 (B)種不同的構(gòu)造。A.3B.4 C.5 D.6專(zhuān)業(yè)資料整理WORD格式13.深度為k 的二叉樹(shù)至多有(2K-1)個(gè)結(jié)點(diǎn)(k 。1)專(zhuān)業(yè)資料整理WORD格式A.2kB.2k

23、-1C.2k-1D.2k專(zhuān)業(yè)資料整理WORD格式三、簡(jiǎn)答題1.一棵二叉樹(shù)的先序遍歷和中序遍歷，那么該二叉樹(shù)的后序遍歷是什么？先序遍歷： 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)化為二叉樹(shù)。專(zhuān)業(yè)資料整理WORD格式解：此題沒(méi)法寫(xiě)略略略3. 已 知 某 二 叉 樹(shù) 的 前 序 序 列 為 EBADCFHGI， 中 序 序 列 為 ABCDEFGHI，請(qǐng)給出二叉樹(shù)且寫(xiě)出二叉樹(shù)的后序序列。解：二叉樹(shù)略后序序列 :A,C,D,B,G,I,H,F,E4.試用權(quán)集

24、合 6， 4， 8，3， 7， 5，10， 8， 2， 1， 11，構(gòu)造哈夫曼 (Huffman) 樹(shù)。(1)畫(huà)出這棵哈夫曼樹(shù)；(2)分別計(jì)算該哈夫曼樹(shù)的路徑長(zhǎng)度和帶權(quán)路徑長(zhǎng)度。解： (1)略(2)路徑長(zhǎng)度為： 1x2+2x4+3x8+4x3+5x2=60;帶權(quán)路徑長(zhǎng)度為： 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)中元素的排 列次序，將所有元素插入一棵初始為空的二叉排序樹(shù)中，使之 仍是一棵二叉排序樹(shù)。(1)試畫(huà)出插入完成之后的二叉排序樹(shù)； (2)假設(shè)查找元素 2，它將依次與二

25、叉排序樹(shù)中哪些元素比擬大小 ? (3)對(duì)該樹(shù)進(jìn)展中序遍歷，試寫(xiě)出中序遍歷序列。專(zhuān)業(yè)資料整理WORD格式解： (1)略(2)10,9,2(3)2,5,6,9,10,15,18,19,20,256.一棵二叉樹(shù)的順序存儲(chǔ)表示如下，其中0 表示空，請(qǐng)分別寫(xiě)出二叉的先序、中序、后序遍歷序列。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,20專(zhuān)業(yè)資料整理WORD格式7.將如下列圖的一般樹(shù)轉(zhuǎn)化為二叉樹(shù)。

26、專(zhuān)業(yè)資料整理WORD格式8.將下列圖中的二叉樹(shù)轉(zhuǎn)換成森林。BAEGKCFHILJ專(zhuān)業(yè)資料整理WORD格式四、論述題1.由分別帶權(quán)為 3， 12，9， 2， 5，7 的葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹(shù)，并計(jì)算該樹(shù)的帶權(quán)路徑長(zhǎng)度。解:帶權(quán)路徑長(zhǎng)度為 :91圖狀構(gòu)造一、填空題1.假設(shè)一個(gè)圖的頂點(diǎn)集為a， b， c，d， e， f，邊集為 (a， b)， (a， c)， (b， c)， (d，e),那么該圖含有 (3個(gè)連通分量。2.具有 10個(gè)頂點(diǎn)的無(wú)向圖，邊的總數(shù)最多為(45)。3.圖的廣度優(yōu)先搜索遍歷類(lèi)似于樹(shù)的(按層次 )遍歷的過(guò)程。4.在無(wú)向圖 G 的鄰接矩陣 A 中，假設(shè) Aij 等于 1，那么 Aj

27、i 等于 (1)。深度)優(yōu)先搜索遍歷算法是一種遞歸算法，圖的(廣度) 優(yōu)先搜索遍歷算法需要使用隊(duì)列5.圖的 (二、選擇題1.一個(gè)有 n 個(gè)頂點(diǎn)的無(wú)向圖最多有(C)條邊。A.n B.n(n-1)C.n(n-1)/2 D.2n2. 在一個(gè)無(wú)向圖中， 所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的(B)倍。A.3 B.2 C.1 D.1/2專(zhuān)業(yè)資料整理WORD格式3.在一個(gè)具有n 個(gè)頂點(diǎn)的無(wú)向圖中，假設(shè)具有e 條邊，那么所有頂點(diǎn)的度數(shù)之為(D)。專(zhuān)業(yè)資料整理WORD格式A.nB.eC.n+eD.2e專(zhuān)業(yè)資料整理WORD格式三、簡(jiǎn)答題專(zhuān)業(yè)資料整理WORD格式1.給出如下列圖所示的無(wú)向圖G 的鄰接矩陣存儲(chǔ)構(gòu)造。答案略

28、專(zhuān)業(yè)資料整理WORD格式2.畫(huà)出下列圖的鄰接表存儲(chǔ)構(gòu)造。答案略專(zhuān)業(yè)資料整理WORD格式3.給出下列圖從 A 點(diǎn)出發(fā)的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的頂點(diǎn)序列。解：深度優(yōu)先遍歷： AECDB廣度優(yōu)先遍歷： AEBDC專(zhuān)業(yè)資料整理WORD格式5.給出從 V1 點(diǎn)出發(fā)的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的頂點(diǎn)序列。解：深度優(yōu)先遍歷 ;v1 v2 v3 v4 v5 v6 v7 v8 v9 廣度優(yōu)先遍歷 ;v1 v2 v3 v4 v7 v5 v6 v8 v9專(zhuān)業(yè)資料整理WORD格式四、論述題1.寫(xiě)出下面帶權(quán)有向圖的的關(guān)鍵路徑。解： (1)1->2->5->8->92.設(shè)將整數(shù)1、2、 3、

29、4 依次進(jìn)棧，請(qǐng)答復(fù)下述問(wèn)題：1假設(shè)入、出棧順序?yàn)?Push(1)， Pop()，Push(2)，Push(3)， Pop()， Pop()，Push(4)， Pop()，那么出棧的數(shù)字序列是什么？ 2能否得到出棧序列 1432 和 1423？并說(shuō)明為什么不能得到或者如何得到？解： (1):1324(2):可以得到 1432不能得到 1423得到 1432 的過(guò)程為： Push(1),pop(),push(2),push(3),push(4),pop(),pop(),pop(), 不能得到 1423 無(wú)法執(zhí)行此操作專(zhuān)業(yè)資料整理WORD格式3.求出下列圖的最小生成樹(shù)。4.求出下列圖的最小生成樹(shù)。答案略答案略專(zhuān)業(yè)資料整理WORD格式查找一、簡(jiǎn)答題1.關(guān)鍵字集合 19， 01， 23， 14， 55， 68， 11， 82， 36，哈希函數(shù)為： H(key)=key MOD 9 構(gòu)建哈希表，采用開(kāi)放定