1、設有乙個陣列中存放了乙個無序的關鍵序列k1、k2、…、kn。現要求將kn放在將元素排序後的正確位置上，試編寫實現該功能的演算法，要求比較關鍵字的次數不超過n。
51. 借助於快速排序的演算法思想，在一組無序的記錄中查詢給定關鍵字值等於key的記錄。設此組記錄存放於陣列r[l..
h]中。若查詢成功，則輸出該記錄在r陣列中的位置及其值，否則顯示「not find」資訊。請編寫出演算法並簡要說明演算法思想。
2、#define maxsize 棧空間容量
void inouts(int s[maxsize])
//s是元素為整數的棧，本演算法進行入棧和退棧操作。
else s[++top]=x; //x入棧
else //讀入的整數等於-1時退棧。
else printf(「出棧元素是%d\n」,s[top
}}//演算法結
3、 將頂點放在兩個集合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); }//是二部圖
[演算法討論] 題目給的是連通無向圖，若非連通，則演算法要修改。
4、設有一組初始記錄關鍵字為(45，80，48，40，22，78)，要求構造一棵二叉排序樹並給出構造過程。
5、對一般二叉樹，僅根據乙個先序、中序、後序遍歷，不能確定另乙個遍歷序列。但對於滿二叉樹，任一結點的左右子樹均含有數量相等的結點，根據此性質，可將任一遍歷序列轉為另一遍歷序列（即任一遍歷序列均可確定一棵二叉樹）。
void pretopost(elemtype pre ,post,int l1,h1,l2,h2)
//將滿二叉樹的先序序列轉為後序序列，l1,h1,l2,h2是序列初始和最後結點的下標。
}//pretopost
32. .葉子結點只有在遍歷中才能知道，這裡使用中序遞迴遍歷。
設定前驅結點指標pre，初始為空。第乙個葉子結點由指標head指向，遍歷到葉子結點時，就將它前驅的rchild指標指向它，最後葉子結點的rchild為空。
linkedlist head,pre=null; //全域性變數
linkedlist inorder(bitree bt)
//中序遍歷二叉樹bt，將葉子結點從左到右鏈成乙個單鏈表，表頭指標為head
//處理第乙個葉子結點
else //將葉子結點鏈入鍊錶
inorder(bt->rchild中序遍歷左子樹
pre->rchild=null設定鍊錶尾
}return(head); } //inorder
時間複雜度為o(n),輔助變數使用head和pre,棧空間複雜度o(n)
6、給出折半查詢的遞迴演算法，並給出演算法時間複雜度性分析。
7、4、 void linklist_reverse(linklist &l)
//鍊錶的就地逆置;為簡化演算法,假設表長大於2
q->next=p;s->next=q;l->next=s;
}//linklist_reverse
8、本題要求建立有序的迴圈鍊錶。從頭到尾掃瞄陣列a，取出a[i]（0<=ilinkedlist creat(elemtype a,int n)
//由含n個資料的陣列a生成迴圈鍊錶，要求鍊錶有序並且無值重複結點
//查詢a[i]的插入位置
if(p==h || p->data!=a[i重複資料不再輸入
}//for
return(h);
}演算法結束
2023年內蒙古自治區資料總結基礎
1 4 void linklist reverse linklist l 鍊錶的就地逆置 為簡化演算法，假設表長大於2 q next p s next q l next s linklist reverse 2 假設以鄰接矩陣作為圖的儲存結構，編寫演算法判別在給定的有向圖中是否存在乙個簡單有向迴路，...
2023年內蒙古自治區資料總結高階
1 設t是給定的一棵二叉樹，下面的遞迴程式count t 用於求得 二叉樹t中具有非空的左,右兩個兒子的結點個數n2 只有非空左兒子的個數nl 只有非空右兒子的結點個數nr和葉子結點個數n0。n2 nl nr n0都是全域性量，且在呼叫count t 之前都置為0.typedef struct no...
2023年內蒙古自治區資料總結入門
1 設有一組初始記錄關鍵字為 45，80，48，40，22，78 要求構造一棵二叉排序樹並給出構造過程。2 後序遍歷最後訪問根結點，即在遞迴演算法中，根是壓在棧底的。採用後序非遞迴演算法，棧中存放二叉樹結點的指標，當訪問到某結點時，棧中所有元素均為該結點的祖先。本題要找p和q 的最近共同祖先結點r ...