數(shù)據(jù)結(jié)構(gòu)課后習(xí)題答案

PAGE76PAGE75第1章緒論1．簡述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、抽象數(shù)據(jù)類型。答案：數(shù)據(jù)：是客觀事物的符號表示，指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號的總稱。如數(shù)學(xué)計(jì)算中用到的整數(shù)和實(shí)數(shù)，文本編輯所用到的字符串，多媒體程序處理的圖形、圖像、聲音、動(dòng)畫等通過特殊編碼定義后的數(shù)據(jù)。數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮和處理。在有些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點(diǎn)、記錄等。數(shù)據(jù)元素用于完整地描述一個(gè)對象，如一個(gè)學(xué)生記錄，樹中棋盤的一個(gè)格局（狀態(tài)）、圖中的一個(gè)頂點(diǎn)等。數(shù)據(jù)項(xiàng)：是組成數(shù)據(jù)元素的、有獨(dú)立含義的、不可分割的最小單位。例如，學(xué)生基本信息表中的學(xué)號、姓名、性別等都是數(shù)據(jù)項(xiàng)。數(shù)據(jù)對象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。例如：整數(shù)數(shù)據(jù)對象是集合N={0，±1，±2，…}，字母字符數(shù)據(jù)對象是集合C={‘A’，‘B’，…，‘Z’，‘a(chǎn)’，‘b’，…，‘z’}，學(xué)生基本信息表也可是一個(gè)數(shù)據(jù)對象。數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。換句話說，數(shù)據(jù)結(jié)構(gòu)是帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合，“結(jié)構(gòu)”就是指數(shù)據(jù)元素之間存在的關(guān)系。邏輯結(jié)構(gòu)：從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲(chǔ)無關(guān)，是獨(dú)立于計(jì)算機(jī)的。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學(xué)模型。存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)對象在計(jì)算機(jī)中的存儲(chǔ)表示，也稱為物理結(jié)構(gòu)。抽象數(shù)據(jù)類型：由用戶定義的，表示應(yīng)用問題的數(shù)學(xué)模型，以及定義在這個(gè)模型上的一組操作的總稱。具體包括三部分：數(shù)據(jù)對象、數(shù)據(jù)對象上關(guān)系的集合和對數(shù)據(jù)對象的基本操作的集合。2．試舉一個(gè)數(shù)據(jù)結(jié)構(gòu)的例子，敘述其邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)兩方面的含義和相互關(guān)系。答案：例如有一張學(xué)生基本信息表，包括學(xué)生的學(xué)號、姓名、性別、籍貫、專業(yè)等。每個(gè)學(xué)生基本信息記錄對應(yīng)一個(gè)數(shù)據(jù)元素，學(xué)生記錄按順序號排列，形成了學(xué)生基本信息記錄的線性序列。對于整個(gè)表來說，只有一個(gè)開始結(jié)點(diǎn)(它的前面無記錄)和一個(gè)終端結(jié)點(diǎn)(它的后面無記錄)，其他的結(jié)點(diǎn)則各有一個(gè)也只有一個(gè)直接前趨和直接后繼。學(xué)生記錄之間的這種關(guān)系就確定了學(xué)生表的邏輯結(jié)構(gòu)，即線性結(jié)構(gòu)。這些學(xué)生記錄在計(jì)算機(jī)中的存儲(chǔ)表示就是存儲(chǔ)結(jié)構(gòu)。如果用連續(xù)的存儲(chǔ)單元(如用數(shù)組表示)來存放這些記錄，則稱為順序存儲(chǔ)結(jié)構(gòu)；如果存儲(chǔ)單元不連續(xù)，而是隨機(jī)存放各個(gè)記錄，然后用指針進(jìn)行鏈接，則稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。即相同的邏輯結(jié)構(gòu)，可以對應(yīng)不同的存儲(chǔ)結(jié)構(gòu)。3．簡述邏輯結(jié)構(gòu)的四種基本關(guān)系并畫出它們的關(guān)系圖。答案：（1）集合結(jié)構(gòu)數(shù)據(jù)元素之間除了“屬于同一集合”的關(guān)系外，別無其他關(guān)系。例如，確定一名學(xué)生是否為班級成員，只需將班級看做一個(gè)集合結(jié)構(gòu)。（2）線性結(jié)構(gòu)數(shù)據(jù)元素之間存在一對一的關(guān)系。例如，將學(xué)生信息數(shù)據(jù)按照其入學(xué)報(bào)到的時(shí)間先后順序進(jìn)行排列，將組成一個(gè)線性結(jié)構(gòu)。（3）樹結(jié)構(gòu)數(shù)據(jù)元素之間存在一對多的關(guān)系。例如，在班級的管理體系中，班長管理多個(gè)組長，每位組長管理多名組員，從而構(gòu)成樹形結(jié)構(gòu)。（4）圖結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)數(shù)據(jù)元素之間存在多對多的關(guān)系。例如，多位同學(xué)之間的朋友關(guān)系，任何兩位同學(xué)都可以是朋友，從而構(gòu)成圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。其中樹結(jié)構(gòu)和圖結(jié)構(gòu)都屬于非線性結(jié)構(gòu)。四類基本邏輯結(jié)構(gòu)關(guān)系圖4．存儲(chǔ)結(jié)構(gòu)由哪兩種基本的存儲(chǔ)方法實(shí)現(xiàn)？答案： （1）順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)是借助元素在存儲(chǔ)器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系，通常借助程序設(shè)計(jì)語言的數(shù)組類型來描述。（2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)要求所有的元素依次存放在一片連續(xù)的存儲(chǔ)空間中，而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，無需占用一整塊存儲(chǔ)空間。但為了表示結(jié)點(diǎn)之間的關(guān)系，需要給每個(gè)結(jié)點(diǎn)附加指針字段，用于存放后繼元素的存儲(chǔ)地址。所以鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通常借助于程序設(shè)計(jì)語言的指針類型來描述。5．選擇題（1）在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(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)答案：C（2）與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個(gè)數(shù)無關(guān)的是數(shù)據(jù)的（）。A．存儲(chǔ)結(jié)構(gòu)B．存儲(chǔ)實(shí)現(xiàn)C．邏輯結(jié)構(gòu)D．運(yùn)算實(shí)現(xiàn)答案：C（3）通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著（）。A．?dāng)?shù)據(jù)具有同一特點(diǎn)B．不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對應(yīng)數(shù)據(jù)項(xiàng)的類型要一致C．每個(gè)數(shù)據(jù)元素都一樣D．?dāng)?shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等答案：B（4）以下說法正確的是（）。A．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位B．?dāng)?shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位C．?dāng)?shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項(xiàng)的集合D．一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)答案：D解釋：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位，數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)元素的集合。（5）算法的時(shí)間復(fù)雜度取決于（）。A．問題的規(guī)模 B．待處理數(shù)據(jù)的初態(tài)C．計(jì)算機(jī)的配置 D．A和B答案：D解釋：算法的時(shí)間復(fù)雜度不僅與問題的規(guī)模有關(guān)，還與問題的其他因素有關(guān)。如某些排序的算法，其執(zhí)行時(shí)間與待排序記錄的初始狀態(tài)有關(guān)。為此，有時(shí)會(huì)對算法有最好、最壞以及平均時(shí)間復(fù)雜度的評價(jià)。（6）以下數(shù)據(jù)結(jié)構(gòu)中，（）是非線性數(shù)據(jù)結(jié)構(gòu)A．樹B．字符串C．隊(duì)列D．棧答案：A6．試分析下面各程序段的時(shí)間復(fù)雜度。（1）x=90;y=100;

while(y>0)if(x>100){x=x-10;y--;}elsex++;答案：O(1)解釋：程序的執(zhí)行次數(shù)為常數(shù)階。（2）for(i=0;i<n;i++)for(j=0;j<m;j++)a[i][j]=0;答案：O(m*n)解釋：語句a[i][j]=0;的執(zhí)行次數(shù)為m*n。（3）s=0;fori=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;答案：O(n2)解釋：語句s+=B[i][j];的執(zhí)行次數(shù)為n2。（4）i=1;while(i<=n)i=i*3;答案：O(log3n)解釋：語句i=i*3;的執(zhí)行次數(shù)為

log3n。（5）x=0;for(i=1;i<n;i++)for(j=1;j<=n-i;j++)x++;答案：O(n2)解釋：語句x++;的執(zhí)行次數(shù)為n-1+n-2+……＋1=n(n-1)/2。（6）x=n;//n>1y=0;while(x≥(y+1)*(y+1))y++;答案：O()解釋：語句y++;的執(zhí)行次數(shù)為

。

第2章線性表1．選擇題（1）順序表中第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長度為2，則第5個(gè)元素的地址是（）。A．110B．108C．100D答案：B解釋：順序表中的數(shù)據(jù)連續(xù)存儲(chǔ)，所以第5個(gè)元素的地址為：100+2*4=108。（2）在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O(1)的操作是（）。A．訪問第i個(gè)結(jié)點(diǎn)（1≤i≤n）和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)（2≤i≤n）B．在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（1≤i≤n）C．刪除第i個(gè)結(jié)點(diǎn)（1≤i≤n）D．將n個(gè)結(jié)點(diǎn)從小到大排序答案：A解釋：在順序表中插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度都是O(n2)，排序的時(shí)間復(fù)雜度為O(n2)或O(nlog2n)。順序表是一種隨機(jī)存取結(jié)構(gòu)，訪問第i個(gè)結(jié)點(diǎn)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)都可以直接通過數(shù)組的下標(biāo)直接定位，時(shí)間復(fù)雜度是O(1)。（3）向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來順序不變，平均要移動(dòng)的元素個(gè)數(shù)為（）。A．8B．63.5C．63D答案：B解釋：平均要移動(dòng)的元素個(gè)數(shù)為：n/2。（4）鏈接存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間（）。A．分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針B．只有一部分，存放結(jié)點(diǎn)值C．只有一部分，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針D．分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)答案：A（5）線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（）。A．必須是連續(xù)的B．部分地址必須是連續(xù)的C．一定是不連續(xù)的D．連續(xù)或不連續(xù)都可以答案：D（6）線性表Ｌ在（）情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。A．需經(jīng)常修改Ｌ中的結(jié)點(diǎn)值Ｂ．需不斷對Ｌ進(jìn)行刪除插入C．Ｌ中含有大量的結(jié)點(diǎn)Ｄ．Ｌ中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜答案：B解釋：鏈表最大的優(yōu)點(diǎn)在于插入和刪除時(shí)不需要移動(dòng)數(shù)據(jù)，直接修改指針即可。（7）單鏈表的存儲(chǔ)密度（）。A．大于1B．等于1C．小于1D．答案：C解釋：存儲(chǔ)密度是指一個(gè)結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲(chǔ)空間和整個(gè)結(jié)點(diǎn)所占的存儲(chǔ)空間之比，假設(shè)單鏈表一個(gè)結(jié)點(diǎn)本身所占的空間為D，指針域所占的空間為N，則存儲(chǔ)密度為：D/(D+N)，一定小于1。（8）將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是（）。A．nB．2n-1C．2nD答案：A解釋：當(dāng)?shù)谝粋€(gè)有序表中所有的元素都小于（或大于）第二個(gè)表中的元素，只需要用第二個(gè)表中的第一個(gè)元素依次與第一個(gè)表的元素比較，總計(jì)比較n次。（9）在一個(gè)長度為n的順序表中，在第i個(gè)元素（1≤i≤n+1）之前插入一個(gè)新元素時(shí)須向后移動(dòng)（）個(gè)元素。A．n-iB．n-i+1C．n-i-1答案：B(10)線性表L=(a1，a2,……an)，下列說法正確的是（）。A．每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼B．線性表中至少有一個(gè)元素C．表中諸元素的排列必須是由小到大或由大到小D．除第一個(gè)和最后一個(gè)元素外，其余每個(gè)元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和直接后繼。答案：D(11)創(chuàng)建一個(gè)包括n個(gè)結(jié)點(diǎn)的有序單鏈表的時(shí)間復(fù)雜度是（）。A．O(1)B．O(n)C．O(n2)D．O(nlog2n)答案：C解釋：單鏈表創(chuàng)建的時(shí)間復(fù)雜度是O(n)，而要建立一個(gè)有序的單鏈表，則每生成一個(gè)新結(jié)點(diǎn)時(shí)需要和已有的結(jié)點(diǎn)進(jìn)行比較，確定合適的插入位置，所以時(shí)間復(fù)雜度是O(n2)。(12)以下說法錯(cuò)誤的是（）。 A．求表長、定位這兩種運(yùn)算在采用順序存儲(chǔ)結(jié)構(gòu)時(shí)實(shí)現(xiàn)的效率不比采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)實(shí)現(xiàn)的效率低B．順序存儲(chǔ)的線性表可以隨機(jī)存取C．由于順序存儲(chǔ)要求連續(xù)的存儲(chǔ)區(qū)域，所以在存儲(chǔ)管理上不夠靈活D．線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu) 答案：D解釋：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和順序存儲(chǔ)結(jié)構(gòu)各有優(yōu)缺點(diǎn)，有不同的適用場合。(13)在單鏈表中，要將s所指結(jié)點(diǎn)插入到p所指結(jié)點(diǎn)之后，其語句應(yīng)為（）。A．s->next=p+1;p->next=s;B．(*p).next=s;(*s).next=(*p).next;C．s->next=p->next;p->next=s->next;D．s->next=p->next;p->next=s;答案：D(14)在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)須修改指針（）。A．p->next->prior=p->prior;p->prior->next=p->next;B．p->next=p->next->next;p->next->prior=p;C．p->prior->next=p;p->prior=p->prior->prior;D．p->prior=p->next->next;p->next=p->prior->prior;答案：A(15)在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點(diǎn)后插入q所指向的新結(jié)點(diǎn)，其修改指針的操作是（）。A．p->next=q;q->prior=p;p->next->prior=q;q->next=q;B．p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;C．q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;D．q->prior=p;q->next=p->next;p->next=q;p->next->prior=q;答案：C2．算法設(shè)計(jì)題（1）將兩個(gè)遞增的有序鏈表合并為一個(gè)遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個(gè)鏈表的存儲(chǔ)空間,不另外占用其它的存儲(chǔ)空間。表中不允許有重復(fù)的數(shù)據(jù)。[題目分析]合并后的新表使用頭指針Lc指向，pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)，從第一個(gè)結(jié)點(diǎn)開始進(jìn)行比較，當(dāng)兩個(gè)鏈表La和Lb均為到達(dá)表尾結(jié)點(diǎn)時(shí)，依次摘取其中較小者重新鏈接在Lc表的最后。如果兩個(gè)表中的元素相等，只摘取La表中的元素，刪除Lb表中的元素，這樣確保合并后表中無重復(fù)的元素。當(dāng)一個(gè)表到達(dá)表尾結(jié)點(diǎn)，為空時(shí)，將非空表的剩余元素直接鏈接在Lc表的最后。[算法描述]voidMergeList(LinkList&La,LinkList&Lb,LinkList&Lc){//合并鏈表La和Lb，合并后的新表使用頭指針Lc指向pa=La->next;pb=Lb->next;//pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)Lc=pc=La;//用La的頭結(jié)點(diǎn)作為Lc的頭結(jié)點(diǎn)while(pa&&pb){if(pa->data<pb->data){pc->next=pa;pc=pa;pa=pa->next;}//取較小者La中的元素，將pa鏈接在pc的后面，pa指針后移elseif(pa->data>pb->data){pc->next=pb;pc=pb;pb=pb->next;}//取較小者Lb中的元素，將pb鏈接在pc的后面，pb指針后移else//相等時(shí)取La中的元素，刪除Lb中的元素{pc->next=pa;pc=pa;pa=pa->next;q=pb->next;deletepb;pb=q;}}pc->next=pa?pa:pb;//插入剩余段deleteLb;//釋放Lb的頭結(jié)點(diǎn)}（2）將兩個(gè)非遞減的有序鏈表合并為一個(gè)非遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個(gè)鏈表的存儲(chǔ)空間,不另外占用其它的存儲(chǔ)空間。表中允許有重復(fù)的數(shù)據(jù)。[題目分析]合并后的新表使用頭指針Lc指向，pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)，從第一個(gè)結(jié)點(diǎn)開始進(jìn)行比較，當(dāng)兩個(gè)鏈表La和Lb均為到達(dá)表尾結(jié)點(diǎn)時(shí)，依次摘取其中較小者重新鏈接在Lc表的表頭結(jié)點(diǎn)之后，如果兩個(gè)表中的元素相等，只摘取La表中的元素，保留Lb表中的元素。當(dāng)一個(gè)表到達(dá)表尾結(jié)點(diǎn)，為空時(shí)，將非空表的剩余元素依次摘取，鏈接在Lc表的表頭結(jié)點(diǎn)之后。[算法描述]voidMergeList(LinkList&La,LinkList&Lb,LinkList&Lc,){//合并鏈表La和Lb，合并后的新表使用頭指針Lc指向pa=La->next;pb=Lb->next;//pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)Lc=pc=La;//用La的頭結(jié)點(diǎn)作為Lc的頭結(jié)點(diǎn)Lc->next=NULL;while(pa||pb){//只要存在一個(gè)非空表，用q指向待摘取的元素if(!pa){q=pb;pb=pb->next;}//La表為空，用q指向pb，pb指針后移elseif(!pb){q=pa;pa=pa->next;}//Lb表為空，用q指向pa，pa指針后移elseif(pa->data<=pb->data){q=pa;pa=pa->next;}//取較小者（包括相等）La中的元素，用q指向pa，pa指針后移else{q=pb;pb=pb->next;}//取較小者Lb中的元素，用q指向pb，pb指針后移q->next=Lc->next;Lc->next=q;//將q指向的結(jié)點(diǎn)插在Lc表的表頭結(jié)點(diǎn)之后}deleteLb;//釋放Lb的頭結(jié)點(diǎn)}（3）已知兩個(gè)鏈表A和B分別表示兩個(gè)集合，其元素遞增排列。請?jiān)O(shè)計(jì)算法求出A與B的交集，并存放于A鏈表中。[題目分析]只有同時(shí)出現(xiàn)在兩集合中的元素才出現(xiàn)在結(jié)果表中,合并后的新表使用頭指針Lc指向。pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)，從第一個(gè)結(jié)點(diǎn)開始進(jìn)行比較，當(dāng)兩個(gè)鏈表La和Lb均為到達(dá)表尾結(jié)點(diǎn)時(shí)，如果兩個(gè)表中相等的元素時(shí)，摘取La表中的元素，刪除Lb表中的元素；如果其中一個(gè)表中的元素較小時(shí)，刪除此表中較小的元素，此表的工作指針后移。當(dāng)鏈表La和Lb有一個(gè)到達(dá)表尾結(jié)點(diǎn)，為空時(shí)，依次刪除另一個(gè)非空表中的所有元素。[算法描述]voidMix(LinkList&La,LinkList&Lb,LinkList&Lc){pa=La->next;pb=Lb->next;pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)Lc=pc=La;//用La的頭結(jié)點(diǎn)作為Lc的頭結(jié)點(diǎn)while(pa&&pb){if(pa->data==pb->data)∥交集并入結(jié)果表中。{pc->next=pa;pc=pa;pa=pa->next;u=pb;pb=pb->next;deleteu;}elseif(pa->data<pb->data){u=pa;pa=pa->next;deleteu;}else{u=pb;pb=pb->next;deleteu;}}while(pa){u=pa;pa=pa->next;deleteu;}∥釋放結(jié)點(diǎn)空間while(pb){u=pb;pb=pb->next;deleteu;}∥釋放結(jié)點(diǎn)空間pc->next=null;∥置鏈表尾標(biāo)記。deleteLb;//釋放Lb的頭結(jié)點(diǎn)}（4）已知兩個(gè)鏈表A和B分別表示兩個(gè)集合，其元素遞增排列。請?jiān)O(shè)計(jì)算法求出兩個(gè)集合A和B的差集（即僅由在A中出現(xiàn)而不在B中出現(xiàn)的元素所構(gòu)成的集合），并以同樣的形式存儲(chǔ)，同時(shí)返回該集合的元素個(gè)數(shù)。[題目分析]求兩個(gè)集合A和B的差集是指在A中刪除A和B中共有的元素，即刪除鏈表中的相應(yīng)結(jié)點(diǎn),所以要保存待刪除結(jié)點(diǎn)的前驅(qū)，使用指針pre指向前驅(qū)結(jié)點(diǎn)。pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)，從第一個(gè)結(jié)點(diǎn)開始進(jìn)行比較，當(dāng)兩個(gè)鏈表La和Lb均為到達(dá)表尾結(jié)點(diǎn)時(shí)，如果La表中的元素小于Lb表中的元素，pre置為La表的工作指針pa刪除Lb表中的元素；如果其中一個(gè)表中的元素較小時(shí)，刪除此表中較小的元素，此表的工作指針后移。當(dāng)鏈表La和Lb有一個(gè)為空時(shí)，依次刪除另一個(gè)非空表中的所有元素。[算法描述]voidDifference（LinkList&La,LinkList&Lb,int*n）{∥差集的結(jié)果存儲(chǔ)于單鏈表La中，*n是結(jié)果集合中元素個(gè)數(shù)，調(diào)用時(shí)為0pa=La->next;pb=Lb->next;∥pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)pre=La;∥pre為La中pa所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針while（pa&&pb）{if（pa->data<q->data）{pre=pa;pa=pa->next;*n++;}∥A鏈表中當(dāng)前結(jié)點(diǎn)指針后移elseif（pa->data>q->data）q=q->next;∥B鏈表中當(dāng)前結(jié)點(diǎn)指針后移else{pre->next=pa->next;∥處理A，B中元素值相同的結(jié)點(diǎn)，應(yīng)刪除u=pa;pa=pa->next;deleteu;}∥刪除結(jié)點(diǎn)}}（5）設(shè)計(jì)算法將一個(gè)帶頭結(jié)點(diǎn)的單鏈表A分解為兩個(gè)具有相同結(jié)構(gòu)的鏈表B、C，其中B表的結(jié)點(diǎn)為A表中值小于零的結(jié)點(diǎn)，而C表的結(jié)點(diǎn)為A表中值大于零的結(jié)點(diǎn)（鏈表A中的元素為非零整數(shù)，要求B、C表利用A表的結(jié)點(diǎn)）。[題目分析]B表的頭結(jié)點(diǎn)使用原來A表的頭結(jié)點(diǎn)，為C表新申請一個(gè)頭結(jié)點(diǎn)。從A表的第一個(gè)結(jié)點(diǎn)開始，依次取其每個(gè)結(jié)點(diǎn)p，判斷結(jié)點(diǎn)p的值是否小于0，利用前插法，將小于0的結(jié)點(diǎn)插入B表,大于等于0的結(jié)點(diǎn)插入C表。[算法描述]voidDisCompose(LinkedListA){ B=A;B->next=NULL;∥B表初始化C=newLNode;∥為C申請結(jié)點(diǎn)空間C->next=NULL;∥C初始化為空表p=A->next;∥p為工作指針while(p!=NULL){r=p->next;∥暫存p的后繼if(p->data<0){p->next=B->next;B->next=p;}∥將小于0的結(jié)點(diǎn)鏈入B表,前插法else{p->next=C->next;C->next=p;}∥將大于等于0的結(jié)點(diǎn)鏈入C表,前插法p=r;∥p指向新的待處理結(jié)點(diǎn)。}}（6）設(shè)計(jì)一個(gè)算法，通過一趟遍歷在單鏈表中確定值最大的結(jié)點(diǎn)。[題目分析]假定第一個(gè)結(jié)點(diǎn)中數(shù)據(jù)具有最大值，依次與下一個(gè)元素比較，若其小于下一個(gè)元素，則設(shè)其下一個(gè)元素為最大值，反復(fù)進(jìn)行比較，直到遍歷完該鏈表。[算法描述]ElemTypeMax(LinkListL){ if(L->next==NULL)returnNULL; pmax=L->next;//假定第一個(gè)結(jié)點(diǎn)中數(shù)據(jù)具有最大值 p=L->next->next; while(p!=NULL){//如果下一個(gè)結(jié)點(diǎn)存在 if(p->data>pmax->data)pmax=p;//如果p的值大于pmax的值，則重新賦值 p=p->next;//遍歷鏈表 } returnpmax->data;（7）設(shè)計(jì)一個(gè)算法，通過遍歷一趟，將鏈表中所有結(jié)點(diǎn)的鏈接方向逆轉(zhuǎn)，仍利用原表的存儲(chǔ)空間。[題目分析]從首元結(jié)點(diǎn)開始，逐個(gè)地把鏈表L的當(dāng)前結(jié)點(diǎn)p插入新的鏈表頭部。[算法描述]voidinverse(LinkList&L){//逆置帶頭結(jié)點(diǎn)的單鏈表Lp=L->next;L->next=NULL;while(p){q=p->next;//q指向*p的后繼p->next=L->next;L->next=p;//*p插入在頭結(jié)點(diǎn)之后p=q;}}（8）設(shè)計(jì)一個(gè)算法，刪除遞增有序鏈表中值大于mink且小于maxk的所有元素（mink和maxk是給定的兩個(gè)參數(shù)，其值可以和表中的元素相同，也可以不同）。[題目分析]分別查找第一個(gè)值>mink的結(jié)點(diǎn)和第一個(gè)值≥maxk的結(jié)點(diǎn)，再修改指針，刪除值大于mink且小于maxk的所有元素。[算法描述]voiddelete(LinkList&L,intmink,intmaxk){p=L->next;//首元結(jié)點(diǎn)while(p&&p->data<=mink){pre=p;p=p->next;}//查找第一個(gè)值>mink的結(jié)點(diǎn)if(p){while(p&&p->data<maxk)p=p->next;//查找第一個(gè)值≥maxk的結(jié)點(diǎn)q=pre->next;pre->next=p;//修改指針while(q!=p){s=q->next;deleteq;q=s;}//釋放結(jié)點(diǎn)空間}//if}（9）已知p指向雙向循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，其結(jié)點(diǎn)結(jié)構(gòu)為data、prior、next三個(gè)域，寫出算法change(p),交換p所指向的結(jié)點(diǎn)和它的前綴結(jié)點(diǎn)的順序。[題目分析]知道雙向循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，與前驅(qū)交換涉及到四個(gè)結(jié)點(diǎn)（p結(jié)點(diǎn)，前驅(qū)結(jié)點(diǎn)，前驅(qū)的前驅(qū)結(jié)點(diǎn)，后繼結(jié)點(diǎn)）六條鏈。[算法描述]voidExchange（LinkedListp）∥p是雙向循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，本算法將p所指結(jié)點(diǎn)與其前驅(qū)結(jié)點(diǎn)交換。{q=p->llink；q->llink->rlink=p；∥p的前驅(qū)的前驅(qū)之后繼為pp->llink=q->llink；∥p的前驅(qū)指向其前驅(qū)的前驅(qū)。q->rlink=p->rlink；∥p的前驅(qū)的后繼為p的后繼。q->llink=p；∥p與其前驅(qū)交換p->rlink->llink=q；∥p的后繼的前驅(qū)指向原p的前驅(qū)p->rlink=q；∥p的后繼指向其原來的前驅(qū)}∥算法exchange結(jié)束。（10）已知長度為n的線性表A采用順序存儲(chǔ)結(jié)構(gòu)，請寫一時(shí)間復(fù)雜度為O(n)、空間復(fù)雜度為O(1)的算法，該算法刪除線性表中所有值為item的數(shù)據(jù)元素。[題目分析]在順序存儲(chǔ)的線性表上刪除元素，通常要涉及到一系列元素的移動(dòng)（刪第i個(gè)元素，第i+1至第n個(gè)元素要依次前移）。本題要求刪除線性表中所有值為item的數(shù)據(jù)元素，并未要求元素間的相對位置不變。因此可以考慮設(shè)頭尾兩個(gè)指針（i=1，j=n），從兩端向中間移動(dòng)，凡遇到值item的數(shù)據(jù)元素時(shí)，直接將右端元素左移至值為item的數(shù)據(jù)元素位置。[算法描述]voidDelete（ElemTypeA[]，intn）∥A是有n個(gè)元素的一維數(shù)組，本算法刪除A中所有值為item的元素。{i=1；j=n；∥設(shè)置數(shù)組低、高端指針（下標(biāo)）。while（i<j）{while（i<j&&A[i]!=item）i++；∥若值不為item，左移指針。if（i<j）while（i<j&&A[j]==item）j--；∥若右端元素為item，指針左移if（i<j）A[i++]=A[j--]；}

第3章棧和隊(duì)列1．選擇題（1）若讓元素1，2，3，4，5依次進(jìn)棧，則出棧次序不可能出現(xiàn)在（）種情況。A．5，4，3，2，1B．2，1，5，4，3C．4，3，1，2，5D．2，3，5，4，1答案：C解釋：棧是后進(jìn)先出的線性表，不難發(fā)現(xiàn)C選項(xiàng)中元素1比元素2先出棧，違背了棧的后進(jìn)先出原則，所以不可能出現(xiàn)C選項(xiàng)所示的情況。（2）若已知一個(gè)棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為（）。A．iB．n-iC．n-i+1D．不確定答案：C解釋：棧是后進(jìn)先出的線性表，一個(gè)棧的入棧序列是1，2，3，…，n，而輸出序列的第一個(gè)元素為n，說明1，2，3，…，n一次性全部進(jìn)棧，再進(jìn)行輸出，所以p1=n，p2=n-1，…，pi=n-i+1。（3）數(shù)組Ｑ［ｎ］用來表示一個(gè)循環(huán)隊(duì)列，ｆ為當(dāng)前隊(duì)列頭元素的前一位置，ｒ?yàn)殛?duì)尾元素的位置，假定隊(duì)列中元素的個(gè)數(shù)小于ｎ，計(jì)算隊(duì)列中元素個(gè)數(shù)的公式為（）。A．r-fB．(n+f-r)%nC．n+r-fD．（n+r-f)%n答案：D解釋：對于非循環(huán)隊(duì)列，尾指針和頭指針的差值便是隊(duì)列的長度，而對于循環(huán)隊(duì)列，差值可能為負(fù)數(shù)，所以需要將差值加上MAXSIZE（本題為n），然后與MAXSIZE（本題為n）求余，即（n+r-f)%n。（4）鏈?zhǔn)綏＝Y(jié)點(diǎn)為：(data,link)，top指向棧頂.若想摘除棧頂結(jié)點(diǎn)，并將刪除結(jié)點(diǎn)的值保存到x中,則應(yīng)執(zhí)行操作（）。A．x=top->data;top=top->link； B．top=top->link;x=top->link；C．x=top;top=top->link； D．x=top->link；答案：A解釋：x=top->data將結(jié)點(diǎn)的值保存到x中，top=top->link棧頂指針指向棧頂下一結(jié)點(diǎn)，即摘除棧頂結(jié)點(diǎn)。（5）設(shè)有一個(gè)遞歸算法如下

intfact(intn){

//n大于等于0

if(n<=0)return1;

elsereturnn*fact(n-1);

}則計(jì)算fact(n)需要調(diào)用該函數(shù)的次數(shù)為（）。

A．

n+1

B．

n-1

C．n

D．n+2答案：A解釋：特殊值法。設(shè)n=0，易知僅調(diào)用一次fact(n)函數(shù)，故選A。（6）棧在

（）中有所應(yīng)用。A．遞歸調(diào)用B．函數(shù)調(diào)用C．表達(dá)式求值D．前三個(gè)選項(xiàng)都有答案：D解釋：遞歸調(diào)用、函數(shù)調(diào)用、表達(dá)式求值均用到了棧的后進(jìn)先出性質(zhì)。（7）為解決計(jì)算機(jī)主機(jī)與打印機(jī)間速度不匹配問題，通常設(shè)一個(gè)打印數(shù)據(jù)緩沖區(qū)。主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是（）。A．隊(duì)列B．棧C．線性表D．有序表答案：A解釋：解決緩沖區(qū)問題應(yīng)利用一種先進(jìn)先出的線性表，而隊(duì)列正是一種先進(jìn)先出的線性表。（8）設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次進(jìn)入棧S，一個(gè)元素出棧后即進(jìn)入Q，若6個(gè)元素出隊(duì)的序列是e2、e4、e3、e6、e5和e1，則棧S的容量至少應(yīng)該是（）。A．2B．3C．4D答案：B解釋：元素出隊(duì)的序列是e2、e4、e3、e6、e5和e1，可知元素入隊(duì)的序列是e2、e4、e3、e6、e5和e1，即元素出棧的序列也是e2、e4、e3、e6、e5和e1，而元素e1、e2、e3、e4、e5和e6依次進(jìn)入棧，易知棧S中最多同時(shí)存在3個(gè)元素，故棧S的容量至少為3。（9）若一個(gè)棧以向量V[1..n]存儲(chǔ)，初始棧頂指針top設(shè)為n+1，則元素x進(jìn)棧的正確操作是()。A．top++;V[top]=x; B．V[top]=x;top++;C．top--;V[top]=x; D．V[top]=x;top--;答案：C解釋：初始棧頂指針top為n+1，說明元素從數(shù)組向量的高端地址進(jìn)棧，又因?yàn)樵卮鎯?chǔ)在向量空間V[1..n]中，所以進(jìn)棧時(shí)top指針先下移變?yōu)閚，之后將元素x存儲(chǔ)在V[n]。（10）設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號是否配對出現(xiàn)的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳。A．線性表的順序存儲(chǔ)結(jié)構(gòu)B．隊(duì)列C.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D.棧答案：D解釋：利用棧的后進(jìn)先出原則。（11）用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)（）。A.僅修改頭指針B.僅修改尾指針C.頭、尾指針都要修改D.頭、尾指針可能都要修改答案：D解釋：一般情況下只修改頭指針，但是，當(dāng)刪除的是隊(duì)列中最后一個(gè)元素時(shí)，隊(duì)尾指針也丟失了，因此需對隊(duì)尾指針重新賦值。（12）循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A[0..m]中，則入隊(duì)時(shí)的操作為（）。A.rear=rear+1B.rear=(rear+1)%(m-1)C.rear=(rear+1)%mD.rear=(rear+1)%(m+1)答案：D解釋：數(shù)組A[0..m]中共含有m+1個(gè)元素，故在求模運(yùn)算時(shí)應(yīng)除以m+1。（13）最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear，隊(duì)頭是front，則隊(duì)空的條件是（）。A.(rear+1)%n==frontB.rear==frontC．rear+1==frontD.(rear-l)%n==front答案：B解釋：最大容量為n的循環(huán)隊(duì)列，隊(duì)滿條件是(rear+1)%n==front，隊(duì)空條件是rear==front。（14）棧和隊(duì)列的共同點(diǎn)是（）。A.都是先進(jìn)先出B.都是先進(jìn)后出C.只允許在端點(diǎn)處插入和刪除元素D.沒有共同點(diǎn)答案：C解釋：棧只允許在棧頂處進(jìn)行插入和刪除元素，隊(duì)列只允許在隊(duì)尾插入元素和在隊(duì)頭刪除元素。（15）一個(gè)遞歸算法必須包括（）。A.遞歸部分B.終止條件和遞歸部分C.迭代部分D.終止條件和迭代部分答案：B2．算法設(shè)計(jì)題（1）將編號為0和1的兩個(gè)棧存放于一個(gè)數(shù)組空間V[m]中，棧底分別處于數(shù)組的兩端。當(dāng)?shù)?號棧的棧頂指針top[0]等于-1時(shí)該棧為空，當(dāng)?shù)?號棧的棧頂指針top[1]等于m時(shí)該棧為空。兩個(gè)棧均從兩端向中間增長。試編寫雙棧初始化，判斷棧空、棧滿、進(jìn)棧和出棧等算法的函數(shù)。雙棧數(shù)據(jù)結(jié)構(gòu)的定義如下：Typedefstruct{inttop[2],bot[2]; //棧頂和棧底指針SElemType*V; //棧數(shù)組intm; //棧最大可容納元素個(gè)數(shù)}DblStack[題目分析]兩棧共享向量空間，將兩棧棧底設(shè)在向量兩端，初始時(shí)，左棧頂指針為-1，右棧頂為m。兩棧頂指針相鄰時(shí)為棧滿。兩棧頂相向、迎面增長，棧頂指針指向棧頂元素。[算法描述](1)

棧初始化int

Init()

{S.top[0]=-1;

S.top[1]=m;

return

1;

//初始化成功}(2)

入棧操作：int

push(stkS

,int

i,int

x)∥i為棧號，i=0表示左棧，i=1為右棧，x是入棧元素。入棧成功返回1，失敗返回0{if(i<0||i>1){cout<<“棧號輸入不對”<<endl;exit(0);}if(S.top[1]-S.top[0]==1){cout<<“棧已滿”<<endl;return(0);}switch(i)

{case

0:S.V[++S.top[0]]=x;

return(1);

break;case

1:S.V[--S.top[1]]=x;

return(1);}}∥push(3)

退棧操作ElemTypepop(stkS,int

i)∥退棧。i代表?xiàng)Ｌ枺琲=0時(shí)為左棧，i=1時(shí)為右棧。退棧成功時(shí)返回退棧元素∥否則返回-1{if(i<0||i>1){cout<<“棧號輸入錯(cuò)誤”<<endl；exit(0);}

switch(i){case

0:

if(S.top[0]==-1){cout<<“?？铡?lt;<endl；return（-1）；}else

return(S.V[S.top[0]--]);case

1:

if(S.top[1]==m{cout<<“?？铡?lt;<endl;

return(-1);}else

return(S.V[S.top[1]++]);

}∥switch

}∥算法結(jié)束(4)

判斷?？読nt

Empty();{return

(S.top[0]==-1&&S.top[1]==m);}[算法討論]

請注意算法中兩棧入棧和退棧時(shí)的棧頂指針的計(jì)算。左棧是通常意義下的棧，而右棧入棧操作時(shí)，其棧頂指針左移（減1），退棧時(shí)，棧頂指針右移（加1）。（2）回文是指正讀反讀均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。試寫一個(gè)算法判定給定的字符向量是否為回文。(提示：將一半字符入棧)

[題目分析]將字符串前一半入棧，然后，棧中元素和字符串后一半進(jìn)行比較。即將第一個(gè)出棧元素和后一半串中第一個(gè)字符比較，若相等，則再出棧一個(gè)元素與后一個(gè)字符比較，……，直至棧空，結(jié)論為字符序列是回文。在出棧元素與串中字符比較不等時(shí)，結(jié)論字符序列不是回文。[算法描述]#defineStackSize100//假定預(yù)分配的棧空間最多為100個(gè)元素typedefcharDataType;//假定棧元素的數(shù)據(jù)類型為字符typedefstruct{DataTypedata[StackSize];inttop;}SeqStack;intIsHuiwen(char*t){//判斷t字符向量是否為回文，若是，返回1，否則返回0SeqStacks;inti,len;chartemp;InitStack(&s);len=strlen(t);//求向量長度for(i=0;i<len/2;i++)//將一半字符入棧Push(&s,t[i]);while(!EmptyStack(&s)){//每彈出一個(gè)字符與相應(yīng)字符比較temp=Pop(&s);if(temp!=S[i])

return0;//不等則返回0elsei++;}

return1;//比較完畢均相等則返回1}（3）設(shè)從鍵盤輸入一整數(shù)的序列：a1,a2,a3，…，an，試編寫算法實(shí)現(xiàn)：用棧結(jié)構(gòu)存儲(chǔ)輸入的整數(shù)，當(dāng)ai≠-1時(shí)，將ai進(jìn)棧；當(dāng)ai=-1時(shí)，輸出棧頂整數(shù)并出棧。算法應(yīng)對異常情況（入棧滿等）給出相應(yīng)的信息。[算法描述]#definemaxsize?？臻g容量voidInOutS(ints[maxsize])//s是元素為整數(shù)的棧，本算法進(jìn)行入棧和退棧操作。{inttop=0;//top為棧頂指針，定義top=0時(shí)為棧空。for(i=1;i<=n;i++)//n個(gè)整數(shù)序列作處理。 {cin>>x);//從鍵盤讀入整數(shù)序列。if(x!=-1)//讀入的整數(shù)不等于-1時(shí)入棧。｛if(top==maxsize-1){cout<<“棧滿”<<endl;exit(0);}elses[++top]=x;//x入棧。｝else//讀入的整數(shù)等于-1時(shí)退棧。{if(top==0){cout<<“棧空”<<endl;exit(0);}elsecout<<“出棧元素是”<<s[top--]<<endl;}}}//算法結(jié)束。（4）從鍵盤上輸入一個(gè)后綴表達(dá)式，試編寫算法計(jì)算表達(dá)式的值。規(guī)定：逆波蘭表達(dá)式的長度不超過一行，以$符作為輸入結(jié)束，操作數(shù)之間用空格分隔,操作符只可能有+、-、*、/四種運(yùn)算。例如：23434+2*$。[題目分析]逆波蘭表達(dá)式(即后綴表達(dá)式)求值規(guī)則如下：設(shè)立運(yùn)算數(shù)棧OPND,對表達(dá)式從左到右掃描(讀入)，當(dāng)表達(dá)式中掃描到數(shù)時(shí)，壓入OPND棧。當(dāng)掃描到運(yùn)算符時(shí)，從OPND退出兩個(gè)數(shù)，進(jìn)行相應(yīng)運(yùn)算，結(jié)果再壓入OPND棧。這個(gè)過程一直進(jìn)行到讀出表達(dá)式結(jié)束符$，這時(shí)OPND棧中只有一個(gè)數(shù)，就是結(jié)果。[算法描述]floatexpr()//從鍵盤輸入逆波蘭表達(dá)式，以‘$’表示輸入結(jié)束，本算法求逆波蘭式表達(dá)式的值。｛floatOPND[30];//OPND是操作數(shù)棧。init(OPND);//兩棧初始化。floatnum=0.0;//數(shù)字初始化。cin>>x;//x是字符型變量。while(x!=’$’) {switch{case‘0’<=x<=’9’:while((x>=’0’&&x<=’9’)||x==’.’)//拼數(shù)if(x!=’.’)//處理整數(shù){num=num*10+（ord(x)-ord(‘0’)）;cin>>x;}else//處理小數(shù)部分。{scale=10.0;cin>>x;while(x>=’0’&&x<=’9’){num=num+(ord(x)-ord(‘0’)/scale;scale=scale*10;cin>>x;}}//elsepush(OPND,num);num=0.0;//數(shù)壓入棧，下個(gè)數(shù)初始化casex=‘’:break;//遇空格，繼續(xù)讀下一個(gè)字符。casex=‘+’:push(OPND,pop(OPND)+pop(OPND));break;casex=‘-’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2-x1);break;casex=‘*’:push(OPND,pop(OPND)*pop(OPND));break;casex=‘/’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2/x1);break;default://其它符號不作處理。}//結(jié)束switchcin>>x;//讀入表達(dá)式中下一個(gè)字符。}//結(jié)束while（x！=‘$’）cout<<“后綴表達(dá)式的值為”<<pop(OPND);}//算法結(jié)束。[算法討論]假設(shè)輸入的后綴表達(dá)式是正確的，未作錯(cuò)誤檢查。算法中拼數(shù)部分是核心。若遇到大于等于‘0’且小于等于‘9’的字符，認(rèn)為是數(shù)。這種字符的序號減去字符‘0’的序號得出數(shù)。對于整數(shù)，每讀入一個(gè)數(shù)字字符，前面得到的部分?jǐn)?shù)要乘上10再加新讀入的數(shù)得到新的部分?jǐn)?shù)。當(dāng)讀到小數(shù)點(diǎn)，認(rèn)為數(shù)的整數(shù)部分已完，要接著處理小數(shù)部分。小數(shù)部分的數(shù)要除以10（或10的冪數(shù)）變成十分位，百分位，千分位數(shù)等等，與前面部分?jǐn)?shù)相加。在拼數(shù)過程中，若遇非數(shù)字字符，表示數(shù)已拼完，將數(shù)壓入棧中，并且將變量num恢復(fù)為0，準(zhǔn)備下一個(gè)數(shù)。這時(shí)對新讀入的字符進(jìn)入‘+’、‘-’、‘*’、‘/’及空格的判斷，因此在結(jié)束處理數(shù)字字符的case（5）假設(shè)以I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由I和O組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。=1\*GB3①下面所示的序列中哪些是合法的？A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO=2\*GB3②通過對=1\*GB3①的分析，寫出一個(gè)算法，判定所給的操作序列是否合法。若合法，返回true，否則返回false（假定被判定的操作序列已存入一維數(shù)組中）。答案：=1\*GB3①A和D是合法序列，B和C是非法序列。=2\*GB3②設(shè)被判定的操作序列已存入一維數(shù)組A中。intJudge(charA[])//判斷字符數(shù)組A中的輸入輸出序列是否是合法序列。如是，返回true，否則返回false。{i=0;//i為下標(biāo)。j=k=0;//j和k分別為I和字母O的的個(gè)數(shù)。while(A[i]!=‘\0’)//當(dāng)未到字符數(shù)組尾就作。{switch(A[i]){case‘I’:j++;break;//入棧次數(shù)增1。case‘O’:k++;if(k>j){cout<<“序列非法”<<ednl；exit(0);}}i++;//不論A[i]是‘I’或‘O’，指針i均后移。}if(j!=k){cout<<“序列非法”<<endl；return(false);}else{cout<<“序列合法”<<endl；return(true);}}//算法結(jié)束。[算法討論]在入棧出棧序列（即由‘I’和‘O’組成的字符串）的任一位置，入棧次數(shù)（‘I’的個(gè)數(shù)）都必須大于等于出棧次數(shù)（即‘O’的個(gè)數(shù)），否則視作非法序列，立即給出信息，退出算法。整個(gè)序列（即讀到字符數(shù)組中字符串的結(jié)束標(biāo)記‘\0’(6）假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾元素站點(diǎn)(注意不設(shè)頭指針)，試編寫相應(yīng)的置空隊(duì)、判隊(duì)空、入隊(duì)和出隊(duì)等算法。[題目分析]置空隊(duì)就是建立一個(gè)頭節(jié)點(diǎn)，并把頭尾指針都指向頭節(jié)點(diǎn)，頭節(jié)點(diǎn)是不存放數(shù)據(jù)的；判隊(duì)空就是當(dāng)頭指針等于尾指針時(shí)，隊(duì)空；入隊(duì)時(shí)，將新的節(jié)點(diǎn)插入到鏈隊(duì)列的尾部，同時(shí)將尾指針指向這個(gè)節(jié)點(diǎn)；出隊(duì)時(shí)，刪除的是隊(duì)頭節(jié)點(diǎn)，要注意隊(duì)列的長度大于1還是等于1的情況，這個(gè)時(shí)候要注意尾指針的修改，如果等于1，則要?jiǎng)h除尾指針指向的節(jié)點(diǎn)。[算法描述]//先定義鏈隊(duì)結(jié)構(gòu):typedefstructqueuenode{Datatypedata;structqueuenode*next;}QueueNode;//以上是結(jié)點(diǎn)類型的定義typedefstruct{queuenode*rear;}LinkQueue;//只設(shè)一個(gè)指向隊(duì)尾元素的指針置空隊(duì)voidInitQueue(LinkQueue*Q)

{//置空隊(duì)：就是使頭結(jié)點(diǎn)成為隊(duì)尾元素

QueueNode*s;Q->rear=Q->rear->next;//將隊(duì)尾指針指向頭結(jié)點(diǎn)while(Q->rear!=Q->rear->next)//當(dāng)隊(duì)列非空，將隊(duì)中元素逐個(gè)出隊(duì){s=Q->rear->next;Q->rear->next=s->next;deletes;}//回收結(jié)點(diǎn)空間}判隊(duì)空

intEmptyQueue(LinkQueue*Q){//判隊(duì)空。當(dāng)頭結(jié)點(diǎn)的next指針指向自己時(shí)為空隊(duì)returnQ->rear->next->next==Q->rear->next;}入隊(duì)voidEnQueue(LinkQueue*Q,Datatypex){//入隊(duì)。也就是在尾結(jié)點(diǎn)處插入元素QueueNode*p=newQueueNode;//申請新結(jié)點(diǎn)p->data=x;p->next=Q->rear->next;//初始化新結(jié)點(diǎn)并鏈入Q-rear->next=p;

Q->rear=p;//將尾指針移至新結(jié)點(diǎn)}出隊(duì)DatatypeDeQueue(LinkQueue*Q){//出隊(duì),把頭結(jié)點(diǎn)之后的元素摘下Datatypet;QueueNode*p;if(EmptyQueue(Q))Error("Queueunderflow");p=Q->rear->next->next;//p指向?qū)⒁碌慕Y(jié)點(diǎn)x=p->data;//保存結(jié)點(diǎn)中數(shù)據(jù)if(p==Q->rear){//當(dāng)隊(duì)列中只有一個(gè)結(jié)點(diǎn)時(shí)，p結(jié)點(diǎn)出隊(duì)后，要將隊(duì)尾指針指向頭結(jié)點(diǎn)Q->rear=Q->rear->next;Q->rear->next=p->next;}else

Q->rear->next->next=p->next;//摘下結(jié)點(diǎn)pdeletep;//釋放被刪結(jié)點(diǎn)returnx;}（7）假設(shè)以數(shù)組Q[m]存放循環(huán)隊(duì)列中的元素,同時(shí)設(shè)置一個(gè)標(biāo)志tag，以tag==0和tag==1來區(qū)別在隊(duì)頭指針(front)和隊(duì)尾指針(rear)相等時(shí)，隊(duì)列狀態(tài)為“空”還是“滿”。試編寫與此結(jié)構(gòu)相應(yīng)的插入(enqueue)和刪除(dlqueue)算法。[算法描述](1)初始化SeQueueQueueInit(SeQueueQ){//初始化隊(duì)列Q.front=Q.rear=0;Q.tag=0;return

Q;}(2)入隊(duì)SeQueueQueueIn(SeQueueQ,inte){//入隊(duì)列if((Q.tag==1)&&(Q.rear==Q.front))cout<<"隊(duì)列已滿"<<endl;else

{Q.rear=(Q.rear+1)%m;Q.data[Q.rear]=e;if(Q.tag==0)Q.tag=1;//隊(duì)列已不空}return

Q;}(3)出隊(duì)ElemTypeQueueOut(SeQueueQ){//出隊(duì)列if(Q.tag==0){cout<<"隊(duì)列為空"<<endl;exit(0);}else{Q.front=(Q.front+1)%m;e=Q.data[Q.front];if(Q.front==Q.rear)Q.tag=0;

//空隊(duì)列}return(e);}(8）如果允許在循環(huán)隊(duì)列的兩端都可以進(jìn)行插入和刪除操作。要求：=1\*GB3①寫出循環(huán)隊(duì)列的類型定義；=2\*GB3②寫出“從隊(duì)尾刪除”和“從隊(duì)頭插入”的算法。[題目分析]用一維數(shù)組v[0..M-1]實(shí)現(xiàn)循環(huán)隊(duì)列，其中M是隊(duì)列長度。設(shè)隊(duì)頭指針front和隊(duì)尾指針rear，約定front指向隊(duì)頭元素的前一位置，rear指向隊(duì)尾元素。定義front=rear時(shí)為隊(duì)空，(rear+1)%m=front為隊(duì)滿。約定隊(duì)頭端入隊(duì)向下標(biāo)小的方向發(fā)展，隊(duì)尾端入隊(duì)向下標(biāo)大的方向發(fā)展。[算法描述]=1\*GB3①#defineM隊(duì)列可能達(dá)到的最大長度typedefstruct{elemtpdata[M];intfront,rear;}cycqueue;=2\*GB3②elemtpdelqueue(cycqueueQ)//Q是如上定義的循環(huán)隊(duì)列，本算法實(shí)現(xiàn)從隊(duì)尾刪除，若刪除成功，返回被刪除元素，否則給出出錯(cuò)信息。{if(Q.front==Q.rear){cout<<"隊(duì)列空"<<endl;exit(0);}Q.rear=(Q.rear-1+M)%M;//修改隊(duì)尾指針。return(Q.data[(Q.rear+1+M)%M]);//返回出隊(duì)元素。}//從隊(duì)尾刪除算法結(jié)束voidenqueue(cycqueueQ,elemtpx)//Q是順序存儲(chǔ)的循環(huán)隊(duì)列，本算法實(shí)現(xiàn)“從隊(duì)頭插入”元素x。{if(Q.rear==(Q.front-1+M)%M){cout<<"隊(duì)滿"<<endl;exit(0);)Q.data[Q.front]=x;//x入隊(duì)列Q.front=(Q.front-1+M)%M;//修改隊(duì)頭指針。}//結(jié)束從隊(duì)頭插入算法。（9）已知Ackermann函數(shù)定義如下:=1\*GB3①寫出計(jì)算Ack(m,n)的遞歸算法，并根據(jù)此算法給出出Ack(2,1)的計(jì)算過程。=2\*GB3②寫出計(jì)算Ack(m,n)的非遞歸算法。[算法描述]intAck(intm,n){if(m==0)return(n+1);elseif(m!=0&&n==0)return(Ack(m-1,1));elsereturn(Ack(m-1,Ack(m,m-1));}//算法結(jié)束=1\*GB3①Ack(2,1)的計(jì)算過程Ack(2,1)=Ack(1,Ack(2,0))//因m<>0,n<>0而得 =Ack(1,Ack(1,1))//因m<>0,n=0而得 =Ack(1,Ack(0,Ack(1,0)))//因m<>0,n<>0而得 =Ack(1,Ack(0,Ack(0,1)))//因m<>0,n=0而得 =Ack(1,Ack(0,2))//因m=0而得 =Ack(1,3)//因m=0而得 =Ack(0,Ack(1,2))//因m<>0,n<>0而得 =Ack(0,Ack(0,Ack(1,1)))//因m<>0,n<>0而得 =Ack(0,Ack(0,Ack(0,Ack(1,0))))//因m<>0,n<>0而得 =Ack(0,Ack(0,Ack(0,Ack(0,1))))//因m<>0,n=0而得 =Ack(0,Ack(0,Ack(0,2)))//因m=0而得 =Ack(0,Ack(0,3))//因m=0而得 =Ack(0,4)//因n=0而得 =5//因n=0而得=2\*GB3②intAckerman(intm,intn){intakm[M][N];inti,j;for(j=0;j<N;j++)akm[0][j]=j+1;for(i=1;i<m;i++){akm[i][0]=akm[i-1][1];for(j=1;j<N;j++)akm[i][j]=akm[i-1][akm[i][j-1]];}return(akm[m][n]);}//算法結(jié)束（10）已知f為單鏈表的表頭指針,鏈表中存儲(chǔ)的都是整型數(shù)據(jù)，試寫出實(shí)現(xiàn)下列運(yùn)算的遞歸算法： =1\*GB3①求鏈表中的最大整數(shù)；=2\*GB3②求鏈表的結(jié)點(diǎn)個(gè)數(shù)；=3\*GB3③求所有整數(shù)的平均值。[算法描述]=1\*GB3①intGetMax(LinkListp){ if(!p->next) returnp->data; else { intmax=GetMax(p->next); returnp->data>=max?p->data:max; }}=2\*GB3②intGetLength(LinkListp){ if(!p->next) return1; else { returnGetLength(p->next)+1; }}=3\*GB3③doubleGetAverage(LinkListp,intn){ if(!p->next) returnp->data; else { doubleave=GetAverage(p->next,n-1); return(ave*(n-1)+p->data)/n; }}

第4章串、數(shù)組和廣義表1．選擇題（1）串是一種特殊的線性表，其特殊性體現(xiàn)在（）。A．可以順序存儲(chǔ)B．?dāng)?shù)據(jù)元素是一個(gè)字符C．可以鏈?zhǔn)酱鎯?chǔ)D．?dāng)?shù)據(jù)元素可以是多個(gè)字符若答案：B（2）串下面關(guān)于串的的敘述中，（）是不正確的？A．串是字符的有限序列B．空串是由空格構(gòu)成的串C．模式匹配是串的一種重要運(yùn)算D．串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)答案：B解釋：空格常常是串的字符集合中的一個(gè)元素，有一個(gè)或多個(gè)空格組成的串成為空格串，零個(gè)字符的串成為空串，其長度為零。（3）串“ababaaababaa”的next數(shù)組為（）。A．012345678999B．012121111212C．011234223456D．答案：C（4）串“ababaabab”的nextval為（）。A．010104101B．010102101C．010100011D答案：A（5）串的長度是指（）。A．串中所含不同字母的個(gè)數(shù)B．串中所含字符的個(gè)數(shù)C．串中所含不同字符的個(gè)數(shù)D．串中所含非空格字符的個(gè)數(shù)答案：B解釋：串中字符的數(shù)目稱為串的長度。（6）假設(shè)以行序?yàn)橹餍虼鎯?chǔ)二維數(shù)組A=array[1..100,1..100]，設(shè)每個(gè)數(shù)據(jù)元素占2個(gè)存儲(chǔ)單元，基地址為10，則LOC[5,5]=（）。A．808B．818C．1010D．答案：B解釋：以行序?yàn)橹?，則LOC[5,5]=[（5-1）*100+（5-1）]*2+10=818。（7）設(shè)有數(shù)組A[i,j]，數(shù)組的每個(gè)元素長度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)用以列為主存放時(shí)，元素A[5,8]的存儲(chǔ)首地址為（）。A．BA+141B．BA+180C．BA+222D答案：B解釋：以列序?yàn)橹?，則LOC[5,8]=[（8-1）*8+（5-1）]*3+BA=BA+180。（8）設(shè)有一個(gè)10階的對稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間，則a85的地址為（）。A．13B．32C答案：C（9）若對n階對稱矩陣A以行序?yàn)橹餍蚍绞綄⑵湎氯切蔚脑?包括主對角線上所有元素)依次存放于一維數(shù)組B[1..(n(n+1))/2]中，則在B中確定aij（i<j）的位置k的關(guān)系為（）。A．i*(i-1)/2+jB．j*(j-1)/2+iC．i*(i+1)/2+jD．j*(j+1)/2+i答案：B（10）二維數(shù)組A的每個(gè)元素是由10個(gè)字符組成的串，其行下標(biāo)i=0,1,…,8,列下標(biāo)j=1,2,…,10。若A按行先存儲(chǔ)，元素A[8,5]的起始地址與當(dāng)A按列先存儲(chǔ)時(shí)的元素（）的起始地址相同。設(shè)每個(gè)字符占一個(gè)字節(jié)。A．A[8,5]B．A[3,10]C.A[5,8]D．A[0,9]答案：B解釋：設(shè)數(shù)組從內(nèi)存首地址M開始順序存放，若數(shù)組按行先存儲(chǔ)，元素A[8,5]的起始地址為：M+[（8-0）*10+（5-1）]*1=M+84；若數(shù)組按列先存儲(chǔ)，易計(jì)算出元素A[3,10]的起始地址為：M+[（10-1）*9+（3-0）]*1=M+84。故選B。（11）設(shè)二維數(shù)組A[1..m，1..n]（即m行n列）按行存儲(chǔ)在數(shù)組B[1..m*n]中，則二維數(shù)組元素A[i,j]在一維數(shù)組B中的下標(biāo)為（）。A．(i-1)*n+jB．(i-1)*n+j-1C．i*(j-1)D答案：A解釋：特殊值法。取i=j=1，易知A[1,1]的的下標(biāo)為1，四個(gè)選項(xiàng)中僅有A選項(xiàng)能確定的值為1，故選A。（12）數(shù)組A[0..4,-1..-3,5..7]中含有元素的個(gè)數(shù)（）。A．55B．45C．36答案：B解釋：共有5*3*3=45個(gè)元素。（13）廣義表A=(a,b,(c,d),(e,(f,g)))，則Head(Tail(Head(Tail(Tail(A)))))的值為（）。A．(g)B．(d)C．cD．d答案：D解釋：Tail(A)=(b,(c,d),(e,(f,g)))；Tail(Tail(A))=((c,d),(e,(f,g)))；Head(Tail(Tail(A)))=(c,d)；Tail(Head(Tail(Tail(A))))=(d)；Head(Tail(Head(Tail(Tail(A)))))=d。（14）廣義表((a,b,c,d))的表頭是（），表尾是（）。A．a(chǎn)B．()C．(a,b,c,d)D．(b,c,d)答案：C、B解釋：表頭為非空廣義表的第一個(gè)元素，可以是一個(gè)單原子，也可以是一個(gè)子表，((a,b,c,d))的表頭為一個(gè)子表(a,b,c,d)；表尾為除去表頭之外，由其余元素構(gòu)成的表，表為一定是個(gè)廣義表，((a,b,c,d))的表尾為空表()。（15）設(shè)廣義表L=((a,b,c))，則L的長度和深度分別為（）。A．1和1B．1和3C．1和2D．2和3答案：C解釋：廣義表的深度是指廣義表中展開后所含括號的層數(shù)，廣義表的長度是指廣義表中所含元素的個(gè)數(shù)。根據(jù)定義易知L的長度為1，深度為2。2．應(yīng)用題（1）已知模式串t=‘a(chǎn)bcaabbabcab’寫出用KMP法求得的每個(gè)字符對應(yīng)的next和nextval函數(shù)值。答案：模式串t的next和nextval值如下：j123456789101112t串a(chǎn)bcaabbabcabnext[j]011122312345nextval[j]011021301105（2）設(shè)目標(biāo)為t=“abcaabbabcabaacbacba”,模式為p=“abcabaa”=1\*GB3①計(jì)算模式p的naxtval函數(shù)值；=2\*GB3②不寫出算法,只畫出利用KMP算法進(jìn)行模式匹配時(shí)每一趟的匹配過程。答案：=1\*GB3①p的nextval函數(shù)值為0110132。（p的next函數(shù)值為0111232）。=2\*GB3②利用KMP(改進(jìn)的nextval)算法，每趟匹配過程如下：第一趟匹配：abcaabbabcabaacbacbaabcab(i=5,j=5)第二趟匹配：abcaabbabcabaacbacbaabc(i=7,j=3)第三趟匹配：abcaabbabcabaacbacbaa(i=7,j=1)第四趟匹配：abcaabbabcabaacbacba(成功)abcabaa(i=15,j=8)（3）數(shù)組A中，每個(gè)元素A[i,j]的長度均為32個(gè)二進(jìn)位,行下標(biāo)從-1到9，列下標(biāo)從1到11，從首地址S開始連續(xù)存放主存儲(chǔ)器中，主存儲(chǔ)器字長為16位。求：=1\*GB3①存放該數(shù)組所需多少單元？=2\*GB3②存放數(shù)組第4列所有元素至少需多少單元？=3\*GB3③數(shù)組按行存放時(shí)，元素A[7,4]的起始地址是多少？=4\*GB3④數(shù)組按列存放時(shí)，元素A[4,7]的起始地址是多少？答案：每個(gè)元素32個(gè)二進(jìn)制位，主存字長16位，故每個(gè)元素占2個(gè)字長，行下標(biāo)可平移至1到11。（1）242（2）22（3）s+182（4）s+142(4)請將香蕉banana用工具H()—Head()，T()—Tail()從L中取出。L=(apple,(orange,(strawberry,(banana)),peach),pear)答案：H（H（T（H（T（H（T（L）））））））3．算法設(shè)計(jì)題（1）寫一個(gè)算法統(tǒng)計(jì)在輸入字符串中各個(gè)不同字符出現(xiàn)的頻度并將結(jié)果存入文件（字符串中的合法字符為A-Z這26個(gè)字母和0-9這10個(gè)數(shù)字）。[題目分析]由于字母共26個(gè)，加上數(shù)字符號10個(gè)共36個(gè)，所以設(shè)一長36的整型數(shù)組，前10個(gè)分量存放數(shù)字字符出現(xiàn)的次數(shù)，余下存放字母出現(xiàn)的次數(shù)。從字符串中讀出數(shù)字字符時(shí)，字符的ASCII代碼值減去數(shù)字字符‘0’的ASCII代碼值，得出其數(shù)值(0..9)，字母的ASCII代碼值減去字符‘A’的ASCII代碼值加上10，存入其數(shù)組的對應(yīng)下標(biāo)分量中。遇其它符號不作處理，直至輸入字符串結(jié)束。[算法描述]voidCount（）//統(tǒng)計(jì)輸入字符串中數(shù)字字符和字母字符的個(gè)數(shù)。｛inti，num[36]；charch；for（i＝0；i<36；i++）num[i]＝０；//初始化while（（ch＝getchar（））!=‘#’）//‘#