7、(3)n+1, n(n+1), n2,(n+1)n2, n3
(4)100, 1000
6.???? 有實現(xiàn)同一功能的兩個算法A1和A2，其中A1的時間復雜度為Tl=O(2n)，A2的時間復雜度為T2=O(n2)，僅就時間復雜度而言，請具體分析這兩個算法哪一個好。
【解答】對算法A1和A2的時間復雜度T1和T2取對數(shù)，得nlog2和2logn。顯然，當n<4時，算法A1好于A2；當n=4時，兩個算法時間復雜度相同；當n>4時，算法A2好于A1。
7.???? 選擇題：算法分析的目的是（ ）
A、找出數(shù)據(jù)結構的合理性 B、研究算法中的輸入和輸出的關系
C、分析算
8、法的效率以求改進 D、分析算法的易懂性和文檔特點
【解答】C
二、算法設計題
8.???? 已知輸入x，y，z三個不相等的整數(shù)，設計一個“高效”算法，使得這三個數(shù)按從小到大輸出。“高效”的含義是用最少的元素比較次數(shù)、元素移動次數(shù)和輸出次數(shù)。
void Best()
{//按序輸出三個整數(shù)的優(yōu)化算法
int a,b,c,t;
scanf(“%d%d%d”,&a,&b,&c);
if(a>b)
{t=a; a=b; b=t:} //a和b已正序
if(b>c)
{t=c; c=b; //c已到位
if(a>
9、t) {b=a; a=t;} //a和b已正序
else b=t;
}
printf(“%d,%d,%d\n”,a,b,c);
//最佳2次比較，無移動；最差3次比較，7個賦值
}
9.???? 在數(shù)組A[n]中查找值為k的元素，若找到則輸出其位置i(1≤i≤n)，否則輸出0作為標志。設計算法求解此問題，并分析在最壞情況下的時間復雜度。
【題目分析】從后向前查找，若找到與k值相同的元素則返回其位置，否則返回0。
int Search(ElemType A[n+1], ElemType k)
{i=n;
wile(i>=1)&&(A[i]!=k)) i-
10、-;
if(i>=1) return i;
else return 0;
}
當查找不成功時，總的比較次數(shù)為n+1次，所以最壞情況下時間復雜度為O(n)。
第2章 線性表
?
一、基礎知識題
2.1 試述頭指針、頭結點、元素結點、首元結點的區(qū)別，說明頭指針和頭結點的作
【解答】指向鏈表第一個結點（或為頭結點或為首元結點）的指針稱為頭指針?！邦^指針”具有標識一個鏈表的作用，所以經(jīng)常用頭指針代表鏈表的名字，如鏈表L既是指鏈表的名字是L，也是指鏈表的第一個結點的地址存儲在指針變量L中，頭指針為“NULL”則表示一個空表。
有時，我們在整個線性鏈表的第一個
11、元素結點之前加入一個結點，稱為頭結點，它的數(shù)據(jù)域可以不存儲任何信息（也可以做監(jiān)視哨或存放線性表的長度等附加信息），指針域中存放的是第一個數(shù)據(jù)結點的地址，空表時為空。 “頭結點”的加入，使插入和刪除等操作方便統(tǒng)一。
元素結點即是數(shù)據(jù)結點，至少包括元素自身信息和其后繼元素的地址兩個域。
首元結點是指鏈表中第一個數(shù)據(jù)元素的結點；為了操作方便，通常在鏈表的首元結點之前附設一個結點，稱為頭結點。
?
2.2分析順序存儲結構和鏈式存儲結構的優(yōu)缺點，說明何時應該利用何種結構。
【解答】①從空間上來看，當線性表的長度變化較大，難以估計其規(guī)模時，選用動態(tài)的鏈表作為存儲結構比較合適，但鏈表除了需要設置數(shù)
12、據(jù)域外，還要額外設置指針域，因此當線性表長度變化不大，易于事先確定規(guī)模時，為了節(jié)約存儲空間，宜采用順序存儲結構。
②從時間上看，順序表具有按元素序號隨機訪問的特點，在順序表中按序號訪問數(shù)據(jù)元素的時間復雜度為O(1)；而鏈表中按序號訪問的時間復雜度為O(n)。所以如果經(jīng)常按序號訪問數(shù)據(jù)元素，使用順序表優(yōu)于鏈表。
在順序表中做插入刪除操作時，平均移動大約表中一半的元素，因此n較大時順序表的插入和刪除效率低。在鏈表中作插入、刪除，雖然也要找插入位置，但操作主要是比較操作。從這個角度考慮顯然鏈表優(yōu)于順序表。
總之，兩種存儲結構各有長短，選擇那一種存儲結構，由實際問題中的主要因素決定。
?
2
13、.3 分析在順序存儲結構下插入和刪除結點時平均需要移動多少個結點。
【解答】平均移動表中大約一半的結點，插入操作平均移動 個結點，刪除操作平均移動 個結點。具體移動的次數(shù)取決于表長和插入、刪除的結點的位置。
?
2.4 為什么在單循環(huán)鏈表中常使用尾指針，若只設頭指針，插入元素的時間復雜度如何？
【解答】單循環(huán)鏈表中無論設置尾指針還是頭指針都可以遍歷表中任一個結點。設置尾指針時，若在表尾進行插入元素或刪除第一元素，操作可在O(1)時間內(nèi)完成；若只設置頭指針，表尾進行插入或刪除操作，需要遍歷整個鏈表，時間復雜度為O(n)。
?
2.5 在單鏈表、雙鏈表、單循環(huán)鏈表中，若知道指針p指向某
14、結點，能否刪除該結點，時間復雜度如何？
【解答：】以上三種鏈表中，若知道指針p指向某結點，都能刪除該結點。雙鏈表刪除p所指向的結點的時間復雜度為O(1)，而單鏈表和單循環(huán)鏈表上刪除p所指向的結點的時間復雜度均為O(n)。
?
2.6 下面算法的功能是什么？
LinkedList Unknown(LinkedList la)
{LNode *q，*p;
if(la && la->next)
{q=la; la=la->next; p=la;
while(p->next) p=p->next;
p->nex
15、t=q; q->next=null;
}
return la;
}
【解答】將首元結點刪除并插入到表尾（設鏈表長度大于1）。
?
2.7 選擇題：在循環(huán)雙鏈表的*p結點之后插入*s結點的操作是（ ）
la、p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;
B、p->next=s; p->next->prior=s; s->prior=p; s->next=p->next;
lc、s->prior=p; s->next=p-
16、>next; p->next:=s; p->next->prior=s;
D、s->prior=p; s>next=p>next; p>next->prior =s; p->next=s;
【解答】D
?
2.8 選擇題：若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（ ）存儲方式最節(jié)省時間。
la．順序表 B．雙鏈表 lc．帶頭結點的雙循環(huán)鏈表 D．單循環(huán)鏈表
【解答】la
?
二、算法設計題
2.9 設ha和hb分別是兩個帶頭結點的非遞減有序單鏈表的頭指針，試設計算法， 將這兩個有序鏈表
17、合并成一個非遞增有序的單鏈表。要求使用原鏈表空間，表中無重復數(shù)據(jù)。
【題目分析】因為兩鏈表已按元素值非遞減次序排列，將其合并時，均從第一個結點起進行比較，將小的鏈入鏈表中，同時后移鏈表工作指針，若遇值相同的元素，則刪除之。該問題要求結果鏈表按元素值非遞增次序排列，故在合并的同時，將鏈表結點逆置。
LinkedList Union(LinkedList ha,hb)
∥ha,hb分別是帶頭結點的兩個單鏈表的頭指針，鏈表中的元素值按遞增序排列
∥本算法將兩鏈表合并成一個按元素值遞減次序排列的單鏈表,并刪除重復元素
{ pa=ha->next; ∥pa是鏈表ha的工作指針
18、pb=hb->next; ∥pb是鏈表hb的工作指針
ha->next=null; ∥ha作結果鏈表的頭指針，先將結果鏈表初始化為空
while(pa!=null && pb!=null) ∥當兩鏈表均不為空時作
{while(pa->next && pa->data==pa->next->data)
{u=pa->next; pa->next=u->next; free(u)}∥刪除pa鏈表中的重復元素
while(pb->next && pb->data==pb->next->data)
{u=pb->
19、next; pb->next=u->next; free(u)}∥刪除pb鏈表中的重復元素
if(pa->datadata)
{r=pa->next; ∥將pa 的后繼結點暫存于r
pa->next=ha->next; ∥將pa結點鏈于結果表中，同時逆置
ha->next=pa;
pa=r; ∥恢復pa為當前待比較結點
}
else if(pb->datadata)
{r=pb->next; ∥ 將pb
20、的后繼結點暫存于r
pb->next=ha->next; ∥將pb結點鏈于結果表中，同時逆置
ha->next=pb;
pb=r; ∥恢復pb為當前待比較結點
}
else{u=pb;pb=pb->next;free(u)}∥刪除鏈表pb和pa中的重復元素
}// while(pa!=null && pb!=null)
if(pa) pb=pa; ∥避免再對pa寫下面的while語句
while(pb!=null) ∥將尚未到尾的表逆置
21、到結果表中
{r=pb->next; pb->next=ha->next; ha->next=pb; pb=r; }
return ha
}∥算法Union結束
?
2.10????????????? 設la是一個雙向循環(huán)鏈表，其表中元素遞增有序。試寫一算法插入元素x，使表中元素依然遞增有序。
【問題分析】雙向鏈表的插入與單鏈表類似，但需修改雙向指針。
DLinkedList DInsert(DLinkedList la, ElemType x)
∥在遞增有序的雙向循環(huán)鏈表la中插入元素x，使表
22、中元素依然遞增有序
{p=la->next; ∥p指向第一元素
la->data=MaxElemType;∥MaxElemType是和x同類型的機器最大值，用做監(jiān)視哨
while(p->datanext?;
s=(DLNode *)malloc(sizeof(DLNode));∥申請結點空間
s->data=x;
s->prior=p->prior; s->next=p; ∥將插入結點鏈入鏈表
p->prior->next=s;
23、p->prior=s;
}
2.11????????????? 設p指向頭指針為la的單鏈表中某結點，試編寫算法，刪除結點*p的直接前驅結點。
【題目分析】設*p是單鏈表中某結點，刪除結點*p的直接前驅結點，要找到*p的前驅結點的前驅*pre。進行如下操作：u=pre->next; pre->next=u->next;free(u);
LinkedList LinkedListDel(LinkedList la，LNode *p)
{∥刪除單鏈表la上的結點*p的直接前驅結點,假定*p存在
pre=la;
if(pre-next==p)
printf(“*p
24、是鏈表第一結點，無前驅\n”)?; exit(0)?; }
while(pre->next->next !=p)
pre=pre->next;
u=pre->next; pre->next=u->next; free(u);
return(la);
}
2.12????????????? 設計一算法，將一個用循環(huán)鏈表表示的稀疏多項式分解成兩個多項式，使這兩個多項式各自僅有奇次冪或偶次冪項，并要求利用原鏈表中的結點空間來構造這兩個鏈表。
【題目分析】設循環(huán)鏈表表示的多項式的結點結構為：
typede
25、f struct node
{int power; ∥冪
float coef; ∥系數(shù)
ElemType other; ∥其他信息
struct node *next; ∥指向后繼的指針
}PNode,*PolyLinkedList;
則可以從第一個結點開始，根據(jù)結點的冪是奇數(shù)或偶數(shù)而將其插入到奇次冪或偶次冪項的鏈表中。假定用原鏈表保存偶次冪，要為奇次冪的鏈表生成一個表頭，為了保持鏈表中結點的原來順序，用一個指針指向奇次冪鏈表的表尾，注意鏈
26、表分解時不能“斷鏈”。
void PolyDis(PolyLinkedList poly)
∥將poly表示的多項式鏈表分解為各含奇次冪或偶次冪項的兩個循環(huán)鏈表
{PolyLinkedList poly2=(PolyLinkedList)malloc(sizeof(PNode));
∥poly2表示只含奇次冪的多項式
r2=poly2; ∥r2是只含奇次冪的多項式鏈表的尾指針
r1=poly; ∥r1是只含偶次冪的多項式鏈表當前結點的前驅結點的指針
p=poly->next; ∥鏈表帶頭結點，p
27、指向第一個元素
while(p!=poly)
if(p->power % 2)∥處理奇次冪
{r=p->next; ∥暫存后繼
r2->next=p; ∥結點鏈入奇次冪鏈表
r2=p; ∥尾指針后移
p=r; ∥恢復當前待處理結點
}
else ∥處理偶次冪
{r1->next=p; r1=p; p=p->next;}
}
r->next=poly2; r1->next=poly; ∥構成循環(huán)鏈表
}∥PolyDis
?
2.13??????
28、??????? 以帶頭結點的雙向鏈表表示的線性表L=(a1，a2，…，an)，試寫一時間復雜度為O(n)的算法，將L改造為L=(a1，a3，…，an，…，a4，a2)。
【題目分析】分析結果鏈表，易見鏈表中位置是奇數(shù)的結點保持原順序，而位置是偶數(shù)的結點移到奇數(shù)結點之后，且以與原來相反的順序存放。因此，可從鏈表第一個結點開始處理，位置是奇數(shù)的結點保留不動，位置是偶數(shù)的結點插入到鏈表尾部，并用一指針指向鏈表尾，以便對偶數(shù)結點“尾插入”。
DLinkedList DInvert(DLinkedList L)
∥將雙向循環(huán)鏈表L位置是偶數(shù)的結點逆置插入到鏈表尾部
29、{p=L->next; ∥p指向第一元素
Q=p->prior; ∥Q指向最后一個元素
pre=L?; ∥pre指向鏈表中位置為奇數(shù)的結點的前驅
r=L?; ∥r指向鏈表中偶數(shù)結點的尾結點
i=0?; ∥i記錄結點序號
while(p?!= Q) ∥尋找插入位置
{i++?;
if(i%2) ∥處理序號為奇數(shù)的結點
{p->prior=pre?;pre->next=p?;pre=p; p=p->next;}
e
30、lse ∥處理序號為偶數(shù)的結點
{u=p?; ∥記住當前結點
p=p->next?;∥p指向下個待處理結點
u->prior=r->prior;?∥以下4個語句將結點插入鏈表尾
u->next=r;
r->prior->next=u;
r->prior=u;
r=u; ∥指向新的表尾
}
}
2.14????????????? 設單向鏈表的頭指針為head，試設計算法，將鏈表按遞增的順序就地排序。
【題目分析】本題中的“就地排序”，可理解為不另辟空間，這里利用直接插入原則把鏈表
31、整理成遞增有序鏈表。
LinkedList LinkListInsertSort(LinkedList head)
∥head是帶頭結點的單鏈表，本算法利用直接插入原則將鏈表整理成遞增的有序鏈表
{if(head->next!=null) ∥鏈表不為空表
{p=head->next->next; ∥p指向第一結點的后繼
head->next->next=null;
∥直接插入原則認為第一元素有序，然后從第二元素起依次插入
while(p!=null)
{r=p->next; ∥暫存p的后繼
q=head;
while(
32、q->next && q->next->datadata)
q=q->next;∥查找插入位置
p->next=q->next; ∥將p結點鏈入鏈表
q->next=p;
p=r;
}
} }
?
2.15????????????? 已知遞增有序的三個單鏈表分別代表集合A，B和C，設計算法實現(xiàn)A=A∪（B∩C），并使結果鏈表仍保持遞增。要求算法的時間復雜度為O(|A|+|B|+|C|)。其中，|A|為集合A的元素個數(shù)。
【題目分析】本題首先求B和C的交集，即求B和C中共有元素，再與A求并集，同時刪除重復元素，以保持結果A遞增。
Linked
33、List union(LinkedList A,B,C)
∥A、B和C均是帶頭結點的遞增有序的單鏈表,本算法實現(xiàn)A=A∪(B∩C)
∥使結果表A保持遞增有序
{pa=A->next;pb=B->next;pc=C->next;∥設置三個工作指針
pre=A; ∥pre指向結果鏈表中當前待合并結點的前驅
A->data=MaxElemType;∥同類型元素最大值，起監(jiān)視哨作用
while(pa || pb && pc)
{while(pb && pc)
if(pb->datadata) pb=pb->next;
else if(pb->d
34、ata>pc->data) pc=pc->next;
else break; ∥B表和C表有公共元素
if(pb && pc)
{while(pa && pa->datadata)∥先將A中小于B，C公共元素部分鏈入
{pre->next=pa;pre=pa;pa=pa->next;}
if(pre->data!=pb->data)
{pre->next=pb;pre=pb;pb=pb->next;pc=pc->next;}
else{pb=pb->next;pc=pc->next;
35、}
∥ 若A中已有B，C公共元素，則不再存入結果表
}
}∥ while(pa||pb&&pc)
if(pa) pre->next=pa;
else pre->next=null; ∥當B，C無公共元素，將A中剩余鏈入
}∥算法Union結束
2.16????????????? 順序表la與lb非遞減有序，順序表空間足夠大。試設計一種高效算法，將lb中元素合到la中，使新的la的元素仍保持非遞減有序。高效指最大限度地避免移動元素。
【題目分析】順序存儲結構的線性表的插入，其時間復雜度為O(n)，平均移動近一半的元素。線性表la和lb合并時，
36、若從第一個元素開始，一定會造成元素后移，這不符合本題“高效算法”的要求。應從線性表的最后一個元素開始比較，大者放到最終位置上。設兩線性表的長度各為m和n ，則結果表的最后一個元素應在m+n位置上。這樣從后向前，直到第一個元素為止。
SeqList Union(SeqList la, SeqList lb)
∥la和lb是順序存儲的非遞減有序線性表，本算法將lb合并到la中，元素仍非遞減有序
{ m=la.last;n=lb.last;∥m，n分別為線性表la和lb的長度
k=m+n-1; ∥k為結果線性表的工作指針（下標）
i=
37、m-1;j=n-1; ∥i，j分別為線性表la和lb的工作指針（下標）
while(i>=0 && j>=0)
if(la.data[i]>=lb.data[j]) la.data[k--]=la.data[i--];
else la.data[k--]=lb.data[j--];
while(j>=0) la.data[k--]=lb.data[j--];
la.last=m+n;
return la;
}
【算法討論】算法中數(shù)據(jù)移動是主要操作。在最佳情況下（lb的最小元
38、素大于la的最大元素），僅將lb的n個元素移（拷貝）到la中，時間復雜度為O（n），最差情況，la的所有元素都要移動，時間復雜度為O（m+n）。因數(shù)據(jù)合并到la中，所以在退出第一個while循環(huán)后，只需要一個while循環(huán)，處理lb中剩余元素。第二個循環(huán)只有在lb有剩余元素時才執(zhí)行，而在la有剩余元素時不執(zhí)行。本算法 “最大限度的避免移動元素”，是“一種高效算法”。
?
2.17????????????? 已知非空線性鏈表由head指出，試寫一算法，將鏈表中數(shù)據(jù)域值最小的那個結點移到鏈表的最前面。要求：不得額外申請新的鏈結點。
【題目分析】 本題要求將鏈表中數(shù)據(jù)域值最小的結點移到鏈表的最
39、前面。首先要查找最小值結點。將其移到鏈表最前面，實質(zhì)上是將該結點從鏈表上摘下（不是刪除并回收空間），再插入到鏈表的最前面。
LinkedList Delinsert(LinkedList head）
∥本算法將非空線性鏈表head中數(shù)據(jù)域值最小的那個結點移到鏈表的最前面
{p=head->next；∥p是鏈表的工作指針
pre=head； ∥pre指向鏈表中數(shù)據(jù)域最小值結點的前驅
q=p； ∥q指向數(shù)據(jù)域最小值結點，初始假定是第一結點
while （p->next）
{if（p->next->datadata）{pre=p；q=p->next
40、；} ∥找到新的最小值結點
p=p->next；
}
if(q!=head->next) ∥若最小值是第一元素結點，則不需再操作
{pre->next=q->next； ∥將最小值結點從鏈表上摘下
q->next=head->next； ∥將q結點插到鏈表最前面
head->next=q；
}
}∥Delinsert
?
2.18 設la是帶頭結點的非循環(huán)雙向鏈表的指針，其結點中除有prior，data和next外，還有一訪問頻度域freq，其值在鏈表初始使用時為0。當在鏈表中進行ListLocate(la，x)運算時，若查找失敗，
41、則在表尾插入值為x的結點；若查找成功，值為x的結點的freq值增1，并要求鏈表按freq域值非增（遞減）的順序排列，且最近訪問的結點排在頻度相同的結點的后面，使頻繁訪問的結點總是靠近表頭。試編寫符合上述要求的ListLocate(la，x)運算的算法，返回找到結點的指針。
【題目分析】首先在雙向鏈表中查找數(shù)據(jù)值為x的結點，查到后，將結點從鏈表上摘下，然后再順結點的前驅鏈查找該結點的位置。
DLinkList ListLocate(DLinkedList L，ElemType x)
∥ L是帶頭結點的按訪問頻度遞減的雙向鏈表,本算法先查找數(shù)據(jù)x
∥查找成功時結點的訪問頻度域
42、增1，最后將該結點按頻度遞減插入鏈表中
{DLinkList p=L->next,q; ∥p為L表的工作指針，q為p的前驅，用于查找插入位置
while(p && p->data!=x) p=p->next;∥ 查找值為x的結點
if(!p) {printf(“不存在所查結點\n”); exit(0);}
else { p->freq++; ∥ 令元素值為x的結點的freq域加1
p->next->prior=p->prior; ∥ 將p結點從鏈表上摘下
p->prior->next=p->next;
43、
q=p->prior; ∥ 以下查找p結點的插入位置
while(q !=L && q->freqfreq) q=q->prior;
p->next=q->next; q->next->prior=p;∥ 將p結點插入
p->prior=q; q->next=p；
}
return(p); ∥返回值為x的結點的指針
} ∥ 算法結束
?
2.19????????????? 三個帶頭結點的線性鏈表la、lb和lc中的結點均依元素值自小至大非遞減排列（可能存在
44、兩個以上值相同的結點），編寫算法對la表進行如下操作：使操作后的la中僅留下三個表中均包含的數(shù)據(jù)元素的結點，且沒有值相同的結點，并釋放所有無用結點。限定算法的時間復雜度為O（m+n+p），其中m、n和p分別為三個表的長度。
【題目分析】 留下三個鏈表中公共數(shù)據(jù)，首先查找兩表la和B中公共數(shù)據(jù)，再去lc中找有無該數(shù)據(jù)。要消除重復元素，應記住前驅，要求時間復雜度O（m+n+p），在查找每個鏈表時，指針不能回溯。
LinkedList lcommon（LinkedList la，lb，lc）
∥本算法使la表留下la、lb和lc三個非遞減有序表共同結點，無重復元素
{pa=la->next；
45、pb=lb->next；pc=lc->next；
∥pa,pb和pc分別是la,lb和lc三個表的工作指針
pre=la；
la->data=MaxElemType ∥pre是la表當前結點的前驅結點的指針,頭結點作監(jiān)視哨
while（pa && pb && pc） ∥當la,lb和lc表均不空時，查找三表共同元素
{while(pa&&pa->data==pre->data)
{u=pa; pa=pa->next; free(u);}//刪la中相同元素
while（pb && pc）
if（pb->datadata）pb=pb->nex
46、t; ∥結點元素值小時，后移指針
else if（pb->data>pc->data）pc=pc->next；
else break ;∥處理lb和lc表元素值相等的結點
if(pb && pc)
{while（pa && pa->datadata）{u=pa；pa=pa->next；free（u）；}
if(pa && pa->data>pc->data){pb=pb->next; pc=pc->next;}
else if(pa && pa->data==pc->data)∥pc，pa和p
47、b對應結點元素值相等
{pre->next=pa；pre=pa；pa=pa->next；∥將新結點鏈入la表
pb=pb->next；pc=pc->next； ∥鏈表的工作指針后移
}∥pc，pa和pb對應結點元素值相等
} }∥while（pa && pb && pc）
pre->next=null； ∥置新la表表尾
while（pa!=null） ∥刪除原la表剩余元素。
{u=pa；pa=pa->next；free（u）；}
}∥算法結束
【算法
48、討論】 算法中l(wèi)a表、lb表和lc表均從頭到尾（嚴格說lb、lc中最多一個到尾）遍歷一遍，算法時間復雜度符合O（m+n+p）。算法主要由while（pa && pb && pc）控制。三表有一個到尾則結束循環(huán)。要注意頭結點的監(jiān)視哨的作用，否則第一個結點要特殊處理。算法最后要給新la表置結尾標記，同時若原la表沒到尾，還應釋放剩余結點所占的存儲空間。
第3章???????????????????? 棧和隊列
一、基礎知識題
3.1? 有五個數(shù)依次進棧：1，2，3，4，5。在各種出棧的序列中，以3，4先出的序列有哪幾個。（３在４之前出棧）。
【解答】34215 ，34
49、251， 34521
?
3.2? 鐵路進行列車調(diào)度時，常把站臺設計成棧式結構，若進站的六輛列車順序為：1，2，3，4，5，6， 那么是否能夠得到435612， 325641， 154623和135426的出站序列，如果不能，說明為什么不能； 如果能， 說明如何得到(即寫出"進棧"或"出棧"的序列)。
【解答】輸入序列為123456，不能得出435612和154623。不能得到435612的理由是，輸出序列最后兩元素是12，前面4個元素（4356）得到后，棧中元素剩12，且2在棧頂，不可能讓棧底元素1在棧頂元素2之前出棧。不能得到154623的理由類似，當棧中元素只剩23，且3在棧頂
50、，2不可能先于3出棧。
得到325641的過程如下：1 2 3順序入棧，32出棧，得到部分輸出序列32；然后45入棧，5出棧，部分輸出序列變?yōu)?25；接著6入棧并退棧，部分輸出序列變?yōu)?256；最后41退棧，得最終結果325641。
得到135426的過程如下：1入棧并出棧，得到部分輸出序列1；然后2和3入棧，3出棧，部分輸出序列變?yōu)?3；接著4和5入棧，5，4和2依次出棧，部分輸出序列變?yōu)?3542；最后6入棧并退棧，得最終結果135426。
?
3.3? 若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后
51、，rear和front的值分別為多少？
【解答】2和 4
?
3.4? 設棧S和隊列Q的初始狀態(tài)為空，元素e1，e2，e3，e4，e5和e6依次通過棧S，一個元素出棧后即進隊列Q，若6個元素出隊的序列是e3，e5，e4，e6，e2，e1，則棧S的容量至少應該是多少？
【解答】 4
?
3.5? 循環(huán)隊列的優(yōu)點是什么，如何判斷“空”和“滿”。
【解答】循環(huán)隊列解決了常規(guī)用0--m-1的數(shù)組表示隊列時出現(xiàn)的“假溢出”（即隊列未滿但不能入隊）。在循環(huán)隊列中我們?nèi)杂藐狀^指針等于隊尾指針表示隊空，而用犧牲一個單元的辦法表示隊滿，即當隊尾指針加1（求模）等于隊頭指針時，表示隊列滿。也有通過設
52、標記以及用一個隊頭或隊尾指針加上隊中元素個數(shù)來區(qū)分隊列的“空”和“滿”的。
?
3.6? 設長度為n的鏈隊列用單循環(huán)鏈表表示，若只設頭指針，則入隊和出隊的時間如何？若只設尾指針呢？
【解答】若只設頭指針，則入隊的時間為O(n），出隊的時間為O(1)。若只設尾指針，則入隊和出隊的時間均為O(1)。
?
3.7? 指出下面程序段的功能是什么？
(1)? void demo1(SeqStack S)
{int i，arr[64]，n=0;
while(!StackEmpty(S)) arr[n++]=Pop(S);
for(i=0;i
53、;
}
【解答】程序段的功能是實現(xiàn)了棧中元素的逆置。
?
(2)? void demo2(SeqStack S，int m)∥設棧中元素類型為int型
{int x;SeqStack T;
StackInit(T);
while(!StackEmpty(S))
if((x=Pop(S)!=m) Push(T，x);
while(!(StackEmpty(T)) {x=Pop(T); Push(S，x);}
}
【解答】程序段的功能是刪除了棧中值為m的元素。
(3)? void demo3(SeQueue Q，int m)∥設隊列中元素類型為int型
{int x;
54、SeqStack S;
StackInit(S);
while(!QueueEmpty(Q)){x=QueueOut(Q); Push(S，x);}
while(!StackEmpty(S)){x=Pop(s); QueueIn(Q，x);}
}
【解答】程序段的功能是實現(xiàn)了隊列中元素的逆置。
?
3.8? 試將下列遞推過程改寫為遞歸過程。
void ditui(int n)
{i=n;
while(i>1) printf(i--);
}
【解答】void digui(int n)
{if(n>1){printf(n);
55、 digui(n-1);
}
}
?
3.9? 寫出下列中綴表達式的后綴表達式：
(1)A*B*C (2)(A+B)*C-D (3)A*B+C/(D-E) (4)(A+B)*D+E/(F+A*D)+C
【解答】(1)ABC**
(2)AB+C*D-
(3)AB*CDE-/+
(4)AB+D*EFAD*+/+C+
?
3.10????????????? 選擇題：循環(huán)隊列存儲在數(shù)組A[0..m]中，則入隊時的操作為( )。
A. rear=rear+1 B. rear=
56、(rear+1) % (m-1)
C. rear=(rear+1) % m D. rear=(rear+1) % (m+1)
【解答】D
?
3.11 選擇題：4個園盤的Hahoi塔，總的移動次數(shù)為( )。
A.7 B. 8 C.15 D.16
【解答】C
?
3.12選擇題：允許對隊列進行的操作有( )。
A. 對隊列中的元素排序 B. 取出最近進隊的元素
C. 在隊頭元素之前插入元素 D. 刪除隊頭元素
【解答】D
?
二
57、、算法設計題
3.13 利用棧的基本操作，編寫求棧中元素個數(shù)的算法。
【題目分析】 將棧值元素出棧，出棧時計數(shù)，直至棧空。
【算法】 int StackLength(Stack S)
{//求棧中元素個數(shù)
int n=0;
while(!StackEmpty(S)
{n++; Pop(S);
}
return n;
}
算法討論：若要求統(tǒng)計完元素個數(shù)后，不能破壞原來棧，則在計數(shù)時，將原棧導入另一臨時棧，計數(shù)完畢
58、，再將臨時棧倒入原棧中。
int StackLength(Stack S)
{//求棧中元素個數(shù)
int n=0;
Stack T;
StackInit(T); //初始化臨時棧T
while(!StackEmpty(S)
{n++; Push(T,Pop(S));
}
while(!StackEmpty(T)
{Push(S,Pop(T));
}
ret
59、urn n;
}
?
3.14 雙向棧S是在一個數(shù)組空間V[m]內(nèi)實現(xiàn)的兩個棧，棧底分別處于數(shù)組空間的兩端。試為此雙向棧設計棧初始化Init(S)、入棧Push(S，i，x)、出棧Pop(S，i)算法，其中i為0或1，用以指示棧號。
[題目分析]兩棧共享向量空間，將兩棧棧底設在向量兩端，初始時，s1棧頂指針為-1，s2棧頂為m。兩棧頂指針相鄰時為棧滿。兩棧頂相向、迎面增長，棧頂指針指向棧頂元素。
#define ElemType int ∥假設元素類型為整型
typedef struct
{ElemType V[m]; ∥?？臻g
int
60、 top[2]; ∥top為兩個棧頂指針
}stk;
stk S; ∥S是如上定義的結構類型變量，為全局變量
(1)? 棧初始化
int Init()
{S.top[0]=-1;
S.top[1]=m;
return 1; //初始化成功
}
(2)? 入棧操作：
int push(stk S ,int i,int x)
∥i為棧號，i=0表示左棧，i=1為右棧，x是入棧元素。入棧成功返回1，否則返回0
{if(i<0||i>1){printf(“棧號輸入不對\n”);exit(0);}
if(S.top[1]-S
61、.top[0]==1) {printf(“棧已滿\n”);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)? 退棧操作
ElemType pop(stk S,int i)
∥退棧。i代表棧號，i=0時為左棧，i=1時為右棧。退棧成功返回退棧元素
∥否則返回-1
{if(i<0 || i>1){printf(“棧號輸入錯誤\n”)；exit(0);}
62、
switch(i)
{case 0: if(S.top[0]==-1) {printf(“?？誠n”)；return（-1）；}
else return(S.V[S.top[0]--]);
case 1: if(S.top[1]==m {printf(“?？誠n”); return(-1);}
else return(S.V[S.top[1]++]);
}∥switch }∥算法結束
(4)? 判斷棧空
int Empty();
63、
{return (S.top[0]==-1 && S.top[1]==m);
}
[算法討論] 請注意算法中兩棧入棧和退棧時的棧頂指針的計算。s1(左棧)是通常意義下的棧，而s2(右棧)入棧操作時，其棧頂指針左移（減1），退棧時，棧頂指針右移（加1）。
?
3.15設以數(shù)組Q[m]存放循環(huán)隊列中的元素，同時設置一個標志tag，以tag=0和tag=1來區(qū)別在隊頭指針(front)和隊尾指針(rear)相等時，隊列狀態(tài)為“空”還是“不空”。試編寫相應的入隊(QueueIn)和出隊(QueueOut)算法。
（1）?????? 初始化
SeQueue QueueInit(S
64、eQueue Q)
{//初始化隊列
Q.front=Q.rear=0; Q.tag=0;
return Q;
}
（2） 入隊
SeQueue QueueIn(SeQueue Q,int e)
{//入隊列
if((Q.tag==1) && (Q.rear==Q.front)) printf("隊列已滿\n");
else {Q.rear=(Q.rear+1) % m;
Q.data[Q.rear]=e;
if(Q.tag==0) Q.tag=1; //隊列已不空
}
return Q;
}
(3)出隊
65、ElemType QueueOut(SeQueue Q)
{//出隊列
if(Q.tag==0) printf("隊列為空\n");
else
{Q.front=(Q.front+1) % m;
e=Q.data[Q.front];
if(Q.front==Q.rear) Q.tag=0; //空隊列
}
return(e);
}
?
3.16假設用變量rear和length分別指示循環(huán)隊列中隊尾元素的位置和內(nèi)含元素的個數(shù)。試給出此循環(huán)隊列的定義，并寫出相應的入隊(QueueIn)和出隊(QueueOut)算法。
【算法設計】
（1）
66、循環(huán)隊列的定義
typedef struct
{ElemType Q[m]; ∥ 循環(huán)隊列占m個存儲單元
int rear,length; ∥ rear指向隊尾元素,length為元素個數(shù)
}SeQueue;
(2) 初始化
SeQueue QueueInit (SeQueue cq)
∥cq為循環(huán)隊列，本算法進行隊列初始化
{ cq.rear=0; cq.length=0; return cq;
}
(3) 入隊
SeQueue QueueIn(SeQueue cq，ElemType x)
∥cq是以如上定義的循環(huán)隊列，本算法將元素x入隊
{if(cq.length==m) return(0); ∥ 隊滿
else {cq.rear=(cq.rear+1) % m; ∥ 計算插入元素位置
cq.Q[cq.rear]=x; ∥ 將元素x入隊列
cq.length++; ∥ 修改隊列長度
}
return (cq);
}
C語言版 第二版 (陳守孔 孟佳娜 武秀川 著) 機械工業(yè)出版社答案
