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

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

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

3、性結(jié)構(gòu)的順序存儲結(jié)構(gòu)是一種隨機(jī)存取的存儲結(jié)構(gòu)，線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是一種順序存取的存儲結(jié)構(gòu)。線性表若采用鏈?zhǔn)酱鎯Ρ硎緯r(shí)所有結(jié)點(diǎn)之間的存儲單元地址可連續(xù)可不連續(xù)。邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、所含結(jié)點(diǎn)個(gè)數(shù)都無關(guān)。3、以下哪一個(gè)術(shù)語與數(shù)據(jù)的存儲結(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存儲方式C結(jié)構(gòu)D數(shù)據(jù)項(xiàng)6、研究數(shù)據(jù)結(jié)構(gòu)就是研究（ ）。A數(shù)據(jù)的邏輯結(jié)構(gòu)B數(shù)據(jù)的存儲結(jié)構(gòu)C數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)D數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其數(shù)據(jù)的運(yùn)算

4、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ù)的存儲方式C數(shù)據(jù)存儲結(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;i<m;i+ +) for(j=0;j<n;j+ +) aij=i*j； AO（m2） BO（n

5、2） CO（m×n） 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ù)的存儲結(jié)構(gòu)（物理結(jié)構(gòu)）可以用

6、（ ）、（ ）、（ ）及散列存儲等四種存儲方法表示。三、 判斷題：1、順序存儲方式優(yōu)點(diǎn)是存儲密度大，且插入和刪除運(yùn)算效率高。 （ ）2、順序存儲結(jié)構(gòu)屬于靜態(tài)存儲結(jié)構(gòu)，鏈?zhǔn)酱鎯Y(jié)構(gòu)屬于動(dòng)態(tài)存儲結(jié)構(gòu)。 （ ）3、線性表的鏈接存儲，表中元素的邏輯順序與物理順序一定相同。 （ ）4、數(shù)據(jù)的機(jī)內(nèi)表示稱為數(shù)據(jù)的存儲結(jié)構(gòu)。 （ ）5、在線性表的順序存儲結(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)、（存儲結(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;j<=n;j+) x=x+k;”的時(shí)間復(fù)雜度為(O(n2)。5、數(shù)據(jù)的存儲結(jié)構(gòu)（物理結(jié)構(gòu)）可以用（順序）、（鏈?zhǔn)剑?、（索引）及散列存儲等四種存儲方法表示。三、判斷題1、順序存儲方式優(yōu)點(diǎn)是存儲密度大，且插入和刪除運(yùn)算效率高。 （×）2、順序存儲結(jié)構(gòu)屬于靜態(tài)存儲結(jié)構(gòu)，鏈?zhǔn)酱鎯?/p>

8、結(jié)構(gòu)屬于動(dòng)態(tài)存儲結(jié)構(gòu)。 （×）3、線性表的鏈接存儲，表中元素的邏輯順序與物理順序一定相同。 （ ）4、數(shù)據(jù)的機(jī)內(nèi)表示稱為數(shù)據(jù)的存儲結(jié)構(gòu)。 （）5、在線性表的順序存儲結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上并不一定相鄰。（×） 6、數(shù)據(jù)元素是數(shù)據(jù)的最小單位。 （×）7、基于某種邏輯結(jié)構(gòu)之上的運(yùn)算，其實(shí)現(xiàn)是惟一的。 （×）2 線性表一、 選擇題：1、在表長為n的順序表上做插入運(yùn)算，平均要移動(dòng)的結(jié)點(diǎn)數(shù)為（ ）。 An Bn/2 Cn/3 Dn/42、在一個(gè)單鏈表中，若P所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在P之后插入S所指結(jié)點(diǎn)，則執(zhí)行（ ） AS->next=P-&g

9、t;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） DO（n2） 解析：單就插入運(yùn)算而言，算法時(shí)間復(fù)雜度為（1），但要將指針定位到鏈表末尾，指針移動(dòng)的時(shí)間復(fù)雜度為O（n）；4、對于只在表的首、尾兩端進(jìn)行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為（ ） A順序表 B用頭指針表示的單循環(huán)鏈表 C用尾指針表示的單循

10、環(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)的時(shí)間復(fù)雜度是（ ） AO（n） BO（1） CO（log2n） DO（n2）7、線性表采用鏈?zhǔn)?/p>

11、存儲時(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)酱鎯?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)線性表

12、的敘述中，正確的是（ ） A線性表中的元素之間是線性關(guān)系 B線性表中至少有一個(gè)元素 C線性表中任何一個(gè)元素有且僅有一個(gè)直接前趨 D線性表中任何一個(gè)元素有且僅有一個(gè)直接后繼12、在單鏈表中，存儲每個(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ù)是（ ）。An B.2n-1 C.2n D.n-114、鏈表不具有的特點(diǎn)是（ ）。A隨機(jī)訪問 B不必事先估計(jì)存儲空間C插入刪除時(shí)不需移動(dòng)元素 D所需的空間與線性表成正比15、在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接前

13、趨，若在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ī)訪問任一元素B插入、刪除需要移動(dòng)元素C不必事先估計(jì)存儲空間D存儲空間是靜態(tài)分配的17、一個(gè)順序表一旦說明，其中可用空間大小（ ）A已固定B可以改變C不能固定D動(dòng)態(tài)變化18、若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前趨元素，則采用（ ）存儲

14、方式最節(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ī)訪問任一元素 B插入、刪除不需要移動(dòng)元素C不必事先估計(jì)存儲空間 D所需空間與線性表長度成正比21、下面關(guān)于線性表的敘述中，錯(cuò)誤的是（ ）。A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元B線性表采用順序存儲，便于進(jìn)行插入和刪除操作C線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元D線性表采用鏈接存儲，便于進(jìn)行

15、插入和刪除操作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)（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

16、=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)的條件是（）。4、在具有n個(gè)結(jié)點(diǎn)的雙鏈表中做插入、刪除運(yùn)算，平均時(shí)間復(fù)雜度為（）。5、在一個(gè)長度為n的順序表中第i個(gè)元素（1 i n）之前插入一個(gè)元素時(shí)，需向后移動(dòng)（）個(gè)元素。6、在雙循環(huán)鏈表中，若要在指針p所指結(jié)點(diǎn)之前插入指針s所指的結(jié)點(diǎn)，則需執(zhí)行下列語句：s->prior=p->prior;p->

17、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)），則刪除結(jié)點(diǎn)p的直接后繼結(jié)點(diǎn)的語句是（ ）；刪除首結(jié)點(diǎn)的語句是（ ）。三、 判斷題1、在有序的順序表和有序的鏈表上，均可以使用折半查找法來提高查找速度。（ ）2、順序存儲的線性表可以隨機(jī)存取。 （ ）3、線性表采用順序存儲，必須占用一片

18、連續(xù)的存儲單元。 （ ）四、 程序設(shè)計(jì)題數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)類型定義如下： 順序存儲： typedef struct int *base; int length; int listsize; sqlist; 鏈?zhǔn)酱鎯Γ?typedef struct LinkList int data; struct LinkList *next; Node,*LinkList; 1、已知帶頭結(jié)點(diǎn)的單鏈表head中的結(jié)點(diǎn)是按整數(shù)值遞增排序的，寫一算法將值為x的結(jié)點(diǎn)插入到表head中，使head仍然有序。2、用尾插法建立帶頭結(jié)點(diǎn)的單鏈表。3、用頭插法建立帶頭結(jié)點(diǎn)的單鏈表。4、對給定的單鏈表L，編寫一個(gè)刪除L中值為x的結(jié)

19、點(diǎn)的直接前趨結(jié)點(diǎn)算法。5、用順序存儲結(jié)構(gòu)實(shí)現(xiàn)線性表的就地逆置算法，即將（a1,a2, ai,an）逆置為（an,ai,a2,a1）;6、用鏈?zhǔn)酱鎯Y(jié)構(gòu)實(shí)現(xiàn)線性表的就地逆置算法，即將（a1,a2, ai,an）逆置為（an,ai,a2,a1）;7、使用順序存儲結(jié)構(gòu)分別實(shí)現(xiàn)A=AB和A=AB運(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的語句序列是（P=R; w

20、hile(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è)元素（1 i n）之前插入一個(gè)元素時(shí)，需向后移動(dòng)（n-i+1）個(gè)元素。6、在雙循環(huán)鏈表中，若要在指針p所指結(jié)點(diǎn)之前插入指針s所指的結(jié)點(diǎn)，則需執(zhí)行下列語句：s->prior=p->prior;p->prior->next=s;( s->next=p;

21、)和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、在有序的

22、順序表和有序的鏈表上，均可以使用折半查找法來提高查找速度。（×）2、順序存儲的線性表可以隨機(jī)存取。 （）3、線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。 （）四、程序設(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->data<x) p=p->next;/指針定位p->next=x;x->next=p->next;2、用尾插入法建立帶頭結(jié)點(diǎn)的單鏈表。 請參考教材“數(shù)據(jù)

23、結(jié)構(gòu)-清華大學(xué)嚴(yán)尉敏著評p29-p30”;3、用頭插入法建立帶頭結(jié)點(diǎn)的單鏈表。請參考教材“數(shù)據(jù)結(jié)構(gòu)-清華大學(xué)嚴(yán)尉敏著評p29-p30”;4、對給定的單鏈表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) ruturn

24、 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、用順序存儲結(jié)構(gòu)實(shí)現(xiàn)線性表的就地逆置算法，即將（a1,a2, ai,an）逆置為（an,ai,a2,a1）;重點(diǎn)語句： for(i=0;i<sqlist.length/2;i+) sqlist.baseißàsqlist.basesqlist.length-i;/第i個(gè)元素和第length-i元素

25、交換存儲6、用鏈?zhǔn)酱鎯Y(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) Return NULL; q=pànext;/q指針指向第二個(gè)結(jié)點(diǎn) pànext=NULL; while(q) r=qànext；/第一次循環(huán)時(shí)，r指向第三個(gè)結(jié)點(diǎn) qànext=p;/第二個(gè)結(jié)點(diǎn)的NEXT指向第一個(gè)結(jié)點(diǎn) p=q;/p總是指向逆置后的第一個(gè)結(jié)點(diǎn) q=r;/q總是指向剩

26、余單鏈表的第一個(gè)結(jié)點(diǎn)，為將其作為逆置單鏈表的第一個(gè)結(jié)點(diǎn)作準(zhǔn)備 return p; 兩外，解決本體還有另外一種思路，將結(jié)點(diǎn)數(shù)據(jù)域拷貝到一個(gè)一維數(shù)組中，然后反過來填充單鏈表結(jié)點(diǎn)的數(shù)據(jù)域。7、使用順序存儲結(jié)構(gòu)分別實(shí)現(xiàn)A=AB和A=AB運(yùn)算；請參考清華大學(xué)出版社出版，嚴(yán)尉敏編著數(shù)據(jù)結(jié)構(gòu)C語言版P20例2-1；3 棧和隊(duì)列一、 選擇題：1、循環(huán)隊(duì)列是空隊(duì)列的條件是（ ） AQ . rear = = Q . front B（Q . rear + 1）%maxsize = = Q .front CQ . rear = = 0 DQ. front = = 02、鏈棧與順序棧相比，比較明顯的優(yōu)點(diǎn)是（ ） A通常

27、不會出現(xiàn)棧滿的情況 B通常不會出現(xiàn)棧空的情況C插入操作更加方便 D刪除操作更加方便分析不管是鏈棧還是順序棧，其插入、刪除操作都是在棧頂進(jìn)行的，都比較方便，所以不可能選C)，D)。對鏈棧來講，當(dāng)棧中沒有元素而又要執(zhí)行出棧操作時(shí)，就會出現(xiàn)?？宅F(xiàn)象，故B)也是不正確的。只要內(nèi)存足夠大，鏈棧上就不會出現(xiàn)棧滿現(xiàn)象。而對順序棧來講，由于其大小是事先確定好的，因此可能會出現(xiàn)棧滿現(xiàn)象。所以A)是正確的。3、若一個(gè)棧的輸入序列是，n，輸出序列的第一個(gè)元素是，則第個(gè)輸出元素是（ ） An - i Bn i + 1 Ci D不確定4、棧與一般線性表的區(qū)別主要在（ ） A元素個(gè)數(shù) B元素類型 C邏輯結(jié)構(gòu) D插入、刪除

28、元素的位置5、一個(gè)鏈棧的棧頂指針是top，則執(zhí)行出棧操作時(shí)（棧非空），用x保存被刪除結(jié)點(diǎn)，則執(zhí)行（ ） Ax = top; top = top ànext； Bx = topàdata； Ctop = top ànext;x = top à data； Dx = topà data;top = topà next；分析棧頂元素出棧后，應(yīng)該從棧底位置即第一個(gè)結(jié)點(diǎn)開始重新定位，執(zhí)行語句是：q=base ; while(qànext!=top) q=qànext; free(top); top=q;6、對于一個(gè)棧，給定輸

29、入序列為1，2，3，則下列不可能為輸出序列的是（ ） A1，2，3 B3，2，1 C3，1，2 D2，1，3分析 每個(gè)元素進(jìn)棧后立即出棧，結(jié)果是答案A；三個(gè)元素全部進(jìn)棧后再出棧，得到答案B；1和2進(jìn)棧后出棧，然后3入棧后出棧，得到答案D；而C答案不可能的原因是：3出棧后，說明1、2還在棧中，1出棧后2還在棧中，說明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，則棧的不

30、可能的輸出序列是（ ）。Ae,d,c,b,a Bd,e,c,b,a Cd,c,e,a,b Da,b,c,d,e10、設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號是否配對出現(xiàn)的算法，采用（ ）數(shù)據(jù)結(jié)構(gòu)最佳。A線性表的順序存儲結(jié)構(gòu) B棧 C隊(duì)列 D線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)11、循環(huán)隊(duì)列的特點(diǎn)之一是不會產(chǎn)生（ ）。 A上溢出 B下溢出 C隊(duì)滿 D假溢出12、設(shè)數(shù)組Datan作為循環(huán)隊(duì)列Q的存儲空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行入隊(duì)操作的語句為（ ）。Arear=(rear+1)%(n+1) Bfront=(front+1)% n Crear=(rear+1)% n Dfront=(front+1)

31、%(n+1)13、棧是限定在（ ）處進(jìn)行插入或刪除操作的線性表。A端點(diǎn) B棧底 C棧頂 D中間14、容量是10的循環(huán)隊(duì)列的隊(duì)頭位置qàfront為2，隊(duì)列中的數(shù)據(jù)元素個(gè)數(shù)為5，則隊(duì)的第一個(gè)數(shù)據(jù)元素的位置是（ ）A2B7C1D0分析 (front-rear+10)%10=5,并且front和rear的取值范圍均是09，所以只有（7-2+10）%10=5。 15、循環(huán)隊(duì)列的出隊(duì)操作是（ ）Aqàfront=(qàfront+1)%maxsize; Bqàfront=qàfront+1;Cqàrear=(qàrear+1)%max

32、size; Dqàrear=qàrear+1;16、當(dāng)循環(huán)隊(duì)列q是滿隊(duì)列時(shí)，存放隊(duì)列元素的數(shù)組data有n個(gè)元素，則data中存放（ ）個(gè)數(shù)據(jù)元素。AnB. n-1C. n-2D.0分析 容量為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

33、fànext=s;f=sBrànext=s;r=s;Csànext=r;r=s; Dsànext=f;f=s19、循環(huán)隊(duì)列的入隊(duì)操作應(yīng)為（ ）。Aqàrear=qàrear+1;qàdataqàrear=x;Bqàdataqàrear+=x;Cqàrear=(qàrear+1)%maxsize; qàdataqàrear=x;Dqàdataqàrear=x;q->rear=(qàrear+1)%maxsize;20、棧和

34、隊(duì)列都是（ ）。A限制存取點(diǎn)的線性結(jié)構(gòu) B限制存取點(diǎn)的非線性結(jié)構(gòu)C順序存儲的線性結(jié)構(gòu) D鏈?zhǔn)酱鎯Φ木€性結(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)棧和退棧操作，則對輸入序列a，b，c，d，e進(jìn)行一系列棧操作SSXSXSSXXX之后，得到的輸出序列為（）。4、隊(duì)列的隊(duì)尾位置隨著（）而變化。5、在（ ）的情況下，鏈隊(duì)列的出隊(duì)操作需要修改尾指針。6、從棧頂指針為top的鏈棧中刪除一個(gè)

35、結(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存儲在數(shù)組s->datamax中，對s進(jìn)行出棧操作，執(zhí)行的語句序列是（ ）。9、以下運(yùn)算實(shí)現(xiàn)在循環(huán)隊(duì)列中的初始化操作void initqueue(seqqueue *q)q->front=0;( );三、 判斷題：1、循環(huán)隊(duì)列中無上溢現(xiàn)象。 （ ）2、循環(huán)隊(duì)列只有下溢，沒有上溢。 （ ）3、對順序棧而言，在棧滿狀

36、態(tài)，如果此時(shí)再作進(jìn)棧運(yùn)算，則會發(fā)生“下溢”。 （ ）4、順序隊(duì)列和循環(huán)隊(duì)列的隊(duì)滿和隊(duì)空的條件是一樣的。 （ ）5、為解決隊(duì)列“假滿”問題，可以采用循環(huán)數(shù)組實(shí)現(xiàn)隊(duì)列存儲。 （ ）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為出棧操作。2、如果編號為1、2、3的三輛列車進(jìn)入一個(gè)棧式結(jié)構(gòu)的站臺，那么可能得到的三輛列車出站序列有哪些？不可能出現(xiàn)的序列是什么？五、 程序設(shè)計(jì)題：1、寫出循環(huán)隊(duì)列入隊(duì)操作的函數(shù)。參考答案（棧和隊(duì)列）一、選擇題12

37、3456789101112131415161718192021AABDBCDBCBDCCBABBBCAB二、填空題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)棧和退棧操作，則對輸入序列a，b，c，d，e進(jìn)行一系列棧操作SSXSXSSXXX之后，得到的輸出序列為（bceda）。4、隊(duì)列的隊(duì)尾位置隨著（入隊(duì)列操作變化）而變化。5、在（鏈隊(duì)列為空）的情況下，鏈隊(duì)列的出隊(duì)操作需要修改尾指針。 分析：Q.

38、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存儲在數(shù)組s->datamax中，對s進(jìn)行出棧操作，執(zhí)行的語句序列是（sàtop-）。9、以下運(yùn)算實(shí)現(xiàn)在循環(huán)隊(duì)列中的初始化操作void initqueue(seqqueue *q)q->front=0;( qàbase=(qelemtype *)mal

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

40、）ACBED，其中I為進(jìn)棧操作，O為出棧操作。參考答案：（1）IIIOOOIOIO (2)IOIIOOIIOO2、如果編號為1、2、3的三輛列車順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的站臺，那么可能得到的三輛列車出站序列有哪些？不可能出現(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ù)。請參考清華大學(xué)出版社嚴(yán)蔚敏編著的數(shù)據(jù)結(jié)構(gòu)C語言版p65。4 串和數(shù)組（含參考答案）一、單選題 1下列那些為空串（ ） A）S=“ ” B）S=“” C）S=“” D）S

41、=“” 答案：B 2S1=“ABCD”，S2=“CD”則S2在S3中的位置是（ ） A）1 B）2 C）3 D）4 答案：C 3假設(shè)S=“abcaabcaaabca”，T=“bca”，Index (S,T,3) 的結(jié)果是（ ） A）2 B）6 C）11 D）0 答案：B 4在串中，對于SubString(&Sub,S,pos,len)基本操作，pos和len的約束條件是（ ） A）0<pos<StrLength(S)+1且1<=len<=StrLength(S)-pos+1 B）0<pos<StrLength(S)+1且0<=len<=S

42、trLength(S)-pos-1 C）1<=pos<=StrLength(S) 且0<=len<=StrLength(S)-pos+1 D）1<=pos<=StrLength(S) 且1<=len<=StrLength(S)-pos-1 答案：C 5串是一種特殊的線性表，其特殊性體現(xiàn)在( )。 A可以順序存儲 B. 數(shù)據(jù)元素是一個(gè)字符 C可以鏈接存儲 D. 數(shù)據(jù)元素可以是多個(gè)字符 答：B 6串是( )。 A少于一個(gè)字母的序列 B. 任意個(gè)字母的序列 C不少于一個(gè)字符的序列 D. 有限個(gè)字符的序列 答：D 7 串的長度是( )。 A串中不同字母的

43、個(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的從序號I的字符開始的j個(gè)字符組成的子串，len(s)返回串s的長度，則con(subs(S1，2，len(S2)，subs(S1，len(S2)，2)的結(jié)果是( )。 ABCDEF B. BCDEFG C. BCPQRST D. BCDEFEF 答：D 9 若某串的長度小于一個(gè)常數(shù)，則采用( )存儲方式最為節(jié)省空間。 A鏈?zhǔn)?B. 堆結(jié)構(gòu) C. 順序表 答：C 二、填空題： 1串

44、是每個(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在串中，對于StrCompare(S,T)基本操作，若S<T，返回值_。 答：<0 5在串順序存儲結(jié)構(gòu)中，實(shí)現(xiàn)串操作的原操作為_。答：字符序列的復(fù)制6串與線性表在邏輯結(jié)構(gòu)上極為相似，區(qū)別僅在于_ ；在基本操作上差別很大，線性表的基本操作大多數(shù)以_ 作為操作對象，而串的基本操作通常以 作為操作對象。 答：串的數(shù)據(jù)對象約

45、束為字符集 “單個(gè)元素” “串的整體” 7兩個(gè)串相等的充分必要條件是_ 且_ 。 答：兩個(gè)串的串長相等 各個(gè)對應(yīng)位置的字符都相等 8空串是指_，空格串是指_。 答：不含任何字符的串 僅含空格字符的串 三、判斷題1空串是由空白字符組成的串（ FALSE ） 2串的定長順序結(jié)構(gòu)是用一組地址連續(xù)的存儲單元存儲串值的字符序列，按照預(yù)定義的大小，為每個(gè)定義的串變量分配一個(gè)固定長度的存儲區(qū)。(TRUE ) 3串的堆分配存儲表示是用一組地址連續(xù)的存儲單元存儲串值的字符序列，但它們的存儲空間是在程序執(zhí)行過程中動(dòng)態(tài)分配得到的。（TRUE ） 4串中StrInsert(&S,pos,T)基本操作是最小的操

46、作子集（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)，反之，其他串操作（除串清除ClearString和串銷毀DestroyString外）均可在最小操作子集上實(shí)現(xiàn)。(TR

47、UE) (題源：根據(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串是字符組成的，長度為1的串和字符是否概念相同？為什么？ (題源：朱戰(zhàn)立，C版題

48、解，p86，4.2.1(典型題解)_2) 答：由于字符的長度固定為1，長度概念可以隱含，所以存儲時(shí)只需存儲該字符即可；而長度為1的串其長度概念不能隱含，必須顯示地表示出來，所以存儲時(shí)要同時(shí)存儲該字符和值為1的長度值。 五、算法設(shè)計(jì)題1設(shè)串s和串t采用順序存儲結(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è)不相等字符的大于和小于情況來決定串s和串t比較的大于和小于情況；當(dāng)串s的n個(gè)字符和串t的m個(gè)字符比較全部相等時(shí)，還需進(jìn)一步判斷此時(shí)串s或串t是