《數(shù)據(jù)結(jié)構(gòu)》習(xí)題集復(fù)習(xí)課程

1、Good is good, but better carries it.精益求精，善益求善。數(shù)據(jù)結(jié)構(gòu)習(xí)題集-1緒論一、選擇題：1、下列算法的時(shí)間復(fù)雜度是（）for(i=0;in;i+)ci=i；AO（1）BO（n）CO（log2n）DO（nlog2n）2、數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址，這種方法稱為（）A索引存儲(chǔ)方法B順序存儲(chǔ)方法C鏈?zhǔn)酱鎯?chǔ)方法D散列存儲(chǔ)方法解析：數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（映像）稱為數(shù)據(jù)的物理（存儲(chǔ)）結(jié)構(gòu)。它包括數(shù)據(jù)元素的表示和關(guān)系的表示。數(shù)據(jù)元素之間的關(guān)系有兩種不同的表示方法：順序映象和非順序映象，并由此得到兩種不同的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)

2、結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。順序存儲(chǔ)方法：它是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)，由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)是一種最基本的存儲(chǔ)表示方法，通常借助于程序設(shè)計(jì)語言中的數(shù)組來實(shí)現(xiàn)。鏈?zhǔn)酱鎯?chǔ)方法：它不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通常借助于程序設(shè)計(jì)語言中的指針類型來實(shí)現(xiàn)。索引存儲(chǔ)方法：除建立存儲(chǔ)結(jié)點(diǎn)信息外，還建立附加的索引表來標(biāo)識(shí)結(jié)點(diǎn)的地址。散列存儲(chǔ)方法：就是根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址。數(shù)據(jù)結(jié)構(gòu)中，邏輯上（邏輯結(jié)構(gòu)：

3、數(shù)據(jù)元素之間的邏輯關(guān)系）可以把數(shù)據(jù)結(jié)構(gòu)分成線性結(jié)構(gòu)和非線性結(jié)構(gòu)。線性結(jié)構(gòu)的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)，線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種順序存取的存儲(chǔ)結(jié)構(gòu)。線性表若采用鏈?zhǔn)酱鎯?chǔ)表示時(shí)所有結(jié)點(diǎn)之間的存儲(chǔ)單元地址可連續(xù)可不連續(xù)。邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、所含結(jié)點(diǎn)個(gè)數(shù)都無關(guān)。3、以下哪一個(gè)術(shù)語與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)？（）。A.順序表B.鏈表C.散列表D.隊(duì)列4、算法在發(fā)生非法操作時(shí)可以做出處理的特性稱為（）。A正確性B易讀性C健壯性D高效性5、邏輯結(jié)構(gòu)是指數(shù)據(jù)元素的（）。A關(guān)聯(lián)方式B存儲(chǔ)方式C結(jié)構(gòu)D數(shù)據(jù)項(xiàng)6、研究數(shù)據(jù)結(jié)構(gòu)就是研究（）。A數(shù)據(jù)的邏輯結(jié)構(gòu)B數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C數(shù)據(jù)的邏輯結(jié)

4、構(gòu)和存儲(chǔ)結(jié)構(gòu)D數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其數(shù)據(jù)的運(yùn)算7、從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（）。A.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)8、以下有關(guān)數(shù)據(jù)的敘述中錯(cuò)誤的是（）。A計(jì)算機(jī)能夠處理的數(shù)據(jù)包括整數(shù)、實(shí)數(shù)、字符、聲音、圖像等B數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它取決于數(shù)據(jù)的存儲(chǔ)方式C數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)依賴于計(jì)算機(jī)語言D數(shù)據(jù)的運(yùn)算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的9、數(shù)據(jù)的基本單位是（）。A.數(shù)據(jù)結(jié)構(gòu)B.數(shù)據(jù)元素C.數(shù)據(jù)項(xiàng)D.文件10、下列算法的時(shí)間復(fù)雜度是（）for(i=0;im;i+)for(j=0;jn;j+)aij=i*j；AO（m2）BO（

5、n2）CO（mn）DO（m+n）11、算法分析的兩個(gè)主要方面是（）。A正確性和簡明性B數(shù)據(jù)復(fù)雜性和程序復(fù)雜性C可讀性和可維護(hù)性D時(shí)間復(fù)雜性和空間復(fù)雜性二、填空題：1、數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，它包括三方面的內(nèi)容，分別是數(shù)據(jù)的邏輯結(jié)構(gòu)、（）和（）。2、數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的（）無關(guān)，是獨(dú)立于計(jì)算機(jī)的。3、()結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。4、程序段“for(i=1;i=n;i+)k+;for(j=1;j=n;j+)x=x+k;”的時(shí)間復(fù)雜度為()。5、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）可以用（）、（）、（）及散列存儲(chǔ)等四種存儲(chǔ)方法表示。判斷

6、題：1、順序存儲(chǔ)方式優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入和刪除運(yùn)算效率高。（）2、順序存儲(chǔ)結(jié)構(gòu)屬于靜態(tài)存儲(chǔ)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)屬于動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)。（）3、線性表的鏈接存儲(chǔ)，表中元素的邏輯順序與物理順序一定相同。（）4、數(shù)據(jù)的機(jī)內(nèi)表示稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。（）5、在線性表的順序存儲(chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上并不一定相鄰。（）6、數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（）7、基于某種邏輯結(jié)構(gòu)之上的運(yùn)算，其實(shí)現(xiàn)是惟一的。（）參考答案（緒論）一、選擇題1234567891011BDDCADCBACD二、填空題1、數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，它包括三方面的內(nèi)容，分別是數(shù)據(jù)的邏輯結(jié)構(gòu)、（存儲(chǔ)

7、結(jié)構(gòu)）和（運(yùn)算）。2、數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的（）無關(guān)，是獨(dú)立于計(jì)算機(jī)的。3、(邏輯)結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。4、程序段“for(i=1;i=n;i+)k+;for(j=1;jnext=P-next;P-next=SBP-next=S-next;S-next=P；CP-next=P;P-next=S；DP-next=S;S-next=P；3、在已知頭指針的單鏈表中，要在其尾部插入一新結(jié)點(diǎn)，其算法所需的時(shí)間復(fù)雜度為（）A（1）B（log2n）CO（n）DO（n2）解析：單就插入運(yùn)算而言，算法時(shí)間復(fù)雜度為（1），但要將指針定位到鏈表末尾，指針移動(dòng)的時(shí)間復(fù)雜度為O

8、（n）；4、對(duì)于只在表的首、尾兩端進(jìn)行插入操作的線性表，宜采用的存儲(chǔ)結(jié)構(gòu)為（）A順序表B用頭指針表示的單循環(huán)鏈表C用尾指針表示的單循環(huán)鏈表D單鏈表解析：尾指針是指向終端結(jié)點(diǎn)的指針，用它來表示單循環(huán)鏈表可以使得查找鏈表的開始結(jié)點(diǎn)和終端結(jié)點(diǎn)都很方便，設(shè)一帶頭結(jié)點(diǎn)的單循環(huán)鏈表，其尾指針為rear，則開始結(jié)點(diǎn)和終端結(jié)點(diǎn)的位置分別是rear-next-next和rear,查找時(shí)間都是O(1)。若用頭指針來表示該鏈表，則查找終端結(jié)點(diǎn)的時(shí)間為O(n)。5、線性表是（）A一個(gè)有限序列，可以為空B一個(gè)有限序列，不能為空C一個(gè)無限序列，可以為空D一個(gè)無限序列，不能為空6、在n個(gè)結(jié)點(diǎn)的雙鏈表的某個(gè)結(jié)點(diǎn)前插入一個(gè)結(jié)點(diǎn)

9、的時(shí)間復(fù)雜度是（）AO（n）BO（1）CO（log2n）DO（n2）7、線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的地址（）A必須是連續(xù)的B必須是不連續(xù)的C連續(xù)與否均可D必須有相等的間隔8、在單鏈表中，增加頭結(jié)點(diǎn)的目的是（）A使單鏈表至少有一結(jié)點(diǎn)B標(biāo)志表中首結(jié)點(diǎn)位置C方便運(yùn)算的實(shí)現(xiàn)D說明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)9、帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（）Ahead=NULL；Bhead-next=NULL；Chead-next=head；Dhead!=NULL；10、在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜度為（）A（1）B（n）C（n2）D（log2n）11、下列有關(guān)線性表

10、的敘述中，正確的是（）A線性表中的元素之間是線性關(guān)系B線性表中至少有一個(gè)元素C線性表中任何一個(gè)元素有且僅有一個(gè)直接前趨D線性表中任何一個(gè)元素有且僅有一個(gè)直接后繼12、在單鏈表中，存儲(chǔ)每個(gè)結(jié)點(diǎn)需有兩個(gè)域，一個(gè)是數(shù)據(jù)域，另一個(gè)是指針域，它指向該結(jié)點(diǎn)的（）A直接前趨B直接后繼C開始結(jié)點(diǎn)D終端結(jié)點(diǎn)13、將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是（）。AnB.2n-1C.2nD.n-114、鏈表不具有的特點(diǎn)是（）。A隨機(jī)訪問B不必事先估計(jì)存儲(chǔ)空間C插入刪除時(shí)不需移動(dòng)元素D所需的空間與線性表成正比15、在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接前趨，若在p，q之間插入s結(jié)點(diǎn)，則執(zhí)

11、行的操作是（）。As-next=p-next;p-next=s;Bq-next=s;s-next=p;Cp-next=s-next;s-next=p;Dp-next=s;s-next=q;16、鏈表具有的特點(diǎn)是（）。A可隨機(jī)訪問任一元素B插入、刪除需要移動(dòng)元素C不必事先估計(jì)存儲(chǔ)空間D存儲(chǔ)空間是靜態(tài)分配的17、一個(gè)順序表一旦說明，其中可用空間大?。ǎ〢已固定B可以改變C不能固定D動(dòng)態(tài)變化18、若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前趨元素，則采用（）存儲(chǔ)方式最節(jié)省時(shí)間。順序表B單鏈表C雙向鏈表D單循環(huán)鏈表19、兩個(gè)指針P和Q，分別指向單鏈表的兩個(gè)元素，P所指元素是Q所指元素的前驅(qū)

12、的條件是（）。AP-next=QBQ-next=PCP=QDP-next=Q-next20、鏈表不具有的特點(diǎn)是（）。A可隨機(jī)訪問任一元素B插入、刪除不需要移動(dòng)元素C不必事先估計(jì)存儲(chǔ)空間D所需空間與線性表長度成正比21、下面關(guān)于線性表的敘述中，錯(cuò)誤的是（）。A線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元B線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作C線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元D線性表采用鏈接存儲(chǔ)，便于進(jìn)行插入和刪除操作22、在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O(1)的操作是（）。A訪問第i個(gè)結(jié)點(diǎn)（1in）和求第i個(gè)結(jié)點(diǎn)的直接前趨（2in）B在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（

13、1in）C刪除第i個(gè)結(jié)點(diǎn)（1in）D將n個(gè)結(jié)點(diǎn)從小到大排序23、在一個(gè)單鏈表中，若刪除p指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行的操作為（）。Aq=p-next;p-next=p-next-next;free(q);Bp=p-next;q=p-next;p=q-next;free(q);Cq=p-next-next;p=p-next;free(q);Dp=p-next-next;q=p-next;free(q);填空題：1、在雙鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p，其時(shí)間復(fù)雜度為（）。2、在僅有尾指針R指示的單循環(huán)鏈表R中，在表尾插入一個(gè)結(jié)點(diǎn)S的語句序列是（）。3、在帶頭結(jié)點(diǎn)的雙鏈表中，指針?biāo)附Y(jié)點(diǎn)是開始結(jié)點(diǎn)的條件是（

14、）。4、在具有n個(gè)結(jié)點(diǎn)的雙鏈表中做插入、刪除運(yùn)算，平均時(shí)間復(fù)雜度為（）。5、在一個(gè)長度為n的順序表中第i個(gè)元素（1in）之前插入一個(gè)元素時(shí)，需向后移動(dòng)（）個(gè)元素。6、在雙循環(huán)鏈表中，若要在指針p所指結(jié)點(diǎn)之前插入指針s所指的結(jié)點(diǎn)，則需執(zhí)行下列語句：s-prior=p-prior;p-prior-next=s;()和p-prior=s;。7、已知指針p指向雙向鏈表中的一個(gè)結(jié)點(diǎn)（非首結(jié)點(diǎn)、非尾結(jié)點(diǎn)），則將結(jié)點(diǎn)s插入在p結(jié)點(diǎn)的直接后繼位置的語句是（）s-prior=p；s-next-prior=s；p-next=s;8、已知帶表頭結(jié)點(diǎn)的單鏈表L，指針p指向L鏈表中的一個(gè)結(jié)點(diǎn)（非首結(jié)點(diǎn)、非尾結(jié)點(diǎn)），則刪

15、除結(jié)點(diǎn)p的直接后繼結(jié)點(diǎn)的語句是（）；刪除首結(jié)點(diǎn)的語句是（）。判斷題1、在有序的順序表和有序的鏈表上，均可以使用折半查找法來提高查找速度。（）2、順序存儲(chǔ)的線性表可以隨機(jī)存取。（）3、線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。（）程序設(shè)計(jì)題數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)類型定義如下：順序存儲(chǔ)：typedefstructint*base;intlength;intlistsize;sqlist;鏈?zhǔn)酱鎯?chǔ)：typedefstructLinkListintdata;structLinkList*next;Node,*LinkList;1、已知帶頭結(jié)點(diǎn)的單鏈表head中的結(jié)點(diǎn)是按整數(shù)值遞增排序的，寫一算法將值為x

16、的結(jié)點(diǎn)插入到表head中，使head仍然有序。2、用尾插法建立帶頭結(jié)點(diǎn)的單鏈表。3、用頭插法建立帶頭結(jié)點(diǎn)的單鏈表。4、對(duì)給定的單鏈表L，編寫一個(gè)刪除L中值為x的結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)算法。5、用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表的就地逆置算法，即將（a1,a2,ai,an）逆置為（an,ai,a2,a1）;6、用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表的就地逆置算法，即將（a1,a2,ai,an）逆置為（an,ai,a2,a1）;7、使用順序存儲(chǔ)結(jié)構(gòu)分別實(shí)現(xiàn)A=AB和A=AB運(yùn)算；參考答案（線性表）一、選擇題1234567891011121314151617181920212223BABCABCCBBABBABCBAAABAA

17、二、填空題1、在雙鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p，其時(shí)間復(fù)雜度為（O(1)）。2、在僅有尾指針R指示的單循環(huán)鏈表R中，在表尾插入一個(gè)結(jié)點(diǎn)S的語句序列是（P=R;while(P-next!=NULL)P=P-next;P-next=S;S-next=NULL;）。3、在帶頭結(jié)點(diǎn)的雙鏈表中，指針?biāo)附Y(jié)點(diǎn)是開始結(jié)點(diǎn)的條件是（P=L）。4、在具有n個(gè)結(jié)點(diǎn)的雙鏈表中做插入、刪除運(yùn)算，平均時(shí)間復(fù)雜度為（O(1)）。5、在一個(gè)長度為n的順序表中第i個(gè)元素（1in）之前插入一個(gè)元素時(shí)，需向后移動(dòng)（n-i+1）個(gè)元素。6、在雙循環(huán)鏈表中，若要在指針p所指結(jié)點(diǎn)之前插入指針s所指的結(jié)點(diǎn)，則需執(zhí)行下列語句：s-prior=

18、p-prior;p-prior-next=s;(s-next=p;)和p-prior=s;。7、已知指針p指向雙向鏈表中的一個(gè)結(jié)點(diǎn)（非首結(jié)點(diǎn)、非尾結(jié)點(diǎn)），則將結(jié)點(diǎn)s插入在p結(jié)點(diǎn)的直接后繼位置的語句是（p-next=s;）s-prior=p；s-next-prior=s；p-next=s;8、已知帶表頭結(jié)點(diǎn)的單鏈表L，指針p指向L鏈表中的一個(gè)結(jié)點(diǎn)（非首結(jié)點(diǎn)、非尾結(jié)點(diǎn)），則刪除結(jié)點(diǎn)p的直接后繼結(jié)點(diǎn)的語句是（q=p-next;p-next=q-next;free(q);）；刪除首結(jié)點(diǎn)的語句是（q=L-next;L=L-next;free(q);）。三、判斷題1、在有序的順序表和有序的鏈表上，均可以使

19、用折半查找法來提高查找速度。（）2、順序存儲(chǔ)的線性表可以隨機(jī)存取。（）3、線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。（）四、程序設(shè)計(jì)題1、已知帶頭結(jié)點(diǎn)的單鏈表head中的結(jié)點(diǎn)是按整數(shù)值遞增排序的，寫一算法將值為x的結(jié)點(diǎn)插入到表head中，使head仍然有序。P=head-next;While(p-next!=NULL&p-datanext;/指針定位p-next=x;x-next=p-next;2、用尾插入法建立帶頭結(jié)點(diǎn)的單鏈表。請(qǐng)參考教材“數(shù)據(jù)結(jié)構(gòu)-清華大學(xué)嚴(yán)尉敏著評(píng)p29-p30”;3、用頭插入法建立帶頭結(jié)點(diǎn)的單鏈表。請(qǐng)參考教材“數(shù)據(jù)結(jié)構(gòu)-清華大學(xué)嚴(yán)尉敏著評(píng)p29-p30”;4、對(duì)給

20、定的單鏈表L，編寫一個(gè)刪除L中值為x的結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)算法。/算法思路：先判斷L中是否存在值為x的結(jié)點(diǎn)，若不存在，返回錯(cuò)誤（-1）；若存在，用一指針p定位到值為x的第一結(jié)點(diǎn),用另一個(gè)指針q定位到值為x的第一結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，然后實(shí)施刪除操作；重點(diǎn)語句為：p=L-next;/p指向第一個(gè)結(jié)點(diǎn)whili(p-data!=x&p-next!=NULL)p=p-next;if(p=NULL)ruturnerror;/不存在elsep=L-next;while(p-next-next-data!=x)p=p-next;q=p-next;p-next=p-next-next;free(q);5、用順序存儲(chǔ)

21、結(jié)構(gòu)實(shí)現(xiàn)線性表的就地逆置算法，即將（a1,a2,ai,an）逆置為（an,ai,a2,a1）;重點(diǎn)語句：for(i=0;irear=(qrear+1)%maxsize;20、棧和隊(duì)列都是（）。A限制存取點(diǎn)的線性結(jié)構(gòu)B限制存取點(diǎn)的非線性結(jié)構(gòu)C順序存儲(chǔ)的線性結(jié)構(gòu)D鏈?zhǔn)酱鎯?chǔ)的線性結(jié)構(gòu)21、實(shí)現(xiàn)遞歸調(diào)用屬于（）的應(yīng)用。A隊(duì)列B棧C數(shù)組D樹填空題：1、循環(huán)隊(duì)列用數(shù)組datam存放其元素值，已知其頭、尾指針分別是front和rear，則當(dāng)前隊(duì)列中元素的個(gè)數(shù)是（）。2、棧頂?shù)奈恢檬请S著（）操作而變化的。3、假設(shè)以S和X分別表示進(jìn)棧和退棧操作，則對(duì)輸入序列a，b，c，d，e進(jìn)行一系列棧操作SSXSXSSXXX

22、之后，得到的輸出序列為（）。4、隊(duì)列的隊(duì)尾位置隨著（）而變化。5、在（）的情況下，鏈隊(duì)列的出隊(duì)操作需要修改尾指針。6、從棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)，并將被刪除的結(jié)點(diǎn)的值保存在x中，其操作步驟為（）；top=top-next;。7、用數(shù)組Am來存放循環(huán)隊(duì)列q的元素，且它的頭、尾指針分別為front和rear，隊(duì)列滿足條件(q.rear+1)%m=q.front,則隊(duì)列中當(dāng)前的元素個(gè)數(shù)為（）。8、順序棧s存儲(chǔ)在數(shù)組s-datamax中，對(duì)s進(jìn)行出棧操作，執(zhí)行的語句序列是（）。9、以下運(yùn)算實(shí)現(xiàn)在循環(huán)隊(duì)列中的初始化操作voidinitqueue(seqqueue*q)q-front=0;()

23、;判斷題：1、循環(huán)隊(duì)列中無上溢現(xiàn)象。（）2、循環(huán)隊(duì)列只有下溢，沒有上溢。（）3、對(duì)順序棧而言，在棧滿狀態(tài)，如果此時(shí)再作進(jìn)棧運(yùn)算，則會(huì)發(fā)生“下溢”。（）4、順序隊(duì)列和循環(huán)隊(duì)列的隊(duì)滿和隊(duì)空的條件是一樣的。（）5、為解決隊(duì)列“假滿”問題，可以采用循環(huán)數(shù)組實(shí)現(xiàn)隊(duì)列存儲(chǔ)。（）6、隊(duì)列是后進(jìn)先出表。（）7、棧是后進(jìn)先出表。（）應(yīng)用題：設(shè)有一個(gè)棧，元素進(jìn)棧的次序?yàn)锳，B，C，D，E，寫出下列出棧序列的操作序列。（1）CBADE（2）ACBED，其中I為進(jìn)棧操作，O為出棧操作。2、如果編號(hào)為1、2、3的三輛列車進(jìn)入一個(gè)棧式結(jié)構(gòu)的站臺(tái)，那么可能得到的三輛列車出站序列有哪些？不可能出現(xiàn)的序列是什么？程序設(shè)計(jì)題：1

24、、寫出循環(huán)隊(duì)列入隊(duì)操作的函數(shù)。參考答案（棧和隊(duì)列）一、選擇題123456789101112131415161718192021AABDBCDBCBDCCBABBBCAB二、填空題1、循環(huán)隊(duì)列用數(shù)組datam存放其元素值，已知其頭、尾指針分別是front和rear，則當(dāng)前隊(duì)列中元素的個(gè)數(shù)是（(rear-front+maxsize）%maxsize）。2、棧頂?shù)奈恢檬请S著（入棧和出棧）操作而變化的。3、假設(shè)以S和X分別表示進(jìn)棧和退棧操作，則對(duì)輸入序列a，b，c，d，e進(jìn)行一系列棧操作SSXSXSSXXX之后，得到的輸出序列為（bceda）。4、隊(duì)列的隊(duì)尾位置隨著（入隊(duì)列操作變化）而變化。5、在（鏈

25、隊(duì)列為空）的情況下，鏈隊(duì)列的出隊(duì)操作需要修改尾指針。分析：Q.rear=h;6、從棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)，并將被刪除的結(jié)點(diǎn)的值保存在x中，其操作步驟為（x=top-data）。7、用數(shù)組Am來存放循環(huán)隊(duì)列q的元素，且它的頭、尾指針分別為front和rear，隊(duì)列滿足條件(q.rear+1)%m=q.front,則隊(duì)列中當(dāng)前的元素個(gè)數(shù)為（0）。8、順序棧s存儲(chǔ)在數(shù)組s-datamax中，對(duì)s進(jìn)行出棧操作，執(zhí)行的語句序列是（stop-）。9、以下運(yùn)算實(shí)現(xiàn)在循環(huán)隊(duì)列中的初始化操作voidinitqueue(seqqueue*q)q-front=0;(qbase=(qelemtype*)

26、malloc(maxsize*sizeof(qelemtype);qrear=0;);三、判斷題1、循環(huán)隊(duì)列中無上溢現(xiàn)象。（）2、循環(huán)隊(duì)列只有下溢，沒有上溢。（）3、對(duì)順序棧而言，在棧滿狀態(tài)，如果此時(shí)再作進(jìn)棧運(yùn)算，則會(huì)發(fā)生“下溢”。（）4、順序隊(duì)列和循環(huán)隊(duì)列的隊(duì)滿和隊(duì)空的條件是一樣的。（）5、為解決隊(duì)列“假滿”問題，可以采用循環(huán)隊(duì)列實(shí)現(xiàn)隊(duì)列存儲(chǔ)。（）6、隊(duì)列是后進(jìn)先出的線性表。（）7、棧是后進(jìn)先出表。（）四、應(yīng)用題1、設(shè)有一個(gè)棧，元素進(jìn)棧的次序?yàn)锳，B，C，D，E，寫出下列出棧序列的操作序列。（1）CBADE（2）ACBED，其中I為進(jìn)棧操作，O為出棧操作。參考答案：（1）IIIOOOIOIO

27、(2)IOIIOOIIOO2、如果編號(hào)為1、2、3的三輛列車順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的站臺(tái)，那么可能得到的三輛列車出站序列有哪些？不可能出現(xiàn)的序列是什么？參考答案：可能得到的三輛列車出站序列有1，2，3；1，3，2；2，1，3；2，1，3；2，3，1；其他3個(gè)數(shù)字的另外1個(gè)排列不可能出現(xiàn)，即3，1，2。五、程序設(shè)計(jì)題1、寫出循環(huán)隊(duì)列入隊(duì)操作的函數(shù)。請(qǐng)參考清華大學(xué)出版社嚴(yán)蔚敏編著的數(shù)據(jù)結(jié)構(gòu)C語言版p65。串和數(shù)組（含參考答案）一、單選題1下列那些為空串（）A）S=“”B）S=“”C）S=“”D）S=“”答案：B2S1=“ABCD”，S2=“CD”則S2在S3中的位置是（）A）1B）2C）3D）4答案

28、：C3假設(shè)S=“abcaabcaaabca”，T=“bca”，Index(S,T,3)的結(jié)果是（）A）2B）6C）11D）0答案：B4在串中，對(duì)于SubString(&Sub,S,pos,len)基本操作，pos和len的約束條件是（）A）0posStrLength(S)+1且1=len=StrLength(S)-pos+1B）0posStrLength(S)+1且0=len=StrLength(S)-pos-1C）1=pos=StrLength(S)且0=len=StrLength(S)-pos+1D）1=pos=StrLength(S)且1=len=StrLength(S)-pos-1答案

29、：C5串是一種特殊的線性表，其特殊性體現(xiàn)在()。A可以順序存儲(chǔ)B.數(shù)據(jù)元素是一個(gè)字符C可以鏈接存儲(chǔ)D.數(shù)據(jù)元素可以是多個(gè)字符答：B6串是()。A少于一個(gè)字母的序列B.任意個(gè)字母的序列C不少于一個(gè)字符的序列D.有限個(gè)字符的序列答：D7串的長度是()。A串中不同字母的個(gè)數(shù)B.串中不同字符的個(gè)數(shù)C串中所含的字符的個(gè)數(shù)D.串中所含字符的個(gè)數(shù)，且大于0答：C8設(shè)有S1=ABCDEFG，S2=PQRST，函數(shù)con(x，y)返回x和y串的連接串，subs(I，j)返回串S的從序號(hào)I的字符開始的j個(gè)字符組成的子串，len(s)返回串s的長度，則con(subs(S1，2，len(S2)，subs(S1，le

30、n(S2)，2)的結(jié)果是()。ABCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF答：D9若某串的長度小于一個(gè)常數(shù)，則采用()存儲(chǔ)方式最為節(jié)省空間。A鏈?zhǔn)紹.堆結(jié)構(gòu)C.順序表答：C二、填空題：1串是每個(gè)結(jié)點(diǎn)僅由一個(gè)字符組成的_。答：線性表2在串中，SubString(“student”,5,0)的結(jié)果是_。答：“”3假設(shè)S=“abcaabcaaabca”，T=“bca”，V=“x”，Replace(S,T,V)結(jié)果是_。答：“axaxaax”4在串中，對(duì)于StrCompare(S,T)基本操作，若ST，返回值_。答：05在串順序存儲(chǔ)結(jié)構(gòu)中，實(shí)現(xiàn)串操作的原操作為_。答：字符序列的復(fù)制

31、6串與線性表在邏輯結(jié)構(gòu)上極為相似，區(qū)別僅在于_；在基本操作上差別很大，線性表的基本操作大多數(shù)以_作為操作對(duì)象，而串的基本操作通常以作為操作對(duì)象。答：串的數(shù)據(jù)對(duì)象約束為字符集“單個(gè)元素”“串的整體”7兩個(gè)串相等的充分必要條件是_且_。答：兩個(gè)串的串長相等各個(gè)對(duì)應(yīng)位置的字符都相等8空串是指_，空格串是指_。答：不含任何字符的串僅含空格字符的串三、判斷題1空串是由空白字符組成的串（FALSE）2串的定長順序結(jié)構(gòu)是用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列，按照預(yù)定義的大小，為每個(gè)定義的串變量分配一個(gè)固定長度的存儲(chǔ)區(qū)。(TRUE)3串的堆分配存儲(chǔ)表示是用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列，但它們

32、的存儲(chǔ)空間是在程序執(zhí)行過程中動(dòng)態(tài)分配得到的。（TRUE）4串中StrInsert(&S,pos,T)基本操作是最小的操作子集（FALSE）5串是由有限個(gè)字符構(gòu)成的連續(xù)序列，串長度為串中字符的個(gè)數(shù)，子串是主串中字符構(gòu)成的有限序列。(FALSE)(錯(cuò)：子串是主串中連續(xù)的字符構(gòu)成的有限序列)(題源：胡元義，C版數(shù)據(jù)結(jié)構(gòu)課程輔導(dǎo)與習(xí)題解析，p80，4.2.1(判斷題)_1)6如果一個(gè)串中的所有字符均在另一串中出現(xiàn)，那么則說明前者是后者的子串。(FALSE)(錯(cuò)：是否連續(xù)是關(guān)鍵)(題源：陳明，C版實(shí)用數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)，p109，(判斷題)_2)7串類型的最小操作子集不能利用其他串操作來實(shí)現(xiàn)，反之，其他串操作

33、（除串清除ClearString和串銷毀DestroyString外）均可在最小操作子集上實(shí)現(xiàn)。(TRUE)(題源：根據(jù)教材p72自編)四、簡答題1已知串s=(xyz)*，t=(x+z)*y，試?yán)么幕具\(yùn)算將s串轉(zhuǎn)化為t串，t串轉(zhuǎn)化為s串。(題源：寧正元，C版題解，p40，4.2_3)答：concat(replace(substring(sub,s,1,5),y,+),replace(substring(sub,s,6,1),*，*y)concat(replace(substring(sub,t,1,5),+,y),replace(substring(sub,t,6,2),*y,*)2串是

34、字符組成的，長度為1的串和字符是否概念相同？為什么？(題源：朱戰(zhàn)立，C版題解，p86，4.2.1(典型題解)_2)答：由于字符的長度固定為1，長度概念可以隱含，所以存儲(chǔ)時(shí)只需存儲(chǔ)該字符即可；而長度為1的串其長度概念不能隱含，必須顯示地表示出來，所以存儲(chǔ)時(shí)要同時(shí)存儲(chǔ)該字符和值為1的長度值。五、算法設(shè)計(jì)題1設(shè)串s和串t采用順序存儲(chǔ)結(jié)構(gòu)，編寫函數(shù)實(shí)現(xiàn)串s和串t的比較操作，要求比較結(jié)果包括大于、小于和等于三種情況。(題源：朱戰(zhàn)立，C版題解，p87，4.2.1(典型題解)_7)提示算法思想：循環(huán)逐個(gè)比較兩個(gè)串，一旦兩個(gè)串的某個(gè)字符比較不相等則說明兩個(gè)串不相等，此時(shí)進(jìn)一步比較這兩個(gè)不相等字符的大于和小于情

35、況來決定串s和串t比較的大于和小于情況；當(dāng)串s的n個(gè)字符和串t的m個(gè)字符比較全部相等時(shí)，還需進(jìn)一步判斷此時(shí)串s或串t是否還有剩余字符沒有比較，來決定串s和串t比較的大于和小于情況；若所有字符比較均相等，并且串s的字符個(gè)數(shù)n和串t的字符個(gè)數(shù)m也相等時(shí)，說明串s等于串t。當(dāng)串s大于串t時(shí)函數(shù)返回1，當(dāng)串s小于串t時(shí)函數(shù)返回-1，當(dāng)串s等于串t時(shí)函數(shù)返回0。解：intStrCompare(SStrTypes,SStrTypet)intn=s.length,m=t.length,i,j,tag;i=0;j=0;while(in&jt.strj)tag=1;/*說明st,退出比較*/returntag;

36、elsetag=-1;/*說明sm)tag=1;/*若串t只和串s的前m個(gè)字符相等則st*/elseif(nm)tag=-1;/*若串s只和串t的前n個(gè)字符相等則st*/returntag;2輸入一個(gè)由若干單詞組成的文本行，每個(gè)單詞之間用若干個(gè)空格隔開，統(tǒng)計(jì)此文本中單詞的個(gè)數(shù)。(題源：寧正元，C版題解，p44，4.2_12)提示：要統(tǒng)計(jì)單詞的個(gè)數(shù)先要解決如何判斷一個(gè)單詞，應(yīng)該從輸入行的開頭一個(gè)字符一個(gè)字符地去辨別。假定把一個(gè)文本行放在數(shù)組r中，那么就相當(dāng)于從r0開始逐個(gè)檢查數(shù)組元素，當(dāng)經(jīng)過若干個(gè)空格符之后，找到第一個(gè)字母就是一個(gè)單詞的開頭，此時(shí)利用一個(gè)統(tǒng)計(jì)計(jì)數(shù)器進(jìn)行累加1運(yùn)算，在此之后若連續(xù)讀

37、到的是非空格符，則這些字符屬于剛統(tǒng)計(jì)到的那個(gè)單詞，因此不應(yīng)將計(jì)數(shù)器累加1，下一次計(jì)數(shù)應(yīng)該是在讀到一個(gè)或幾個(gè)空格后再遇到非空格字符之時(shí)進(jìn)行。因此，統(tǒng)計(jì)一個(gè)單詞時(shí)不僅要滿足當(dāng)前所檢查的這個(gè)字符是非空格，而且要滿足所檢查的前一個(gè)字符是空格。解：intcount(r)charr80;charprec,nowc;intnum,j;prec=;num=0;for(j=0;j80;j+)nowc=rj;if(nowc!=)&(prec=)num+;prec=nowc;returnnum;/*count*/3編寫算法，求串s所含不同字符的總數(shù)和每種字符的個(gè)數(shù)。(題源：嚴(yán)蔚敏，C版習(xí)題集，p29，4.18)解：

38、typedefstructcharch;intnum;mytype;voidStrAnalyze(StringtypeS)/統(tǒng)計(jì)串S中字符的種類和個(gè)數(shù)mytypeTMAXSIZE;/用結(jié)構(gòu)數(shù)組T存儲(chǔ)統(tǒng)計(jì)結(jié)果for(i=1;i1）的父結(jié)點(diǎn)是（）A2iB不存在C2i+1Di/22、有m個(gè)葉結(jié)點(diǎn)的哈夫曼樹所具有的結(jié)點(diǎn)數(shù)為（）AmBm+1C2mD2m-13、下列陳述中正確的（）A二叉樹是度為2的有序樹B二叉樹中結(jié)點(diǎn)只有一個(gè)孩子時(shí)無左右之分C二叉樹中必有度為2的結(jié)點(diǎn)D二叉樹中最多只有兩棵子樹，并且有左右之分4、以二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)，在具有個(gè)結(jié)點(diǎn)的二叉鏈表中(n0)，空鏈域的個(gè)數(shù)為（）A2n-1

39、Bn-1Cn+1D2n+15、將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從上到下，從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)為49的結(jié)點(diǎn)的左孩子編號(hào)為（）A99B98C50D486、在一棵具有五層的滿二叉樹中，結(jié)點(diǎn)總數(shù)為（）A31B32C33D167、在一棵二叉樹中，第5層上的結(jié)點(diǎn)數(shù)最多為（）A8B15C16D328、由二叉樹的（）遍歷，可以惟一確定一棵二叉樹A前序和后序B前序和中序C后序D中序9、具有35個(gè)結(jié)點(diǎn)的完全二叉樹的深度為（）。A.5B.6C.7D.810、已知一棵二叉樹的先序遍歷序列為EFHIGJK，中序遍歷序列為HFIEJGK，則該二叉樹根的右子樹的根是（）。AEB.FC.GD.

40、J11、由4個(gè)結(jié)點(diǎn)構(gòu)造出的不同的二叉樹個(gè)數(shù)共有（）。A8B.10C12D14解析：（解釋：最多有4層，最少有3層。若有4層，從第二層開始，均有兩個(gè)位置可選；若有3層，第3層上有4個(gè)位置可選）12、在完全二叉樹中，如果一個(gè)結(jié)點(diǎn)是葉子結(jié)點(diǎn)，則它沒有（）。A.左孩子結(jié)點(diǎn)B.右孩子結(jié)點(diǎn)C.左、右孩子結(jié)點(diǎn)D.左、右孩子結(jié)點(diǎn)和兄弟結(jié)點(diǎn)13、深度為6的二叉樹最多有（）個(gè)結(jié)點(diǎn)。A64B63C32D3114、二叉樹使用二叉鏈表存儲(chǔ)，若p指針指向二叉樹的一個(gè)結(jié)點(diǎn)，當(dāng)p-lchild=NULL時(shí)，則（）。p結(jié)點(diǎn)左孩子為空Bp結(jié)點(diǎn)有右孩子p結(jié)點(diǎn)右孩子為空Dp結(jié)點(diǎn)有左孩子15、在具有n個(gè)結(jié)點(diǎn)的完全二叉樹中，若結(jié)點(diǎn)i有左

41、孩子，則結(jié)點(diǎn)i的左孩子編號(hào)為（）。A2iB不存在C2i+1D2i-116、將含100個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，按從上到下從左到右依次對(duì)結(jié)點(diǎn)編號(hào)，根結(jié)點(diǎn)的編號(hào)為。編號(hào)為50的結(jié)點(diǎn)X的雙親的編號(hào)為（）。A25B48C100D無法確定17、三個(gè)結(jié)點(diǎn)可以構(gòu)成（）種不同形狀的二叉樹。2C3D518、若由樹轉(zhuǎn)化得到的二叉樹是非空的二叉樹，則二叉樹形狀是（）。A根結(jié)點(diǎn)無右子樹的二叉樹B根結(jié)點(diǎn)無左子樹的二叉樹C根結(jié)點(diǎn)可能有左子樹和右子樹D各結(jié)點(diǎn)只有一個(gè)孩子的二叉樹19、哈夫曼樹是訪問葉結(jié)點(diǎn)的帶權(quán)路徑長度（）的二叉樹。A最短B最長C可變D不定20、某二叉樹的前序和后序序列正好相反，則該二叉樹一定是（）的

42、二叉樹。A空或只有一個(gè)結(jié)點(diǎn)B高度等于其結(jié)點(diǎn)數(shù)C任一結(jié)點(diǎn)無左孩子D任一結(jié)點(diǎn)無右孩子填空題：1、12個(gè)結(jié)點(diǎn)的完全二叉樹的葉結(jié)點(diǎn)有（5）個(gè)。2、在任何一棵二叉樹中，度為的結(jié)點(diǎn)n0和度為的結(jié)點(diǎn)n2之間的關(guān)系是（n0=n2+1。3、已知完全二叉樹的第4層有4個(gè)結(jié)點(diǎn)，則其葉子結(jié)點(diǎn)數(shù)是（11）。4、10個(gè)結(jié)點(diǎn)的完全二叉樹的葉結(jié)點(diǎn)有（3）個(gè)。5、深度為6的二叉樹最多有（63）個(gè)結(jié)點(diǎn)。6、一個(gè)二叉樹中，度為2的結(jié)點(diǎn)有3個(gè)，則葉結(jié)點(diǎn)有（4）個(gè)。7、若二叉樹的一個(gè)葉子是某子樹的中根遍歷序列中的第一個(gè)結(jié)點(diǎn)，則它必是該子樹的后根遍歷序列中的（第一）個(gè)結(jié)點(diǎn)。8、下圖為某樹的靜態(tài)雙親表示，則結(jié)點(diǎn)D、E的雙親結(jié)點(diǎn)分別為（B）

43、和（C）。A-1B0C0D1E2012349、具有m個(gè)葉結(jié)點(diǎn)的哈夫曼樹共有（2m-1）個(gè)結(jié)點(diǎn)。10、二叉樹通常有（順序）存儲(chǔ)結(jié)構(gòu)和（鏈?zhǔn)剑┐鎯?chǔ)結(jié)構(gòu)兩種。11、二叉樹在二叉鏈表表示方式下，p指向二叉樹的根結(jié)點(diǎn)，經(jīng)運(yùn)算s=p；while(s-rchild)s=s-rchild后，s指針指向（根或最右）結(jié)點(diǎn)。判斷題：1、完全二叉樹中，若一個(gè)結(jié)點(diǎn)沒有左孩子，則它必須是葉子。（TRUE）2、由二叉樹結(jié)點(diǎn)的先根序列和后根序列可以唯一地確定一棵二叉樹。（FALSE）3、一般在哈夫曼樹中，權(quán)值越大的葉子離根結(jié)點(diǎn)越近。（TRUE）4、二叉樹中任何一個(gè)結(jié)點(diǎn)的度都是2。（FALSE）5、一棵哈夫曼樹中不存在度為1的

44、結(jié)點(diǎn)。（TRUE）解析：n=n0+n1+n2;2n0-1=n;n0=n2+1;可推出不存在n1;6、若一個(gè)二叉樹的葉結(jié)點(diǎn)是先根遍歷序列的最后一個(gè)結(jié)點(diǎn)，則它必是中根遍歷的序列中的最后一個(gè)結(jié)點(diǎn)。（FALSE）7、中序遍歷二叉排序樹的結(jié)點(diǎn)不能得到排好序的結(jié)點(diǎn)序列。（FALSE）8、完全二叉樹一定是滿二叉樹。（FALSE）9、由二叉樹的前序和中序遍歷序列可以推導(dǎo)出此二叉樹的后序遍歷序列。（TRUE）10、滿二叉樹一定是完全二叉樹。（TRUE）11、完全二叉樹可采用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)存儲(chǔ)，非完全二叉樹則不能。（FALSE）應(yīng)用題：1、對(duì)給定的一組權(quán)值W=5，2，9，11，8，3，7，試構(gòu)造相應(yīng)的哈夫曼樹，

45、并計(jì)算它的帶權(quán)路徑長度。參考答案：帶權(quán)路徑長度=11*1+9*2+8*3+7*3+5*3+3*4+2*42、已知一棵二叉樹的前序序列和中序序列分別如下，請(qǐng)畫出該二叉樹。前序序列：ABDGJKLHCEIF中序序列：BGJLKDHAEICF解析：前序序列：ABDGJKLHCEIF中序序列：BGJLKDHAEICF找到根后，可確定左子樹結(jié)點(diǎn)和右子樹結(jié)點(diǎn)，然后遞歸進(jìn)行即可；3、試找出分別滿足下列條件的所有二叉樹。（1）前序序列和中序序列相同；（2）中序序列和后序序列相同；（3）前序序列和后序序列相同。解答：只有空樹或只有根結(jié)點(diǎn)的二叉樹，同時(shí)滿足上述三個(gè)條件；4、設(shè)有一組結(jié)點(diǎn)，其權(quán)值W=1，4，9，16

46、，25，36，49，64，81，100，畫出由這些結(jié)點(diǎn)所構(gòu)成的哈夫曼樹，并計(jì)算帶權(quán)路徑長度。解析：參考第一題；5、畫出下圖所示森林經(jīng)轉(zhuǎn)換后所對(duì)應(yīng)的二叉樹。eqoac(,A)eqoac(,B)eqoac(,C)eqoac(,D)eqoac(,E)eqoac(,F)eqoac(,J)eqoac(,G)eqoac(,H)eqoac(,I)參考答案：6、已知一棵二叉樹的先根遍歷序列和中根遍歷序列分別是ABDGHE及GDHBEA，畫出這棵二叉樹。參考答案：8、寫出下圖所示二叉樹的先根遍歷、中根遍歷、后根遍歷的結(jié)點(diǎn)序列，并將其轉(zhuǎn)換為森林。ABECDFGHI參考答案：程序設(shè)計(jì)題：1、寫出二叉樹的建立及前序遍歷遞歸算法。參考答案：#includestdio.h#includestring.h#includestdlib.h#includewindows.htypedefstructBTNodechardata;structBTNode*Lchild,*Rchild;BTNode,*BTree;/*BTreeisaddressofroot*/BTreePre_Create_BT(BTreeBT)/返回指針的函數(shù)c