數(shù)據(jù)結(jié)構(gòu)習(xí)題庫大全(c語言版)

第一章緒論一、基本內(nèi)容數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)類型等概念術(shù)語的確定含義、抽象數(shù)據(jù)類型的定義、表示和實現(xiàn)方法、描述算法的類c語言、算法設(shè)計的基本要求。二、學(xué)習(xí)要點1、熟悉各名詞、術(shù)語的含義，掌握基本概念，特別是數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)之間的關(guān)系。分清哪些是邏輯結(jié)構(gòu)的性質(zhì)，哪些是存儲結(jié)構(gòu)的性質(zhì)。2、了解抽象數(shù)據(jù)類型的定義、表示和實現(xiàn)方法。3、熟悉類C語言的書寫規(guī)范，特別要注意值調(diào)用和引用調(diào)用的區(qū)別，輸入、輸出的方式以及錯誤處理方式。4,理解算法五個要素的確切含義。1.1基礎(chǔ)知識一、填空題1、數(shù)據(jù)的邏輯結(jié)構(gòu)包括_（D_，②，③和⑷四種類型,樹型結(jié)構(gòu)和圖型結(jié)構(gòu)合稱為⑤，數(shù)據(jù)的存儲結(jié)構(gòu)即物理結(jié)構(gòu)包括：⑥， ⑦等兩種基本類型。2、在線性結(jié)構(gòu)中元素之間存在一①一關(guān)系，樹形結(jié)構(gòu)中元素間存在②關(guān)系,圖形結(jié)構(gòu)中元素間存在③關(guān)系。3、一個數(shù)據(jù)結(jié)構(gòu)用二元組表示時，它包括Q集合D和D上的集合S。4、一個算法應(yīng)具有①，②，③，④和⑤這五個特性。5、在圖形結(jié)構(gòu)中，每個節(jié)點的前驅(qū)節(jié)點和后繼節(jié)點可以有Q個。6、一個抽象數(shù)據(jù)類型用三元組（D,S,P）表示時，D是①，S是②，P是③。7、數(shù)據(jù)元素在計算機中的映象是①。8、算法的設(shè)計取決于①，算法的實現(xiàn)取決于②。二、選擇題1、數(shù)據(jù)元素是數(shù)據(jù)的單位。（A）基本 （B）最小2、使用指針表示數(shù)據(jù)元素之間邏輯關(guān)系的存儲結(jié)構(gòu)是（A）順序結(jié)構(gòu) （B）鏈?zhǔn)浇Y(jié)構(gòu) （C）樹狀結(jié)構(gòu) （D）圖狀結(jié)構(gòu)3、以下一術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)。（A）線索二又樹 （B）雙向鏈表 （C）棧（D）哈希表4、以下一術(shù)語與數(shù)據(jù)的邏輯結(jié)構(gòu)無關(guān)。（A）線性結(jié)構(gòu) （B）鏈?zhǔn)浇Y(jié)構(gòu) （C）樹型結(jié)構(gòu) （D）網(wǎng)狀結(jié)構(gòu)5、指出下列敘述一不屬于算法的特性。（A）有窮性（B）復(fù)雜性 （C）可行性 （D）確定性6、以下數(shù)據(jù)結(jié)構(gòu)中是線性結(jié)構(gòu)。（A）隊列（B）有向圖（C）樹 （D）哈夫曼樹解答：一、填空題1、①線性②集合③樹④圖或網(wǎng)⑤非線性結(jié)構(gòu)⑥順序存儲⑦鏈?zhǔn)酱鎯?、①1：1②1：n③m：n3、①數(shù)據(jù)元素②關(guān)系4、①有窮性②確定性③可行性④輸入⑤輸出5、①多個6、①數(shù)據(jù)對象②D上的關(guān)系集合③對D的基本操作集合7、①元素或結(jié)點8、①數(shù)據(jù)（邏輯）結(jié)構(gòu)②采用的存儲結(jié)構(gòu)二、選擇題1、A2、B3、C4、B5、B6、A1.2應(yīng)用知識1、什么是算法？算法的特性是什么？算法設(shè)計的要求是什么？解答：（略）2、設(shè)仃數(shù)據(jù)結(jié)構(gòu)USER_STRU表示如下：USER.STRU=（D,S）D={al?a2,…，a9)

S={<al,a3>,<al,a8>,<a2,a3>,<a2,a4>,<a2,a5>,<a3,a9>,<a5,a6>,<a8,a9>,<a9,a7>,<a4,a7>,<a4,a6>}畫出這個數(shù)據(jù)結(jié)構(gòu)的圖示，并確定其類型。解答：該結(jié)構(gòu)的圖示如卜,該結(jié)構(gòu)為圖形結(jié)構(gòu)。3、設(shè)有數(shù)據(jù)結(jié)構(gòu)USER_STRU表示如下:USER_STRU=(D,S)D={al,a2,...?a9}S={<al,a2>,<al?a3>,<a3,a4>,<a3,a6>,<a6,a8>,<a4,a5>,<a6,a7>,<a8,a9>}畫出這個數(shù)據(jù)結(jié)構(gòu)的圖示，并確定其類型。解答：該結(jié)構(gòu)的圖示如下，該結(jié)構(gòu)為樹形結(jié)構(gòu)。4、影響高級語言程序運行消耗時間的因素有哪些？解答：主要有以下因素：(1)算法選用的策略；(2)問題的規(guī)模；(3)書寫程序的語言；(4)編譯程序產(chǎn)生的機器代碼質(zhì)量；(5)機器執(zhí)行指令的速度。5、選擇解決某種問題的最佳數(shù)據(jù)結(jié)構(gòu)的標(biāo)準(zhǔn)是什么？解答：一般有兩條標(biāo)準(zhǔn)：(1)所需的存儲空間量；(2)算法所需要的時間；而算法所需要的時間又包括以下幾點：(D程序運行時所需要的數(shù)據(jù)總量；(2)源程序進(jìn)行編譯所需要的時間；(3)計算機執(zhí)行每條指令所需要的時間；(4)程序中的指令重復(fù)執(zhí)行的次數(shù)，而本條正是討論算法中的重點內(nèi)容。6、設(shè)三個函數(shù)f,g,h分別為￡缶)=100/+/+1000,g(n)=25n3+5000n2,h(n)=n's+5000nlgn請判斷下列關(guān)系是否成立：f(n)=O(g(n))g(n)=O(f(n))h(n)=O(n~h(n)=O(nlgn)解答：(1)成立；(2)成立；(3)成立：(4)不成立。7、設(shè)n為正整數(shù)，利用大"0"記號，將下列程序段的執(zhí)行時間表示為n的函數(shù)。i=l;k=0;while(i<n){k=k+10*i;i++;i=0;k=0;do{k=k+10*i;i++;)while(i<n);i=l;j=0;while(i+j<=n)(if(i>j)j++；elsei++;)(4)x=n：//n>lwhile(x>=(y+l)*(y+D)y++;(5)x=91;y=100;while(y>0)if(x>100){x=x-10;y—;}elsex++;解答：(1)為T(n)=0(n)；(2)為T(n)=0(n)；(3)為T(n)=0(n)(4)由x=n且x的值在程序中不變，又while的循環(huán)條件(x>=(y+l)*(y+l))可知：當(dāng)(y+l)*(y+l)剛超過n的值時退出循環(huán)。由(y+l)*(y+l)<n得：y<n"0.5-1所以，該程序段的執(zhí)行時間為：向下取整(n"0.5-1)(5)為T(n)=0(l)8、算法的時間復(fù)雜度僅與問題的規(guī)模相關(guān)嗎？解答：算法的時間復(fù)雜度不僅與問題的規(guī)模相關(guān)，還與輸入實例中的初始狀態(tài)有關(guān)。但在最壞的情況下，其時間復(fù)雜度就是只與求解問題的規(guī)模相關(guān)的。我們在討論時間復(fù)雜度時，一

般就是以最壞情況下的時間復(fù)雜度為準(zhǔn)的。9、按增長率由小至大的順序排列下列各函數(shù)：2100,(3/2)n.(2/3)n,nn,n0.5,n!12n,Ign,nlgn,n(3/2)解答：常見的時間復(fù)雜度按數(shù)量級遞增排列，依次為：常數(shù)階0(1)、對數(shù)階0(log2n)、線性階0(n)、線性對數(shù)階0(nlog2n)、平方階0(n2)、立方階0(n3)、k次方階O(nk)、指數(shù)階0(2n)o先將題中的函數(shù)分成如下幾類：常數(shù)階：2100對數(shù)階：IgnK次方階：n0.5、n(3/2)指數(shù)階(按指數(shù)由小到大排)：nlgn、(3/2)n,2n、n!、nn注意：(2/3)、n由于底數(shù)小于1,所以是一個遞減函數(shù)，其數(shù)量級應(yīng)小于常數(shù)階。根據(jù)以上分析按增長率由小至大的順序可排列如下：(2/3)n<2100<Ign<n0.5<n(3/2)<nlgn<(3/2)n<2n<n!<nn10、設(shè)有兩個算法在同一機器上運行，其執(zhí)行時間分別為100n2和2n,要使前者快于后者，n至少要多大？解答：要使前者快于后者，即前者的時間消耗低于后者，即：100n2<2n求解上式，可得n=15求解上式，可得n=15第二章線性表一、基本內(nèi)容線性表的邏輯結(jié)構(gòu)定義、抽象數(shù)據(jù)類型定義和各種存儲結(jié)構(gòu)的描述方法；在線性表的兩類存儲結(jié)構(gòu)(順序的和鏈?zhǔn)降?上實現(xiàn)基本操作、稀疏多項式的抽象數(shù)據(jù)類型定義、表示和加法的實現(xiàn)。二、學(xué)習(xí)要點1、了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系，在計算機中表示這種關(guān)系的兩類不同的存儲結(jié)構(gòu)是順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。用前者表示的線性表簡稱為順序表，用后者表示的線性表簡稱為鏈表。2、熟練掌握這兩類存儲結(jié)構(gòu)的描述方法，如一維數(shù)組中一個區(qū)域［i…j］的上、下界和長度之間的變換公式(L=j-i+l,i=j-L+l,j=i+L-l),鏈表中指針p和結(jié)點*p的對應(yīng)關(guān)系(結(jié)點*(p->next)是結(jié)點*p的后繼等)，鏈表中的頭結(jié)點、頭指針和首元結(jié)點的區(qū)別及循環(huán)鏈表、雙向鏈表的特點等。鏈表是本章的用:點和難點。扎實的指針操作和內(nèi)存動態(tài)分配的編程技術(shù)是學(xué)好本章的基本要求。3、熟練掌握線性表在順序存儲結(jié)構(gòu)上實現(xiàn)基本操作：查找、插入和刪除的算法。4、熟練掌握在各種鏈表結(jié)構(gòu)中實現(xiàn)線性表操作的基本方法，能在實際應(yīng)用中選用適當(dāng)?shù)逆湵斫Y(jié)構(gòu)。了解靜態(tài)鏈表，能夠加深對鏈表本質(zhì)的理解。2.1基礎(chǔ)知識一、填空題1、對于雙向循環(huán)鏈表，在兩個結(jié)點間插入一個新結(jié)點時需修改的指針共有①個,單鏈表為②個。2、當(dāng)向一個順序表插入一個元素時，被插入元素之后的所有元素均需向 ①移動一個位置，元素的移動順序是從②向③依次移動。3.要從一個順序表刪除一個元素時，被刪除元素之后的所有元素均需向①移動一個位置，元素的移動順序是從②向③依次移動。4、在一個循環(huán)單鏈表中，表尾結(jié)點指針域與表頭指針值①。5、在線性表的順序存儲中，元素之間的邏輯關(guān)系是通過①表示的:在線性表的鏈接存儲中，元素之間的邏輯關(guān)系是通過表示的。6、在雙向鏈表中，每個結(jié)點含有兩個指針域，-個指向 ①結(jié)點,另一個指向②結(jié)點。7、在?個單鏈表中刪除p所指結(jié)點時，應(yīng)執(zhí)行下列操作：q=p->next;p->data=p->next->data;TOC\o"1-5"\h\zp->next=① ;free(q);8、若要在一個不帶表頭結(jié)點的單鏈表的首結(jié)點*p之前插入一個*s結(jié)點時，可執(zhí)行下列操作：s->next=① ；p->next=S；t=p->data；p->data=② ：s->data=③ ；9、根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每個結(jié)點所含指針的個數(shù)，鏈表可分為①和②；而根據(jù)指針的聯(lián)接方式，鏈表又可分為③和④ °10、單鏈表表示法的基本思想是利用_蟲_表示結(jié)點間的邏輯關(guān)系。11,當(dāng)對一個線性表經(jīng)常進(jìn)行的是存取操作，而很少進(jìn)行插入和刪除操作時，則采用①存儲結(jié)構(gòu)為宜，相反，當(dāng)經(jīng)常進(jìn)行的是插入和刪除操作時，則采用②存儲結(jié)構(gòu)為宜。12、在單鏈表中設(shè)置頭結(jié)點的作用是①。13、順序表中邏輯上相鄰的元素，物理位置①緊鄰,單鏈表中邏輯上相鄰的元素，物理位置②緊鄰。14、一個采用了順序存儲結(jié)構(gòu)的線性表，其長度為30,若在第7個元素前插入一個元素，需要移動①個元素,若接著又將第12個元素刪除，那么需要移動②個元素。二、選擇題1、在一個長度為n的順序表中刪除第i個元素(iWiMn)時，需向前移動個元素。(A)n-i (B)n-i+1 (C)n-i-1 (D)i2、用鏈表表示線性結(jié)構(gòu)的優(yōu)點在于o(A)便于隨機存取 (B)便于插入和刪除(C)節(jié)省空間 (D)元素的物理順序和邏輯順序一致3.在雙向循環(huán)鏈表中，在p所指的結(jié)點之后插入s指針?biāo)傅慕Y(jié)點，其操作是。(A)p->next=s；s->prior=p；(p->next)->prior=s； s->next=p->next；(B)s->prior=p；s->next=p->next；p->next=s；p->next->prior=s；(C)p->next=s；p->next->prior=s；s->prior=p；s->next=p->next；(D)s->prior=p；s->next=p->next；p->next->prior=s；p->next=s；4、設(shè)單鏈表中指針p指向結(jié)點m,若要刪除m之后的結(jié)點(假定存在)，則需修改指針的操作為.(A)p->next=p->next->next； (B)p=p->next；(C)p=p->next->next； (D)p->next=p；5、線性表采用鏈?zhǔn)酱鎯r，其存儲單元的地址.(A)必須是連續(xù)的：(B)一定是不連續(xù)的：(C)部分地址必須是連續(xù)的；(D)連續(xù)與否均可以；6、在一個單鏈表中，已知*q結(jié)點是*p結(jié)點的前趨結(jié)點，若在*q和*p之間插入*s結(jié)點，則須執(zhí)行.s->next=p->next；p->next=s；q->next=s；s->next=p；p->next=s->next； s->next=p；p->next=s：s->next=q；7、線性表是o一個有限序列，可以為空；一個有限序列，不可以為空；一個無限序列，可以為空；一個無限序列，不可以為空；8、在一個長度為n的順序表中向第i個元素(0<i<n+l)之前插入一個新元素時，需向后移動個元素。

(A)n-i(B)n-i+1(C)n-i-1(D)i(A)n-i(B)n-i+1(C)n-i-1(D)i9、下面關(guān)于線性表的敘述中，錯誤的是.(A)若采用順序結(jié)構(gòu)，需占用連續(xù)存儲空間(B)若采用順序結(jié)構(gòu)，便于進(jìn)行插入和刪除(C)若采用鏈?zhǔn)浇Y(jié)構(gòu)，不必占用連續(xù)存儲空間(D)若采用鏈?zhǔn)浇Y(jié)構(gòu)，便于進(jìn)行插入和刪除10、線性表是具有n個的有限序列。(A)信息 (B)字符 (C)數(shù)據(jù)元素 (D)數(shù)據(jù)項11＞下面關(guān)于線性表的敘述中，正確的是O(A)順序結(jié)構(gòu)的優(yōu)點在于存儲密度大，便于插入和刪除(B)鏈表的結(jié)點都恰好包含一個指針(C)順序結(jié)構(gòu)優(yōu)于鏈?zhǔn)浇Y(jié)構(gòu)(D)鏈?zhǔn)浇Y(jié)構(gòu)屬于動態(tài)結(jié)構(gòu)三、判斷題1、線性表采用鏈表存儲時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。2、在具有頭結(jié)點的單鏈表結(jié)構(gòu)中，頭指針指向鏈表中的第一個數(shù)據(jù)結(jié)點。3、腴序表可以隨機存取。4、單鏈表是一種隨機存取結(jié)構(gòu)。5、順序表中插入和刪除元素時，元素移動個數(shù)與插入或刪除位置有關(guān)。解答：一、填空題1、①4②22,①后移②后③前3,①前移①前③后4、①相等5、①物理存儲位置②鏈域的指針值6、①前趨②后繼7、①q->next8、①p->next②s->data③t9、①單鏈表②雙鏈表③非循環(huán)鏈表④循環(huán)鏈表10、①（后繼）指針域的取值11、①順序②鏈接12、使空表和非空表統(tǒng)一；算法處理一致。13、①一定②不一定14、①24②19二、選擇題1、A2、B3、D4,A5、D6、B7、A8、B9、B10、C11、D三、判斷題1、錯2、錯3、對4、錯5、對2.2應(yīng)用知識1、描述以下三個概念的區(qū)別：頭指針、頭結(jié)點、表頭結(jié)點。解答：頭指針是指向鏈表中第一個結(jié)點（即表頭結(jié)點）的指針，在表頭結(jié)點之前附設(shè)的一個結(jié)點稱為頭結(jié)點，表頭結(jié)點為鏈表中存儲線性表中第一個數(shù)據(jù)元素的結(jié)點。若鏈表中附設(shè)頭結(jié)點，則不管線性表是否為空表，頭指針均不為空，頭指針的設(shè)置使得對鏈表的第一個位置上的操作與在表其他位置上的操作一致（都是在某一結(jié)點之后），否則表示空表的鏈表的頭指針為空。2、在單鏈表和雙向鏈表中，能否從當(dāng)前結(jié)點出發(fā)訪問任一結(jié)點？在單鏈表、雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結(jié)點，不知道頭指針，能否將結(jié)點*p從相應(yīng)的鏈表中刪去?若可以，其時間復(fù)雜度各為多少？解答：在單鏈表中只能由當(dāng)前結(jié)點訪問其后的任一結(jié)點，因為沒有指向其前趨結(jié)點的指針。而在雙向鏈表中既有指向其后繼結(jié)點的指針又有指向其前趨結(jié)點的指針，故可由當(dāng)前結(jié)點出發(fā)訪問鏈表中的任一結(jié)點。下面分別討論三種鏈表的情況。.單鏈表。若指針p指向某結(jié)點時，能夠根據(jù)該指針找到其直接后繼，能夠順后繼指針鏈找到*p結(jié)點后的結(jié)點。但是由于不知道其頭指針，所以無法訪問到p指針指向的結(jié)點的直接前趨。因此無法刪去該結(jié)點。.雙鏈表。由于這樣的鏈表提供雙向指針，根據(jù)*p結(jié)點的前趨指針和后繼指針可以查找到其直接前趨和直接后繼，從而可以刪除該結(jié)點。其時間復(fù)雜度為0(1)。.單循環(huán)鏈表。根據(jù)已知結(jié)點位置，可以直接得到其后相鄰的結(jié)點位置(直接后繼)，又因為是循環(huán)鏈表，所以我們可以通過查找，得到p結(jié)點的宜接前趨。因此可以刪去p所指結(jié)點。其時間復(fù)雜度應(yīng)為O(n)。3、線性表的兩種存儲結(jié)構(gòu)各有哪些優(yōu)缺點？何時選用順序表、何時選用鏈表作為線性表的存儲結(jié)構(gòu)為立？解答：線性表具有兩種存儲結(jié)構(gòu)即順序存儲結(jié)構(gòu)和鏈接存儲結(jié)構(gòu)。線性表的順序存儲結(jié)構(gòu)可以直接存取數(shù)據(jù)元素，方便靈活、效率高，但插入、刪除操作時將會引起元素的大量移動，因而降低效率；而在鏈接存儲結(jié)構(gòu)中內(nèi)存采用動態(tài)分配，利用率高，但需增設(shè)指示結(jié)點之間關(guān)系的指針域，存取數(shù)據(jù)元素不如順序存儲方便，但結(jié)點的插入、刪除操作較簡單。在實際應(yīng)用中，應(yīng)根據(jù)具體問題的要求和性質(zhì)來選擇順序表或鏈表作為線性表的存儲結(jié)構(gòu)，通常有以下幾方面的考慮：.基于空間的考慮。當(dāng)要求存儲的線性表長度變化不大，易于事先確定其大小時，為了節(jié)約存儲空間，宜采用順序表：反之，當(dāng)線性表長度變化大，難以估計其存儲規(guī)模時，采用動態(tài)鏈表作為存儲結(jié)構(gòu)為好。.基于時間的考慮。若線性表的操作主要是進(jìn)行查找，很少做插入和刪除操作時，采用順序表做存儲結(jié)構(gòu)為宜；反之，若需要對線性表進(jìn)行頻繁地插入或刪除等的操作時，宜采用鏈表做存儲結(jié)構(gòu)。并且，若鏈表的插入和刪除主要發(fā)生在表的首尾兩端，則采用尾指針表示的單循環(huán)鏈表為宜。4、對于線性表的兩種存儲結(jié)構(gòu)，如果有n個線性表同時并存，而且在處理過程中各表的長度會動態(tài)發(fā)生變化，線性表的總數(shù)也會自動改變，在此情況下，應(yīng)選用哪一種存儲結(jié)構(gòu)？為什么？解答：應(yīng)選用鏈接存儲結(jié)構(gòu)，因為鏈?zhǔn)酱鎯Y(jié)構(gòu)是用一組任意的存儲單元依次存儲線性表中的各元素，這里存儲單元可以是連續(xù)的，也可以是不連續(xù)的，這種存儲結(jié)構(gòu)對于元素的刪除或插入運算是不需要移動元素的，只需修改指針即可，所以很容易實現(xiàn)表的容量的擴充。5,對于線性表的兩種存儲結(jié)構(gòu)，若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素，那么應(yīng)選用何種存儲結(jié)構(gòu)？試說明理由。解答：應(yīng)選用順序存儲結(jié)構(gòu)，因為每個數(shù)據(jù)元素的存儲位置和線性表的起始位置相差一個和數(shù)據(jù)元素在線性表中的序號成正比的常數(shù)。因此，只要確定了其起始位置，線性表中的任一個數(shù)據(jù)元素都可隨機存取，因此，線性表的順序存儲結(jié)構(gòu)是一種隨機存取的存儲結(jié)構(gòu)，而鏈表則是一種順序存取的存儲結(jié)構(gòu)。6,為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好？解答：尾指針是指向終端結(jié)點的指針，用它來表示單循環(huán)鏈表可以使得查找鏈表的開始結(jié)點和終端結(jié)點都很方便，設(shè)一帶頭結(jié)點的單循環(huán)鏈表，其尾指針為rear,則開始結(jié)點和終端結(jié)點的位置分別是rear->next->next和rear,查找時間都是0(1)。若用頭指針來表示該鏈表，則查找終端結(jié)點的時間為0(n)o7、假設(shè)單鏈表的表頭指針用head表示，其類型為linklist,寫出將其所有結(jié)點按相反次序鏈接的算法。contray(head)/*將head單鏈表中所有結(jié)點按相反次序鏈接*/linklist*head；/*head為單鏈表類型，含有數(shù)據(jù)域和指針域等*/{linklist*p,*q：p=head；/*p指向未被逆序的第一個結(jié)點，初始時指向原表頭結(jié)點*/head=Nul1：while(pl-Null)(q=P;/*q指向?qū)⒈荒嫘蜴溄拥慕Y(jié)點*/P=p->next；q->next=head；head=q；)}/*contray*/8、設(shè)計產(chǎn)生一個有兩個結(jié)點的鏈表的算法，且第一個結(jié)點中放數(shù)值x,第二個結(jié)點中放數(shù)值y,head為頭指針。解答：先分別生成兩個結(jié)點，然后將這兩個結(jié)點鏈接起來，最后對這兩個結(jié)點的數(shù)據(jù)域賦值。linklist*createlist() /*產(chǎn)生一個有兩個結(jié)點的鏈表*/linklist*head,*s；intx,y；head=malloc(sizeof(linklist))；s=malloc(sizeof(linklist))；head->next=s；s->next=Null；head->data=x；s->data=y；returnhead；}/*createlist*/9、設(shè)計在無頭結(jié)點的單鏈表中刪除第i個結(jié)點的算法。解答：算法的思想為：(1)應(yīng)判斷刪除位置的合法性，當(dāng)i<0或i>n-1時，不允許進(jìn)行刪除操作；(2)當(dāng)i=0時，刪除第一個結(jié)點；(3)當(dāng)0<i<n時，允許進(jìn)行刪除操作，但在查找被刪除結(jié)點時，須用指針記住該結(jié)點的前趨結(jié)點。從而將算法描述為：delete(q,i)/*在無頭結(jié)點的單鏈表中刪除第i個結(jié)點*/linklist*q；inti；{linklist*p,*S；intj；if(i<0)printf(<<Can，tdelete\nw)；elseif(i==0){s=q；q=q->next；free(s)；}else{j=0：s=q；while((j<i)&&(s!=Null))p=S；s=s->next；j++}if(s==Null)printf(^cant,tdelete\nw)；else(p->next=s->next；free(s)；})}/"delete*/10、假設(shè)有一個帶附加表頭結(jié)點的鏈表，表頭指針為head,每個結(jié)點含三個域：data、next和prioro其中data為整型數(shù)域，next和prior均為指針域?，F(xiàn)在所有結(jié)點已經(jīng)由next域連接起來，試編?個算法，利用prior域(此域初值為Null)把所有結(jié)點按照其值從小到大的順序鏈接起來。解答：insert(head)/*將鏈表中所有結(jié)點利用prior域按照其值有序鏈接起來*/linklist*head；/*linklist為,個具有三個域的結(jié)點類型，含data；next和prior*/|linklist*p,*s,*q；p=head->next； /*p指向待插入的結(jié)點，初始時指向第一個結(jié)點*/while(p!=Null)Is=head；/*s指向結(jié)點的前趨結(jié)點*/q=head->prior；/*q指向由prior域構(gòu)成的鏈表中待比較的結(jié)點*/while((q!=Nul1)&&(p->data>q->data))/*查找插入結(jié)點*p的合適的插入位置*/s二q；q=q->prior；s->prior=P；p->prior=q；/**q結(jié)點插入到*S和*q結(jié)點之間*/}p=p->next；"insert*/)}"insert*/11、設(shè)有個向量A=(見，a2,-.an),試設(shè)計一個算法將向量膛，即使得元素排列次序顛倒，成為逆向量A=(an?--1,…，@2,ai),要求不重新開辟空間，且用順序表和單鏈表兩種表示方法，設(shè)計不同的處理算法。解答：.順序表：要將該表逆置，可以將表中的開始結(jié)點與終端結(jié)點互換，第二個結(jié)點與倒數(shù)第二個結(jié)點互換，如此反復(fù)，就可將整個表逆置了。算法如下：#defineListSize100//假定表空間大小為100typedefintDataType;〃假定DataType的類型為int型typedefstruct{DataTypedata(ListSize];//向量data用于存放表結(jié)點intlength;//當(dāng)前的表長度}Seqlist;〃以上為定義表結(jié)構(gòu)voidReverseList(Seqlist*L)DataTypetemp;〃設(shè)置臨時空間用于存放datainti;for(i=0;i<=L->length/2;i++)//L->length/2為整除運算{temp=L->data[i];〃交換數(shù)據(jù)L->data[i]=L->data[L->length-1-i];L->data[L->length-1-i]=temp;}}.鏈表：可以用交換數(shù)據(jù)的方式來達(dá)到逆置的目的。但是由于是單鏈表，數(shù)據(jù)的存取不是隨機的，因此算法效率太低?？梢岳弥羔樃闹竵磉_(dá)到表逆置的目的。具體情況入下：(1)當(dāng)鏈表為空表或只有?個結(jié)點時，該鏈表的逆置鏈表與原表相同。(2)當(dāng)鏈表含2個以上結(jié)點時，可將該鏈表處理成只含第一結(jié)點的帶頭結(jié)點鏈表和一個無頭結(jié)點的包含該鏈表剩余結(jié)點的鏈表。然后，將該無頭結(jié)點鏈表中的所有結(jié)點順著鏈表指針，由前往后將每個結(jié)點依次從無頭結(jié)點鏈表中摘下，作為第一個結(jié)點插入到帶頭結(jié)點鏈表中。這樣就可以得到逆置的鏈表。算法是這樣的：結(jié)點結(jié)構(gòu)定義如下：typedefcharDataType;〃假設(shè)結(jié)點的數(shù)據(jù)域類型的字符typedefstructnode{〃結(jié)點類型定義DataTypedata;〃結(jié)點的數(shù)據(jù)域structnode*next;〃結(jié)點的指針域JListNode;typedefListNode*LinkList;ListNode*p;LinkListhead;LinkListReverseList(LinkListhead){//將head所指的單鏈表(帶頭結(jié)點)逆置ListNode*p,*q;〃設(shè)置兩個臨時指針變量head->next&&head->next->next){〃當(dāng)鏈表不是空表或單結(jié)點時p=head->next;q=p->next;p->next=NULL;〃將開始結(jié)點變成終端結(jié)點while(q){〃每次循環(huán)將后一個結(jié)點變成開始結(jié)點p=q；q=q->next;p->next=head->next;head->next=p;}returnhead;}returnhead;〃如是空表或單結(jié)點表，直接返1nlhead}12、設(shè)計將單循環(huán)鏈表逆置的算法。解答：設(shè)單循環(huán)鏈表的頭指針為head,類型為linklist,則可得算法如下:invert(head)/*逆置head指針?biāo)赶虻膯窝h(huán)鏈表*/linklist*head；(linklist*p,*q,*S；q=head；p=head->next；while(p!=head){s=q；q=P：p=p->next；q->next=S；p->next=q；}"invert*/13、設(shè)計將?個雙向循環(huán)鏈表逆置的算法。解答:設(shè)雙向循環(huán)鏈表的結(jié)點類型為dblinklist,其中每個結(jié)點含三個域,分別為next,data與prior域，雙向鏈表的頭指針為head,從而可得算法如下：invert(head) /*將head指針?biāo)赶虻碾p向循環(huán)鏈表逆置*/dblinklist*head；{dblinklist*p,*q；p=head；do(q=p->next；p->next=p->prior；p->prior=q；P=q；}while(p==head)}/"invert*/14、用順序存儲結(jié)構(gòu)實現(xiàn)將兩個有序表合并成為一個有序表，合并后的結(jié)果不另設(shè)新表存儲。解答：設(shè)有序表為遞增序列，則其算法思想為：(1)設(shè)A,B均為有序表，且均為整型數(shù)組，合并后的結(jié)果仍存放在A表中。(2)設(shè)A表的長度為n,B表的長度為m,合并之后的長度為m+n：(3)合成過程中需進(jìn)行元素的比較，可以先從A和B的最后一個元素逐個向前進(jìn)行比較,可以使得合并后的結(jié)果不影響A中原來存放的元素。算法如下：intmerge(A,B)/*將兩個有序表A和B合并成為F一個有序表*/sequenlist*A,*B； /*A；*B為指向sequenlist類型的指針變量，含last和vec域*/intm,n；n=(*A).last；m=(*B).last；while((*B).last>0)(if(((*A).last==O)||(*A).vec[(*A).last]<(*B).vec[(*B).last]))((*A).vec[(*A).last+{*B}.last]=(*B).vec[(*B).last]；(*B).last=(*B).last-1；}else((*A).vec[(*A).last+(*B).last]=(*A).vec[(*A).last]；(*A).last=(*A).last；}}(*A).last=n+m；return(1)；}/*merge*/15、用鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)將兩個有序表合成一個有序表。解答：設(shè)有序表為遞增序列，則算法如下：merge(ahead,bhead)linklist*ahead,*bhead；/*head,bhead分別為兩個有序表的頭指針，合并后的結(jié)果存放在以ahead為頭指針的有序鏈表中*/(linklist*p,*q,*t；p=Null；while(bhead!=Nu11)if{ahead二二Null}ahead=bhead；bhead=Null；)else{if(bhead->data>ahead->data)(t=ahead；ahead=ahead->next；)else(t=bhead：bhead=bhead->next：)t->next=Null；if(p==Null)p=t；elseq->next=t；)if(ahead==Nul1)p=ahead；elseq->next=ahead；q二ahead；ahead=p；}/*merge*/16、已知兩個循環(huán)鏈表a=（ai，a2,…，an-i,an）^Db=（bi，b2,…，bm-i?bm）,設(shè)計出將這

兩個表合并為循環(huán)鏈表C的算法。解答：算法如下:dblinklistmerge(ha,hb) *合并兩個循環(huán)鏈表*/dblinklist*ha,hb；/*ha,hb為指向循環(huán)鏈表類型dblinklist的指針變dblinklist*ha,hb；量*/{dblinklist*hc,*qa,*qb,*qc：if(ha==Nul1)hc=hb；/*a表為空*/if(hb==Null)hc=ha；if(ha==Nul1)hc=hb；/*a表為空*/if(hb==Null)hc=ha；/*b表為空*/if((ha!=Null)&&(hb!=Nul1))qa=ha；qb=hb；he二ha；qa=qa->next；hc->next=qb；qc=qb：qb=qb->next；while((ha!=qa)&&(hb!=qb))Iqc->next=qa；qc=qa；qa=qa->next；qc->next=qb；qc=qb；qb=qb->next；Iif(ha==qa)while((hb!=qb)qc->next=qb；qc=qb；qb=qb->next；}if(hb==qb)while(ha!=qa)Iqc->next=qb；qc=qa；qa=qa->next；)qc->next=hc；returnhe；}/*merge*/17、假設(shè)有?個循環(huán)鏈表的長度大于1,且表中既無頭結(jié)點也無頭指針， 己知p為指向鏈表中某結(jié)點的指針，設(shè)計出在鏈表中刪除p所指結(jié)點的前趨結(jié)點的算法。解答：可引入一個指針q,當(dāng)p->next=q時，說明此時q所指的結(jié)點為p所指結(jié)點的前趨結(jié)點，從而可得算法如下：delete(p) /*在鏈表中刪除p所指結(jié)點的前趨結(jié)點*/linklist*p；linklist*q；q=p：while(q->next->next!=p){q=q->next；t=q->next；q->next=p；free(t)；}/*delete*/18、已知線性表的元素按遞增順序排列，并以帶頭結(jié)點的單鏈表作存儲結(jié)構(gòu)。試編寫一個刪除表中所有值大于min且小于max的元素(若表中存在這樣的元素)的算法。解答：算法如下：delete(head,max,min)/*刪除有序單鏈表中所有值大于min且小于max的元素*/linklist*head；intmax,min；Ilinklist*p,*q；if(head!=Null)(q=head：p=head->next；while((p!=Null)&&(p->data<=min))(q=P;p=p->next；}while((p!=Null)&&(p->data<max))p=p->next；q->next=P；)}/*delete*/19、已知線性表的元素是無序的，且以帶頭結(jié)點的單鏈表作為存儲結(jié)構(gòu)。設(shè)計一個刪除表中所有值小于max但大于min的元素的算法。解答：算法如下：delete(head,max,min)/*刪除無序單鏈表中所有值大于min且小于max的元素*/linklist*head；intmin,max；linklist*p,*q；q=head；p=head->next；while(p!=Null)if((p->data<=min)||(p->data>=max))(q=P;p=p->next；}elseIq->next=p->next；free(p)；q=q->next；}}/*delete*/20、設(shè)指針la,lb分別指向兩個不帶頭結(jié)點的單鏈表a、b的第一個結(jié)點，試設(shè)計一個從表a中刪除自第i個元素起共len個元素，并將這len個元素插入到表b中第i個元素之前的算法。解答：算法描述如下：deleteinsert(la,lb,i,len)/*從表a中刪除元素，并將這些元素插入到表b中*/linkfist*la,*lb/*la*la,*lb分別為linklist類型的指針變量*/inti,len；{linklist*r,*p,*q,*s；inti,k；if(i<01Ilen<0)printf(uerror\nw)；P=la；k=l；while((p!=Null)&&(k<i))r=p；p=p->next；k++；)/*查找la表中第i個元素*/if(p==Null)printf(aerror\rw)；else(q二P;1k=l；while((q!=Null)&&(k<len)) /*查找第i+len-1個元素*/Iq=q->next；k++；}if(q==Null)printf(<<error\n**)；else{r->next=q->next；if(i==1){q->next=b；lb=P；} /*在lb表中查找插入位置并插入*/else{s=lb；k=l；while((s!=Null)&&(k<i-l)){s=s->next；

k++；) /*查找1b表中第i-1個元素*/if(s==Null)printf("error\n")；else{q->next=s->next；s->next=p；))}}*deleteinsert*/21、設(shè)計一個在不帶頭結(jié)點的鏈表的第i個元素之前插入一個元素的算法。解答：算法步驟為：(1)當(dāng)i<=0時，不允許進(jìn)行插入，出錯處理；(2)當(dāng)i=l時，則插入的結(jié)點作為第一個表結(jié)點；(3)當(dāng)i>n時，n為鏈表中的結(jié)點個數(shù)，此時不允許插入，出錯處理；(4)當(dāng)l<i<=n時，則可進(jìn)行插入，此時必須查找第i個結(jié)點，但同時須記住它的前趨在點。從而算法可描述如下：insert(q,x,i)/*在不帶頭結(jié)點的鏈表的第i個元素之前插入一個元素*/linklist*q；inti；datatypex；{linklist*s, *p；intj；if(i<=0)printf(“can'tinserterror\)；else(s=malloc(sizeof(linklist))；s->data=x；if(i==1){s->next=q；q=s；)elseIj=l;p=q；while((j<i-l)&&(p!=Null)){p=p->next；j++;}if(p==Null)printf(“error\n")；else{s->next=p->next；p->next=s；}/*insert*/22、計一個算法，將一個用循環(huán)鏈表表示的稀疏多項式分解成兩個多項式，使這兩個多項式中各自僅含奇數(shù)項或偶數(shù)項，并要求利用原鏈表中的結(jié)點空間來構(gòu)成這兩個鏈表。解答：此題解題思想為：(1)首先建立奇數(shù)項循環(huán)鏈表的頭結(jié)點，偶數(shù)項的頭結(jié)點仍用多項式循環(huán)鏈表的頭結(jié)點；(2)然后查找該多項式循環(huán)鏈表的各個結(jié)點，依據(jù)結(jié)點的指數(shù)域進(jìn)行處理；(3)當(dāng)查找的結(jié)點的指數(shù)域為偶數(shù)時，則只修改查找指針及其前趨結(jié)點指針；(4)當(dāng)查找的結(jié)點的指數(shù)域為奇數(shù)時，將該結(jié)點與原鏈表分離開，且原鏈表仍保持循環(huán)鏈表，然后再鏈接到奇數(shù)項循環(huán)鏈表中，再修改奇數(shù)循環(huán)鏈表指針及查找指針；(5)當(dāng)分解結(jié)束時，查找指針應(yīng)與原鏈表的頭結(jié)點的指針一致。從而算法可描述為：linklistseparate(head)/*將循環(huán)鏈表表示的稀疏多項式分解成兩個多項式*/linklist*head；/*linklist為鏈表的結(jié)點類型*/{linklist*odd,*q,*p,*s；odd=malloc(sizeof(linklist))； /*構(gòu)造奇數(shù)表的表頭結(jié)點*/odd->next=odd；q=head；s=head；p=head->next；while(p!=head)if((p->data)%2==0) /*偶數(shù)項*/(q=p；p=p->next；)else(q->next=p->next；p->next=s->next；s->next=p；p=q->next；s=s->next；}returnodd；} /*separate*/23、試分別在一個雙向循環(huán)鏈表中的值為x的結(jié)點之前、之后插入值為y的結(jié)點，分別寫出各自的算法。解答：設(shè)一個雙向循環(huán)鏈表的頭指針為head,且設(shè)類型為dblinkist,則可寫出算法為：(1)在值為X的結(jié)點之前插入值為y的結(jié)點的算法：insertbefore(head,x,y)dblinklist*head； /*設(shè)鏈表頭指針為head*/intx,y；(dblinklist*p,*q；p=head->next；q=malloc(sizeof(dblinklist))；q->data=y；while((p!=head)&&(p->data!=x))p=p->next；if(p==head)printf("xdoesn*texist'n")；else{q->prior=p->prior；q->next=p；p->prior->next=q；p->prior=q：)}/*insertbefore*/(2)在結(jié)點x之后插入結(jié)點y的算法：insertafter(head,x,y)dblinklist*head；intx,y；{dblinklist*p,*q；p=head->next；q=malloc(sizeof(dblinklist))；q->data=y；while((p!=head)&&(p->data!=x))if(p==head)printf("xdoesn，texist\n,f)；else{q->prior=p；q->next=p->next；p->next->priOr=q；p->next=q；)} /*insertafter*/24、試設(shè)計實現(xiàn)刪除單鏈表中值相同的多余結(jié)點的算法。解答：設(shè)單鏈表(設(shè)類型為linklist)的頭指針head指向頭結(jié)點，則可按下列步驟執(zhí)行：首先，用一個指針P指向單鏈表中第一個表結(jié)點，然后用另一個指針q查找鏈表中的結(jié)點元素，由于是單鏈表，故結(jié)束條件為p=Null,同時讓指針pre指向q所指結(jié)點的前趨結(jié)點，當(dāng)查找到結(jié)點具有q->data=p-〉data時刪除q所指的結(jié)點，然后再修改P，使P指針后移(即P=p->next),重復(fù)進(jìn)行，直到p為空時為止。算法描述如下：delete(head) /*刪除單鏈表中值相同的多余結(jié)點*/linklist*head；(linklist*p,*pre,*q；p=head->next；q=P：while(p!=Null)(pre=q；q=q->next；while((q!=Null)&&(q->data!=p->data)) /*查找值相同的結(jié)點并刪除*/{pre=q；if(q!=Null){pre->next=q->next；free(q)；q=pre->next；)p=p->next；q二P；)}/"delete*/25、寫出在一個帶頭結(jié)點的單鏈表中的值為x的結(jié)點之后插入m個結(jié)點的算法。解答：算法描述如下：insert(head,m,x)/*在單鏈表head中值為x的結(jié)點之后插入m個結(jié)點*/linklist*head； /*設(shè)單鏈表的結(jié)點類型為linklist*/intm；datatypex；{linklist*p, *q, *s；inti；datatypey；p=head->next；while((p!=Null)&&(p->data!=x))p=p->next；/*查找值為x的結(jié)點*/if(p==Null)printf(uxdoesn'texist\nM)；else{q=p->next；for(i=0；i<m；i++) /*插入m個結(jié)點*/(s=malloc(sizeof(linklist))；scanf(&y)；p->next=s；p=s；}p->next=q；}}/*insert*/26、給定(已生成)一個帶頭結(jié)點的單鏈表，設(shè)head為頭指針，結(jié)點的結(jié)構(gòu)為(data,next),data為整數(shù)元素，nexl為指針。寫出算法，按遞增次序輸出鏈表各結(jié)點的數(shù)據(jù)元素，并釋放結(jié)點所占的存儲空間。(要求：不允許使用數(shù)組作輔助空間)解答：voidincrease(linklist*head){lingklist*p,*q,*r;intmin;p=head->next;while(p!=NULL){q=NULL;min=p->data;匚P；while(r->next!=NULL){if(r->next->data<min){q=r;min=r->next->data;}r=r->next;}printf(44%dv,min);if(q=NULL)p=p->next;elseq->next=q->next->next;))27、設(shè)順序表L是一個遞增有序表，試寫一算法，將x插入L中，并使L仍是一個有序表。解答：因已知順序表L是遞增有序表，所以只要從順序表終端結(jié)點(設(shè)為i位置元素)開始向前尋找到笫一個小于或等于x的元素位置i后插入該位置即可。在尋找過程中，由于大于x的元素都應(yīng)放在x之后，所以可邊尋找，邊后移元素，當(dāng)找到第一個小于或等于X的元素位置i時，該位置也空出來了。算法如下：〃順序表存儲結(jié)構(gòu)如題11voidInsertIncreaseList(Seqlist*L,Datatypex){inti;if(L->length>=ListSize)ErrorC'overflow");for(i=L->length;i>0&&L->data[i-1]>x;i—)L->data[i]=L->data|i-1];//比較并移動元素L->data[i]=x;L->length++;)28、設(shè)順序表L是一個遞減有序表，試寫一算法，將x插入其后仍保持L的有序性。解答：與上題相類似，只要從終端結(jié)點開始往前找到第一個比x大(或相等)的結(jié)點數(shù)據(jù),在這個位置插入就可以了。(邊尋找，邊移動)算法如下：voidInsertDecreaseList(Seqlist*L,Datatypex)(inti;if(L->length>=ListSize)Error(44overflow,');for(i=L->length;i>0&&L->data[i-1]<x;i-)L->data[i]=L->data[i];//比較并移動元素L->data[i]=x;L->length++;}29、寫一夕法在的鏈表上實現(xiàn)線性表的ListLength(L)運駕。解答：由于在單鏈表中只給出一個頭指針，所以只能用遍歷的方法來數(shù)單鏈表中的結(jié)點個數(shù)了。算法如下：intListLength(LinkListL)intlen=O;ListNode*p;p=L;〃設(shè)該表有頭結(jié)點while(p->next){p=p->next;Ien++;)returnlen;第三章棧和隊列一、基本內(nèi)容棧和隊列的結(jié)構(gòu)特性；在兩種存儲結(jié)構(gòu)上如何實現(xiàn)棧和隊列的基本操作以及棧和隊列在程序設(shè)計中的應(yīng)用。二、學(xué)習(xí)要點1、掌握棧和隊列這兩種抽象數(shù)據(jù)類型的特點，并能在相應(yīng)的應(yīng)用問題中正確選用它們。2、熟練掌握棧類型的兩種實現(xiàn)方法，即兩種存儲結(jié)構(gòu)表示時的基本操作實現(xiàn)算法。3、熟練掌握循環(huán)隊列和鏈隊列的基本操作實現(xiàn)算法。.1基礎(chǔ)知識一、填空題1、線性表、棧和隊列都是①結(jié)構(gòu),可以在線性表的②位置插入和刪除元素:對于棧只能在③插入和刪除元素：對于隊列只能在 ④插入元素和在⑤刪除元素。2、棧的插入和刪除只能在棧的頂端進(jìn)行,后進(jìn)棧的元素必定先被刪除,所以又把棧稱作_①表；隊列的插入和刪除運算分別在兩端進(jìn)行，進(jìn)行插入的一端叫做② ，進(jìn)行刪除的一端叫做③，先進(jìn)隊的元素必定先出隊，所以又把隊列稱作④表。3、（棧頂指針指向棧頂元素）向順序棧中插入新的元素分三步：第一步，進(jìn)行①判斷,判斷條件是②；第二步，修改③；第三步即把新元素賦給④。同樣從順序棧中刪除元素的過程可分三步：第一步進(jìn)行⑤判斷,判斷條件為⑥ ，第二步是把⑦的值返回,第三步是⑧ 。4、在遞歸算法中，每次遞歸調(diào)用前，系統(tǒng)自動把①，②的當(dāng)前值以及調(diào)用后的③壓入棧:在每次遞歸調(diào)用結(jié)束后，又自動作退棧處理，恢復(fù)值參和局部變量的原值，接著由④返回地址所決定的位置執(zhí)行。5,對于一個棧作進(jìn)棧運算時，應(yīng)先判別棧是否為① ，作退棧運算時，應(yīng)先判別棧是否為②，當(dāng)棧中元素為m時，作進(jìn)棧運算時發(fā)生上溢，則說明棧的可用最大容量為⑧_=為了增加內(nèi)存空間的利用率和減少發(fā)生上溢的可能性，由兩個棧共享一片連續(xù)的內(nèi)存空間時，應(yīng)將兩棧的④分別設(shè)在這片內(nèi)存空間的兩端，這樣只有當(dāng)⑤時

才產(chǎn)生上溢。6、設(shè)有一空棧，現(xiàn)有輸入序列1,2,3,4,5,經(jīng)過push,push,pop,push,pop,TOC\o"1-5"\h\zpush,push后，輸出序列是① 。7、設(shè)一個數(shù)列的順序為1,2,3,4,5,6,通過棧結(jié)構(gòu)可以排成的順序數(shù)列為 ①8、有一個循環(huán)隊列如圖3-1,其隊滿條件是①，隊列空的條件是② 。隊尾指針注：陰影部分表示隊列中有元素隊頭指針隊尾指針注：陰影部分表示隊列中有元素(A)rear%n=front(B)(front+l)%n=rear(C)rear%n-l=front(D)(rear+l)%n=front(A)rear%n=front(B)(front+l)%n=rear(C)rear%n-l=front(D)(rear+l)%n=front圖3-1二、選擇題1、若有一個棧的輸入序列是1,2,3,…，n,輸出序列的第一個元素是n,則第i個輸出元素是。(A)n-i(B)n-i-1(C)n-i+1(D)不確定2、設(shè)有一個棧，元素的進(jìn)棧次序為A,B,C,D,E,下列是不可能的出棧序列。(A) A, B, C, D, E (B)B, C, D, E, A(C) E, A, B, C, D (D)E, D, C, B, A3、在一個具有n個單元的順序棧中，假定以地址低端(即0單元)作為棧底，以top作為棧頂指針，則當(dāng)做出棧處理時，top變化為。(A)top不變(B)top=0(C) top- (D)top++4,在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊頭指針和隊尾指針，則判斷隊滿的條件為l_3_+x_-y_*l_3_x_+-y_*l_3_+x_-y_*l_3_x_+-y_*5、一個中綴算術(shù)表達(dá)式為1+(3-x)*y,則其對應(yīng)的后綴算術(shù)表達(dá)式為。知表示空格鍵)

6、向一個棧頂指針為hs的鏈棧中插入一個*s結(jié)點時，應(yīng)執(zhí)行hs->next=s； (B)s->next=hs；hs=s；snext=hs->next；hs->next=s；(D)s->next=hs；hs=hs->next；7、在一個鏈隊列中，假定front和rear分別為隊頭和隊尾指針，則插入*s結(jié)點的操作應(yīng)執(zhí)行 (A)front->next=s；front=s；(B)s->next=rear；rear=s；rear->next=s；rear=s； (D)s->next=front；front=s8、在一個鏈隊列中，假定front和rear分別為隊首和隊尾指針，則刪除一個結(jié)點的操作為o(該鏈隊列不設(shè)頭結(jié)點)front=front->next(B)rear=rear->nextrear=front->next (D)front=rear->next9、進(jìn)棧序列為1,2,3,4,5,并且在它們進(jìn)棧的過程中可以進(jìn)行出棧操作，那么不可能是出棧序列。(A)l,3,2,5,4 (B)l,2,5,4,3(04,3,2,1,5 (D)3,5,1,4,210、設(shè)棧S和隊列Q的初始狀態(tài)為空,元素el,e2,e3,e4,e5和e6依次通過棧S,一個元素出棧后即進(jìn)入隊列Q,若6個元素出隊的順序為e2,e4,e3,e6,e5,el,則棧S的容量至少應(yīng)該是 o(A)6 (B)4 (C)3 (D)211、以下不是棧的基本運算。(A)從棧頂刪除一個元素(B)判斷一個棧是否為空(C)在棧中的第i個元素之前插入一個新元素(D)讀取棧頂元素的值12、若對一個空棧S進(jìn)行如下操作：PUSH(S,1);PUSH(S,2);POP(S);PUSH(S,3);PUSH(S,4);POP(S);PUSH(S,5)那么棧S中從棧頂?shù)綏５自氐呐帕许樞驗?。(A)l,3,5 (B)2,4,5 (C)5,3,1 (D)5,4,213、數(shù)組Q[l..n]是一個環(huán)形隊列，front記錄當(dāng)前隊頭元素的前一位置,rear記錄著隊尾元

素的位置,那么在隊列未滿時進(jìn)行將元素X進(jìn)隊的操作需要執(zhí)行一_o(A)rear=rear+1；Q[rear]=x；(B)rear=(rear+1)modn；Q[rear]=x；(C)Q[rear]=x；rear=rear+l；(D)Q[rear]=x；rear=(rear+l)modn14、若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)rear和front的值分別為0和3,當(dāng)從隊列中刪除一個元素后，rear和front的值分別為多少?(A)l,5 (B)2,4 (C)4,2 (D)5,115、設(shè)枝S和隊列Q的初始狀態(tài)為空，元素el,e2,e3,e4,e5,e6依次通過棧S,一個元素出棧后即進(jìn)入隊列Q,若6個元素出隊的序列是e2,e4,e3,e6,e5,el,則棧S的容量至少應(yīng)該為0(A)6 (B)4 (C)3 (D)2解答：一、填空題1、①線性②任何③棧頂④隊尾⑤隊頭2、①后進(jìn)先出②隊尾③隊頭或隊首④先進(jìn)先出3、①溢出或棧滿②s->top=maxs-1③棧頂指針④棧頂單元⑤?？闸辳->top=-1⑦棧頂指針⑧修改棧頂指針4、①值參②局部變量③返回地址④無條件轉(zhuǎn)向5、①棧滿②?？闸踡④棧底⑤兩個棧的棧頂在?？臻g的某一位置相遇6、①2；3①3、2、5、6、4、1②2、4、3、5、1、6③4、5,3、6、2、1①front=(rear+l)%n②rear=front二、選擇題1、(C)2、(C)3、(C)4、(D)5,(C)6、(B)7、(C)8、(A)9、(D)10、(C)11、(C)12、(C)13、(B)14、(B)15、(C)3.2應(yīng)用知識1、試證明：若借助棧由輸入序列1、試證明：若借助棧由輸入序列1,2,n,得到輸出序列P”P2,…，匕(它是輸入序列的一個排列），則在輸出序列中不可能出現(xiàn)這樣的情況：存在i〈j<k使得Pj<Pk<Pio證明：若有j〈k和P）<Pk,則必須在R進(jìn)棧之前將P,出棧；若PDR,則必須把R留在棧中，直到P進(jìn)棧之后。顯然，由上面兩條可知，條件i<j〈k和PKPKP、是不可能同時成立的，因為由這兩個條件可知，P,必須在葭之前和P,之后返棧，而匕又出現(xiàn)在R之后，顯然不符合邏輯，因而得證。2,何謂隊列的上溢現(xiàn)象，一般有幾種解決方法，試簡述之。解答：在隊列的順序存儲結(jié)構(gòu)中，設(shè)隊頭指針為front,隊尾指針為rear,隊列的容量（即存儲的空間大?。閙axsize。當(dāng)有元素要加入隊列（即入隊）時，若rear=maxsize,則會發(fā)生隊列的上溢現(xiàn)象，此時就不能將該元素加入隊列。對于隊列，還有一種“假溢出”現(xiàn)象，隊列中尚余有足夠的空間，但元素卻不能入隊，一般是由于隊列的存儲結(jié)構(gòu)或操作方式的選擇不當(dāng)所致，可以用循環(huán)隊列解決。一般地，要解決隊列的上溢現(xiàn)象可有以下幾種方法：（1）可建立一個足夠大的存儲空間以避免溢出，但這樣做往往會造成空間使用率低，浪費存儲空間。（2）要避免出現(xiàn)“假溢出”現(xiàn)象可用以下方法解決：第一種：采用移動元素的方法。每當(dāng)有一個新元素入隊，就將隊列中已有的元素向隊頭移動一個位置，假定空余空間足夠。第二種：每當(dāng)刪去一個隊頭元素，則可依次移動隊列中的元素總是使front指針指向隊列中的第一個位置。第三種：采用循環(huán)隊列方式。將隊頭、隊尾看作是一個苜尾相接的循環(huán)隊列，即用循環(huán)數(shù)組實現(xiàn)，此時隊首仍在隊尾之前，作插入和刪除運算時仍遵循“先進(jìn)先出”的原則。3、利用兩個棧模擬?個隊列的入隊，出隊和判隊空等運算。解答：利用兩個棧模擬一個隊列的運算的基本思想是：用一個棧S"乍為輸入棧，即另一個棧Sz作為輸出棧。當(dāng)入隊列時，總是將數(shù)據(jù)加入到作為輸入的棧（即$）中；在輸出時，如果輸出棧Sz己空，則從輸入棧與將己輸入到輸入棧％中的數(shù)據(jù)輸入到輸出棧8中，然后由輸出棧&輸出數(shù)據(jù)，如果輸出棧S2不空，則就應(yīng)輸出棧S2輸出元素。顯然，當(dāng)輸入棧S,和輸出棧S?均為空時表示隊列為空。4、假定有四個元素A,B,C,D依次進(jìn)棧，進(jìn)棧過程中允許出棧，試寫出所有可能的出棧序列。解答：共有14種可能的出棧序列分別為：ABCD、ABDC,ACBD、ACDB,BACD、ADBC、BADC、BCAD、BCDA、BDCA、CBAD,CBDA,CDBA、DCBA、5、對于一個具有m個單元的循環(huán)隊列，假定隊頭指針和隊尾指針分別為f和r,試寫出求此隊列中元素個數(shù)的計算公式。解答：計算公式可為：一 fr-f(r>f)循環(huán)隊列中的兀素個數(shù)=( 或為+m)%m6、假定用一[m+r-f(r</)個單循環(huán)鏈表來表示隊列(也稱為循環(huán)隊列)，該隊列只設(shè)一個隊尾指針，不設(shè)隊首指針，試編寫下列各種運算的算法：(1)向循環(huán)鏈隊列插入一個元素值為x的結(jié)點；(2)從循環(huán)鏈隊列中刪除一個結(jié)點。解答：顯然本題意即對一個循環(huán)鏈隊列做插入和刪除運算，假設(shè)不需要保留被刪結(jié)點的值和不需要回收結(jié)點，可將算法描述為：(1)插入(即入隊)算法：insert(rear,x)/*設(shè)循環(huán)鏈隊列的隊尾指針為rear,x為待插入的元素*/linklist*rear；datatypex；{linklist*p；p=malloc(sizeof(linklist))； /*建立值為x的新結(jié)點*p*/if(rear==Null){rear=p；rear->next=p； /*鏈接成循環(huán)鏈表*/Ielse{ p->next=rear->next；rear->next=p；rear=p；} /*若條件成立，則建立循環(huán)鏈隊列的第?個結(jié)點，否則在隊尾插入*P結(jié)點*/

}/"insert*/(2)刪除(即出隊)算法：delete(rear)/*刪除(即出隊)算法*/linklist*rear； /*設(shè)循環(huán)鏈隊列的隊尾指針為rear*/{if(rear==Null)printf("underflow\n")；if(rear->next==rear)rear=Null；elserear->next=rear->next->next；/*rear->next指向的結(jié)點為循環(huán)鏈隊列的隊頭結(jié)點*/}/"delete*/7、用標(biāo)志位方式設(shè)計出在循環(huán)隊列中進(jìn)行插入和刪除運算的算法。解答：可引入標(biāo)志位flag,且規(guī)定flag=0 flag=1表示隊列不為空同時，設(shè)front,rear和maxsize分別為隊頭指針，隊尾指針和隊列的長度。另一方面，可規(guī)定隊頭指針指向隊頭元素所在的實際存儲單元的前一個位置，從而可得隊滿條件為：(rear=fronto)&&(flag==1)現(xiàn)給出插入和刪除算法如下：(1)插入(入隊)算法：intequeue(sq,x,flag)/*x插入循環(huán)隊列sq中，sq具有隊頭與隊尾指針*/sequeuesq；datatypex；intflag；{if((flag==l)&&(sq->rear==sq->front))printf("queueisfull\nw)；elseif(Sq->rear==maxsize-1) /*隊滿判斷*/sq->rear=O；elsesq->rear=sq->rear+l；Sq->data[s->rear]=x；/*x入隊*/}if(flag==0)flag=l；}/*equeue*/(2)刪除(出隊)算法：datatypedequeqll(sq)/*刪除隊列sq的頭元素，并返回該元素*/sequeue*sq；{datatypex；if(flag==0)printf(uqueueisempty\nff)；else{sq->front++； /*出隊*/if(sq->front==maxsizeT)sq->front=0；x=sq->data[sq->front]；}if(sq->front=sq->rear)flag=0；returnx；}/*dequeque*/8、假設(shè)以一個一維向量data[0…mansizeT]存放一個循環(huán)隊列中的元素，同時設(shè)變量rear和len分別指示循環(huán)隊列中隊尾元素的位置和內(nèi)含元素的個數(shù)。試寫出此循環(huán)隊列的隊滿條件，并設(shè)計出相應(yīng)的入隊和出隊的算法。解答：假定隊尾指針rear表示隊尾元素實際存放的存儲單元的位置，且設(shè)sq為指向sequeue類型的隊列指針，該類型含域rear和data數(shù)組以及l(fā)en域，從而可將入隊、出隊算法描述如下：(1)入隊算法：intenqueue(sq,x) /*x插入隊列sq中即入隊*/sequeue*sq；datatypex；{if(sq->len==maxsize)printf("overflow\n")；else{sq->rear=(sq->rear+1)%maxsize；sq->data[sq->rear]=x； /*x入隊*/sq->len=sq->len+1；}return(1)；}/"enqueue*/(2)出隊算法：datatypedelqueue(sq)/*刪除隊列*sq的隊頭元素，并返回該元素*/sequeue*sq；{intfront；if(sq->len==0)printf("underflow、/)； /*下溢*/else{front=sq->rear+l-sq->len；if(front<0)front=front+rnaxsize；sq->len ；)return(sq->data[front])；}/*delqueue*/9、內(nèi)存中一片連續(xù)空間(不妨假設(shè)地址從1到m),提供給兩個棧SI、S2使用，怎樣分配這部分空間，使得對任一個棧，僅當(dāng)該部分空間全滿時才發(fā)生溢出？解答：設(shè)定兩個棧的結(jié)構(gòu)如下圖，兩個棧的棧底分別位于連續(xù)空間的兩端，每個棧都向空間內(nèi)部增長，這樣就可以滿足要求。?—?---SP1SP2SP110、指出下述程序段的功能是什么？voidDemol(SeqStack*S){inti;arr[64];n=0;while(StackEmpty(S))arr[n++]=Pop(S);for(i=0,i<n;i++)Push(S,arr[i]);}//Demo1SeqStackSI,S2,tmp;DataTypex;???〃假設(shè)棧tmp和S2已做過初始化while(!StackEmpty(&S1))Ix=Pop(&Sl);Push(&tmp,x);}while(!StackEmpty(&tmp))Ix=Pop(&tmp);Push(&S1,x);Push(&S2,x);)voidDemo2(SeqStack*S,intm){//設(shè)DataType為int型SeqStackT;inti;InitStack(&T);while(!StackEmpty(S))if((i=Pop(S))!=m)Push(&T,i);while(!StackEmpty(&T))i=Pop(&T);Push(S,i);(4)voidDemo3(CirQueue*Q){//設(shè)DataType為int型intx;SeqStackS;InitStack(&S);while(!QueueEmpty(Q)){x=DeQueue(Q);Push(&S,x);}while(!StackEmpty(&s)){x=Pop(&S);EnQueue(Q,x);}}//Demo3(5)CirQueueQI,Q2;//設(shè)DataType為int型intx,i,n=0;...//設(shè)QI已有內(nèi)容，Q2已初始化過while(!QueueEmpty(&Q1)){x=DeQueue(&Q1);EnQueue(&Q2,x);n++;}for(i=0;i<n;i++){x=DeQueue(&Q2);EnQueue(&Q1,x);EnQueue(&Q2,x);}解答：(1)程序段的功能是將一棧中的元素按反序重新排列，也就是原來在棧頂?shù)脑胤诺綏５?，棧底的元素放到棧頂。此棧中元素個數(shù)限制在64個以內(nèi)。(2)程序段的功能是利用tmp棧將一個非空棧si的所有元素按原樣復(fù)制到一個棧s2當(dāng)中去。(3)程序段的功能是利用棧T,將一個非空棧S中值等于m的元素全部刪去。(4)程序段的功能是將?個循環(huán)隊列Q經(jīng)過S棧的處理，反向排列，原來的隊頭變成隊尾，原來的隊尾變成隊頭。(5)這段程序的功能是將隊列1的所有元素復(fù)制到隊列2中去，但其執(zhí)行過程是先把隊列1的元素全部出隊，進(jìn)入隊列2,然后再把隊列2的元素復(fù)制到隊列1中。11、設(shè)計算法判斷一個算術(shù)表達(dá)式的圓括號是否正確配對。(提示：對表達(dá)式進(jìn)行掃描，凡遇到'('就進(jìn)棧，遇')'就退掉棧頂?shù)?('，表達(dá)式被掃描完畢，棧應(yīng)為空。解答：根據(jù)提示，可以設(shè)計算法如下：intPairBracket(char*SR){〃檢查表達(dá)式ST中括號是否配對inti;SeqStackS;〃定義一個棧InitStack(&s);for(i=0;i<strlen(SR);i++)(if(S[i]=='(')Push(&S,SR[i]);〃遇'('時進(jìn)棧if(!StackEmpty(S))〃棧不為空時，將棧頂元素出棧Pop(&s);elsereturn0;〃不匹配，返回0}ifEmptyStack(&s)return1;//匹配，返回1elsereturn0;〃不匹配，返回0}第四章串一、基本內(nèi)容串的數(shù)據(jù)類型定義；串的三種存儲表示：定長順序存儲結(jié)構(gòu)；塊鏈存儲結(jié)構(gòu)和堆分配存儲結(jié)構(gòu)；串的各種基本操作的實現(xiàn)及其應(yīng)用。二、學(xué)習(xí)要點1、熟悉串的七種基本操作的定義，并能利用這些基本操作實現(xiàn)串的其他各種操作的方法。2、熟練掌握在串的定長順序存儲結(jié)構(gòu)上實現(xiàn)串的各種操作的方法。3、掌握串的堆存儲結(jié)構(gòu)以及在其上實現(xiàn)串操作的基本方法。4、了解串操作的應(yīng)用方法和特點。4.1基礎(chǔ)知識一、填空題1,計算機軟件系統(tǒng)中，有兩種表達(dá)字符串長度的方法：一種是采用① ，第二種是?。2、一個字符串相