1、有一種簡單的排序演算法，叫做計數排序（count sorting）。這種排序演算法對乙個待排序的表(用陣列表示)進行排序，並將排序結果存放到另乙個新的表中。必須注意的是，表中所有待排序的關鍵碼互不相同，計數排序演算法針對表中的每個記錄，掃瞄待排序的表一趟，統計表中有多少個記錄的關鍵碼比該記錄的關鍵碼小，假設針對某乙個記錄，統計出的計數值為c，那麼，這個記錄在新的有序表中的合適的存放位置即為c。
(1) (3分)給出適用於計數排序的資料表定義;
(2) (7分)使用pascal或c語言編寫實現計數排序的演算法；
(3) (4分)對於有n個記錄的表，關鍵碼比較次數是多少?
(4) (3分)與簡單選擇排序相比較，這種方法是否更好?為什麼?
2、對一般二叉樹，僅根據乙個先序、中序、後序遍歷，不能確定另乙個遍歷序列。但對於滿二叉樹，任一結點的左右子樹均含有數量相等的結點，根據此性質，可將任一遍歷序列轉為另一遍歷序列（即任一遍歷序列均可確定一棵二叉樹）。
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)
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);
}演算法結束
2023年黑龍江省資料總結大綱
1 給出折半查詢的遞迴演算法，並給出演算法時間複雜度性分析。2 將頂點放在兩個集合v1和v2。對每個頂點，檢查其和鄰接點是否在同乙個集合中，如是，則為非二部圖。為此，用整數1和2表示兩個集合。再用一佇列結構存放圖中訪問的頂點。int bpgraph adjmatrix g 判斷以鄰接矩陣表示的圖g是...
2023年黑龍江省資料總結高階
1 二部圖 bipartite graph g v，e 是乙個能將其結點集v分為兩不相交子集v 1和v2 v v1的無向圖，使得 v1中的任何兩個結點在圖g中均不相鄰，v2中的任何結點在圖g中也均不相鄰。1 請各舉乙個結點個數為5的二部圖和非二部圖的例子。2 請用c或pascal編寫乙個函式bipa...
2023年黑龍江省資料總結加強
1 在有向圖g中，如果r到g中的每個結點都有路徑可達，則稱結點r為g的根結點。編寫乙個演算法完成下列功能 1 建立有向圖g的鄰接表儲存結構 2 判斷有向圖g是否有根，若有，則列印出所有根結點的值。2 約瑟夫環問題 josephus問題 是指編號為1 2 n的n n 0 個人按順時針方向圍坐成一圈，現...