[理學(xué)]2011考研計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)講義

1、.數(shù)據(jù)結(jié)構(gòu)緒論數(shù)據(jù)元素：數(shù)據(jù)元素是數(shù)據(jù)的基本單位一個(gè)數(shù)據(jù)元素可由若干數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割的最小單位數(shù)據(jù)的邏輯結(jié)構(gòu)分為：集合、線性結(jié)構(gòu)（線性表）、非線性結(jié)構(gòu)(樹和圖)存儲結(jié)構(gòu)：順序存儲（實(shí)現(xiàn)隨機(jī)存?。?、鏈?zhǔn)酱鎯Γㄖ荒茼樞虼嫒。⑺饕鎯?、散列存儲?shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為數(shù)據(jù)的物理結(jié)構(gòu)，又稱為存儲結(jié)構(gòu) 一、線性表大綱要求：（一） 線性表的定義和基本操作 （二） 線性表的實(shí)現(xiàn) 1. 順序存儲結(jié)構(gòu) 2. 鏈?zhǔn)酱鎯Y(jié)構(gòu) 3. 線性表的應(yīng)用 知識點(diǎn)：1 深刻理解數(shù)據(jù)結(jié)構(gòu)的概念，掌握數(shù)據(jù)結(jié)構(gòu)的“三要素”：邏輯結(jié)構(gòu)、物理（存儲）結(jié)構(gòu)及在這種結(jié)構(gòu)上所定義的操作“運(yùn)算”。2 時(shí)間復(fù)雜度和空間復(fù)雜度

2、的定義，常用計(jì)算語句頻度來估算算法的時(shí)間復(fù)雜度。以下六種計(jì)算算法時(shí)間的多項(xiàng)式是最常用的。其關(guān)系為：O(1)<O(logn)<O(n)<O(nlogn) <O(n2)<O(n3)指數(shù)時(shí)間的關(guān)系為： O(2n)<O(n!)<O(nn)3 線性表的邏輯結(jié)構(gòu)，是指線性表的數(shù)據(jù)元素間存在著線性關(guān)系。主要是指：除第一及最后一個(gè)元素外，每個(gè)結(jié)點(diǎn)都只有一個(gè)前趨和只有一個(gè)后繼。在順序存儲結(jié)構(gòu)中，元素存儲的先后位置反映出這種邏輯關(guān)系，而在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，是靠指針來反映這種邏輯關(guān)系的。4 順序存儲結(jié)構(gòu)用向量（一維數(shù)組）表示，給定下標(biāo)，可以存取相應(yīng)元素，屬于隨機(jī)存取的存儲結(jié)構(gòu)

3、。5 線性表的順序存儲方式及其在具體語言環(huán)境下的兩種不同實(shí)現(xiàn)：表空間的靜態(tài)分配和動(dòng)態(tài)分配。掌握順序表上實(shí)現(xiàn)插入、刪除、定位等運(yùn)算的算法。6 盡管“只要知道某結(jié)點(diǎn)的指針就可以存取該元素”，但因鏈表的存取都需要從頭指針開始，順鏈而行，故鏈表不屬于隨機(jī)存取結(jié)構(gòu)。要理解頭指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn)和元素結(jié)點(diǎn)的差別。頭結(jié)點(diǎn)是在插入、刪除等操作時(shí)，為了算法的統(tǒng)一而設(shè)立的（若無頭結(jié)點(diǎn)，則在第一元素前插入元素或刪除第一元素時(shí)，鏈表的頭指針總在變化）。對鏈表（不包括循環(huán)鏈表）的任何操作，均要從頭結(jié)點(diǎn)開始，頭結(jié)點(diǎn)的指針具有標(biāo)記作用，故頭指針往往被稱為鏈表的名字，如鏈表head是指鏈表頭結(jié)點(diǎn)的指針是head。理解循環(huán)鏈

4、表中設(shè)置尾指針而不設(shè)置頭指針的好處。鏈表操作中應(yīng)注意不要使鏈意外“斷開”。因此，若在某結(jié)點(diǎn)前插入一個(gè)元素或刪除某元素，必須知道該元素的前驅(qū)結(jié)點(diǎn)的指針。7 鏈表是本部分學(xué)習(xí)的重點(diǎn)和難點(diǎn)。重點(diǎn)掌握以下幾種常用鏈表的特點(diǎn)和運(yùn)算：單鏈表、循環(huán)鏈表、雙向鏈表、雙向循環(huán)鏈表的生成、插入、刪除、遍歷以及鏈表的分解和歸并等操作。并能夠設(shè)計(jì)出實(shí)現(xiàn)線性表其它運(yùn)算的算法。8 從時(shí)間復(fù)雜度和空間復(fù)雜度的角度綜合比較線性表在順序和鏈?zhǔn)絻煞N存儲結(jié)構(gòu)下的特點(diǎn)，即其各自適用的場合。小結(jié)：順序表和鏈表的比較通過對它們的討論可知它們各有優(yōu)缺點(diǎn)，順序存儲有三個(gè)優(yōu)點(diǎn)：（1）方法簡單，各種高級語言中都有數(shù)組，容易實(shí)現(xiàn)。（2）不用為表示

5、結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲開銷。（3）順序表具有按元素序號隨機(jī)訪問的特點(diǎn)。 但它也有兩個(gè)缺點(diǎn)：（1）在順序表中做插入刪除操作時(shí)，平均移動(dòng)大約表中一半的元素，因此對n較大的順序表效率低。（2）需要預(yù)先分配足夠大的存儲空間，估計(jì)過大，可能會導(dǎo)致順序表后部大量閑置；預(yù)先分配過小，又會造成溢出。鏈表的優(yōu)缺點(diǎn)恰好與順序表相反。在實(shí)際中怎樣選取存儲結(jié)構(gòu)呢？（1）基于存儲的考慮對線性表的長度或存儲規(guī)模難以估計(jì)時(shí)，不宜采用順序表；鏈表不用事先估計(jì)存儲規(guī)模，但鏈表的存儲密度較低，顯然鏈?zhǔn)酱鎯Y(jié)構(gòu)的存儲密度是小于的。（2）基于運(yùn)算的考慮在順序表中按序號訪問ai的時(shí)間性能時(shí)O(1)，而鏈表中按序號訪問的時(shí)間性

6、能O(n)，所以如果經(jīng)常做的運(yùn)算是按序號訪問數(shù)據(jù)元素，顯然順序表優(yōu)于鏈表；而在順序表中做插入、刪除時(shí)平均移動(dòng)表中一半的元素，當(dāng)數(shù)據(jù)元素的信息量較大且表較長時(shí)，這一點(diǎn)是不應(yīng)忽視的；在鏈表中作插入、刪除，雖然也要找插入位置，但操作主要是比較操作，從這個(gè)角度考慮顯然后者優(yōu)于前者。（3）基于環(huán)境的考慮 順序表容易實(shí)現(xiàn)，任何高級語言中都有數(shù)組類型，鏈表的操作是基于指針的，相對來講前者簡單些，也是用戶考慮的一個(gè)因素?？傊?，兩種存儲結(jié)構(gòu)各有長短，選擇那一種由實(shí)際問題中的主要因素決定。通?！拜^穩(wěn)定”的線性表選擇順序存儲，而頻繁做插入刪除的即動(dòng)態(tài)性較強(qiáng)的線性表宜選擇鏈?zhǔn)酱鎯?。練?xí)題：（一）選擇題：1以下那一個(gè)術(shù)

7、語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)？（ A ）A隊(duì)列 B. 哈希表 C. 線索樹 D. 雙向鏈表2、一個(gè)算法應(yīng)該是（ B ）。A程序 B問題求解步驟的描述 C要滿足五個(gè)基本特性 DA和C.3、數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的（ C ）A存儲結(jié)構(gòu) B物理結(jié)構(gòu) C邏輯結(jié)構(gòu) D物理結(jié)構(gòu)和存儲結(jié)構(gòu)4. 算法的計(jì)算量的大小稱為計(jì)算的（ B ）。A效率 B復(fù)雜性 C現(xiàn)實(shí)性 D難度5下列說法，不正確的是（D）。A數(shù)據(jù)元素是數(shù)據(jù)的基本單位B數(shù)據(jù)項(xiàng)是數(shù)據(jù)中不可分割的最小可標(biāo)識單位C數(shù)據(jù)可由若干個(gè)數(shù)據(jù)元素構(gòu)成D數(shù)據(jù)項(xiàng)可由若干個(gè)數(shù)據(jù)元素構(gòu)成6連續(xù)存儲設(shè)計(jì)時(shí)，存儲單元的地址（ A ）。A一定連續(xù) B一定不連續(xù) C不一定

8、連續(xù) D部分連續(xù)，部分不連續(xù)7. 線性表（ a1,a2,an）以鏈接方式存儲時(shí)，訪問第i位置元素的時(shí)間復(fù)雜性為（ C ）。AO（i） BO（1） CO（n） DO（i-1）8. 對于順序存儲的線性表，訪問結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為（ C ）。AO(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)9. 設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data，link）。已知指針q所指點(diǎn)是指針p所指結(jié)點(diǎn)的直接前驅(qū)，若在*q與*p之間插入結(jié)點(diǎn)*s，則應(yīng)執(zhí)行下列哪一個(gè)操作？（ B ）。As>link=p>link；p>link=sBq>link=s

9、；s>link=pCp>link=s>link；s>link=pDp>link=s；s>link=q10. 在一個(gè)長度為n的順序表的表尾插入一個(gè)新元素的漸進(jìn)時(shí)間復(fù)雜度為（ B ）。AO（n） BO（1） CO（n2） DO（log2n）11. 表長為n的順序存儲的線性表，當(dāng)在任何位置上插入一個(gè)元素的概率相等時(shí)，插入一個(gè)元素所需移動(dòng)元素的平均個(gè)數(shù)為（ B ）An B. n/2C. (n-1)/2 D. (n+1)/212. 循環(huán)鏈表的主要優(yōu)點(diǎn)是（ D ）A不再需要頭指針了。B已知某個(gè)結(jié)點(diǎn)的位置后，能很容易找到它的直接前驅(qū)結(jié)點(diǎn)。C在進(jìn)行刪除操作后，能保證鏈表不斷

10、開。D從表中任一結(jié)點(diǎn)出發(fā)都能遍歷整個(gè)鏈表。（二）應(yīng)用題1、按增長率由小至大排列以下7個(gè)函數(shù)。答：2、數(shù)據(jù)的存儲結(jié)構(gòu)由哪四種基本的存儲方法實(shí)現(xiàn)，并做以簡要說明？答：四種表示方法（1）順序存儲方式。數(shù)據(jù)元素順序存放，每個(gè)存儲結(jié)點(diǎn)只含一個(gè)元素。存儲位置反映數(shù)據(jù)元素間的邏輯關(guān)系。存儲密度大，但有些操作（如插入、刪除）效率較差。（2）鏈?zhǔn)酱鎯Ψ绞?。每個(gè)存儲結(jié)點(diǎn)除包含數(shù)據(jù)元素信息外還包含一組（至少一個(gè)）指針。指針反映數(shù)據(jù)元素間的邏輯關(guān)系。這種方式不要求存儲空間連續(xù)，便于動(dòng)態(tài)操作（如插入、刪除等），但存儲空間開銷大（用于指針），另外不能折半查找等。（3）索引存儲方式。除數(shù)據(jù)元素存儲在一地址連續(xù)的內(nèi)存空間外，

11、尚需建立一個(gè)索引表，索引表中索引指示存儲結(jié)點(diǎn)的存儲位置（下標(biāo)）或存儲區(qū)間端點(diǎn)（下標(biāo)），兼有靜態(tài)和動(dòng)態(tài)特性。（4）散列存儲方式。通過散列函數(shù)和解決沖突的方法，將關(guān)鍵字散列在連續(xù)的有限的地址空間內(nèi)，并將散列函數(shù)的值解釋成關(guān)鍵字所在元素的存儲地址，這種存儲方式稱為散列存儲。其特點(diǎn)是存取速度快，只能按關(guān)鍵字隨機(jī)存取，不能順序存取，也不能折半存取。3. 線性表有兩種存儲結(jié)構(gòu)：一是順序表，二是鏈表。試問：（1）如果有 n個(gè)線性表同時(shí)并存，并且在處理過程中各表的長度會動(dòng)態(tài)變化，線性表的總數(shù)也會自動(dòng)地改變。在此情況下，應(yīng)選用哪種存儲結(jié)構(gòu)？ 為什么？（2）若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最

12、快的速度存取線性表中的元素，那么應(yīng)采用哪種存儲結(jié)構(gòu)？為什么？ 答：（1）選鏈?zhǔn)酱鎯Y(jié)構(gòu)。它可動(dòng)態(tài)申請內(nèi)存空間，不受表長度（即表中元素個(gè)數(shù)）的影響，插入、刪除時(shí)間復(fù)雜度為O（1）。（2）選順序存儲結(jié)構(gòu)。順序表可以隨機(jī)存取，時(shí)間復(fù)雜度為O（1）。（三）算法設(shè)計(jì)題1設(shè)計(jì)算法，求帶表頭的單循環(huán)鏈表的表長。解：int length(Linklist L) int I; listnode *p; I=0; P=L; while (p->next!=L) p=p->next; I+; return I;2.已知單鏈表L，寫一算法，刪除其重復(fù)結(jié)點(diǎn)。算法思路：用指針p指向第一個(gè)數(shù)據(jù)結(jié)點(diǎn)，從它的后繼結(jié)

13、點(diǎn)開始到表的結(jié)束，找與其值相同的結(jié)點(diǎn)并刪除之；p指向下一個(gè)；依此類推，p指向最后結(jié)點(diǎn)時(shí)算法結(jié)束。算法如下：解：void pur_LinkList(LinkList H) LNode *p,*q,*r; p=H->next; /*p指向第一個(gè)結(jié)點(diǎn)*/ if(p=NULL) return; while (p->next) q=p; while (q->next) /* 從*p的后繼開始找重復(fù)結(jié)點(diǎn)*/ if (q->next->data=p->data) r=q->next; /*找到重復(fù)結(jié)點(diǎn)，用r指向，刪除*r */ q->next=r->ne

14、xt; free(r); /*if*/ else q=q->next; /*while(q->next)*/ p=p->next; /*p指向下一個(gè)，繼續(xù)*/ /*while(p->next)*/該算法的時(shí)間性能為O(n2)。3.已知指針la和lb分別指向兩個(gè)無頭結(jié)點(diǎn)的單鏈表中的首結(jié)點(diǎn)。請編寫函數(shù)完成從表la中刪除自第i個(gè)元素開始的共len個(gè)元素并將它們插入到表lb中第j個(gè)元素之前，若lb中只有j-1個(gè)元素，則插在表尾。函數(shù)原型如下：int DeleteAndInsertSub(LinkList &la,LinkList &lb,int i,int j,

15、int len)；答：int DeleteAndInsertSub(LinkList &la,LinkList &lb,int i,int j,int len)int k; LinkList p,q,prev,s;if(i<0|j<0|len<0)return -1;p=la;k=1;prev=NULL;while(p&&k<i)prev=p;p=p->next;k+;if(!p)return -1;q=p;k=1;while(q&&k<len)q=q->next;k+;if(!q)return -1;i

16、f(!prev)la=q->next;elseprev->next=q->next;if(j=1)q->next=lb;lb=q;elses=lb;k=1;while(s&&k<j-1)s=s->next;k+;if(!s)return -1;q->next=s->next;s->next=p;return 1;4寫一算法，將一帶有頭結(jié)點(diǎn)的單鏈表就地逆置，即要求逆置在原鏈表上進(jìn)行，不允許重新構(gòu)造新鏈表。圖 單鏈表的倒置254525187629L297625184525L(a)(b)函數(shù)原型如下：void LinkList_r

17、everse(LinkList &L)；答：void LinkList_reverse(LinkList &L)LinkList p,q,s;p=L->next;q=p->next;s=q->next;p->next=NULL;while(s->next)q->next=p;p=q;q=s;s=s->next;q->next=p;s->next=q;L->next=s;5寫一算法，將帶有頭結(jié)點(diǎn)的非空單鏈表中數(shù)據(jù)域值最小的那個(gè)結(jié)點(diǎn)移到鏈表的最前面。要求：不得額外申請新的鏈結(jié)點(diǎn)。函數(shù)原型如下：void delinsert(

18、LinkList &L)；答：void delinsert(LinkList &L)p=L->next;/p是鏈表的工作指針pre=L;/pre指向鏈表中數(shù)據(jù)域最小值結(jié)點(diǎn)的前驅(qū)q=p;/q指向數(shù)據(jù)域最小值結(jié)點(diǎn)，初始假定是第一結(jié)點(diǎn)while(p->next!=NULL)if(p->next->data<q->data)/找到新的最小值結(jié)點(diǎn)pre=p;q=p->next; p=p->next;if(q!=L->next)/若最小值是第一元素結(jié)點(diǎn)，則不需再操作pre->next=q->next;/將最小值結(jié)點(diǎn)從鏈表上摘

19、下q->next=L->next;/將q結(jié)點(diǎn)插到鏈表最前面L->next=q;6編寫一個(gè)算法來交換單鏈表中指針P所指結(jié)點(diǎn)與其后繼結(jié)點(diǎn)，HEAD是該鏈表的頭指針，P指向該鏈表中某一結(jié)點(diǎn)。答：單鏈表中查找任何結(jié)點(diǎn)，都必須從頭指針開始。本題要求將指針p所指結(jié)點(diǎn)與其后繼結(jié)點(diǎn)交換，這不僅要求知道p結(jié)點(diǎn)，還應(yīng)知道p的前驅(qū)結(jié)點(diǎn)。這樣才能在p與其后繼結(jié)點(diǎn)交換后，由原p結(jié)點(diǎn)的前驅(qū)來指向原p結(jié)點(diǎn)的后繼結(jié)點(diǎn)。LinkedList Exchange（LinkedList HEAD，p） HEAD是單鏈表頭結(jié)點(diǎn)的指針，p是鏈表中的一個(gè)結(jié)點(diǎn)。本算法將p所指結(jié)點(diǎn)與其后繼結(jié)點(diǎn)交換。q=head->ne

20、xt； q是工作指針，指向鏈表中當(dāng)前待處理結(jié)點(diǎn)。pre=head； pre是前驅(qū)結(jié)點(diǎn)指針，指向q的前驅(qū)。while（q!=null && q!=p）pre=q；q=q->next； 未找到p結(jié)點(diǎn)，后移指針。if（p->next=null）printf（“p無后繼結(jié)點(diǎn)n”）; p是鏈表中最后一個(gè)結(jié)點(diǎn)，無后繼。Else 處理p和后繼結(jié)點(diǎn)交換 q=p->next； 暫存p的后繼。 pre->next=q； p前驅(qū)結(jié)點(diǎn)的后繼指向p的后繼。 p->next=q->next；p的后繼指向原p后繼的后繼。 q->next=p ；原p后繼的后繼指針指向

21、p。 算法結(jié)束。7已知線性鏈表第一個(gè)鏈結(jié)點(diǎn)指針為list，請寫一算法，將該鏈表分解為兩個(gè)帶有頭結(jié)點(diǎn)的循環(huán)鏈表，并將兩個(gè)循環(huán)鏈表的長度分別存放在各自頭結(jié)點(diǎn)的數(shù)據(jù)域中。其中,線性表中序號為偶數(shù)的元素分解到第一個(gè)循環(huán)鏈表中,序號為奇數(shù)的元素分解到第二個(gè)循環(huán)鏈表中。答：算法如下：void split(ListNode *List, ListNode *&list1, ListNode *&list2)list1=(ListNode *)malloc(sizeof(ListNode )；list2=(ListNode *)malloc(sizeof(ListNode )；p=list;；

22、q=list1；r=list2；len1=0；len2=0；mark=1；while (p!=null)if(mark=1)q->next=p;q=q->next;len1+;mark=2;elser->next=p;r=r->next;len2+;mark=1;list1->data=len1;list2->data=len2;q->next=list1;r->next=list2;8. 設(shè)A和B是兩個(gè)單鏈表，其表中元素遞增有序。試寫一算法將A和B歸并成一個(gè)按元素值遞減有序的單鏈表C，并要求輔助空間為O(1)。答：Linklist merge(

23、Linklist A,Linklist B)Linklist C;Listnode *p;C=null;while (A&&B) if(A->data<=B->data) p=A->next;A->next=C;C=A;A=p; else p=B->next;B->next=C;C=B;B=p; if (A)while(A) p=A->next;A->next=C;C=A;A=p; else while(B) p=B->next;B->next=C;C=B;B=p;return C;二、棧、隊(duì)列和數(shù)組大綱要求：（

24、一） 棧和隊(duì)列的基本概念 （二） 棧和隊(duì)列的順序存儲結(jié)構(gòu) （三） 棧和隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu) （四） 棧和隊(duì)列的應(yīng)用 （五） 特殊矩陣的壓縮存儲 知識點(diǎn)：1 棧、隊(duì)列的定義及其相關(guān)數(shù)據(jù)結(jié)構(gòu)的概念，包括：順序棧、鏈棧、循環(huán)隊(duì)列、鏈隊(duì)列等。棧與隊(duì)列存取數(shù)據(jù)（請注意包括：存和取兩部分）的特點(diǎn)。2 掌握順序棧和鏈棧上的進(jìn)棧和退棧的算法，并弄清?？蘸蜅M的條件。注意因棧在一端操作，故通常鏈棧不設(shè)頭結(jié)點(diǎn)。3 如何將中綴表達(dá)式轉(zhuǎn)換成前綴、后綴表達(dá)式，了解對兩種表達(dá)式求值的方法。4 棧與遞歸的關(guān)系。用遞歸解決的幾類問題：問題的定義是遞歸的，數(shù)據(jù)結(jié)構(gòu)是遞歸的，以及問題的解法是遞歸的。掌握典型問題的算法以及將遞歸算法

25、轉(zhuǎn)換為非遞歸算法，如n!階乘問題，fib數(shù)列問題，hanoi問題。了解在數(shù)值表達(dá)式的求解、括號的配對等問題中應(yīng)用棧的工作原理。5 掌握在鏈隊(duì)列上實(shí)現(xiàn)入隊(duì)和出隊(duì)的算法。注意對僅剩一個(gè)元素的鏈隊(duì)列刪除元素時(shí)的處理（令隊(duì)尾指針指向隊(duì)頭）。還需特別注意僅設(shè)尾指針的循環(huán)鏈隊(duì)列的各種操作的實(shí)現(xiàn)。6 循環(huán)隊(duì)列隊(duì)空及隊(duì)滿的條件。隊(duì)空定義為隊(duì)頭指針等于隊(duì)尾指針，隊(duì)滿則可用犧牲一個(gè)單元或是設(shè)標(biāo)記的方法，這里特別注意取模運(yùn)算。掌握循環(huán)隊(duì)列中入隊(duì)與出隊(duì)算法。7 在后續(xù)章節(jié)中多處有棧和隊(duì)列的應(yīng)用，如二叉樹遍歷的遞歸和非遞歸算法、圖的深度優(yōu)先遍歷等都用到棧，而樹的層次遍歷、圖的廣度優(yōu)先遍歷等則用到隊(duì)列。這些方面的應(yīng)用應(yīng)重

26、點(diǎn)掌握。8 數(shù)組在機(jī)器（內(nèi)存）級上采用順序存儲結(jié)構(gòu)。掌握數(shù)組（主要是二維）在以行序?yàn)橹骱土行驗(yàn)橹鞯拇鎯χ械牡刂酚?jì)算方法。9 特殊矩陣（對稱矩陣、對角矩陣、三角矩陣）在壓縮存儲是的下標(biāo)變換公式。練習(xí)題：（一）選擇題：1. 一個(gè)棧的輸入序列為1 2 3 4，則（D）不可能是其出棧序列。A. 1 2 4 3B. 2 1 3 4C. 1 4 3 2D. 4 3 1 22. 一個(gè)遞歸算法必須包括（ B ）。A. 遞歸部分 B. 終止條件和遞歸部分 C. 迭代部分 D.終止條件和迭代部分3. 一個(gè)遞歸的定義可以用遞歸過程求解，也可以用非遞歸過程求解，但單從運(yùn)行時(shí)間來看，通常遞歸過程比非遞歸過程（B）。 A

27、較快 B較慢 C相同 D以上答案都不對4. 棧和隊(duì)列都是（C）A順序存儲的線性表 B鏈?zhǔn)酱鎯Φ木€性表C限制存儲的線性表 D限制存儲的非線性結(jié)構(gòu)5. 二維數(shù)組N的元素是4個(gè)字符（每個(gè)字符占一個(gè)存儲單元）組成的串，行下標(biāo)i的范圍從0到4，列下標(biāo)j的范圍從0到5，N按行存儲時(shí)元素N35的起始地址與N按列存儲時(shí)元素（B）的起始地址相同。A. N24 B. N34C. N35 D. N446. 設(shè)有數(shù)組Ai,j，數(shù)組的每個(gè)元素長度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)以列為主序存放時(shí)，元素A5,8的存儲首地址是（B）A. BA+141 B. BA+180C. B

28、A+222 D. BA+2257. 遞歸過程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種稱為（ C ）的數(shù)據(jù)結(jié)構(gòu)。A隊(duì)列 B多維數(shù)組 C棧 D. 線性表 8. 對于單鏈表形式的隊(duì)列，隊(duì)空的條件是（ A ）AFRnil BFRCFnil且Rnil DRF19. 若循環(huán)隊(duì)列以數(shù)組Q0.m-1作為其存儲結(jié)構(gòu)，變量rear表示循環(huán)隊(duì)列中的隊(duì)尾元素的實(shí)際位置，其移動(dòng)按 rear=(rear+1) Mod m 進(jìn)行，變量length表示當(dāng)前循環(huán)隊(duì)列中的元素個(gè)數(shù)，則循環(huán)隊(duì)列的隊(duì)首元素的實(shí)際位置是（ C ）Arear-lengthB(rear-length+m) Mod mC(1+rear+m-length)

29、Mod mDM-length（二）應(yīng)用題1、（10分）假設(shè)一個(gè)準(zhǔn)對角矩陣按以下方式存儲于一維數(shù)組B4m中：01234k4m24m1.寫出由一對下標(biāo)（i，j）表示的k的轉(zhuǎn)換公式。答：i為奇數(shù)時(shí) k=i+j-2i為偶數(shù)時(shí) k=i+j-1合并后可寫成 k=i+j-(i%2)-1 或 k=2(i/2)+j-12、特殊矩陣和稀疏矩陣哪一種壓縮存儲后失去隨機(jī)存取的功能？為什么？答：特殊矩陣指值相同的元素或零元素在矩陣中的分布有一定規(guī)律，因此可以對非零元素分配單元（對值相同元素只分配一個(gè)單元），將非零元素存儲在向量中，元素的下標(biāo)i和j和該元素在向量中的下標(biāo)有一定規(guī)律，可以用簡單公式表示，仍具有隨機(jī)存取功能。

30、而稀疏矩陣是指非零元素和矩陣容量相比很?。╰<<m*n），且分布沒有規(guī)律。用十字鏈表作存儲結(jié)構(gòu)自然失去了隨機(jī)存取的功能。即使用三元組表的順序存儲結(jié)構(gòu)，存取下標(biāo)為i和j的元素時(shí)，要掃描三元組表，下標(biāo)不同的元素，存取時(shí)間也不同，最好情況下存取時(shí)間為O(1)，最差情況下是O(n)，因此也失去了隨機(jī)存取的功能。3、有人說，采用循環(huán)鏈表作為存儲結(jié)構(gòu)的隊(duì)列就是循環(huán)隊(duì)列，你認(rèn)為這種說法對嗎？說明你的理由。答：這種說法是錯(cuò)誤的。隊(duì)列（包括循環(huán)隊(duì)列）是一個(gè)邏輯概念，而鏈表是一個(gè)存儲概念，一個(gè)隊(duì)列是否是循環(huán)隊(duì)列。不取決于它將采用何種存儲結(jié)構(gòu)。根據(jù)實(shí)際的需要，循環(huán)隊(duì)列可以采用順序存儲結(jié)構(gòu)，也可以采用鏈?zhǔn)?/p>

31、存儲結(jié)構(gòu)，包括采用循環(huán)鏈表作為存儲結(jié)構(gòu)。4、指出下列程序段的功能是什么？ (1) void demo1(seqstack *s) int I;arr64;n=0; while (!stackempty(s) arrn+=pop(s); for(I=0;<n;I+) push(s,arrI); (2) void demo2(seqstack *s,int m) seqstack t; int i; initstack(t);while(! Stackempty(s) if(I=pop(s)!=m) push(t,I);while(! Stackempty(t) i=pop(t); push

32、(s,I);（三）算法設(shè)計(jì)題1 試?yán)醚h(huán)隊(duì)列編寫求k階斐波那契序列中前n+1項(xiàng)（）的算法，要求滿足且，其中max為某個(gè)約定的常數(shù)。循環(huán)隊(duì)列的容量為k，因此，在算法執(zhí)行結(jié)束時(shí)，留在循環(huán)隊(duì)列中的元素應(yīng)是所求k階斐波那契序列中的最后k項(xiàng)。答：void GetFib(int k,int n)InitQueue(Q);for(i=0;k<k-1;i+)Q.basei=0;Q.basek-1=1;for(i=0;i<k;i+)printf(“%d”,Q.basei);for(i=k;i<=n;i+)m=i%k;sum=0;for(j=0;j<k;j+)sum+=Q.base(m+

33、j)%k;Q.basem=sum;printf(“%d”,sum);2. 已知num為無符號十進(jìn)制整數(shù)，請寫一非遞歸算法，該算法輸出num對應(yīng)的r進(jìn)制的各位數(shù)字。要求算法中用到的棧采用線性鏈表存儲結(jié)構(gòu)（1<r<10）。 解：typedef struct nodeint data;struct node *next;link;void trans(int num,int r) link *head=NULL,*s; int n; while (num>0) n=num%r; s=(link *)malloc(sizeof(link); s->data=n; s->n

34、ext=head;head=s; num=num/r; printf(“輸出r進(jìn)制的各位數(shù)字：”)； s=head; while (s!=NULL) printf(“%d”,s->data); s=s->next; 三、樹與二叉樹大綱要求：（一） 樹的概念 （二） 二叉樹 1. 二叉樹的定義及其主要特征 2. 二叉樹的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu) 3. 二叉樹的遍歷 4. 線索二叉樹的基本概念和構(gòu)造 5. 二叉排序樹 6. 平衡二叉樹 （三） 樹、森林 1. 樹的存儲結(jié)構(gòu) 2. 森林與二叉樹的轉(zhuǎn)換 3. 樹和森林的遍歷 （四） 樹的應(yīng)用 1. 等價(jià)類問題 2. 哈夫曼（Huffman

35、）樹和哈夫曼編碼 知識點(diǎn)：1. 二叉樹的概念、性質(zhì)（1）掌握樹和二叉樹的定義。（2）理解二叉樹與普通雙分支樹的區(qū)別。二叉樹是一種特殊的樹，這種特殊不僅僅在于其分支最多為2以及其它特征，一個(gè)最重要的特殊之處是在于：二叉樹是有序的。即二叉樹的左右孩子是不可交換的，如果交換了就成了另外一棵二叉樹，這樣交換之后的二叉樹與原二叉樹是不相同的兩棵二叉樹。但是，對于普通的雙分支樹而言，不具有這種性質(zhì)。（3）滿二叉樹和完全二叉樹的概念。（4）重點(diǎn)掌握二叉樹的五個(gè)性質(zhì)及證明方法，并把這種方法推廣到K叉樹。普通二叉樹的五個(gè)性質(zhì)：第i層的最多結(jié)點(diǎn)數(shù)，深度為k的二叉樹的最多結(jié)點(diǎn)數(shù)，n0=n2+1的性質(zhì)，n個(gè)結(jié)點(diǎn)的完全

36、二叉樹的深度，順序存儲二叉樹時(shí)孩子結(jié)點(diǎn)與父結(jié)點(diǎn)之間的換算關(guān)系（序號i結(jié)點(diǎn)的左孩子為：2*i，右孩子為：2*i+1）。2. 掌握二叉樹的順序存儲結(jié)構(gòu)和二叉鏈表、三叉鏈表存儲結(jié)構(gòu)的各自優(yōu)缺點(diǎn)及適用場合，以及二叉樹的順序存儲結(jié)構(gòu)和二叉鏈表存儲結(jié)構(gòu)的相互轉(zhuǎn)換的算法。3. 熟練掌握二叉樹的先序，中序和后序遍歷算法以及按層次遍歷二叉樹的先序、中序和后序三種遍歷算法，劃分的依據(jù)是視其每個(gè)算法中對根結(jié)點(diǎn)數(shù)據(jù)的訪問順序而定。不僅要熟練掌握這三種遍歷的遞歸算法，理解其執(zhí)行的實(shí)際步驟，并且應(yīng)該熟練掌握三種遍歷的非遞歸算法。按層次遍歷二叉樹void LayerOrder(Bitree T)/層序遍歷二叉樹 

37、 InitQueue(Q); /建立工作隊(duì)列  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); /LayerOrder 4. 遍歷是基礎(chǔ)，重點(diǎn)掌握在三種基本遍歷算法的基礎(chǔ)上實(shí)現(xiàn)二叉樹的其它算法如求二叉樹葉子結(jié)點(diǎn)總數(shù)，求二叉樹結(jié)點(diǎn)總數(shù)，求度為1或度為2的結(jié)點(diǎn)總數(shù)，復(fù)制二叉樹，建立二叉樹

38、，交換左右子樹，查找值為n的某個(gè)指定結(jié)點(diǎn)，刪除值為n的某個(gè)指定結(jié)點(diǎn)等等。5. 線索二叉樹的引出，是為避免如二叉樹遍歷時(shí)的遞歸求解。遞歸雖然形式上比較好理解，但是消耗了大量的內(nèi)存資源，如果遞歸層次一多，勢必帶來資源耗盡的危險(xiǎn)。二叉樹線索化的實(shí)質(zhì)是建立結(jié)點(diǎn)在相應(yīng)序列中與其前驅(qū)和后繼之間的直接聯(lián)系。對于線索二叉樹，應(yīng)該掌握：線索化的實(shí)質(zhì)，三種線索化的算法，線索化后二叉樹的遍歷算法，基本線索二叉樹的其它算法問題（如：查找某一類線索二叉樹中指定結(jié)點(diǎn)的前驅(qū)或后繼結(jié)點(diǎn)）。6. 二叉排序樹的中序遍歷結(jié)果是一個(gè)遞增的有序序列。二叉排序樹的形態(tài)取決于元素的輸入順序，二叉排序樹在最差情況下形成單支樹。熟練掌握其建立

39、、查找、插入和刪除算法，以及判斷某棵二叉樹是否二叉排序樹這一問題的遞歸與非遞歸算法。7. 平衡二叉樹是二叉排序樹的優(yōu)化，平衡二叉樹對左右子樹的深度有了限定：深度之差的絕對值不得大于1。掌握平衡二叉樹的四種調(diào)整算法。8. 樹與森林的遍歷，只有兩種遍歷算法：先根與后根（對于森林而言稱作：先序與中序遍歷）。二者的先根與后根遍歷與二叉樹中的遍歷算法是有對應(yīng)關(guān)系的：先根遍歷對應(yīng)二叉樹的先序遍歷，而后根遍歷對應(yīng)二叉樹的中序遍歷。二叉樹使用二叉鏈表分別存放它的左右孩子，樹利用二叉鏈表存儲孩子及兄弟（稱孩子兄弟鏈表），而森林也是利用二叉鏈表存儲孩子及兄弟。掌握樹、森林和二叉樹間的相互轉(zhuǎn)換。9. 簡單掌握等價(jià)類

40、的生成算法。10. 哈夫曼樹為了解決特定問題引出的特殊二叉樹結(jié)構(gòu)，它的前提是給二叉樹的每條邊賦予了權(quán)值，這樣形成的二叉樹按權(quán)相加之和是最小的，一般來說，哈夫曼樹的形態(tài)不是唯一的。理解哈夫曼編碼的基本原理，掌握基于哈夫曼樹生成哈夫曼編碼的方法。練習(xí)題：（一）選擇題：1. 一棵二叉樹的前序遍歷結(jié)果為ABCDEF，中序遍歷結(jié)果為CBAEDF，則后序遍歷結(jié)果為（A）A. CBEFDA B. FEDCBAC. CBEDFA D. 不確定2. 某二叉樹的后序遍歷序列為dabec，中序遍歷序列為debac，則前序遍歷序列為（D）。Aacbed Bdecab Cdeabc Dcedba3. 具有10個(gè)葉子結(jié)點(diǎn)

41、的二叉樹中有（B）個(gè)度為2的結(jié)點(diǎn)。A. 8 B. 9C. 10 D. 114. 樹中所有結(jié)點(diǎn)的度等于所有結(jié)點(diǎn)數(shù)加（ C ）。A0 B1 C1 D25. 設(shè)n，m為一棵二叉樹的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，n在m前的條件是（ C ）A. n在m的右方 B. n是m的祖先C. n在m的左方 D. n是m的子孫6. 利用逐點(diǎn)插入建立序列（50，72，43，85，75，20，35，45，65，30）對應(yīng)的二叉排序樹以后，要查找元素30要進(jìn)行（ B ）次元素間的比較。A4 B. 5C6 D. 77. 在平衡二叉樹中，（ C ）。A任意結(jié)點(diǎn)的左、右子樹結(jié)點(diǎn)數(shù)目相同B任意結(jié)點(diǎn)的左、右子樹高度相同C任意結(jié)點(diǎn)的左右子

42、樹高度之差的絕對值不大于1D不存在度為1的結(jié)點(diǎn)8. 由元素序列（27，16，75，38，51）構(gòu)造平衡二叉樹，則首次出現(xiàn)的最小不平衡子樹的根（即離插入結(jié)點(diǎn)最近且平衡因子的絕對值為2的結(jié)點(diǎn)）為（ D ）A27 B38C51 D. 759. 在二叉樹的順序存儲中，每個(gè)結(jié)點(diǎn)的存儲位置與其父結(jié)點(diǎn)、左右子樹結(jié)點(diǎn)的位置都存在一個(gè)簡單的映射關(guān)系，因此可與三叉鏈表對應(yīng)。若某二叉樹共有n個(gè)結(jié)點(diǎn)，采用三叉鏈表存儲時(shí)，每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域需要d個(gè)字節(jié)，每個(gè)指針域占用4個(gè)字節(jié)，若采用順序存儲，則最后一個(gè)結(jié)點(diǎn)下標(biāo)為k（起始下標(biāo)為1），那么（ A ）時(shí)采用順序存儲更節(jié)省空間。Ad<12n/(k-n) B. d>1

43、2n/(k-n)C. d<12n/(k+n) D. d>12n/(k+n)10. 在常用的描述二叉排序樹的存儲結(jié)構(gòu)中，關(guān)鍵字值最大的結(jié)點(diǎn)（ B ）A左指針一定為空 B. 右指針一定為空C左右指針均為空 D. 左右指針均不為空（二）應(yīng)用題1、一棵滿k叉樹，按層次遍歷（從1開始對全部結(jié)點(diǎn)進(jìn)行編號）存儲在一維數(shù)組中，試計(jì)算編號為u的結(jié)點(diǎn)的第i個(gè)孩子（若存在）的下標(biāo)以及編號為v的結(jié)點(diǎn)的雙親結(jié)點(diǎn)（若存在）的下標(biāo)。答：結(jié)點(diǎn)下標(biāo)為u的結(jié)點(diǎn)的第i個(gè)孩子的下標(biāo)：結(jié)點(diǎn)下標(biāo)為v的結(jié)點(diǎn)的父母結(jié)點(diǎn)的下標(biāo)：2、試求有n個(gè)葉結(jié)點(diǎn)的非滿的完全二叉樹的高度.答：完全二叉樹中葉子結(jié)點(diǎn)數(shù)為n，則根據(jù)完全二叉樹的性質(zhì)，度

44、為2的結(jié)點(diǎn)數(shù)是n-1，而完全二叉樹中，度為1的結(jié)點(diǎn)數(shù)至多為1，所以具有n個(gè)葉子結(jié)點(diǎn)的完全二叉樹結(jié)點(diǎn)數(shù)是n+(n-1)+1=2n或2n-1（有或無度為1的結(jié)點(diǎn)）。由于具有2n(或2n-1)個(gè)結(jié)點(diǎn)的完全二叉樹的深度是ëlog2(2n)û+1( 或ëlog2(2n-1)û+1)，即élog2nù+1,故n個(gè)葉結(jié)點(diǎn)的非滿的完全二叉樹的高度是élog2nù+1。（最下層結(jié)點(diǎn)數(shù)>=2）。3、已知一棵度為m的樹中有N1個(gè)度為1的結(jié)點(diǎn)，N2個(gè)度為2的結(jié)點(diǎn)，Nm個(gè)度為m的結(jié)點(diǎn)，問該樹中有多少個(gè)葉子結(jié)點(diǎn)。請寫出推導(dǎo)過程。答：設(shè)N

45、為總結(jié)點(diǎn)數(shù)，N0為葉子結(jié)點(diǎn)數(shù)則：N=N0+N1+N2+Nm又有：N-1=度的總數(shù)，則：N-1=N1*1+N2*2+Nm*m則有：N0=1+N2+2N3+(m-1)Nm4有七個(gè)帶權(quán)結(jié)點(diǎn)，其權(quán)值分別為3,7,8,2,6,10,14，試以它們?yōu)槿~子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，并計(jì)算出帶權(quán)路徑長度WPL。答：WPL = 3*4+7*3+8*3+2*4+6*3+10*2+14*2 = 1315、給定字母a,b,c,d,e的使用頻率為0.09,0.17,0.2,0.23,0.31。設(shè)計(jì)以該權(quán)值為基礎(chǔ)的哈夫曼樹，并給出哈夫曼編碼？平均長度是多少？答：構(gòu)造的哈夫曼樹如下：cc d e a b哈夫曼編碼如下：c(00

46、)d(01)a(100)b(101)e(11)平均長度=0.09*3+0.17*3+0.2*2+0.23*2+0.31*2=2.266. 從概念上講，樹，森林和二叉樹是三種不同的數(shù)據(jù)結(jié)構(gòu)，將樹，森林轉(zhuǎn)化為二叉樹的基本目的是什么，并指出樹和二叉樹的主要區(qū)別。 解：樹的孩子兄弟鏈表表示法和二叉樹二叉鏈表表示法，本質(zhì)是一樣的，只是解釋不同，也就是說樹（樹是森林的特例，即森林中只有一棵樹的特殊情況）可用二叉樹唯一表示，并可使用二叉樹的一些算法去解決樹和森林中的問題。樹和二叉樹的區(qū)別有：一是二叉樹的度至多為2，樹無此限制；二是二叉樹有左右子樹之分，即使在只有一個(gè)分枝的情況下， 也必須指出是左子樹還是右子

47、樹，樹無此限制；7. 如果給出了一個(gè)二叉樹結(jié)點(diǎn)的前序序列和中序序列，能否構(gòu)造出此二叉樹?若能，請證明之。若不能，請給出反例。如果給出了一個(gè)二叉樹結(jié)點(diǎn)的前序序列和后序序列，能否構(gòu)造出此二叉樹?若能，請證明之。若不能，請給出反例。解：給定二叉樹前序序列和中序序列，可以唯一確定該二叉樹。因?yàn)榍靶蛐蛄械牡谝粋€(gè)元素是根結(jié)點(diǎn)，該元素將二叉樹中序序列分成兩部分，左邊（設(shè)l個(gè)元素）表示左子樹，若左邊無元素，則說明左子樹為空；右邊（設(shè)r個(gè)元素）是右子樹，若為空，則右子樹為空。根據(jù)前序遍歷中“根左子樹右子樹”的順序，則由從第二元素開始的l個(gè)結(jié)點(diǎn)序列和中序序列根左邊的l個(gè)結(jié)點(diǎn)序列構(gòu)造左子樹，由前序序列最后r個(gè)元素序

48、列與中序序列根右邊的r個(gè)元素序列構(gòu)造右子樹。由二叉樹的前序序列和后序序列不能唯一確定一棵二叉樹，因無法確定左右子樹兩部分。例如，任何結(jié)點(diǎn)只有左子樹的二叉樹和任何結(jié)點(diǎn)只有右子樹的二叉樹，其前序序列相同，后序序列相同，但卻是兩棵不同的二叉樹。（三）算法設(shè)計(jì)題1請利用棧的基本操作寫出先序遍歷二叉樹的非遞歸形式的算法。要求以二叉鏈表作為二叉樹的存儲結(jié)構(gòu)。函數(shù)原型如下：void PreOrder(Bitree T)；答：void PreOrder(Bitree T)InitStack(S);Push(S,T);while(!StackEmpty(S)while(Gettop(S,p)&&

49、p)visit(p->data);push(S,p->lchild);pop(S,p);if(!StackEmpty(S)pop(S,p);push(S,p->rchlid);2試寫一個(gè)判別給定二叉樹是否為二叉排序樹的遞歸算法，設(shè)此二叉樹以二叉鏈表作存儲結(jié)構(gòu)，且樹中結(jié)點(diǎn)的關(guān)鍵字均不同。函數(shù)原型如下：int Is_BSTree（BiTree T）；答：int last=0,flag=1;int Is_BSTree（BiTree T）if(T->lchild&&flag)Is_BSTree(T->lchild);if(T->data<las

50、t)flag=0;last=T->data;if(T->rchild&&flag)Is_BSTree(T->rchild);return flag;3假設(shè)一個(gè)僅包含二元運(yùn)算符的算術(shù)表達(dá)式以鏈表形式存儲在二叉樹BT中，寫出計(jì)算該算術(shù)表達(dá)式值的算法。答：以二叉樹表示算術(shù)表達(dá)式，根結(jié)點(diǎn)用于存儲運(yùn)算符。若能先分別求出左子樹和右子樹表示的子表達(dá)式的值，最后就可以根據(jù)根結(jié)點(diǎn)的運(yùn)算符的要求，計(jì)算出表達(dá)式的最后結(jié)果。typedef struct node ElemType data; float val;char optr; /只取+， -， *，/struct node *lchild，*rchild BiNode,*BiTree;float PostEval(BiTree bt) / 以后序遍歷算法求以二叉樹表示的算術(shù)表達(dá)式的值float lv,rv;if(bt!=null)lv=PostEval(bt->lchild); / 求左子樹表示的子表達(dá)式的值rv=PostEval(bt->rchild); / 求右子樹表示的子表達(dá)式的值switch(bt-&