《《數(shù)據(jù)結(jié)構(gòu)》習(xí)題集》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《《數(shù)據(jù)結(jié)構(gòu)》習(xí)題集（28頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、真誠(chéng)為您提供優(yōu)質(zhì)參考資料，若有不當(dāng)之處，請(qǐng)指正。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ǔ)XXX，這種方法稱(chēng)為（ ） A索引存儲(chǔ)方法 B順序存儲(chǔ)方法 C鏈?zhǔn)酱鎯?chǔ)方法 D散列存儲(chǔ)方法 解析： 數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（映像）稱(chēng)為數(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)。順序

2、存儲(chǔ)方法：它是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)，由此得到的存儲(chǔ)表示稱(chēng)為順序存儲(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ǔ)表示稱(chēng)為鏈?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)的XXX。散列存儲(chǔ)方法：就是根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)XXX。數(shù)據(jù)結(jié)構(gòu)中，邏輯上（邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)

3、系）可以把數(shù)據(jù)結(jié)構(gòu)分成線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)。線(xiàn)性結(jié)構(gòu)的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)，線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種順序存取的存儲(chǔ)結(jié)構(gòu)。線(xiàn)性表若采用鏈?zhǔn)酱鎯?chǔ)表示時(shí)所有結(jié)點(diǎn)之間的存儲(chǔ)單元XXX可連續(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í)可以做出處理的特性稱(chēng)為（ ）。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é)構(gòu)和

4、存儲(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.線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(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)依賴(lài)于計(jì)算機(jī)語(yǔ)言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=

5、i*j； AO（m2） BO（n2） CO（mn） DO（m+n）11、算法分析的兩個(gè)主要方面是（ ）。A正確性和簡(jiǎn)明性 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ù)的（）無(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)）可

6、以用（ ）、（ ）、（ ）及散列存儲(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、線(xiàn)性表的鏈接存儲(chǔ)，表中元素的邏輯順序與物理順序一定相同。 （ ）4、數(shù)據(jù)的機(jī)內(nèi)表示稱(chēng)為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。 （ ）5、在線(xiàn)性表的順序存儲(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)是相互

7、之間存在一種或多種特定關(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;jnext=P-next;P-next=S BP-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

8、） DO（n2） 解析：?jiǎn)尉筒迦脒\(yùn)算而言，算法時(shí)間復(fù)雜度為（1），但要將指針定位到鏈表末尾，指針移動(dòng)的時(shí)間復(fù)雜度為O（n）；4、對(duì)于只在表的首、尾兩端進(jìn)行插入操作的線(xià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、線(xiàn)性表是（ ） A一

9、個(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ù)雜度是（ ） AO（n） BO（1） CO（log2n） DO（n2）7、線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的XXX（ ） 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ō)明單鏈表是線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)9、帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（ ） Ahead = NULL； Bhead - next = NULL； C

10、head - 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)線(xiàn)性表的敘述中，正確的是（ ） A線(xiàn)性表中的元素之間是線(xiàn)性關(guān)系 B線(xiàn)性表中至少有一個(gè)元素 C線(xiàn)性表中任何一個(gè)元素有且僅有一個(gè)直接前趨 D線(xiàn)性表中任何一個(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ù)是

11、（ ）。An B.2n-1 C.2n D.n-114、鏈表不具有的特點(diǎn)是（ ）。A隨機(jī)訪問(wèn) B不必事先估計(jì)存儲(chǔ)空間C插入刪除時(shí)不需移動(dòng)元素 D所需的空間與線(xiàn)性表成正比15、在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接前趨，若在p，q之間插入s結(jié)點(diǎn)，則執(zhí)行的操作是（ ）。 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ī)訪問(wèn)任一元素B插入、刪除需要移動(dòng)元素C不必事先估計(jì)存儲(chǔ)空間D存儲(chǔ)空間是靜態(tài)分配的17、一個(gè)順序表一旦說(shuō)明，其中

12、可用空間大小（ ）A已固定B可以改變C不能固定D動(dòng)態(tài)變化18、若某線(xiàn)性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前趨元素，則采用（ ）存儲(chǔ)方式最節(jié)省時(shí)間。A 順序表B單鏈表C雙向鏈表D單循環(huán)鏈表19、兩個(gè)指針P和Q，分別指向單鏈表的兩個(gè)元素，P所指元素是Q所指元素的前驅(qū)的條件是（ ）。AP-next=QBQ-next=PCP=QDP-next=Q-next20、鏈表不具有的特點(diǎn)是（ ）。A可隨機(jī)訪問(wèn)任一元素 B插入、刪除不需要移動(dòng)元素C不必事先估計(jì)存儲(chǔ)空間 D所需空間與線(xiàn)性表長(zhǎng)度成正比21、下面關(guān)于線(xiàn)性表的敘述中，錯(cuò)誤的是（ ）。A線(xiàn)性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元B線(xiàn)性表采用

13、順序存儲(chǔ)，便于進(jìn)行插入和刪除操作C線(xiàn)性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元D線(xiàn)性表采用鏈接存儲(chǔ)，便于進(jìn)行插入和刪除操作22、在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O(1)的操作是（ ）。A訪問(wèn)第i個(gè)結(jié)點(diǎn)（1in）和求第i個(gè)結(jié)點(diǎn)的直接前趨（2in）B在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（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-

14、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的語(yǔ)句序列是（ ）。3、在帶頭結(jié)點(diǎn)的雙鏈表中，指針?biāo)附Y(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-nex

15、t=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ǔ)的線(xiàn)性表可以隨機(jī)存取。 （ ）3、線(xiàn)性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。 （ ）四、 程序設(shè)計(jì)題數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)類(lèi)型定義如下

16、： 順序存儲(chǔ)： typedef struct int *base; int length; int listsize; sqlist; 鏈?zhǔn)酱鎯?chǔ)： typedef struct LinkList int data; struct LinkList *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)線(xiàn)性表的就地逆置算法，

17、即將（a1,a2, ai,an）逆置為（an,ai,a2,a1）;6、用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)線(xiàn)性表的就地逆置算法，即將（a1,a2, ai,an）逆置為（an,ai,a2,a1）;7、使用順序存儲(chǔ)結(jié)構(gòu)分別實(shí)現(xiàn)A=AB和A=AB運(yùn)算；參考答案（線(xià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-ne

18、xt=S; S-next=NULL;）。3、在帶頭結(jié)點(diǎn)的雙鏈表中，指針?biāo)附Y(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-

19、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ǔ)的線(xiàn)性表可以隨機(jī)存取。 （）3、線(xiàn)性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。 （）四、程序設(shè)計(jì)題1、已知帶頭結(jié)點(diǎn)的單鏈表head中的結(jié)點(diǎn)是按整數(shù)值遞

20、增排序的，寫(xiě)一算法將值為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ì)給定的單鏈表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

21、定位到值為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) ruturn error;/不存在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)線(xiàn)性表的就地逆置算法，即將（a1,a2, ai,an）逆置為（an,ai,a2,a1）;重點(diǎn)語(yǔ)句： for(i=0;irear=(qrear+1)%maxsiz

22、e;20、棧和隊(duì)列都是（ ）。A限制存取點(diǎn)的線(xiàn)性結(jié)構(gòu) B限制存取點(diǎn)的非線(xiàn)性結(jié)構(gòu)C順序存儲(chǔ)的線(xiàn)性結(jié)構(gòu) D鏈?zhǔn)酱鎯?chǔ)的線(xiàn)性結(jié)構(gòu)21、實(shí)現(xiàn)遞歸調(diào)用屬于（ ）的應(yīng)用。A隊(duì)列 B棧 C 數(shù)組 D樹(shù)二、 填空題： 1、循環(huán)隊(duì)列用數(shù)組datam存放其元素值，已知其頭、尾指針?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的

23、鏈棧中刪除一個(gè)結(jié)點(diǎn)，并將被刪除的結(jié)點(diǎn)的值保存在x中，其操作步驟為（ ）；top=top-next;。7、用數(shù)組Am來(lái)存放循環(huán)隊(duì)列q的元素，且它的頭、尾指針?lè)謩e為front和rear，隊(duì)列滿(mǎn)足條件(q.rear+1)%m=q.front,則隊(duì)列中當(dāng)前的元素個(gè)數(shù)為（ ）。8、順序棧s存儲(chǔ)在數(shù)組s-datamax中，對(duì)s進(jìn)行出棧操作，執(zhí)行的語(yǔ)句序列是（ ）。9、以下運(yùn)算實(shí)現(xiàn)在循環(huán)隊(duì)列中的初始化操作void initqueue(seqqueue *q)q-front=0;( );三、 判斷題：1、循環(huán)隊(duì)列中無(wú)上溢現(xiàn)象。 （ ）2、循環(huán)隊(duì)列只有下溢，沒(méi)有上溢。 （ ）3、對(duì)順序棧而言，在棧滿(mǎn)狀態(tài)，如果此

24、時(shí)再作進(jìn)棧運(yùn)算，則會(huì)發(fā)生“下溢”。 （ ）4、順序隊(duì)列和循環(huán)隊(duì)列的隊(duì)滿(mǎn)和隊(duì)空的條件是一樣的。 （ ）5、為解決隊(duì)列“假滿(mǎn)”問(wèn)題，可以采用循環(huán)數(shù)組實(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為出棧操作。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ì)列）一、選擇題1234567

25、89101112131415161718192021AABDBCDBCBDCCBABBBCAB二、填空題1、循環(huán)隊(duì)列用數(shù)組datam存放其元素值，已知其頭、尾指針?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=

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

27、; qrear=0;);三、判斷題1、循環(huán)隊(duì)列中無(wú)上溢現(xiàn)象。 （）2、循環(huán)隊(duì)列只有下溢，沒(méi)有上溢。 （）3、對(duì)順序棧而言，在棧滿(mǎn)狀態(tài)，如果此時(shí)再作進(jìn)棧運(yùn)算，則會(huì)發(fā)生“下溢”。 （）4、順序隊(duì)列和循環(huán)隊(duì)列的隊(duì)滿(mǎn)和隊(duì)空的條件是一樣的。 （）5、為解決隊(duì)列“假滿(mǎn)”問(wèn)題，可以采用循環(huán)隊(duì)列實(shí)現(xiàn)隊(duì)列存儲(chǔ)。 （）6、隊(duì)列是后進(jìn)先出的線(xià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

28、、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。4 串和數(shù)組（含參考答案）一、單選題 1下列那些為空串（ ） A）S=“ ” B）S=“” C）S=“” D）S=“” 答案：B 2S1=“ABCD”，S2=“CD”則S2在S3中的位置是（ ） A）1 B）2 C）3 D）4 答案：C 3假

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

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

31、s)返回串s的長(zhǎng)度，則con(subs(S1，2，len(S2)，subs(S1，len(S2)，2)的結(jié)果是( )。 ABCDEF B. BCDEFG C. BCPQRST D. BCDEFEF 答：D 9 若某串的長(zhǎng)度小于一個(gè)常數(shù)，則采用( )存儲(chǔ)方式最為節(jié)省空間。 A鏈?zhǔn)?B. 堆結(jié)構(gòu) C. 順序表 答：C 二、填空題： 1串是每個(gè)結(jié)點(diǎn)僅由一個(gè)字符組成的_。 答：線(xiàn)性表 2在串中，SubString (“student”,5,0) 的結(jié)果是_。 答：“” 3假設(shè)S=“abcaabcaaabca”，T=“bca”，V=“x”，Replace (S,T,V)結(jié)果是_。 答：“axaxaax”

32、 4在串中，對(duì)于StrCompare(S,T)基本操作，若ST，返回值_。 答：0 5在串順序存儲(chǔ)結(jié)構(gòu)中，實(shí)現(xiàn)串操作的原操作為_(kāi)。答：字符序列的復(fù)制6串與線(xiàn)性表在邏輯結(jié)構(gòu)上極為相似，區(qū)別僅在于_ ；在基本操作上差別很大，線(xiàn)性表的基本操作大多數(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)是用一組

33、XXX連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列，按照預(yù)定義的大小，為每個(gè)定義的串變量分配一個(gè)固定長(zhǎng)度的存儲(chǔ)區(qū)。(TRUE ) 3串的堆分配存儲(chǔ)表示是用一組XXX連續(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è)串中的所有字符均在

34、另一串中出現(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,+

35、), 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

36、的比較操作，要求比較結(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ù)返回

37、 0。 解：int StrCompare(SStrType s,SStrType t) int n=s.length, m=t.length, i,j,tag; i=0; j=0; while(in &jt.strj) tag=1; /*說(shuō)明st,退出比較*/ return tag; else tag=-1; /*說(shuō)明sm) tag=1; /*若串t只和串s的前m個(gè)字符相等則st*/ else if(nm) tag=-1;/*若串s只和串t的前n個(gè)字符相等則st*/ return tag; 2輸入一個(gè)由若干單詞組成的文本行，每個(gè)單詞之間用若干個(gè)空格隔開(kāi)，統(tǒng)計(jì)此文本中單詞的個(gè)數(shù)。 (題源：寧正元

38、，C版題解，p44，4.2_12) 提示：要統(tǒng)計(jì)單詞的個(gè)數(shù)先要解決如何判斷一個(gè)單詞，應(yīng)該從輸入行的開(kāi)頭一個(gè)字符一個(gè)字符地去辨別。假定把一個(gè)文本行放在數(shù)組r中，那么就相當(dāng)于從r0開(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í)不僅要滿(mǎn)足當(dāng)前所檢查的這個(gè)字符是非空格，而且要滿(mǎn)足所檢查的前一個(gè)字符是空格。 解：int count(r) char r80; ch

39、ar prec,nowc; int num,j; prec= ; num=0; for(j=0;j80;j+) nowc=rj; if(nowc!= )&(prec= ) num+; prec=nowc; return num; /*count*/ 3編寫(xiě)算法，求串s所含不同字符的總數(shù)和每種字符的個(gè)數(shù)。 (題源：嚴(yán)蔚敏，C版習(xí)題集，p29，4.18) 解：typedef struct char ch; int num; mytype; void StrAnalyze(Stringtype S) /統(tǒng)計(jì)串S中字符的種類(lèi)和個(gè)數(shù) mytype TMAXSIZE; /用結(jié)構(gòu)數(shù)組T存儲(chǔ)統(tǒng)計(jì)結(jié)果 for(

40、i=1;i=S0;i+) c=S;j=0; while(Tj.ch & Tj.ch!=c) j+; /在結(jié)構(gòu)數(shù)組T中逐元素查找當(dāng)前字符c是否已記錄過(guò). /當(dāng)循環(huán)停止時(shí)，再看是什么原因造成的停止。 if(Tj.ch) Tj.num+; /循環(huán)停止時(shí)Tj.ch不等于NULL,說(shuō)明是由于Tj.ch=c所致 /若是 Tj.ch =c所致則說(shuō)明字符c在串s中已經(jīng)出現(xiàn)過(guò) /故將其個(gè)數(shù)加1. else Tj=c,1; /否則為首次出現(xiàn)，將其出現(xiàn)次數(shù)記為1. /for for(j=0;Tj.ch;j+) /打印每個(gè)字符在串s中的出現(xiàn)次數(shù)。 printf(“%c: %dn”,Tj.num); /StrAnalyze 5 數(shù)組和廣義表（收集整理題目）一、 單項(xiàng)選擇題1. 常對(duì)數(shù)組進(jìn)行的兩種基本操作是_。A. 建立與刪除 B. 索引和修改 C. 對(duì)數(shù)據(jù)元素的存取和修改 D. 查