數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題2013新版

數(shù)據(jù)結(jié)構(gòu)各章復(fù)習(xí)資料PAGE數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)參考題資料計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)2013.7第一章緒論一、選擇題:1、在數(shù)據(jù)結(jié)構(gòu)的討論中把數(shù)據(jù)結(jié)構(gòu)從邏輯上分為(C)。A、內(nèi)部結(jié)構(gòu)與外部結(jié)構(gòu)B、靜態(tài)結(jié)構(gòu)與動(dòng)態(tài)結(jié)構(gòu)C、線性結(jié)構(gòu)與非線性結(jié)構(gòu) D、緊湊結(jié)構(gòu)與非緊湊結(jié)構(gòu)2、下面程序段的時(shí)間復(fù)雜度為(C)。for(inti=0;i<m;i++)for(intj=0;j<n;j++)a[i][j]=i*j;A、O(m2)B、O(n2)C、O(m*n)D、O(m+n)3、執(zhí)行下面程序段時(shí)，執(zhí)行S語(yǔ)句的次數(shù)為(D)。for(inti=1;i<=n;i++)for(intj=1;j<=i;j++)S;A、n2B、n2/2C、n(n+1)D、n(n+1)/2４、某算法的時(shí)間代價(jià)為T(mén)（n）=100n+10nLog2n+n2+10，其時(shí)間復(fù)雜度為（C）。A、O（n）B、O(nlog2n)C、O(n2)D、O(1)二、填空題１、數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型ADT可用三元組表示（D，S，P），其中D是（數(shù)據(jù)對(duì)象），S是(關(guān)系集)，P是(操作集)。２、數(shù)據(jù)的基本單位是(數(shù)據(jù)元素),最小單位是(數(shù)據(jù)項(xiàng))。3、一個(gè)算法的時(shí)間復(fù)雜性通常用它的(T（n）=O(F(n)))形式表示，當(dāng)一個(gè)算法的時(shí)間復(fù)雜性與問(wèn)題的規(guī)模n大小無(wú)關(guān)時(shí)，則表示為(O(1))；成正比時(shí)，則表示為(O(n))；成對(duì)數(shù)關(guān)系時(shí)，則表示為(O(log2n))；成平方關(guān)系時(shí)，則表示為(O(n2))。4、我們常常稱數(shù)據(jù)的邏輯結(jié)構(gòu)為數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)的邏輯結(jié)構(gòu)有兩類：(線性結(jié)構(gòu))，(非線性結(jié)構(gòu))。5、一個(gè)算法應(yīng)該具有(有窮性)、(確定性)、(可行性)、(零個(gè)或多個(gè)輸入)、(一個(gè)或多個(gè)輸出)五個(gè)特征。6、數(shù)據(jù)結(jié)構(gòu)中的邏輯結(jié)構(gòu)具體分為四種分別是（線性結(jié)構(gòu)）（樹(shù)型結(jié)構(gòu)）（圖或網(wǎng)型結(jié)構(gòu)）（集合）。7、數(shù)據(jù)結(jié)構(gòu)中的存儲(chǔ)結(jié)構(gòu)具體分為二種分別是（順序存儲(chǔ)結(jié)構(gòu)）（鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）。三、簡(jiǎn)答題1、比較順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)？參考答案：1）順序表的特點(diǎn)是邏輯上相鄰的數(shù)據(jù)元素，物理存儲(chǔ)位置也相鄰，并且，順序表的存儲(chǔ)空間需要預(yù)先分配。它的優(yōu)點(diǎn)是：（1）方法簡(jiǎn)單，各種高級(jí)語(yǔ)言中都有數(shù)組，容易實(shí)現(xiàn)。（2）不用為表示節(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲(chǔ)開(kāi)銷。（3）順序表具有按元素序號(hào)隨機(jī)訪問(wèn)的特點(diǎn)。缺點(diǎn)：（1）在順序表中做插入、刪除操作時(shí)，平均移動(dòng)表中的一半元素，因此對(duì)n較大的順序表效率低。（2）需要預(yù)先分配足夠大的存儲(chǔ)空間，估計(jì)過(guò)大，可能會(huì)導(dǎo)致順序表后部大量閑置；預(yù)先分配過(guò)小，又會(huì)造成溢出。2）在鏈表中邏輯上相鄰的數(shù)據(jù)元素，物理存儲(chǔ)位置不一定相鄰，它使用指針實(shí)現(xiàn)元素之間的邏輯關(guān)系。并且，鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配的。鏈表的最大特點(diǎn)是：插入、刪除運(yùn)算方便。缺點(diǎn)：（1）要占用額外的存儲(chǔ)空間存儲(chǔ)元素之間的關(guān)系，存儲(chǔ)密度降低。存儲(chǔ)密度是指一個(gè)節(jié)點(diǎn)中數(shù)據(jù)元素所占的存儲(chǔ)單元和整個(gè)節(jié)點(diǎn)所占的存儲(chǔ)單元之比。（2）鏈表不是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)，不能隨機(jī)存取元素。3）順序表與鏈表的優(yōu)缺點(diǎn)切好相反，那么在實(shí)踐應(yīng)用中怎樣選取存儲(chǔ)結(jié)構(gòu)呢？通常有以下幾點(diǎn)考慮：（1）順序表的存儲(chǔ)空間是靜態(tài)分配的，在程序執(zhí)行之前必須明確規(guī)定它的存儲(chǔ)規(guī)模，也就是說(shuō)事先對(duì)“MaxSize”要有合適的設(shè)定，設(shè)定過(guò)大會(huì)造成存儲(chǔ)空間的浪費(fèi)，過(guò)小造成溢出。因此，當(dāng)對(duì)線性表的長(zhǎng)度或存儲(chǔ)規(guī)模難以估計(jì)時(shí)，不宜采用順序表。然而，鏈表的動(dòng)態(tài)分配則可以克服這個(gè)缺點(diǎn)。鏈表不需要預(yù)留存儲(chǔ)空間，也不需要知道表長(zhǎng)如何變化，只要內(nèi)存空間尚有空閑，就可以再程序運(yùn)行時(shí)隨時(shí)地動(dòng)態(tài)分配空間，不需要時(shí)還可以動(dòng)態(tài)回收。因此，當(dāng)線性表的長(zhǎng)度變化較大或者難以估計(jì)其存儲(chǔ)規(guī)模時(shí)，宜采用動(dòng)態(tài)鏈表作為存儲(chǔ)結(jié)構(gòu)。但在鏈表中，除數(shù)據(jù)域外海需要在每個(gè)節(jié)點(diǎn)上附加指針。如果節(jié)點(diǎn)的數(shù)據(jù)占據(jù)的空間小，則鏈表的結(jié)構(gòu)性開(kāi)銷就占去了整個(gè)存儲(chǔ)空間的大部分。當(dāng)順序表被填滿時(shí)，則沒(méi)有結(jié)構(gòu)開(kāi)銷。在這種情況下，順序表的空間效率更高。由于設(shè)置指針域額外地開(kāi)銷了一定的存儲(chǔ)空間，從存儲(chǔ)密度的角度來(lái)講，鏈表的存儲(chǔ)密度小于1.因此，當(dāng)線性表的長(zhǎng)度變化不大而且事先容易確定其大小時(shí)，為節(jié)省存儲(chǔ)空間，則采用順序表作為存儲(chǔ)結(jié)構(gòu)比較適宜。（2）基于運(yùn)算的考慮（時(shí)間）順序存儲(chǔ)是一種隨機(jī)存取的結(jié)構(gòu)，而鏈表則是一種順序存取結(jié)構(gòu)，因此它們對(duì)各種操作有完全不同的算法和時(shí)間復(fù)雜度。例如，要查找線性表中的第i個(gè)元素，對(duì)于順序表可以直接計(jì)算出a(i)的的地址，不用去查找，其時(shí)間復(fù)雜度為0(1).而鏈表必須從鏈表頭開(kāi)始，依次向后查找，平均需要0(n)的時(shí)間。所以，如果經(jīng)常做的運(yùn)算是按序號(hào)訪問(wèn)數(shù)據(jù)元素，顯然順表優(yōu)于鏈表。反之，在順序表中做插入，刪除時(shí)平均移動(dòng)表中一半的元素，當(dāng)數(shù)據(jù)元素的信息量較大而且表比較長(zhǎng)時(shí)，這一點(diǎn)是不應(yīng)忽視的；在鏈表中作插入、刪除，雖然要找插入位置，但操作是比較操作，從這個(gè)角度考慮顯然后者優(yōu)于前者。（3）基于環(huán)境的考慮（語(yǔ)言）順序表容易實(shí)現(xiàn)，任何高級(jí)語(yǔ)言中都有數(shù)組類型；鏈表的操作是基于指針的。相對(duì)來(lái)講前者簡(jiǎn)單些，也用戶考慮的一個(gè)因素。總之，兩種存儲(chǔ)結(jié)構(gòu)各有長(zhǎng)短，選擇哪一種由實(shí)際問(wèn)題中的主要因素決定。通常“較穩(wěn)定”的線性表，即主要操作是查找操作的線性表，適于選擇順序存儲(chǔ)；而頻繁做插入刪除運(yùn)算的（即動(dòng)態(tài)性比較強(qiáng)）的線性表適宜選擇鏈?zhǔn)酱鎯?chǔ)。2、評(píng)價(jià)一個(gè)算法的好壞的標(biāo)準(zhǔn)是什么？由于針對(duì)一個(gè)問(wèn)題可能會(huì)有不同的算法去解決，不同的算法思路不同，有的執(zhí)行速度很慢，效率低；有的執(zhí)行速度很快，效率自然會(huì)很高。這樣也就出現(xiàn)了算法的“好”與“壞”之分，如何衡量一個(gè)算法的好壞，通常要從以下幾個(gè)方面來(lái)分析。1）正確性算法能滿足具體問(wèn)題的需求，即對(duì)任何合法的輸入算法都會(huì)得出正確的結(jié)果。2）可讀性算法創(chuàng)建后由人來(lái)閱讀、理解、使用以及修改。所以可讀性的好壞直接影響到算法的好壞。如果一個(gè)算法涉及的想法很多，就會(huì)給閱讀的人造成困難，那么這個(gè)算法就不能得到更好的交流和推廣，更不便于對(duì)算法進(jìn)行修改、擴(kuò)展和維護(hù)。所以要提高算法的可讀性，就要做到簡(jiǎn)明易懂。3）健壯性一個(gè)程序完成后，運(yùn)行該程序的用戶對(duì)程序的理解各有不同，并不能保證每一個(gè)人都能按照要求進(jìn)行輸入，健壯性就是指對(duì)非法輸入的抵抗能力，當(dāng)輸入的數(shù)據(jù)非法時(shí)，算法能識(shí)別并做出處理，而不會(huì)因?yàn)檩斎氲腻e(cuò)誤產(chǎn)生錯(cuò)誤動(dòng)作或造成癱瘓。4）時(shí)間復(fù)雜度與空間復(fù)雜度時(shí)間復(fù)雜度簡(jiǎn)單地說(shuō)就是算法運(yùn)行所需要的時(shí)間。不同的算法具有不同的時(shí)間復(fù)雜度，當(dāng)一個(gè)程序較小時(shí)感覺(jué)不到時(shí)間復(fù)雜度的重要性，當(dāng)一個(gè)程序特別大時(shí)便會(huì)察覺(jué)到時(shí)間復(fù)雜度的重要性。所以如何寫(xiě)出更高速的算法一直是算法不斷改進(jìn)的目標(biāo)。空間復(fù)雜度是指算法運(yùn)行所需的存儲(chǔ)空間，隨著計(jì)算機(jī)硬件的發(fā)展，空間復(fù)雜度已經(jīng)顯得不再那么重要。第二章線性表一、選擇題1．線性表是(A)。A、一個(gè)有限序列，可以為空；B、一個(gè)有限序列，不能為空；C、一個(gè)無(wú)限序列，可以為空；D、一個(gè)無(wú)序序列，不能為空。2．對(duì)順序存儲(chǔ)的線性表，設(shè)其長(zhǎng)度為n，在任何位置上插入或刪除操作都是等概率的。插入一個(gè)元素時(shí)平均要移動(dòng)表中的（A）個(gè)元素。A、n/2B、（n+1）/2C、（n-1）/2D、n3．線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址(D)。A、必須是連續(xù)的B、部分地址必須是連續(xù)的C、一定是不連續(xù)的D、連續(xù)與否均可以4．用鏈表表示線性表的優(yōu)點(diǎn)是（C）。A、便于隨機(jī)存取B、花費(fèi)的存儲(chǔ)空間較順序存儲(chǔ)少C、便于插入和刪除D、數(shù)據(jù)元素的物理順序與邏輯順序相同5、某鏈表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除最后一個(gè)元素，則采用(D)存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A、單鏈表B、雙鏈表C、單循環(huán)鏈表D、帶頭結(jié)點(diǎn)的雙循環(huán)鏈表6、循環(huán)鏈表的主要優(yōu)點(diǎn)是(D)。A、不在需要頭指針了B、已知某個(gè)結(jié)點(diǎn)的位置后，能夠容易找到他的直接前趨C、在進(jìn)行插入、刪除運(yùn)算時(shí)，能更好的保證鏈表不斷開(kāi)D、從表中的任意結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表7、下面關(guān)于線性表的敘述錯(cuò)誤的是(B)。A、線性表采用順序存儲(chǔ)，必須占用一片地址連續(xù)的單元；B、線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作；C、線性表采用鏈?zhǔn)酱鎯?chǔ)，不必占用一片地址連續(xù)的單元；D、線性表采用鏈?zhǔn)酱鎯?chǔ)，便于進(jìn)行插入和刪除操作；8、單鏈表中，增加一個(gè)頭結(jié)點(diǎn)的目的是為了（C）。A、使單鏈表至少有一個(gè)結(jié)點(diǎn)B、標(biāo)識(shí)表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置C、方便運(yùn)算的實(shí)現(xiàn)D、說(shuō)明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)9、若某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用（D）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A、單鏈表B、僅有頭指針的單循環(huán)鏈表C、雙鏈表D、僅有尾指針的單循環(huán)鏈表10、若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前趨元素，則采用（B）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A、單鏈表B、順序表C、雙鏈表D、單循環(huán)鏈表11、鏈表不具有的特點(diǎn)是（A）。Ａ、可隨機(jī)訪問(wèn)任一元素Ｂ、插入刪除不需要移動(dòng)元素Ｃ、不必事先估計(jì)存儲(chǔ)空間Ｄ、所需空間與線性表長(zhǎng)度成正比12、在一個(gè)有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜性為(B)。A、O(1)

B、O(n)C、O(n2)D、O(log2n)13、在一個(gè)單鏈表HL中，若要向表頭插入一個(gè)自由指針p指向的結(jié)點(diǎn)，則執(zhí)行（D）。A、HL=p;p->next=HL;B、p->next=HL;HL=p;C、p->next=HL;p=HL;D、p->next=HL->next;HL->next=p;14、在一個(gè)單鏈表HL中，若要在指針q所指結(jié)點(diǎn)的后面插入一個(gè)自由指針p所指向的結(jié)點(diǎn)，則執(zhí)行（D）。A、q->next=p->next;p->next=q;B、p->next=q->next;q=p;C、q->next=p->next;p->next=pD、p->next=q->next;q->next=p;15、在一個(gè)單鏈表HL中，若要?jiǎng)h除由指針q所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行（D）。A、p=q->next;p->next=q->next;B、p=q->next;q->next=p;C、p=q->next;p->next=q;D、q->next=q->next->next;16、給定有n個(gè)元素的向量，建立一個(gè)有序的單鏈表的時(shí)間復(fù)雜度為（C）。A、O（1）B、O（n）C、O(n2)D、O(nlog2n)17、不帶頭結(jié)點(diǎn)的單鏈表first為空的判定條件是（A）。A、first==NULLB、first->next==NULLC、first->next==firstD、first!=NULL18、在非空的循環(huán)雙鏈表中q所指的結(jié)點(diǎn)前插入一個(gè)由p所指結(jié)點(diǎn)的過(guò)程依次為：p->next=q;p->prior=q->prior;q->prior=p;和（C）。A、q->next=pＢ、q->prior->next=pＣ、p->prior->next=pＤ、p->next->prior=p19、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)相比優(yōu)點(diǎn)是(D)。A、所有的操作算法實(shí)現(xiàn)簡(jiǎn)單B、便于隨機(jī)存儲(chǔ)C、不便于插入與刪除D、便于利用零散的存儲(chǔ)空間20、在雙向鏈表存儲(chǔ)結(jié)構(gòu)中,刪除P所指向的結(jié)點(diǎn)時(shí)須修改指針(A)。A、P->next->prior=P->priorP->prior->next=P->nextB、P->next=P->next->nextP->next->prior=PC、P->prior->next=PP->prior=P->prior->priorD、P->prior=P->next->nextP->next=P->prior->prior21、向一個(gè)有127個(gè)元素原順序表中插入一個(gè)新元素并保存原來(lái)順序不變，平均要移動(dòng)（B）個(gè)元素。A、8B、63.5C、63D、722、在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)的線性表中，向第i個(gè)元素(1≤i≤n+1)之前插入一個(gè)新元素時(shí)，需要從年向前依次移（B）個(gè)元素。A、n-iB、n-i+1C、n-i-1D、i二、填空題1、帶頭結(jié)點(diǎn)的單鏈表H為空的條件是(H->next==NULL)。2、非空單循環(huán)鏈表L中*p是尾結(jié)點(diǎn)的條件是(p->next==L)。3、在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)由指針f所指結(jié)點(diǎn)，應(yīng)執(zhí)行s->next=(p->next);和p->next=(f)的操作。4、在一個(gè)單鏈表中p所指結(jié)點(diǎn)之前插入一個(gè)由指針s所指結(jié)點(diǎn)，可執(zhí)行以下操作：s->next=(p->next);p->next=s;t=p->data;p->data=(s->dada);s->data=(t);5．在順序表中做插入操作時(shí)首先檢查(插入位置是否合理)。6、順序表、鏈表分別通過(guò)(存儲(chǔ)的相對(duì)位置)、(指針)體現(xiàn)元素的邏輯關(guān)系。7、線性鏈表中指針的作用是(表示邏輯關(guān)系)。8、在順序表中，插入或者刪除一個(gè)元素，需要平均移動(dòng)(一半)個(gè)元素，具體移動(dòng)的元素個(gè)數(shù)與(插入與刪除的位置有關(guān))有關(guān)。9、順序表中邏輯上相鄰的元素的物理位置(一定)緊鄰。單鏈表中邏輯上相鄰的元素的物理位置(不一定)緊鄰。10、在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由(前趨結(jié)點(diǎn)的指針域)指示。11、有一個(gè)單鏈表（不同結(jié)點(diǎn)的data域可能相等），其頭指針為head,編寫(xiě)一算法計(jì)算數(shù)據(jù)域?yàn)閤的結(jié)點(diǎn)的個(gè)數(shù)，請(qǐng)?zhí)羁?。intcount(LinkListhead,ElemTypex){Node*p;intn=0;(p=head->next);While(p!=NULL){if((p->data==x))n++;(p=p->next);}returnn;}12、單鏈表的逆置，請(qǐng)?zhí)羁誺oidinsert(LikListL){Node*p,*q,*r;p=head;(q=p->next或q=head->next);while(q!=NULL){r=q->next;(q->next=p);p=q;q=r;}head->next=NULL;head=p;}三、判斷題1、雙循環(huán)鏈表中，任一結(jié)點(diǎn)的后繼指針均指向其邏輯后繼。(F)2、線性表的邏輯順序與存儲(chǔ)順序總是一致的。(F)3、順序存儲(chǔ)的線性表可以按序號(hào)隨機(jī)存取。(T)4、順序表的插入和刪除操作不需要付出很大的時(shí)間代價(jià)，因?yàn)槊看尾僮髌骄挥薪话氲脑匦枰苿?dòng)。(F)5、線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性，因此是屬于同一數(shù)據(jù)對(duì)象。(T)6、在線性表的順序存儲(chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上并不一定緊鄰。(F)7、在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰。(T)8、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。(F)9、在線性表的順序存儲(chǔ)結(jié)構(gòu)中，插入和刪除時(shí)，移動(dòng)元素的個(gè)數(shù)與該元素的位置有關(guān)。(T)10、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一組任意的存儲(chǔ)單元來(lái)存儲(chǔ)線性表中數(shù)據(jù)元素的。(T)11、在單鏈表中，要取得某個(gè)元素，只要知道該元素的指針即可，因此，單鏈表是隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。(F)四、操作題1、下面算法調(diào)用方式為unknown（rear）；說(shuō)明該算法的功能，若輸入數(shù)據(jù)為ABCDE回車，畫(huà)出該算法所得到的存儲(chǔ)結(jié)構(gòu)。voidunknown(LinkList&rear){LinkListhead，s；DataTypech；rear=head=(ListNode*)malloc(sizeof(ListNode))；head->next=head；printf("輸入數(shù)據(jù)以回車鍵結(jié)束！\n")；while((ch=getchar())!='\n'){s=(LNode*)malloc(sizeof(LNode))；s->data=ch；s->next=rear->next；rear->next=s；rear=rear->next；}rear->next=head->next；free（head）；}EDCBA參考答案：EDCBArear2、下面算法調(diào)用方式為Unknown（root）；說(shuō)明該算法的功能，若輸入數(shù)據(jù)為AB#CD##EF####回車，畫(huà)出該算法所得到的存儲(chǔ)結(jié)構(gòu)。voidUnknown(BiTree&T){charch；if（（ch=getchar（））=='#'）T=NULL；else{T=(BiTree)malloc(sizeof(BiTNode))；T->data=ch；Unknown(T->lchild)；Unknown(T->rchild)；}}參考答案:^F^E^^D^C^BA^root^F^E^^D^C^BA^3、已知線性鏈表元素為字符（‘A’，‘B’，‘C’，‘D’，‘E’，‘F’），說(shuō)明下面算法的功能，并畫(huà)出該算法處理后所得到的存儲(chǔ)結(jié)構(gòu)。voidUnknown(LinkList&head)//head為鏈表的表頭指針{LinkListp，s；p=head->next；while(p->next){s=p->next；if（s->data%2==1）p=p->next；else{p->next=s->next;free（s）；}}//endofwhile}參考答案:將單鏈表中ASCII碼為偶數(shù)的結(jié)點(diǎn)刪除。4、設(shè)單鏈表的結(jié)點(diǎn)的結(jié)構(gòu)為L(zhǎng)istNode=(data,link)，閱讀下面的函數(shù)，指出它所實(shí)現(xiàn)的功能是什么。Intunknown(ListNode*Ha){Intn=0;ListNode*p=Ha->link;While(p){n++;p=p->next;}Return(n);}參考答案:計(jì)算單鏈表的長(zhǎng)度或計(jì)算單鏈表的結(jié)點(diǎn)的個(gè)數(shù)。5、假定p1和p2是兩個(gè)單鏈表的表頭指針，用來(lái)表示兩個(gè)集合，單鍵表中的結(jié)點(diǎn)包括值域data和指向后繼的結(jié)點(diǎn)的指針域link，試根據(jù)下面的算法指出算法的功能。intSS(ListNode*p1,ListNode*p2){ListNoder;while(p2!=NULL){r=p1;while(r!=NULL){if(p2->data==r->data)break;r=r->link;}if(r==NULL)return0;P2=p2->link;}return1;}參考答案:判斷P2單鏈表所代表的集合是否為P1單鏈表所代表的集合的子集，若是則返回1，否則返回0。五、算法題１、已知兩個(gè)單向鏈表A=(a，b，．．．．．．，c)；B=(d，e，．．．．．．，f)，設(shè)計(jì)算法voidMergeList（LinkList&A，LinkListB），實(shí)現(xiàn)將兩個(gè)鏈表合并為一個(gè)單向鏈表A=(d，e，．．．．．，f，c，．．．．．，b，a)，其中A，B為兩個(gè)鏈表的表頭指針，小寫(xiě)字母為表中元素。voidmerger(LinkList*A,LinkListB){}參考答案:voidMergrList(LIstList&A,LinkListB){for(R=B;R->next;R=R->next);P=A->nextwhile(P){S=P;P=P->next;S->next=R->next;R->next=S;}A=B;}２、假定在一個(gè)帶頭結(jié)點(diǎn)的單鏈表L中所有結(jié)點(diǎn)的值按遞增順序排列，試寫(xiě)下面的函數(shù)，功能是刪除表L跌所有的值大于等于min，同時(shí)小于等于max的結(jié)點(diǎn)。單鏈表的結(jié)構(gòu)定義如下：voidrangeDelete(ListNode*L,ElemTypemin,ElemTypemax){}參考答案：voidrangeDelete(ListNode*L,ElemTypemin,ElemTypemax){listNode*q=L,*p=L->next;while(p!=NULL){if(p->data>=min&&p->data<=max){q->next=p->next;free(p);p=q->next;}else{q=p;p=p->next;}}}3、線性順序表及鏈表就地逆置算法.intrevSqList(SqList*L){}intrevLinkList(LinkListL){}參考答案:intrevSqList(SqList*L){inti;ElemTypetemp;for(i=0;i<L->length/2;i++){temp=L->elem[i];L->elem[i]=L->elem[L->length-1-i];L->elem[L->length-1-i]=temp;}returnOK;}intrevLinkList(LinkListL){LinkListP,Q;P=L->next;if(L->next&&P->next){Q=P->next; P->next=NULL; while(Q) {P=Q; Q=Q->next; P->next=L->next; L->next=P;} }returnOK;}4、設(shè)A和B是兩個(gè)單鏈表，其表中元素遞增有序。試寫(xiě)一算法將A和B歸并成一個(gè)按元素值遞增有序的單鏈表C，并要求輔助空間為O(1)。LinkListMergeList_L(LinkListLa,LinkListLb){}參考答案:LinkListMergeList_L(LinkListLa,LinkListLb){LinkListLc,pa,pb,pc;pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else {pc->next=pb;pc=pb;pb=pb->next;}}pc->next=pa?pa:pb;free(Lb);returnLa;}5、已知一個(gè)的鏈表A，表中元素為整數(shù)，設(shè)計(jì)算法把表中的所有的負(fù)整數(shù)排列在所有非負(fù)整數(shù)之后。voidDivide（LinkList*A）{}參考答案:voidDivide（LinkList*A）{P=A->next;q=A;while(p){if(p->data>=0){q->next=p->next;p->next=A->next;A->next=p;P=q->next;}else{q=p;p=p->next;}}}第三章棧與隊(duì)列一、選擇題1、一個(gè)棧的輸入序列為1，2，3，4，下面哪一個(gè)序列不可能是這個(gè)棧的輸出序列(C)。A、1，3，2，4B、2，3，4，1C、4，3，1，2D、3，4，2，12、將一個(gè)遞歸算法改為對(duì)應(yīng)的非遞歸算法時(shí)，通常需要使用（A）。A、棧 B、隊(duì)列 C、循環(huán)隊(duì)列 D、優(yōu)先隊(duì)列3、若用數(shù)組S[1..n]作為兩個(gè)棧S1和S2的共同存儲(chǔ)結(jié)構(gòu)，對(duì)任何一個(gè)棧，只有當(dāng)S全滿時(shí)才不能作入棧操作。為這兩個(gè)棧分配空間的最佳方案是（C）。A、S1的棧底位置為0，S2的棧底位置為n+1B、S1的棧底位置為0，S2的棧底位置為n/2C、S1的棧底位置為1，S2的棧底位置為nD、S1的棧底位置為1，S2的棧底位置為n/24、在一個(gè)具有n個(gè)單元的順序棧中，假設(shè)棧底是存儲(chǔ)地址的低端，現(xiàn)在我們以top作為棧頂指針，則作退棧操作時(shí)，top的變化是(A)。A、top=top-1B、top=top+1C、top不變

D、top不確定5、鏈棧和順序棧相比較，有一個(gè)明顯的特點(diǎn)是(A)。A、鏈棧通常不會(huì)出現(xiàn)棧滿的情況B、鏈棧通常不會(huì)出現(xiàn)?？盏那闆rC、鏈棧的插入操作更加方便D、鏈棧的刪除操作更加方便。6、在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)首和隊(duì)尾指針，刪除一個(gè)結(jié)點(diǎn)的運(yùn)算是(C)。A、r=f—>nextB、r=r—>nextC、f=f—>next

D、f=r—>next7、向一個(gè)棧頂指針為top的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，其操作步驟是(B)。A、top—>next=sB、s—>next=top;top=s;C、s—>next=top—>next;top—>next=s;D、s—>next=top;top=top—>next8、棧的插入與刪除操作在（A）進(jìn)行。A、棧頂B、棧底C、任意位置D、指定位置9、當(dāng)利用大小為N的數(shù)組順序存儲(chǔ)一個(gè)隊(duì)列時(shí)，該隊(duì)列的最大長(zhǎng)度為（B）。A、N-2B、N-1C、ND、N+110、假定一個(gè)順序隊(duì)列的隊(duì)首和隊(duì)尾指針?lè)謩e為f和r，則判斷隊(duì)空指針的條件為（D）。A、f+1==rB、r+1==fC、f==0D、f==r11、在系統(tǒng)實(shí)現(xiàn)遞歸調(diào)用時(shí)需利用遞歸工作記錄保存（C），當(dāng)遞歸調(diào)用結(jié)束時(shí)通過(guò)它將控制轉(zhuǎn)到上層調(diào)用程序。A、調(diào)用地址B、遞歸入口C、返回地址D、遞歸出口12、設(shè)棧的輸入序列是1,2,3,4……n若輸出序列的第一個(gè)元素是n,則第i個(gè)輸出元素(B)。A、不確定B、n-i+1C、iD、n-i二、填空題1、已知順序存儲(chǔ)的循環(huán)隊(duì)列中，front，rear分別為隊(duì)頭、隊(duì)尾指針，MAX為隊(duì)列中存儲(chǔ)單元的最大個(gè)數(shù)，若當(dāng)隊(duì)列中僅有一個(gè)空閑單元時(shí)視為隊(duì)滿，則隊(duì)滿條件為((rear+1)%MAX==front)；一般情況下，隊(duì)列中元素個(gè)數(shù)可表示為((rear-front+MAX)%MAX)。2、已知元素入棧先后為ABCDE，若C為第一個(gè)出棧元素，則下一個(gè)出棧的元素可能是(B、D、E)。3、已知僅設(shè)尾指針的單循環(huán)鏈表rear（指針域?yàn)閚ext）表示隊(duì)列，鏈表前端為隊(duì)頭，則結(jié)點(diǎn)*s入隊(duì)的語(yǔ)句依次為(s->next=rear->next)；(rear->next=s)；rear=rear->next；4、已知僅設(shè)尾指針rear的無(wú)頭結(jié)點(diǎn)的單循環(huán)鏈表（指針域?yàn)閚ext）表示棧，鏈表前端為棧頂，則結(jié)點(diǎn)*new進(jìn)棧的語(yǔ)句依次為(new->next=rear->next)；(rear->next=new)；(rear=new);5、在對(duì)棧的操作中，其插入和刪除都是在棧的(同一端)進(jìn)行的，所以導(dǎo)致后進(jìn)棧的元素必定先被刪除，也就是說(shuō)，棧的修改是按照(后進(jìn)先出)的原則進(jìn)行的，所以棧又稱為(LIFO)表。6、在隊(duì)列的操作中，其插入和刪除工作是在表的兩端進(jìn)行的，它允許在表的一端進(jìn)行插入，一端進(jìn)行刪除，則允許插入的一端稱為(隊(duì)尾)，允許刪除的一端稱為(隊(duì)首)，先進(jìn)入隊(duì)列的成員必定先離開(kāi)隊(duì)列，所以隊(duì)列又稱為(FIFO)表。7、向一個(gè)棧頂找針為HS的鏈棧中插入一個(gè)S所指的結(jié)點(diǎn)時(shí)，則執(zhí)行(S->next=HS;HS=S；)。8、在順序隊(duì)列中，應(yīng)該有隊(duì)頭和隊(duì)尾兩個(gè)指針來(lái)指示，隊(duì)頭指針和隊(duì)尾指針的初值在隊(duì)列的初始化時(shí)均應(yīng)該設(shè)置為(0)，當(dāng)對(duì)隊(duì)列進(jìn)行插入和刪除的操作后，如果頭指針和尾指針相等時(shí)，隊(duì)列為(空)。9、向棧中壓入元素的操作是(壓棧)。對(duì)棧進(jìn)行出棧時(shí)的操作是(出棧)。10、在具有n個(gè)存儲(chǔ)單元的隊(duì)列中，隊(duì)滿時(shí)隊(duì)中共有(n-1)個(gè)元素。11、假設(shè)有一個(gè)順序棧A，其中元素a1,a2,a3,a4,a5,a6依次進(jìn)棧，如果已知六個(gè)元素出棧的順序是a2,a3,a4,a6,a5,a1,則此棧容量至少應(yīng)該為(3)。12、線性表、棧和隊(duì)列都是(線性結(jié)構(gòu))結(jié)構(gòu)，可以在線性表的(任意)位置上插入和刪除。13、判斷單鏈表是否對(duì)稱，對(duì)稱返回1，否則返回0，請(qǐng)?zhí)羁?。intxyz(LinkListL){Node*p,*q;intn1,n,i,x;Stacks;P=L->next;q=p;n=0;while(q!=NULL){n++;q=q->next;}n1=(n/2);for(i=1;i<=n1;i++){push(s,p->data);(p=p->next);}if((n%2!=0))p=p->next;while(p!=NULL){pop(s,x);if(p->data!=x)break;(p=p->next);}if(p==NULL或!p)return1;elsereturn0;}三、判斷題1、棧與隊(duì)列都是限制存取點(diǎn)的表，只是它們的存取特征不一樣。(T)2、在鏈隊(duì)列中，即使不設(shè)置尾指針也能進(jìn)行入隊(duì)操作。(T)3、遞歸調(diào)用算法與相同的功能的非遞歸算法相比，主要問(wèn)題在于重復(fù)計(jì)算太多，而且本身需要分配額外的空間和傳遞數(shù)據(jù)和控制，所以時(shí)間與空間開(kāi)銷通常都比較大。(T)4、鏈?zhǔn)綏Ｅc順序棧的相比，一個(gè)明顯的優(yōu)點(diǎn)是通常不會(huì)出現(xiàn)棧滿的情況。(T)四、操作題1、寫(xiě)出下列程序的運(yùn)行結(jié)果。main(){StackS;charx,y;S.InitStack();X=’c’;y=’k’;S.Push(x);S.Push(‘a(chǎn)’);S.Push(y);S.Pop(S,x);S.Push(‘t’);S.Push(‘s’);while(!S.IsEmpty()){S.Pop(S,x);printf(“%c”,x);}printf(“%c”,y);}參考答案：stack2、請(qǐng)寫(xiě)出下列算法的功能。Voidunknown(Queue&Q){StackS;intd;S.InitStack();while(!Q.IsEmpty()){Q.DeQueue(d);S.Push(d);}while(!S.IsEmpty()){S.Pop(d);Q.EnQueue(d);}}參考答案：利用棧，將隊(duì)列中的元素逆置。五、算法題1、請(qǐng)分別寫(xiě)出在循環(huán)隊(duì)列上進(jìn)行插入與刪除操作的算法。循環(huán)隊(duì)列的結(jié)構(gòu)定義如下：StructCyclicQueue{ElemTypeelem[M]//M為已定義過(guò)的整型常量，表示隊(duì)列的長(zhǎng)度Intrear,front;//rear指向隊(duì)尾元素的后一個(gè)位置，front指向隊(duì)頭元素Inttag;//當(dāng)front=rear且tag=0時(shí)，隊(duì)列空。當(dāng)front=rear且tag=1，隊(duì)列滿。};BoolEnCQueue(CyclicQueue*Q,ElemTypex){}BoolDelCQueue(CyclicQueue*Q,ElemTypex){}參考答案：BoolEnCQueue(CyclicQueue*Q,ElemTypex){if(Q->rear==Q->front&&Q->tag==1)returnfalse;Q->elem[Q->rear]=x;Q->rear=(Q->reat+1)%M;if(Q->rear==Q.front)Q.tag=1;Returntrue;}BoolDelCQueue(CyclicQueue*Q,ElemTypex){if(Q->front==Q->rear&&Q->tag==0)returnfalse;x=Q->elem[Q->front];Q->front=(Q->front+1)%M;if(Q->front==Q->rear)Q.tag=0;returntrue;}假設(shè)稱正讀和反讀都相同的字符序列為“回文”，例如，“abcddcba”、“qwerewq”是回文，“ashgash”不是回文。是寫(xiě)一個(gè)算法判斷讀入的一個(gè)以‘@’為結(jié)束符的字符序列是否為回文。參考答案：intIshuiwen(char*s){SqStackT;inti,l;charc;InitStack(T);l=(int)strlen(s);for(i=0;i<l/2;i++)Push(T,s[i]);while(!StackEmpty(T)){Pop(T,&c);if(c!=s[l-i])returnERROR;i--;}returnOK;}第五章數(shù)組與廣義表一、選擇題1、設(shè)一個(gè)廣義表的A=（a），其表尾為（C）。A、aB、(())C、()D、(a)2、設(shè)有一個(gè)N*N的對(duì)稱矩陣A，將其下三角部分存入一個(gè)一維數(shù)組B中，A[0][0]存入B[0]中，那么第i行的對(duì)角元素A[i][i]存入于B中的（）處。A、（i+3）*i/2B、(i+1)*i/2C、(2N-i+1)*i/2D、(2N-i-1)*i/23、廣義表((A,B,E,F,G))的表尾是(B)。A、(B,E,F,G)B、()C、（A，B，E，F(xiàn)，G)D、不存在4、廣義表（（()，(））,(a,b,c),(e,d)）的表頭是(C)，表尾是(D)。A、((e,d))B、(())C、((),())D、（（a,b,c）,(e,d)）5、對(duì)廣義表Ａ＝((a),(b))進(jìn)行下面的操作head(head(Ａ)后的結(jié)果是(A)。A、aB、(a)C、()D、不確定6、廣義表(A,B,E,F,G)的表尾是(A)。A、(B,E,F,G)B、()C、（A，B，E，F(xiàn)，G)D、（G）7、設(shè)有一個(gè)二維數(shù)A[m][n],假設(shè)A[0][0]存放位置在644(10),A[2][2]存放位置在676(10),每個(gè)元素占一個(gè)空間，則A[4][5]在（C）位置，(10)表明用10進(jìn)數(shù)表示。A、692(10)B、626(10)C、709(10)D、724(10)8.二維數(shù)組M的成員是6個(gè)字符（每個(gè)字符占一個(gè)存儲(chǔ)單元）組成的串，行下標(biāo)i的范圍從0到8，列下標(biāo)j的范圍從1到10，則存放M至少需要（D）個(gè)字節(jié)；M的第8列和第5行共占（A）個(gè)字節(jié)；若M按行優(yōu)先方式存儲(chǔ)，元素M[8][5]的起始地址與當(dāng)M按列優(yōu)先方式存儲(chǔ)時(shí)的（B）元素的起始地址一致。（1）A、90B、180C、240D、540（2）A、108B、114C、54D、60（3）A、M[8][5]B、M[3][10]C、M[5][8]D、M[0][9]9.二維數(shù)組M的元素是4個(gè)字符（每個(gè)字符占一個(gè)存儲(chǔ)單元）組成的串，行下標(biāo)i的范圍從0到4，列下標(biāo)j的范圍從0到5，M按行存儲(chǔ)時(shí)元素M[3][5]的起始地址與M按列存儲(chǔ)時(shí)元素（B）的起始地址相同。A、m[2][4]B、M[3][4]C、M[3][5]D、M[4][4]10.數(shù)組A中，每個(gè)元素A的存儲(chǔ)占3個(gè)單元，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi)，存放該數(shù)組至少需要的單元個(gè)數(shù)是（C），若該數(shù)組按行存放時(shí)，元素A[8][5]的起始地址是（C），若該數(shù)組按列存放時(shí)，元素A[8][5]的起始地址是（B）。（1）A、80B、100C、240D、270（2）A、SA+141B、SA+144C、SA+222D、SA+225（3）A、SA+141B、SA+180C、SA+222D、SA+225二、填空題1、設(shè)廣義表A=((a,(b),c),（(d)）,(e,f))，則表長(zhǎng)為(3)；表頭，表尾運(yùn)算分別用H（A），T（A）表示，則表示原子e的表達(dá)式為(H(H(T(T(A)))))。2、一個(gè)向量的第一個(gè)元素存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第五個(gè)元素的地址(108)。3、廣義表中元素既可以是單原子，也可以是(廣義表)廣義表兩個(gè)基本操作是(取表頭)、(取表尾)。4、若設(shè)一個(gè)N*N的矩陣A的開(kāi)始存儲(chǔ)地址LOC（0，0）及元素所占的存儲(chǔ)單元數(shù)d已知，按行優(yōu)先存儲(chǔ)時(shí)任意一個(gè)矩陣元素a[i][j]的存儲(chǔ)地址為（LOG(0,0)+(i*n+j)*d）。5、廣義表的深度定義為廣義表的括號(hào)的（重?cái)?shù)）。6、一棵樹(shù)的廣義表的表示為a(b(c,d(e,f),g(h)),i(j,k(x,y))),結(jié)點(diǎn)的f的層次為（3）。設(shè)根結(jié)點(diǎn)的層次為0。7、假定一棵樹(shù)的廣義表表示為A(B,C,D(E,F(H(I,J),G)))則樹(shù)中所含的結(jié)點(diǎn)數(shù)為（10），樹(shù)的深度為（4），樹(shù)的度是（3）。設(shè)根結(jié)點(diǎn)的層次為0。8、將一個(gè)N階矩陣A的上三角部分按行優(yōu)壓縮存放于一個(gè)一維數(shù)組B中，A[0][0]存放于B[0]中，則A[i][j]在i<=j時(shí)將存放于數(shù)組B的（(2n-i-1)i/2+j-i）位置。三、判斷題1、一個(gè)廣義表的（（a）,((b),c),(((d)))）的長(zhǎng)度為3，深度為4。(T)2、C=((x,(a,b)),y)是一個(gè)長(zhǎng)度為3的廣義表。(F)3、tail(tail(a,(c,d))的結(jié)果是（d）。(F)4、廣義表((a))的表頭是(a),表尾不存在。(F)5、三元組表是稀疏矩陣的一種順序存儲(chǔ)結(jié)構(gòu)。(T)6、對(duì)非空的廣義表的表頭和表尾總是一個(gè)廣義表。(F)7、將一個(gè)對(duì)角陣按照行優(yōu)先的順序壓縮到一個(gè)向量中時(shí)，對(duì)應(yīng)的存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)的存取結(jié)構(gòu)。(T)8、若已知一個(gè)數(shù)組的起始存儲(chǔ)地址和維數(shù)以及每維的上、下界，且已知每個(gè)數(shù)組元素所占有的單元數(shù)，則不管按照行優(yōu)先還是列優(yōu)先，元素a[i,j]的存儲(chǔ)地址是一樣的。(F)9、順序存儲(chǔ)的數(shù)組是一個(gè)隨機(jī)存取結(jié)構(gòu)。(T)10、對(duì)一個(gè)空表作求表頭和表尾的運(yùn)算后得到的表頭和表尾均是空表。(F)四、操作題1、n階矩陣Aij（Aij（0≤i，j≤n-1）的上三角(不含對(duì)角線)為常數(shù)C，下三角無(wú)規(guī)律，設(shè)計(jì)壓縮存儲(chǔ)方案。參考答案：1）、共需空間為n(n+1)/2+1個(gè),地址從0至n(n+1)/22）、按照行優(yōu)先順序依次存儲(chǔ)下三角的元素，將常數(shù)C存入n(n+)/2中3）、關(guān)系為：i(i+1)/2+ji>=jK=n(n+1)/2i<j第六章樹(shù)與二叉樹(shù)一、選擇題1、若一棵二叉樹(shù)具有10個(gè)度為2的結(jié)點(diǎn)，則該二叉樹(shù)的度為0的結(jié)點(diǎn)個(gè)數(shù)是（B）A、9B、11C、12D、不確定2、在有n個(gè)結(jié)點(diǎn)的二叉鏈表中，值為非空的鏈域的個(gè)數(shù)為（A）。A、n-1B、2n-1C、n+1D、2n+13、對(duì)二叉樹(shù)從1開(kāi)始進(jìn)行連續(xù)編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左右孩子的編號(hào)，同一個(gè)結(jié)點(diǎn)的左右孩子中，其左孩子的編號(hào)小于其右孩子的編號(hào)，則可采用（C）遍歷實(shí)現(xiàn)編號(hào)。

A、無(wú)序B、中序C、后序D、從根開(kāi)始的層次遍歷4、某二叉樹(shù)的中序序列和后序序列正好相反，則該二叉樹(shù)一定是（C）的二叉樹(shù)。

A、空或只有一個(gè)結(jié)點(diǎn)B、高度等于其結(jié)點(diǎn)數(shù)C、任一結(jié)點(diǎn)無(wú)左孩子D、任一結(jié)點(diǎn)無(wú)右孩子5、有64個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為（B）（根的層次為1）。A、8

B、7

C、6

D、56、在有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)中，其結(jié)點(diǎn)總數(shù)為（D）。Ａ、不確定Ｂ、2nＣ、2n+1D、2n-17、設(shè)只含根結(jié)點(diǎn)的二叉樹(shù)的高度為0,則高度為k的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)為(B)A、2kB、2k+1-1C、2k-1D、2k-1-18、將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根這一層開(kāi)始，每一層上從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)為49的結(jié)點(diǎn)的左孩子編號(hào)為（A）。A、98B、99Ｃ、50Ｄ、489、樹(shù)中所有結(jié)點(diǎn)的度之和等于所有結(jié)點(diǎn)數(shù)加（C）A、0B、1C、-1D、210、一棵具有35個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度為（B），假定樹(shù)根的高度為1。A、5B、6C、7D、811、在一個(gè)棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中，樹(shù)枝結(jié)點(diǎn)的最大編號(hào)是（A）設(shè)按層次編號(hào)，且樹(shù)根的編號(hào)為0。A、（n-1）」/2B、n/2」C、「n/2D、n/2」-112、利用n個(gè)權(quán)值作為葉子結(jié)點(diǎn)的生成的哈夫曼樹(shù)中共包含(D)個(gè)結(jié)點(diǎn)Ａ、nB、n+1Ｃ、2*nＤ、2*n-113、權(quán)值分別為3，8，6，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為（D）。A、24B、48C、72D、5314、如果T2是由有序樹(shù)T轉(zhuǎn)換而來(lái)的二叉樹(shù),那么T中的結(jié)點(diǎn)的后序就是T2中的結(jié)點(diǎn)的(B)A、先序B、中序C、后序D、層次序列15、設(shè)有13個(gè)值,用它們組成一棵哈夫曼樹(shù),則該哈無(wú)曼樹(shù)的共有(D)個(gè)結(jié)點(diǎn).A、13B、12C、26D、25二、填空題1、樹(shù)與二叉樹(shù)的區(qū)別是(樹(shù)是無(wú)序的，而二叉樹(shù)是有序的)、(二叉樹(shù)的度小于等于2，而樹(shù)是任意的)。2、93個(gè)結(jié)點(diǎn)的完全二叉樹(shù)高度為(7)，葉子數(shù)為(47)。3、已知一棵度為5的樹(shù)中，2度、3度、4度、5度結(jié)點(diǎn)的個(gè)數(shù)依次為1，2，3，4個(gè)，則葉子個(gè)數(shù)為(31)。4、8層完全二叉樹(shù)至少有(128)個(gè)結(jié)點(diǎn),擁有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的最大層數(shù)為(7)。5、深度為K的完全二叉樹(shù),其前K-1層共有(2k-1-1)個(gè)結(jié)點(diǎn)。 6、哈夫曼樹(shù)是帶權(quán)路徑(最短)的樹(shù),通常權(quán)值較大的結(jié)點(diǎn)離根(近)。三、判斷題1、將一棵樹(shù)轉(zhuǎn)換成一棵二叉樹(shù)之后，二叉樹(shù)的根結(jié)點(diǎn)的右子樹(shù)必定為空。（T）

2、一棵樹(shù)的度是指該樹(shù)中所有結(jié)點(diǎn)的度的和。（F）3、滿二叉樹(shù)一定是完全二叉樹(shù)，并且完全二叉樹(shù)也一定是滿二叉樹(shù)。（F）4、從樹(shù)的根結(jié)點(diǎn)到樹(shù)中其余結(jié)點(diǎn)均存在一條惟一的路徑。（T）5、在完全二叉樹(shù)中，一個(gè)結(jié)點(diǎn)若沒(méi)有左孩子，則它一定沒(méi)有右孩子。（T）四、操作題1、已知二叉樹(shù)的先序、中序和后序序列分別如下，但其中有一些模糊不清，請(qǐng)將其補(bǔ)完整。先序序列＿BC＿EF＿＿中序序列BDE＿AG＿H后序序列＿DC＿GH＿A參考答案：先：ABCDEFGH中：BDECAGFH后：EDCBGHFA2、假設(shè)字符a,b,c,d,e,f的使用頻度分別是0.07,0.09,0.12,0.22,0.23,0.27。(1)畫(huà)出這棵Huffman（哈夫曼）樹(shù),并計(jì)算WPL值。(2)寫(xiě)出a,b,c,d,e,f的Huffman（哈夫曼）編碼。參考答案：哈夫曼樹(shù)(略)WPL=2.44字符abcdef編碼111011111100001103、已知某二叉樹(shù)的先序、中序遍歷序列分別為ABCDEFG;BDCEAGF，畫(huà)出它的邏輯結(jié)構(gòu)，中序線索樹(shù),后序遍歷序列。參考答案：中序線索樹(shù)(略)AABCDEFG后序?yàn)椋篋ECBGFA4、請(qǐng)證明任意一棵二叉樹(shù)中葉子結(jié)點(diǎn)數(shù)等于度為2的結(jié)點(diǎn)數(shù)加1。參考答案：設(shè)度為0，1，2的結(jié)點(diǎn)個(gè)數(shù)分別為n0,n1,n2,總的結(jié)點(diǎn)數(shù)為n，則有下面的關(guān)系：n=n0+n1+n2;n-1=n1+2*n2;求得：n0=n2+15、假定一棵二叉樹(shù)的廣義表表示為A（B（，D（G）），C（E，F(xiàn)）），請(qǐng)分別寫(xiě)出對(duì)它的前序，中序，層次的遍歷序列。參考答案：前序遍歷序列:ABDGCEF。中序遍歷序列:BGDAECF。層次遍歷序列:ABCDEFG6、已知二叉樹(shù)的中的結(jié)點(diǎn)的類型BintreeNode定義為：StructBinTreeNode{ElemTypedata;BinTreeNode*left,*right;}其中data為結(jié)點(diǎn)值域，left和right分別為指向左右子女結(jié)點(diǎn)的指針域。根據(jù)下面的函數(shù)的定義指出函數(shù)的功能。算法中參數(shù)BT指向一棵二叉樹(shù)。VoidBTC(BinTreeNode*BT){BintreeNode*tIf(BT!=NULL){if(BT->left!=NULL&&BT->right->right!=NULL)If(BT->left->data>BT->right->data){T=Bt->left;BT->left=BT->right;BT->right=t;}BTC(BT->left);BTC(BT->right);}}參考答案：當(dāng)BT中的每個(gè)結(jié)點(diǎn)的左子女的值大于右子女的值則交換左右子樹(shù)。5、已知二叉樹(shù)的中的結(jié)點(diǎn)的類型BintreeNode定義為：StructBinTreeNode{ElemTypedata;BinTreeNode*left,*right;}其中data為結(jié)點(diǎn)值域，left和right分別為指向左右子女結(jié)點(diǎn)的指針域。參數(shù)bt指向一棵二叉棵，引用參數(shù)x一開(kāi)始具有的值小于樹(shù)中的所有的結(jié)點(diǎn)的值。試根據(jù)下面的函數(shù)定義指出此算法的功能。IntJB(BinTreeNode*bt,ElemType*x){if(bt==NULL)return1;else{if(JB(bt->left,*x)==0)rturn0;if(bt->data<*x)return0;*x=bt->data;if(JB(bt->right,*x)==0)return0;elsereturn1;}}參考答案：判定一樹(shù)二叉樹(shù)是否為二叉排序樹(shù)，是則返回1，否則返回0。6.有一個(gè)二叉樹(shù)中序序列為:ABCEFGHD后序序列為:ABFHGEDC,請(qǐng)畫(huà)出此二叉樹(shù)。參考答案：CCDBDBAEAEGGFHFH7、已知字符A，B，C，D，E，F(xiàn)，G的權(quán)值依次為(7，6，10，9，20，15，30)，設(shè)計(jì)它們的哈夫曼編碼，并計(jì)算WPL值。參考答案：A：1110B：1111C：010D：011E：00F：110G：10WPL=254五、算法題1、編寫(xiě)計(jì)算二叉樹(shù)的葉子個(gè)數(shù)算法，其中T為二叉樹(shù)的根指針。intCountLeaf(BinTreeT){}參考答案：intcountLeaf(BitTreeT){if(T==NULL)return0;elseif(T->lchild==NULL&&T->rchild==NULL)return1;elsereturn(countleaf(T->lchild)+countleaf(T->rchild));}2、二叉樹(shù)的中序與先序遍歷的非遞歸算法.StatusInOrderTraverse(BiTreeT){}StatusPreOrdertraverse(BiTreeT){}參考答案：//中序遍歷的非遞歸算法StatusInOrderTraverse(BiTreeT){BiTreeStackS;BiTreep;Initial(S);p=T;while(p||!StackEmpty(S)){if(p){Push(S,p);p=p->lchild;}else{Pop(S,p); printf("%c",p->data); p=p->rchild;}}returnOK}//先序遍歷的非遞歸算法StatusPreOrdertraverse(BiTreeT){BiTreeStackS;BiTreep;Initial(S);p=T;while(p||!StackEmpty(S)){if(p){printf("%c",p->data); Push(S,p);p=p->lchild;}else{Pop(S,p);p=p->rchild;}}returnOK;}3、編寫(xiě)層次遍歷二叉樹(shù)的算法。其中T為二叉樹(shù)的根指針。voidLayer(BiTreeT){}參考答案：voidLayer(BiTreeT){

InitQueue(Q);

EnQueue(Q,T);

while(!QueueEmpty(Q))

{

DeQueue(Q,p);

visit(p);

if(p->lchild)EnQueue(Q,p->lchild);

if(p->rchild)EnQueue(Q,p->rchild);

}}4、求二叉樹(shù)高度的算法.intBiTreeHigh(BiTree*b){}參考答案：intBiTreeHigh(BiTree*b){intlchilddep,rchilddep;if(b==NULL)return0;else{lchilddep=treedepth(b->lchild);rchilddep=treedepth(b->rchild);}return(lchilddep>rchilddep)?lchilddep+1:rchilddep+1;}第七章圖一、選擇題1、n個(gè)頂點(diǎn)的連通圖至少有（A）條邊。A、n-1B、nC、n+1D、02、帶權(quán)有向圖G用鄰接矩陣A存儲(chǔ)，則頂點(diǎn)i的人度等于A中（D）。A、第i行非∞的元素之和B、第i列非∞的元素之和C、第i行非∞的元素個(gè)數(shù)

D、第i列非∞的元素個(gè)數(shù)3、在有向圖中，所有頂點(diǎn)的入度之和是所有頂點(diǎn)的出度之和的(B)倍。A、2B、1

C、0.5

Ｄ、不確定4、任何一個(gè)無(wú)向連通圖的最小生成樹(shù)（B）A、只有一棵B、有一棵或多棵C、一定有多棵D、可能不存在5、對(duì)于一個(gè)具有N個(gè)頂點(diǎn)的圖，如果我們采用鄰接矩陣法表示，則此矩陣的維數(shù)應(yīng)該是(B)。A、(N-1)×(N-1)

B、N×N

C、(N+1)×(N+1)

D、不確定

6、對(duì)于一個(gè)具有N個(gè)結(jié)點(diǎn)和E條邊的無(wú)向圖，若采用鄰接表表示，則表頭向量的大小是(A)。A、N

B、N+1

C、N-E

D、N-17、判斷一個(gè)有向圖是否存在回路的方法中，除了可以利用拓?fù)渑判蚍椒ㄍ猓€可以利用的方法是(C)。A、求最短路徑的方法

B、求關(guān)鍵路徑的方法

C、深度優(yōu)先遍歷的方法

D、廣度優(yōu)先遍歷的方法8、一個(gè)具有N個(gè)頂點(diǎn)的有向圖最多有(B)條邊。A、N(N-1)/2

B、N(N-1)

C、N(N+1)

D、N(N+1)/2

9、對(duì)于具有e條邊的無(wú)向圖，它的鄰接表中有（D）邊結(jié)點(diǎn)A、e-1B、eC、2(e-1)D、2e10、圖的深度優(yōu)先搜索類似于樹(shù)的（A）次序遍歷。A、先根B、中根C、后根D、層次11、設(shè)有向圖有n個(gè)頂點(diǎn)和e條邊，采用鄰接表作為其存儲(chǔ)表示，在進(jìn)行拓?fù)渑判驎r(shí)，總的計(jì)算時(shí)間為（B）。A、O(nlog2e)B、O(n+e)C、O(ne)D、O(n2)12、在連通具有n個(gè)頂點(diǎn)的有向圖，至少需要（B）條邊。A、n-1B、nC、n+1D、2n13、以知有向圖G=（V，E），其中V={V1，V2，V3，V4，V5，V6，V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V3,V7>,<V6,V7>}則G的可能拓?fù)湫蛄袨椋海ˋ）A、V1，V3，V4，V6，V2，V5，V7B、V1，V3，V2，V6，V4，V5，V7C、V1，V3，V4，V5，V2，V6，V7D、V1，V2，V5，V3，V4，V6，V714、對(duì)于一個(gè)有向圖,其鄰接矩陣表示比鄰接表表示更易于(A)A、求一個(gè)頂點(diǎn)的入度B、求一個(gè)頂點(diǎn)的出邊鄰接點(diǎn)C、進(jìn)行圖的濃度優(yōu)先遍歷D、進(jìn)行圖的廣度優(yōu)先遍歷15、在一個(gè)帶權(quán)的連通圖G中，權(quán)值最小的邊一定包含在G的（A）中。A、最小生成樹(shù)中B、生成樹(shù)中C、廣度優(yōu)先生成樹(shù)中D、深度優(yōu)先生成樹(shù)中16、與鄰接矩陣相比，鄰接表更適合存儲(chǔ)（C）A、無(wú)向圖B、連通圖C、稀疏圖D、稠密圖17、設(shè)無(wú)向圖的頂點(diǎn)的個(gè)數(shù)為n，則該圖的最多有（B）條邊。A、n-1B、n(n-1)/2C、n(n+1)/2D、n(n-1)18、N個(gè)頂點(diǎn)的強(qiáng)連通圖至少有（A）條邊，這樣的有向圖的形狀是（C）。（1）A、nB、n＋1C、n－1D、n（n－1）（2）A、無(wú)回路B、有回路C、環(huán)狀D、樹(shù)狀19、最短路徑的生成算法可用（C）。A、普里姆算法B、克魯斯卡爾算法C、迪杰斯特拉算法D、哈夫曼算法20、有拓?fù)渑判虻膱D一定是（D）。A、有環(huán)圖B、無(wú)向圖C、強(qiáng)連通圖D、有向無(wú)環(huán)圖21、圖的鄰接表如下圖所示：vertexfirstedgeV013∧V0V1V1023∧V21V21V3V301∧從頂點(diǎn)V0出發(fā)進(jìn)行深度優(yōu)先搜索，經(jīng)歷的結(jié)點(diǎn)順序?yàn)椋˙）。A、V0,V3,V2,V1B、V0,V1,V2,V3C、V0,V2,V1,V3D、V0,V1,V3,V2從頂點(diǎn)V0出發(fā)進(jìn)行廣度優(yōu)先搜索，經(jīng)歷的結(jié)點(diǎn)順序?yàn)椋―）。A、V0,V3,V2,V1B、V0,V1,V2,V3C、V0,V2,V1,V3D、V0,V1,V3,V222、對(duì)于含有n個(gè)頂點(diǎn)e條邊的無(wú)向連通圖，利用Kruskal算法生成最小代價(jià)生成樹(shù)其時(shí)間復(fù)雜度為（A）。A、O(elog2e)B、O(en)C、O(elog2n)D、O(nlog2n)23、關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（A）。A、從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑B、從源點(diǎn)到匯點(diǎn)的最短路徑C、最長(zhǎng)的回路D、最短的回路二、填空題1、在一個(gè)無(wú)向圖中，所有的頂點(diǎn)的度數(shù)之和等于邊數(shù)的（2）倍。2、已知一個(gè)圖的頂點(diǎn)集V和邊的集合E分別如下：V={0，1，2，3，4，5，6}E={(0,1)8,(0,2)2,(0,3)6,(1,3)9,(1,4)5,(2,6)10,(3,6)12,(4,5)16,(5,6)15}則按照克魯斯卡爾算法寫(xiě)出得到的最小生成樹(shù)的過(guò)程中依次求出的各邊數(shù)（(0,2)2）（(1,4)5）（(0,3)6）（(0,1)8）（(2,6)10）（(5,6)15）。3、一般來(lái)說(shuō)，深度優(yōu)先生成樹(shù)比廣度優(yōu)先生成樹(shù)的高度要（高）。4、設(shè)無(wú)向圖G中頂點(diǎn)數(shù)為n，則圖G最少有(n-1)條邊，最多有(n（n-1）/2)條邊。若G為有向圖，有n個(gè)頂點(diǎn)，則圖G最少有(n)條邊；最多有(n（n-1）)條邊。5、具有n個(gè)頂點(diǎn)的無(wú)向完全圖，邊的總數(shù)為(n（n-1）/2)條；而在n個(gè)頂點(diǎn)的有向完全圖中，邊的總數(shù)為(n（n-1）)條。圖的鄰接矩陣表示法是表示(邊)之間相鄰關(guān)系的矩陣。一個(gè)圖的生成樹(shù)的頂點(diǎn)是圖的(所有)頂點(diǎn)。8、寫(xiě)出下圖所示的一組拓?fù)湫蛄?V0-V1-V5-V2-V3-V6-V4)。V3V0V3V0V41V2V41V2v1v1V5V6V5V69、在如下圖所示的網(wǎng)絡(luò)計(jì)劃圖中關(guān)鍵路徑是(11,13,16,17)，全部計(jì)劃完成的時(shí)間是(19)。121551215308171411207.21714112416134.56.51613810、深度優(yōu)先遍歷類似于樹(shù)的(先根)遍歷.它所用的數(shù)據(jù)結(jié)構(gòu)是(棧)11、一個(gè)連通圖的生成樹(shù)是一個(gè)(極大)連通子圖，n個(gè)頂點(diǎn)的生成樹(shù)有(n-1)條邊。12、對(duì)于含有n個(gè)頂點(diǎn)e條邊的無(wú)向連通圖，利用prim算法生成最小代價(jià)生成樹(shù)其時(shí)間復(fù)雜度為(O(n2))。13、鄰接表和十字鏈表適合于存儲(chǔ)(有向)圖，鄰接多重表適合于存儲(chǔ)(無(wú)向)圖。14、一個(gè)非連通無(wú)向圖,共有28條邊,則該圖至少有(9)個(gè)頂點(diǎn).15、克魯斯卡爾算法的時(shí)間復(fù)雜度是(O(elog2e)),它對(duì)(稀疏)圖較適用.16、從源點(diǎn)到匯點(diǎn)長(zhǎng)度最大的路徑稱為關(guān)鍵路徑,該路徑上的活動(dòng)稱為(關(guān)鍵活動(dòng))三、判斷題1、對(duì)任意一個(gè)圖，從它的某個(gè)頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索遍歷可訪問(wèn)到該圖的每個(gè)頂點(diǎn)。（F）2、一個(gè)有向圖的鄰接表和逆鄰接表中的結(jié)點(diǎn)個(gè)數(shù)一定相等。（T）3、任何有向圖的結(jié)點(diǎn)都可以排成拓?fù)渑判?，而且拓?fù)渑判虿晃ㄒ?。（F）4、當(dāng)改變網(wǎng)上某一關(guān)鍵路徑上任一關(guān)鍵活動(dòng)后，必將產(chǎn)生不同的關(guān)鍵路徑。（F）5、若V（G）中有兩個(gè)不同的頂點(diǎn)是連通的，則G就稱為是連通圖。（F）6、任何圖的連通分量只有一個(gè)。（F）7、對(duì)于一個(gè)有向圖進(jìn)行拓?fù)渑判?，一定可以將圖中所有的頂點(diǎn)按其關(guān)鍵碼大小排序到一個(gè)拓?fù)溆行虻男蛄兄小＃‵）8、存儲(chǔ)有向圖的鄰接矩陣是對(duì)稱的，因此可以只存儲(chǔ)鄰接矩陣的下（上）三角部分。（F）9、若連通圖上各邊權(quán)值均不相同,則該圖的最小生成樹(shù)是唯一的。（T）10、有回路的有向圖不能完成拓?fù)渑判?。（T）四、操作題1、帶權(quán)無(wú)向圖Ｇ（頂點(diǎn)分別為Ｖ１，Ｖ２，Ｖ３，Ｖ４，Ｖ５，Ｖ６）的鄰接矩陣是Ａv1v2v3v4v5v6∞６∞∞６３６∞５∞∞４∞５∞６∞∞Ａ＝∞∞６∞∞７６∞∞∞∞２３４∞７２∞要求：（１）畫(huà)出圖Ｇ。（２）分別畫(huà)出一棵