1、假設以鄰接矩陣作為圖的儲存結構，編寫演算法判別在給定的有向圖中是否存在乙個簡單有向迴路，若存在，則以頂點序列的方式輸出該迴路（找到一條即可）。（注：圖中不存在頂點到自己的弧）
有向圖判斷迴路要比無向圖複雜。利用深度優先遍歷，將頂點分成三類：未訪問；已訪問但其鄰接點未訪問完；已訪問且其鄰接點已訪問完。
下面用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
2、請編寫乙個判別給定二叉樹是否為二叉排序樹的演算法，設二叉樹用llink-rlink法儲存。
3、題目中要求矩陣兩行元素的平均值按遞增順序排序，由於每行元素個數相等，按平均值排列與按每行元素之和排列是乙個意思。所以應先求出各行元素之和，放入一維陣列中，然後選擇一種排序方法，對該陣列進行排序，注意在排序時若有元素移動，則與之相應的行中各元素也必須做相應變動。
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).
4、假設k1，…，kn是n個關鍵詞，試解答：
試用二叉查詢樹的插入演算法建立一棵二叉查詢樹，即當關鍵詞的插入次序為k1，k2，…，kn 時，用演算法建立一棵以llink / rlink 鏈結表示的二叉查詢樹。
5、設從鍵盤輸入一整數的序列：a1, a2, a3，…，an,試編寫演算法實現：用棧結構儲存輸入的整數，當ai≠-1時，將ai進棧；當ai=-1時，輸出棧頂整數並出棧。
演算法應對異常情況（入棧滿等）給出相應的資訊。
設有乙個揹包可以放入的物品重量為s，現有n件物品，重量分別為w1，w2，...，wn。問能否從這n件物品中選擇若干件放入揹包，使得放入的重量之和正好是s。
設布林函式knap(s，n)表示揹包問題的解，wi(i=1,2,...，n)均為正整數，並已順序儲存地在陣列w中。請在下列演算法的下劃線處填空，使其正確求解揹包問題。
knap(s，n)
若s=0
則knap←true
否則若（s<0）或(s>0且n<1)
則knap←false
否則若knap(1) , _=true
則print(w[n])；knap ←true
否則 knap←knap(2) _ , _
設有乙個順序棧s，元素s1, s2, s3, s4, s5, s6依次進棧，如果6個元素的出棧順序為s2, s3, s4, s6, s5, s1，則順序棧的容量至少應為多少？畫出具體進棧、出棧過程。
假定採用帶頭結點的單鏈表儲存單詞，當兩個單詞有相同的字尾時，則可共享相同的字尾儲存空間。例如：
設str1和str2是分別指向兩個單詞的頭結點，請設計乙個盡可能的高效演算法，找出兩個單詞共同字尾的起始位置，分析演算法時間複雜度。
將n(n>1)個整數存放到一維陣列r中。設計乙個盡可能高效（時間、空間）的算
法，將r中儲存的序列迴圈左移p（06、約瑟夫環問題（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); /*呼叫函式*/}}
7、假設以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
}//演算法結束。
8、#define maxsize 棧空間容量
void inouts(int s[maxsize])
//s是元素為整數的棧，本演算法進行入棧和退棧操作。
else s[++top]=x; //x入棧。
else //讀入的整數等於-1時退棧。
else printf(「出棧元素是%d\n」,s[top--])；}
}}//演算法結
2019山東省資料結構 C必備
1 若某線性表最常用的操作是訪問任一指定序號的元素和在最後進行插入和刪除運算，則利用 d 儲存方式最節省時間。a 順序表b 雙鏈表c 帶頭結點的雙迴圈鍊錶d 單迴圈鍊錶 2 n個頂點的圖的最小生成樹必定 d 是不正確的描述。a 不唯一b 權的總和唯一 c 不含迴路d 有n條邊 3 若一棵二叉樹具有1...
2023年山東省資料總結加強
1 設一組有序的記錄關鍵字序列為 13，18，24，35，47，50，62，83，90 查詢方法用二分查詢，要求計算出查詢關鍵字62時的比較次數並計算出查詢成功時的平均查詢長度。2 題目中要求矩陣兩行元素的平均值按遞增順序排序，由於每行元素個數相等，按平均值排列與按每行元素之和排列是乙個意思。所以應...
2023年山東省資料總結加強
1 設一組有序的記錄關鍵字序列為 13，18，24，35，47，50，62，83，90 查詢方法用二分查詢，要求計算出查詢關鍵字62時的比較次數並計算出查詢成功時的平均查詢長度。2 給出折半查詢的遞迴演算法，並給出演算法時間複雜度性分析。3 連通圖的生成樹包括圖中的全部n個頂點和足以使圖連通的n 1...