數(shù)據(jù)結(jié)構(gòu)習(xí)題集

1緒論一、選擇題：1、下列算法的時(shí)間復(fù)雜度是（）for(i=0;i<n;i++)c[i]=i；A．O（1）B．O（n）C．O（log2n）D．O（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ǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。順序存儲(chǔ)方法：它是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)，由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)是一種最基本的存儲(chǔ)表示方法，通常借助于程序設(shè)計(jì)語(yǔ)言中的數(shù)組來(lái)實(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ì)語(yǔ)言中的指針類(lèi)型來(lái)實(shí)現(xiàn)。索引存儲(chǔ)方法：除建立存儲(chǔ)結(jié)點(diǎn)信息外，還建立附加的索引表來(lái)標(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)：數(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ù)都無(wú)關(guān)。3、以下哪一個(gè)術(shù)語(yǔ)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(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．?dāng)?shù)據(jù)項(xiàng)6、研究數(shù)據(jù)結(jié)構(gòu)就是研究（）。A．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu) B．?dāng)?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)D．?dāng)?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．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它取決于數(shù)據(jù)的存儲(chǔ)方式C．?dāng)?shù)據(jù)存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)依賴于計(jì)算機(jī)語(yǔ)言D．?dāng)?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;i<m;i++)for(j=0;j<n;j++)a[i][j]=i*j；A．O（m2）B．O（n2）C．O（m×n）D．O（m+n）11、算法分析的兩個(gè)主要方面是（）。A．正確性和簡(jiǎn)明性 B．?dāng)?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ù)的（）無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。3、()結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無(wú)關(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ǔ)方法表示。判斷題：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ǔ)結(jié)構(gòu)）和（運(yùn)算）。2、數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的（）無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。3、(邏輯)結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無(wú)關(guān)。4、程序段“for(i=1;i<=n;i++){k++;for(j=1;j<=n;j++)x=x+k;}”的時(shí)間復(fù)雜度為(O(n2))。5、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）可以用（順序）、（鏈?zhǔn)剑?、（索引）及散列存?chǔ)等四種存儲(chǔ)方法表示。三、判斷題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)是惟一的。（×）2線性表選擇題：1、在表長(zhǎng)為n的順序表上做插入運(yùn)算，平均要移動(dòng)的結(jié)點(diǎn)數(shù)為（）。A．nB．n/2C．n/3D．n/42、在一個(gè)單鏈表中，若P所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在P之后插入S所指結(jié)點(diǎn)，則執(zhí)行（）A．S->next=P->next;P->next=SB．P->next=S->next;S->next=P；C．P->next=P;P->next=S；D．P->next=S;S->next=P；3、在已知頭指針的單鏈表中，要在其尾部插入一新結(jié)點(diǎn)，其算法所需的時(shí)間復(fù)雜度為（）A．Ｏ（1）B．Ｏ（log2n）C．O（n）D．O（n2）解析：?jiǎn)尉筒迦脒\(yùn)算而言，算法時(shí)間復(fù)雜度為Ｏ（1），但要將指針定位到鏈表末尾，指針移動(dòng)的時(shí)間復(fù)雜度為O（n）；4、對(duì)于只在表的首、尾兩端進(jìn)行插入操作的線性表，宜采用的存儲(chǔ)結(jié)構(gòu)為（）A．順序表B．用頭指針表示的單循環(huán)鏈表C．用尾指針表示的單循環(huán)鏈表D．單鏈表解析：尾指針是指向終端結(jié)點(diǎn)的指針，用它來(lái)表示單循環(huán)鏈表可以使得查找鏈表的開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)都很方便，設(shè)一帶頭結(jié)點(diǎn)的單循環(huán)鏈表，其尾指針為rear，則開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)的位置分別是rear->next->next和rear,查找時(shí)間都是O(1)。

若用頭指針來(lái)表示該鏈表，則查找終端結(jié)點(diǎn)的時(shí)間為O(n)。5、線性表是（）A．一個(gè)有限序列，可以為空B．一個(gè)有限序列，不能為空C．一個(gè)無(wú)限序列，可以為空D．一個(gè)無(wú)限序列，不能為空6、在n個(gè)結(jié)點(diǎn)的雙鏈表的某個(gè)結(jié)點(diǎn)前插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度是（）A．O（n）B．O（1）C．O（log2n）D．O（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．說(shuō)明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)9、帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（）A．head=NULL；B．head->next=NULL；C．head->next=head；D．head!=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)線性表的敘述中，正確的是（）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．開(kāi)始結(jié)點(diǎn)D．終端結(jié)點(diǎn)13、將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是（）。A．nB.2n-1C.2nD14、鏈表不具有的特點(diǎn)是（）。A．隨機(jī)訪問(wèn)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í)行的操作是（）。A．s->next=p->next;p->next=s;B．q->next=s;s->next=p;C．p->next=s->next;s->next=p;D．p->next=s;s->next=q;16、鏈表具有的特點(diǎn)是（）。A．可隨機(jī)訪問(wèn)任一元素 B．插入、刪除需要移動(dòng)元素C．不必事先估計(jì)存儲(chǔ)空間 D．存儲(chǔ)空間是靜態(tài)分配的17、一個(gè)順序表一旦說(shuō)明，其中可用空間大?。ǎ〢．已固定 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ū)的條件是（）。A．P->next==Q B．Q->next==PC．P==Q D．P->next==Q->next20、鏈表不具有的特點(diǎn)是（）。A．可隨機(jī)訪問(wèn)任一元素B．插入、刪除不需要移動(dòng)元素C．不必事先估計(jì)存儲(chǔ)空間D．所需空間與線性表長(zhǎng)度成正比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．訪問(wèn)第i個(gè)結(jié)點(diǎn)（1≤i≤n）和求第i個(gè)結(jié)點(diǎn)的直接前趨（2≤i≤n）B．在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（1≤i≤n）C．刪除第i個(gè)結(jié)點(diǎn)（1≤i≤n）D．將n個(gè)結(jié)點(diǎn)從小到大排序23、在一個(gè)單鏈表中，若刪除p指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行的操作為（）。A．q=p->next;p->next=p->next->next;free(q);B．p=p->next;q=p->next;p=q->next;free(q);C．q=p->next->next;p=p->next;free(q);D．p=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的語(yǔ)句序列是（）。3、在帶頭結(jié)點(diǎn)的雙鏈表Ｌ中，指針Ｐ所指結(jié)點(diǎn)是開(kāi)始結(jié)點(diǎn)的條件是（）。4、在具有n個(gè)結(jié)點(diǎn)的雙鏈表中做插入、刪除運(yùn)算，平均時(shí)間復(fù)雜度為（）。5、在一個(gè)長(zhǎng)度為n的順序表中第i個(gè)元素（1≤i≤n）之前插入一個(gè)元素時(shí)，需向后移動(dòng)（）個(gè)元素。6、在雙循環(huán)鏈表中，若要在指針p所指結(jié)點(diǎn)之前插入指針s所指的結(jié)點(diǎn)，則需執(zhí)行下列語(yǔ)句：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)的直接后繼位置的語(yǔ)句是（）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)的語(yǔ)句是（）；刪除首結(jié)點(diǎn)的語(yǔ)句是（）。判斷題1、在有序的順序表和有序的鏈表上，均可以使用折半查找法來(lái)提高查找速度。（）2、順序存儲(chǔ)的線性表可以隨機(jī)存取。（）3、線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。（）程序設(shè)計(jì)題數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)類(lèi)型定義如下：順序存儲(chǔ)：typedefstruct{int*base;intlength;intlistsize;}sqlist;鏈?zhǔn)酱鎯?chǔ)：typedefstructLinkList{intdata;structLinkList*next;}Node,*LinkList;1、已知帶頭結(jié)點(diǎn)的單鏈表head中的結(jié)點(diǎn)是按整數(shù)值遞增排序的，寫(xiě)一算法將值為x的結(jié)點(diǎn)插入到表head中，使head仍然有序。2、用尾插法建立帶頭結(jié)點(diǎn)的單鏈表。3、用頭插法建立帶頭結(jié)點(diǎn)的單鏈表。4、對(duì)給定的單鏈表L，編寫(xiě)一個(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=A∪B和A=A∩B運(yùn)算；參考答案（線性表）一、選擇題1234567891011121314151617181920212223BABCABCCBBABBABCBAAABAA二、填空題1、在雙鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p，其時(shí)間復(fù)雜度為（O(1)）。2、在僅有尾指針R指示的單循環(huán)鏈表R中，在表尾插入一個(gè)結(jié)點(diǎn)S的語(yǔ)句序列是（P=R;while(P->next!=NULL)P=P->next;P->next=S;S->next=NULL;）。3、在帶頭結(jié)點(diǎn)的雙鏈表Ｌ中，指針Ｐ所指結(jié)點(diǎn)是開(kāi)始結(jié)點(diǎn)的條件是（P==L）。4、在具有n個(gè)結(jié)點(diǎn)的雙鏈表中做插入、刪除運(yùn)算，平均時(shí)間復(fù)雜度為（O(1)）。5、在一個(gè)長(zhǎng)度為n的順序表中第i個(gè)元素（1≤i≤n）之前插入一個(gè)元素時(shí)，需向后移動(dòng)（n-i+1）個(gè)元素。6、在雙循環(huán)鏈表中，若要在指針p所指結(jié)點(diǎn)之前插入指針s所指的結(jié)點(diǎn)，則需執(zhí)行下列語(yǔ)句：s->prior=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)的直接后繼位置的語(yǔ)句是（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)的語(yǔ)句是（q=p->next;p->next=q->next;free(q);）；刪除首結(jié)點(diǎn)的語(yǔ)句是（q=L->next;L=L->next;free(q);）。三、判斷題1、在有序的順序表和有序的鏈表上，均可以使用折半查找法來(lái)提高查找速度。（×）2、順序存儲(chǔ)的線性表可以隨機(jī)存取。（√）3、線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。（√）四、程序設(shè)計(jì)題1、已知帶頭結(jié)點(diǎn)的單鏈表head中的結(jié)點(diǎn)是按整數(shù)值遞增排序的，寫(xiě)一算法將值為x的結(jié)點(diǎn)插入到表head中，使head仍然有序。P=head->next;While(p->next!=NULL&&p->data<x)p=p->next;//指針定位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ì)給定的單鏈表L，編寫(xiě)一個(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)語(yǔ)句為：p=L->next;//p指向第一個(gè)結(jié)點(diǎn)whili(p->data!=x&&p->next!=NULL)p=p->next;if(p==NULL)ruturnerror;//不存在else{p=L->next;while(p->next->next->data!=x)p=p->next;q=p->next;p->next=p->next->next;free(q);}5、用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表的就地逆置算法，即將（a1,a2,…ai,…an）逆置為（an,…,ai,…a2,a1）;重點(diǎn)語(yǔ)句：for(i=0;i<sqlist.length/2;i++){sqlist.base[i]sqlist.base[sqlist.length-i];//第i個(gè)元素和第length-i元素交換存儲(chǔ)}6、用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表的就地逆置算法(不帶頭結(jié)點(diǎn)的單鏈表)，即將（a1,a2,…ai,…an）逆置為（an,…,ai,…a2,a1）;參考答案：Node*fun(Node*h)//h指向單鏈表的第一個(gè)結(jié)點(diǎn){Node*p,*q,*r;P=h;If(p==NULL)ReturnNULL;q=pnext;//q指針指向第二個(gè)結(jié)點(diǎn)pnext=NULL;while(q){r=qnext；//第一次循環(huán)時(shí)，r指向第三個(gè)結(jié)點(diǎn)qnext=p;//第二個(gè)結(jié)點(diǎn)的NEXT指向第一個(gè)結(jié)點(diǎn)p=q;//p總是指向逆置后的第一個(gè)結(jié)點(diǎn)q=r;//q總是指向剩余單鏈表的第一個(gè)結(jié)點(diǎn)，為將其作為逆置單鏈表的第一個(gè)結(jié)點(diǎn)作準(zhǔn)備}returnp;}兩外，解決本體還有另外一種思路，將結(jié)點(diǎn)數(shù)據(jù)域拷貝到一個(gè)一維數(shù)組中，然后反過(guò)來(lái)填充單鏈表結(jié)點(diǎn)的數(shù)據(jù)域。7、使用順序存儲(chǔ)結(jié)構(gòu)分別實(shí)現(xiàn)A=A∪B和A=A∩B運(yùn)算；請(qǐng)參考清華大學(xué)出版社出版，嚴(yán)尉敏編著《數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版》P20例2-1；棧和隊(duì)列選擇題：1、循環(huán)隊(duì)列是空隊(duì)列的條件是（）A．Q.rear==Q.frontB．（Q.rear+1）%maxsize==Q.frontC．Q.rear==0D．Q.front==02、鏈棧與順序棧相比，比較明顯的優(yōu)點(diǎn)是（）A．通常不會(huì)出現(xiàn)棧滿的情況B．通常不會(huì)出現(xiàn)棧空的情況

C．插入操作更加方便D．刪除操作更加方便[分析]不管是鏈棧還是順序棧，其插入、刪除操作都是在棧頂進(jìn)行的，都比較方便，所以不可能選C)，D)。對(duì)鏈棧來(lái)講，當(dāng)棧中沒(méi)有元素而又要執(zhí)行出棧操作時(shí)，就會(huì)出現(xiàn)?？宅F(xiàn)象，故B)也是不正確的。只要內(nèi)存足夠大，鏈棧上就不會(huì)出現(xiàn)棧滿現(xiàn)象。而對(duì)順序棧來(lái)講，由于其大小是事先確定好的，因此可能會(huì)出現(xiàn)棧滿現(xiàn)象。所以A)是正確的。3、若一個(gè)棧的輸入序列是１，２，３，……，n，輸出序列的第一個(gè)元素是ｎ，則第ｉ個(gè)輸出元素是（）A．n-iB．n–i+1C．iD．不確定4、棧與一般線性表的區(qū)別主要在（）A．元素個(gè)數(shù)B．元素類(lèi)型C．邏輯結(jié)構(gòu)D．插入、刪除元素的位置5、一個(gè)鏈棧的棧頂指針是top，則執(zhí)行出棧操作時(shí)（棧非空），用x保存被刪除結(jié)點(diǎn)，則執(zhí)行（）A．x=top;top=topnext；B．x=topdata；C．top=topnext;x=topdata；D．x=topdata;top=topnext；[分析]棧頂元素出棧后，應(yīng)該從棧底位置即第一個(gè)結(jié)點(diǎn)開(kāi)始重新定位，執(zhí)行語(yǔ)句是：q=base;while(qnext!=top)q=qnext;free(top);top=q;6、對(duì)于一個(gè)棧，給定輸入序列為1，2，3，則下列不可能為輸出序列的是（）A．1，2，3B．3，2，1C．3，1，2D．2，1，3[分析]每個(gè)元素進(jìn)棧后立即出棧，結(jié)果是答案A；三個(gè)元素全部進(jìn)棧后再出棧，得到答案B；1和2進(jìn)棧后出棧，然后3入棧后出棧，得到答案D；而C答案不可能的原因是：3出棧后，說(shuō)明1、2還在棧中，1出棧后2還在棧中，說(shuō)明2的入棧次序在1之前。7、在鏈接隊(duì)列執(zhí)行入隊(duì)操作（）A．需判別隊(duì)是否空B．需判別隊(duì)是否滿C．限制在鏈表頭p進(jìn)行D．限制在鏈表尾p進(jìn)行8、以下不屬于棧的基本運(yùn)算是（）。A．刪除棧頂元素B．刪除棧底元素C．判斷棧是否為空D．將棧置為空棧9、一個(gè)棧的入棧序列是a,b,c,d,e，則棧的不可能的輸出序列是（）。A．e,d,c,b,aB．d,e,c,b,aC．d,c,e,a,bD．a(chǎn),b,c,d,e10、設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否配對(duì)出現(xiàn)的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳。A．線性表的順序存儲(chǔ)結(jié)構(gòu)B．棧C．隊(duì)列D．線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)11、循環(huán)隊(duì)列的特點(diǎn)之一是不會(huì)產(chǎn)生（）。A．上溢出B．下溢出C．隊(duì)滿D．假溢出12、設(shè)數(shù)組Data[n]作為循環(huán)隊(duì)列Q的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行入隊(duì)操作的語(yǔ)句為（）。A．rear=(rear+1)%(n+1)B．front=(front+1)%nC．rear=(rear+1)%nD．front=(front+1)%(n+1)13、棧是限定在（）處進(jìn)行插入或刪除操作的線性表。A．端點(diǎn) B．棧底 C．棧頂 D．中間14、容量是10的循環(huán)隊(duì)列的隊(duì)頭位置qfront為2，隊(duì)列中的數(shù)據(jù)元素個(gè)數(shù)為5，則隊(duì)的第一個(gè)數(shù)據(jù)元素的位置是（）A．2 B．7 C．1 D．[分析](front-rear+10)%10=5,并且front和rear的取值范圍均是0—9，所以只有（7-2+10）%10=5。15、循環(huán)隊(duì)列的出隊(duì)操作是（）A． qfront=(qfront+1)%maxsize; B．qfront=qfront+1;C．qrear=(qrear+1)%maxsize;D．qrear=qrear+1;16、當(dāng)循環(huán)隊(duì)列q是滿隊(duì)列時(shí)，存放隊(duì)列元素的數(shù)組data有n個(gè)元素，則data中存放（）個(gè)數(shù)據(jù)元素。A．n B.n-1 C.n-2 D.[分析]容量為maxsize的循環(huán)隊(duì)列最多只能存放maxsize-1個(gè)數(shù)據(jù)元素，當(dāng)隊(duì)列滿時(shí)，隊(duì)尾指針再往前走一步就追上隊(duì)頭指針，即(rear+1)%maxsize=front；17、以下哪一個(gè)不是隊(duì)列的基本運(yùn)算（）。A．從隊(duì)尾插入一個(gè)新元素B．從隊(duì)列中刪除第i個(gè)元素C．判斷一個(gè)隊(duì)列是否為空D．讀取隊(duì)頭元素的值18、在一個(gè)鏈隊(duì)列中，若f,r分別為隊(duì)首、隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的操作為（）。A．fnext=s;f=s B．rnext=s;r=s;C．snext=r;r=s; D．snext=f;f=s19、循環(huán)隊(duì)列的入隊(duì)操作應(yīng)為（）。A．qrear=qrear+1;qdata[qrear]=x; B．qdata[qrear++]=x;C．qrear=(qrear+1)%maxsize;qdata[qrear]=x;D．qdata[qrear]=x;q->rear=(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．?dāng)?shù)組 D．樹(shù)填空題：1、循環(huán)隊(duì)列用數(shù)組data[m]存放其元素值，已知其頭、尾指針?lè)謩e是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之后，得到的輸出序列為（）。4、隊(duì)列的隊(duì)尾位置隨著（）而變化。5、在（）的情況下，鏈隊(duì)列的出隊(duì)操作需要修改尾指針。6、從棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)，并將被刪除的結(jié)點(diǎn)的值保存在x中，其操作步驟為（）；top=top->next;。7、用數(shù)組A[m]來(lái)存放循環(huán)隊(duì)列q的元素，且它的頭、尾指針?lè)謩e為front和rear，隊(duì)列滿足條件(q.rear+1)%m==q.front,則隊(duì)列中當(dāng)前的元素個(gè)數(shù)為（）。8、順序棧s存儲(chǔ)在數(shù)組s->data[max]中，對(duì)s進(jìn)行出棧操作，執(zhí)行的語(yǔ)句序列是（）。9、以下運(yùn)算實(shí)現(xiàn)在循環(huán)隊(duì)列中的初始化操作voidinitqueue(seqqueue*q){q->front=0;();}判斷題：1、循環(huán)隊(duì)列中無(wú)上溢現(xiàn)象。（）2、循環(huán)隊(duì)列只有下溢，沒(méi)有上溢。（）3、對(duì)順序棧而言，在棧滿狀態(tài)，如果此時(shí)再作進(jìn)棧運(yùn)算，則會(huì)發(fā)生“下溢”。（）4、順序隊(duì)列和循環(huán)隊(duì)列的隊(duì)滿和隊(duì)空的條件是一樣的。（）5、為解決隊(duì)列“假滿”問(wèn)題，可以采用循環(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，寫(xiě)出下列出棧序列的操作序列。（1）CBADE（2）ACBED，其中I為進(jìn)棧操作，O為出棧操作。2、如果編號(hào)為1、2、3的三輛列車(chē)進(jìn)入一個(gè)棧式結(jié)構(gòu)的站臺(tái)，那么可能得到的三輛列車(chē)出站序列有哪些？不可能出現(xiàn)的序列是什么？程序設(shè)計(jì)題：1、寫(xiě)出循環(huán)隊(duì)列入隊(duì)操作的函數(shù)。參考答案（棧和隊(duì)列）一、選擇題123456789101112131415161718192021AABDBCDBCBDCCBABBBCAB二、填空題1、循環(huán)隊(duì)列用數(shù)組data[m]存放其元素值，已知其頭、尾指針?lè)謩e是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、在（鏈隊(duì)列為空）的情況下，鏈隊(duì)列的出隊(duì)操作需要修改尾指針。分析：Q.rear=h;6、從棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)，并將被刪除的結(jié)點(diǎn)的值保存在x中，其操作步驟為（x=top->data）。7、用數(shù)組A[m]來(lái)存放循環(huán)隊(duì)列q的元素，且它的頭、尾指針?lè)謩e為front和rear，隊(duì)列滿足條件(q.rear+1)%m==q.front,則隊(duì)列中當(dāng)前的元素個(gè)數(shù)為（0）。8、順序棧s存儲(chǔ)在數(shù)組s->data[max]中，對(duì)s進(jìn)行出棧操作，執(zhí)行的語(yǔ)句序列是（stop--）。9、以下運(yùn)算實(shí)現(xiàn)在循環(huán)隊(duì)列中的初始化操作voidinitqueue(seqqueue*q){q->front=0;(qbase=(qelemtype*)malloc(maxsize*sizeof(qelemtype));qrear=0;);}三、判斷題1、循環(huán)隊(duì)列中無(wú)上溢現(xiàn)象。（×）2、循環(huán)隊(duì)列只有下溢，沒(méi)有上溢。（×）3、對(duì)順序棧而言，在棧滿狀態(tài)，如果此時(shí)再作進(jìn)棧運(yùn)算，則會(huì)發(fā)生“下溢”。（×）4、順序隊(duì)列和循環(huán)隊(duì)列的隊(duì)滿和隊(duì)空的條件是一樣的。（×）5、為解決隊(duì)列“假滿”問(wèn)題，可以采用循環(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，寫(xiě)出下列出棧序列的操作序列。（1）CBADE（2）ACBED，其中I為進(jìn)棧操作，O為出棧操作。參考答案：（1）IIIOOOIOIO(2)IOIIOOIIOO2、如果編號(hào)為1、2、3的三輛列車(chē)順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的站臺(tái)，那么可能得到的三輛列車(chē)出站序列有哪些？不可能出現(xiàn)的序列是什么？參考答案：可能得到的三輛列車(chē)出站序列有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、寫(xiě)出循環(huán)隊(duì)列入隊(duì)操作的函數(shù)。請(qǐng)參考清華大學(xué)出版社嚴(yán)蔚敏編著的《數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版》p65。串和數(shù)組（含參考答案）一、單選題1．下列那些為空串（）A）S=“”B）S=“”C）S=“φ”D）S=“θ”答案：B2．S1=“ABCD”，S2=“CD”則S2在S3中的位置是（）A）1B）2C）3D）4答案：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）0<pos<StrLength(S)+1且1<=len<=StrLength(S)-pos+1B）0<pos<StrLength(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答案：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．串的長(zhǎng)度是()。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的字符開(kāi)始的j個(gè)字符組成的子串，len(s)返回串s的長(zhǎng)度，則con(subs(S1，2，len(S2))，subs(S1，len(S2)，2))的結(jié)果是()。A．BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF答：D9．若某串的長(zhǎng)度小于一個(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)基本操作，若S<T，返回值____________________。答：<05．在串順序存儲(chǔ)結(jié)構(gòu)中，實(shí)現(xiàn)串操作的原操作為_(kāi)___________________。答：字符序列的復(fù)制6．串與線性表在邏輯結(jié)構(gòu)上極為相似，區(qū)別僅在于____________________；在基本操作上差別很大，線性表的基本操作大多數(shù)以____________________作為操作對(duì)象，而串的基本操作通常以作為操作對(duì)象。答：串的數(shù)據(jù)對(duì)象約束為字符集“單個(gè)元素”“串的整體”7．兩個(gè)串相等的充分必要條件是____________________且____________________。答：兩個(gè)串的串長(zhǎng)相等各個(gè)對(duì)應(yīng)位置的字符都相等8．空串是指____________________，空格串是指_______________________。答：不含任何字符的串僅含空格字符的串三、判斷題1．空串是由空白字符組成的串（FALSE）2．串的定長(zhǎng)順序結(jié)構(gòu)是用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列，按照預(yù)定義的大小，為每個(gè)定義的串變量分配一個(gè)固定長(zhǎng)度的存儲(chǔ)區(qū)。(TRUE)3．串的堆分配存儲(chǔ)表示是用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列，但它們的存儲(chǔ)空間是在程序執(zhí)行過(guò)程中動(dòng)態(tài)分配得到的。（TRUE）4．串中StrInsert(&S,pos,T)基本操作是最小的操作子集（FALSE）5．串是由有限個(gè)字符構(gòu)成的連續(xù)序列，串長(zhǎng)度為串中字符的個(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)，那么則說(shuō)明前者是后者的子串。(FALSE)(錯(cuò)：是否連續(xù)是關(guān)鍵)(題源：陳明，C版實(shí)用數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)，p109，(判斷題)_2)7．串類(lèi)型的最小操作子集不能利用其他串操作來(lái)實(shí)現(xiàn)，反之，其他串操作（除串清除ClearString和串銷(xiāo)毀DestroyString外）均可在最小操作子集上實(shí)現(xiàn)。(TRUE)(題源：根據(jù)教材p72自編)四、簡(jiǎn)答題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．串是字符組成的，長(zhǎng)度為1的串和字符是否概念相同？為什么？(題源：朱戰(zhàn)立，C版題解，p86，4.2.1(典型題解)_2)答：由于字符的長(zhǎng)度固定為1，長(zhǎng)度概念可以隱含，所以存儲(chǔ)時(shí)只需存儲(chǔ)該字符即可；而長(zhǎng)度為1的串其長(zhǎng)度概念不能隱含，必須顯示地表示出來(lái)，所以存儲(chǔ)時(shí)要同時(shí)存儲(chǔ)該字符和值為1的長(zhǎng)度值。五、算法設(shè)計(jì)題1．設(shè)串s和串t采用順序存儲(chǔ)結(jié)構(gòu)，編寫(xiě)函數(shù)實(shí)現(xiàn)串s和串t的比較操作，要求比較結(jié)果包括大于、小于和等于三種情況。(題源：朱戰(zhàn)立，C版題解，p87，4.2.1(典型題解)_7)提示算法思想：循環(huán)逐個(gè)比較兩個(gè)串，一旦兩個(gè)串的某個(gè)字符比較不相等則說(shuō)明兩個(gè)串不相等，此時(shí)進(jìn)一步比較這兩個(gè)不相等字符的大于和小于情況來(lái)決定串s和串t比較的大于和小于情況；當(dāng)串s的n個(gè)字符和串t的m個(gè)字符比較全部相等時(shí)，還需進(jìn)一步判斷此時(shí)串s或串t是否還有剩余字符沒(méi)有比較，來(lái)決定串s和串t比較的大于和小于情況；若所有字符比較均相等，并且串s的字符個(gè)數(shù)n和串t的字符個(gè)數(shù)m也相等時(shí)，說(shuō)明串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(i<n&&j<m){if(s.str==t.str[j])/*繼續(xù)比較下一個(gè)字符*/{i++;j++;}elseif(s.str>t.str[j]){tag=1;/*說(shuō)明s>t,退出比較*/returntag;}else{tag=-1;/*說(shuō)明s<t，退出比較*/returntag;}}if(n==m)tag=0;/*若所有字符比較均相等則tag=0*/elseif(n>m)tag=1;/*若串t只和串s的前m個(gè)字符相等則s>t*/elseif(n<m)tag=-1;/*若串s只和串t的前n個(gè)字符相等則s<t*/returntag;}2．輸入一個(gè)由若干單詞組成的文本行，每個(gè)單詞之間用若干個(gè)空格隔開(kāi)，統(tǒng)計(jì)此文本中單詞的個(gè)數(shù)。(題源：寧正元，C版題解，p44，4.2_12)提示：要統(tǒng)計(jì)單詞的個(gè)數(shù)先要解決如何判斷一個(gè)單詞，應(yīng)該從輸入行的開(kāi)頭一個(gè)字符一個(gè)字符地去辨別。假定把一個(gè)文本行放在數(shù)組r中，那么就相當(dāng)于從r[0]開(kāi)始逐個(gè)檢查數(shù)組元素，當(dāng)經(jīng)過(guò)若干個(gè)空格符之后，找到第一個(gè)字母就是一個(gè)單詞的開(kāi)頭，此時(shí)利用一個(gè)統(tǒng)計(jì)計(jì)數(shù)器進(jìn)行累加1運(yùn)算，在此之后若連續(xù)讀到的是非空格符，則這些字符屬于剛統(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)charr[80];{charprec,nowc;intnum,j;prec=‘’;num=0;for(j=0;j<80;j++){nowc=r[j];if((nowc!=‘’)&&(prec==‘’))num++;prec=nowc;}returnnum;}/*count*/3．編寫(xiě)算法，求串s所含不同字符的總數(shù)和每種字符的個(gè)數(shù)。(題源：嚴(yán)蔚敏，C版習(xí)題集，p29，4.18)解：typedefstruct{charch;intnum;}mytype;voidStrAnalyze(StringtypeS)//統(tǒng)計(jì)串S中字符的種類(lèi)和個(gè)數(shù){mytypeT[MAXSIZE];//用結(jié)構(gòu)數(shù)組T存儲(chǔ)統(tǒng)計(jì)結(jié)果for(i=1;i<=S[0];i++){c=S;j=0;while(T[j].ch&&T[j].ch!=c)j++;//在結(jié)構(gòu)數(shù)組T中逐元素查找當(dāng)前字符c是否已記錄過(guò).//當(dāng)循環(huán)停止時(shí)，再看是什么原因造成的停止。if(T[j].ch)T[j].num++;//循環(huán)停止時(shí)T[j].ch不等于NULL,說(shuō)明是由于T[j].ch=c所致//若是T[j].ch=c所致則說(shuō)明字符c在串s中已經(jīng)出現(xiàn)過(guò)//故將其個(gè)數(shù)加1.elseT[j]={c,1};//否則為首次出現(xiàn)，將其出現(xiàn)次數(shù)記為1.}//forfor(j=0;T[j].ch;j++)//打印每個(gè)字符在串s中的出現(xiàn)次數(shù)。printf(“%c:%d\n”,T[j].num);}//StrAnalyze數(shù)組和廣義表樹(shù)和二叉樹(shù)選擇題：1、在具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中，結(jié)點(diǎn)i（i>1）的父結(jié)點(diǎn)是（）A．2iB．不存在C．2i+1D．?i/2?2、有m個(gè)葉結(jié)點(diǎn)的哈夫曼樹(shù)所具有的結(jié)點(diǎn)數(shù)為（）A．mB．m+1C．2mD．2m-13、下列陳述中正確的（）A．二叉樹(shù)是度為2的有序樹(shù)B．二叉樹(shù)中結(jié)點(diǎn)只有一個(gè)孩子時(shí)無(wú)左右之分C．二叉樹(shù)中必有度為2的結(jié)點(diǎn)D．二叉樹(shù)中最多只有兩棵子樹(shù)，并且有左右之分4、以二叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，在具有ｎ個(gè)結(jié)點(diǎn)的二叉鏈表中(n>0)，空鏈域的個(gè)數(shù)為（）A．2n-1B．n-1C．n+1D．5、將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從上到下，從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)為49的結(jié)點(diǎn)的左孩子編號(hào)為（）A．99B．98C．50D．486、在一棵具有五層的滿二叉樹(shù)中，結(jié)點(diǎn)總數(shù)為（）A．31B．32C．33D．167、在一棵二叉樹(shù)中，第5層上的結(jié)點(diǎn)數(shù)最多為（）A．8B．15C．16D．8、由二叉樹(shù)的（）遍歷，可以惟一確定一棵二叉樹(shù)A．前序和后序B．前序和中序C．后序D．中序9、具有35個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為（）。A.5B.6C.7D.810、已知一棵二叉樹(shù)的先序遍歷序列為EFHIGJK，中序遍歷序列為HFIEJGK，則該二叉樹(shù)根的右子樹(shù)的根是（）。A．EB.FC.GD.J11、由4個(gè)結(jié)點(diǎn)構(gòu)造出的不同的二叉樹(shù)個(gè)數(shù)共有（）。A．8B.10C．12解析：（解釋：最多有4層，最少有3層。若有4層，從第二層開(kāi)始，均有兩個(gè)位置可選；若有3層，第3層上有4個(gè)位置可選）12、在完全二叉樹(shù)中，如果一個(gè)結(jié)點(diǎn)是葉子結(jié)點(diǎn)，則它沒(méi)有（）。A.左孩子結(jié)點(diǎn)B.右孩子結(jié)點(diǎn)C.左、右孩子結(jié)點(diǎn)D.左、右孩子結(jié)點(diǎn)和兄弟結(jié)點(diǎn)13、深度為6的二叉樹(shù)最多有（）個(gè)結(jié)點(diǎn)。A．64 B．63 C．32 D．14、二叉樹(shù)使用二叉鏈表存儲(chǔ)，若p指針指向二叉樹(shù)的一個(gè)結(jié)點(diǎn)，當(dāng)p->lchild=NULL時(shí)，則（）。p結(jié)點(diǎn)左孩子為空 B．p結(jié)點(diǎn)有右孩子p結(jié)點(diǎn)右孩子為空 D．p結(jié)點(diǎn)有左孩子15、在具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中，若結(jié)點(diǎn)i有左孩子，則結(jié)點(diǎn)i的左孩子編號(hào)為（）。A．2i B．不存在 C．2i+1 D．2i-116、將含100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根這一層開(kāi)始，按從上到下從左到右依次對(duì)結(jié)點(diǎn)編號(hào)，根結(jié)點(diǎn)的編號(hào)為１。編號(hào)為50的結(jié)點(diǎn)X的雙親的編號(hào)為（）。A．25B．48C．10017、三個(gè)結(jié)點(diǎn)可以構(gòu)成（）種不同形狀的二叉樹(shù)。１ Ｂ．2 C．3 D．518、若由樹(shù)轉(zhuǎn)化得到的二叉樹(shù)是非空的二叉樹(shù)，則二叉樹(shù)形狀是（）。A．根結(jié)點(diǎn)無(wú)右子樹(shù)的二叉樹(shù) B．根結(jié)點(diǎn)無(wú)左子樹(shù)的二叉樹(shù)C．根結(jié)點(diǎn)可能有左子樹(shù)和右子樹(shù) D．各結(jié)點(diǎn)只有一個(gè)孩子的二叉樹(shù)19、哈夫曼樹(shù)是訪問(wèn)葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度（）的二叉樹(shù)。A．最短 B．最長(zhǎng) C．可變 D．不定20、某二叉樹(shù)的前序和后序序列正好相反，則該二叉樹(shù)一定是（）的二叉樹(shù)。A．空或只有一個(gè)結(jié)點(diǎn) B．高度等于其結(jié)點(diǎn)數(shù)C．任一結(jié)點(diǎn)無(wú)左孩子 D．任一結(jié)點(diǎn)無(wú)右孩子填空題：1、12個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的葉結(jié)點(diǎn)有（5）個(gè)。2、在任何一棵二叉樹(shù)中，度為０的結(jié)點(diǎn)n0和度為２的結(jié)點(diǎn)n2之間的關(guān)系是（n0=n2+1。3、已知完全二叉樹(shù)的第4層有4個(gè)結(jié)點(diǎn)，則其葉子結(jié)點(diǎn)數(shù)是（11）。4、10個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的葉結(jié)點(diǎn)有（3）個(gè)。5、深度為6的二叉樹(shù)最多有（63）個(gè)結(jié)點(diǎn)。6、一個(gè)二叉樹(shù)中，度為2的結(jié)點(diǎn)有3個(gè)，則葉結(jié)點(diǎn)有（4）個(gè)。7、若二叉樹(shù)的一個(gè)葉子是某子樹(shù)的中根遍歷序列中的第一個(gè)結(jié)點(diǎn)，則它必是該子樹(shù)的后根遍歷序列中的（第一）個(gè)結(jié)點(diǎn)。8、下圖為某樹(shù)的靜態(tài)雙親表示，則結(jié)點(diǎn)D、E的雙親結(jié)點(diǎn)分別為（B）和（C）。A-1B0C0D1E2012349、具有m個(gè)葉結(jié)點(diǎn)的哈夫曼樹(shù)共有（2m-1）個(gè)結(jié)點(diǎn)。10、二叉樹(shù)通常有（順序）存儲(chǔ)結(jié)構(gòu)和（鏈?zhǔn)剑┐鎯?chǔ)結(jié)構(gòu)兩種。11、二叉樹(shù)在二叉鏈表表示方式下，p指向二叉樹(shù)的根結(jié)點(diǎn)，經(jīng)運(yùn)算s=p；while(s->rchild)s=s->rchild后，s指針指向（根或最右）結(jié)點(diǎn)。判斷題：1、完全二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)沒(méi)有左孩子，則它必須是葉子。（TRUE）2、由二叉樹(shù)結(jié)點(diǎn)的先根序列和后根序列可以唯一地確定一棵二叉樹(shù)。（FALSE）3、一般在哈夫曼樹(shù)中，權(quán)值越大的葉子離根結(jié)點(diǎn)越近。（TRUE）4、二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)的度都是2。（FALSE）5、一棵哈夫曼樹(shù)中不存在度為1的結(jié)點(diǎn)。（TRUE）解析：n=n0+n1+n2;2n0-1=n;n0=n2+1;可推出不存在n1;6、若一個(gè)二叉樹(shù)的葉結(jié)點(diǎn)是先根遍歷序列的最后一個(gè)結(jié)點(diǎn)，則它必是中根遍歷的序列中的最后一個(gè)結(jié)點(diǎn)。（FALSE）7、中序遍歷二叉排序樹(shù)的結(jié)點(diǎn)不能得到排好序的結(jié)點(diǎn)序列。（FALSE）8、完全二叉樹(shù)一定是滿二叉樹(shù)。（FALSE）9、由二叉樹(shù)的前序和中序遍歷序列可以推導(dǎo)出此二叉樹(shù)的后序遍歷序列。（TRUE）10、滿二叉樹(shù)一定是完全二叉樹(shù)。（TRUE）11、完全二叉樹(shù)可采用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)存儲(chǔ)，非完全二叉樹(shù)則不能。（FALSE）應(yīng)用題：1、對(duì)給定的一組權(quán)值W=｛5，2，9，11，8，3，7｝，試構(gòu)造相應(yīng)的哈夫曼樹(shù)，并計(jì)算它的帶權(quán)路徑長(zhǎng)度。參考答案：帶權(quán)路徑長(zhǎng)度=11*1+9*2+8*3+7*3+5*3+3*4+2*42、已知一棵二叉樹(shù)的前序序列和中序序列分別如下，請(qǐng)畫(huà)出該二叉樹(shù)。前序序列：ABDGJKLHCEIF中序序列：BGJLKDHAEICF解析：前序序列：ABDGJKLHCEIF中序序列：BGJLKDHAEICF找到根后，可確定左子樹(shù)結(jié)點(diǎn)和右子樹(shù)結(jié)點(diǎn)，然后遞歸進(jìn)行即可；3、試找出分別滿足下列條件的所有二叉樹(shù)。（1）前序序列和中序序列相同；（2）中序序列和后序序列相同；（3）前序序列和后序序列相同。解答：只有空樹(shù)或只有根結(jié)點(diǎn)的二叉樹(shù)，同時(shí)滿足上述三個(gè)條件；4、設(shè)有一組結(jié)點(diǎn)，其權(quán)值W=｛1，4，9，16，25，36，49，64，81，100｝，畫(huà)出由這些結(jié)點(diǎn)所構(gòu)成的哈夫曼樹(shù)，并計(jì)算帶權(quán)路徑長(zhǎng)度。解析：參考第一題；5、畫(huà)出下圖所示森林經(jīng)轉(zhuǎn)換后所對(duì)應(yīng)的二叉樹(shù)。eq\o\ac(○,A)eq\o\ac(○,B)eq\o\ac(○,C)eq\o\ac(○,D)eq\o\ac(○,E)eq\o\ac(○,F)eq\o\ac(○,J)eq\o\ac(○,G)