1、假設以i和o分別表示入棧和出棧操作。棧的初態和終態均為空,入棧和出棧的操作序列可表示為僅由i和o組成的序列,稱可以操作的序列為合法序列,否則稱為非法序列。(15分)
(1)a和d是合法序列,b和c 是非法序列。
(2)設被判定的操作序列已存入一維陣列a中。
int judge(char a)
判斷字元陣列a中的輸入輸出序列是否是合法序列。如是,返回true,否則返回false。
i++; //不論a[i]是『i』或『o』,指標i均後移。}
if(j!=k)
else
演算法結束。
2、約瑟夫環問題(josephus問題)是指編號為1、2、…,n的n(n>0)個人按順時針方向圍坐成一圈,現從第s個人開始按順時針方向報數,數到第m個人出列,然後從出列的下乙個人重新開始報數,數到第m的人又出列,…,如此重複直到所有的人全部出列為止。現要求採用迴圈鍊錶結構設計乙個演算法,模擬此過程。
#include
typedef int datatype;
typedef struct node
listnode;
typedef listnode *linklist;
void jose(linklist head,int s,int m)
while(k1->next!=k1) /*當迴圈鍊錶中的結點個數大於1時*/
pre->next=p->next; /*輸出該結點,並刪除該結點*/
printf("%4d",p->data);
free(p);
k1=pre->next新的報數起點*/
} printf("%4d",k1->data); /*輸出最後乙個結點*/
free(k1);
}main()
r->next=head; /*生成迴圈鍊錶*/
jose(head,s,m); /*呼叫函式*/
}}3、假設以鄰接矩陣作為圖的儲存結構,編寫演算法判別在給定的有向圖中是否存在乙個簡單有向迴路,若存在,則以頂點序列的方式輸出該迴路(找到一條即可)。(注:圖中不存在頂點到自己的弧)
有向圖判斷迴路要比無向圖複雜。利用深度優先遍歷,將頂點分成三類:未訪問;已訪問但其鄰接點未訪問完;已訪問且其鄰接點已訪問完。
下面用0,1,2表示這三種狀態。前面已提到,若dfs(v)結束前出現頂點u到v的回邊,則圖中必有包含頂點v和u的迴路。對應程式中v的狀態為1,而u是正訪問的頂點,若我們找出u的下一鄰接點的狀態為1,就可以輸出迴路了。
void print(int v,int start ) //輸出從頂點start開始的迴路。
//if
void dfs(int v)
//if
else
visited[v]=2;
}//dfs
void find_cycle() //判斷是否有迴路,有則輸出鄰接矩陣。visited陣列為全域性變數。
//find_cycle
4、設一棵樹t中邊的集合為,要求用孩子兄弟表示法(二叉鍊錶)表示出該樹的儲存結構並將該樹轉化成對應的二叉樹。
5、根據二叉排序樹中序遍歷所得結點值為增序的性質,在遍歷中將當前遍歷結點與其前驅結點值比較,即可得出結論,為此設全域性指標變數pre(初值為null)和全域性變數flag,初值為true。若非二叉排序樹,則置flag為false。
#define true 1
#define false 0
typedef struct node
*btree;
void judgebst(btree t,int flag)
// 判斷二叉樹是否是二叉排序樹,本演算法結束後,在呼叫程式中由flag得出結論。
//不是完全二叉樹
judgebst (t->rlink,flag);// 中序遍歷右子樹
}//judgebst演算法結束
6、本題要求建立有序的迴圈鍊錶。從頭到尾掃瞄陣列a,取出a[i](0<=ilinkedlist creat(elemtype a,int n)
//由含n個資料的陣列a生成迴圈鍊錶,要求鍊錶有序並且無值重複結點
//查詢a[i]的插入位置
if(p==h || p->data!=a[i重複資料不再輸入
}//for
return(h);
}演算法結束
7、設一棵二叉樹的結點結構為 (llink,info,rlink),root為指向該二叉樹根結點的指標,p和q分別為指向該二叉樹中任意兩個結點的指標,試編寫一演算法ancestor(root,p,q,r),該演算法找到p和q的最近共同祖先結點r。
2023年江蘇省資料總結大綱
1 我們用l代表最長平台的長度,用k指示最長平台在陣列b中的起始位置 下標 用j記住區域性平台的起始位置,用i指示掃瞄b陣列的下標,i從0開始,依次和後續元素比較,若區域性平台長度 i j 大於l時,則修改最長平台的長度k l i j 和其在b中的起始位置 k j 直到b陣列結束,l即為所求。voi...
2023年江蘇省資料總結高階
1 請設計乙個演算法,要求該演算法把二叉樹的葉子結點按從左到右的順序連成乙個單鏈表,表頭指標為head。二叉樹按二叉鍊錶方式儲存,鏈結時用葉子結點的右指標域來存放單鏈表指標。分析你的演算法的時 空複雜度。2 4 void linklist reverse linklist l 鍊錶的就地逆置 為簡化...
2023年江蘇省資料總結要領
1 有乙個帶頭結點的單鏈表,每個結點包括兩個域,乙個是整型域info,另乙個是指向下乙個結點的指標域next。假設單鏈表已建立,設計演算法刪除單鏈表中所有重複出現的結點,使得info域相等的結點只保留乙個。include typedef char datatype typedef struct no...