一基礎知識題
設將整數依次進棧但只要出棧時棧非空則可將出棧操作按任何次序夾入其中請回答下述問題
()若入出棧次序為Push() Pop()Push()Push() Pop() Pop( )Push() Pop( )則出棧的數字序列為何(這裡Push(i)表示i進棧Pop( )表示出棧)?
() 能否得到出棧序列和?並說明為什麼不能得到或者如何得到
()請分析 的種排列中哪些序列是可以通過相應的入出棧操作得到的
鏈棧中為何不設置頭結點?
循環隊列的優點是什麼? 如何判別它的空和滿?
設長度為n的鏈隊用單循環鏈表表示若設頭指針則入隊出隊操作的時間為何? 若只設尾指針呢?
指出下述程序段的功能是什麼?
() void Demo(SeqStack *S){
int i; arr[] ; n= ;
while ( StackEmpty(S)) arr[n++]=Pop(S);
for (i= i< n; i++) Push(S arr[i]);
} //Demo
() SeqStack S S tmp;
DataType x;
//假設棧tmp和S已做過初始化
while ( ! StackEmpty (&S))
{
x=Pop(&S) ;
Push(&tmpx);
}
while ( ! StackEmpty (&tmp) )
{
x=Pop( &tmp);
Push( &Sx);
Push( &S x);
}
() void Demo( SeqStack *S int m)
{ // 設DataType 為int 型
SeqStack T; int i;
InitStack (&T);
while (! StackEmpty( S))
if(( i=Pop(S)) !=m) Push( &Ti);
while (! StackEmpty( &T))
{
i=Pop(&T); Push(Si);
}
}
()void Demo( CirQueue *Q)
{ // 設DataType 為int 型
int x; SeqStack S;
InitStack( &S);
while (! QueueEmpty( Q ))
{x=DeQueue( Q); Push( &Sx);}
while (! StackEmpty( &s))
{ x=Pop(&S); EnQueue( Qx );}
}// Demo
() CirQueue Q Q; // 設DataType 為int 型
int x i n= ;
// 設Q已有內容 Q已初始化過
while ( ! QueueEmpty( &Q) )
{ x=DeQueue( &Q ) ; EnQueue(&Q x); n++;}
for (i=; i< n; i++)
{ x=DeQueue(&Q) ;
EnQueue( &Q x) ; EnQueue( &Q x);}
二算法設計題
回文是指正讀反讀均相同的字符序列如abba和abdba均是回文但good不是回文試寫一個算法判定給定的字符向量是否為回文(提示將一半字符入棧)
利用棧的基本操作寫一個將棧S中所有結點均刪去的算法void ClearStack( SeqStack *S)並說明S為何要作為指針參數?
利用棧的基本操作 寫一個返回S中結點個數的算法 int StackSize( SeqStack S)並說明S為何不作為指針參數?
設計算法判斷一個算術表達式的圓括號是否正確配對 (提示 對表達式進行掃描凡遇到(就進棧遇)就退掉棧頂的(表達式被掃描完畢棧應為空
一個雙向棧S是在同一向量空間內實現的兩個棧它們的棧底分別設在向量空間的兩端 試為此雙向棧設計初始化InitStack ( S ) 入棧Push( S i x) 和出棧Pop( S i )等算法 其中i為 或 用以表示棧號
Ackerman 函數定義如下請寫出遞歸算法
┌ n+ 當m=時
AKM ( m n ) = │ AKM( m ) 當m≠ n=時
└ AKM( m AKM( mn)) 當m≠ n ≠ 時
用第二種方法 即少用一個元素空間的方法來區別循環隊列的隊空和隊滿試為其設計置空隊判隊空判隊滿出隊入隊及取隊頭元素等六個基本操作的算法
假設以帶頭結點的循環鏈表表示隊列並且只設一個指針指向隊尾元素站點(注意不設頭指針) 試編寫相應的置空隊判隊空 入隊和出隊等算法
對於循環向量中的循環隊列寫出求隊列長度的公式
假設循環隊列中只設rear和quelen 來分別指示隊尾元素的位置和隊中元素的個數試給出判別此循環隊列的隊滿條件並寫出相應的入隊和出隊算法要求出隊時需返回隊頭元素
From:http://tw.wingwit.com/Article/program/sjjg/201311/23990.html
