數(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ù)類型的定義、表示和實(shí)現(xiàn)方法、描述算法的類c語言、算法設(shè)計(jì)的基本要求。二、學(xué)習(xí)要點(diǎn)1、熟悉各名詞、術(shù)語的含義，掌握基本概念，特別是數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)之間的關(guān)系。分清哪些是邏輯結(jié)構(gòu)的性質(zhì)，哪些是存儲結(jié)構(gòu)的性質(zhì)。2、了解抽象數(shù)據(jù)類型的定義、表示和實(shí)現(xiàn)方法。3、熟悉類C語言的書寫規(guī)范，特別要注意值調(diào)用和引用調(diào)用的區(qū)別，輸入、輸出的方式以及錯(cuò)誤處理方式。4,理解算法五個(gè)要素的確切含義。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、一個(gè)數(shù)據(jù)結(jié)構(gòu)用二元組表示時(shí)，它包括Q集合D和D上的集合S。4、一個(gè)算法應(yīng)具有①，②，③，④和⑤這五個(gè)特性。5、在圖形結(jié)構(gòu)中，每個(gè)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)可以有Q個(gè)。6、一個(gè)抽象數(shù)據(jù)類型用三元組（D,S,P）表示時(shí)，D是①，S是②，P是③。7、數(shù)據(jù)元素在計(jì)算機(jī)中的映象是①。8、算法的設(shè)計(jì)取決于①，算法的實(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）隊(duì)列（B）有向圖（C）樹 （D）哈夫曼樹解答：一、填空題1、①線性②集合③樹④圖或網(wǎng)⑤非線性結(jié)構(gòu)⑥順序存儲⑦鏈?zhǔn)酱鎯?、①1：1②1：n③m：n3、①數(shù)據(jù)元素②關(guān)系4、①有窮性②確定性③可行性④輸入⑤輸出5、①多個(gè)6、①數(shù)據(jù)對象②D上的關(guān)系集合③對D的基本操作集合7、①元素或結(jié)點(diǎn)8、①數(shù)據(jù)（邏輯）結(jié)構(gòu)②采用的存儲結(jié)構(gòu)二、選擇題1、A2、B3、C4、B5、B6、A1.2應(yīng)用知識1、什么是算法？算法的特性是什么？算法設(shè)計(jì)的要求是什么？解答：（略）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>}畫出這個(gè)數(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>}畫出這個(gè)數(shù)據(jù)結(jié)構(gòu)的圖示，并確定其類型。解答：該結(jié)構(gòu)的圖示如下，該結(jié)構(gòu)為樹形結(jié)構(gòu)。4、影響高級語言程序運(yùn)行消耗時(shí)間的因素有哪些？解答：主要有以下因素：(1)算法選用的策略；(2)問題的規(guī)模；(3)書寫程序的語言；(4)編譯程序產(chǎn)生的機(jī)器代碼質(zhì)量；(5)機(jī)器執(zhí)行指令的速度。5、選擇解決某種問題的最佳數(shù)據(jù)結(jié)構(gòu)的標(biāo)準(zhǔn)是什么？解答：一般有兩條標(biāo)準(zhǔn)：(1)所需的存儲空間量；(2)算法所需要的時(shí)間；而算法所需要的時(shí)間又包括以下幾點(diǎn)：(D程序運(yùn)行時(shí)所需要的數(shù)據(jù)總量；(2)源程序進(jìn)行編譯所需要的時(shí)間；(3)計(jì)算機(jī)執(zhí)行每條指令所需要的時(shí)間；(4)程序中的指令重復(fù)執(zhí)行的次數(shù)，而本條正是討論算法中的重點(diǎn)內(nèi)容。6、設(shè)三個(gè)函數(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í)行時(shí)間表示為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的值時(shí)退出循環(huán)。由(y+l)*(y+l)<n得：y<n"0.5-1所以，該程序段的執(zhí)行時(shí)間為：向下取整(n"0.5-1)(5)為T(n)=0(l)8、算法的時(shí)間復(fù)雜度僅與問題的規(guī)模相關(guān)嗎？解答：算法的時(shí)間復(fù)雜度不僅與問題的規(guī)模相關(guān)，還與輸入實(shí)例中的初始狀態(tài)有關(guān)。但在最壞的情況下，其時(shí)間復(fù)雜度就是只與求解問題的規(guī)模相關(guān)的。我們在討論時(shí)間復(fù)雜度時(shí)，一

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

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

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

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

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

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

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