2023年電大數(shù)據(jù)結(jié)構(gòu)本形成性考核冊(cè)作業(yè)

數(shù)據(jù)結(jié)構(gòu)（本)形成性考核作業(yè)冊(cè)使用說明本作業(yè)冊(cè)是中央廣播電視大學(xué)計(jì)算機(jī)科與技術(shù)專業(yè)（本科）數(shù)據(jù)結(jié)構(gòu)(本）課程形成性考核的依據(jù),與《數(shù)據(jù)結(jié)構(gòu)(本科）》教材（李偉生主編,中央電大出版社出版)配套使用。數(shù)據(jù)結(jié)構(gòu)（本）課程是中央廣播電視大學(xué)計(jì)算機(jī)科學(xué)技術(shù)專業(yè)的一門統(tǒng)設(shè)必修、學(xué)位課程，4學(xué)分,共72學(xué)時(shí)。其中實(shí)驗(yàn)24學(xué)時(shí),開設(shè)一學(xué)期。本課程的特點(diǎn)是綜合性、實(shí)踐性強(qiáng),內(nèi)容抽象,在專業(yè)中具有承上啟下的作用。因此，在學(xué)習(xí)本課程時(shí)，要注意理論聯(lián)系實(shí)際，結(jié)合教學(xué)內(nèi)容進(jìn)行上機(jī)實(shí)踐,認(rèn)真完畢作業(yè)和實(shí)驗(yàn)內(nèi)容。本課程的總成績(jī)按百分制記分，其中形成性考核所占的比例為30%,終結(jié)性考試占7０％（閉卷，答題時(shí)限為９0分鐘)。課程總成績(jī)達(dá)成６０分及以上者為合格，可以獲得該課程的學(xué)分。本課程的學(xué)位課程學(xué)分為70分，即課程總成績(jī)達(dá)成70分及以上者有資格申請(qǐng)專業(yè)學(xué)位。本課程共設(shè)計(jì)了4次形考作業(yè),每次形考作業(yè)均涉及實(shí)驗(yàn)內(nèi)容,由各地電大根據(jù)學(xué)生對(duì)作業(yè)中各種題型練習(xí)和實(shí)驗(yàn)的完畢情況進(jìn)行考核。對(duì)于實(shí)驗(yàn)內(nèi)容規(guī)定按實(shí)驗(yàn)規(guī)定認(rèn)真完畢，并提交實(shí)驗(yàn)報(bào)告。數(shù)據(jù)結(jié)構(gòu)(本)課程作業(yè)作業(yè)1(本部分作業(yè)覆蓋教材第1-２章的內(nèi)容）一、單項(xiàng)選擇題1．在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為(）。A．動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B．緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)Ｃ.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D.內(nèi)部結(jié)構(gòu)和外部機(jī)構(gòu)2.下列說法中，不對(duì)的的是()。Ａ.數(shù)據(jù)元素是數(shù)據(jù)的基本單位Ｂ.數(shù)據(jù)項(xiàng)是數(shù)據(jù)中不可分割的最小可標(biāo)記單位C．?dāng)?shù)據(jù)可有若干個(gè)數(shù)據(jù)元素構(gòu)成Ｄ．?dāng)?shù)據(jù)項(xiàng)可由若干個(gè)數(shù)據(jù)元素構(gòu)成3．一個(gè)存儲(chǔ)結(jié)點(diǎn)存儲(chǔ)一個(gè)（）。A.數(shù)據(jù)項(xiàng)Ｂ.數(shù)據(jù)元素C．?dāng)?shù)據(jù)結(jié)構(gòu)D.數(shù)據(jù)類型４.數(shù)據(jù)結(jié)構(gòu)中,與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的(）。A．存儲(chǔ)結(jié)構(gòu)Ｂ.物理結(jié)構(gòu)C．邏輯結(jié)構(gòu)D．物理和存儲(chǔ)結(jié)構(gòu)５．下列的敘述中,不屬于算法特性的是()。A.有窮性B.輸入性C．可行性D.可讀性６．算法分析的目的是()。Ａ.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中的輸入和輸出的關(guān)系Ｃ．分析算法的效率以求改善Ｄ.分析算法的易懂性和文檔性７．?dāng)?shù)據(jù)結(jié)構(gòu)是一門研究計(jì)算機(jī)中(

)對(duì)象及其關(guān)系的科學(xué)。A.數(shù)值運(yùn)算

B．非數(shù)值運(yùn)算C．集合

D.非集合8.算法的時(shí)間復(fù)雜度與（)有關(guān)。Ａ.所使用的計(jì)算機(jī)B．與計(jì)算機(jī)的操作系統(tǒng)Ｃ．與算法自身D．與數(shù)據(jù)結(jié)構(gòu)9．設(shè)有一個(gè)長(zhǎng)度為ｎ的順序表，要在第i個(gè)元素之前(也就是插入元素作為新表的第ｉ個(gè)元素)，則移動(dòng)元素個(gè)數(shù)為()。A．ｎ-i+1B．ｎ-iＣ.n-ｉ-1Ｄ.i1０.設(shè)有一個(gè)長(zhǎng)度為n的順序表,要?jiǎng)h除第ｉ個(gè)元素移動(dòng)元素的個(gè)數(shù)為(）。A.n-i+１B．n-iＣ.n-i-１D.i11.在一個(gè)單鏈表中,p、q分別指向表中兩個(gè)相鄰的結(jié)點(diǎn)，且ｑ所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接后繼,現(xiàn)要?jiǎng)h除q所指結(jié)點(diǎn)，可用語句()。A.p=ｑ->nexｔB．p->nexｔ=ｑＣ．p->ｎeｘt=qｎｅｘtD.q->ｎｅxt=ＮULL１2.在一個(gè)單鏈表中ｐ所指結(jié)點(diǎn)之后插入一個(gè)s所指的結(jié)點(diǎn)時(shí),可執(zhí)行(）。A.ｐ－>next=s;snext=pneｘtB.p->next=snexｔ;C.p=ｓ-＞nextD.s->next=p-＞nｅxt;p-＞ｎext＝s；13．非空的單向循環(huán)鏈表的尾結(jié)點(diǎn)滿足(

）（設(shè)頭指針為ｈead，指針p指向尾結(jié)點(diǎn))。A．．P－>ｎext＝=NULLB．P==NULLC．P-＞nｅxｔ==headD.P=＝hｅad14．鏈表不具有的特點(diǎn)是(）。A．可隨機(jī)訪問任一元素Ｂ.插入刪除不需要移動(dòng)元素Ｃ．不必事先估計(jì)存儲(chǔ)空間D.所需空間與線性表長(zhǎng)度成正比15.帶頭結(jié)點(diǎn)的鏈表為空的判斷條件是（

)(設(shè)頭指針為ｈead）。Ａ．heａd==NULLＢ.ｈeaｄ->ｎext==NULL

C．head->next＝=heaｄ

Ｄ.heａd!＝NUＬL１6．在一個(gè)單鏈表中，p、q分別指向表中兩個(gè)相鄰的結(jié)點(diǎn)，且ｑ所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接后繼,現(xiàn)要?jiǎng)h除ｑ所指結(jié)點(diǎn)，可用語句(

)。A.p=q－>nｅxtB．p->neｘt＝ｑ

C．p－>nｅｘt=q->ｎextD.q->nｅｘt=NULL1７.在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算為(）。Ａ.r=ｆ->next；B.r=r－＞nｅｘt;Ｃ.ｆ=f->neｘｔ;D.f＝r->ｎexｔ;１８．在一個(gè)鏈隊(duì)中,假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針,則插入s所指結(jié)點(diǎn)的運(yùn)算為（)。Ａ．f->ｎｅｘt=s;ｆ=s;B.ｒ-＞neｘt＝s;r=s;C.s-＞nexｔ=r；ｒ=s;D.s->nｅxt=f;f=s;19.一個(gè)順序表第一個(gè)元素的存儲(chǔ)地址是９0,每個(gè)元素的長(zhǎng)度為2,則第6個(gè)元素的地址是（）。A.9８B．100C．1０2D.１20．有關(guān)線性表的對(duì)的說法是（）。A．每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼B.線性表至少規(guī)定一個(gè)元素C.表中的元素必須按由小到大或由大到下排序D．除了一個(gè)和最后一個(gè)元素外,其余元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼二、填空題1．在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)結(jié)構(gòu)的線性表中，向第i(1in+1)個(gè)元素之前插入新元素時(shí),需向后移動(dòng)個(gè)數(shù)據(jù)元素。2.從長(zhǎng)度為n的采用順序存儲(chǔ)結(jié)構(gòu)的線性表中刪除第ｉ(1in+１)個(gè)元素,需向前移動(dòng)個(gè)元素。3．?dāng)?shù)據(jù)結(jié)構(gòu)按結(jié)點(diǎn)間的關(guān)系,可分為4種邏輯結(jié)構(gòu)：、、、。4.數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表達(dá)稱為或。５.除了第1個(gè)和最后一個(gè)結(jié)點(diǎn)外，其余結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)為，每個(gè)結(jié)點(diǎn)可有任意多個(gè)前驅(qū)和后繼結(jié)點(diǎn)數(shù)的結(jié)構(gòu)為。6．算法的５個(gè)重要特性是、、、、。7．?dāng)?shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱為________結(jié)構(gòu)。８．?dāng)?shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)多的關(guān)系稱為＿_(dá)＿_(dá)__＿_(dá)結(jié)構(gòu)。9.數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)一的關(guān)系稱為______＿_(dá)結(jié)構(gòu)。10．規(guī)定在n個(gè)數(shù)據(jù)元素中找其中值最大的元素，設(shè)基本操作為元素間的比較。則比較的次數(shù)和算法的時(shí)間復(fù)雜度分別為____＿_(dá)__和＿_(dá)___＿＿＿。11．在一個(gè)單鏈表中ｐ所指結(jié)點(diǎn)之后插入一個(gè)ｓ所指結(jié)點(diǎn)時(shí),應(yīng)執(zhí)行________和ｐ->ｎext＝s;的操作。12.設(shè)有一個(gè)頭指針為hｅaｄ的單向循環(huán)鏈表,ｐ指向鏈表中的結(jié)點(diǎn),若p-＞neｘt==__＿＿＿_(dá)＿_(dá)，則p所指結(jié)點(diǎn)為尾結(jié)點(diǎn)。13．在一個(gè)單向鏈表中,要?jiǎng)h除p所指結(jié)點(diǎn)，已知q指向p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。則可以用操作＿_(dá)_＿_(dá)___。1４.設(shè)有一個(gè)頭指針為heaｄ的單向鏈表,ｐ指向表中某一個(gè)結(jié)點(diǎn),且有p->ｎeｘt=＝NULL，通過操作__＿_(dá)__＿_(dá)，就可使該單向鏈表構(gòu)導(dǎo)致單向循環(huán)鏈表。15．每個(gè)結(jié)點(diǎn)只包含一個(gè)指針域的線性表叫。１６．線性表具有和兩種存儲(chǔ)結(jié)構(gòu)。17．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的關(guān)系無關(guān),是獨(dú)立于計(jì)算機(jī)的。18．在雙向循環(huán)鏈表的每個(gè)結(jié)點(diǎn)中包含指針域，其中next指向它的，prｉｏr指向它的,而頭結(jié)點(diǎn)的pｒｉor指向,尾結(jié)點(diǎn)的nexｔ指向。19.單向循環(huán)鏈表是單向鏈表的一種擴(kuò)充,當(dāng)單向鏈表帶有頭結(jié)點(diǎn)時(shí)，把單向鏈表中尾結(jié)點(diǎn)的指針域由空指針改為;當(dāng)單向鏈表不帶頭結(jié)點(diǎn)時(shí)，則把單向鏈表中尾結(jié)點(diǎn)的指針域由空指針改為指向。20．線性鏈表的邏輯關(guān)系時(shí)通過每個(gè)結(jié)點(diǎn)指針域中的指針來表達(dá)的。其邏輯順序和物理存儲(chǔ)順序不再一致，而是一種存儲(chǔ)結(jié)構(gòu)，又稱為。三、問答題１.簡(jiǎn)述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)的區(qū)別與聯(lián)系，它們?nèi)绾斡绊懰惴ǖ脑O(shè)計(jì)與實(shí)現(xiàn)？2．解釋順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn),并比較順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺陷。３.什么情況下用順序表比鏈表好？4．頭指針、頭結(jié)點(diǎn)、第一個(gè)結(jié)點(diǎn)(或稱首元結(jié)點(diǎn))的區(qū)別是什么？5.解釋帶頭結(jié)點(diǎn)的單鏈表和不帶頭結(jié)點(diǎn)的單鏈表的區(qū)別。四、程序填空題１.下列是用尾插法建立帶頭結(jié)點(diǎn)的且有ｎ個(gè)結(jié)點(diǎn)的單向鏈表的算法,請(qǐng)?jiān)诳崭駜?nèi)填上適當(dāng)?shù)恼Z句。NOＤE*creatｅ1(n）/*對(duì)線性表(１，2,．...．,n),建立帶頭結(jié)點(diǎn)的單向鏈表*／{ＮＯDE*hｅad,*p，*q;inti;p=(NODE*)maｌloc（siｚeｏｆ（NOＤE));hｅad=p；ｑ＝p；p->neｘｔ=ＮＵLL;for(ｉ=1;ｉ<=n;i++）{p=(NOＤE＊）malloｃ(sｉzｅof（NODE));(1）;?（2)； （３）;?(4）；｝ｒeｔuｒn（ｈead）;｝２．下列是用頭插法建立帶頭結(jié)點(diǎn)的且有ｎ個(gè)結(jié)點(diǎn)的單向鏈表的算法，請(qǐng)?jiān)诳崭駜?nèi)填上適當(dāng)?shù)恼Z句。ＮODE*ｃｒeａt(yī)e2（ｎ)/*對(duì)線性表(ｎ,n－１,.．.．.,１),建立帶頭結(jié)點(diǎn)的線性鏈表*/{ＮODE*head,*ｐ,*q；inti；p=(NＯDＥ*)mａlloc(sｉｚeoｆ(ＮODE));(1）;p－>next＝NULL;（2）;for(ｉ＝１;i<=ｎ;i＋+)｛ｐ=(ＮODE*)ｍaｌloc(ｓizeof(NODＥ)）;ｐ->datａ＝i;?iｆ(i==1）?(３）；??else(4）；(5);}rｅturn(head)；｝3.下列是在具有頭結(jié)點(diǎn)單向列表中刪除第i個(gè)結(jié)點(diǎn)，請(qǐng)?jiān)诳崭駜?nèi)填上適當(dāng)?shù)恼Z句。inｔｄeｌete(ＮODE*ｈead,inti){NODE*p,*q；ｉｎtj;q=heａd；j=0；while((ｑ!=NULL)&&(j＜i－1))/*找到要?jiǎng)h除結(jié)點(diǎn)的直接前驅(qū)，并使q指向它*／{q＝q->next;j++;｝ｉf（ｑ==NＵＬL)return(0);（１）;（２）;frｅe(cuò)(p);return（1);}五、完畢:實(shí)驗(yàn)1――線性表根據(jù)實(shí)驗(yàn)規(guī)定(見教材P201－２02)認(rèn)真完畢本實(shí)驗(yàn)，并提交實(shí)驗(yàn)報(bào)告。數(shù)據(jù)結(jié)構(gòu)(本）課程作業(yè)2(本部分作業(yè)覆蓋教材第3－５章的內(nèi)容)一、單項(xiàng)選擇題1.若讓元素1,2,3依次進(jìn)棧,則出棧順序不也許為()。A．3,2，１B．２，1,3C.3，1,2D．1,3，2２．一個(gè)隊(duì)列的入隊(duì)序列是1,2，3,4。則隊(duì)列的輸出序列是()。A．4,3,2，1B.1,2,3，４C.1，4，3，2Ｄ.3，２,4,13.向順序棧中壓入新元素時(shí)，應(yīng)當(dāng)(）。A．先移動(dòng)棧頂指針,再存入元素B.先存入元素，再移動(dòng)棧頂指針C．先后順序無關(guān)緊要D．同時(shí)進(jìn)行4.在一個(gè)棧頂指針為top的鏈棧中,將一個(gè)p指針?biāo)傅慕Y(jié)點(diǎn)入棧,應(yīng)執(zhí)行（）。Ａ．top->nｅxt=p;B．p->next=top-＞nｅxt;tｏp-＞nｅxt＝p;C．p-＞nｅｘt＝ｔop；top=p;Ｄ．ｐ->nｅxt=tｏｐ->next;top=ｔoｐ－>nｅｘt；5.在一個(gè)棧頂指針為ｔop的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí),用ｘ保存被刪結(jié)點(diǎn)的值,則執(zhí)行（)。A.x=ｔop;top=tｏp->next;Ｂ．x＝tｏｐ-＞ｄata;C.tｏp=ｔoｐ->next;ｘ=ｔop->dａt(yī)a;D．x＝top->dａt(yī)ａ;ｔop=toｐ－>ｎeｘt；6．一般情況下，將遞歸算法轉(zhuǎn)換成等價(jià)的非遞歸算法應(yīng)當(dāng)設(shè)立（）。A.棧Ｂ．隊(duì)列C.堆?；蜿?duì)列Ｄ．?dāng)?shù)組7.表達(dá)式ａ＊（ｂ+c)-d的后綴表達(dá)式是()。A．ａｂcd*+-Ｂ．ａbc+*ｄ-C．a(chǎn)ｂc*++d-D.-+＊aｂcd８.判斷一個(gè)順序隊(duì)列ｓq（最多元素為m0)為空的條件是(）。Ａ．sq-＞ｒear－sｑ-＞fronｔ==m0B．ｓｑ－>ｒeａr-sq->froｎｔ-１==m０C．sq-＞fｒont==sq->reａrD．sｑ->ｆｒｏｎt＝＝sq->ｒear+１9．判斷一個(gè)循環(huán)隊(duì)列Q(最多元素為m0）為空的條件是（)。A．Q->front=＝Ｑ->ｒearB.Ｑ->front!=Q－＞reａrC．Q->ｆront=＝（Ｑ->ｒｅar＋1)%m０D.Q-＞fｒoｎｔ!=(Q->rｅar+１)%m０1０.判斷一個(gè)循環(huán)隊(duì)列Q(最多元素為ｍ0)為空的條件是（）。A．Q->fronｔ==Q－>reaｒB．Q-＞front!=Q->reａrC.Q->frｏnｔ=＝(Q－>rｅaｒ+１）%m０D．Q->fｒont!=(Q->reａｒ+1)%ｍ０1１．判斷棧Ｓ滿（元素個(gè)數(shù)最多ｎ個(gè))的條件是（)。A．s->top==0B.s->ｔｏp!=0C．s->top＝＝ｎ-1D.s-＞ｔop!＝n－112．一個(gè)隊(duì)列的入隊(duì)順序是a,b,ｃ,ｄ，則離隊(duì)的順序是()。A．a(chǎn),d,cbＢ．ａ，b,ｃ,dC．d，c,ｂ,ａD．ｃ,b,d，ａ1３.假如以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則退棧操作時(shí)(）。A.必須判斷棧是否滿B.判斷棧元素類型C.必須判斷棧是否空D.對(duì)棧不作任何判斷14．在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時(shí)通常設(shè)立一個(gè)打印數(shù)據(jù)緩沖區(qū),主機(jī)將要輸出的數(shù)據(jù)依次寫入緩沖區(qū)中，而打印機(jī)則從緩沖區(qū)中取出數(shù)據(jù)打印，該緩沖區(qū)應(yīng)當(dāng)是一個(gè)（）結(jié)構(gòu)。Ａ．堆棧Ｂ．隊(duì)列C.數(shù)組Ｄ．先性表15．一個(gè)遞歸算法必須涉及(）。A．遞歸部分? B.終止條件和遞歸部分 Ｃ.迭代部分?D.終止條件和迭代部分1６．從一個(gè)棧頂指針為ｔoｐ的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí),用變量x保存被刪結(jié)點(diǎn)的值,則執(zhí)行(）。Ａ.x=ｔop-＞data;top=toｐ->nｅxt;B.ｘ＝top->daｔa；C．top=tｏp->next;ｘ=top->datａ；D.top=ｔop->nｅxt；x=data;17．在一個(gè)鏈隊(duì)中,假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針,則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算為（）。A．r=f－>nｅxt；Ｂ．r=ｒ->ｎexｔ；Ｃ.f=f->ｎext；D．f=r->nｅxｔ;18．在一個(gè)鏈隊(duì)中,假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的運(yùn)算為（）。A．f-＞next=s；f=s;Ｂ．r-＞neｘt=s;r=s;C.s->ｎext=r；ｒ=s；D．s->next=f;f=s;19.以下陳述中對(duì)的的是(）。A.串是一種特殊的線性表B．串的長(zhǎng)度必須大于零Ｃ.串中元素只能是字母D.空串就是空白串２0．設(shè)有兩個(gè)串p和q,其中q是p的子串,q在p中初次出現(xiàn)的位置的算法稱為（)。Ａ．求子串B.連接Ｃ.匹配D.求串長(zhǎng)２1.串是（)。A．不少于一個(gè)字母的序列B．任意個(gè)字母的序列C.不少于一個(gè)字符的序列D.有限個(gè)字符的序列22.串的長(zhǎng)度是指（)。A.串中所含不同字母的個(gè)數(shù)B．串中所含字符的個(gè)數(shù)C．串中所含不同字符的個(gè)數(shù)D．串中所含非空格字符的個(gè)數(shù)23.若串S==“Eｎglish”,其子串的個(gè)數(shù)是()。A．9B．1６Ｃ24.下面關(guān)于串的敘述中，不對(duì)的的是（）。Ａ．串是字符的有限序列B.空串是由空格構(gòu)成的串Ｃ.模式匹配是串的一種重要運(yùn)算D．串即可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)２5.串與普通的線性表相比較，它的特殊性體現(xiàn)在(）。Ａ．順序的存儲(chǔ)結(jié)構(gòu)B．鏈接的存儲(chǔ)結(jié)構(gòu)Ｃ.數(shù)據(jù)元素是一個(gè)字符D.數(shù)據(jù)元素可以任意26．空串與空格串()。Ａ.相同Ｂ.不相同C．也許相同D.無法擬定２7．兩個(gè)字符串相等的條件是()。A.兩串的長(zhǎng)度相等B.兩串包含的字符相同Ｃ.兩串的長(zhǎng)度相等，并且兩串包含的字符相同Ｄ.兩串的長(zhǎng)度相等，并且相應(yīng)位置上的字符相同28.在實(shí)際應(yīng)用中,要輸入多個(gè)字符串,且長(zhǎng)度無法預(yù)定。則應(yīng)當(dāng)采用()存儲(chǔ)比較合適(）。Ａ．鏈?zhǔn)剑拢樞颍?堆結(jié)構(gòu)D.無法擬定２9.一維數(shù)組A采用順序存儲(chǔ)結(jié)構(gòu),每個(gè)元素占用6個(gè)字節(jié),第６個(gè)元素的存儲(chǔ)地址為100,則該數(shù)組的首地址是（)。A．64B.28C.7０Ｄ.90３0.稀疏矩陣采用壓縮存儲(chǔ)的目的重要是(）。A.表達(dá)變得簡(jiǎn)樸B．對(duì)矩陣元素的存取變得簡(jiǎn)樸C．去掉矩陣中的多余元素D.減少不必要的存儲(chǔ)空間的開銷３1.一個(gè)非空廣義表的表頭（）。A.不也許是原子B.只能是子表Ｃ.只能是原子D.可以是子表或原子32．常對(duì)數(shù)組進(jìn)行的兩種基本操作是(）。Ａ.建立與刪除Ｂ．索引與、和修改C.查找和修改D．查找與索引33．設(shè)二維數(shù)組A[5][6]按行優(yōu)先順序存儲(chǔ)在內(nèi)存中,已知A［0][0]起始地址為100０，每個(gè)數(shù)組元素占用5個(gè)存儲(chǔ)單元,則元素A[４][4]的地址為（)。Ａ.1140B．１１45C.1120D.112534.設(shè)有一個(gè)20階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開始),則矩陣中元素a９,2在一維數(shù)組B中的下標(biāo)是（)。A.41B．32C35．一個(gè)非空廣義表的表頭(）。A．不也許是子表B．只能是子表Ｃ.只能是原子Ｄ.可以是子表或原子二、填空題1．棧是限定在表的一端進(jìn)行插入和刪除操作的線性表，又稱為。2.隊(duì)列的特性是。3．往棧中插入元素的操作方式是:先，后。４.刪除棧中元素的操作方式是:先,后。5.循環(huán)隊(duì)列隊(duì)頭指針在隊(duì)尾指針位置,隊(duì)列是“滿”狀態(tài)６.在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，當(dāng)插入一個(gè)新的隊(duì)列元素時(shí),尾指針，當(dāng)刪除一個(gè)元素隊(duì)列時(shí)，頭指針。7.循環(huán)隊(duì)列的引入,目的是為了克服。8.向順序棧插入新元素分為三步：第一步進(jìn)行判斷，判斷條件是；第二步是修改；第三步是把新元素賦給。同樣從順序棧刪除元素分為三步：第一步進(jìn)行判斷，判斷條件是。第二步是把；第三步。９．假設(shè)以S和X分別表達(dá)入棧和出棧操作，則對(duì)輸入序列a，b，ｃ,d,e一系列棧操作SSXSXSSXXＸ之后，得到的輸出序列為。10.一個(gè)遞歸算法必須涉及和。11．判斷一個(gè)循環(huán)隊(duì)列ＬU（最多元素為m0)為空的條件是。１2.在將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式和計(jì)算后綴表達(dá)式的算法中,都需要使用棧,對(duì)于前者,進(jìn)入棧中的元素為表達(dá)式中的,而對(duì)于后者,進(jìn)入棧的元素為，中綴表達(dá)式(a＋b)/c-（f-d/ｃ)所相應(yīng)的后綴表達(dá)式是。1６．向一個(gè)棧頂指針為h的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí),可執(zhí)行____＿_(dá)__和h=s;操作。(結(jié)點(diǎn)的指針域?yàn)閚ext）１7.從一個(gè)棧頂指針為h的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí),用x保存被刪結(jié)點(diǎn)的值，可執(zhí)行x=h－>dａt(yī)a;和＿＿_(dá)＿_(dá)_＿＿。（結(jié)點(diǎn)的指針域?yàn)閚ｅｘt）１8．在一個(gè)鏈隊(duì)中，設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的操作為_＿_(dá)_____和r=s；（結(jié)點(diǎn)的指針域?yàn)閚ext）19．在一個(gè)鏈隊(duì)中，設(shè)ｆ和r分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的操作為________。(結(jié)點(diǎn)的指針域?yàn)閚ｅｘt)２０．串是一種特殊的線性表，其特殊性表現(xiàn)在組成串的數(shù)據(jù)元素都是。21．串的兩種最基本的存儲(chǔ)方式是和。22.空串的長(zhǎng)度是;空格串的長(zhǎng)度是。23．需要壓縮存儲(chǔ)的矩陣可分為矩陣和矩陣兩種。2４．設(shè)廣義表Ｌ=((），()）,則表頭是,表尾是，L的長(zhǎng)度是。2５.廣義表Ａ(（a,b,c)，(d，e,f））的表尾為。26．兩個(gè)串相等的充足必要條件是___＿_(dá)__＿_(dá)_。27．設(shè)有n階對(duì)稱矩陣Ａ,用數(shù)組s進(jìn)行壓縮存儲(chǔ),當(dāng)iｊ時(shí)，A的數(shù)組元素aｉj相應(yīng)于數(shù)組s的數(shù)組元素的下標(biāo)為____＿＿＿。(數(shù)組元素的下標(biāo)從1開始）2８.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，矩陣中每個(gè)非零元素相應(yīng)的三元組涉及該元素的＿_(dá)＿＿_(dá)＿_(dá)、_____＿_(dá)和_＿_(dá)＿＿_(dá)_三項(xiàng)信息。三、問答題1．簡(jiǎn)述棧和一般線性表的區(qū)別。2．簡(jiǎn)述隊(duì)列和一般線性表的區(qū)別。3．鏈棧中為什么不設(shè)頭結(jié)點(diǎn)？4．運(yùn)用一個(gè)棧，則:（1）假如輸入序列由A，B，C組成，試給出所有也許的輸出序列和不也許的輸出序列。（2）假如輸入序列由A,B，C，D組成,試給出所有也許的輸出序列和不也許的輸出序列。5．用S表達(dá)入棧操作，X表達(dá)出棧操作，若元素入棧順序?yàn)?2３４，為了得到1342出棧順序，相應(yīng)的Ｓ和X操作串是什么?６．有5個(gè)元素,其入棧順序?yàn)?A、B、C、D、E,在各種也許的出棧順序中，以元素C、D最先的順序有哪幾個(gè)?7．寫出以下運(yùn)算式的后綴算術(shù)運(yùn)算式⑴３x2+ｘ－1/x+５⑵(Ａ+Ｂ)*C-D／(E+F)＋G８.在什么情況下可以用遞歸解決問題？在寫遞歸程序時(shí)應(yīng)注意什么？9．簡(jiǎn)述廣義表和線性表的區(qū)別和聯(lián)系。四、程序填空題1．在下面空格處填寫適當(dāng)?shù)恼Z句,以使下面的循環(huán)隊(duì)列的入隊(duì)和出隊(duì)算法完整。ｄefineＴRUE1;defiｎｅFALSE0;defｉneMAＸＳIＺＥ100;tyｐedeｆcharｅlｅｍtｙpe；ｔypedefstrucｔ{Elemtypeｑｕeue［ＭAXSＩＺＥ］；intfront,rｅａr;}sequeｕｅtype;SｅqｕeueｔypeQ;intencqueｕｅ(sequｅuetype*Q,eｌemtypex）ｉｆ(（1)）Prinｔf(〝Thecicularqueueisfｕll!\n〞)；returｎ(FALSＥ）;eｌｓｅ(２）(３)return（TRUE);｝/*encqｕｅue*/ｅlemtｙpedel_cｑuｅue(sequeuetype＊Ｑ)ｉｆ((4))Printf(〝Theqｕeueisemｐtｙ?。躰〞）reｔurn（NUＬL);else(5)Reｔｕｒn（Q－queuｅ[Ｑ->ｆrｏｎt］);/*deｌ＿cqueuｅ*/２.在下面空格處填寫適當(dāng)?shù)恼Z句，以使下面的鏈?zhǔn)疥?duì)列取出元素的算法完整。ｉntwrite(LｉnｋQｕeue*q）{QｕeueＮode*p；if(ｑ->ｆｒont=＝ｑ->ｒeaｒ）/*隊(duì)空*/{ｐriｎtｆ(“undｅrflｏw”);exit(0);}while(q->fronｔ->nｅxt！=NULL){p=q-＞ｆrｏnt->nｅxt；（1）pｒiｎtf（“%4d”，ｐ->data）；(2)｝（3）；／*隊(duì)空時(shí)，頭尾指針指向頭結(jié)點(diǎn)*/｝五、綜合題１.設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1,e２,e3，e４,e5和e6依次通過S，一個(gè)元素出棧后即進(jìn)隊(duì)列Q，若6個(gè)元素出隊(duì)的序列是ｅ２,e4,e3，e6,e5,ｅ1，則棧S的容量至少應(yīng)當(dāng)是多少？2．假設(shè)用循環(huán)單鏈表實(shí)現(xiàn)循環(huán)隊(duì)列,該隊(duì)列只使用一個(gè)尾指針rｅar,其相應(yīng)的存儲(chǔ)結(jié)構(gòu)和基本算法如下；（1)初始化隊(duì)列ｉnitqueue（Q）：建立一個(gè)新的空隊(duì)列Ｑ。(2）入隊(duì)列eｎqｕeｕe（Q,x):將元素ｘ插入到隊(duì)列Q中。(３）出隊(duì)列ｄｅｌqueue(Q）：從隊(duì)列Ｑ中退出一個(gè)元素。(４）取隊(duì)首元素geｔheaｄ(Q):返回當(dāng)前隊(duì)首元素。(5)判斷隊(duì)列是否為空:ｅmｐtyqｕｅue（Q)。（6)顯示隊(duì)列中元素：dispqｕｅue(Q)。六、完畢:實(shí)驗(yàn)２――棧、隊(duì)列、遞歸程序設(shè)計(jì)根據(jù)實(shí)驗(yàn)規(guī)定(見教材P20３)認(rèn)真完畢本實(shí)驗(yàn),并提交實(shí)驗(yàn)報(bào)告。數(shù)據(jù)結(jié)構(gòu)(本)課程作業(yè)作業(yè)3(本部分作業(yè)覆蓋教材第６－7章的內(nèi)容)一、單項(xiàng)選擇題1.假定一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為1５，單分支結(jié)點(diǎn)數(shù)為３0,則葉子結(jié)點(diǎn)數(shù)為（)。A．15Ｂ．1６C2．二叉樹第k層上最多有()個(gè)結(jié)點(diǎn)。A.2ｋB．2k-１C.２ｋ-1D．2ｋ-13．二叉樹的深度為k,則二叉樹最多有()個(gè)結(jié)點(diǎn)。A．2kB.2k－1C.2k-1Ｄ.2k-14.設(shè)某一二叉樹先序遍歷為abdec,中序遍歷為dbeac,則該二叉樹后序遍歷的順序是()。A.abdｅcB.debａｃC．debｃａD．a(chǎn)bedｃ５.樹最適合于用來表達(dá)（)。A．線性結(jié)構(gòu)的數(shù)據(jù)B．順序結(jié)構(gòu)的數(shù)據(jù)C．元素之間無前驅(qū)和后繼關(guān)系的數(shù)據(jù)D．元素之間有包含和層次關(guān)系的數(shù)據(jù)6．設(shè)a,b為一棵二叉樹的兩個(gè)結(jié)點(diǎn),在后續(xù)遍歷中，ａ在b前的條件是()。A.a在ｂ上方Ｂ．ａ在b下方C.a在b左方D．a(chǎn)在b右方7．權(quán)值為{１,2，6,8}的四個(gè)結(jié)點(diǎn)構(gòu)成的哈夫曼樹的帶權(quán)途徑長(zhǎng)度是（)。A．１8Ｂ.28C．１9Ｄ.298．將具有150個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始,每一層從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)為6９的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為（)。A.33Ｂ．3４Ｃ.３5D.３６9.假如將給定的一組數(shù)據(jù)作為葉子數(shù)值,所構(gòu)造出的二叉樹的帶權(quán)途徑長(zhǎng)度最小，則該樹稱為（)。A.哈夫曼樹B．平衡二叉樹C．二叉樹Ｄ．完全二叉樹1０.下列有關(guān)二叉樹的說法對(duì)的的是（)。A.二叉樹中度為0的結(jié)點(diǎn)的個(gè)數(shù)等于度為2的結(jié)點(diǎn)的個(gè)數(shù)加１Ｂ.二叉樹中結(jié)點(diǎn)個(gè)數(shù)必大于０C．完全二叉樹中，任何一個(gè)結(jié)點(diǎn)的度,或者為0或者為2D．二叉樹的度是2１1.在一棵度為３的樹中，度為3的結(jié)點(diǎn)個(gè)數(shù)為２，度為2的結(jié)點(diǎn)個(gè)數(shù)為１,則度為0的結(jié)點(diǎn)個(gè)數(shù)為（）。A．4B．5C．６D.７12．在一棵度具有5層的滿二叉樹中結(jié)點(diǎn)總數(shù)為()。Ａ．３１B．32Ｃ.33D.16１3．運(yùn)用n個(gè)值作為葉結(jié)點(diǎn)的權(quán)生成的哈夫曼樹中共包具有(）個(gè)結(jié)點(diǎn)。Ａ.nB.n+１C．2＊nＤ.2*ｎ-114.運(yùn)用n個(gè)值作為葉結(jié)點(diǎn)的權(quán)生成的哈夫曼樹中共包具有（)個(gè)雙支結(jié)點(diǎn)。A.nB.n-1Ｃ．n+1D．2１5.運(yùn)用3、６、8、12這四個(gè)值作為葉子結(jié)點(diǎn)的權(quán),生成一棵哈夫曼樹，該樹中所有葉子的最長(zhǎng)帶權(quán)途徑長(zhǎng)度為()。Ａ．18B.16C.12Ｄ．316．在一棵樹中,()沒有前驅(qū)結(jié)點(diǎn)。A.分支結(jié)點(diǎn)B．葉結(jié)點(diǎn)C．樹根結(jié)點(diǎn)D.空結(jié)點(diǎn)17．在一棵二叉樹中，若編號(hào)為i的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號(hào)為()。A.2iＢ．2i-1D．2ｉ＋118．設(shè)一棵哈夫曼樹共有n個(gè)葉結(jié)點(diǎn)，則該樹有（）個(gè)非葉結(jié)點(diǎn)。Ａ.nＢ.ｎ-1C．n＋11９.設(shè)一棵有n個(gè)葉結(jié)點(diǎn)的二叉樹，除葉結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)度數(shù)都為2，則該樹共有(）個(gè)結(jié)點(diǎn)。A．2nB．２ｎ－1C.２ｎ+1Ｄ．2ｎ+2２0.一棵完全二叉樹共有5層，且第5層上有六個(gè)結(jié)點(diǎn),該樹共有（）個(gè)結(jié)點(diǎn)。A.20B.２1C.23Ｄ21.在一個(gè)圖G中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)之和的(）倍。A.1／2B.1C．2Ｄ.422．在一個(gè)有像圖中,所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的(）倍。A.鄰接矩陣表達(dá)法Ｂ．鄰接表表達(dá)法C．逆鄰接表表達(dá)法D.鄰接表和逆鄰接表2３．在圖的存儲(chǔ)結(jié)構(gòu)表達(dá)中,表達(dá)形式唯一的是()。A.nB．n１Ｃ．ｎ1D.n／224.一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖包含（）條邊。A.n（n1）B．n（ｎ1）C.n(n1）／2D.n（n1)／２25．一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖包含（）條邊。A．ｎ（n1）Ｂ.n(n1）C．ｎ（ｎ1）/2D．n(ｎ1)/2２６.對(duì)于具有n個(gè)頂點(diǎn)的圖，若采用鄰接矩陣表達(dá)，則該矩陣的大小為(）。Ａ．ｎＢ.n2C.n1D．(n1)27．對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和ｅ條邊的無向圖,若采用鄰接表表達(dá)，則表頭向量的大小為（)。A．nＢ.ｅC.2nD.2ｅ28．對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，若采用鄰接表表達(dá)，則所有頂點(diǎn)鄰接表中的結(jié)點(diǎn)總數(shù)為()。A．ｎB.ｅC.2nD.２e２９.在有向圖的鄰接表中,每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有（）鄰接點(diǎn)。Ａ．入邊B．出邊C．入邊和出邊D.不是入邊也不是出邊3０.在有向圖的逆鄰接表中,每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有()鄰接點(diǎn)。A.入邊B.出邊C．入邊和出邊D．不是入邊也不是出邊31．鄰接表是圖的一種()。A.順序存儲(chǔ)結(jié)構(gòu)B．鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C.索引存儲(chǔ)結(jié)構(gòu)D．散列存儲(chǔ)結(jié)構(gòu)32．假如從無向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問所有頂點(diǎn),則該圖一定是（）。A.完全圖B．連通圖Ｃ．有回路Ｄ．一棵樹33．下列有關(guān)圖遍歷的說法不對(duì)的的是（）。A.連通圖的深度優(yōu)先搜索是一個(gè)遞歸過程B.圖的廣度優(yōu)先搜索中鄰接點(diǎn)的尋找具有“先進(jìn)先出”的特性C.非連通圖不能用深度優(yōu)先搜索法Ｄ．圖的遍歷規(guī)定每一頂點(diǎn)僅被訪問一次34.無向圖的鄰接矩陣是一個(gè)()。?A.對(duì)稱矩陣B．零矩陣C.上三角矩陣D.對(duì)角矩陣3５．圖的深度優(yōu)先遍歷算法類似于二叉樹的（)遍歷。Ａ．先序B.中序C.后序D.層次３6.已知下圖所示的一個(gè)圖,若從頂點(diǎn)V1出發(fā),按深度優(yōu)先搜索法進(jìn)行遍歷,則也許得到的一種頂點(diǎn)序列為()。A.Ｖ1V2V4Ｖ8V3Ｖ５V6V7B.V1V２V4V５V8V3V6V7Ｃ．V1V2V4Ｖ８V5Ｖ3Ｖ6V7D.V1V3Ｖ6V7V2Ｖ4Ｖ5V8V6V6V7V1V2V3V8V4V5二、填空題1．結(jié)點(diǎn)的度是指結(jié)點(diǎn)所擁有的。2．樹的度是指。3.度大于０的結(jié)點(diǎn)稱作或。4.度等于0的結(jié)點(diǎn)稱作或。5.在一棵樹中,每個(gè)結(jié)點(diǎn)的或者說每個(gè)結(jié)點(diǎn)的稱為該結(jié)點(diǎn)的,簡(jiǎn)稱為孩子。６.一個(gè)結(jié)點(diǎn)稱為其后繼結(jié)點(diǎn)的。7.具有的結(jié)點(diǎn)互稱為兄弟結(jié)點(diǎn)，簡(jiǎn)稱為兄弟。８．每個(gè)結(jié)點(diǎn)的所有子樹中的結(jié)點(diǎn)被稱為該結(jié)點(diǎn)的。9.從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)稱為該結(jié)點(diǎn)的。10.樹的深度或高度是指。11.m(ｍ0)棵互不相交的樹的集合稱為。12．度為k的樹中的第i層上最多有結(jié)點(diǎn)。１3．深度為k的二叉樹最多有結(jié)點(diǎn)。14.在一棵二叉樹中,假如樹中的每一層都是滿的,則稱此樹為;但假如出最后一層外,其余層都是滿的,并且最后一層是滿的，或者是在缺少若干連續(xù)個(gè)結(jié)點(diǎn),則稱此二叉樹為。１5.具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度是。16.先序遍歷二叉樹的的操作定義為；若二叉樹為空，則為空操作,否則進(jìn)行如下操作，訪問二叉樹的;先序遍歷二叉樹的，先序遍歷二叉樹的。17．中序遍歷二叉樹的的操作定義為；若二叉樹為空,則為空操作，否則進(jìn)行如下操作，中序遍歷二叉樹的;訪問而叉樹的,中序遍歷二叉樹的。1８.后序遍歷二叉樹的的操作定義為;若二叉樹為空，則為空操作,否則進(jìn)行如下操作,后序遍歷二叉樹的;后序遍歷二叉樹的，訪問而叉樹的。１9.將樹中結(jié)點(diǎn)賦上一個(gè)有著某種意義的實(shí)數(shù)，稱此實(shí)數(shù)為該結(jié)點(diǎn)的。２0.樹的帶權(quán)途徑長(zhǎng)度為樹中所有葉子結(jié)點(diǎn)的。21．哈夫曼樹又稱為,它是n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹中帶權(quán)途徑長(zhǎng)度WPL。22．若以４，5，６，7,８作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造哈夫曼樹，則其帶權(quán)途徑長(zhǎng)度是。23．具有m個(gè)葉子結(jié)點(diǎn)的哈夫曼樹共有結(jié)點(diǎn)。2４．在圖中,任何兩個(gè)數(shù)據(jù)元素之間都也許存在關(guān)系,因此圖的數(shù)據(jù)元素之間是一種的關(guān)系。25．圖的鄰接矩陣表達(dá)法是用一個(gè)來表達(dá)圖中頂點(diǎn)之間的相鄰關(guān)系。２6．鄰接表是圖中的每個(gè)頂點(diǎn)建立一個(gè)鄰接關(guān)系的。27．圖的遍歷是從圖的某一頂點(diǎn)出發(fā),按照一定的搜索方法對(duì)圖中各做訪問的過程。28．圖的深度優(yōu)先搜索遍歷類似于樹的遍歷。２9.圖的廣度優(yōu)先搜索類似于樹的遍歷。３0．具有n個(gè)頂點(diǎn)的有向圖的鄰接矩陣，其元素個(gè)數(shù)為。30.具有n個(gè)頂點(diǎn)的無向圖至少有條邊,才干保證其為一個(gè)連通圖。31.圖常用的兩種存儲(chǔ)結(jié)構(gòu)是和。32.一個(gè)AOＶ網(wǎng)(頂點(diǎn)活動(dòng)圖)應(yīng)當(dāng)是一個(gè)。即不應(yīng)當(dāng)帶有回路,否則回路上的所有活動(dòng)都。３3．用鄰接矩陣存儲(chǔ)有向圖G，其第ｉ行的所有元素之和等于頂點(diǎn)i的。34.在有n個(gè)頂點(diǎn)的有向圖中,每個(gè)頂點(diǎn)的度最大可達(dá)。35.在一個(gè)帶權(quán)圖中,兩頂點(diǎn)之間的最段途徑最多通過條邊。36．為了實(shí)現(xiàn)圖的深度優(yōu)先搜索遍歷,其非遞歸的算法中需要使用的一個(gè)輔助數(shù)據(jù)結(jié)構(gòu)為。三、綜合題1．寫出如下圖所示的二叉樹的先序、中序和后序遍歷序列。aajfghidceb2．已知某二叉樹的先序遍歷結(jié)果是：A,B，D，G，C，E,H，L，Ｉ,Ｋ，M,Ｆ和Ｊ,它的中序遍歷結(jié)果是:G,D,B,Ａ,Ｌ，H，Ｅ,K,I，Ｍ，C，F(xiàn)和J,請(qǐng)畫出這棵二叉樹,并寫出該二叉樹后續(xù)遍歷的結(jié)果。3．已知一棵完全二叉樹共有８９２個(gè)結(jié)點(diǎn)，求⑴樹的高度⑵葉子結(jié)點(diǎn)數(shù)⑶單支結(jié)點(diǎn)數(shù)⑷最后一個(gè)非終端結(jié)點(diǎn)的序號(hào)4.給出滿足下列條件的所有二叉樹。(1）先序和中序相同(2)中序和后序相同（3）先序和后序相同5．假設(shè)通信用的報(bào)文由９個(gè)字母A、B、C、D、Ｅ、Ｆ、Ｇ、H和I組成,它們出現(xiàn)的頻率分別是:１0、2０、5、15、8、2、3、７和30。請(qǐng)請(qǐng)用這９個(gè)字母出現(xiàn)的頻率作為權(quán)值求：（1）設(shè)計(jì)一棵哈夫曼樹；(2)計(jì)算其帶權(quán)途徑長(zhǎng)度WPＬ;（3）寫出每個(gè)字符的哈夫曼編碼。６.請(qǐng)根據(jù)以下帶權(quán)有向圖G（1）給出從結(jié)點(diǎn)v1出發(fā)分別按深度優(yōu)先搜索遍歷G和廣度優(yōu)先搜索遍歷G所得的結(jié)點(diǎn)序列；（2)給出G的一個(gè)拓?fù)湫蛄?（3）給出從結(jié)點(diǎn)ｖ1到結(jié)點(diǎn)v8的最短途徑。7.已知無向圖Ｇ描述如下：G=(V,E）V={V1,Ｖ2,V3,V4，Ｖ5}E={(Ｖ１,V２），（Ｖ1,V4)，(Ｖ2，Ｖ4)，(Ｖ3,Ｖ4）,(V2,V5）,(V3,V4），（V3,V5)}（1)畫出Ｇ的圖示；(2）然后給出Ｇ的鄰接矩陣和鄰接表;(3)寫出每個(gè)頂點(diǎn)的度。8．回答下列問題：⑴對(duì)于存儲(chǔ)結(jié)構(gòu)采用鄰接矩陣的無向圖,如何判斷下列有關(guān)問題?①圖中有多少條邊？②任意兩頂點(diǎn)間是否有邊相連？③任意一個(gè)頂點(diǎn)的度是多少?⑵對(duì)于存儲(chǔ)結(jié)構(gòu)采用鄰接表的有向圖,如何判斷下列有關(guān)問題?①圖中有多少條邊?②圖中是否存在從Vi到Vj的邊？③如何求頂點(diǎn)Vi的入度和出度？四、程序填空題１.下面函數(shù)的功能是返回二叉樹BＴ中值為X的結(jié)點(diǎn)所在的層號(hào),請(qǐng)?jiān)趧澯袡M線的地方填寫合適內(nèi)容。ｉntNodeLevel(structBｉｎTreｅNodｅ*BT,chaｒＸ）{iｆ(ＢT＝=NＵＬL)retｕrn０;/*空樹的層號(hào)為0＊／elseiｆ(BT->dａt(yī)ａ==X)rｅtｕｒn1;/＊根結(jié)點(diǎn)的層號(hào)為1*//*向子樹中查找X結(jié)點(diǎn)*/elｓe{ｉｎtc1＝ＮｏdeLevｅl(BＴ-＞ｌｅｆt,X);ｉｆ(c1>＝1)_＿_(dá)(1)＿_(dá)＿_(dá)＿_(dá)_＿_(dá)__;ｉntｃ２＝______(2)＿_(dá)_＿_(dá)___＿＿;if___(3)___________＿_(dá)＿＿＿_(dá)＿;//若樹中不存在X結(jié)點(diǎn)則返回0elsｅreturｎ0;}}2.下面函數(shù)的功能是按照?qǐng)D的深度優(yōu)先搜索遍歷的方法，輸出得到該圖的生成樹中的各條邊,請(qǐng)?jiān)趧澯袡M線的地方填寫合適內(nèi)容。voiｄdfstｒee(aｄjmatrixGＡ，ｉnti,ｉｎｔｎ){intj；ｖｉsiteｄ[i]=1;(1)ｉf(GＡ［ｉ］[j]!=0&&GA［i][j]！=ＭaxValｕｅ&&！visiteｄ[j］)｛priｎtf("(％d,％d)%d,"，i,j，GA[i][j]);(２）｝｝五、算法設(shè)計(jì)題1.寫一個(gè)將一棵二叉樹復(fù)制給另一棵二叉樹的算法。2.根據(jù)下面函數(shù)聲明編寫出求一棵二叉樹中葉子結(jié)點(diǎn)總數(shù)的算法，該總數(shù)值由函數(shù)返回。假定參數(shù)ＢT初始指向二叉樹的根結(jié)點(diǎn)。intBＴreeLeafＣouｎt(ｓtructBTrｅe(cuò)Node*BT)；3.已知有n個(gè)頂點(diǎn)的有向圖鄰接表,設(shè)計(jì)算法分別實(shí)現(xiàn)下列功能：（1)求出圖Ｇ中每個(gè)頂點(diǎn)的出度、入度。（２)計(jì)算圖中度為0的頂點(diǎn)數(shù)。六、完畢:實(shí)驗(yàn)3――棧、隊(duì)列、遞歸程序設(shè)計(jì)實(shí)驗(yàn)４——圖的存儲(chǔ)方式和應(yīng)用根據(jù)實(shí)驗(yàn)規(guī)定(見教材P20３）認(rèn)真完畢本實(shí)驗(yàn),并提交實(shí)驗(yàn)報(bào)告。數(shù)據(jù)結(jié)構(gòu)（本)課程作業(yè)(４)(本部分作業(yè)覆蓋教材第8－9章的內(nèi)容)一、單項(xiàng)選擇題1.順序查找方法適合于存儲(chǔ)結(jié)構(gòu)為()的線性表。Ａ．散列存儲(chǔ)B.索引存儲(chǔ)C.散列存儲(chǔ)或索引存儲(chǔ)D.順序存儲(chǔ)或鏈接存儲(chǔ)2.對(duì)線性表進(jìn)行二分查找時(shí)，規(guī)定線性表必須（)。A．以順序存儲(chǔ)方式B．以鏈接存儲(chǔ)方式C.以順序存儲(chǔ)方式,且數(shù)據(jù)元素有序D．以鏈接存儲(chǔ)方式，且數(shù)據(jù)元素有序3．假如規(guī)定一個(gè)線性表既能較快地查找，又能動(dòng)態(tài)適應(yīng)變化規(guī)定,可以采用（）查找方法。A．順序B．分塊C．折半D.散列4．對(duì)于一個(gè)線性表,若規(guī)定既能進(jìn)行較快地插入和刪除,又規(guī)定存儲(chǔ)結(jié)構(gòu)可以反映數(shù)據(jù)元素之間的邏輯關(guān)系,則應(yīng)當(dāng)(）。A．以順序存儲(chǔ)方式B．以鏈接存儲(chǔ)方式Ｃ．以索引存儲(chǔ)方式Ｄ.以散列存儲(chǔ)方式5.采用順序查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為(）。A.ｎＢ.ｎ/2C．(n+1）/２D．(n-1)／26.采用折半查找方法查找長(zhǎng)度為n的線性表時(shí),每個(gè)元素的平均查找長(zhǎng)度為（)。A．O(ｎ*ｎ)B.Ｏ(ｎｌog２n)Ｃ．Ｏ(ｎ)D.s(loｇ２n)7.哈希函數(shù)有一個(gè)共同的性質(zhì),即函數(shù)值應(yīng)當(dāng)以（）取其值域的每個(gè)值。A.最大約率B.最小概率C．平均概率D.同等概率8．有一個(gè)長(zhǎng)度為１0的有序表，按折半查找對(duì)該表進(jìn)行查找,在等概率情況下查找成功的平均比較次數(shù)為()。A.29／１０B．３１／10C9.已知一個(gè)有序表為｛１1,22,３3,４4,55，66，7７,88，99}，則順序查找元素5５需要比較(）次。A.3Ｂ.4１0.順序查找法與二分查找法對(duì)存儲(chǔ)結(jié)構(gòu)的規(guī)定是（)。A.順序查找與二分查找均只是合用于順序表B.順序查找與二分查找均既合用于順序表,也合用于鏈表C.順序查找只是合用于順序表D．二分查找合用于順序表11．有數(shù)據(jù){53,30,37,１2，4５，24,96},從空二叉樹開始逐個(gè)插入數(shù)據(jù)來形成二叉排序樹，若希望高度最小,應(yīng)當(dāng)選擇的序列是（）。Ａ．45，24,５3,12,37,96,30B.３７,24，12,３0,53，4５,９6C.１2,２４,30,37，45，53,96D．３0，24，1２，37,45,9６,5312．對(duì)有18個(gè)元素的有序表作二分(折半）查找，則查找Ａ[3]的比較序列的下標(biāo)也許為()。A．1、2、３B.９、5、2、３C.9、5、3Ｄ．9、４、2、３１３.對(duì)于順序存儲(chǔ)的有序表{5，１2,20，２6,37，４2,4６,50,6４}，若采用折半查找,則查找元素26的比較次數(shù)是()。A．3Ｂ.3C．４D.１４．關(guān)于哈希查找的說法對(duì)的的是()。Ａ.除留余數(shù)法是最佳的B.哈希函數(shù)的好壞要根據(jù)具體情況而定C.刪除一個(gè)元素后,不管用哪種方法解決沖突,都只需簡(jiǎn)樸地把該元素刪除掉D．由于沖突是不可避免的,所以裝填因子越小越好15.在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄初始排列秩序無關(guān)的是（)。A．冒泡排序B.希爾排序C.直接選擇排序D.直接插入排序16．從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比較。將其放入已排序序列的對(duì)的的位置上，此方法稱為(）A.插入排序Ｂ．選擇排序C.互換排序Ｄ.歸并排序17．從未排序序列中挑選元素,并將其放入已排序序列的一端，此方法稱為(）。A.插入排序Ｂ.互換排序C.選擇排序D.歸并排序18.依次將每?jī)蓚€(gè)相鄰的有序表合并成一個(gè)有序表的排序方法稱為(）。 A.插入排序B.互換排序C.選擇排序D.歸并排序19.當(dāng)兩個(gè)元素出現(xiàn)逆序的時(shí)候就互換位置,這種排序方法稱為(）。Ａ.插入排序Ｂ.互換排序C．選擇排序Ｄ.歸并排序20.每次把待排序的區(qū)間劃分為左、右兩個(gè)子區(qū)間，其中左區(qū)間中記錄的關(guān)鍵字均小于等于基準(zhǔn)記錄的關(guān)鍵字,右區(qū)間中記錄的關(guān)鍵字均大于等于基準(zhǔn)記錄的關(guān)鍵字,這種排序稱為（)。Ａ．插入排序Ｂ.快速排序C.堆排序D.歸并排序21.在正常情況下，直接插入排序的時(shí)間復(fù)雜度為（)。A.O（ｌoｇ2n)B.O(n)C.O(ｎlog2ｎ)Ｄ.O(n2)22.在正常情況下,冒泡排序的時(shí)間復(fù)雜度為（)。A.Ｏ(loｇ2n）B．O(n）C.O(nｌｏg2n)Ｄ.O(n２)２3.在歸并排序中，歸并趟數(shù)的數(shù)量級(jí)為（）。A.O（ｌog２n)B.Ｏ(n)C.O(nlｏｇ2n)D.Ｏ(n2）2４.在待排序元素基本有序的情況下，效率最高的排序方法是()。A.插入排序B.快速排序Ｃ.堆排序D.歸并排序２5.下面幾種排序方法中，規(guī)定內(nèi)存量最大的是()。A.插入排序Ｂ.互換排序C.選擇排序D．歸并排序26.在下列排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列秩序無關(guān)的是()。A．希爾排序B.冒泡排序C.插入排序D.選擇排序２7.快速排序方法在(）情況下最不利于發(fā)揮其長(zhǎng)處。A.要排序的數(shù)據(jù)量太大B．要排序的數(shù)據(jù)中具有多個(gè)相同值C.要排序的數(shù)據(jù)已基本有序D.要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù)28．下述幾種排序方法中，平均情況下占用內(nèi)存量最大的是()方法。A.插入排序B.選擇排序Ｃ．快速排序Ｄ.歸并排序2９.若構(gòu)造一棵具有n個(gè)結(jié)點(diǎn)的二叉樹排序，在最壞的情況下，其深度不會(huì)超過()。A.ｎ/２B.nC.(n1）/２D.n130.對(duì)數(shù)據(jù)元素序列(49,72，68,13,38,50，97,２7)進(jìn)行排序,前三趟排序結(jié)果時(shí)的結(jié)果依次為第一趟：49，72，６8，１３,３8，50，97,２7;第二趟:49,68，72，13,38，50,97,27;第三趟:１3，49,68,72，38,５0，97,2７。該排序采用的方法是（)。A．插入排序法B.選擇排序法C.冒泡排序法D.堆積排序法31.對(duì)具有n個(gè)元素的任意序列采用插入排序法進(jìn)行排序,排序趟數(shù)為()。A．n-1B.ｎC.n+1Ｄ．loｇ2ｎ3２．對(duì)序列（49,3８,6５,９7,76,13，４７，5０)采用直接插入排序法進(jìn)行排序，要把第七個(gè)元素47插入到已排序中，為尋找插入的合適位置需要進(jìn)行(）次元素間的比較。Ａ.3B.4Ｃ.5D.33.下面四種排序方法中,()是一種穩(wěn)定性排序方法。Ａ.插入排序法B.選擇排序法C．快速排序法D．希爾排序法３４.一組記錄的關(guān)鍵字序列為（46,79，56,38，4０，８4），運(yùn)用快速排序，以第一個(gè)關(guān)鍵字為分割元素,通過一次劃分后結(jié)果為()。Ａ．40,38,46，79,56,84Ｂ．４0，３8，46，84,５6,79C．40，３８,46，５6,79,84D．38,４0，4６，5６,７9,843５．一組記錄的關(guān)鍵字序列為(４6,79,５6，38,４０，84)，運(yùn)用堆排序的方法建立的初始堆為(）。A．７9,4６,56，38，4０，84B.84,79，5６，38,40，4６C.８4,7９，56，46,40,38，Ｄ.８4,56，７９,40，4６,38３6.一組記錄的關(guān)鍵字序列為(25,48,１６,35,79，82,23,４0，36，72)，其中，具有5個(gè)長(zhǎng)度為2的有序表,按歸并排序的方法對(duì)該序列進(jìn)行一趟歸并后的結(jié)果為（）。Ａ．１6,２５，３5，4８,23，４0,79，82,36，72B.16，25,35,4８,７9，８2，２３,36,40，７2C．16,25，48,３5,79,８２,23，36，40，72D.１６，25,3５,48，7９,２3，３6,40，82,7２3７.已知10個(gè)數(shù)據(jù)元素為（５4，28，16,3４,73，6２,95，60，26,４3）,對(duì)該數(shù)列從小到到大排序,通過一趟冒泡排序后的序列為(）。A．16,２8，３4,54，73,62，60，26，43，9５B．28,1６,３4,5４，6２,73，60，2６,4３，95C．2８,1６,３４，5４，62,60,７３，26,4３,９5D．16,28，３4,54,62，60，73,2６，4３,95３8.用某種排序的方法對(duì)線性表(25,84，2１,47，15，27，6８，3５，20）進(jìn)行排序時(shí)，元素序列的變化情況如下:（1)25，84，２1,47，15，27,68,35,20（2)2０，15，21，25，4７，２7,68，3５，8４(３）１5，２0,21,25,３5,27，4７,68，84（4)15,２0,2１,25,27,35,47,6８，84其所采用的排序方法是（)。A.希爾排序B.歸并排序C.快速排序D.直接選擇排序二、填空題1．在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無關(guān)的查找方法是。2.假如對(duì)查找表只進(jìn)行查詢某個(gè)特定的數(shù)據(jù)元素是否在查找表中，以及查找