1、約瑟夫環問題（josephus問題）是指編號為1、2、…，n的n（n>0）個人按順時針方向圍坐成一圈，現從第s個人開始按順時針方向報數，數到第m個人出列，然後從出列的下乙個人重新開始報數，數到第m的人又出列，…，如此重複直到所有的人全部出列為止。現要求採用迴圈鍊錶結構設計乙個演算法，模擬此過程。
2、給出折半查詢的遞迴演算法，並給出演算法時間複雜度性分析。
3、本題要求建立有序的迴圈鍊錶。從頭到尾掃瞄陣列a，取出a[i]（0<=ilinkedlist creat(elemtype a,int n)
//由含n個資料的陣列a生成迴圈鍊錶，要求鍊錶有序並且無值重複結點
//查詢a[i]的插入位置
if(p==h || p->data!=a[i重複資料不再輸入
}//for
return(h);
}演算法結束
4、二部圖（bipartite graph） g=（v，e）是乙個能將其結點集v分為兩不相交子集v 1和v2=v-v1的無向圖，使得：v1中的任何兩個結點在圖g中均不相鄰，v2中的任何結點在圖g中也均不相鄰。
（1）．請各舉乙個結點個數為5的二部圖和非二部圖的例子。
（2）．請用c或pascal編寫乙個函式bipartite判斷乙個連通無向圖g是否是二部圖，並分析程式的時間複雜度。設g用二維陣列a來表示，大小為n*n（n為結點個數）。請在程式中加必要的注釋。
若有必要可直接利用堆疊或佇列操作。【
5、本題要求建立有序的迴圈鍊錶。從頭到尾掃瞄陣列a，取出a[i]（0<=ilinkedlist creat(elemtype a,int n)
//由含n個資料的陣列a生成迴圈鍊錶，要求鍊錶有序並且無值重複結點
//查詢a[i]的插入位置
if(p==h || p->data!=a[i重複資料不再輸入
}//for
return(h);
}演算法結束
6、二路插入排序是將待排關鍵字序列r[1..n]中關鍵字分二路分別按序插入到輔助向量d[1..n]前半部和後半部（注:
向量d可視為迴圈表），其原則為，先將r[l]賦給d[1]，再從r[2] 記錄開始分二路插入。編寫實現二路插入排序演算法。
7、題目中要求矩陣兩行元素的平均值按遞增順序排序，由於每行元素個數相等，按平均值排列與按每行元素之和排列是乙個意思。所以應先求出各行元素之和，放入一維陣列中，然後選擇一種排序方法，對該陣列進行排序，注意在排序時若有元素移動，則與之相應的行中各元素也必須做相應變動。
void translation（float *matrix，int n）
//本演算法對n×n的矩陣matrix，通過行變換，使其各行元素的平均值按遞增排列。
//for i
for(i=0; i
sum=p[i]; p[i]=p[k]; p[k]=sum; //交換一維陣列中元素之和.
}//if
}//for i
free(p); //釋放p陣列.
}// translation
[演算法分析] 演算法中使用選擇法排序,比較次數較多,但資料交換(移動)較少.若用其它排序方法,雖可減少比較次數,但資料移動會增多.演算法時間複雜度為o(n2).
8、約瑟夫環問題（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); /*呼叫函式*/
}}9、在有向圖g中，如果r到g中的每個結點都有路徑可達，則稱結點r為g的根結點。編寫乙個演算法完成下列功能：
（1）．建立有向圖g的鄰接表儲存結構；
（2）．判斷有向圖g是否有根，若有，則列印出所有根結點的值。
10、約瑟夫環問題（josephus問題）是指編號為1、2、…，n的n（n>0）個人按順時針方向圍坐成一圈，現從第s個人開始按順時針方向報數，數到第m個人出列，然後從出列的下乙個人重新開始報數，數到第m的人又出列，…，如此重複直到所有的人全部出列為止。現要求採用迴圈鍊錶結構設計乙個演算法，模擬此過程。
#include<>
typedef int datatype;
typedef struct node
listnode;
typedef listnode *linklist;
2019台灣省資料簡介基礎
1 根據二叉排序樹中序遍歷所得結點值為增序的性質，在遍歷中將當前遍歷結點與其前驅結點值比較，即可得出結論，為此設全域性指標變數pre 初值為null 和全域性變數flag，初值為true。若非二叉排序樹，則置flag為false。define true 1 define false 0 typede...
2019台灣省資料結構考試題庫
1 n個頂點的圖的最小生成樹必定 d 是不正確的描述。a 不唯一b 權的總和唯一 c 不含迴路d 有n條邊 2 資料結構中，在邏輯上可以把資料結構分成 b a 動態結構和靜態結構 b 線性結構和非線性結構 c 緊湊結構和非緊湊結構 d 內部結構和外部結構 3 n個頂點的強連通圖至少有 a 條邊。a ...
2019台灣省資料結構 C考試試題庫 完整版
a n b n 1 c n 1 d n n 1 8 與無向圖相關的術語有 c a 強連通圖b 入度 c 路徑d 弧 9 下列各種資料結構中屬於線性結構的有 a a 棧b 二叉樹 c 廣義表d 圖 10 如果結點a有3個兄弟，而且b為a的雙親，則b的度為 b a 3 b 4 c 5d 111 n個頂點...