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

)對象及其關系的科學。A.數值運算

B．非數值運算C．集合

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

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

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

C．head->next＝=heaｄ

Ｄ.heａd!＝NUＬL１6．在一個單鏈表中，p、q分別指向表中兩個相鄰的結點，且ｑ所指結點是p所指結點的直接后繼,現要刪除ｑ所指結點，可用語句(

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

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