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

一、選擇題A、數(shù)據(jù)得邏輯結(jié)構(gòu)B、數(shù)據(jù)得存儲(chǔ)結(jié)構(gòu)C、數(shù)據(jù)得邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)D、數(shù)據(jù)得邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其基本操作2、算法分析得兩個(gè)主要方面就是(A)。C、可讀性與文檔性D、數(shù)據(jù)復(fù)雜性與程4、計(jì)算機(jī)中得算法指得就是解決某一個(gè)問題得有限運(yùn)算序列，它必須具備輸入、輸出、A、可執(zhí)行性、可移植性與可擴(kuò)充性??B、可執(zhí)行性、有窮性與確定性???for(j=0;j＜n;j++)2得有限運(yùn)算序列27、某算法得語句執(zhí)行頻度為(3n+nlogn+n2+8),其時(shí)間復(fù)雜度表示（C）。2n)while（i<＝n)A、O(n）???B、O(3n)C、O(log3n)D、O（n3)9、數(shù)據(jù)結(jié)構(gòu)就是一門研究非數(shù)值計(jì)算得程序設(shè)計(jì)問題中計(jì)算機(jī)得數(shù)據(jù)元素以及它們之間得()與?i=s=0;i++；s+=i;11、抽象數(shù)據(jù)類型得三個(gè)組成部分分別為（).A、數(shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系與基本操作??B、數(shù)據(jù)元素、邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)C、數(shù)據(jù)項(xiàng)、數(shù)據(jù)元素與數(shù)據(jù)類型?D、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類型12、通常從正確性、易讀性、健壯性、高效性等4個(gè)方面評(píng)價(jià)算法得質(zhì)量，以下解釋錯(cuò)誤得就是A、正確性算法應(yīng)能正確地實(shí)現(xiàn)預(yù)定得功能??B、易讀性算法應(yīng)易于閱讀與理解,以便調(diào)試、修改與擴(kuò)充C、健壯性當(dāng)環(huán)境發(fā)生變化時(shí)，算法能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，不會(huì)產(chǎn)生不需要得運(yùn)行結(jié)果?D、高效性即達(dá)到所需要得時(shí)間性能二、填空題2、數(shù)據(jù)結(jié)構(gòu)得四種基本類型中，樹形結(jié)構(gòu)得元素就是一對(duì)多關(guān)系.三、綜合題1、將數(shù)量級(jí)O（1)，O(N),O（N2),O（N3),O(NLOG2NO（LOG2N）,O（2N)按增長(zhǎng)率由小到大排序.O(N3)O(2N)1、數(shù)據(jù)結(jié)構(gòu)被形式地定義為(D,R),其中D就是數(shù)據(jù)元素得有限集合,R就是D上得關(guān)系有限集合.2、數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)得邏輯結(jié)構(gòu)、數(shù)據(jù)得存儲(chǔ)結(jié)構(gòu)與數(shù)據(jù)得運(yùn)算這三個(gè)方面得內(nèi)容。3、數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別就是線性結(jié)構(gòu)與非線性結(jié)構(gòu).4、線性結(jié)構(gòu)中元素之間存在一對(duì)一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對(duì)多關(guān)系,圖形結(jié)構(gòu)中元素之間存在多對(duì)多關(guān)系。5。在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn);最后一個(gè)結(jié)點(diǎn)沒有后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)后續(xù)結(jié)點(diǎn)。6、在樹形結(jié)構(gòu)中,樹根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn);葉子結(jié)點(diǎn)沒有后續(xù)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)得后續(xù)結(jié)點(diǎn)數(shù)可以任意多個(gè)。7、在圖形結(jié)構(gòu)中,每個(gè)結(jié)點(diǎn)得前驅(qū)結(jié)點(diǎn)數(shù)與后續(xù)結(jié)點(diǎn)數(shù)可以任意多個(gè)。8。數(shù)據(jù)得存儲(chǔ)結(jié)構(gòu)可用四種基本得存儲(chǔ)方法表示,它們分別就是順序、鏈?zhǔn)健⑺饕?、散?A）一對(duì)多關(guān)系B)多對(duì)多關(guān)系C)多對(duì)一關(guān)系D)一對(duì)一關(guān)系(C)2、數(shù)據(jù)結(jié)構(gòu)中,與所使用得計(jì)算機(jī)無關(guān)得就是數(shù)據(jù)得結(jié)構(gòu)；A)存儲(chǔ)B)物理C）邏輯D）物理與存儲(chǔ)A)找出數(shù)據(jù)結(jié)構(gòu)得合理性B)研究算法中得輸入與輸出得關(guān)系C）分析算法得效率以求改進(jìn)D)分析算法得易懂性與文檔性(A)4、算法分析得兩個(gè)主要方面5就是:A)空間復(fù)雜性與時(shí)間復(fù)雜性B）正確性與簡(jiǎn)明性C)可讀性與文檔性D）數(shù)據(jù)復(fù)雜性與程序復(fù)雜性(C)5、計(jì)算機(jī)算法指得就是:A)計(jì)算方法B）排序方法C)解決問題得有限運(yùn)算序列D)調(diào)度方法（B）6、計(jì)算機(jī)算法必須具備輸入、輸出與等5個(gè)特性.A)可行性、可移植性與可擴(kuò)充性B)可行性、確定性與有窮性C)確定性、有窮性與穩(wěn)定性D）易讀性、穩(wěn)定性與安全性1、數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類型兩個(gè)概念之間有區(qū)別嗎?答：簡(jiǎn)單地說,數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起得數(shù)組元素。數(shù)據(jù)類型不僅定義了一組帶結(jié)構(gòu)得數(shù)據(jù)元素，而且還在其上定義了一組操作.2、簡(jiǎn)述線性結(jié)構(gòu)與非線性結(jié)構(gòu)得不同點(diǎn)。答:線性結(jié)構(gòu)反映結(jié)點(diǎn)間得邏輯關(guān)系就是一對(duì)一得，非線性結(jié)構(gòu)反映結(jié)點(diǎn)間EQ\*jc3\*hps36\o\al(\s\up0(設(shè)),f)EQ\*jc3\*hps36\o\al(\s\up11(定),1)EQ\*jc3\*hps31\o\al(\s\up9(1邏),d)EQ\*jc3\*hps31\o\al(\s\up7(i構(gòu)),d)EQ\*jc3\*hps31\o\al(\s\up3(j),4)EQ\*jc3\*hps31\o\al(\s\up12(h),d)EQ\*jc3\*hps31\o\al(\s\up12(il),３)EQ\*jc3\*hps31\o\al(\s\up7(s),3d)一、選擇題１、若長(zhǎng)度為ｎ得線性表采用順序存儲(chǔ)結(jié)構(gòu),在其第i個(gè)位置插入一個(gè)新元素算法得時(shí)間復(fù)雜度2n)2)２、若一個(gè)線性表中最常用得操作就是取第i個(gè)元素與找第i個(gè)元素得前趨元素,則采用存儲(chǔ)方式最節(jié)省時(shí)間。3、具有線性結(jié)構(gòu)得數(shù)據(jù)結(jié)構(gòu)就是()。4、在一個(gè)長(zhǎng)度為ｎ得順序表中,在第i個(gè)元素之前插入一個(gè)新元素時(shí),需向后移動(dòng)（5、非空得循環(huán)單鏈表aｄ得尾結(jié)點(diǎn)p滿足（)。A、可隨機(jī)訪問任一元素??Ｂ、插入刪除不需要移動(dòng)元素?C、不必事先估計(jì)存儲(chǔ)空間??D、所需空間與線性表長(zhǎng)度成正比７、在雙向循環(huán)鏈表中,在p指針?biāo)傅媒Y(jié)點(diǎn)后插入一個(gè)指針q所指向得新結(jié)點(diǎn),修改指針得操作就是?A、必須就是連續(xù)得??B、必須就是不連續(xù)得?C、連續(xù)與否均可???Ｄ、與頭結(jié)點(diǎn)得9、在一個(gè)長(zhǎng)度為n得順序表中刪除第i個(gè)元素，需要向前移動(dòng)（)個(gè)元素。2)D、A、每個(gè)元素都有一個(gè)直接前驅(qū)與一個(gè)直接后繼?B、線性表中至少要有一個(gè)元素C、表中諸元素得排列順序必須就是由小到大或由大到小?D、除第一個(gè)與最后一個(gè)元素外,其余每個(gè)元素都由一個(gè)且僅有一個(gè)直接前驅(qū)與直接后繼14、一個(gè)順序表得第一個(gè)元素得存儲(chǔ)地址就是90，每個(gè)元素得長(zhǎng)度為2,則第6個(gè)元素得存儲(chǔ)地15、在線性表得下列存儲(chǔ)結(jié)構(gòu)中,讀取元素花費(fèi)得時(shí)間最少得就是()。A、p—〉next=p－>next－〉next;B、p=p—〉next；p—>next=p->next—〉next;C、p=p->next；D、p=p—>next—>next;17、將長(zhǎng)度為n得單鏈表連接在長(zhǎng)度為m得單鏈表之后得算法得時(shí)間復(fù)雜度為().19、順序表中，插入一個(gè)元素所需移動(dòng)得元素平均數(shù)就是()。A、不再需要頭指針B、已知某結(jié)點(diǎn)位置后能容易找到其直接前驅(qū)C、在進(jìn)行插入、刪除運(yùn)算時(shí)能保證鏈表不斷開D、在表中任一結(jié)點(diǎn)出發(fā)都能掃描整個(gè)鏈表?11、不帶頭結(jié)點(diǎn)得單鏈表head為空得判定條件就是（)。ULL?ead!=NULLA、訪問第i個(gè)元素得前驅(qū)(1＜)?B、在第i個(gè)元素之后插入一個(gè)新元素()?C、刪除第i個(gè)元素()???D、對(duì)順序表中元素進(jìn)行排序13、已知指針p與q分別指向某單鏈表中第一個(gè)結(jié)點(diǎn)與最后一個(gè)結(jié)點(diǎn)。假設(shè)指針s指向另一個(gè)單鏈表中某個(gè)結(jié)點(diǎn)，則在s所指結(jié)點(diǎn)之后插入上述鏈表應(yīng)執(zhí)行得語句為（)。=s->next;?＞next=q；?q;p—〉next=s—〉next;A、線性表得順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu)??B、線性表得順序存儲(chǔ)結(jié)構(gòu)適用于頻繁插入／刪除數(shù)據(jù)元素得情況?C、線性表得鏈表存儲(chǔ)結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素得情況???D、線性表得鏈表存儲(chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)15、在表長(zhǎng)為n得順序表中，當(dāng)在任何位置刪除一個(gè)元素得概率相同時(shí)，刪除一個(gè)元素所需移動(dòng)得平n+1）/2??D、n16、在一個(gè)單鏈表中,已知q所指結(jié)點(diǎn)就是p所指結(jié)點(diǎn)得前驅(qū)結(jié)點(diǎn),若在q與p之間插入一個(gè)結(jié)點(diǎn)s,A、s->next=p-〉next;p-〉next=s;?B、p-〉next=s—>next;s-〉next=p;??D、p->next＝s;s—〉next=q;?17、在單鏈表中,指針p指向元素為x得結(jié)點(diǎn),實(shí)現(xiàn)刪除x得后繼得語句就是（)。A、p=p-〉next;??B、p—>next=p—〉next—〉next;?C、p—>next=p；D、p=p—〉next—〉next;18、在頭指針為head且表長(zhǎng)大于1得單循環(huán)鏈表中,指針p指向表中某個(gè)結(jié)點(diǎn),若p—〉next-A、p指向頭結(jié)點(diǎn)?B、p指向尾結(jié)點(diǎn)??C、p得直接后繼就是頭結(jié)點(diǎn)D、p得直接后繼就是尾結(jié)點(diǎn)二、填空題1、設(shè)單鏈表得結(jié)點(diǎn)結(jié)構(gòu)為(data,next)。已知指針p指向單鏈表中得結(jié)點(diǎn),q指向新結(jié)點(diǎn)，欲將q插入到p結(jié)點(diǎn)之后,則需要執(zhí)行得語句:;。答案:q-＞next=p->nextp—〉next=q2、線性表得邏輯結(jié)構(gòu)就是,其所含元素得個(gè)數(shù)稱為線性表得。答案:線性結(jié)構(gòu)長(zhǎng)度3、寫出帶頭結(jié)點(diǎn)得雙向循環(huán)鏈表L為空表得條件。答案:L－〉prior＝=L—>next=＝L4、帶頭結(jié)點(diǎn)得單鏈表head為空得條件就是.答案：head—>next==NULL5、在一個(gè)單鏈表中刪除p所指結(jié)點(diǎn)得后繼結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行以下操作：p－〉next___；答案：q->next三、判斷題1、單鏈表不就是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)?！?、在具有頭結(jié)點(diǎn)得單鏈表中,頭指針指向鏈表得第一個(gè)數(shù)據(jù)結(jié)點(diǎn)．X3、用循環(huán)單鏈表表示得鏈隊(duì)列中,可以不設(shè)隊(duì)頭指針,僅在隊(duì)尾設(shè)置隊(duì)尾指針。√4、順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu).X5、在線性表得順序存儲(chǔ)結(jié)構(gòu)中,邏輯上相鄰得兩個(gè)元素但就是在物理位置上不一定就是相鄰得。X四、程序分析填空題1、函數(shù)GetElem實(shí)現(xiàn)返回單鏈表得第i個(gè)元素，請(qǐng)?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整。nkListL,inti,Elemtype*e）{p＝L－>next;j＝1；}}2、函數(shù)實(shí)現(xiàn)單鏈表得插入算法，請(qǐng)?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整。，＊ULL)&＆(j<i—1)）{??p=p－>next;j++;}?if（p==NULL｜|j〉i—1）returnERROR;f(LNode)）;答案:(1)s-〉next＝p-〉next（2）p->next=s3、函數(shù)ListDelete__sq實(shí)現(xiàn)順序表刪除算法,請(qǐng)?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整.intListDelete＿sq(Sqlist*L,inti){for(k=i-1;k〈L-〉length—1;k++) }答案:(1)L－〉slist［k＋1](2)——L-〉Length4、函數(shù)實(shí)現(xiàn)單鏈表得刪除算法，請(qǐng)?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整。intListDelete(LinkListL，inti,ElemType*s){LNode＊p,＊q；}if(p—〉next==NULL|｜j＞i-1)returnERROR; *s=qdata;returnOK;}/*listDelete*/答案:(1）p—〉next!=NULL(2)p—〉next=q—>next5、寫出算法得功能.intL(head）{??while(p！=NULL）答案:求單鏈表head得長(zhǎng)度五、綜合題1、編寫算法,實(shí)現(xiàn)帶頭結(jié)點(diǎn)單鏈表得逆置算法.答案:voidinvent(Lnodep=head—〉next;q=p—〉next；p—〉next=NULL;}2、有兩個(gè)循環(huán)鏈表,鏈頭指針分別為L(zhǎng)1與L2,要求寫出算法將L2鏈表鏈到L1鏈表之后,且連接后仍保持循環(huán)鏈表形式。e(Lnode＊L1,Lnode*L2){Lnode*p,＊q；while(p->next！=L1)while(q->next！=L2)}3、設(shè)一個(gè)帶頭結(jié)點(diǎn)得單向鏈表得頭指針為head,設(shè)計(jì)算法,將鏈表得記錄,按照data域得值遞增排p=head-〉next；q=p—〉next;p—＞next=NULL;while（q）if(r-〉data<=p-〉data)else{while(！p&&r->data〉p-〉data)r—>next=p;s—〉next=r;}}4、編寫算法,將一個(gè)頭指針為head不帶頭結(jié)點(diǎn)得單鏈表改造為一個(gè)單向循環(huán)鏈表，并分析算法得答案:voidlinklist_c(Lnode＊head）{Lnode*p；p=head; ROR；while(p-〉next！=NULL）p=p->next;p—〉next＝head;}設(shè)單鏈表得長(zhǎng)度（數(shù)據(jù)結(jié)點(diǎn)數(shù)）為N，則該算法得時(shí)間主要花費(fèi)在查找鏈表最后一個(gè)結(jié)點(diǎn)上（算法中得while循環(huán)）,所以該算法得時(shí)間復(fù)雜度為O（N).5、已知head為帶頭結(jié)點(diǎn)得單循環(huán)鏈表得頭指針,鏈表中得數(shù)據(jù)元素依次為（a1,a2,a3,a4,…,an)，A為指向空得順序表得指針。閱讀以下程序段，并回答問題:(1)寫出執(zhí)行下列程序段后得順序表A中得數(shù)據(jù)元素；if(head->next！=head){p=head—＞next;{A—〉data[A－>length+＋]=p—〉data;if（pnext!=head)p=p—>next；}（1）(a2，a4,…,)（2)將循環(huán)單鏈表中偶數(shù)結(jié)點(diǎn)位置得元素值寫入順序表A6、設(shè)順序表va中得數(shù)據(jù)元數(shù)遞增有序。試寫一算法,將x插入到順序表得適當(dāng)位置上，以保持該表答案:n=length(va［］);if（xva[iwhile（x〉va[i］)i++;for(j=n—1;j>=I；j--)va[j+1]＝va［jva[i]=x；}}7、假設(shè)線性表采用順序存儲(chǔ)結(jié)構(gòu)，表中元素值為整型。閱讀算法f2,設(shè)順序表L=(3,7,3,2,1，1,8，7,3),寫出執(zhí)行算法f2后得線性表L得數(shù)據(jù)元素,并描述該算法得功能。?}答案:if(j==k){[k]=L—〉data[i}L-〉length=k；刪除順序表中重復(fù)得元素8、已知線性表中得元素以值遞增有序排列,并以單鏈表作存儲(chǔ)結(jié)構(gòu)。試寫一算法,刪除表中所有大于x且小于y得元素（若表中存在這樣得元素)同時(shí)釋放被刪除結(jié)點(diǎn)空間。voidDelete_list（Lnode*head,ElemTypex,ElemTypey)｛Lnode*p,*q;p=head;q=p;{if(p->data>x）&＆(p—＞data<y)}i++;p=head；q=p;}p=q—>next；}｛q=p;p=p->next;｝}}9、在帶頭結(jié)點(diǎn)得循環(huán)鏈表L中,結(jié)點(diǎn)得數(shù)據(jù)元素為整型,且按值遞增有序存放。給定兩個(gè)整數(shù)a與b,且a〈b，編寫算法刪除鏈表L中元素值大于a且小于b得所有結(jié)點(diǎn)。一、選擇題1、一個(gè)棧得輸入序列為:a,b,c,d，e,則棧得不可能輸出得序列就是(）。?2、判斷一個(gè)循環(huán)隊(duì)列Q(最多n個(gè)元素）為滿得條件就是(Q—〉rear==Q－〉front+1C、Q—>front==(Q—〉rear+1）%n???D、Q->front==(Q->rear—1）%n3、設(shè)計(jì)一個(gè)判別表達(dá)式中括號(hào)就是否配對(duì)得算法，采用(）數(shù)據(jù)結(jié)構(gòu)最佳。4、帶頭結(jié)點(diǎn)得單鏈表head為空得判定條件就是().head—>next＝=NULL??C、head-〉nextNULL?D、head!=NULL5、一個(gè)棧得輸入序列為:1,2,3，4,則棧得不可能輸出得序列就是()。2134?C、1432D、4312?E、6、若用一個(gè)大小為6得數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列,且當(dāng)rear與front得值分別為0,3。當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear與front得值分別為(）。8、循環(huán)隊(duì)列得隊(duì)頭與隊(duì)尾指針分別為front與rear,則判斷循環(huán)隊(duì)列為空得條件就是()。9、一個(gè)順序棧S,其棧頂指針為top,則將元素e入棧得操作就是()。A、*S->top=e;S－〉top++；??B、S-＞top+＋;＊S-〉top=e;11、將遞歸算法轉(zhuǎn)換成對(duì)應(yīng)得非遞歸算法時(shí),通常需要使用（)來保存中間結(jié)果。12、棧得插入與刪除操作在（).位置13、五節(jié)車廂以編號(hào)1,2,3,4,5順序進(jìn)入鐵路調(diào)度站(棧),可以得到（)得編組。，3,5,2，414、判定一個(gè)順序棧S(?？臻g大小為n)為空得條件就是()。15、在一個(gè)鏈隊(duì)列中,front與rear分別為頭指針與尾指針,則插入一個(gè)結(jié)點(diǎn)s得操作為(）。C、rear—〉next=s；rear=s;?D、s-〉next=front;front=s;16、一個(gè)隊(duì)列得入隊(duì)序列就是1,2,3，4,則隊(duì)列得出隊(duì)序列就是（)。17、依次在初始為空得隊(duì)列中插入元素a，b,c,d以后,緊接著做了兩次刪除操作，此時(shí)得隊(duì)頭元素18、正常情況下，刪除非空得順序存儲(chǔ)結(jié)構(gòu)得堆棧得棧頂元素,棧頂指針top得變化就是()。19、判斷一個(gè)循環(huán)隊(duì)列Q(空間大小為M）為空得條件就是()。A、Q->front==Q—〉rear?B、Q-〉rear-Q-〉front－1＝＝M?C、Q—〉front+1=Q－〉rear??D、Q-〉rear+1=Q—〉front20、設(shè)計(jì)一個(gè)判別表達(dá)式中左右括號(hào)就是否配對(duì)出現(xiàn)得算法,采用（)數(shù)據(jù)結(jié)構(gòu)最佳。A、線性表得順序存儲(chǔ)結(jié)構(gòu)B、隊(duì)列??C、棧儲(chǔ)結(jié)構(gòu)23、若讓元素1,2,3依次進(jìn)棧,則出棧次序不可能就是()。24、循環(huán)隊(duì)列用數(shù)組A[0,m—1]存放其元素值，已知其頭尾指針分別就是front與rear,則當(dāng)前25、在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時(shí),通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū),主機(jī)將要輸出得數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則從該緩沖區(qū)中取走數(shù)據(jù)打印。該緩沖區(qū)應(yīng)該就是一個(gè)()A、鏈?zhǔn)酱鎯?chǔ)得線性結(jié)構(gòu)?B、鏈?zhǔn)酱鎯?chǔ)得非線性結(jié)構(gòu)C、限制存取點(diǎn)得線性結(jié)構(gòu)?D、限制存取點(diǎn)得非線性結(jié)構(gòu)27、在一個(gè)鏈隊(duì)列中，假定front與rear分別為隊(duì)頭指針與隊(duì)尾指針,刪除一個(gè)結(jié)點(diǎn)得操作就是（).A、front=front—〉nextB、rear=rear—〉next?C、rear—〉next=front??D、front—＞next=rearC、所包含得運(yùn)算個(gè)數(shù)不同?D、限定插入與刪除得位置不同二、填空題1、設(shè)棧S與隊(duì)列Q得初始狀態(tài)為空，元素e1，e2,e3,e4,e5,e6依次通過棧S,一個(gè)元素出棧后即進(jìn)入隊(duì)列Q,若6個(gè)元素出隊(duì)得序列就是e2,e4,e3,e6,e5,e1,則棧得容量至少應(yīng)該就2、一個(gè)循環(huán)隊(duì)列Q得存儲(chǔ)空間大小為M,其隊(duì)頭與隊(duì)尾指針分別為front與rear,則循環(huán)隊(duì)列中3、在具有n個(gè)元素得循環(huán)隊(duì)列中,隊(duì)滿時(shí)具有個(gè)元素。答案：n-14、設(shè)循環(huán)隊(duì)列得容量為70，現(xiàn)經(jīng)過一系列得入隊(duì)與出隊(duì)操作后,front為20，rear為11，則隊(duì)列中元素得個(gè)數(shù)為.答案：615、已知循環(huán)隊(duì)列得存儲(chǔ)空間大小為20，且當(dāng)前隊(duì)列得頭指針與尾指針得值分別為8與3，且該隊(duì)列得當(dāng)前得長(zhǎng)度為＿.三、判斷題2、在單鏈表中，要訪問某個(gè)結(jié)點(diǎn),只要知道該結(jié)點(diǎn)得地址即可;因此，單鏈表就是一種隨機(jī)存取結(jié)3、以鏈表作為棧得存儲(chǔ)結(jié)構(gòu)，出棧操作必須判別?？盏们闆r.√四、程序分析填空題1、已知棧得基本操作函數(shù):intStackEmpty(SqStack*S）;//判斷棧空intPush(SqStack*S，ElemTypee);/／入棧?intPop(SqStack*S,ElemType*e);／/出棧函數(shù)conversion實(shí)現(xiàn)十進(jìn)制數(shù)轉(zhuǎn)換為八進(jìn)制數(shù),請(qǐng)將函數(shù)補(bǔ)充完整。voidconversion(){?InitStack（S)；?scanf(?%d"，&N)；while（N){ (1）;N＝N/8;}while((2)）{Pop(S,＆e）;printf(“%d"，e)；}}//conversion答案:(1)Push(S,N%8)（2)!StackEmpty(S)intfunction(SqQueue*Q,ElemType*e){if（Q—〉front==Q->rear)?returnERROR;*e=Q-〉base[Q—>front］;?Q—〉front=（Q—>front+1)%MAXSIZE;returnOK；}3、閱讀算法f2，并回答下列問題:(1）設(shè)隊(duì)列Q=(1,3,5，2,4,6)。寫出執(zhí)行算法f2后得隊(duì)列Q;(2）簡(jiǎn)述算法f2得功能。voidf2(Queue*Q){DataTypee；if(!QueueEmpty(Q)){e＝DeQueue（Q)；f2(Q);EnQueue（Q，e）;}}答案:(1）6,4，2,5，3,1(2)將隊(duì)列倒置五、綜合題1、假設(shè)以帶頭結(jié)點(diǎn)得循環(huán)鏈表表示隊(duì)列,并且只設(shè)一個(gè)指針指向隊(duì)尾結(jié)點(diǎn),但不設(shè)頭指針,請(qǐng)寫出相應(yīng)得入隊(duì)列算法(用函數(shù)實(shí)現(xiàn)）.答案：voidEnQueue(Lnode*rear,ElemTypee)New=(Lnode*)malloc（sizeof（Lnode));If(!new）returnERROR;}2、已知Q就是一個(gè)非空隊(duì)列,S就是一個(gè)空棧。編寫算法,僅用隊(duì)列與棧得ADT函數(shù)與少量工作變voidmakeEmpty(SqStacks);?置空棧voidpush（SqStacks,ElemTypee);?元素e入棧ElemTypepop(SqStacks)；出棧,返回棧頂元素intisEmpty(SqStacks)；?判斷?？誺oidenQueue(Queueq，ElemTypee)；元素e入隊(duì)ElemTypedeQueue(Queueq)；出隊(duì)，返回隊(duì)頭元素intisEmpty(Queueq);?判斷隊(duì)空while(!isEmpty({x=pop(SqStacks)；}3、對(duì)于一個(gè)棧，給出輸入項(xiàng)A,B,C，D，如果輸入項(xiàng)序列為A,B,C,D,試給出全部可能得輸出序答案:出棧得可能序列：ABCDABDCACDBACBDADCBBACDBADCBCADBCDACBDACBADCDBADCBA一、選擇題1、設(shè)有兩個(gè)串S1與S2，求串S2在S1中首次出現(xiàn)位置得運(yùn)算稱作(C)。2、已知串S=’aaab’，則next數(shù)組值為（A）。A、0123?B、1123??C、1231D、12113、串與普通得線性表相比較,它得特殊性體現(xiàn)在(C）。A、順序得存儲(chǔ)結(jié)構(gòu)?B、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)??C、數(shù)據(jù)元素就是A、O(m)B、O（n)?C、O(m*n)D、O(nlog2m)6、與線性表相比,串得插入與刪除操作得特點(diǎn)就是（).A、通常以串整體作為操作對(duì)象???B、需要更多得輔助空間C、算法得時(shí)間復(fù)雜度較高?7、設(shè)SUBSTR(S,i,k）就是求S中從第i個(gè)字符開始得連續(xù)k個(gè)字符組成得子串得操作,則對(duì)于S=?Beijing&Nanjing'，SUBSTR（S，4,5)=（B）。ng&N’二、判斷題()1、造成簡(jiǎn)單模式匹配算法BF算法執(zhí)行效率低得原因就是有回溯存在。(√)2、KMP算法得最大特點(diǎn)就是指示主串得指針不需要回溯。(√)3、完全二叉樹某結(jié)點(diǎn)有右子樹,則必然有左子樹。三、填空題1、求子串在主串中首次出現(xiàn)得位置得運(yùn)算稱為模式匹配。2、設(shè)s='I︺AM︺A︺TEACHER’,其長(zhǎng)度就是_＿_(dá)_。3、兩個(gè)串相等得充分必要條件就是兩個(gè)串得長(zhǎng)度相等且對(duì)應(yīng)位置字符相同。四、程序填空題1、函數(shù)kmp實(shí)現(xiàn)串得模式匹配,請(qǐng)?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整。intkmp（sqstring*s,sqstring*t,intstart,intnext[]）{?while(i〈s—>len＆&j〈t-〉len)if（j〉=t—>len)}2、函數(shù)實(shí)現(xiàn)串得模式匹配算法，請(qǐng)?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整。intindex_bf(sqstring*s,sqstring＊t,intstart){while（i＜s—〉len&&j＜t—〉len)if(s—〉data[i]==t->data[j]){}}}/*listDelete*/3、寫出下面算法得功能.length;i++)?if(s—〉data[i]!＝s2??returns1-〉data[i]-s2—>data[i}while(i<s－〉len&＆j〈t—>len)ta[ii;j＋+;}else{}if(j〉=t->len)}答案:串得模式匹配算法一、選擇題1、設(shè)廣義表L＝((a,b,c)則L得長(zhǎng)度與深度分別為(C）。2、廣義表（(a),a)得表尾就是(B)。3、稀疏矩陣得常見壓縮存儲(chǔ)方法有(C)兩種。D、散列表與十字鏈表D、可以就是子表或原子5、數(shù)組A[0、、5,0、、6]得每個(gè)元素占5個(gè)字節(jié)，將其按列優(yōu)先次序存儲(chǔ)在起始地址為1000得內(nèi)存單元中，則元素A[5]［5]得地址就是(A).6、廣義表G＝(a，b(c,d,(e,f))，g)得長(zhǎng)度就是(A)。7、采用稀疏矩陣得三元組表形式進(jìn)行壓縮存儲(chǔ),若要完成對(duì)三元組表進(jìn)行轉(zhuǎn)置,只要將行與列對(duì)換,8、廣義表(a，b，c)得表尾就是(B)。9、常對(duì)數(shù)組進(jìn)行兩種基本操作就是(C).10、對(duì)一些特殊矩陣采用壓縮存儲(chǔ)得目得主要就是為了(D)。A、表達(dá)變得簡(jiǎn)單B、對(duì)矩陣元素得存取變得簡(jiǎn)單???C、去掉矩陣中得多余元素?D、減少不必要得存儲(chǔ)空間得開銷11、設(shè)有一個(gè)10階得對(duì)稱矩陣A,采用壓縮存儲(chǔ)方式,以行序?yàn)橹鞔鎯?chǔ)，a11為第一個(gè)元素,其存儲(chǔ)地址為1，每元素占1個(gè)地址空間,則a85得地址為(）.12、設(shè)矩陣A就是一個(gè)對(duì)稱矩陣，為了節(jié)省存儲(chǔ),將其下三角部分按行序存放在一維數(shù)組B[1,n(n—1)/2］中，對(duì)下三角部分中任一元素ai,j（i>=j)，在一維數(shù)組B得下標(biāo)位置k得值就是）／13、廣義表A=((a)，a)得表頭就A、二維數(shù)組與三維數(shù)組B、三元組與散列??C、三元組與十字鏈表?D、散列與十字鏈表15、假設(shè)以三元組表表示稀疏矩陣，則與如圖所示三元組表對(duì)應(yīng)得4×5得稀疏矩陣就是(注：矩陣A、由0個(gè)或多個(gè)原子或子表構(gòu)成得有限序列B、至少有一個(gè)元素就是子表?17、對(duì)廣義表L＝((a，b)(c,d）,(e,f)執(zhí)行head（tail(head(tail(L))))操作得二、判斷題（)1、廣義表中原子個(gè)數(shù)即為廣義表得長(zhǎng)度.()2、一個(gè)稀疏矩陣采用三元組表示,若把三元組中有關(guān)行下標(biāo)與列下標(biāo)得值互換，并把mu與nu得值進(jìn)行互換,則完成了矩陣轉(zhuǎn)置。三、填空題1、已知二維數(shù)組A[m][n]采用行序?yàn)橹鞣绞酱鎯?chǔ),每個(gè)元素占k個(gè)存儲(chǔ)單元，并且第一個(gè)元素得存儲(chǔ)地址就是LOC（A[0][0]則A［i][j]得地址就是___Loc(A[0］[0](i*N+jk__＿_(dá)。2、廣義表運(yùn)算式HEAD(TAIL((a,b,c）,(x,y，z)）)得結(jié)果就是：(x,y，3、二維數(shù)組,可以按照兩種不同得存儲(chǔ)方式.4、稀疏矩陣得壓縮存儲(chǔ)方式有:與。1、現(xiàn)有一個(gè)稀疏矩陣,請(qǐng)給出它得三元組表.答案:第六章樹一、選擇題2k2、用順序存儲(chǔ)得方法,將完全二叉樹中所有結(jié)點(diǎn)按層逐個(gè)從左到右得順序存放在一維數(shù)組R[1、、N]中，若結(jié)點(diǎn)R［i］有右孩子,則其右孩子就是(B).3、設(shè)a,b為一棵二叉樹上得兩個(gè)結(jié)點(diǎn),在中序遍歷時(shí),a在b前面得條件就是(B）.b得子孫4、設(shè)一棵二叉樹得中序遍歷序列：badce,后序遍歷序列：bdeca,則二叉樹先序遍歷序列為5、在一棵具有5層得滿二叉樹中結(jié)點(diǎn)總數(shù)為（A)。6、由二叉樹得前序與后序遍歷序列（B)惟一確定這棵二叉樹。7、某二叉樹得中序序列為ABCDEFG，后序序列為BDCAFGE,則其左子樹中結(jié)點(diǎn)數(shù)目為8、若以{4,5,6,7,8}作為權(quán)值構(gòu)造哈夫曼樹,則該樹得帶權(quán)路徑長(zhǎng)度為（C)。9、將一棵有100個(gè)結(jié)點(diǎn)得完全二叉樹從根這一層開始，每一層上從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào),根結(jié)點(diǎn)得編號(hào)為1,則編號(hào)為49得結(jié)點(diǎn)得左孩子編號(hào)為(A）。10、表達(dá)式a*（b+c）-d得后綴表達(dá)式就是(B)。11、對(duì)某二叉樹進(jìn)行先序遍歷得結(jié)果為ABDEFC,中序遍歷得結(jié)果為DBFEAC，則后序遍歷得結(jié)?A、DBFEAC??B、DFEBCA?C、BDFECA??D、BDEFACA、有序數(shù)據(jù)元素B、無序數(shù)據(jù)元素C、元素之間具有分支層次關(guān)系13、表達(dá)式A*（B＋C)/（D—E+F)得后綴表達(dá)式就是(C).+F?B、AB＊C+D/E—F+?C、ABC+*DE—F+/?D、ABCDED*＋/-+14、在線索二叉樹中,t所指結(jié)點(diǎn)沒有左子樹得充要條件就是().15、任何一棵二叉樹得葉結(jié)點(diǎn)在先序、中序與后序遍歷序列中得相對(duì)次序()。16、假定在一棵二叉樹中，度為2得結(jié)點(diǎn)數(shù)為15，度為1得結(jié)點(diǎn)數(shù)為30,則葉子結(jié)點(diǎn)數(shù)為()A、每個(gè)結(jié)點(diǎn)至多有兩棵子樹得樹??B、哈夫曼樹??C、每個(gè)結(jié)點(diǎn)至多有兩棵子樹得有序樹??D、每個(gè)結(jié)點(diǎn)只有一棵子樹18、用順序存儲(chǔ)得方法,將完全二叉樹中所有結(jié)點(diǎn)按層逐個(gè)從左到右得順序存放在一維數(shù)組R[1、、n]中,若結(jié)點(diǎn)R[i]有左孩子,則其左孩子就是（)。+1]??C、R[2i]??D、R[219、下面說法中正確得就是()。?C、子樹有嚴(yán)格左右之分得樹就是二叉樹???D、子樹有嚴(yán)格左右之分,且度不超過2得樹就是二叉樹20、樹得先根序列等同于與該樹對(duì)應(yīng)得二叉樹得()。層序序列21、按照二叉樹得定義，具有3個(gè)結(jié)點(diǎn)得二叉樹有（C22、由權(quán)值為3，6,7,2,5得葉子結(jié)點(diǎn)生成一棵哈夫曼樹,它得帶權(quán)路徑長(zhǎng)度為(A）。二、判斷題（)3、對(duì)于任意非空二叉樹,要設(shè)計(jì)其后序遍歷得非遞歸算法而不使用堆棧結(jié)構(gòu),最適合得方法就是對(duì)該二叉樹采用三叉鏈表。()4、在哈夫曼編碼中，當(dāng)兩個(gè)字符出現(xiàn)得頻率相同時(shí),其編碼也相同，對(duì)于這種情況應(yīng)做特殊處+1。三、填空題2、哈夫曼樹就是其樹得帶權(quán)路徑長(zhǎng)度最小得二叉樹。3、在一棵二叉樹中,度為0得結(jié)點(diǎn)得個(gè)數(shù)就是n0,度為2得結(jié)點(diǎn)得個(gè)數(shù)為n2，則有n0=N2+1。4、樹內(nèi)各結(jié)點(diǎn)度得最大值稱為樹得度。四、代碼填空題1、函數(shù)InOrderTraverse(Bitreebt）實(shí)現(xiàn)二叉樹得中序遍歷,請(qǐng)?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完??InOrderTraverse(bt—〉lchild）;?}2、函數(shù)depth實(shí)現(xiàn)返回二叉樹得高度，請(qǐng)?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整。intdepth(Bitree*t){??if(t==NULL)??return0;else{??hl=depth(t—＞lchild???hr=???if(hl〉hr）??returnhl+1；??else?returnhr+1；}????}Bitree*function（Bitree*bt){Bitree*t,*t1,*t2;if（bt==NULL)??t=NULL；?else{??t=(Bitree＊)malloc(sizeof（Bitree）)；???t—〉data=bt-〉data;??t1=function(bt-＞left)??t2＝function(bt-〉right);???t->left=t2;???t—〉right=t1；}?return（t）;}答案：交換二叉樹結(jié)點(diǎn)左右子樹得遞歸算法4、寫出下面算法得功能.voidfunction(Bitree*t){if（p！=NULL){function(p—〉lchild);function(p->rchild）;printf(?%d”,p-〉data);}答案:二叉樹后序遍歷遞歸算法五、綜合題1、假設(shè)以有序?qū)Γ紁,c〉表示從雙親結(jié)點(diǎn)到孩子結(jié)點(diǎn)得一條邊,若已知樹中邊得集合為{〈a,b〉，<a,d>,<a，c〉,〈c,e>,〈c，f＞，<c，g>，<c,h>，<e,i〉,〈e，j＞，〈g,k>},請(qǐng)回答下列問題:(1)哪個(gè)結(jié)點(diǎn)就是根結(jié)點(diǎn)？（3）哪些結(jié)點(diǎn)就是k得祖先?(4)哪些結(jié)點(diǎn)就是j得兄弟?(5)樹得深度就是多少？。2、假設(shè)一棵二叉樹得先序序列為EBADCFHGIKJ，中序序列為ABCDEFGHIJK，請(qǐng)畫出該二叉樹.3、假設(shè)用于通訊得電文僅由8個(gè)字母A、B、C、D、E、F、G、H組成，字母在電文中出現(xiàn)得頻率分別為:0、07,0、19,0、02,0、06,0、32,0、03,0、21,0、10。請(qǐng)為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。010101017AH02CG01513FB6D4、已知二叉樹得先序遍歷序列為ABCDEFGH，中序遍歷序列為CBEDFAGH,畫出二叉樹。答案:二叉樹形態(tài)ABCEGDFH5、試用權(quán)集合{12,4,5，6，1,2}構(gòu)造哈夫曼樹,并計(jì)算哈夫曼樹得帶權(quán)路徑長(zhǎng)度。743561+(4+5+6)＊31+2)＊4=126、已知權(quán)值集合為｛5,7,2,3，6,9},要求給出哈夫曼樹,并計(jì)算帶權(quán)路徑長(zhǎng)度WPL。55(2)帶權(quán)路徑長(zhǎng)度:WPL=（6+7＋9)*2+5*3+(2＋3）*4=44＋15+20=797、已知一棵二叉樹得先序序列：ABDGJEHCFIKL;中序序列:DJGBEHACKILF.畫出二叉樹得ABDECF答案:GJHKIL8、一份電文中有6種字符：A，B,C,D,E,F,它們得出現(xiàn)頻率依次為16,5，9,3,30,1，完成（1）設(shè)計(jì)一棵哈夫曼樹;(畫出其樹結(jié)構(gòu)）（2)計(jì)算其帶權(quán)路徑長(zhǎng)度WPL;9954(2)帶權(quán)路徑長(zhǎng)度:WPL=30*1+16*2+9*3+5*4+(1+3)*5=30+32+27+20+20＝1299、已知某森林得二叉樹如下所示,試畫出它所表示得森林。AABCFGHDE答案:ADHADHEFBCEFG10、有一分電文共使用5個(gè)字符；a,b，c，d，e，它們得出現(xiàn)頻率依次為4、7、5、2、9,試構(gòu)造哈夫曼樹,并給出每個(gè)字符得哈夫曼編碼。11、畫出與下圖所示得森林相對(duì)應(yīng)得二叉樹,并指出森林中得葉子結(jié)點(diǎn)在二叉樹中具有什么特點(diǎn)。IJIJMNACFHBEDG12、如下所示得二叉樹,請(qǐng)寫出先序、中序、后序遍歷得序列.答案:先序:FDBACEGIHJ中序:ABCDEFGHIJ后序：ACBEDHJIGF六、編程題1、編寫求一棵二叉樹中結(jié)點(diǎn)總數(shù)得算法。答案：(以先序遍歷得方法為例)voidcount_preorder（Bitree*t,int*n）{{＊n++;count_preorder(t-〉lchild);count_preorder(t—〉lchild);}}一、選擇題1、12、對(duì)于具有n個(gè)頂點(diǎn)得圖，若采用鄰接矩陣表示，則該矩陣得大小為()。22、如果從無向圖得任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問所有頂點(diǎn)，則該圖一定就是A、從源點(diǎn)到匯點(diǎn)得最長(zhǎng)路徑?B、從源點(diǎn)到匯點(diǎn)得最短路徑?4、下面（）可以判斷出一個(gè)有向圖中就是否有環(huán)(回路)。5、帶權(quán)有向圖G用鄰接矩陣A存儲(chǔ),則頂點(diǎn)i得入度等于A中.?A、第i行非無窮得元素之與?B、第i列非無窮得元素個(gè)數(shù)之與C、第i行非無窮且非0得元素個(gè)數(shù)?D、第i行與第i列非無窮且非0得元素之與6、采用鄰接表存儲(chǔ)得圖,其深度優(yōu)先遍歷類似于二叉樹得。8、當(dāng)利用大小為N得數(shù)組存儲(chǔ)循環(huán)隊(duì)列時(shí),該隊(duì)列得最大長(zhǎng)度就是（)。9、鄰接表就是圖得一種.A、順序存儲(chǔ)結(jié)構(gòu)B、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C、索引存儲(chǔ)結(jié)構(gòu)D、散列存儲(chǔ)結(jié)構(gòu)10、下面有向圖所示得拓?fù)渑判虻媒Y(jié)果序列就是（)。3456?D、52164311、在無向圖中定義頂點(diǎn)vi與vj之間得路徑為從vi到vj得一個(gè)(）。邊得條數(shù)?12、在有向圖得逆鄰接表中，每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有（）鄰接點(diǎn)。13、設(shè)G1=(V1，E1)與G2=(V2,E2）為兩個(gè)圖,如果V1V2，E1E2則稱(）。A、G1就是G2得子圖?B、G2就是G1得子圖C、G1就是G2得連通分量D、G2就是G1得連通分量14、已知一個(gè)有向圖得鄰接矩陣表示,要?jiǎng)h除所有從第i個(gè)結(jié)點(diǎn)發(fā)出得邊,應(yīng)()。A、將鄰接矩陣得第i行刪除B、將鄰接矩陣得第i行元素全部置為0?C、將鄰接矩陣得第i列刪除?D、將16、在一個(gè)有向圖中，所有頂點(diǎn)得入度之與等于所有頂點(diǎn)得出度之與得(）倍.17、下列關(guān)于圖遍歷得說法不正確得就是(）.A、連通圖得深度優(yōu)先搜索就是一個(gè)遞歸過程?B、圖得廣度優(yōu)先搜索中鄰接點(diǎn)得尋找具有“先進(jìn)先出”得特征?C、非連通圖不能用深度優(yōu)先搜索法???D、圖得遍歷要求每一頂點(diǎn)僅被訪問一次18、帶權(quán)有向圖G用鄰接矩陣A存儲(chǔ),則頂點(diǎn)i得入度為A中：()。C、第i行非∞且非0得元素個(gè)數(shù)D、第i列非∞且非0得元素個(gè)數(shù)19、采用鄰接表存儲(chǔ)得圖得廣度優(yōu)先遍歷算法類似于二叉樹得(）.20、一個(gè)具有n個(gè)頂點(diǎn)得有向圖最多有(）條邊。1)/2B、n×(n-1）?C、n×(n+1)/2??D、n221、已知一個(gè)有向圖得鄰接表存儲(chǔ)結(jié)構(gòu)如圖所示,根據(jù)深度優(yōu)先遍歷算法,從頂點(diǎn)v1出發(fā)，所得到得24v1,v4，v3,v22、關(guān)鍵路徑就是事件結(jié)點(diǎn)網(wǎng)絡(luò)中(A、從源點(diǎn)到匯點(diǎn)得最長(zhǎng)路徑?B、從源點(diǎn)到匯點(diǎn)得最短路徑A、連通分量就是無向圖中得極小連通子圖?B、強(qiáng)連通分量就是有向圖中得極大強(qiáng)連通子圖?C、在一個(gè)有向圖得拓?fù)湫蛄兄腥繇旤c(diǎn)a在頂點(diǎn)b之前，則圖中必有一條弧〈a,b>D、對(duì)有向圖G,如果以任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索能訪問到每個(gè)頂點(diǎn),則該圖一定就是完全圖24、假設(shè)有向圖含n個(gè)頂點(diǎn)及e條弧,則表示該圖得鄰接表中包含得弧結(jié)點(diǎn)個(gè)數(shù)為()。26、為便于判別有向圖中就是否存在回路,可借助于。A、廣度優(yōu)先搜索算法?B、最小生成樹算法?C、最短路徑算法???D、拓?fù)渑判蛩惴ù嬖?8、已知一有向圖得鄰接表存儲(chǔ)結(jié)構(gòu)如圖所示,根據(jù)有向圖得廣度優(yōu)先遍歷算法，從頂點(diǎn)v1出發(fā)，所29、對(duì)于一個(gè)有向圖,若一個(gè)頂點(diǎn)得入度為k1,、出度為k2,則對(duì)應(yīng)鄰接表中該頂點(diǎn)單鏈表中得結(jié)點(diǎn)數(shù)為1+k2?D、k1—30、一個(gè)具有8個(gè)頂點(diǎn)得有向圖中，所有頂點(diǎn)得入度之與與所有頂點(diǎn)得出度之與得差等于()。31、無向圖中一個(gè)頂點(diǎn)得度就是指圖中()。A、通過該頂點(diǎn)得簡(jiǎn)單路徑數(shù)??B、與該頂點(diǎn)相鄰接得頂點(diǎn)數(shù)?C、與該頂點(diǎn)連通得頂點(diǎn)數(shù)???D、通過該頂點(diǎn)得回路數(shù)二、填空題1、n個(gè)頂點(diǎn)得連通圖至少有邊。答案:n—1條2、一個(gè)連通圖得生成樹就是一個(gè)，它包含圖中所有頂點(diǎn),但只有足以構(gòu)成一棵答案:極小連通子圖3、一個(gè)圖得表示法就是惟一得。答案:鄰接矩陣4、遍歷圖得基本方法有深度優(yōu)先搜索與廣度優(yōu)先搜索,其中就是一個(gè)遞歸過程.答案：深度優(yōu)先搜索5、在無向圖G得鄰接矩陣A中,若A［i］[j]等于1，則A［j][i]等于.6、判定一個(gè)有向圖就是否存在回路,可以利用。答案:拓?fù)渑判?、已知一個(gè)圖得鄰接矩陣表示，計(jì)算第i個(gè)結(jié)點(diǎn)得入度得方法就是.9、已知一個(gè)圖得鄰接矩陣表示,刪除所有從第i個(gè)結(jié)點(diǎn)出發(fā)得邊得方法就是。10、若以鄰接矩陣表示有向圖,則鄰接矩陣上第i行中非零元素得個(gè)數(shù)即為頂點(diǎn)vi得。三、判斷題2、一個(gè)圖得廣度優(yōu)先搜索樹就是惟一得.X3、圖得深度優(yōu)先搜索序列與廣度優(yōu)先搜索序列不就是惟一得?！?、鄰接表只能用于存儲(chǔ)有向圖,而鄰接矩陣則可存儲(chǔ)有向圖與無向圖.X5、存儲(chǔ)圖得鄰接矩陣中,鄰接矩陣得大小不但與圖得頂點(diǎn)個(gè)數(shù)有關(guān)，而且與圖得邊數(shù)也有關(guān).X6、AOV網(wǎng)就是一個(gè)帶權(quán)得有向圖。X7、從源點(diǎn)到終點(diǎn)得最短路徑就是唯一得。X8、鄰接表只能用于存儲(chǔ)有向圖，而鄰接矩陣則可存儲(chǔ)有向圖與無向圖.X9、圖得生成樹就是惟一得。X四、程序分析題?typedefstruct{intvexnum,arcnum;charvexs[N];}graph;voidfuntion(inti,graph*g){?visited[i]=TRUE;?for（j=0;j〈g-〉vexnum;j++)if（(g—〉arcs[i］[j］==1）&&（!visited[j]))function（j,g);答案：實(shí)現(xiàn)圖得深度優(yōu)先遍歷算法五、綜合題1、已知圖G得鄰接矩陣如下所示:(2)根據(jù)prim算法，求圖G從頂點(diǎn)1出發(fā)得最小生成樹，要求表示出其每一步生成過程.(用圖或者表得方式均可)。11322442113224422（2)最小生成樹(prim算法）22、設(shè)一個(gè)無向圖得鄰接矩陣如下圖所示：答案1）圖形態(tài)035035(2)深度優(yōu)先搜索樹1243、寫出下圖中全部可能得拓?fù)渑判蛐蛄小?、AOE網(wǎng)G如下所示,求關(guān)鍵路徑。（要求標(biāo)明每個(gè)頂點(diǎn)得最早發(fā)生時(shí)間與最遲發(fā)生時(shí)間,并畫出關(guān)鍵路徑)答案：答案：(1）最早發(fā)生時(shí)間與最遲發(fā)生時(shí)間:（2)關(guān)鍵路徑：68頂點(diǎn)vl82225、已知有向圖G如下所示,根據(jù)迪杰斯特拉算法求頂點(diǎn)v0到其她頂點(diǎn)得最短距離。(給出求解過答案答案:終點(diǎn)從v0到各終點(diǎn)得d值與最短路徑得求解過程v24(v0,v2)s{v0,v2}{v0,v4}{v0,v4,v1}{v0，v4,v3}答案:prim算法求最小生成樹如下:444444264426445445527、已知有向圖如下所示，請(qǐng)寫出該圖所有得拓?fù)湫蛄小?、如下圖所示得AOE網(wǎng),求:VeVl7244EQ\*jc3\*hps23\o\al(\s\up9(a),5)4EQ\*jc3\*hps23\o\al(\s\up9(a),26)答案：(1)求ve與vl(2）關(guān)鍵路徑事件vl**346458*67***619724如下所示得有向圖，回答下面問題:(1）該圖就是強(qiáng)連通得嗎？若不就是，給出強(qiáng)連通分量.(2)請(qǐng)給出圖得鄰接矩陣與鄰接表表示。答案：(1)就是強(qiáng)連通圖(2)鄰接矩陣與鄰接表為：9、已知圖G得鄰接矩陣A＝，試畫出它所表示得圖G，并根據(jù)Prim算法求出圖得得最小生成樹（給出生成過程).(1(1)圖形態(tài):1924(2）prim算法求最小生成樹:1118214810、如下圖所示得AOV網(wǎng),寫出其中三種拓?fù)渑判蛐蛄小?1、已知圖G如下,根據(jù)克魯斯卡爾算法求圖G得一棵最小生成樹。(要求給出構(gòu)造過程）答案：kruskal算法得最小生成樹B2FB2FABDBD2432B2FB2FABDBD24323FD3K333HHHD3K4D3K4EAAABBDB442435AAABBDB442435CF3HD3K4E12、已知圖G如下所示,求從頂點(diǎn)a到其余各頂點(diǎn)得最短路徑。（給出求解過程)55365c4bdeabcdefvjSb)3∞∞∞c{a，c}最短路徑求解過程5(a,c，b)∞bc,d)7∞de{a,c,e}ff}一、選擇題1、已知一個(gè)有序表為(11,22,33,44,55,66,77,88,99）,則折半查找55需要比較哈希表得表長(zhǎng)為13,哈希函數(shù)為H(key）=keyMOD13,沖突解決得辦法為鏈地址法,請(qǐng)構(gòu)造哈希表(用圖表示）.3、解決哈希沖突得主要方法有。?A、數(shù)字分析法、除余法、平方取中法????B、數(shù)字分析法、除余法、線性探測(cè)法C、數(shù)字分析法、線性探測(cè)法、再哈希法?D、線性探測(cè)法、再哈希法、鏈地址法4、在一棵深度為h得具有n個(gè)元素得二叉排序樹中,查找所有元素得最長(zhǎng)查找長(zhǎng)度為(）。1)/2D、h5、已知表長(zhǎng)為25得哈希表，用除留取余法，按公式H（key）=keyMODp建立哈希表，則p6、設(shè)哈希表長(zhǎng)m=14，哈希函數(shù)H（key）=keyMOD11。表中已有4個(gè)結(jié)點(diǎn):addr(15）=4,addr(38）=5,addr（61)=6,addr(84）=7其余地址為空，如用二次探測(cè)再散列處理沖突,則關(guān)鍵字為49得地址為(A).7、在散列查找中,平均查找長(zhǎng)度主要與（C)有關(guān)。A、散列表長(zhǎng)度B、散列元素個(gè)數(shù)??C、裝填因子?D、處理沖8、根據(jù)一組記錄(56,42,50,64,48）依次插入結(jié)點(diǎn)生成一棵AVL樹，當(dāng)插入到值為得結(jié)點(diǎn)時(shí)需要進(jìn)行旋轉(zhuǎn)調(diào)整.9、m階B—樹中得m就是指（)。A、每個(gè)結(jié)點(diǎn)至少具有m棵子樹????B、每個(gè)結(jié)點(diǎn)最多具有m棵子樹?10、一個(gè)待散列得線性表為k=｛18,25,63,50,42,32,9},散列函數(shù)為H(k)＝kMOD9,與18發(fā)生沖突得元素有()個(gè)。11、在對(duì)查找表得查找過程中，若被查找得數(shù)據(jù)元素不存在,則把該數(shù)據(jù)元素插到集合中,這種方式兩種表都不適合值為82得結(jié)點(diǎn)時(shí),(B)次比較后查找成功.13、在各種查找方法中,平均查找承擔(dān)與結(jié)點(diǎn)個(gè)數(shù)n無關(guān)得查找方法就是（C）。14、下列二叉樹中,不平衡得二叉樹就是(C)..15、對(duì)一棵二叉排序樹按(B)遍歷,可得到結(jié)點(diǎn)值從小到大得排列序列。16、解決散列法中出現(xiàn)得沖突問題常采用得方法就是(D).A、數(shù)字分析法、除余法、平方取中法?B、數(shù)字分析法、除余法、線性探C、數(shù)字分析法、線性探測(cè)法、多重散列法??D、線性探測(cè)法、多重散列法、鏈地址法17、對(duì)線性表進(jìn)行折半查找時(shí),要求線性表必須（C)。C、以順序方式存儲(chǔ),且結(jié)點(diǎn)按關(guān)鍵字有序排序D、以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序二、填空題1、在散列函數(shù)H(key)=key%p中，p應(yīng)取。2次查找可確定成功.3、具有相同函數(shù)值得關(guān)鍵字對(duì)哈希函數(shù)來說稱為.4、在一棵二叉排序樹上實(shí)施遍歷后，其關(guān)鍵字序列就是一個(gè)有序表。5、在散列存儲(chǔ)中,裝填因子α得值越大，則存取元素時(shí)發(fā)生沖突得可能性就越大;α值越小,則存取元素發(fā)生沖突得可能性就越小。三、判斷題(×)1、折半查找只適用于有序表,包括有序得順序表與鏈表.（)2、二叉排序樹得任意一棵子樹中，關(guān)鍵字最小得結(jié)點(diǎn)必?zé)o左孩子，關(guān)鍵字最大得結(jié)點(diǎn)必?zé)o右孩（)3、哈希表得查找效率主要取決于哈希表造表時(shí)所選取得哈希函數(shù)與處理沖突得方法。（)4、平衡二叉樹就是指左右子樹得高度差得絕對(duì)值不大于1得二叉樹。(√)5、AVL就是一棵二叉樹，其樹上任一結(jié)點(diǎn)得平衡因子得絕對(duì)值不大于1。1、選取哈希函數(shù)H(k)=（k）MOD11。用二次探測(cè)再散列處理沖突，試在0—10得散列地址空間中對(duì)關(guān)鍵字序列(22,41,53,46，30,13,01,67)造哈希表,并求等概率情況下查找成功時(shí)得平均查找長(zhǎng)度.答案:(1)表形態(tài):(2)ASL：ASL(7)=(1*5+2*1+3＊17＝(5+2+3)/7=10/72、設(shè)哈希表HT表長(zhǎng)m為13,哈希函數(shù)為H(k)=kMODm,給定得關(guān)鍵值序列為{19,14,23,10，68，20,84,27,55，11}。試求出用線性探測(cè)法解決沖突時(shí)所構(gòu)造得哈希表，并求出在等概率得情況下查找成功得平均查找長(zhǎng)度ASL.答案：(1)表形態(tài)：（2)平均查找長(zhǎng)度:ASL(10）=（1*5+2＊4＋3*1）/10=1、63、設(shè)散列表容量為7（散列地址空間0、、6),給定表（30，36,47,52,34),散列函數(shù)H（K）=Kmod6,采用線性探測(cè)法解決沖突,要求：（1)構(gòu)造散列表;（2）查找34得比較次數(shù)：34、已知下面二叉排序樹得各結(jié)點(diǎn)得值依次為1-9，請(qǐng)標(biāo)出各結(jié)點(diǎn)得值.答案:52,68序樹。畫出生成后得二叉排序樹（不需畫出生成過程).ey)=keyMOD13,采用開放地址法得二次探測(cè)再散列方法解決沖突,試在0-18得散列空間中對(duì)關(guān)鍵字序列構(gòu)造哈希表,畫出哈希表,并求其查找成功時(shí)得平均查找長(zhǎng)度。7、已知關(guān)鍵字序列{11,2，13,26，5，18,4，9}，設(shè)哈希表表長(zhǎng)為16,哈希函數(shù)H(key)=keyMOD13,處理沖突得方法為線性探測(cè)法,請(qǐng)給出哈希表,并計(jì)算在等概率得條件下得平均查找長(zhǎng)8、設(shè)散列表得長(zhǎng)度為m=13，散列函數(shù)為H(k)＝kMODm，給定得關(guān)鍵碼序列為19,14，253813538134407717119、依次讀入給定得整數(shù)序列｛7,16,4,8,20，9,6，18，5構(gòu)造一棵二叉排序樹，并計(jì)算在等概率情況下該二叉排序樹得平均查找長(zhǎng)度ASL。（要求給出構(gòu)造過程)10、設(shè)有一組關(guān)鍵字(19,1,23，14,55，20,84,27,68，11，10,77),采用哈希函數(shù)H（key)=key%13,采用二次探測(cè)再散列得方法解決沖突,試在0—18得散列地址空間中對(duì)該關(guān)鍵字序列構(gòu)造哈希表.答案:0311122314253