第1章習(xí)題解答一、填空1．?dāng)?shù)據(jù)是指所有能夠輸入到計(jì)算機(jī)中被計(jì)算機(jī)加工、處理的符號(hào)的集合。2．可以把計(jì)算機(jī)處理的數(shù)據(jù)，籠統(tǒng)地分成數(shù)值型和非數(shù)值型兩大類。3．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)就是指數(shù)據(jù)間的鄰接關(guān)系。4．?dāng)?shù)據(jù)是由一個(gè)個(gè)數(shù)據(jù)元素集合而成的。5．?dāng)?shù)據(jù)項(xiàng)是數(shù)據(jù)元素中不可再分割的最小標(biāo)識(shí)單位，通常不具備完整、確定的實(shí)際意義，只是反映數(shù)據(jù)元素某一方面的屬性。6．?dāng)?shù)據(jù)是以數(shù)據(jù)元素為單位存放在內(nèi)存的，分配給它的內(nèi)存區(qū)域稱為存儲(chǔ)結(jié)點(diǎn)。7．每個(gè)數(shù)據(jù)元素都具有完整、確定的實(shí)際意義，是數(shù)據(jù)加工處理的對(duì)象。8．如果兩個(gè)數(shù)據(jù)結(jié)點(diǎn)之間有著邏輯上的某種關(guān)系，那么就稱這兩個(gè)結(jié)點(diǎn)是鄰接的。9．在一個(gè)存儲(chǔ)結(jié)點(diǎn)里，除了要有數(shù)據(jù)本身的內(nèi)容外，還要有體現(xiàn)數(shù)據(jù)間鄰接關(guān)系的內(nèi)容。10．從整體上看，數(shù)據(jù)在存儲(chǔ)器內(nèi)有兩種存放的方式：一是集中存放在一個(gè)連續(xù)的內(nèi)存存儲(chǔ)區(qū)中；一是利用存儲(chǔ)器中的零星區(qū)域，分散地存放在內(nèi)存的各個(gè)地方。11．在有些書里，數(shù)據(jù)的“存儲(chǔ)結(jié)構(gòu)”也稱為數(shù)據(jù)的“物理結(jié)構(gòu)”。12．“基本操作”是指算法中那種所需時(shí)間與操作數(shù)的具體取值無關(guān)的操作。二、選擇1．在常見的數(shù)據(jù)處理中，B是最基本的處理。A．刪除B．查找C．讀取D．插入2．下面給出的名稱中，A不是數(shù)據(jù)元素的同義詞。A．字段B．結(jié)點(diǎn)C．頂點(diǎn)D．記錄3．D是圖狀關(guān)系的特例。A．只有線性關(guān)系B．只有樹型關(guān)系C．線性關(guān)系和樹型關(guān)系都不D．線性關(guān)系和樹型關(guān)系都4．鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，每個(gè)數(shù)據(jù)的存儲(chǔ)結(jié)點(diǎn)里D指向鄰接存儲(chǔ)結(jié)點(diǎn)的指針，用以反映數(shù)據(jù)間的邏輯關(guān)系。A．只能有1個(gè)B．只能有2個(gè)C．只能有3個(gè)D．可以有多個(gè)5．本書將采用C來描述算法。A．自然語言B．流程圖（即框圖）C．類C語言D．C語言6．有下面的算法段：for(i=0;i<n;i++)k++;其時(shí)間復(fù)雜度為B。A．O(1)B．O(n)C．O(log2n)D．O(n2)三、問答1．中國(guó)百家姓中的趙、錢、孫、李、周、吳、鄭、王……等姓氏數(shù)據(jù)之間，是一種什么樣的鄰接關(guān)系，為什么？答：是一種線性關(guān)系，因?yàn)檫@些姓氏之間符合關(guān)系的“有頭有尾，順序排列”的特點(diǎn)。2．什么是數(shù)據(jù)結(jié)點(diǎn)？什么是存儲(chǔ)結(jié)點(diǎn)？它們間有什么關(guān)系？答：數(shù)據(jù)結(jié)點(diǎn)即是數(shù)據(jù)集合中的一個(gè)數(shù)據(jù)元素，存儲(chǔ)結(jié)點(diǎn)是存放數(shù)據(jù)結(jié)點(diǎn)的內(nèi)存單位。在存儲(chǔ)結(jié)點(diǎn)里，不僅要存放數(shù)據(jù)結(jié)點(diǎn)的內(nèi)容，還要（顯式或隱式地）存放數(shù)據(jù)結(jié)點(diǎn)間的邏輯關(guān)系。3．為什么說鏈?zhǔn)酱鎯?chǔ)既提高了存儲(chǔ)的利用率，又降低了存儲(chǔ)的利用率？答：由于鏈?zhǔn)酱鎯?chǔ)是通過指針來體現(xiàn)數(shù)據(jù)元素之間的邏輯關(guān)系的，因此，存儲(chǔ)結(jié)點(diǎn)可以不占用存儲(chǔ)器的連續(xù)存儲(chǔ)區(qū)。從這個(gè)意義上說，鏈?zhǔn)酱鎯?chǔ)能夠充分利用存儲(chǔ)器中小的存儲(chǔ)區(qū)，因此提高了存儲(chǔ)器的利用率。另一方面，鏈?zhǔn)酱鎯?chǔ)中的存儲(chǔ)結(jié)點(diǎn)不僅要存放數(shù)據(jù)元素，還要占用適當(dāng)?shù)拇鎯?chǔ)區(qū)來存放指針，這是一種額外的存儲(chǔ)開銷。從這個(gè)意義上說，鏈?zhǔn)酱鎯?chǔ)降低了存儲(chǔ)器的利用率。4．列舉幾個(gè)數(shù)據(jù)之間具有樹型結(jié)構(gòu)的實(shí)際例子。答：學(xué)校各級(jí)管理之間，是一種分支層次結(jié)構(gòu)；一本書的書目，是一種分支層次結(jié)構(gòu)。5．判斷如下除法過程是否是一個(gè)算法，為什么：（1）開始；（2）給變量m賦初值5，給變量n賦初值0；（3）m=m/n；（4）輸出m；（5）結(jié)束。答：因?yàn)?不能為除數(shù)，本題第（3）步不具有有效性，所以它不是一個(gè)算法。但如果n的初值不為0，則是一個(gè)正確的算法。四、應(yīng)用1．用類C語言中的do-while語句，描述輸出整數(shù)1、2、3、……、9、10的過程。答：算法編寫如下。voidnum(){i=1;do{printf(“i=%d\n”,i);i=i+1;}while(i<=10);}2．用類C語言中的if-else語句，編寫算法，描述當(dāng)輸入的數(shù)據(jù)大于等于0時(shí)，輸出信息：“輸入的是正數(shù)”；當(dāng)輸入的數(shù)據(jù)小于0時(shí)，輸出信息：“輸入的是負(fù)數(shù)”。答：算法編寫如下。voidjudge(){scanf(“%d\n”,&x);if(x>=0)printf(“輸入的是正數(shù)”);elseprintf(“輸入的是負(fù)數(shù)”);}3．分析算法段中標(biāo)有記號(hào)“#1”和“#2”的基本操作的執(zhí)行次數(shù)：for(i=0;i<n;i++)for(j=0;j<n;j++){#1y=1;for(k=0;k<n;k++)#2y=y+1;}答：標(biāo)有記號(hào)“#1”的基本操作的執(zhí)行次數(shù)是：n2；標(biāo)有記號(hào)“#2”的基本操作的執(zhí)行次數(shù)是：n3。4．給出下面3個(gè)算法段的時(shí)間復(fù)雜度：（1）x++；（2）for(j=1;j<n;j++)x++;（3）for(j=1;j<=n;j++){printf(“j=%”,j);for(k=j;k<=n;k++)x++;}答：（1）的時(shí)間復(fù)雜度為O(1)；（2）的時(shí)間復(fù)雜度O(n)；（3）中“printf(“j=%”,j);”執(zhí)行次數(shù)的數(shù)量級(jí)為O(n)，“x++;”執(zhí)行次數(shù)是：n+(n-1)+(n-2)+……+2+1=n(n+1)/2其數(shù)量級(jí)為O(n2)，因此整個(gè)算法段的時(shí)間復(fù)雜度應(yīng)該是O(n2)。第2章習(xí)題解答一、填空1．當(dāng)一組數(shù)據(jù)的邏輯結(jié)構(gòu)呈線性關(guān)系時(shí)，在數(shù)據(jù)結(jié)構(gòu)里就稱其為線性表。2．線性表中數(shù)據(jù)元素的個(gè)數(shù)n稱為線性表的長(zhǎng)度。3．以順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的線性表，被稱為順序表。4．以鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)的線性表，被稱為鏈表。5．不帶表頭結(jié)點(diǎn)的鏈表，是指該鏈表的表頭指針直接指向該鏈表的起始結(jié)點(diǎn)。6．在一個(gè)雙鏈表中，已經(jīng)由指針ptr指向需要?jiǎng)h除的存儲(chǔ)結(jié)點(diǎn)，則刪除該結(jié)點(diǎn)所要執(zhí)行的兩條操作是①ptr->Prior->Next=ptr->Next;②ptr->Next->Prior=ptr->Prior;。7．設(shè)tail是指向非空、帶表頭結(jié)點(diǎn)的循環(huán)單鏈表的表尾指針。那么，該鏈表起始結(jié)點(diǎn)的存儲(chǔ)位置應(yīng)該表示成tail->Next->Next。8．在一個(gè)不帶表頭結(jié)點(diǎn)的非空單鏈表中，若要在指針qtr所指結(jié)點(diǎn)的后面插入一個(gè)值為x的結(jié)點(diǎn)，則需要執(zhí)行下列操作：ptr=malloc(size);ptr->Data=x;ptr->Next=qtr->Next;qtr->Next=ptr;9．順序表Sq=(a1，a2，a3，…，an)（n≥1）中，每個(gè)數(shù)據(jù)元素需要占用w個(gè)存儲(chǔ)單元。若m為元素a1的起始地址，那么元素an的存儲(chǔ)地址是m+(n-1)*w。10．當(dāng)線性表的數(shù)據(jù)元素個(gè)數(shù)基本穩(wěn)定、很少進(jìn)行插入和刪除操作，但卻要求以最快的速度存取表中的元素時(shí)，我們應(yīng)該對(duì)該表采用順序存儲(chǔ)結(jié)構(gòu)。二、選擇1．下面，對(duì)非空線性表特點(diǎn)的論述，C是正確的。A．所有結(jié)點(diǎn)有且只有一個(gè)直接前驅(qū)B．所有結(jié)點(diǎn)有且只有一個(gè)直接后繼C．每個(gè)結(jié)點(diǎn)至多只有一個(gè)直接前驅(qū)，至多只有一個(gè)直接后繼D．結(jié)點(diǎn)間是按照1對(duì)多的鄰接關(guān)系來維系其邏輯關(guān)系的2．一般單鏈表Lk_h為空的判定條件是A。A．Lk_h==NULLB．Lk_h->Next==NULLC．Lk_h->Next==Lk_hD．Lk_h!=NULL3．帶表頭結(jié)點(diǎn)的單鏈表Lk_h為空的判定條件是B。A．Lk_h==NULLB．Lk_h->Next==NULLC．Lk_h->Next==Lk_hD．Lk_h!=NULL4．往一個(gè)順序表的任一結(jié)點(diǎn)前插入一個(gè)新數(shù)據(jù)結(jié)點(diǎn)時(shí)，平均而言，需要移動(dòng)B個(gè)結(jié)點(diǎn)。A．nB．n/2C．n+1D．(n+1)/25．在一個(gè)單鏈表中，已知qtr所指結(jié)點(diǎn)是ptr所指結(jié)點(diǎn)的直接前驅(qū)。現(xiàn)要在qtr所指結(jié)點(diǎn)和ptr所指結(jié)點(diǎn)之間插入一個(gè)rtr所指的結(jié)點(diǎn)，要執(zhí)行的操作應(yīng)該是C。A．rtr->Next=ptr->Next;ptr->Next=rtr;B．ptr->Next=rtr->Next;C．qtr->Next=rtr;rtr->Next=ptr;D．ptr->Next=rtr;rtr->Next=qtr->Next;6．在一個(gè)單鏈表中，若現(xiàn)在要?jiǎng)h除ptr指針?biāo)附Y(jié)點(diǎn)的直接后繼結(jié)點(diǎn)，則需要執(zhí)行的操作是A。A．ptr->Next=ptr->Next->Next;B．ptr=ptr->Next;ptr->Next=ptr->Next->Next;C．ptr=ptr->Next->Next;D．ptr->Nextptr;7．在長(zhǎng)度為n的順序表中，往其第i個(gè)元素（1≤i≤n）之前插入一個(gè)新的元素時(shí)，需要往后移動(dòng)B個(gè)元素。A．n-iB．n-i+1C．n-i-1D．i8．在長(zhǎng)度為n的順序表中，刪除第i個(gè)元素（1≤i≤n）時(shí)，需要往前移動(dòng)A個(gè)元素。A．n-iB．n-i+1C．n-i-1D．i9．設(shè)tail是指向一個(gè)非空帶表頭結(jié)點(diǎn)的循環(huán)單鏈表的尾指針。那么，刪除鏈表起始結(jié)點(diǎn)的操作應(yīng)該是D。A．ptr=tail;B．tail=tail->Next;tail=tail->Next;free(tail);free(ptr);C．tail=tail->Next->Next;D．ptr=tail->Next->Next;Free(tail);tail->Next->Next=ptr->Next;Free(ptr);free(ptr);10．在單鏈表中，如果指針ptr所指結(jié)點(diǎn)不是鏈表的尾結(jié)點(diǎn)，那么在ptr之后插入由指針qtr所指結(jié)點(diǎn)的操作應(yīng)該是B。A．qtr->Next=ptr;B．qtr->Next=ptr->Next;ptr->Next=qtr;ptr->Next=qtr;C．qtr->Next=ptr->Next;D．ptr->Next=qtr;ptr=qtr;qtr->Next=ptr;三、問答1．試問，如下的線性表：L=(29，25，21，17，13，11，7，5，3，1)是有序線性表還是無序線性表？答：L是一個(gè)有序線性表。2．線性表L第i個(gè)存儲(chǔ)結(jié)點(diǎn)ai的起始地址LOC（ai）可以通過下面的公式計(jì)算得到：LOC（ai）=LOC（ai-1）+k其中k表示存儲(chǔ)結(jié)點(diǎn)的長(zhǎng)度。這個(gè)公式對(duì)嗎？為什么？答：這個(gè)公式是對(duì)的，因?yàn)榈趇個(gè)存儲(chǔ)結(jié)點(diǎn)ai的起始地址LOC（ai），實(shí)際上就是等于第i-1個(gè)存儲(chǔ)結(jié)點(diǎn)ai-1的起始地址LOC（ai-1）加上一個(gè)存儲(chǔ)結(jié)點(diǎn)的長(zhǎng)度k得到。3．試說明創(chuàng)建順序表算法Create_Sq()中，Sq_max和Sq_num的不同之處。答：Sq_max代表的是順序表的最大長(zhǎng)度，也就是它最多可以容納下多少個(gè)數(shù)據(jù)元素，順序表創(chuàng)建后，Sq_max是一個(gè)保持不變的常量；Sq_num代表的是順序表內(nèi)當(dāng)前擁有的數(shù)據(jù)元素個(gè)數(shù)，在順序表創(chuàng)建后，隨著對(duì)數(shù)據(jù)元素進(jìn)行的插入、刪除操作，Sq_num將會(huì)不斷地發(fā)生變化。4．如何判斷一個(gè)順序表是否為空？答：只需判定Sq_num的當(dāng)前值是多少，如果Sq_num為0，則表示順序表Sq為空，否則表示該順序表里有數(shù)據(jù)元素存在。5．在算法2-3里，操作“Sq_num=Sq_num-1”的作用是什么？沒有它行嗎？答：該操作是非常重要的，因?yàn)轫樞虮砝锂?dāng)前擁有的元素個(gè)數(shù)是通過Sq_num來記錄的，刪除了一個(gè)元素，Sq_num必須減1，這樣才能正確反映出刪除后表中元素的個(gè)數(shù)。所以，沒有這個(gè)操作是不行的。6．在算法2-9里，如果現(xiàn)在是把一個(gè)結(jié)點(diǎn)插入到單鏈表尾結(jié)點(diǎn)的后面。按照算法的描述，能夠保證插入后最后一個(gè)結(jié)點(diǎn)的Next域?yàn)椤唉眴幔看穑耗軌?。因?yàn)樵瓉韕tr->Next里是“Λ”，做了第1步操作：qtr->Next=ptr->Next;后，就是把插入結(jié)點(diǎn)的Next域置為“Λ”。7．在一個(gè)單鏈表中，為了刪除指針ptr所指的結(jié)點(diǎn)，有人編寫了下面的操作序列。讀懂并加以理解。試問，編寫者能夠達(dá)到目的嗎？其思想是什么？x=ptr->Data;qtr=ptr->Next;ptr->Data=ptr->Next->Data;ptr->Next=ptr->Next->Next;free(qtr);答：能夠達(dá)到刪除指針ptr所指結(jié)點(diǎn)的目的。編寫者的思想是不去直接刪除ptr所指的結(jié)點(diǎn)，而是在把ptr直接后繼的Data域內(nèi)容寫入ptr所指結(jié)點(diǎn)的Data域之后，把它的直接后繼刪除。對(duì)于單鏈表來說，得到一個(gè)結(jié)點(diǎn)的直接后繼容易，得到它的直接前驅(qū)難，所以這樣的設(shè)計(jì)是有其可取之處的。8．在一個(gè)單鏈表中，為了在指針ptr所指結(jié)點(diǎn)之前插入一個(gè)由指針qtr所指的結(jié)點(diǎn)，有人編寫了下面的操作序列，其中temp是一個(gè)臨時(shí)工作單元。讀懂并加以理解。試問，編寫者能夠達(dá)到目的嗎？其思想是什么？qtr->Next=ptr->Next;ptr->Next=qtr;temp=ptr->Data;p->Data=qtr->Data;qtr->Data=temp;答：能夠達(dá)到在指針ptr所指結(jié)點(diǎn)之前插入一個(gè)由指針qtr所指結(jié)點(diǎn)的目的。編寫者的思想是考慮到在單鏈表中得到一個(gè)結(jié)點(diǎn)的前驅(qū)信息較為困難，因此在這里先把qtr所指結(jié)點(diǎn)插入到ptr所指結(jié)點(diǎn)的后面，暫時(shí)成為它的直接后繼。然后通過臨時(shí)工作單元temp，將ptr及qtr所指結(jié)點(diǎn)的Data域內(nèi)容進(jìn)行交換，從而達(dá)到插入的目的。9．打算形成一個(gè)有表頭結(jié)點(diǎn)的循環(huán)雙鏈表，初始時(shí)除了每個(gè)結(jié)點(diǎn)的Next域已經(jīng)鏈接好外，它們的Prior域還都是空的。有人編寫了下面的算法，試圖完成Prior域的鏈接：Com_Cd(Cd_h){ptr=Cd_h->Next;qtr=Cd_h;while(ptr!=Cd_h){ptr->Prior=qtr;qtr=ptr;ptr=ptr->Next;}Cd_h->Prior=qtr;}讀懂并理解它，解釋為什么能夠完成各結(jié)點(diǎn)的Prior域的鏈接？答：算法中用兩個(gè)指針ptr和qtr配合，從頭到尾掃描這個(gè)循環(huán)雙鏈表，以達(dá)到讓每個(gè)結(jié)點(diǎn)的Prior域指向其直接前驅(qū)的目的。四、應(yīng)用1．設(shè)計(jì)一個(gè)計(jì)算表頭指針為L(zhǎng)k_h的單鏈表長(zhǎng)度（即結(jié)點(diǎn)個(gè)數(shù)）的算法。答：算法設(shè)計(jì)如下：Length_Lk(Lk_h){n=0;ptr=Lk_h;/*ptr指向起始結(jié)點(diǎn)*/while(ptr!=NULL){ptr=ptr->Next;n=n+1;/*n為結(jié)點(diǎn)計(jì)數(shù)單元*/}return(n);}2．用總是在表的頭部插入整數(shù)結(jié)點(diǎn)的方法建立一個(gè)單鏈表，當(dāng)輸入為0時(shí)，建表過程結(jié)束。答：算法設(shè)計(jì)如下：Clink(){Lk_h=NULL;scanf(%d,&x);while(x!=“0”){ptr=malloc(size);ptr->Data=x;ptr->Next=Lk_h;Lk_h=ptr;scanf(%d,&x);}returnLk_h;}3．一個(gè)不帶表頭結(jié)點(diǎn)的循環(huán)雙鏈表Ck的表頭指針為Ck_h，要在指針ptr指向處前插入一個(gè)rtr所指結(jié)點(diǎn)。模仿圖2-21，對(duì)一般插入位置標(biāo)示出下面4個(gè)操作步驟：①rtr->Next=ptr;②rtr->Prior=ptr->Prior;③ptr->Prior->Next=rtr;④ptr->Prior=rtr;答：4個(gè)操作步驟的具體功能體現(xiàn)如下圖所示。4．試設(shè)計(jì)一個(gè)算法copy(Ck_h1,Ck_h2)，將一個(gè)帶表頭結(jié)點(diǎn)的、以Ck_h1為表頭指針的單鏈表Ck1的內(nèi)容，復(fù)制到一個(gè)不帶表頭結(jié)點(diǎn)的、以Ck_h2為表頭指針的單鏈表Ck2中。答：算法具體如下。Copy(Ck_h1,Ck_h2){ptr=Ck_h1->Next;qtr=Ck_h2;while(ptr!=NULL){rtr=malloc(size);rtr->Data=ptr->Data;qtr->Next=rtr;qtr=rtr;ptr=ptr->Next;}qtr->Next=NULL;}5．已知一個(gè)帶表頭結(jié)點(diǎn)的遞增單鏈表。試編寫一個(gè)算法，功能是從表中去除值大于min、且值小于max的數(shù)據(jù)元素。（假定表中存在這樣的元素）答：所需算法編寫如下。Del_Sq(Lk_h,nim,max){ptr=Lk_h->Next;/*ptr指向鏈表的起始結(jié)點(diǎn)*/while((ptr!=NULL)&&(ptr->Data<=min))/*跳過所有值<=min的結(jié)點(diǎn)*/{qtr=ptr;ptr=ptr->Next;}while((ptr!=NULL)&&(ptr->Data<max))/*若結(jié)點(diǎn)值<max，則去除*/p=p->Next;qtr->Next=ptr;/*qtr指出第1個(gè)大于max的結(jié)點(diǎn)位置，完成鏈接*/}6．已知一個(gè)帶表頭結(jié)點(diǎn)的無序單鏈表。試編寫一個(gè)算法，功能是從表中去除所有值大于min、且值小于max的數(shù)據(jù)元素。答：所需算法編寫如下，其中指針ptr總是指向當(dāng)前被檢查的結(jié)點(diǎn)，qtr總是指向被檢查結(jié)點(diǎn)的直接前驅(qū)。Del_Lk(Lk_h,min,max){ptr=Lk_h->Next;/*ptr指向單鏈表的起始結(jié)點(diǎn)*/while(ptr!=NULL)/*掃視直到鏈尾結(jié)點(diǎn)*/{if((ptr->Data<=min)||(ptr->Data>=max)/*不滿足刪除條件*/{qtr=ptr;/*往后移動(dòng)qtr和ptr*/ptr=ptr->Next;}else/*刪除ptr所指結(jié)點(diǎn)，往后移動(dòng)ptr*/{qtr->Next=ptr->Next;free(ptr);ptr=qtr->Next;}}}7．一個(gè)單鏈表Lk的表頭指針為L(zhǎng)k_h，不同結(jié)點(diǎn)的Data域值有可能相同。編寫一個(gè)算法，功能是計(jì)算出Data域值為x的結(jié)點(diǎn)的個(gè)數(shù)。答：算法應(yīng)該遍歷鏈表的每一個(gè)結(jié)點(diǎn)，遇到一個(gè)結(jié)點(diǎn)的Data域值為x時(shí)，計(jì)數(shù)器n就加1。最后返回計(jì)數(shù)器n。Count_Lk(Lk_h){n=0;ptr=Lk_h;while(ptr!=NULL){if(ptr->Data==x)n=n+1;ptr=ptr->Next}return(n);}第3章習(xí)題解答一、填空1．限定插入和刪除操作只能在一端進(jìn)行的線性表，被稱為是棧。2．如果在順序棧滿時(shí)仍打算進(jìn)行進(jìn)棧操作，就稱為發(fā)生了“上溢”出錯(cuò)。3．如果在順序?？諘r(shí)仍打算進(jìn)行出棧操作，就稱為發(fā)生了“下溢”出錯(cuò)。4．在具有n個(gè)數(shù)據(jù)結(jié)點(diǎn)的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有n-1個(gè)數(shù)據(jù)元素。5．如果操作順序是先讓字母A、B、C進(jìn)棧，做兩次出棧；再讓字母D、E、F進(jìn)棧，做一次出棧；最后讓字母G進(jìn)棧，做三次出棧。最終這個(gè)堆棧從棧頂?shù)綏５椎挠嗔粼貞?yīng)該是DA。6．中綴表達(dá)式(a+b)-(c/(d+e))對(duì)應(yīng)的后綴表達(dá)式是ab+cde+/-。7．函數(shù)的遞歸調(diào)用有兩種形式：如果一個(gè)函數(shù)是直接調(diào)用自己，就稱其為直接遞歸調(diào)用；如果一個(gè)函數(shù)是通過另一個(gè)函數(shù)來調(diào)用自己，就稱其為間接遞歸調(diào)用。8．設(shè)某棧的元素輸入順序是1、2、3、4、5，想得到4、3、5、2、1的輸出順序。那么push、pop的操作序列應(yīng)該是push、push、push、push、pop、pop、push、pop、pop、pop。9．設(shè)鏈棧的棧頂指針為L(zhǎng)s_top，那么它非空的條件應(yīng)該是Ls_top!=NULL。10．隊(duì)列中，允許進(jìn)行刪除的一端稱為隊(duì)首。二、選擇1．一個(gè)棧的元素進(jìn)棧序列是a、b、c、d、e，那么下面的C不能做為一個(gè)出棧序列。A．e、d、c、b、aB．d、e、c、b、aC．d、c、e、a、bD．a(chǎn)、b、c、d、e2．判定一個(gè)順序隊(duì)列Qs（最多有n個(gè)元素）為空的條件是C。A．Qs_rear-Qs_front==n*sizeB．Qs_rear-Qs_front+1==n*sizeC．Qs_front==Qs_rearD．Qs_front==Qs_rear+size3．判定一個(gè)順序隊(duì)列Qs（最多有n個(gè)元素）真滿的條件是A。A．Qs_rear-Qs_front==n*sizeB．Qs_rear-Qs_front+1==n*sizeC．Qs_front==Qs_rearD．Qs_front==Qs_rear+size4．在一個(gè)鏈?zhǔn)疥?duì)列Lq中，Lq_front和Lq_rear分別為隊(duì)首、隊(duì)尾指針?，F(xiàn)在由指針ptr所指結(jié)點(diǎn)要進(jìn)隊(duì)，則插入操作應(yīng)該是B。A．Lq_front->Next=ptr;Lq_front=ptr;B．Lq_rear->Next=ptr;Lq_rear=ptr;C．ptr->Next=Lq_rear;Lq_rear=ptr;D．ptr->Next=Lq_front;Lq_front=ptr;5．鏈棧與順序棧相比，一個(gè)較為明顯的優(yōu)點(diǎn)是D。A．通常不會(huì)出現(xiàn)棧空的情形B．插入操作更加便利C．刪除操作更加便利D．通常不會(huì)出現(xiàn)棧滿的情形6．向鏈棧插入一個(gè)結(jié)點(diǎn)時(shí)，操作順序應(yīng)該是C。A．先修改棧頂指針，再插入結(jié)點(diǎn)B．無須修改棧頂指針C．先插入結(jié)點(diǎn)，再修改棧頂指針D．誰先誰后沒有關(guān)系7．從鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，操作順序應(yīng)該是A。A．先保存被刪結(jié)點(diǎn)的值，再修改棧頂指針B．先修改棧頂指針，再保存被刪結(jié)點(diǎn)的值C．無須修改棧頂指針的值D．誰先誰后沒有關(guān)系8．一個(gè)循環(huán)隊(duì)列的最大容量為m+1，front為隊(duì)首指針，rear為隊(duì)尾指針。那么進(jìn)隊(duì)操作時(shí)求隊(duì)位號(hào)應(yīng)該使用公式D。A．Cq_front=(Cq_front+1)%mB．Cq_front=(Cq_front+1)%(m+1)C．Cq_rear=(Cq_rear+1)%mD．Cq_rear=(Cq_rear+1)%(m+1)9．在一個(gè)循環(huán)順序隊(duì)列里，隊(duì)首指針Cq_front總是指向B。A．隊(duì)首元素B．隊(duì)首元素的前一個(gè)隊(duì)位C．任意位置D．隊(duì)首元素的后一個(gè)隊(duì)位10．若一個(gè)棧的進(jìn)棧序列是1、2、3、4，那么要求出棧序列為3、2、1、4時(shí)，進(jìn)、出棧操作的順序應(yīng)該是A。（注：所給順序中，I表示進(jìn)棧操作，O表示出棧操作）A．IIIOOOIOB．IOIOIOIOC．IIOOIOIOD．IOIIIOOO三、問答1．若元素進(jìn)棧的序列是1、2、3、…、n，有一個(gè)出棧序列的第1個(gè)元素是n。那么，這個(gè)出棧序列的第i個(gè)元素是什么？答：由于棧具有“先進(jìn)后出”的特性，因此只有將1、2、3、…、n依次都進(jìn)棧后，出棧序列的第1個(gè)元素才能是n。所以，在這個(gè)出棧序列里，第個(gè)i元素應(yīng)該是n-i+1。2．設(shè)元素進(jìn)棧的次序是a，b，c，d，e。試問，在下面所列的6種元素序列里，哪些可以是這個(gè)棧的出棧序列？A．c，e，a，b，dB．c，b，a，d，eC．d，c，a，b，eD．a(chǎn)，c，b，e，dE．a(chǎn)，b，c，d，eF．e，a，b，c，d答：對(duì)A進(jìn)行分析。由于是c第1個(gè)出棧，因此b必須先于a出棧。但所給序列里，a卻先于b出棧，故A不能是該棧的出棧序列。對(duì)C進(jìn)行分析。由于是d第1個(gè)出棧，因此a、b、c三者出棧的順序必須是c、b、a。但所給序列里，a卻先于b出棧，故C不能是該棧的出棧序列。對(duì)F進(jìn)行分析。由于是e第1個(gè)出棧，因此a、b、c、d四者出棧的順序必須是d、c、b、a。但所給序列里，它們的出棧順序全亂了，故F不能是該棧的出棧序列。因此，所列的6種元素序列里，只有B、D、E可以是這個(gè)棧的出棧序列。3．有一個(gè)順序棧Ss，其棧頂指針為Ss_top，棧底指針為Ss_bottom。閱讀下面給出的算法，其中的兩條prinf函數(shù)的輸出結(jié)果各是什么？(算法中的Push_Ss(Ss_top,ch)表示將ch里的元素進(jìn)棧，Pop_Ss(Ss_top,ch)表示將棧頂元素出棧，存入ch中)print(){for(ch=‘A’;ch<=‘A’+12;ch++){Push_Ss(Ss_top,ch);printf(“%c”,ch);}while(Ss_top!=Ss_bottom){Pop_Ss(Ss_top,ch);printf(“%c”,ch);}}答：第1條printf的輸出是前13個(gè)英文大寫字母ABCDEFGHIJKLM，第2條printf輸出的是前面輸出的倒置，即MLKJIHGFEDCBA。4．設(shè)有6個(gè)元素a1、a2、a3、a4、a5、a6，它們以此順序依次進(jìn)棧。假定要求它們的出棧順序是a4、a3、a2、a6、a5、a1，那么應(yīng)該如何安排push和pop操作序列？答：所需的push和pop操作序列如下：push，push，push，push，pop，pop，pop，push，push，pop，pop，pop5．有中綴表達(dá)式a/(b/(c/(d/e)))。有人將其轉(zhuǎn)化為相應(yīng)的后綴表達(dá)式是abcde////。這一轉(zhuǎn)化結(jié)果對(duì)嗎？答：轉(zhuǎn)化結(jié)果是對(duì)的。6．試述棧與隊(duì)列各自具有什么樣的邏輯特點(diǎn)？它們之間又有什么共同點(diǎn)？答：對(duì)于棧來說，由于只能在棧頂處進(jìn)行插入和刪除操作，這就使得數(shù)據(jù)元素到達(dá)棧（即往棧里插入元素）的順序與數(shù)據(jù)元素離開棧（即從棧里刪除元素）的順序恰好相反。所以，堆棧的邏輯特點(diǎn)是后進(jìn)先出（LIFO），或先進(jìn)后出（FILO）。而對(duì)隊(duì)列來說，插入在一端進(jìn)行，刪除在另一端進(jìn)行，這就使得數(shù)據(jù)元素到達(dá)隊(duì)列（即往隊(duì)列里插入元素）的順序與數(shù)據(jù)元素離開隊(duì)列（即從隊(duì)列里刪除元素）的順序是完全一致的。所以，隊(duì)列的邏輯特點(diǎn)是先進(jìn)先出（FIFO）或后進(jìn)后出（LILO）。它們之間的共同之處是插入和刪除只能在表的端點(diǎn)處進(jìn)行（要知道，對(duì)于線性表，可以在表的任何位置處插入和刪除）。7．有一個(gè)順序隊(duì)列，最大容量為5。初始時(shí)有Qs_front=Qs_rear=0。畫出做下列操作時(shí)隊(duì)列及其首、尾指針的變化情況。若不能進(jìn)隊(duì)時(shí)就停止，并簡(jiǎn)述原因。（1）d、e、b進(jìn)隊(duì)（2）d、e出隊(duì)（3）i、j進(jìn)隊(duì)（4）b出隊(duì)（5）n、o、p進(jìn)隊(duì)答：隊(duì)列及其首、尾指針的變化情況如下圖所示。在做（5）時(shí)，由于隊(duì)滿（假溢出），故操作停止。8．有一個(gè)遞歸函數(shù)Write()，定義如下：Write(x){if(x!=0){Write(x-1);for(j=1;j<=x;j++)printf(“%3d”,x);printf(“/n”);}}試問，Write(5)的輸出結(jié)果是什么？答：輸出結(jié)果為：122333444455555四、應(yīng)用1．編寫一個(gè)判順序?？盏乃惴?。要求是如果?？?，返回1，否則返回0。答：算法設(shè)計(jì)如下：Empty_Ss(Ss,Ss_top){if(Ss_top==0)/*棧空*/return(1);else/*棧不空*/return(0);}2．編寫一個(gè)算法，它能夠輸出順序隊(duì)列Qs上所有元素的值。答：算法編寫如下：Print_Qs(Qs_front,Qs_rear){if(Qs_front==Qs_rear)/*隊(duì)列空！*/printf(“queueisempty!”);else/*隊(duì)列非空！*/{qtr=Qs_front;while(qtr<=Qs_rear){printf(“%d”,*qtr);qtr++;}}}3．編寫一個(gè)算法，它能夠取得鏈?zhǔn)疥?duì)列首元素的值。答：取得鏈?zhǔn)疥?duì)列首元素的值，只有在隊(duì)列非空的前途下才有意義。算法編寫如下。Getf_Lq(Lq_front,Lq_rear){if(Lq_front==Lq_rear)/*隊(duì)列空！*/printf(“Thelinkedqueueisempty!”);else/*隊(duì)列非空！*/{ptr=Lq_front->Next;x=ptr->Data;return(x);}}4．有五個(gè)人順序坐在一起。問第5個(gè)人多少歲，回答說比第4個(gè)人大2歲；問第4個(gè)人多少歲，回答說比第3個(gè)人大2歲；問第3個(gè)人多少歲，回答說比第2個(gè)人大2歲；問第2個(gè)人多少歲，回答說比第1個(gè)人大2歲；問第1個(gè)人多少歲，回答說是10歲。試給出該遞歸的公式、結(jié)束條件，并編寫出相應(yīng)的遞歸算法。答：遞歸公式為：age(n)=age(n-1)+22<=n<=5遞歸的結(jié)束條件是：age(1)=10相應(yīng)算法為：Age(n){if(n==1)return(10);else{x=age(n-1)+2;return(x);}}5．將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式的方法類似于中綴表達(dá)式求值。具體地，要開辟一個(gè)運(yùn)算符棧op和一個(gè)數(shù)組st。在自左至右掃描算術(shù)表達(dá)式時(shí)，遇到操作數(shù)就直接順序存入st；遇到運(yùn)算符時(shí)就與op棧頂元素比較，高則進(jìn)棧，不高則讓棧頂元素出棧，存入st，然后該運(yùn)算符再次去與新的op棧頂元素比較。最后，在數(shù)組st里形成所需要的后綴表達(dá)式。試用這種方法，用圖示將中綴表達(dá)式5+8*3-2轉(zhuǎn)化成為相應(yīng)的后綴表達(dá)式。答：相應(yīng)的后綴表達(dá)式是583*+2-，其圖示如下。6．語言編譯時(shí)，總是先將中綴表達(dá)式轉(zhuǎn)化成為后綴表達(dá)式，然后再計(jì)算后綴表達(dá)式的值，因?yàn)楹缶Y表達(dá)式已經(jīng)去除了括號(hào)，沒有了運(yùn)算符的優(yōu)先級(jí)。計(jì)算后綴表達(dá)式的方法是只開辟一個(gè)對(duì)象棧ob，當(dāng)從左往右掃描后綴表達(dá)式時(shí)，每遇到操作數(shù)就讓其進(jìn)入ob棧，每遇到運(yùn)算符就從ob棧里彈出兩個(gè)操作數(shù)進(jìn)行當(dāng)前的計(jì)算，并將計(jì)算結(jié)果進(jìn)ob棧。該過程直至整個(gè)表達(dá)式結(jié)束。ob棧的棧頂值就是最終結(jié)果。試用圖示計(jì)算后綴表達(dá)式583*+2-的值。答：計(jì)算結(jié)果為27，其圖示如下。第4章習(xí)題解答一、填空1．字符串是一種特殊的線性表，特殊在于它的數(shù)據(jù)元素只能是字符，特殊在于串可以作為一個(gè)整體參與所需要的處理。2．空格串是由空格組成的串，空串是不含任何字符的串，因此空格串和空串不是一個(gè)概念。3．字符串中任意多個(gè)連續(xù)字符所組成的子序列，被稱作是這個(gè)串的“子串”，這個(gè)字符串本身則稱為“主串”。4．我們說兩個(gè)字符串相等，在計(jì)算機(jī)內(nèi)部實(shí)際上是通過對(duì)相應(yīng)位置上字符ASCII碼的比較而得到的結(jié)論。5．設(shè)有串s=“Iamateacher”。該串的長(zhǎng)度是14。6．設(shè)有三個(gè)串：s1=“Good”，s2=“Ф”，s3=“bye!”。則s1、s2、s3連接后的結(jié)果串應(yīng)該是“Goodbye!”。7．所謂“數(shù)組”，是指n（n>1)個(gè)具有相同類型的數(shù)據(jù)的有序集合。8．矩陣與通常所說的二維數(shù)組有關(guān)。9．所謂“特殊矩陣”，是指那些元素在矩陣中的分布具有一定規(guī)律性的矩陣；而矩陣中的零元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)多于非零元素的個(gè)數(shù)，但非零元素的分布卻沒有規(guī)律，這樣的矩陣被稱為“稀疏矩陣”。10．在一個(gè)n階方陣A中，若所有元素都有性質(zhì)：，就稱其為對(duì)稱矩陣。二、選擇1．設(shè)有兩個(gè)串s1和s2。求s2在s1中首次出現(xiàn)的位置的操作稱為B。A．連接B．模式匹配C．求子串D．求串長(zhǎng)2．有串：“Ф”，那么它的長(zhǎng)度是B。A．0B．1C．2D．33．設(shè)有串s1=“ABCDEFG”和s2=“PQRST”。已知：算法con(x,y)返回串x和y的連接串；subs(s,i,j)返回串s的第i個(gè)字符開始往后j個(gè)字符組成的子串；len(s)返回串s的長(zhǎng)度。那么，con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的操作結(jié)果是串D。A．BCDEFB．BCDEFGC．BCPQRSTD．BCDEFEF4．設(shè)有一個(gè)8階的對(duì)稱矩陣A，采用以行優(yōu)先的方式壓縮存儲(chǔ)。a11為第1個(gè)元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間。試問元素a85的地址是A。A．33B．30C．13D．235．一個(gè)m*m的對(duì)稱矩陣，如果以行優(yōu)先的方式壓縮存入內(nèi)存。那么所需存儲(chǔ)區(qū)的容量應(yīng)該是C。A．m*(m-1)/2B．m*m/2C．m*(m+1)/2D．(m+1)*(m+1)/26．二維數(shù)組M的每個(gè)元素含4個(gè)字符（每個(gè)字符占用一個(gè)存儲(chǔ)單元），行下標(biāo)i從1變到5，列下標(biāo)j從1變到6。那么按行順序存儲(chǔ)時(shí)元素M[4][6]的起始地址與M按列順序存儲(chǔ)時(shí)元素B的起始地址相同。A．M[3][5]B．M[4][5]C．M[4][6]D．M[5][5]7．二維數(shù)組M中的每個(gè)元素占用3個(gè)存儲(chǔ)單元，行下標(biāo)i從1變到8，列下標(biāo)j從1變到10?，F(xiàn)從首地址為SA的存儲(chǔ)區(qū)開始存放A。那么該數(shù)組以行優(yōu)先存放時(shí)，元素A[8][5]的起始地址應(yīng)該是C。A．SA+141B．SA+180C．SA+222D．SA+2258．設(shè)有一個(gè)5階上三角矩陣A，將其元素按列優(yōu)先順序存放在一維數(shù)組B中。已知每個(gè)元素占用2個(gè)存儲(chǔ)單元，B[1]的地址是100。那么A[3][4]的地址是A。A．116B．118C．120D．122（分析：把一個(gè)上三角矩陣按列優(yōu)先順序存放在一個(gè)一維數(shù)組B中，元素的順序是：a11a12a22a13……A[3,4]的地址=100+a34前面的元素個(gè)數(shù)*2=100+（前3列的個(gè)數(shù)+本列a34前面的個(gè)數(shù)）*2=100+（（1+2+3）+2）*2=116）三、問答1．為什么可以把二維數(shù)組視為是一種線性結(jié)構(gòu)？答：實(shí)際上，二維數(shù)組是一種較為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)元素之間的關(guān)系并不是線性的。不過，如果我們把它看作是其每個(gè)元素為一維數(shù)組的一個(gè)一維數(shù)組，那么就可以把二維數(shù)組視為是線性表的一種推廣（因?yàn)橐痪S數(shù)組即是線性表），因此可以說它的數(shù)據(jù)元素間的邏輯關(guān)系呈現(xiàn)出的是一種線性結(jié)構(gòu)。2．圖4-34（a）所示為一個(gè)特殊矩陣A55，這種形式的矩陣被稱作是“帶狀矩陣”，因?yàn)樗姆橇阍囟挤植荚谝灾鲗?duì)角線為中心的一個(gè)帶狀區(qū)域里，其他位置上的元素全部為0?？梢砸孕袃?yōu)先的方式，將其壓縮存儲(chǔ)到一個(gè)一維數(shù)組里，如圖4-34（b）所示。試找出元素下標(biāo)i、j與存儲(chǔ)序號(hào)k間的對(duì)應(yīng)關(guān)系。圖4-34帶狀矩陣答：壓縮存儲(chǔ)元素下標(biāo)i、j與存儲(chǔ)序號(hào)k間的對(duì)應(yīng)關(guān)系是：k=2*i+j–23．一個(gè)稀疏矩陣如圖4-35所示。試問，它對(duì)應(yīng)的三元組表是什么？圖4-35稀疏矩陣示例答：它所對(duì)應(yīng)的三元組表如下。四、應(yīng)用1．請(qǐng)將算法4-1改為用while循環(huán)來實(shí)現(xiàn)。答：改寫的算法4-1可以是如下所示。Concat_St(St1,St2){charSt3[maxsize];/*創(chuàng)建一個(gè)新的順序串為空*/St3_len=0;if(St1_len+St2_len>maxsize+1)/*新串放不下兩個(gè)串*/{printf(“兩串長(zhǎng)度之和超長(zhǎng)！”);return(NULL);}else{i=1；while(i<=St1_len){St3[i]=St1[i];i++;}j=1;while(j<=St2_len){St3[j+St1_len]=St2[j];j++;}St3_Len=St1_len+St2_len;St3[St3_len+1]=“\0”;return(St3);}}2．算法4-2也可以這樣來描述，直接核對(duì)相應(yīng)位置上的字符是否相同，然后再分別情況做出判斷：一是有不相同的字符出現(xiàn)，一是有一個(gè)字符串比另一個(gè)字符串長(zhǎng)，最后則是兩個(gè)串完全相等。按照這樣的設(shè)計(jì)，改寫算法4-2。答：按照這樣的設(shè)計(jì)，算法4-2的描述如下。Equal_St(St1,St2){i=1;while(St1[i]!=“\0”)/*兩串進(jìn)行比較*/{if(St1[i]==St2[i])/*相等，繼續(xù)比較*/i++;else/*不等，強(qiáng)制退出*/black;}if(St1[i]!=St2[i])/*比較是由于相應(yīng)位置上的字符不同而結(jié)束*/return(0);else{if(St1[i]!=“\0”||St2[i]!=“\0”)/*比較是由于長(zhǎng)度不同而結(jié)束*/return(0);elsereturn(1);}}3．算法：Trans_St(St，ch1，ch2){i=1；While(St[i]！="\0"){if(St[i]==ch1)St[i]==ch2；i++；}}是通過while循環(huán)來實(shí)現(xiàn)將順序串St中所有的字符ch1改為字符ch2的。請(qǐng)改寫成用for循環(huán)來實(shí)現(xiàn)相同的功能。答：用for循環(huán)改寫的算法如下。Trans_St(St,ch1,ch2){for(i=1;i<=St_len;i++)if(St[i]==ch1)St[i]=ch2;}4．編寫一個(gè)算法，將順序串St中所有的大寫字母全部換成小寫字母。(提示：大寫英文字母A~Z對(duì)應(yīng)的ASCII碼為65~90，小寫英文字母a~z對(duì)應(yīng)的ASCII碼為97~122，在大寫字母的ASCII碼上加32，就是對(duì)應(yīng)小寫字母的ASCII碼)答：算法編寫如下。Catosm_St(St){for(i=1;i<=St_len;i++)if((A<=St[i])&&(St[i]<=Z))St[i]=St[i]+32;}5．已知順序串St，編寫一個(gè)算法，將其中第i個(gè)字符開始連續(xù)的j個(gè)字符刪除。（提示：先要判斷所給參數(shù)是否合理，然后通過將第i+j開始往后的字符全部移動(dòng)j個(gè)位置，完成刪除的功能）答：算法編寫如下。Moveij(St,i,j){if(i+j<=St_len){for(k=i+j;k<=St_len;k++)/*將i+j開始往后的所有字符前移j個(gè)位置*/St[k-j]=St[k];St_len=St_len-j;/*修改St的長(zhǎng)度*/St[St_len]=“\0”;/*安放新的串結(jié)束符*/}elseprintf(“參數(shù)不合理，無法進(jìn)行刪除！”);}6．在算法4-12的最后，為了釋放被刪結(jié)點(diǎn)使用的存儲(chǔ)空間，先做了操作：ptr->Next=NULL;把由指針ptr指向的最后一個(gè)要釋放空間的結(jié)點(diǎn)的Next域設(shè)置為NULL，然后通過while循環(huán)完成釋放。其實(shí)，由于知道要釋放空間的結(jié)點(diǎn)共有m個(gè)，因此可以取消這一操作，改用for循環(huán)通過m來控制釋放空間的結(jié)點(diǎn)個(gè)數(shù)。請(qǐng)?jiān)囍凑者@一思路改寫那一小段算法。答：改寫一小段算法如下。for(j=1;j<=m;j++){ptr=rtr;rtr=rtr->Next;free(ptr);}7．編寫一個(gè)算法，功能是復(fù)制一個(gè)鏈串。答：復(fù)制一個(gè)完整的鏈串，是一件比較容易的事情。其算法起名為Copy_Lt()，參數(shù)為L(zhǎng)t1。具體編寫如下。Copy_Lt(Lt1){ptr=Lt1_h;rtr=malloc(size);rtr->Data=ptr->Data;Lt2_h=rtr;ptr=ptr->Next;while(ptr!=NULL){qtr=malloc(size);qtr->Data=ptr->Data;rtr->Next=qtr;ptr=ptr->Next;}rtr->Next=NULL;return(Lt2_h);}算法是通過while循環(huán)，不斷修改指針ptr，以便指向鏈串Lt1的各個(gè)結(jié)點(diǎn)；指針rtr總是指向當(dāng)前已形成的新鏈串Lt2的最后一個(gè)結(jié)點(diǎn)；用指針qtr指向剛申請(qǐng)到的新存儲(chǔ)結(jié)點(diǎn)，并把它鏈入到rtr所指結(jié)點(diǎn)的后面。8．已知兩個(gè)mⅹn的矩陣A和B。編寫一個(gè)算法，求C=A+B。即C也是一個(gè)mⅹn的矩陣，其元素滿足條件：cij=aij+bij（1≤i≤m，1≤j≤n）答：算法名為Add_Mt()，參數(shù)為A，B，C。Add_Mt(A,B,C){for(i=1;i<=m;i++)for(j=1;j<=n;j++)C[i][j]=A[i][j]+B[i][j];}第5章習(xí)題解答（此處樹的高度不計(jì)算根節(jié)點(diǎn)）一、填空1．結(jié)點(diǎn)數(shù)為7的二叉樹的高度最矮是2，最高是6。2．給定二叉樹的結(jié)點(diǎn)數(shù)，要使樹高為最大，那么該樹應(yīng)該是單枝形狀。3．給定二叉樹的結(jié)點(diǎn)數(shù)，要使樹高為最矮，那么該樹應(yīng)該是完全二叉樹形狀。4．如果一棵滿二叉樹的深度為6，那么它共有127個(gè)結(jié)點(diǎn)，有64個(gè)葉結(jié)點(diǎn)。5．有15個(gè)結(jié)點(diǎn)的二叉樹，最少有1個(gè)葉結(jié)點(diǎn)，最多有8個(gè)葉結(jié)點(diǎn)。6．由n個(gè)帶權(quán)值的葉結(jié)點(diǎn)生成的哈夫曼樹，最終共有2n-1個(gè)結(jié)點(diǎn)。7．將一棵完全二叉樹按層次進(jìn)行編號(hào)。那么，對(duì)編號(hào)為i的結(jié)點(diǎn)，如果有左孩子，則左孩子的編號(hào)應(yīng)該是2i；如果有右孩子，則右孩子的編號(hào)應(yīng)該是2i+1。8．若二叉樹共有n個(gè)結(jié)點(diǎn)，采用二叉鏈表存儲(chǔ)結(jié)構(gòu)。那么在所有存儲(chǔ)結(jié)點(diǎn)里，一共會(huì)有2n個(gè)指針域，其中有n+1個(gè)指針域是空的。9．深度為5的二叉樹，至多有31個(gè)結(jié)點(diǎn)。10．在二叉樹中，有一個(gè)結(jié)點(diǎn)具有左、右兩個(gè)孩子。那么在中序遍歷序列里，它的右孩子一定排在它的右邊。二、選擇1．在所給的4棵二叉樹中，C不是完全二叉樹。2．把一棵深度為3的左單支二叉樹改造成完全二叉樹時(shí)，要增添D個(gè)空結(jié)點(diǎn)。A．10B．8C．6D．43．設(shè)有一棵5個(gè)結(jié)點(diǎn)的二叉樹，其先序遍歷序列為：A-B-C-D-E，中序遍歷序列為：B-A-D-C-E，那么它的后序遍歷序列為B。A．A-B-D-E-CB．B-D-E-C-AC．D-E-C-A-BD．A-B-C-D-E4．將一棵有50個(gè)結(jié)點(diǎn)的完全二叉樹按層編號(hào)，那么編號(hào)為25的結(jié)點(diǎn)是B。A．無左、右孩子B．有左孩子，無右孩子C．有右孩子，無左孩子D．有左、有孩子5．深度為6的二叉樹，最多可以有A個(gè)結(jié)點(diǎn)。A．63B．64C．127D．1286．在一棵非空二叉樹的中序遍歷序列里，根結(jié)點(diǎn)的右邊D結(jié)點(diǎn)。A．只有左子樹上的部分B．只有左子樹上的所有C．只有右子樹上的部分D．只有右子樹上的所有7．在任何一棵二叉樹的各種遍歷序列中，葉結(jié)點(diǎn)的相對(duì)次序是A。A．不發(fā)生變化B．發(fā)生變化C．不能確定D．以上都不對(duì)8．權(quán)值為1、2、6、8的四個(gè)結(jié)點(diǎn)，所構(gòu)造的哈夫曼樹的帶權(quán)路徑長(zhǎng)度是D。A．18B．28C．19D．299．一棵二叉樹度2的結(jié)點(diǎn)數(shù)為7，度1的結(jié)點(diǎn)數(shù)為6。那么它的葉結(jié)點(diǎn)數(shù)是C。A．6B．7C．8D．910．在一棵二叉樹中，第5層上的結(jié)點(diǎn)數(shù)最多是C個(gè)。A．8B．15C．16D．32三、問答1．試問滿二叉樹與完全二叉樹之間有何關(guān)系？答：由滿二叉樹與完全二叉樹的定義可知，滿二叉樹一定是一棵完全二叉樹，但完全二叉樹卻不一定是一棵滿二叉樹。如果一棵二叉樹不是完全二叉樹，那么它絕對(duì)不可能是一棵滿二叉樹。這就是滿二叉樹與完全二叉樹之間的關(guān)系。2．請(qǐng)畫出由3個(gè)結(jié)點(diǎn)構(gòu)成的所有二叉樹，它們的高度分別是多少？答：大小為3的不同的二叉樹共有5種，如下圖所示。其中，4棵樹的高度為2，1棵樹的高度為1。3．一棵高度為3的滿二叉樹有多少個(gè)葉結(jié)點(diǎn)？有多少個(gè)度為2的結(jié)點(diǎn)？總共有多少個(gè)結(jié)點(diǎn)？答：有23=8個(gè)葉結(jié)點(diǎn)，有度為2的結(jié)點(diǎn)23-1=7個(gè)，總共有23+1-1=24-1=15個(gè)結(jié)點(diǎn)。4．有人說，任何一棵非空滿二叉樹，它的葉結(jié)點(diǎn)數(shù)等于其分支結(jié)點(diǎn)數(shù)加1。這樣的一個(gè)結(jié)論正確嗎？請(qǐng)說明理由。（提示：利用性質(zhì)5-3）答：在我們介紹的二叉樹性質(zhì)中，只有性質(zhì)5-3是涉及葉結(jié)點(diǎn)數(shù)與（度為2的）分支結(jié)點(diǎn)數(shù)的關(guān)系的。對(duì)于滿二叉樹來說，所有的分支結(jié)點(diǎn)都是度為2的結(jié)點(diǎn)。因此，正好可以直接利用性質(zhì)5-3得出所需要的結(jié)論。所以，此人說的結(jié)論是完全正確的。5．有人說，有一棵結(jié)點(diǎn)數(shù)為n>1的二叉樹，只包含有一個(gè)葉結(jié)點(diǎn)。這可能嗎？如果可能的話，這樣一棵二叉樹應(yīng)該是個(gè)什么樣子呢？答：這是完全可能的，這種二叉樹是從根結(jié)點(diǎn)開始只有左子樹，或只有右子樹的單支二叉樹，如圖所示。6．試問，什么樣的二叉樹其先序遍歷序列與中序遍歷序列相同？答：先序遍歷序列與中序遍歷序列相同的二叉樹，或是空二叉樹，或是任一結(jié)點(diǎn)都沒有左孩子的非空二叉樹。7．分別寫出如圖5-32所示二叉樹的先序、中序、后序遍歷序列。圖5-32二叉樹示例答：先序遍歷序列為：A-B-C-D-F-G-H-E，中序遍歷序列為：B-A-D-G-F-H-C-E，后序遍歷序列為：B-G-H-F-D-E-C-A。四、應(yīng)用1．對(duì)一個(gè)二叉樹進(jìn)行順序存儲(chǔ)，各結(jié)點(diǎn)的編號(hào)及數(shù)據(jù)如表所示：編號(hào)i1234571011數(shù)據(jù)xABCDEFGH試畫出對(duì)應(yīng)的二叉樹，并給出先序、中序、后序遍歷該二叉樹后，所得到的各種結(jié)點(diǎn)序列。答：對(duì)應(yīng)的二叉樹如圖所示。其先序遍歷序列是：A-B-D-E-G-H-C-F；中序遍歷序列是：D-B-G-E-H-A-C-F；后許遍歷序列是：D-G-H-E-B-F-C-A。2．已知中序遍歷序列為：A-B-C-E-F-G-H-D，后序遍歷序列為：A-B-F-H-G-E-D-C。試畫出這棵二叉樹。答：這棵二叉樹如應(yīng)用題2答案圖所示。3．已知前序遍歷序列為：A-B-C-D-E-F，中序遍歷序列為：C-B-A-E-D-F。試畫出這棵二叉樹。答：這棵二叉樹如應(yīng)用題3答案圖所示。4．若一棵二叉樹的左、右子樹均有3個(gè)結(jié)點(diǎn)，其左子樹的先序遍歷序列與中序遍歷序列相同，右子樹的中序遍歷序列與后序遍歷序列相同。請(qǐng)畫出這棵二叉樹。答：這棵二叉樹如應(yīng)用題4答案圖所示。5．理解算法5-10。在圖5-25(b)的基礎(chǔ)上，進(jìn)行下一次組合。試給出第2次組合后數(shù)組的情形，以及那時(shí)二叉樹的樣子。答：第2次組合后數(shù)組的情形如下圖(a)所示，那時(shí)二叉樹的樣子如下圖(b)所示。6．權(quán)值序列為：10、16、20、6、30、24，請(qǐng)用圖示來表達(dá)構(gòu)造一棵哈夫曼樹的全過程。答：構(gòu)造這棵哈夫曼樹的全過程如下所示。7．一棵有11個(gè)結(jié)點(diǎn)的二叉樹的順序存儲(chǔ)情況如表所示，序號(hào)3的結(jié)點(diǎn)是根結(jié)點(diǎn)。畫出該二叉樹，并給出它的先序、中序、后序遍歷序列（其中“^”表示空）。序號(hào)1234567891011Lchild6^7^8^5^2^^DataMFAKBLCRDSERchild^^^9^10411^^^答：二叉樹如圖所示，先序遍歷序列為：A-C-B-R-S-E-D-F-M-L-K，中序遍歷序列為：R-B-S-C-E-A-F-D-L-K-M，后序遍歷序列為：R-S-B-E-C-F-K-L-M-D-A。第6章習(xí)題解答一、填空1．樹中結(jié)點(diǎn)的度，是指結(jié)點(diǎn)擁有子樹的個(gè)數(shù)。2．樹中除根結(jié)點(diǎn)外，其他結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)，但可以有零個(gè)或多個(gè)后繼結(jié)點(diǎn)。3．樹中一個(gè)結(jié)點(diǎn)的直接后繼，或一個(gè)結(jié)點(diǎn)子樹的根結(jié)點(diǎn)，被稱作是該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。4．樹中一個(gè)結(jié)點(diǎn)的子樹中的任何結(jié)點(diǎn)，都被稱作是該結(jié)點(diǎn)的子孫結(jié)點(diǎn)。5．樹中有同一雙親的結(jié)點(diǎn)，被互稱為兄弟結(jié)點(diǎn)。6．所謂結(jié)點(diǎn)的深度，即是指該結(jié)點(diǎn)位于樹的層次數(shù)。7．雙親位于樹中相同層次上的結(jié)點(diǎn)，互稱為堂兄弟結(jié)點(diǎn)。8．在數(shù)據(jù)結(jié)構(gòu)中，把n（n≥0）棵互不相交的樹的集合稱為森林。9．在如圖6-21所示的樹中，，結(jié)點(diǎn)H的祖先是A、D、G。圖6-21樹示例圖6-22樹示例10．在樹中，一個(gè)結(jié)點(diǎn)的孩子個(gè)數(shù)，稱為該結(jié)點(diǎn)的度。11．一棵樹的形狀如圖6-22所示。它的根結(jié)點(diǎn)是A，葉結(jié)點(diǎn)是E、G、I、J、K、L、N、O、P、Q、R，這棵樹的度是3，這棵樹的深度是4，結(jié)點(diǎn)F的孩子結(jié)點(diǎn)是J、K，結(jié)點(diǎn)G的父結(jié)點(diǎn)是C，結(jié)點(diǎn)M、H、D、A是結(jié)點(diǎn)R的祖先。二、選擇1．已知一棵單右支的二叉樹，如下左圖所示。把它還原成森林，應(yīng)該是D。A．B．C．D．2．將一棵樹Tr轉(zhuǎn)換成相應(yīng)的二叉樹Bt，那么對(duì)Tr的先序遍歷是對(duì)Bt的A。A．先序遍歷B．中序遍歷C．后序遍歷D．無法確定3．將一棵樹Tr轉(zhuǎn)換成相應(yīng)的二叉樹Bt，那么對(duì)Tr的后序遍歷是對(duì)Bt的B。A．先序遍歷B．中序遍歷C．后序遍歷D．無法確定4．設(shè)森林F中有3棵樹，依次有結(jié)點(diǎn)n1、n2、n3個(gè)。把該森林轉(zhuǎn)換成對(duì)應(yīng)的二叉樹后，該二叉樹的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是D。A．n1B．n1+n2C．n3D．n2+n35．設(shè)有由三棵樹T1、T2、T3組成的森林，其結(jié)點(diǎn)個(gè)數(shù)分別為n1、n2、n3。與該森林相應(yīng)的二叉樹為Bt。則該二叉樹根結(jié)點(diǎn)的左子樹中應(yīng)該有結(jié)點(diǎn)A個(gè)。A．n1-1B．n1C．n1+1D．n1+n26．現(xiàn)有一棵度為3的樹，它有兩個(gè)度為3的結(jié)點(diǎn)，一個(gè)度為2的結(jié)點(diǎn)，兩個(gè)度為1的結(jié)點(diǎn)。那么其度為0的結(jié)點(diǎn)的個(gè)數(shù)應(yīng)該是C。A．5B．8C．6D．9注意：有n個(gè)結(jié)點(diǎn)的樹，樹中所有結(jié)點(diǎn)的度之和為n-1。現(xiàn)在這棵樹應(yīng)該滿足條件：n-1=2*3+1*2+2*1=10這表示該樹共有11個(gè)結(jié)點(diǎn)（加上一個(gè)根結(jié)點(diǎn)）。在11個(gè)結(jié)點(diǎn)里，減去度為3、2、1的結(jié)點(diǎn)數(shù)5，剩下的就是度為0的結(jié)點(diǎn)。所以，該樹有葉結(jié)點(diǎn)6個(gè)。7．一棵有n個(gè)結(jié)點(diǎn)的樹，在把它轉(zhuǎn)換成對(duì)應(yīng)的二叉樹之后，該二叉樹根結(jié)點(diǎn)的左子樹上共有B個(gè)結(jié)點(diǎn)。A．n-2B．n-1C．n+1D．n+28．一棵有n個(gè)結(jié)點(diǎn)的樹，在把它轉(zhuǎn)換成對(duì)應(yīng)的二叉樹之后，該二叉樹根結(jié)點(diǎn)的右子樹上共有A個(gè)結(jié)點(diǎn)。A．0B．nC．n+1D．n+29．下列說法中，正確的是A。A．樹的先序遍歷序列與其對(duì)應(yīng)的二叉樹的先序遍歷序列相同B．樹的先序遍歷序列與其對(duì)應(yīng)的二叉樹的后序遍歷序列相同C．樹的后序遍歷序列與其對(duì)應(yīng)的二叉樹的先序遍歷序列相同D．樹的后序遍歷序列與其對(duì)應(yīng)的二叉樹的后序遍歷序列相同三、問答1．如圖6-23所示的兩棵樹是一樣的嗎？為什么？答：從圖6-23(a)知，該樹的根結(jié)點(diǎn)為A，下面有兩棵子樹，其中的一棵子樹是最小樹，只有根結(jié)點(diǎn)為B；另一棵子樹的根結(jié)點(diǎn)為C，下面又有一棵最小子樹，它的根結(jié)點(diǎn)為D。從圖6-23(b)知，該樹的根結(jié)點(diǎn)也是A，它的下面也有兩棵子樹，這兩棵子樹的構(gòu)成也與圖6-23(a)里的相同。因此如果把樹的子樹視為是無序的，那么該圖所展示的兩棵樹是一樣的，否則是不一樣的。圖6-23樹示例2．二叉樹與樹有什么不同？答：二叉樹是一種樹，但是一種特殊的樹。第一，二叉樹的每個(gè)結(jié)點(diǎn)至多可以有兩棵子樹，但樹的每個(gè)結(jié)點(diǎn)可以有多棵子樹；第二，二叉樹的子樹有左、右之分（即是有序的），但樹的子樹通常是不分順序的。3．為什么對(duì)于二叉樹有中序遍歷，而對(duì)一般樹卻沒有中序遍歷？答：二叉樹有中序遍歷，是因?yàn)槎鏄涞拿總€(gè)結(jié)點(diǎn)最多只有兩個(gè)子樹，且子樹有左、右之分，因此可以規(guī)定在訪問左子樹和右子樹的中間去訪問子樹的根結(jié)點(diǎn)。但對(duì)于一般的樹，其結(jié)點(diǎn)可以有任意數(shù)目的子樹，因此，無法規(guī)定怎樣的訪問順序才算是“中序”。所以，對(duì)一般的樹沒有中序遍歷。4．對(duì)于樹的各種遍歷，哪一種遍歷是（1）首先訪問樹的根結(jié)點(diǎn)？（2）位于最左邊的結(jié)點(diǎn)最先訪問？（3）根結(jié)點(diǎn)最后訪問？（4）最右邊的結(jié)點(diǎn)最后訪問？答：（1）層次遍歷和先序遍歷總是首先訪問樹的根結(jié)點(diǎn)；（2）后序遍歷總是最先訪問位于樹最左邊的結(jié)點(diǎn)；（3）后序遍歷總是最后訪問樹的根結(jié)點(diǎn)；（4）前序遍歷總是最后訪問樹的最右邊的結(jié)點(diǎn)。5．一棵度為2的樹與一棵二叉樹有什么區(qū)別？答：從形狀上看，一棵度為2的樹與一棵二叉樹沒有什么區(qū)別。但度為2的樹結(jié)點(diǎn)的子樹一般是無序的，沒有左、右之分；而二叉樹結(jié)點(diǎn)的子樹是有序的，它們之間有左、右之分，不能隨意換位。四、應(yīng)用1．已知一棵樹的孩子鏈表表示法如圖6-24所示，試畫出該樹。圖6-24一棵樹的孩子鏈表表示法圖6-25樹示例答：該樹形狀如下圖所示。2．已知一棵樹如圖6-25所示。請(qǐng)畫出該樹的以下存儲(chǔ)結(jié)構(gòu)：（1）雙親表示法；（2）帶雙親的孩子鏈表表示法（我們介紹過雙親表示法和孩子鏈表表示法，沒有介紹過帶雙親的孩子鏈表表示法。望能夠把兩者結(jié)合起來）；（3）孩子/兄弟鏈表表示法。答：（1）雙親表示法如下圖(a)所示；（2）帶雙親的孩子鏈表表示法如圖下(b)所示；（3）孩子/兄弟鏈表表示法如下圖(c)所示。3．將圖6-26所示的二叉樹轉(zhuǎn)換成相應(yīng)的森林。圖6-26二叉樹示例圖6-27樹示例答：轉(zhuǎn)換成的森林如下圖所示。4．給出如圖6-27所示樹的先序遍歷序列和后序遍歷序列。答：該樹的先序遍歷序列為：A-B-E-F-K-L-M-C-G-D-H-I-J；該樹的后序遍歷序列是：E-K-M-L-F-B-G-C-H-I-J-D-A。5．將圖6-28所示的森林轉(zhuǎn)換成對(duì)應(yīng)的二叉樹。圖6-28森林示例圖6-29樹示例答：對(duì)應(yīng)的二叉樹如下圖所示。6．將圖6-29所示的樹轉(zhuǎn)換成相對(duì)應(yīng)的二叉樹。答：對(duì)應(yīng)的二叉樹如下圖所示第7章習(xí)題解答一、填空1．由4個(gè)頂點(diǎn)組成的一個(gè)連通圖，應(yīng)該有邊6條。2．在一個(gè)具有4個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)，，至少需要3條邊。3．在無向圖中，若頂點(diǎn)vi和vj之間有一條邊（vi，vj）存在，那么則稱頂點(diǎn)vi和vj互為鄰接點(diǎn)。4．圖中頂點(diǎn)vi的“度”，是指與它相鄰接的頂點(diǎn)的個(gè)數(shù)，并記為D(vi)。5．在有向圖中，把從頂點(diǎn)vi到頂點(diǎn)vj的弧記為<vi，vj>，而把從頂點(diǎn)vj到頂點(diǎn)vi的弧記為<vj，vi>，這是兩條不同的弧。6．對(duì)于一個(gè)無向圖，其鄰接矩陣中第i行（或第i列）里非零或非∞元素的個(gè)數(shù)，正好是第i個(gè)頂點(diǎn)vi的度。7．對(duì)于一個(gè)有向圖，其鄰接矩陣中第i行里非零或非∞元素的個(gè)數(shù)，正好是第i個(gè)頂點(diǎn)vi的出度；其鄰接矩陣中第i列里非零或非∞元素的個(gè)數(shù)，正好是第i個(gè)頂點(diǎn)vi的入度。8．在無向圖中，若從頂點(diǎn)vi到頂點(diǎn)vj之間有路徑存在，則稱vi與vj是連通的。9．如果無向圖G中任意一對(duì)頂點(diǎn)之間都是連通的，則稱該圖G為連通圖，否則是非連通圖。10．在無向圖G中，盡可能多地從集合V及E里收集頂點(diǎn)和邊，使它們成為該圖的一個(gè)極大的連通子圖，這個(gè)子圖就被稱為是無向圖G的一個(gè)連通分量。11．包含無向連通圖G的所有n個(gè)頂點(diǎn)在內(nèi)的極小連通子圖，是這個(gè)圖的生成樹。12．只要在無向連通圖的生成樹里減少任意一條邊，它就成為了一個(gè)非連通圖。13．對(duì)圖的廣度優(yōu)先搜索，類似于對(duì)樹進(jìn)行按層次遍歷。14．拓?fù)渑判蚴堑玫紸OV網(wǎng)的一個(gè)線性序列，使得網(wǎng)中所有頂點(diǎn)間的優(yōu)先關(guān)系在序列中得以體現(xiàn)。15．已知無向圖的頂點(diǎn)個(gè)數(shù)為n，邊數(shù)為e。那么，在其鄰接表表示法中，鏈表結(jié)點(diǎn)數(shù)與單鏈表表頭結(jié)點(diǎn)數(shù)之和是n+2e。二、選擇1．在一個(gè)有n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)，至少需要C條邊。A．nB．n+1C．n-1D．n/22．對(duì)于一個(gè)無向完全圖來說，它的每個(gè)不同頂點(diǎn)對(duì)之間，都存在有一條邊。因此，有n個(gè)頂點(diǎn)的無向完全圖包含有C條邊。A．n(n-1)B．n(n+1)C．n(n-1)/2D．n(n+1)/23．對(duì)于一個(gè)有向完全圖來說，它的每個(gè)不同頂點(diǎn)對(duì)之間，都存在有兩條弧。因此，有n個(gè)頂點(diǎn)的有向完全圖包含有A條邊。A．n(n-1)B．n(n+1)C．n(n-1)/2D．n(n+1)/24．在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和，是其所有邊數(shù)之和的C倍。A．1/2B．1C．2D．45．在一個(gè)有向圖中，所有頂點(diǎn)的入度之和B所有頂點(diǎn)的出度之和。A．二分之一于B．等于C．兩倍于D．四倍于6．一個(gè)無向連通網(wǎng)圖的最小生成樹A。A．有一棵或多棵B．只有一棵C．一定有多棵D．可能不存在7．一個(gè)無向圖有n個(gè)頂點(diǎn)，那么該圖擁有的邊數(shù)至少是D。A．2nB．nC．n/2D．08．一個(gè)有n個(gè)頂點(diǎn)的無向連通網(wǎng)圖，其生成樹里含有C條邊。A．4n-1B．2n-1C．n-1D．n/29．下面關(guān)于圖的存儲(chǔ)的敘述中，正確的是C。A．用鄰接表存儲(chǔ)圖，所用存儲(chǔ)空間大小只與圖中頂點(diǎn)個(gè)數(shù)有關(guān)，與邊數(shù)無關(guān)B．用鄰接表存儲(chǔ)圖，所用存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，與頂點(diǎn)個(gè)數(shù)無關(guān)C．用鄰接矩陣存儲(chǔ)圖，所用存儲(chǔ)空間大小只與圖中頂點(diǎn)個(gè)數(shù)有關(guān)，與邊數(shù)無關(guān)D．用鄰接矩陣存儲(chǔ)圖，所用存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，與頂點(diǎn)個(gè)數(shù)無關(guān)10．對(duì)如圖7-21所示的無向圖實(shí)施深度優(yōu)先搜索遍歷，可能的遍歷序列是B。圖7-21無向圖示例三、問答1．試求圖7-22所示的無向連通網(wǎng)圖的MST。一個(gè)無向連通網(wǎng)圖的MST唯一嗎？圖7-22無向連通網(wǎng)圖示例圖7-23無向圖示例答：其MST如圖7-15(g)所示。如果使用邊（v4,v6）代替邊（v3,v6），就可以得到另一個(gè)MST。所以，MST不是唯一的。2．試述簡(jiǎn)單回路、回路兩者間的聯(lián)系與不同。答：簡(jiǎn)單回路的定義是“如果一條路徑的第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同，其他頂點(diǎn)不重復(fù)出現(xiàn)，那么這條路徑稱為簡(jiǎn)單回路”；回路的定義是“如果一條路徑的第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同，那么這條路徑稱為回路”。比較后可知，一條路徑是簡(jiǎn)單回路，那么它一定是回路，因?yàn)榛芈分灰舐窂降钠鹗柬旤c(diǎn)和終端頂點(diǎn)相同，簡(jiǎn)單路徑是滿足這一要求的；但一條路徑是回路，則不一定是簡(jiǎn)單回路，因?yàn)榛芈窌r(shí)并不去理會(huì)路徑中的其他頂點(diǎn)是否重復(fù)出現(xiàn)，可是簡(jiǎn)單路徑是不允許其他頂點(diǎn)重復(fù)出現(xiàn)的。3．有如圖7-23所示的一個(gè)無向圖，給出它的鄰接矩陣以及從頂點(diǎn)v1出發(fā)的深度優(yōu)先遍歷序列。答：它的鄰接矩陣如圖所示。從頂點(diǎn)v1出發(fā)的深度優(yōu)先遍歷序列為：v1->v2->v4->v5->v7->v6->v3注意，該序列是不唯一的。4．構(gòu)造最小生成樹的Prim算法與求單源最短路徑的Dijkstra算法十分相似，它們都把圖中的頂點(diǎn)分成U和V-U兩個(gè)部分，都是在V-U里挑選出一個(gè)頂點(diǎn)，并將它從V-U移到U中。那么，它們的主要區(qū)別是什么？答：這兩個(gè)算法的處理思路確實(shí)較為相似，主要區(qū)別在于：Prim算法是從V-U里挑選出下一個(gè)與MST中某個(gè)頂點(diǎn)相距最近的頂點(diǎn)，而Dijkstra算法是從V-U里挑選出下一個(gè)離源點(diǎn)最近的頂點(diǎn)。5．對(duì)有m個(gè)頂點(diǎn)的無向圖G，如何通過它的鄰接矩陣判定下列問題：（1）圖中有多少條邊？（2）任意兩個(gè)頂點(diǎn)i和j之間是否有邊相連？（3）任意一個(gè)頂點(diǎn)i的度是多少？答：（1）鄰接矩陣中非零元素個(gè)數(shù)的一半，是圖中邊的數(shù)目；（2）通過判斷鄰接矩陣中元素A{[i,j]和A[j,i]是否不為0，可知頂點(diǎn)i和j之間是否有邊相連；（3）第i行或第i列上非零元素的個(gè)數(shù)，就是頂點(diǎn)i的度。6．對(duì)圖7-24回答下列問題：（1）頂點(diǎn)集合V；（2）邊集合E；（3）每個(gè)頂點(diǎn)x的度D(x)；（4）一個(gè)長(zhǎng)度為5的路徑；（5）一個(gè)長(zhǎng)度為4的回路；（6）圖的一個(gè)生成樹；（7）鄰接矩陣；（8）鄰接表。圖7-24圖示例答：（1）頂點(diǎn)集合V={v1,v2,v3,v4,v5,v6}。（2）邊集合E={<v1,v2>,<v2,v3>,<v2,v4>,<v3,v4>,<v3,v5>,<v4,v5>,<v3,v6>,<v4,v6>}。（3）每個(gè)頂點(diǎn)的度：D(v1)=1，D(v2)=3，D(v3)=D(v4)=4，D(v5)=D(v6)=2。（4）一個(gè)長(zhǎng)度為5的路徑是：v1->v2->v3->v6->v4->v5。（5）一個(gè)長(zhǎng)度為4的回路是：v2->v3->v5->v4->v2。（6）如下圖(a)所示。（7）如下圖(b)所示。（8）如下圖(c)所示。問答5的（6）~（8）答案四、應(yīng)用1．利用Kruskal算法，求圖7-14(a)所給無向連通網(wǎng)圖的最小生成樹。答：初始時(shí)，所求MST里只有七個(gè)各自孤立的連通分量，如圖(a)所示。開始執(zhí)行Kruskal算法時(shí)，從圖的邊E里挑選邊（v6,v7），因?yàn)檫@兩個(gè)頂點(diǎn)分屬M(fèi)ST中的不同連通分量，且權(quán)值為最小。這樣，該邊把MST里的頂點(diǎn)v6和v7連接在了一起，如圖(b)所示。接著，從圖的邊E里挑選邊（v1,v3）、挑選邊（v1,v2）、挑選邊（v4,v6）挑選邊（v5,v7）挑選邊（v3,v6），最終得到如圖(g)所示的最小生成樹。2．利用Floyd算法，求圖7-25所示的有向網(wǎng)圖中各頂點(diǎn)對(duì)的最短路徑長(zhǎng)度。圖7-25有向網(wǎng)圖示例答：Floyd算法基于的鄰接矩陣，以及推演出的各個(gè)矩陣、最終結(jié)果如下所示。3．利用Dijkstra算法，求圖7-26所示的圖中頂點(diǎn)v1到其他各頂點(diǎn)間的最短路徑長(zhǎng)度。答：v1到v2的最短路徑長(zhǎng)度是4；v1到v3的最短路徑長(zhǎng)度是4；v1到v4的最短路徑長(zhǎng)度是1；v1到v5的最短路徑長(zhǎng)度是6；v1到v6的最短路徑長(zhǎng)度是3；v1到v7的最短路徑長(zhǎng)度是6；v1到v8的最短路徑長(zhǎng)度是7。如圖所示。圖7-26圖示例圖7-27AOV網(wǎng)4．寫出圖7-27所示的AOV網(wǎng)的拓?fù)渑判蛐蛄?。答：該網(wǎng)只有頂點(diǎn)v3的入度為0，所以只能從它開始進(jìn)行拓?fù)渑判?，其拓?fù)湫蛄袨椋簐3->v1->v4->v5->v2->v65．已知無向連通網(wǎng)的鄰接矩陣如下所示，試畫出該無向連通網(wǎng)以及所對(duì)應(yīng)的最小生成樹。答：無向連通網(wǎng)以及所對(duì)應(yīng)的最小生成樹如圖(a)、(b)所示。第8章習(xí)題解答一、填空1．記錄的集合是實(shí)施查找的數(shù)據(jù)基礎(chǔ)。在討論查找問題時(shí)，常把T稱為查找表。2．能夠唯一確定記錄的數(shù)據(jù)項(xiàng)，被稱為關(guān)鍵字。3．如果查找只是為了得知是否成功或獲取相應(yīng)的記錄信息，并不去改變查找表的內(nèi)容，那么這種查找稱為靜態(tài)查找；如果查找過程會(huì)伴隨著對(duì)數(shù)據(jù)元素的變更，那么這種查找稱為動(dòng)態(tài)查找。4．有序表和分塊有序表是一種靜態(tài)查找表；二叉查找樹是一種動(dòng)態(tài)查找表。5．在AVL樹的平衡調(diào)整中，稱離插入結(jié)點(diǎn)最近且其平衡因子絕對(duì)值大于1的那個(gè)結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹為“最小不平衡樹”。6．在散列查找中使用的函數(shù)，稱為“散列函數(shù)”。在散列法中的查找表，稱為散列表或哈希表。7．散列法中，如果兩個(gè)不同的關(guān)鍵字經(jīng)過散列函數(shù)的計(jì)算后，得到了相同的索引地址，那么這種現(xiàn)象被稱作“沖突”。8．散列法中，計(jì)算后得到相同索引地址的那些不同關(guān)鍵字，被稱作“同義詞”。二、選擇1．在對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須B。A．以順序方式存儲(chǔ)B．以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列C．以鏈?zhǔn)椒绞酱鎯?chǔ)D．以鏈?zhǔn)椒绞酱鎯?chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列2．采用順序查找法查找長(zhǎng)度為n的線性表時(shí)，其平均查找長(zhǎng)度為C。A．nB．n/2C．(n+1)/2D．(n-1)/23．有一個(gè)有序表：1，3，9，12，32，41，45，62，75，77，82，95，100采用折半查找法查找值為82的記錄時(shí)，要經(jīng)C次關(guān)鍵字比較后，查找成功。A．1B．2C．4D．84．設(shè)散列表長(zhǎng)m=14，散列函數(shù)h(key)=key%11。表中已有四個(gè)記錄，關(guān)鍵字分別為15、38、61、84，采用二次探測(cè)法解決沖突。那么關(guān)鍵字為49的記錄的散列地址為D。A．1B．3C．5D．95．在下列各種查找方法中，只有A查找法的平均查找長(zhǎng)度與表長(zhǎng)n無關(guān)。A．散列查找B．二叉查找樹C．折半查找D．分塊查找6．在開放地址法中，由于散列到同一個(gè)地址而引起的“堆積”現(xiàn)象，是由B產(chǎn)生的。A．同義詞之間發(fā)生沖突B．非同義詞之間發(fā)生沖突C．同義詞之間或非同義詞之間發(fā)生沖突D．散列表“溢出”7．在最壞的情況下，查找成功時(shí)二叉查找樹的平均查找長(zhǎng)度C。A．小于線性表的平均查找長(zhǎng)度B．大于線性表的平均查找長(zhǎng)度C．與線性表的平均查找長(zhǎng)度相同D．無法與線性表的平均查找長(zhǎng)度相比較8．在散列中采用線性探測(cè)法解決沖突時(shí)，產(chǎn)