1．選擇題
（ 1）若讓元素 1， 2， 3， 4， 5 依次進堆疊，則出堆疊次序不可能出現在（）種情況，
A． 5， 4， 3， 2， 1
B． 2， 1， 5， 4， 3
C． 4， 3， 1， 2， 5
D． 2， 3， 5， 4， 1
答案： C
解釋：堆疊是后進先出的線性表，不難發現 C 選項中元素 1 比元素 2 先出堆疊，違背了堆疊
的后進先出原則，所以不可能出現 C 選項所示的情況，
（ 2）若已知一個堆疊的入堆疊序列是 1，2，3… n，其輸出序列為 p1，p2，p3 … pn， 若 p1=n ，則 pi 為（），
A． i
B ． n-i
C ． n-i+1
D ．不確定
答案： C
解釋：堆疊是后進先出的線性表，一個堆疊的入堆疊序列是 1， 2， 3，, ， n，而輸出序列的
第一個元素為 n，說明 1，2，3，, ， n 一次性全部進堆疊， 再進行輸出， 所以 p1=n ，p2=n-1 ，, ，
pi=n-i+1 ，
（ 3）陣列Ｑ［ｎ］用來表示一個回圈佇列，ｆ為當前佇列頭元素的前一位置，ｒ為隊尾
元素的位置，假定佇列中元素的個數小于ｎ，計算佇列中元素個數的公式為（） ，
A ． r-f
B ． (n+f-r)%n
C ． n+r-f
D ．( n+r-f)%n
答案： D
解釋：對于非回圈佇列，尾指標和頭指標的差值便是佇列的長度，而對于回圈佇列，
差值可能為負數， 所以需要將差值加上 MAXSIZE （本題為 n），然后與 MAXSIZE （本題為 n）
求余，即（ n+r-f)%n ，
（ 4）鏈式堆疊結點為： (data,link) ， top 指向堆疊頂 .若想摘除堆疊頂結點，并將洗掉結點的值
保存到 x 中 ,則應執行操作（） ，
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 將結點的值保存到 x 中，top=top->link 堆疊頂指標指向堆疊頂下一結點，
即摘除堆疊頂結點，
（ 5）設有一個遞回演算法如下
int fact(int n) { //n 大于等于 0
if(n<=0) return 1;
else return n*fact(n-1);
}
則計算 fact(n) 需要呼叫該函式的次數為（），
A． n+1
B． n-1
C． n
D． n+2
答案： A
解釋：特殊值法，設 n=0，易知僅呼叫一次 fact(n) 函式，故選 A ，
（ 6）堆疊在 （）中有所應用，
A．遞回呼叫 B．函式呼叫 C．運算式求值 D．前三個選項都有
答案： D
解釋：遞回呼叫、函式呼叫、運算式求值均用到了堆疊的后進先出性質，
（ 7）為解決計算機主機與列印機間速度不匹配問題，通常設一個列印資料緩沖區，主機
將要輸出的資料依次寫入該緩沖區，而列印機則依次從該緩沖區中取出資料，該緩沖區的邏
輯結構應該是（） ，
A．佇列 B ．堆疊 C．線性表 D．有序表
答案： A
解釋：解決緩沖區問題應利用一種先進先出的線性表，而佇列正是一種先進先出的線性表，
（ 8）設堆疊 S 和佇列 Q 的初始狀態為空，元素 e1、 e2、 e3、 e4、 e5 和 e6 依次進入堆疊 S，
一個元素出堆疊后即進入 Q，若 6 個元素出隊的序列是 e2、 e4、e3、e6、e5 和 e1，則堆疊 S 的容
量至少應該是（ ），
A． 2 B． 3 C． 4 D． 6
答案： B
解釋：元素出隊的序列是 e2、e4、e3、e6、e5 和 e1 ，可知元素入隊的序列是 e2、e4、
e3、 e6、 e5 和 e1，即元素出堆疊的序列也是 e2、 e4、 e3、 e6、 e5 和 e1，而元素 e1、 e2、 e3、
e4、 e5 和 e6 依次進入堆疊，易知堆疊 S 中最多同時存在 3 個元素，故堆疊 S 的容量至少為 3，
（ 9）若一個堆疊以向量 V[1…n] 存盤，初始堆疊頂指標 top 設為 n+1 ，則元素 x 進堆疊的正確操作是 ( ) ，
A． top++; V[top]=x; B． V[top]=x; top++;
C． top–; V[top]=x; D． V[top]=x; top–;
答案： C
解釋：初始堆疊頂指標 top 為 n+1 ，說明元素從陣列向量的高端地址進堆疊，又因為元素
存盤在向量空間 V[1…n] 中，所以進堆疊時 top 指標先下移變為 n，之后將元素 x 存盤在 V[n] ，
（ 10）設計一個判別運算式中左，右括號是否配對出現的演算法，采用（ ）資料結構最佳，
A．線性表的順序存盤結構 B．佇列
C. 線性表的鏈式存盤結構 D. 堆疊
答案： D
解釋：利用堆疊的后進先出原則，
（ 11）用鏈接方式存盤的佇列，在進行洗掉運算時（ ），
A. 僅修改頭指標 B. 僅修改尾指標
C. 頭、尾指標都要修改 D. 頭、尾指標可能都要修改
答案： D
解釋：一般情況下只修改頭指標，但是，當洗掉的是佇列中最后一個元素時，隊尾指
針也丟失了，因此需對隊尾指標重新賦值，
（ 12）回圈佇列存盤在陣列 A[0…m] 中，則入隊時的操作為（ ），
A. rear=rear+1 B. rear=(rear+1)%(m-1)
C. rear=(rear+1)%mD. rear=(rear+1)%(m+1)
答案： D
解釋：陣列 A[0…m] 中共含有 m+1 個元素，故在求模運算時應除以 m+1，
（ 13）最大容量為 n 的回圈佇列， 隊尾指標是 rear ，隊頭是 front ，則隊空的條件是 （ ），
A. (rear+1)%n==front B. rear==front
C． rear+1==front D. (rear-l)%n==front
答案： B
解 釋 ： 最 大 容 量 為 n 的 循 環 隊 列 ， 隊 滿 條 件 是 (rear+1)%n==front ， 隊 空 條 件 是rear==front ，
（ 14）堆疊和佇列的共同點是（ ），
A. 都是先進先出 B. 都是先進后出
C. 只允許在端點處插入和洗掉元素 D. 沒有共同點
答案： C
解釋：堆疊只允許在堆疊頂處進行插入和洗掉元素，佇列只允許在隊尾插入元素和在隊頭
洗掉元素，
（ 15）一個遞回演算法必須包括（ ），
A. 遞回部分 B. 終止條件和遞回部分
C. 迭代部分 D. 終止條件和迭代部分
答案： B
2．演算法設計題
（ 1）將編號為 0 和 1 的兩個堆疊存放于一個陣列空間 V[m] 中，堆疊底分別處于陣列的兩端，
當第 0 號堆疊的堆疊頂指標 top[0] 等于 -1 時該堆疊為空，當第 1 號堆疊的堆疊頂指標 top[1] 等于 m 時該
堆疊為空，兩個堆疊均從兩端向中間增長，試撰寫雙堆疊初始化，判斷堆疊空、堆疊滿、進堆疊和出堆疊等
演算法的函式，雙堆疊資料結構的定義如下：
Typedef struct
{
int top[2],bot[2]; //堆疊頂和堆疊底指標
SElemType *V; //堆疊陣列
int m; //堆疊最大可容納元素個數
}DblStack
[ 題目分析 ]
兩堆疊共享向量空間，將兩堆疊堆疊底設在向量兩端，初始時，左堆疊頂指標為 -1 ，右堆疊頂為 m，
兩堆疊頂指標相鄰時為堆疊滿，兩堆疊頂相向、迎面增長，堆疊頂指標指向堆疊頂元素，
[ 演算法描述 ]
(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){
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) 退堆疊操作
ElemType pop(stk S,int i)
∥退堆疊， i 代表堆疊號， i=0 時為左堆疊， i=1 時為右堆疊，退堆疊成功時回傳退堆疊元素
∥否則回傳 -1
{
if(i<0 || i>1){cout<< “堆疊號輸入錯誤 ”<<endl ； exit(0);}
switch(i) {
case 0:
if(S.top[0]==-1) {
cout<< “堆疊空 ”<<endl ； return （ -1）； }
else return(S.V[S.top[0]--]);
case 1:
if(S.top[1]==m {
cout<< “堆疊空 ”<<endl; return(-1);}
else return(S.V[S.top[1]++]);
} ∥ switch
} ∥演算法結束
(4) 判斷堆疊空
int Empty();
{
return (S.top[0]==-1 && S.top[1]==m);
}
[演算法討論 ]
請注意演算法中兩堆疊入堆疊和退堆疊時的堆疊頂指標的計算，左堆疊是通常意義下的堆疊，而右堆疊入
堆疊操作時，其堆疊頂指標左移（減 1），退堆疊時，堆疊頂指標右移（加 1）， （ 2）回文是指正讀反讀均相同的字符序列， 如“ abba”和“ abdba ”均是回文， 但“ good ”
不是回文，試寫一個演算法判定給定的字符向量是否為回文， (提示：將一半字符入堆疊 )
[ 題目分析 ]
將字串前一半入堆疊，然后，堆疊中元素和字串后一半進行比較，即將第一個出堆疊元素
和后一半串中第一個字符比較，若相等，則再出堆疊一個元素與后一個字符比較， , ，直至
堆疊空， 結論為字符序列是回文， 在出堆疊元素與串中字符比較不等時， 結論字符序列不是回文，
[ 演算法描述 ]
#define StackSize 100 // 假定預分配的堆疊空間最多為 100 個元素
typedef char DataType;// 假定堆疊元素的資料型別為字符
typedef struct {
DataType data[StackSize];
int top;
}SeqStack;
int IsHuiwen( char *t)
{// 判斷 t 字符向量是否為回文，若是，回傳 1，否則回傳 0
SeqStack s;
int i , len;
char temp;
InitStack( &s);
len=strlen(t); // 求向量長度
for ( i=0; i<len/2; i++)// 將一半字符入堆疊
Push( &s, t[i]);
while( !EmptyStack( &s))
{// 每彈出一個字符與相應字符比較
temp=Pop (&s);
if( temp!=S[i]) return 0 ;// 不等則回傳 0
else i++;
}
return 1 ; // 比較完畢均相等則回傳 1
}
（ 3）設從鍵盤輸入一整數的序列： a1, a2, a3， …， an，試撰寫演算法實作：用堆疊結構存盤
輸入的整數，當 ai≠ -1 時，將 ai 進堆疊；當 ai=-1 時，輸出堆疊頂整數并出堆疊，演算法應對例外情
況（入堆疊滿等）給出相應的資訊，
[ 演算法描述 ]
#define maxsize 堆疊空間容量
void InOutS(int s[maxsize])
//s 是元素為整數的堆疊，本演算法進行入堆疊和退堆疊操作，
{
int top=0; //top 為堆疊頂指標，定義 top=0 時為堆疊空，
for(i=1; i<=n; i++) //n 個整數序列作處理，
18
{cin>>x); // 從鍵盤讀入整數序列，
if(x!=-1) // 讀入的整數不等于 -1 時入堆疊，
｛
if(top==maxsize-1)
{cout<< “堆疊滿” <<endl;exit(0);}
else s[++top]=x; //x 入堆疊，
｝
else // 讀入的整數等于 -1 時退堆疊，
{
if(top==0)
{cout<< “堆疊空” <<endl;exit(0);}
else cout<< “出堆疊元素是” <<s[top--]<<endl;}
}
}// 演算法結束，
（ 4）從鍵盤上輸入一個后綴運算式，試撰寫演算法計算運算式的值，規定：逆波蘭運算式
的長度不超過一行，以
符
作
為
輸
入
結
束
，
操
作
數
之
間
用
空
格
分
隔
,
操
作
符
只
可
能
有
+
、
?
、
?
、
/
四
種
運
算
，
例
如
：
23434
+
2
?
符作為輸入結束，運算元之間用空格分隔 , 運算子只可能有 +、 - 、 * 、 / 四種運算，例如： 234 34+2*
符作為輸入結束，操作數之間用空格分隔,操作符只可能有+、?、?、/四種運算，例如：23434+2? ， [ 題目分析 ]
逆波蘭運算式 ( 即后綴運算式 ) 求值規則如下：設立運算元堆疊 OPND,對運算式從左到右掃
描 ( 讀入 ) ，當運算式中掃描到數時， 壓入 OPND堆疊， 當掃描到運算子時， 從 OPND退出兩個數，
進行相應運算，結果再壓入 OPND 堆疊，這個程序一直進行到讀出運算式結束符 $，這時 OPND
堆疊中只有一個數，就是結果，
[ 演算法描述 ]
float expr( )
// 從鍵盤輸入逆波蘭運算式，以‘ $’表示輸入結束，本演算法求逆波蘭式運算式的值，
｛
float OPND[30]; // OPND 是運算元堆疊，
init(OPND); // 兩堆疊初始化，
float num=0.0; // 數字初始化，
cin>>x;//x 是字符型變數，
while(x!= ’$’)
{
switch
{
case ‘0’<=x<=’9’:
while((x>= ’0’&&x<=’9’)||x== ’. ’) // 拼數
if(x!= ’. ’) // 處理整數
{
num=num*10+ （ ord(x)- ord( ‘0’) ） ; cin>>x;
}
else // 處理小數部分，
{
scale=10.0; cin>>x;
while(x>= ’0’&&x<=’9’)
{num=num+(ord(x)- ord( ‘0’)/scale;
scale=scale*10; cin>>x; }
}//else
push(OPND,num); num=0.0;// 數壓入堆疊，下個數初始化
case x= ‘ ’:break; // 遇空格，繼續讀下一個字符，
case x= ‘+’:push(OPND,pop(OPND)+pop(OPND));break;
case x= ‘ - ’ :x1=pop(OPND);x2=pop(OPND);push(OPND,x2-x1);break;
case x= ‘*’:push(OPND,pop(OPND)*pop(OPND));break;
case x= ‘ / ’ :x1=pop(OPND);x2=pop(OPND);push(OPND,x2/x1);break;
default: // 其它符號不作處理，
}// 結束 switch
cin>>x;// 讀入運算式中下一個字符，
}// 結束 while （ x！ =‘$’）
cout<< “后綴運算式的值為” <<pop(OPND);
}// 演算法結束，
[ 演算法討論 ] 假設輸入的后綴運算式是正確的，未作錯誤檢查，演算法中拼數部分是核心，
若遇到大于等于‘ 0’且小于等于‘ 9’的字符，認為是數，這種字符的序號減去字符‘ 0’的
序號得出數，對于整數，每讀入一個數字字符，前面得到的部分數要乘上 10 再加新讀入的數
得到新的部分數，當讀到小數點，認為數的整數部分已完，要接著處理小數部分，小數部分
的數要除以 10 （或 10 的冪數）變成十分位，百分位，千分位數等等，與前面部分數相加，
在拼數程序中，若遇非數字字符，表示數已拼完，將數壓入堆疊中，并且將變數 num 恢復為 0，
準備下一個數，這時對新讀入的字符進入‘ +’、‘ - ’、‘ * ’、‘ / ’及空格的判斷，因此在結束
處理數字字符的 case 后，不能加入 break 陳述句，
（ 5）假設以 I 和 O 分別表示入堆疊和出堆疊操作，堆疊的初態和終態均為空，入堆疊和出堆疊的操
作序列可表示為僅由 I 和 O 組成的序列， 稱可以操作的序列為合法序列， 否則稱為非法序列，
①下面所示的序列中哪些是合法的？
A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO
②通過對①的分析， 寫出一個演算法， 判定所給的操作序列是否合法， 若合法， 回傳 true ，
否則回傳 false （假定被判定的操作序列已存入一維陣列中） ，
答案：
① A 和 D 是合法序列， B 和 C 是非法序列，
②設被判定的操作序列已存入一維陣列 A 中，
int Judge(char A[])
// 判斷字符陣列 A 中的輸入輸出序列是否是合法序列，如是，回傳 true ，否則回傳
false ，
{
i=0; //i 為下標，
j=k=0; //j 和 k 分別為 I 和字母 O 的的個數，
while(A[i]!= ‘ 0’) // 當未到字符陣列尾就作，
{
switch(A[i])
{
case ‘I ’: j++; break; // 入堆疊次數增 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);}
}// 演算法結束，
[ 演算法討論 ] 在入堆疊出堆疊序列（即由‘ I ’和‘ O’組成的字串）的任一位置，入堆疊次數
（‘ I ’的個數）都必須大于等于出堆疊次數（即‘ O’的個數） ，否則視作非法序列，立即給出
資訊，退出演算法，整個序列（即讀到字符陣列中字串的結束標記‘ \0 ’），入堆疊次數必須等
于出堆疊次數（題目中要求堆疊的初態和終態都為空） ，否則視為非法序列，
(6）假設以帶頭結點的回圈鏈表表示佇列，并且只設一個指標指向隊尾元素站點 ( 注意不
設頭指標 ) ，試撰寫相應的置空隊、判隊空、入隊和出隊等演算法，
[ 題目分析 ]
置空隊就是建立一個頭節點，并把頭尾指標都指向頭節點，頭節點是不存放資料的；判
隊空就是當頭指標等于尾指標時，隊空；入隊時，將新的節點插入到鏈佇列的尾部，同時將
尾指標指向這個節點；出隊時，洗掉的是隊頭節點，要注意佇列的長度大于 1 還是等于 1 的
情況，這個時候要注意尾指標的修改，如果等于 1，則要洗掉尾指標指向的節點，
[演算法描述 ]
//先定義鏈隊結構 :
typedef struct queuenode
{
Datatype data;
struct queuenode *next;
}QueueNode; // 以上是結點型別的定義
typedef struct
{
queuenode *rear;
}LinkQueue; // 只設一個指向隊尾元素的指標
(1) 置空隊
void InitQueue( LinkQueue *Q)
{ // 置空隊：就是使頭結點成為隊尾元素
QueueNode *s;
Q->rear = Q->rear->next;// 將隊尾指標指向頭結點
while (Q->rear!=Q->rear->next)// 當佇列非空，將隊中元素逐個出隊
{
s=Q->rear->next;
Q->rear->next=s->next;
}
delete s;
}// 回收結點空間
}
(2) 判隊空
int EmptyQueue( LinkQueue *Q)
{ // 判隊空，當頭結點的 next 指標指向自己時為空隊
return Q->rear->next->next==Q->rear->next;
}
(3) 入隊
void EnQueue( LinkQueue *Q, Datatype x)
{ // 入隊，也就是在尾結點處插入元素
QueueNode *p=new QueueNode;// 申請新結點
p->data=x; p->next=Q->rear->next;// 初始化新結點并鏈入
Q-rear->next=p;
Q->rear=p;// 將尾指標移至新結點
}
(4) 出隊
Datatype DeQueue( LinkQueue *Q)
{// 出隊 ,把頭結點之后的元素摘下
Datatype t;
QueueNode *p;
if(EmptyQueue( Q ))
Error("Queue underflow");
p=Q->rear->next->next; //p 指向將要摘下的結點
x=p->data; // 保存結點中資料
if (p==Q->rear)
{// 當佇列中只有一個結點時， p 結點出隊后，要將隊尾指標指向頭結點
Q->rear = Q->rear->next;
Q->rear->next=p->next;
}
else
Q->rear->next->next=p->next;// 摘下結點 p
delete p;// 釋放被刪結點
return x;
}
（ 7）假設以陣列 Q[ m] 存放回圈佇列中的元素 , 同時設定一個標志 tag ，以 tag== 0 和 tag == 1 來區別在隊頭指標 ( front )和隊尾指標 ( rear )相等時，佇列狀態為 “空 ”還是 “滿 ”，試撰寫與此結構相應的插入 (enqueue )和洗掉 (dlqueue )演算法，
[演算法描述 ]
(1) 初始化
SeQueue QueueInit(SeQueue 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))
cout<<" 佇列已滿 "<<endl;
else
{
Q.rear=(Q.rear+1) % m;
Q.data[Q.rear]=e;
if(Q.tag==0) Q.tag=1; // 佇列已不空
}
return Q;
}
(3) 出隊
ElemType QueueOut(SeQueue Q)
{// 出佇列
if(Q.tag==0) {
cout<<" 佇列為空 "<<endl; exit(0);}
else
{Q.front=(Q.front+1) % m;
e=Q.data[Q.front];
if(Q.front==Q.rear) Q.tag=0; // 空佇列
}
return(e);
}
(8 ）如果允許在回圈佇列的兩端都可以進行插入和洗掉操作，要求：
① 寫出回圈佇列的型別定義；
② 寫出“從隊尾洗掉”和“從隊頭插入”的演算法，
[ 題目分析 ] 用一維陣列 v[0…M-1] 實作回圈佇列，其中 M 是佇列長度，設隊頭指標front 和隊尾指標 rear ，約定 front 指向隊頭元素的前一位置， rear 指向隊尾元素，定義front=rear 時為隊空，(rear+1)%m=front 為隊滿，約定隊頭端入隊向下標小的方向發展，隊尾端入隊向下標大的方向發展，
[ 演算法描述 ]
①
#define M 佇列可能達到的最大長度
typedef struct
{
elemtp data[M];
int front,rear;
}cycqueue;
②
elemtp delqueue ( cycqueue Q)
//Q 是如上定義的回圈佇列，本演算法實作從隊尾洗掉，若洗掉成功，回傳被洗掉元素，
否則給出出錯資訊，
{
if (Q.front==Q.rear) {
cout<<" 佇列空 "<<endl; exit(0);}
Q.rear=(Q.rear-1+M)%M; // 修改隊尾指標，
return(Q.data[(Q.rear+1+M)%M]); // 回傳出隊元素，
}// 從隊尾洗掉演算法結束
void enqueue (cycqueue Q, elemtp x)
// Q 是順序存盤的回圈佇列，本演算法實作“從隊頭插入”元素 x，
{
if(Q.rear==(Q.front-1+M)%M)
{cout<<" 隊滿 "<<endl; exit(0);)
Q.data[Q.front]=x; //x 入佇列
Q.front=(Q.front-1+M)%M; // 修改隊頭指標，
}// 結束從隊頭插入演算法，
（ 9）已知 Ackermann 函式定義如下 :
① 寫出計算 Ack(m,n) 的遞回演算法，并根據此演算法給出出 Ack(2,1) 的計算程序，
② 寫出計算 Ack(m,n) 的非遞回演算法，
[ 演算法描述 ]
int Ack(int m,n)
{
if (m==0) return(n+1);
else if(m!=0&&n==0) return(Ack(m-1,1));
else return(Ack(m-1,Ack(m,m-1));
}// 演算法結束
① Ack(2,1) 的計算程序
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 而得
②
int Ackerman(int m, int n)
{
int akm[M][N];int i,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]);
}// 演算法結束
（ 10）已知 f 為單鏈表的表頭指標 , 鏈表中存盤的都是整型資料，試寫出實作下列運算
的遞回演算法：
①求鏈表中的最大整數；
②求鏈表的結點個數；
③求所有整數的平均值，
[演算法描述 ]
①
int GetMax(LinkList p)
{
if(!p->next)
return p->data;
else
{
int max=GetMax(p->next);
return p->data>=max ? p->data:max;
}
}
②
int GetLength(LinkList p)
{
if(!p->next)
return 1;
else
{
return GetLength(p->next)+1;
}
}
③
double GetAverage(LinkList p , int n)
{
if(!p->next)
return p->data;
else
{
double ave=GetAverage(p->next,n-1);
return (ave*(n-1)+p->data)/n;
}
}
排版和格式真的很費勁啊啊啊啊， 求贊~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/200472.html
標籤：其他
下一篇：第九周總結