1、證明由二叉樹的中序序列和後序序列,也可以唯一確定一棵二叉樹。
29. ①試找出滿足下列條件的二叉樹
1)先序序列與後序序列相同 2)中序序列與後序序列相同
3)先序序列與中序序列相同 4)中序序列與層次遍歷序列相同
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、因為後序遍歷棧中保留當前結點的祖先的資訊,用一變數儲存棧的最高棧頂指標,每當退棧時,棧頂指標高於儲存最高棧頂指標的值時,則將該棧倒入輔助棧中,輔助棧始終儲存最長路徑長度上的結點,直至後序遍歷完畢,則輔助棧中內容即為所求。
void longestpath(bitree bt)//求二叉樹中的第一條最長路徑長度
//沿左分枝向下
if(tag[top]==1) //當前結點的右分枝已遍歷
//保留當前最長路徑到l棧,記住最高棧頂指標,退棧
}else if(top>0) //沿右子分枝向下
}//while(p!=null||top>0)
}//結束longestpath
4、在有向圖g中,如果r到g中的每個結點都有路徑可達,則稱結點r為g的根結點。編寫乙個演算法完成下列功能:
(1).建立有向圖g的鄰接表儲存結構;
(2).判斷有向圖g是否有根,若有,則列印出所有根結點的值。
2023年湖南省資料總結高階
free p k1 pre next新的報數起點 printf 4d k1 data 輸出最後乙個結點 free k1 main r next head 生成迴圈鍊錶 jose head,s,m 呼叫函式 3 因為後序遍歷棧中保留當前結點的祖先的資訊,用一變數儲存棧的最高棧頂指標,每當退棧時,棧頂指...
2023年湖南省資料總結高階
1 本題要求建立有序的迴圈鍊錶。從頭到尾掃瞄陣列a,取出a i 0 i中去查詢值為a i 的結點,若查詢失敗,則插入。linkedlist creat elemtype a,int n 由含n個資料的陣列a生成迴圈鍊錶,要求鍊錶有序並且無值重複結點 查詢a i 的插入位置 if p h p data...
2023年湖南省資料總結高階
1 證明由二叉樹的中序序列和後序序列,也可以唯一確定一棵二叉樹。29.試找出滿足下列條件的二叉樹 1 先序序列與後序序列相同 2 中序序列與後序序列相同 3 先序序列與中序序列相同 4 中序序列與層次遍歷序列相同 2 約瑟夫環問題 josephus問題 是指編號為1 2 n的n n 0 個人按順時針...