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、 將頂點放在兩個集合v1和v2。對每個頂點，檢查其和鄰接點是否在同乙個集合中，如是，則為非二部圖。為此，用整數1和2表示兩個集合。再用一佇列結構存放圖中訪問的頂點。
int bpgraph (adjmatrix g)
//判斷以鄰接矩陣表示的圖g是否是二部圖。
//初始化，各頂點未確定屬於那個集合
q[1]=1; r=1; s[1]=1;//頂點1放入集合s1
while(f //鄰接點入佇列
else if (s[j]==s[v]) return(0);} //非二部圖
}//if (!visited[v])
}//while
return(1); }//是二部圖
[演算法討論] 題目給的是連通無向圖，若非連通，則演算法要修改。
3、設一棵樹t中邊的集合為，要求用孩子兄弟表示法（二叉鍊錶）表示出該樹的儲存結構並將該樹轉化成對應的二叉樹。
4、有一種簡單的排序演算法，叫做計數排序（count sorting）。這種排序演算法對乙個待排序的表(用陣列表示)進行排序，並將排序結果存放到另乙個新的表中。必須注意的是，表中所有待排序的關鍵碼互不相同，計數排序演算法針對表中的每個記錄，掃瞄待排序的表一趟，統計表中有多少個記錄的關鍵碼比該記錄的關鍵碼小，假設針對某乙個記錄，統計出的計數值為c，那麼，這個記錄在新的有序表中的合適的存放位置即為c。
(1) (3分)給出適用於計數排序的資料表定義;
(2) (7分)使用pascal或c語言編寫實現計數排序的演算法；
(3) (4分)對於有n個記錄的表，關鍵碼比較次數是多少?
(4) (3分)與簡單選擇排序相比較，這種方法是否更好?為什麼?
5、請編寫乙個判別給定二叉樹是否為二叉排序樹的演算法，設二叉樹用llink-rlink法儲存。
6、#define maxsize 棧空間容量void inouts(int s[maxsize])
//s是元素為整數的棧，本演算法進行入棧和退棧操作。
else s[++top]=x; //x入棧else //讀入的整數等於-1時退棧。
else printf(「出棧元素是%d\n」,s[top演算法結
7、若第n件物品能放入揹包，則問題變為能否再從n-1件物品中選出若干件放入揹包（這時揹包可放入物品的重量變為s-w[n]）。若第n件物品不能放入揹包，則考慮從n-1件物品選若干件放入揹包（這時揹包可放入物品仍為s）。若最終s=0,則有一解；否則，若s<0或雖然s>0但物品數n<1,則無解。
（1）s-w[n],n-1 //knap(s-w[n],n-1)=true
（2）s,n-1knap←knap(s,n-1)
8、兩棵空二叉樹或僅有根結點的二叉樹相似；對非空二叉樹，可判左右子樹是否相似，採用遞迴演算法。
int similar(bitree p,q) //判斷二叉樹p和q是否相似
//結束similar
9、設指標變數p指向雙向鍊錶中結
點a，指標變數q指向被插入結點b，要求給出在結點a的後面插入結點b的操作序列（設雙向鍊錶中結點的兩個指標域分別為llink和rlink）。
10、氣泡排序演算法是把大的元素向上移（氣泡的上浮），也可以把小的元素向下移（氣泡的下沉）請給出上浮和下沉過程交替的氣泡排序演算法。
48.有n個記錄儲存在帶頭結點的雙向鍊錶中，現用雙向起泡排序法對其按上公升序進行排序，請寫出這種排序的演算法。（注：雙向起泡排序即相鄰兩趟排序向相反方向起泡）
11、氣泡排序演算法是把大的元素向上移（氣泡的上浮），也可以把小的元素向下移（氣泡的下沉）請給出上浮和下沉過程交替的氣泡排序演算法。
48.有n個記錄儲存在帶頭結點的雙向鍊錶中，現用雙向起泡排序法對其按上公升序進行排序，請寫出這種排序的演算法。（注：雙向起泡排序即相鄰兩趟排序向相反方向起泡）
12、設指標變數p指向雙向鍊錶中結點a，指標變數q指向被插入結點b，要求給出在結點a的後面插入結點b的操作序列（設雙向鍊錶中結點的兩個指標域分別為llink和rlink）。
13、證明由二叉樹的中序序列和後序序列，也可以唯一確定一棵二叉樹。
當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;
else return(similar(p->lchild,q->lchild) && similar(p->rchild,q->rchild))
}//結束similar
15、設一棵樹t中邊的集合為，要求用孩子兄弟表示法（二叉鍊錶）表示出該樹的儲存結構並將該樹轉化成對應的二叉樹。
16、設一組有序的記錄關鍵字序列為(13，18，24，35，47，50，62，83，90)，查詢方法用二分查詢，要求計算出查詢關鍵字62時的比較次數並計算出查詢成功時的平均查詢長度。
17、證明由二叉樹的中序序列和後序序列，也可以唯一確定一棵二叉樹。
當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
typedef char datatype;
typedef struct node listnode;
typedef listnode* linklist刪除單鏈表中重複的結點linklist deletelist(linklist head)
else
p=p->next;
}return head19、在有向圖g中
，如果r到g中的每個結點都有路徑可達，則稱結點r為g的根結點。編寫乙個演算法完成下列功能：
（1）．建立有向圖g的鄰接表儲存結構；
（2）．判斷有向圖g是否有根，若有，則列印出所有根結點的值。
2023年浙江省資料總結摘要
1 二叉樹的層次遍歷序列的第乙個結點是二叉樹的根。實際上，層次遍歷序列中的每個結點都是 區域性根 確定根後，到二叉樹的中序序列中，查到該結點，該結點將二叉樹分為 左根右 三部分。若左 右子樹均有，則層次序列根結點的後面應是左右子樹的根 若中序序列中只有左子樹或只有右子樹，則在層次序列的根結點後也只有...
2023年浙江省資料總結摘要
1 二叉樹的層次遍歷序列的第乙個結點是二叉樹的根。實際上，層次遍歷序列中的每個結點都是 區域性根 確定根後，到二叉樹的中序序列中，查到該結點，該結點將二叉樹分為 左根右 三部分。若左 右子樹均有，則層次序列根結點的後面應是左右子樹的根 若中序序列中只有左子樹或只有右子樹，則在層次序列的根結點後也只有...
2023年浙江省資料總結要領
1 將頂點放在兩個集合v1和v2。對每個頂點，檢查其和鄰接點是否在同乙個集合中，如是，則為非二部圖。為此，用整數1和2表示兩個集合。再用一佇列結構存放圖中訪問的頂點。int bpgraph adjmatrix g 判斷以鄰接矩陣表示的圖g是否是二部圖。初始化，各頂點未確定屬於那個集合 q 1 1 r...