【正文】 答： 序號(hào) 運(yùn)算符棧 操作數(shù)棧 輸入字符 1 9 2 9 3 9 2 4 92 * 5 * 92 4 6 * 924 + 7 98 8 1 9 + 1 ( 10 +( 1 8 11 +( 18 + 12 +(+ 18 1 13 +(+ 181 ) 14 + 19 / 15 +/ 19 3 16 +/ 193 17 + 13 18 4 5．鏈棧中為何不設(shè)置頭結(jié)點(diǎn) ? 答：因?yàn)殒湕Ｖ辉阪湵眍^插入和刪除結(jié)點(diǎn)，不可能在鏈表中間插入或刪除結(jié)點(diǎn)，算法實(shí)現(xiàn)很簡(jiǎn)單，所以一般不設(shè)置頭結(jié)點(diǎn)。 四、應(yīng)用題 2．設(shè)有字符串為 3*ya/y^2，試?yán)脳?xiě)出將其轉(zhuǎn)換為 3y*ay2^/的操作過(guò)程。 14．設(shè)用一維數(shù)組 A[n]來(lái)表示一個(gè)棧，令 A[0]為棧底。 11．設(shè)一個(gè)鏈棧的棧頂指針為 ls，棧中結(jié)點(diǎn)的格式為 data:next，?？盏臈l件是 _ ls = NULL__；如果棧不為空，則出棧操作為 p=ls。 8． ___棧 ___可以作為實(shí)現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。 6．在一個(gè)鏈隊(duì)中，如果 f、 r 分別為隊(duì)頭、隊(duì)尾指針，則插入 s 所指結(jié)點(diǎn)的操作是 _rnext=s。 3．在具有 n 個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有 ___n1_個(gè)元素。 ╳ 7．一個(gè)棧的輸入序列是 1,2,3,4，則在棧的輸出序列中可以得到 4,3,1,2． √ 8．一個(gè)棧的輸入序列是 1,2,3,4，則在棧的輸出序列中可以得到 1,2,3,4。 ╳ 3．若一個(gè)棧的輸入序列為 1， 2， 3，?， n，其輸出序列的第一個(gè)元素為 n，則其輸出序列的每個(gè)元素 ai 一定滿足 ai=i+1(i=1， 2，?， n)。 A． e， d， c， b， a B． d， e， c， b， a *C． d， c， e， a， b D． a， b， c， d， e 18．一個(gè)隊(duì)列的入隊(duì)序列是 1， 2， 3， 4，則隊(duì)列可能的輸出序列是 ( )。 A．必須判別棧是否滿 B．判別棧元素的類型 *C．必須判別棧是否空 D．對(duì)棧不做任何判別 14，向一個(gè)棧頂指針為 Top 的鏈棧中插入一個(gè) s 所指結(jié)點(diǎn)時(shí)，其操作步驟為 ( )。 10．循環(huán)隊(duì)列的出隊(duì)操作為 (sq. front 初值為 1 )。 D． []=x； =x。 A．不確定 B． ni *C． ni+1 D． ni1 6．以下說(shuō)法正確的是 ( )。 A． 4 *B． 5 C． 6 D． 7 3．設(shè)有一順序棧已經(jīng)含有 3 個(gè)元素，如圖 31 所示，元素 a4 正等待入棧。 i++) {s=0； while(sK) {j=(j%N)+1； s=s+A[j1]； } ／／計(jì)數(shù) printf(” %d”， j)； A[j1]=0。例如， n= k=3 時(shí)，輸出的置換是 3， 6，9， 2， 7， 1， 8， 5， 10。 Plink add(PLink pa， PLink pb) {／／多項(xiàng) 式相加 p=pa； q=pb； pc=(PLink)malloc(sizeof(struct PNode))； r=pc； while(p!=NULLamp。m)； while(n!=0) ／／若 n=0 則退出循環(huán) {s=(Plink)malloc(sizeof(struct PNode))； scoef=n； sexp=m； rnext=s； r=s；／／把 s 鏈接到 r 的后面 printf(”輸入系數(shù)和指數(shù) :” )； scanf(amp。amp。每當(dāng)鏈表進(jìn)行一次LocateNode(L， x)操作時(shí) 令元素值為 x 的結(jié)點(diǎn)中 freq 域的值加 l，并調(diào)整表中結(jié)點(diǎn)的次序，使其按訪問(wèn)頻度的遞減次序排列，以便使頻繁訪問(wèn)的結(jié)點(diǎn)總是靠近表頭。pdata!=x) p=pnext； ／／在鏈表中查找值為 x 的結(jié)點(diǎn) if(pdata==x) ／／找到值為 x 的結(jié)點(diǎn) {q=pprior； ／／ q 指向值為 x 的結(jié)點(diǎn)的前驅(qū) s=(DLinkedList)malloc(sizeof(DLNode))； sdata=y； snext=p； sprior=q； ／／將 y 插入到 q 與 p 指向的結(jié)點(diǎn)之間 pprior=s； qnext=s； } else{printf(”沒(méi)有值為 x 的結(jié)點(diǎn)” )； exit(0)； } } void DLDelete(DLinkedList L， int x) {／／在雙循環(huán)鏈表中刪除結(jié)點(diǎn) p=Lnext； while(p!=Lamp。 (2)刪除值為 x 的結(jié)點(diǎn)。amp。k) {if([j][k]) j++； else if([j][k]) k++。 ／／ i 指示 A 中元素原來(lái)的位置， m 為移動(dòng)后的位置 while(iAlengthamp。amp。 void change(LinkedList *L， LinkedList *pa， LinkedList *pb， LinkedList *pc) {／／分解含有三類字符的單鏈表為三個(gè)以循環(huán)鏈表表 示的線性表，使其分別含有三類字符 p=L— next； pa=L； pa— next=pa； ／／分別構(gòu)造三個(gè)單循環(huán)鏈表 pb=(LinkedList*)malloc(sizeof(LinkedList))； pc=(LinkedList*)malloc(sizeof(LinkedList))； pb— next=pb； pc— next=pc； while(p!=L) {q=p— next； 答： int number(Linkedlist *head) {／／計(jì)算單循環(huán)鏈表中結(jié)點(diǎn)的個(gè)數(shù) p=head— next； i=0； while(p!=head) {i++； p=pnext； } return i； } 13．已知由單鏈表表示的線性表中，含有三類字符的數(shù)據(jù)元素 (如：字母字符、數(shù)字字符和其他字符 )，試編寫(xiě)算法構(gòu)造三個(gè)以循環(huán)鏈表表示的 線性表，使得每個(gè)表中只含有同一類的字符，且利用原表中的結(jié)點(diǎn)空間作為這三個(gè)表的結(jié)點(diǎn)空間，頭結(jié)點(diǎn)可另辟空間。(j=)) {if([i]==[j]) ／／找到值相同的元素 {Cdata[k]=[i]； ／／相同元素寫(xiě)入 C 表中 k++； i++； j++； } else if([i][j]) i++；／／ A、 B 表當(dāng)前元素不等，值較小的下標(biāo)增 1 else j++； } Clength=k； return C； } 9 11．假設(shè)在長(zhǎng)度大于 1 的 單循環(huán)鏈表中，既無(wú)頭結(jié)點(diǎn)也無(wú)頭指針。用順序表實(shí)現(xiàn)并寫(xiě)出 C 的算法。 void depose(LinkedList *A， LinkedList *B) {／／單鏈表 A 分解成元素序號(hào)為奇數(shù)的單鏈表 A 和元素序號(hào)為偶數(shù)的單鏈表 B p=Anext； B=(LinkedList*)malloc(sizeof(LinkedList))； r=B； while(p!=NULLamp。 答： LinkedList delete(LinkedList *L， int min， int max) {／／刪除遞減有序單鏈表 L 中值大于 min 且小于 max 的結(jié)點(diǎn) q=L； if(minmax) {printf(” minmax＼ n” )； exit(0)； } else p=L— next； ／／ q 始終指向 p 的前驅(qū) while(p— data=max) ／／當(dāng)前元素大于或等于 max，則 p、 q 依次向后移動(dòng) {q=p； p=p— next； } while((p!=NULL)amp。klen) {q=q— next； k++； } ／／查找 la 表中第 i+len1 個(gè)結(jié)點(diǎn) if(!q) exit(0)； if(pre==la) la=q— next； ／／ i=1 的情況 else pre— next=q— next； ／／完成刪除 ／／將從 la 中刪除的結(jié)點(diǎn)插入到 lb 中 if(j==1) {qnext=lb； lb=p； } ／／ j=1 時(shí) 8 else { r=lb。amp。 6．設(shè)指針 la 和 lb 分別指向兩個(gè)不帶頭結(jié)點(diǎn)的單鏈表的首結(jié)點(diǎn)，設(shè)計(jì)從表 la 中刪除第 i 個(gè)元素起共 len 個(gè)元素，并將這些元素插入到 lb 中第 j 個(gè)結(jié)點(diǎn)之前的算法。k++； } ／／ B 表長(zhǎng)度大于 A 表 else for(t=i； tm； t++) {Cdata[k]=[t]； k++； } ／／ A 表長(zhǎng)度大于 B 表 Clength=m+n； return C。 SeqList *Seqmerge(SeqList A， SeqList B， SeqList *C){／／有序順序表 A 和 B 歸并成有序順序表 C i=0； j=0； k=0； ／／ i， i， k 分別為順序表 A， B， C 的下標(biāo) while(imamp。ji1) ／／找到第 i1 個(gè)元素 {p=p— next； j++； } if(i=0||p==NULL) printf(”插入位置不正確＼ n” )； else {q=(LinkedList*)malloc(sizeof(LinkedList))； q— data=x； 7 if(i==1) {q— next=L； L=q； } ／／在第一個(gè)元素之前插入 else{q— next=p— next； p— next=q； } ／／在其他位置插入 } } 5．設(shè) A、 B 是兩個(gè)線性表，其表中元素遞增有序，長(zhǎng)度分別為 m 和 n。 答：分析：對(duì)不帶頭結(jié)點(diǎn)的鏈表操作時(shí)，要注意對(duì)第一個(gè)結(jié)點(diǎn)和其他結(jié)點(diǎn)操作的不同。 答：分析：此問(wèn)題的關(guān)鍵是在鏈表中找到 x 的插入位置，因此需要兩個(gè)指針一前一后地依次向后移動(dòng)。 while((i=Llength1)amp。 } } (2)鏈表的就地逆置 分析：本算法的思想是逐個(gè)地把 L 的當(dāng)前元素 r 插入到新的鏈表頭部。 答： (1)順序表的就地逆置 分析：分別用兩個(gè)整型變量指向順序表的兩端，同時(shí)向中間移動(dòng)，移動(dòng)的同時(shí)互換兩個(gè)下標(biāo)指示的元素的值。 int length } SeqList。 8．若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入、刪除操作，但要求以最快的方式存取線性表的元素，應(yīng)該用哪種存儲(chǔ)結(jié)構(gòu)？為什么？ 答：應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)。 7．如果有 n 個(gè)線性表同時(shí)共存，并且在處理過(guò)程中各表的長(zhǎng)度會(huì)發(fā)生動(dòng)態(tài)變化，線性表的總長(zhǎng)度也會(huì)自動(dòng)地改變。amp。但若設(shè)置的是頭指針，表尾進(jìn)行插入或刪除操作，需要遍歷整個(gè)鏈表，時(shí)間復(fù)雜度為 O(n)。對(duì)于頻繁進(jìn)行插入和刪除操作的線性表，宜采用鏈表作為存儲(chǔ)結(jié)構(gòu)。為了操作方便，通常在鏈表的首元結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)。 16．在單鏈表中，若 p 和 s 是兩個(gè)指針，且滿足 pnext 與 s相同，則語(yǔ)句 pnext=snext的作用是 _刪除 __s 指向的結(jié)點(diǎn)。 12．在一個(gè)長(zhǎng)度為 n 的向量中刪除第 i(1≤ i≤ n)個(gè)元素時(shí)，需向前移動(dòng) __ ni __個(gè)元素。 8．對(duì)于一個(gè)具有 n 個(gè)結(jié)點(diǎn)的單鏈表，在 p 所指結(jié)點(diǎn)后插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為 __O(1)__，在給定值為 x 的結(jié)點(diǎn)后插入新結(jié)點(diǎn)的時(shí)間復(fù)雜度為 __ O(n)__。 4．線性表的邏輯結(jié)構(gòu)是 __線性 _結(jié)構(gòu)，其所含結(jié)點(diǎn)的個(gè)數(shù)稱為線性表的 ___長(zhǎng)度 _。 a1 稱為 _第一個(gè) _結(jié)點(diǎn)， an 稱為 __最后一個(gè) _結(jié)點(diǎn)， i 稱為 ai 在線性表中的 _位置 __。 √ 8．在線性表的順 序存儲(chǔ)結(jié)構(gòu)中，插入和刪除元素時(shí)，移動(dòng)元素的個(gè)數(shù)與該元素的位置有關(guān)。 ╳ 4．在線性表的順序存儲(chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上不一定相鄰。 A．不再需要頭指針了 B．已知某個(gè)結(jié)點(diǎn)的位置后，容易找到它的直接前驅(qū) C．在進(jìn)行插入、刪除操作時(shí)，能更好地保證鏈表不斷開(kāi) *D．從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表 20．在線性表的下列存儲(chǔ)結(jié)構(gòu)中，讀取元素花費(fèi)時(shí)間最少的是 ( )。 A． p=rear； rear=rearnext； free(p) B． rear=rearnext； free(rear)； C． rear=rearnextnext； free(rear)；