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