1、約瑟夫環問題（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); /*呼叫函式*/}}
2、二叉樹的層次遍歷序列的第乙個結點是二叉樹的根。實際上，層次遍歷序列中的每個結點都是「區域性根」。確定根後，到二叉樹的中序序列中，查到該結點，該結點將二叉樹分為「左根右」三部分。
若左、右子樹均有，則層次序列根結點的後面應是左右子樹的根；若中序序列中只有左子樹或只有右子樹，則在層次序列的根結點後也只有左子樹的根或右子樹的根。這樣，定義乙個全域性變數指標r，指向層次序列待處理元素。演算法中先處理根結點，將根結點和左右子女的資訊入佇列。
然後，在佇列不空的條件下，迴圈處理二叉樹的結點。佇列中元素的資料結構定義如下：
typedef struct
qnode;
bitree creat(datatype in,level,int n)
//由二叉樹的層次序列level[n]和中序序列in[n]生成二叉樹。 n是二叉樹的結點數
qnode s,qq是元素為qnode型別的佇列，容量足夠大
init(q); int r=0; //r是層次序列指標，指向當前待處理的結點
bitree p=(bitree)malloc(sizeof(binode生成根結點
p->data=level[0]; p->lchild=null; p->rchild=null; //填寫該結點資料
for (i=0; iif (in[i]==level[0]) break;
if (i==0) //根結點無左子樹，遍歷序列的1—n-1是右子樹
else if (i==n-1) //根結點無右子樹，遍歷序列的1—n-1是左子樹
else //根結點有左子樹和右子樹
while (!empty(q)) //當佇列不空，進行迴圈，構造二叉樹的左右子樹
else if (i==
else
}//結束while (!empty(q))
return(p);
}//演算法結束
3、證明由二叉樹的中序序列和後序序列，也可以唯一確定一棵二叉樹。
當n=1時，只有乙個根結點，由中序序列和後序序列可以確定這棵二叉樹。
設當n=m-1時結論成立，現證明當n=m時結論成立。
設中序序列為s1，s2，…，sm,後序序列是p1,p2,…，pm。因後序序列最後乙個元素pm是根，則在中序序列中可找到與pm相等的結點（設二叉樹中各結點互不相同）si(1≤i≤m)，因中序序列是由中序遍歷而得，所以si是根結點，s1，s2，…，si-1是左子樹的中序序列，而si+1,si+2,…,sm是右子樹的中序序列。
若i=1，則s1是根，這時二叉樹的左子樹為空，右子樹的結點數是m-1,則和可以唯一確定右子樹，從而也確定了二叉樹。
若i=m,則sm是根，這時二叉樹的右子樹為空，左子樹的結點數是m-1，則和唯一確定左子樹，從而也確定了二叉樹。
最後，當1可唯一確定二叉樹的左子樹，由和
可唯一確定二叉樹的右子樹。
2023年山西省資料分析基礎
1 假設以i和o分別表示入棧和出棧操作。棧的初態和終態均為空，入棧和出棧的操作序列可表示為僅由i和o組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。15分 1 a和d是合法序列，b和c是非法序列。2 設被判定的操作序列已存入一維陣列a中。int judge char a 判斷字元陣列a中的...
2023年山西省資料總結大綱
1 設t是給定的一棵二叉樹，下面的遞迴程式count t 用於求得 二叉樹t中具有非空的左，右兩個兒子的結點個數n2 只有非空左兒子的個數nl 只有非空右兒子的結點個數nr和葉子結點個數n0。n2 nl nr n0都是全域性量，且在呼叫count t 之前都置為0.typedef struct no...
2023年山西省資料總結高階
1 氣泡排序演算法是把大的元素向上移 氣泡的上浮 也可以把小的元素向下移 氣泡的下沉 請給出上浮和下沉過程交替的氣泡排序演算法。48.有n個記錄儲存在帶頭結點的雙向鍊錶中，現用雙向起泡排序法對其按上公升序進行排序，請寫出這種排序的演算法。注 雙向起泡排序即相鄰兩趟排序向相反方向起泡 2 我們用l代表...