【正文】 第五節(jié) 樹 (樹根結(jié)點(diǎn)的高度為 1) 一、選擇題 1．以下說法錯(cuò)誤的是 ( )。 答： XSXXXSSSXXSXXSXXSSSS 3．設(shè)有一個(gè)輸入序列 a， b， c， d，元素經(jīng)過一個(gè)棧到達(dá)輸出序列，而且元素一旦離開輸入序列就不能再回到輸入序列，試問經(jīng)過這個(gè)棧后可以得到多少種輸出序列 ? 答：可以得到 14 種輸出序列： abcd,abdc,acbd,acdb,adcb,bacd,bcad,bcda,bdca,cbad,cbda,cdba,dcba,badc. 4．按照運(yùn)算符優(yōu)先法 ，畫出對下面算術(shù)表達(dá)式求值時(shí)，操作數(shù)棧和運(yùn)算符棧的變化過程： 92*4+(8+1)/3。假定用 X 代表掃描該字符串過程中順序取 一個(gè)字符入棧的操作，用 S 代表從棧中取出一個(gè)字符加入到新字符串尾的出棧操作。設(shè)空棧時(shí)，輸入序列 a， b， c 經(jīng)過 push， pop， push， push， pop 操作后，從棧中彈出的元素是 ___c__。用整型變量 t 來指示當(dāng)前棧頂?shù)奈恢茫?A[t]為棧頂元素。 13．設(shè)有一個(gè)空棧，現(xiàn)在輸入序列為 1， 2， 3， 4， 5，經(jīng)過 push， push， pop， push， pop， push 后，棧頂指針?biāo)冈厥?__4__。 ___ ls = ls next __；free(p)。當(dāng) lq． front==lq． rear 時(shí)，隊(duì)中無元素，此時(shí) ___隊(duì)空 __。 14 9．在隊(duì)列中，新插入的結(jié)點(diǎn)只能添加到 __隊(duì)尾 __。 7．棧的邏輯特點(diǎn)是 __后進(jìn)先出 ____，隊(duì)列的邏輯特點(diǎn)是 _先進(jìn)先出 __，二者的共同特點(diǎn)是 _操作受限 __。 r=s。__。 4．假設(shè)以 S 和 X 分別表示入棧和出棧操作，則對輸入序列 a， b， c， d， e 進(jìn)行一系列棧操作 SSXSXSSXXX之后，得到的輸出序列為 __ b， c， e， d， a ___。 2．從棧頂指針為 Top 的鏈棧中刪除一個(gè)結(jié)點(diǎn)，并將結(jié)點(diǎn)保存在 x 中，進(jìn)行的操作是 _ x=Topdata； Top=Topnext； __。 ╳ 9．若以鏈表作為棧的存儲結(jié)構(gòu)，則入棧需要判斷棧是否滿． √ 10．若以鏈表作為棧的存儲結(jié)構(gòu)，則出棧需要判斷棧是否空。 ╳ 6．循環(huán)隊(duì)列中元素個(gè)數(shù)為 rearfront。 √ 4．在鏈隊(duì) 中，即使不設(shè)置尾指針也能進(jìn)行入隊(duì)操作。 ╳ 2．與順序棧相比，鏈棧的一個(gè)優(yōu)點(diǎn)是插入和刪除操作更加方便。 A． 4， 3， 2， 1 *B． 1， 2， 3， 4 C． 1， 4， 3， 2 D． 3， 2， 4， 1 19．設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號是否配對出現(xiàn)的算法，采用 ( )數(shù)據(jù)結(jié)構(gòu)最佳。 A． fnext=s； f=s； *B． rnext=s； r=s； C． snext=r； r=s； D． snext=f； f=s； 17．一個(gè)棧的入棧序列是 a， b， c， d， e，則棧的不可能的輸出序列是 ( )。 A． Topnext=s； B． snext=Topnext； Topnext=s； *C． snext=Top； Top=s； D． snext=Top； Top=Topnext； 15．從棧頂指針為 Top 的鏈棧中刪除一個(gè)結(jié)點(diǎn)，并將被刪結(jié)點(diǎn)的值保存到 x 中，其操作步驟為 ( )。 A． (sq． rear+1)％ maxsize==(sq． front+1)％ maxsize； B． (sq． rear+1)％ maxsize==sq． front+1； C． (sq． rear+1)％ maxsize==sq． front； *D． sq． rear==sq． front； 13．如果以鏈表作為棧的存儲結(jié)構(gòu)，則出棧操作時(shí) ( )。 *A． sq． front=(sq． front+1)％ maxsize； B． sq． front=sq． front+1； C． sq． rear=(sq． rear+1)％ maxsize； D． sq． rear=sq． rear+l； 11．循環(huán)隊(duì)列的隊(duì)滿條件為 ( )。 A． sq． front=(sq． front+1)％ maxsize； *B． sq． front=sq． front+1； C． sq． rear=(sq． rear+1)％ maxsize； D． sq． rear=sq． rear+1。 =(+1)％ maxslze； 8．循環(huán)隊(duì)列的入隊(duì)操作應(yīng)為 ( 初值為 1 )。 B． []=x； =+1； C． =(+1)％ maxsize； [+1]=x。 *A．因鏈棧本身沒有容量限制，故在用戶內(nèi)存空間的范圍內(nèi)不會出現(xiàn)棧滿情況 B．因順序棧本身沒有容量限制，故在用戶內(nèi)存空間的范圍內(nèi)不會出現(xiàn)棧滿情況 C．對于鏈棧而言，在棧滿狀態(tài)下，如果再進(jìn)行 入棧操作，則會發(fā)生“上溢” D．對于順序棧而言，在棧滿狀態(tài)下，如果再進(jìn)行入棧操作，則會發(fā)生“下溢” 7．順序隊(duì)列的入隊(duì)操作應(yīng)為 ( 初值為 1 )。 *A．通常不會出現(xiàn)棧滿的情況 B．通常不會出現(xiàn)?？盏那闆r C．插入操作更容易實(shí)現(xiàn) D．刪除操作更容易實(shí)現(xiàn) 5．若一個(gè)棧的輸入序列是 1， 2， 3， 4，?， n，輸出序列的第一個(gè)元素是 n，則第 i 個(gè)輸出元素是 ( )。以下序列中不可能出現(xiàn)的出棧序列是 ( )。 A． 2 *B． 3 C． 5 D． 6 2．若一個(gè)棧的輸入序列是 a、 b、 c，則通過入棧、出棧操作可能得到 a、 b、 c 的不同排列個(gè)數(shù)為 ( )。／／將計(jì)滿 k 值的數(shù)字輸出，并將其位置標(biāo)為 0 表明已刪除 } } void Js2(LinkedList last， int N， int K) {／／以不帶頭結(jié)點(diǎn)的、已知尾指針的單循環(huán)鏈表為存儲結(jié)構(gòu) p=last； q=pnext； ／／此時(shí) q 為頭結(jié)點(diǎn) fp 為 q 的前驅(qū) while(N0) {for(j=2； j=K； j++) ／／循環(huán) K1 次 {p=q； q=pnext； } printf(” %d”， qdata)； N； pnext=qnext。i++)A[I]=1； ／／用 1 標(biāo)志在環(huán)上的結(jié)點(diǎn) j=0； for(i=0； iN。分別以數(shù)組和以不帶頭結(jié)點(diǎn)的、已知尾指針的單循環(huán)鏈表為存儲結(jié)構(gòu)解決上述問題。 } 20．約瑟夫環(huán)問題：任給正整數(shù) n、 k，按下述方法可得排列 1， 2，?， n 的一個(gè)置換：將數(shù)字 l， 2，?， n 環(huán)形排列，按順時(shí)針方向從 1 開始計(jì)數(shù)；計(jì) 滿 k時(shí)輸出該位置上的數(shù)字 (并從環(huán)中刪去該數(shù)字 )，然后從下一個(gè)數(shù)字開始繼續(xù)計(jì)數(shù)，直到環(huán)中所有數(shù)字均被輸出為止。amp。 答：分析：對所有指數(shù)相同的項(xiàng)，將其對應(yīng)系數(shù)相加，若和不為 0，則構(gòu)造新“和多項(xiàng)式”的結(jié)點(diǎn)；將所有指數(shù)不同的項(xiàng)復(fù)制到和多項(xiàng)式中。n， amp。n， amp。p1freqtempfreq； p2=p1， pl=p2next)；／／插入 if(p1==NULL) {p2next=temp； tempprior=p2； tempnext=NULL； } else {p2next=temp； tempprior=p2； tempnext=pl； p1prior=temp； } } } 18．給出用單鏈表存儲多項(xiàng)式的結(jié)構(gòu)，并編寫一個(gè)按指數(shù)值遞增次序輸入所產(chǎn)生的多項(xiàng)式鏈表的過程。 typedef struct DLNode {int data， freq； struct DLNode *prior， *next； }DLNode， *DLinkedList； void LocateNode(DLinkedList head， int x) {／／雙鏈表按訪問頻度域 freq 遞減次序排列 p2=head； p1=p2— next； ／／ p2 在前， p1 在后 while(p1) ／／查找單鏈表中值為 x 的結(jié)點(diǎn) if(pl— data==x) {pl— freq++； break； }／／使值為 x 的結(jié)點(diǎn)的 freq 加 1 else {p2=pl； p1=p2— next； } 11 if(p1==NULL) printf(” Not found.＼ n” )； else{if(p1— next==NULL) {p2— next=p1— next； temp=p1； } ／／在鏈表中找 temp 所指向的結(jié)點(diǎn)，按 freq 值遞減應(yīng)插入的位置 else{p2— next=p1— next； ／／插入鏈表中間的某一位置 p1— nextprior=p2； temp=pl； } for(p2=head， p1=p2next； plamp。試寫一符合上述要求的 LocateNode 操作的算法。 答： typedef struct Node {DataType data； struct Node *prior， *next； }DLNode， *DLinkedList； void DLchange(DLinkedList p) {／／將雙循環(huán)鏈表中 p 指向的結(jié)點(diǎn)與其右邊的一個(gè)結(jié)點(diǎn)進(jìn)行交換 q=p— next； ／／ q 指向 p 的后繼 p— prior— next=q； q— prior=p— prior； ／／將 p 的前驅(qū)與 q 相鏈接 p— next=q— next； p— prior=q； ／／將 p 插入到 q 之后 qnext— prior=p； q— next=p； } 17．設(shè)有一個(gè)雙鏈表，每個(gè)結(jié)點(diǎn)中除有 prior、 data 和 next 三個(gè)域外，還有一個(gè)可訪問頻度域 freq，在鏈表啟用之前，其初始值均為 0。amp。amp。 答：分析：在雙循環(huán)鏈表中插入和刪除結(jié)點(diǎn)要注意修改雙向的指針。 (1)在值為 x 的結(jié)點(diǎn)之前插入值為 y 的結(jié)點(diǎn)。Adata[i]==same。Adata[i]same) Adata[m++]=Adata[i++]；／／需保留的元素移動(dòng)到新位置 10 while(iA1engthamp。 else {same=[j]； ／／找到了相同元素 same while([j]==same) j++； while([k]==same) k++； ／ j、 k 后移到新的元素 while(iAlengthamp。amp。amp。 答：分析：先從 B 和 C 中找出共有元素，記為 same，再在 A 中從當(dāng)前位置開始，凡小于 same 的元素均保留 (存到新的位置 )，等于 same 的就跳過，到大于 same時(shí)就再找下一個(gè) Same SeqList IntersectDelete(SeqList *A， SeqList B， SeqList C) {／／對順序表 A 刪去那些既在 B 表中出現(xiàn)又在 C 表中出現(xiàn)的元素 i=0； j=0； k=0； m=0。(p— data=’ 0’ ) ／／鏈接到數(shù)字鏈表的頭部 {p— next=pb— next； pb— next=p； } else{pnext=pcnext； pcnext=p； }／／鏈接到其他字母鏈表的頭部 p=q； } } 1己知 A、 B 和 C 為三個(gè)遞增有序的線性表 ，現(xiàn)要求對 A 表進(jìn)行如下操作：刪去那些既在 B 表中出現(xiàn)又在 C 表中出現(xiàn)的元素。p— data=’ a’ ) ／／鏈接到字母鏈表的頭部 {p— next=pa— next； pa— next=p； } else if (p— data=’ 9’ amp。 ／／ q 記下 L 中下一個(gè)結(jié)點(diǎn)的位置 if(p— data=’ z’ amp。再把 q 的值給 p，處理下一個(gè)結(jié)點(diǎn)。 答：分析： p 指向待處理的單鏈表的首元結(jié)點(diǎn)，構(gòu)造三個(gè)空的單循環(huán)鏈表，分別存儲三類字符，其中一個(gè)表可使用原來的單鏈表。 void DeletePre(Linkedlist *s) {／／刪除單循環(huán)鏈表中結(jié)點(diǎn) s 的直接前驅(qū) p=s； while(p— next— next!=s) p=p— next； ／／找到 s 的前驅(qū)的前驅(qū) p q=p— next； ／／ q 是 p 的后繼，即 s 的前驅(qū) p— next=s； ／／將 q 刪除 free(q)； } 12．計(jì)算帶頭結(jié)點(diǎn)的循環(huán)鏈表的結(jié)點(diǎn)個(gè)數(shù)。 s 為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫算法刪除結(jié)點(diǎn) *s 的直接前驅(qū)結(jié)點(diǎn)。amp。 答：分析：用三個(gè)變量