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

《《數(shù)據(jù)結(jié)構(gòu)》習題集》由會員分享，可在線閱讀，更多相關(guān)《《數(shù)據(jù)結(jié)構(gòu)》習題集（28頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、真誠為您提供優(yōu)質(zhì)參考資料，若有不當之處，請指正。 1 緒論 一、選擇題： 1、下列算法的時間復(fù)雜度是（ ） for(i=0;i

2、結(jié)構(gòu)。它包括數(shù)據(jù)元素的表示和關(guān)系的表示。數(shù)據(jù)元素之間的關(guān)系有兩種不同的表示方法：順序映象和非順序映象，并由此得到兩種不同的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。順序存儲方法：它是把邏輯上相鄰的結(jié)點存儲在物理位置相鄰的存儲單元里，結(jié)點間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)，由此得到的存儲表示稱為順序存儲結(jié)構(gòu)。順序存儲結(jié)構(gòu)是一種最基本的存儲表示方法，通常借助于程序設(shè)計語言中的數(shù)組來實現(xiàn)。鏈式存儲方法：它不要求邏輯上相鄰的結(jié)點在物理位置上亦相鄰，結(jié)點間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存儲表示稱為鏈式存儲結(jié)構(gòu)，鏈式存儲結(jié)構(gòu)通常借助于程序設(shè)計語言中的指針類型來實現(xiàn)。索引存儲方法：除建立存儲

3、結(jié)點信息外，還建立附加的索引表來標識結(jié)點的XXX。散列存儲方法：就是根據(jù)結(jié)點的關(guān)鍵字直接計算出該結(jié)點的存儲XXX。數(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)的順序存儲結(jié)構(gòu)是一種隨機存取的存儲結(jié)構(gòu)，線性表的鏈式存儲結(jié)構(gòu)是一種順序存取的存儲結(jié)構(gòu)。線性表若采用鏈式存儲表示時所有結(jié)點之間的存儲單元XXX可連續(xù)可不連續(xù)。邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、所含結(jié)點個數(shù)都無關(guān)。 3、以下哪一個術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)？（ ）。 A.順序表 B.鏈表 C.散列表 D.隊列 4、

4、算法在發(fā)生非法操作時可以做出處理的特性稱為（ ）。 A．正確性 B．易讀性 C．健壯性 D．高效性 5、邏輯結(jié)構(gòu)是指數(shù)據(jù)元素的（ ）。 A．關(guān)聯(lián)方式 B．存儲方式 C．結(jié)構(gòu) D．數(shù)據(jù)項 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ù)的運算 7、從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ ）。 A.動態(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)和外部

5、結(jié)構(gòu) 8、以下有關(guān)數(shù)據(jù)的敘述中錯誤的是（ ）。 A．計算機能夠處理的數(shù)據(jù)包括整數(shù)、實數(shù)、字符、聲音、圖像等 B．數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它取決于數(shù)據(jù)的存儲方式 C．數(shù)據(jù)存儲結(jié)構(gòu)的實現(xiàn)依賴于計算機語言 D．數(shù)據(jù)的運算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的 9、數(shù)據(jù)的基本單位是（ ）。 A.數(shù)據(jù)結(jié)構(gòu) B.數(shù)據(jù)元素 C.數(shù)據(jù)項 D.文件 10、下列算法的時間復(fù)雜度是（ ） for(i=0;i

6、;j+ +) a[i][j]=i*j； A．O（m2） B．O（n2） C．O（mn） D．O（m+n） 11、算法分析的兩個主要方面是（ ）。 A．正確性和簡明性 B．數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 C．可讀性和可維護性 D．時間復(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)，是獨立于計算機的。 3、(

7、 )結(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;}”的時間復(fù)雜度為( )。 5、數(shù)據(jù)的存儲結(jié)構(gòu)（物理結(jié)構(gòu)）可以用（ ）、（ ）、（ ）及散列存儲等四種存儲方法表示。 三、 判斷題： 1、順序存儲方式優(yōu)點是存儲密度大，且插入和刪除運算效率高。 （ ） 2、順序存儲結(jié)構(gòu)屬于靜態(tài)存儲結(jié)構(gòu)，鏈式存儲結(jié)構(gòu)屬于動態(tài)存儲結(jié)構(gòu)。 （ ?。? 3、線性表的鏈接

8、存儲，表中元素的邏輯順序與物理順序一定相同。 （ ） 4、數(shù)據(jù)的機內(nèi)表示稱為數(shù)據(jù)的存儲結(jié)構(gòu)。 （ ） 5、在線性表的順序存儲結(jié)構(gòu)中，邏輯上相鄰的兩個元素在物理位置上并不一定相鄰。（ ） 6、數(shù)據(jù)元素是數(shù)據(jù)的最小單位。 （ ） 7、基于某種邏輯結(jié)構(gòu)之上的運算，其實現(xiàn)是惟一的。 （ ） 參考答案（緒論） 一、選擇題 1 2 3 4

9、 5 6 7 8 9 10 11 B D D C A D C B A C D 二、填空題 1、數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，它包括三方面的內(nèi)容，分別是數(shù)據(jù)的邏輯結(jié)構(gòu)、（存儲結(jié)構(gòu)）和（運算）。 2、數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的（　　　　　　?。o關(guān)，是獨立于計算機的。 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;}”的時間復(fù)雜度為(O(n2))。 5、數(shù)據(jù)的存儲結(jié)構(gòu)（物理結(jié)構(gòu)）可以用

10、（順序）、（鏈式）、（索引）及散列存儲等四種存儲方法表示。 三、判斷題 1、順序存儲方式優(yōu)點是存儲密度大，且插入和刪除運算效率高。 （） 2、順序存儲結(jié)構(gòu)屬于靜態(tài)存儲結(jié)構(gòu)，鏈式存儲結(jié)構(gòu)屬于動態(tài)存儲結(jié)構(gòu)。 （） 3、線性表的鏈接存儲，表中元素的邏輯順序與物理順序一定相同。 （ √） 4、數(shù)據(jù)的機內(nèi)表示稱為數(shù)據(jù)的存儲結(jié)構(gòu)。 （√） 5、在線性表的順序存儲結(jié)構(gòu)中，邏輯上相鄰的兩個元素在物理位置上并不一定相鄰。（）

11、 6、數(shù)據(jù)元素是數(shù)據(jù)的最小單位。 （） 7、基于某種邏輯結(jié)構(gòu)之上的運算，其實現(xiàn)是惟一的。 （） 2 線性表 一、 選擇題： 1、在表長為n的順序表上做插入運算，平均要移動的結(jié)點數(shù)為（ ）。 A．n B．n/2 C．n/3 D．n/4 2、在一個單鏈表中，若P所指結(jié)點不是最后結(jié)點，在P之后插入S所指結(jié)點，則執(zhí)行（ ） A．S->next=P->next;P

12、->next=S B．P->next=S->next;S->next=P； C．P->next=P;P->next=S； D．P->next=S;S->next=P； 3、在已知頭指針的單鏈表中，要在其尾部插入一新結(jié)點，其算法所需的時間復(fù)雜度為（ ） A．Ｏ（1） B．Ｏ（log2n） C．O（n） D．O（n2） 解析：單就插入運算而言，算法時間復(fù)雜度為Ｏ（1），但要將指針定位到鏈表末尾，指針移動的時間復(fù)雜度為O（n）； 4、對于只在表的首、尾兩端進行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為（ ）

13、 A．順序表 B．用頭指針表示的單循環(huán)鏈表 C．用尾指針表示的單循環(huán)鏈表 D．單鏈表 解析：尾指針是指向終端結(jié)點的指針，用它來表示單循環(huán)鏈表可以使得查找鏈表的開始結(jié)點和終端結(jié)點都很方便，設(shè)一帶頭結(jié)點的單循環(huán)鏈表，其尾指針為rear，則開始結(jié)點和終端結(jié)點的位置分別是rear->next->next 和 rear, 查找時間都是O(1)。 若用頭指針來表示該鏈表，則查找終端結(jié)點的時間為O(n)。 5、線性表是（ ） A．一個有限序列，可以為空 B．一個有限序列，不能為空 C．一個無限序列，可以

14、為空 D．一個無限序列，不能為空 6、在n個結(jié)點的雙鏈表的某個結(jié)點前插入一個結(jié)點的時間復(fù)雜度是（ ） A．O（n） B．O（1） C．O（log2n） D．O（n2） 7、線性表采用鏈式存儲時，結(jié)點的XXX（ ） A．必須是連續(xù)的 B．必須是不連續(xù)的 C．連續(xù)與否均可 D．必須有相等的間隔 8、在單鏈表中，增加頭結(jié)點的目的是（ ） A．使單鏈表至少有一結(jié)點 B．標志表中首結(jié)點位置 C．方便運算的實現(xiàn) D．說明單鏈表是線性表的

15、鏈式存儲實現(xiàn) 9、帶頭結(jié)點的單鏈表head為空的判定條件是（ ） A．head = NULL； B．head - > next = NULL； C．head - > next = head； D．head ! = NULL； 10、在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然有序的時間復(fù)雜度為（ ） A．Ｏ（1） B．Ｏ（n） C．Ｏ（n2） D．Ｏ（log2n） 11、下列有關(guān)線性表的敘述中，正確的是（ ） A．線性表中的元素之間是線性關(guān)系 B．

16、線性表中至少有一個元素 C．線性表中任何一個元素有且僅有一個直接前趨 D．線性表中任何一個元素有且僅有一個直接后繼 12、在單鏈表中，存儲每個結(jié)點需有兩個域，一個是數(shù)據(jù)域，另一個是指針域，它指向該結(jié)點的（ ） A．直接前趨 B．直接后繼 C．開始結(jié)點 D．終端結(jié)點 13、將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是（ ）。 A．n B.2n-1 C.2n D.n-1 14、鏈表不具有的特點是（ ）。 A．隨機訪問 　　　　

17、B．不必事先估計存儲空間 C．插入刪除時不需移動元素 D．所需的空間與線性表成正比 15、在一個單鏈表中，已知q所指結(jié)點是p所指結(jié)點的直接前趨，若在p，q之間插入s結(jié)點，則執(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、鏈表具有的特點是（ ）。 A．可隨機訪問任一元素 B．插入、刪除需要移動元素 C．不必事先估計存儲空間 D．存儲空間是靜態(tài)分配的

18、 17、一個順序表一旦說明，其中可用空間大?。? ） A．已固定 B．可以改變 C．不能固定 D．動態(tài)變化 18、若某線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素，則采用（ ）存儲方式最節(jié)省時間。 A． 順序表 B．單鏈表 C．雙向鏈表 D．單循環(huán)鏈表 19、兩個指針P和Q，分別指向單鏈表的兩個元素，P所指元素是Q所指元素的前驅(qū)的條件是（ ）。 A．P->next==Q B．Q->next==P C．P==Q D．P->next==Q->next 20、鏈表不具有的特點是（ ）。 A．可隨機訪問任一元素

19、 B．插入、刪除不需要移動元素 C．不必事先估計存儲空間 D．所需空間與線性表長度成正比 21、下面關(guān)于線性表的敘述中，錯誤的是（ ）。 A．線性表采用順序存儲，必須占用一片連續(xù)的存儲單元 B．線性表采用順序存儲，便于進行插入和刪除操作 C．線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元 D．線性表采用鏈接存儲，便于進行插入和刪除操作 22、在n個結(jié)點的順序表中，算法的時間復(fù)雜度是O(1)的操作是（ ）。 A．訪問第i個結(jié)點（1≤i≤n）和求第i個結(jié)點的直接前趨（2≤i≤n） B．在第i個結(jié)點后插入一個新結(jié)點（1≤i≤n） C．刪

20、除第i個結(jié)點（1≤i≤n） D．將n個結(jié)點從小到大排序 23、在一個單鏈表中，若刪除p指向結(jié)點的后繼結(jié)點，則執(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é)點*p，其時間復(fù)雜度為（　　　　　）。 2、在僅有尾指針R指示的單循環(huán)鏈表R中，在

21、表尾插入一個結(jié)點S的語句序列是（　　　 　　　　　　　　　　　　?。? 3、在帶頭結(jié)點的雙鏈表Ｌ中，指針Ｐ所指結(jié)點是開始結(jié)點的條件是（　　　　?。? 4、在具有n個結(jié)點的雙鏈表中做插入、刪除運算，平均時間復(fù)雜度為（　　　　?。?。 5、在一個長度為n的順序表中第i個元素（1 ≤ i ≤ n）之前插入一個元素時，需向后移動（　　　　　　?。﹤€元素。 6、在雙循環(huán)鏈表中，若要在指針p所指結(jié)點之前插入指針s所指的結(jié)點，則需執(zhí)行下列語句：s->prior=p->prior;p->prior->next=s;(

22、 )和p->prior=s;。 7、已知指針p指向雙向鏈表中的一個結(jié)點（非首結(jié)點、非尾結(jié)點），則將結(jié)點s插入在p結(jié)點的直接后繼位置的語句是（ ）s->prior=p；s->next->prior=s；p->next=s; 8、已知帶表頭結(jié)點的單鏈表L，指針p指向L鏈表中的一個結(jié)點（非首結(jié)點、非尾結(jié)點），則刪除結(jié)點p的直接后繼結(jié)點的語句是（ ）；刪除首結(jié)點的語句是（ ）。

23、 三、 判斷題 1、在有序的順序表和有序的鏈表上，均可以使用折半查找法來提高查找速度。（ ） 2、順序存儲的線性表可以隨機存取。 （ ） 3、線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。 （ ） 四、 程序設(shè)計題 數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)類型定義如下： 順序存儲： typedef struct { int *base; int length; int listsize; }sqlist; 鏈式存儲： typ

24、edef struct LinkList {int data; struct LinkList *next; }Node,*LinkList; 1、已知帶頭結(jié)點的單鏈表head中的結(jié)點是按整數(shù)值遞增排序的，寫一算法將值為x的結(jié)點插入到表head中，使head仍然有序。 2、用尾插法建立帶頭結(jié)點的單鏈表。 3、用頭插法建立帶頭結(jié)點的單鏈表。 4、對給定的單鏈表L，編寫一個刪除L中值為x的結(jié)點的直接前趨結(jié)點算法。 5、用順序存儲結(jié)構(gòu)實現(xiàn)線性表的就地逆置算法，即將（a1,a2, …ai,…an）逆置為（an,…,ai,…a2,a1）; 6、用

25、鏈式存儲結(jié)構(gòu)實現(xiàn)線性表的就地逆置算法，即將（a1,a2, …ai,…an）逆置為（an,…,ai,…a2,a1）; 7、使用順序存儲結(jié)構(gòu)分別實現(xiàn)A=A∪B和A=A∩B運算； 參考答案（線性表） 一、選擇題 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 B A B C A B C C B B A B B A B C B A A A B A A 二、填空題 1、在雙鏈表中要刪除已知結(jié)點*p，其時間復(fù)雜度為（O(1

26、)）。 2、在僅有尾指針R指示的單循環(huán)鏈表R中，在表尾插入一個結(jié)點S的語句序列是（P=R; while(P->next!=NULL) P=P->next; P->next=S; S->next=NULL;）。 3、在帶頭結(jié)點的雙鏈表Ｌ中，指針Ｐ所指結(jié)點是開始結(jié)點的條件是（P= =L）。 4、在具有n個結(jié)點的雙鏈表中做插入、刪除運算，平均時間復(fù)雜度為（O(1)）。 5、在一個長度為n的順序表中第i個元素（1 ≤ i ≤ n）之前插入一個元素時，需向后移動（n-i+1）個元素。 6、在雙循環(huán)鏈表中，若要在指針p所指結(jié)點之前插入指針s所指的結(jié)點，則需執(zhí)行下列語句：s->prior=p->p

27、rior;p->prior->next=s;( s->next=p; )和p->prior=s;。 7、已知指針p指向雙向鏈表中的一個結(jié)點（非首結(jié)點、非尾結(jié)點），則將結(jié)點s插入在p結(jié)點的直接后繼位置的語句是（p->next=s;）s->prior=p；s->next->prior=s；p->next=s; 8、已知帶表頭結(jié)點的單鏈表L，指針p指向L鏈表中的一個結(jié)點（非首結(jié)點、非尾結(jié)點），則刪除結(jié)點p的直接后繼結(jié)點的語句是（q=p->next; p->next=q->next; free(q);）；刪除首結(jié)點的語句是（q=L->next; L=L->next; free(q);）。 三

28、、判斷題 1、在有序的順序表和有序的鏈表上，均可以使用折半查找法來提高查找速度。（） 2、順序存儲的線性表可以隨機存取。 （√） 3、線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。 （√） 四、程序設(shè)計題 1、已知帶頭結(jié)點的單鏈表head中的結(jié)點是按整數(shù)值遞增排序的，寫一算法將值為x的結(jié)點插入到表head中，使head仍然有序。 P=head->next; While(p->next!=NULL&&p->datanext;//指針定位 p->next=x;

29、x->next=p->next; 2、用尾插入法建立帶頭結(jié)點的單鏈表。 請參考教材“數(shù)據(jù)結(jié)構(gòu)-清華大學(xué)嚴尉敏著評p29-p30”; 3、用頭插入法建立帶頭結(jié)點的單鏈表。 請參考教材“數(shù)據(jù)結(jié)構(gòu)-清華大學(xué)嚴尉敏著評p29-p30”; 4、對給定的單鏈表L，編寫一個刪除L中值為x的結(jié)點的直接前趨結(jié)點算法。 //算法思路：先判斷L中是否存在值為x的結(jié)點，若不存在，返回錯誤（-1）；若存在，用一指針p定位到值為x的第一結(jié)點,用另一個指針q定位到值為x的第一結(jié)點的前驅(qū)結(jié)點，然后實施刪除操作；重點語句為： p=L->next;//p指向第一個結(jié)點 whili(p->data!

30、=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、用順序存儲結(jié)構(gòu)實現(xiàn)線性表的就地逆置算法，即將（a1,a2, …ai,…an）逆置為（an,…,ai,…a2,a1）; 重點語句： for(i=0;i

31、 { sqlist.base[i]sqlist.base[sqlist.length-i];//第i個元素和第length-i元素交換存儲 } 6、用鏈式存儲結(jié)構(gòu)實現(xiàn)線性表的就地逆置算法(不帶頭結(jié)點的單鏈表)，即將（a1,a2, …ai,…an）逆置為（an,…,ai,…a2,a1）; 參考答案： Node *fun(Node *h)//h指向單鏈表的第一個結(jié)點 { Node *p,*q,*r; P=h; If(p==NULL) Return NULL; q=pnext;//q

32、指針指向第二個結(jié)點 pnext=NULL; while(q) { r=qnext；//第一次循環(huán)時，r指向第三個結(jié)點 qnext=p;//第二個結(jié)點的NEXT指向第一個結(jié)點 p=q;//p總是指向逆置后的第一個結(jié)點 q=r;//q總是指向剩余單鏈表的第一個結(jié)點，為將其作為逆置單鏈表的第一個結(jié)點作準備 } return p; } 兩外，解決本體還有另外一種思路，將結(jié)點數(shù)據(jù)域拷貝到一個一維數(shù)組中，然后反過來填充單鏈表結(jié)點的數(shù)據(jù)域。 7、使用順

33、序存儲結(jié)構(gòu)分別實現(xiàn)A=A∪B和A=A∩B運算； 請參考清華大學(xué)出版社出版，嚴尉敏編著《數(shù)據(jù)結(jié)構(gòu)C語言版》P20例2-1； 3 棧和隊列 一、 選擇題： 1、循環(huán)隊列是空隊列的條件是（ ） A．Q . rear = = Q . front B．（Q . rear + 1）%maxsize = = Q .front C．Q . rear = = 0 D．Q. front = = 0 2、鏈棧與順序棧相比，比較明顯的優(yōu)點是（ ） A．通常不會出現(xiàn)棧滿的情況 B．通常不會出現(xiàn)?？盏那闆r C．插入操作更加

34、方便 D．刪除操作更加方便 [分析]不管是鏈棧還是順序棧，其插入、刪除操作都是在棧頂進行的，都比較方便，所以不可能選C)，D)。對鏈棧來講，當棧中沒有元素而又要執(zhí)行出棧操作時，就會出現(xiàn)?？宅F(xiàn)象，故B)也是不正確的。只要內(nèi)存足夠大，鏈棧上就不會出現(xiàn)棧滿現(xiàn)象。而對順序棧來講，由于其大小是事先確定好的，因此可能會出現(xiàn)棧滿現(xiàn)象。所以A)是正確的。 3、若一個棧的輸入序列是１，２，３，……，n，輸出序列的第一個元素是ｎ，則第ｉ個輸出元素是（ ） A．n - i B．n – i + 1 C．i D．不確定 4、棧與一般線性表的區(qū)別

35、主要在（ ） A．元素個數(shù) B．元素類型 C．邏輯結(jié)構(gòu) D．插入、刪除元素的位置 5、一個鏈棧的棧頂指針是top，則執(zhí)行出棧操作時（棧非空），用x保存被刪除結(jié)點，則執(zhí)行（ ） A．x = top; top = top next； B．x = topdata； C．top = top next;x = top data； D．x = top data;top = top next； [分析]棧頂元素出棧后，應(yīng)該從棧底位置即第一個結(jié)點開始重新定位，執(zhí)行語句是：q=base ; while(qnex

36、t!=top) q=qnext; free(top); top=q; 6、對于一個棧，給定輸入序列為1，2，3，則下列不可能為輸出序列的是（ ） A．1，2，3 B．3，2，1 C．3，1，2 D．2，1，3 [分析] 每個元素進棧后立即出棧，結(jié)果是答案A；三個元素全部進棧后再出棧，得到答案B；1和2進棧后出棧，然后3入棧后出棧，得到答案D；而C答案不可能的原因是：3出棧后，說明1、2還在棧中，1出棧后2還在棧中，說明2的入棧次序在1之前。 7、在鏈接隊列執(zhí)行入隊操作（　 ） A．需判別隊是否空 B

37、．需判別隊是否滿 C．限制在鏈表頭p進行 D．限制在鏈表尾p進行 8、以下不屬于棧的基本運算是（ ）。 A．刪除棧頂元素 B．刪除棧底元素 C．判斷棧是否為空 D．將棧置為空棧 9、一個棧的入棧序列是a,b,c,d,e，則棧的不可能的輸出序列是（ ）。 A．e,d,c,b,a　 B．d,e,c,b,a C．d,c,e,a,b 　　 D．a(chǎn),b,c,d,e 10、設(shè)計一個判別表達式中左、右括號是否配對出現(xiàn)的算法，采用（

38、 ）數(shù)據(jù)結(jié)構(gòu)最佳。 A．線性表的順序存儲結(jié)構(gòu)　 B．棧 C．隊列　　　　 D．線性表的鏈式存儲結(jié)構(gòu) 11、循環(huán)隊列的特點之一是不會產(chǎn)生（ ）。 A．上溢出 B．下溢出 C．隊滿 D．假溢出 12、設(shè)數(shù)組Data[n]作為循環(huán)隊列Q的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行入隊操作的語句為（ ）。 A．rear=(rear+1)%(n+1) B．front=(front+1)% n C．rear=(rear+1)% n

39、 D．front=(front+1)%(n+1) 13、棧是限定在（ ）處進行插入或刪除操作的線性表。 A．端點 B．棧底 C．棧頂 D．中間 14、容量是10的循環(huán)隊列的隊頭位置qfront為2，隊列中的數(shù)據(jù)元素個數(shù)為5，則隊的第一個數(shù)據(jù)元素的位置是（ ） A．2 B．7 C．1 D．0 [分析] (front-rear+10)%10=5,并且front和rear的取值范圍均是0—9，所以只有（7-2+10）%10=5。 15、循環(huán)隊列的出隊操作是（ ） A． qfront=(qfront+1)%max

40、size; B．qfront=qfront+1; C．qrear=(qrear+1)%maxsize; D．qrear=qrear+1; 16、當循環(huán)隊列q是滿隊列時，存放隊列元素的數(shù)組data有n個元素，則data中存放（ ）個數(shù)據(jù)元素。 A．n B. n-1 C. n-2 D.0 [分析] 容量為maxsize的循環(huán)隊列最多只能存放maxsize-1個數(shù)據(jù)元素，當隊列滿時，隊尾指針再往前走一步就追上隊頭指針，即(rear+1)% maxsize=front； 17、以下哪一個不是隊列的基本運算（ ）。 A．

41、從隊尾插入一個新元素 B．從隊列中刪除第i個元素 C．判斷一個隊列是否為空 D．讀取隊頭元素的值 18、在一個鏈隊列中，若f , r分別為隊首、隊尾指針，則插入s所指結(jié)點的操作為（ ）。 A．fnext=s;f=s B．rnext=s;r=s; C．snext=r;r=s; D．snext=f;f=s 19、循環(huán)隊列的入隊操作應(yīng)為（ ）。 A．qrear=qrear+1;qdata[qrear]=x; B．qdata[qrear++]=x; C．qrear=(qrear+1)%m

42、axsize; qdata[qrear]=x; D．qdata[qrear]=x;q->rear=(qrear+1)%maxsize; 20、棧和隊列都是（ ）。 A．限制存取點的線性結(jié)構(gòu) B．限制存取點的非線性結(jié)構(gòu) C．順序存儲的線性結(jié)構(gòu) D．鏈式存儲的線性結(jié)構(gòu) 21、實現(xiàn)遞歸調(diào)用屬于（ ）的應(yīng)用。 A．隊列 B．棧 C． 數(shù)組 D．樹 二、 填空題： 1、循環(huán)隊列用數(shù)組data[m]存放其元素值，已知其頭、尾指針分別是front和rear，則當前隊列中元素的個數(shù)是（　　　　　　　　　　　　

43、）。 2、棧頂?shù)奈恢檬请S著（　　　　　　?。┎僮鞫兓摹? 3、假設(shè)以S和X分別表示進棧和退棧操作，則對輸入序列a，b，c，d，e進行一系列棧操作SSXSXSSXXX之后，得到的輸出序列為（　　　　　　　　）。 4、隊列的隊尾位置隨著（　　　　　）而變化。 5、在（　　　　 　　?。┑那闆r下，鏈隊列的出隊操作需要修改尾指針。 6、從棧頂指針為top的鏈棧中刪除一個結(jié)點，并將被刪除的結(jié)點的值保存在x中，其操作步驟為（ ）；top=top->next;。 7、用數(shù)組A[m]來存放循環(huán)隊列q的元素，且它的頭、尾指針分別為front和rear，隊列滿足條件(q.

44、rear+1)%m==q.front,則隊列中當前的元素個數(shù)為（ ）。 8、順序棧s存儲在數(shù)組s->data[max]中，對s進行出棧操作，執(zhí)行的語句序列是（ ）。 9、以下運算實現(xiàn)在循環(huán)隊列中的初始化操作 void initqueue(seqqueue *q){q->front=0;( );} 三、 判斷題： 1、循環(huán)隊列中無上溢現(xiàn)象。 （ ） 2、循環(huán)隊列只有下溢，沒有

45、上溢。 （ ） 3、對順序棧而言，在棧滿狀態(tài)，如果此時再作進棧運算，則會發(fā)生“下溢”。 （ ） 4、順序隊列和循環(huán)隊列的隊滿和隊空的條件是一樣的。 （ ） 5、為解決隊列“假滿”問題，可以采用循環(huán)數(shù)組實現(xiàn)隊列存儲。　 （ ） 6、隊列是后進先出表。 （ ） 7、棧是后進先出表。

46、 （ ） 四、 應(yīng)用題： 1、 設(shè)有一個棧，元素進棧的次序為A，B，C，D，E，寫出下列出棧序列的操作序列。（1）CBADE（2）ACBED，其中I為進棧操作，O為出棧操作。 2、如果編號為1、2、3的三輛列車進入一個棧式結(jié)構(gòu)的站臺，那么可能得到的三輛列車出站序列有哪些？不可能出現(xiàn)的序列是什么？ 五、 程序設(shè)計題： 1、寫出循環(huán)隊列入隊操作的函數(shù)。 參考答案（棧和隊列） 一、選擇題 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

47、16 17 18 19 20 21 A A B D B C D B C B D C C B A B B B C A B 二、填空題 1、循環(huán)隊列用數(shù)組data[m]存放其元素值，已知其頭、尾指針分別是front和rear，則當前隊列中元素的個數(shù)是（(rear-front+maxsize）%maxsize）。 2、棧頂?shù)奈恢檬请S著（入棧和出棧）操作而變化的。 3、假設(shè)以S和X分別表示進棧和退棧操作，則對輸入序列a，b，c，d，e進行一系列棧操作SSXSXSSXXX之后，得到的輸出序列為（bceda）。 4、隊列的隊尾位置隨著（入隊

48、列操作變化）而變化。 5、在（鏈隊列為空）的情況下，鏈隊列的出隊操作需要修改尾指針。 分析：Q.rear=h; 6、從棧頂指針為top的鏈棧中刪除一個結(jié)點，并將被刪除的結(jié)點的值保存在x中，其操作步驟為（x=top->data）。 7、用數(shù)組A[m]來存放循環(huán)隊列q的元素，且它的頭、尾指針分別為front和rear，隊列滿足條件(q.rear+1)%m==q.front,則隊列中當前的元素個數(shù)為（0）。 8、順序棧s存儲在數(shù)組s->data[max]中，對s進行出棧操作，執(zhí)行的語句序列是（stop--）。 9、以下運算實現(xiàn)在循環(huán)隊列中的初始化操作 void initqueue

49、(seqqueue *q){q->front=0;( qbase=(qelemtype *)malloc(maxsize*sizeof(qelemtype)); qrear=0;);} 三、判斷題 1、循環(huán)隊列中無上溢現(xiàn)象。 （） 2、循環(huán)隊列只有下溢，沒有上溢。 （） 3、對順序棧而言，在棧滿狀態(tài)，如果此時再作進棧運算，則會發(fā)生“下溢”。 （） 4、順序隊列和循環(huán)隊列的隊滿和隊空的條件是一樣的。

50、 （） 5、為解決隊列“假滿”問題，可以采用循環(huán)隊列實現(xiàn)隊列存儲。　 （√） 6、隊列是后進先出的線性表。 （） 7、棧是后進先出表。 （√） 四、應(yīng)用題 1、設(shè)有一個棧，元素進棧的次序為A，B，C，D，E，寫出下列出棧序列的操作序列。（1）CBADE（2）ACBED，其中I為進棧操作，O為出棧操作。 參考答案：（1）IIIOOOIOIO (2)IO

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

52、．S1=“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

53、os-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ù)元素是一個字符 C．可以鏈接存儲 D. 數(shù)據(jù)元素可以是多個字符 答：B 6．串是( )。 A．少于一個字母的序列 B. 任意個字母的序列 C．不少于一個字符的序列 D. 有限個字符的序列 答：D 7． 串的長度是( )。 A．

54、串中不同字母的個數(shù) B. 串中不同字符的個數(shù) C．串中所含的字符的個數(shù) D. 串中所含字符的個數(shù)，且大于0 答：C 8． 設(shè)有S1=‘ABCDEFG’，S2=‘PQRST’，函數(shù)con(x，y)返回x和y串的連接串，subs(I，j)返回串S的從序號I的字符開始的j個字符組成的子串，len(s)返回串s的長度，則con(subs(S1，2，len(S2))，subs(S1，len(S2)，2))的結(jié)果是( )。 A．BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF 答：D 9． 若某串的長度小于一個常數(shù)，則采用( )存儲方式最

55、為節(jié)省空間。 A．鏈式 B. 堆結(jié)構(gòu) C. 順序表 答：C 二、填空題： 1．串是每個結(jié)點僅由一個字符組成的____________________。 答：線性表 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

56、_________________。 答：<0 5．在串順序存儲結(jié)構(gòu)中，實現(xiàn)串操作的原操作為____________________。 答：字符序列的復(fù)制 6．串與線性表在邏輯結(jié)構(gòu)上極為相似，區(qū)別僅在于____________________ ；在基本操作上差別很大，線性表的基本操作大多數(shù)以____________________ 作為操作對象，而串的基本操作通常以 作為操作對象。 答：串的數(shù)據(jù)對象約束為字符集 “單個元素” “串的整體” 7．兩個串相等的充分必要條件是____________________ 且____________________ 。

57、答：兩個串的串長相等 各個對應(yīng)位置的字符都相等 8．空串是指____________________，空格串是指_______________________。 答：不含任何字符的串 僅含空格字符的串 三、判斷題 1．空串是由空白字符組成的串（ FALSE ） 2．串的定長順序結(jié)構(gòu)是用一組XXX連續(xù)的存儲單元存儲串值的字符序列，按照預(yù)定義的大小，為每個定義的串變量分配一個固定長度的存儲區(qū)。(TRUE ) 3．串的堆分配存儲表示是用一組XXX連續(xù)的存儲單元存儲串值的字符序列，但它們的存儲空間是在程序執(zhí)行過程中動態(tài)分配得到的。（TRUE ） 4．串中S

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

59、作（除串清除ClearString和串銷毀DestroyString外）均可在最小操作子集上實現(xiàn)。(TRUE) (題源：根據(jù)教材p72自編) 四、簡答題 1．已知串s=‘(xyz)*’，t=‘(x+z)*y’，試利用串的基本運算將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),‘

60、+’,‘y’),replace(substring(sub,t,6,2),‘*y’,‘*’)) 2．串是字符組成的，長度為1的串和字符是否概念相同？為什么？ (題源：朱戰(zhàn)立，C版題解，p86，4.2.1(典型題解)_2) 答：由于字符的長度固定為1，長度概念可以隱含，所以存儲時只需存儲該字符即可；而長度為1的串其長度概念不能隱含，必須顯示地表示出來，所以存儲時要同時存儲該字符和值為1的長度值。 五、算法設(shè)計題 1．設(shè)串s和串t采用順序存儲結(jié)構(gòu)，編寫函數(shù)實現(xiàn)串s和串t的比較操作，要求比較結(jié)果包括大于、小于和等于三種情況。 (題源：朱戰(zhàn)立，C版題解，p87，4.2.1

61、(典型題解)_7) 提示 算法思想：循環(huán)逐個比較兩個串，一旦兩個串的某個字符比較不相等則說明兩個串不相等，此時進一步比較這兩個不相等字符的大于和小于情況來決定串s和串t比較的大于和小于情況；當串s的n個字符和串t的m個字符比較全部相等時，還需進一步判斷此時串s或串t是否還有剩余字符沒有比較，來決定串s和串t比較的大于和小于情況；若所有字符比較均相等，并且串s的字符個數(shù)n和串t的字符個數(shù)m也相等時，說明串s等于串t。當串s大于串t時函數(shù)返回1，當串s小于串t時函數(shù)返回-1，當串s等于串t時函數(shù)返回 0。 解：int StrCompare(SStrType s,SStrType t)

62、{ int n=s.length, m=t.length, i,j,tag; i=0; j=0; while(it.str[j]) { tag=1; /*說明s>t,退出比較*/ return tag; } else { tag=-1; /*說明s

63、 else if(n>m) tag=1; /*若串t只和串s的前m個字符相等則s>t*/ else if(n

64、，此時利用一個統(tǒng)計計數(shù)器進行累加1運算，在此之后若連續(xù)讀到的是非空格符，則這些字符屬于剛統(tǒng)計到的那個單詞，因此不應(yīng)將計數(shù)器累加1，下一次計數(shù)應(yīng)該是在讀到一個或幾個空格后再遇到非空格字符之時進行。因此，統(tǒng)計一個單詞時不僅要滿足當前所檢查的這個字符是非空格，而且要滿足所檢查的前一個字符是空格。 解：int count(r) char r[80]; { char prec,nowc; int num,j; prec=‘ ’; num=0; for(j=0;j<80;j++) { nowc=r[j]; if((nowc!=‘ ’)&&(prec==‘ ’))

65、 num++; prec=nowc; } return num; }/*count*/ 3．編寫算法，求串s所含不同字符的總數(shù)和每種字符的個數(shù)。 (題源：嚴蔚敏，C版習題集，p29，4.18) 解：typedef struct{ char ch; int num; }mytype; void StrAnalyze(Stringtype S) //統(tǒng)計串S中字符的種類和個數(shù) { mytype T[MAXSIZE]; //用結(jié)構(gòu)數(shù)組T存儲統(tǒng)計結(jié)果 for(i=1;i<=S[0];i++) { c=S;j=0; while(

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