1、請編寫乙個判別給定二叉樹是否為二叉排序樹的演算法,設二叉樹用llink-rlink法儲存。
2、有一種簡單的排序演算法,叫做計數排序(count sorting)。這種排序演算法對乙個待排序的表(用陣列表示)進行排序,並將排序結果存放到另乙個新的表中。必須注意的是,表中所有待排序的關鍵碼互不相同,計數排序演算法針對表中的每個記錄,掃瞄待排序的表一趟,統計表中有多少個記錄的關鍵碼比該記錄的關鍵碼小,假設針對某乙個記錄,統計出的計數值為c,那麼,這個記錄在新的有序表中的合適的存放位置即為c。
(1) (3分)給出適用於計數排序的資料表定義;
(2) (7分)使用pascal或c語言編寫實現計數排序的演算法;
(3) (4分)對於有n個記錄的表,關鍵碼比較次數是多少?
(4) (3分)與簡單選擇排序相比較,這種方法是否更好?為什麼?
3、矩陣中元素按行和按列都已排序,要求查詢時間複雜度為o(m+n),因此不能採用常規的二層迴圈的查詢。可以先從右上角(i=a,j=d)元素與x比較,只有三種情況:一是a[i,j]>x, 這情況下向j 小的方向繼續查詢;二是a[i,j]void search(datatype a[ ][ ], int a,b,c,d, datatype x)
//n*m矩陣a,行下標從a到b,列下標從c到d,本演算法查詢x是否在矩陣a中.
else if (a[i][j]>x) j--; else i++;
if(flag) printf(「a[%d][%d]=%d」,i,j,x假定x為整型.
else printf(「矩陣a中無%d 元素」,x);
}演算法search結束。
[演算法討論]演算法中查詢x的路線從右上角開始,向下(當x>a[i,j])或向左(當x4、對一般二叉樹,僅根據乙個先序、中序、後序遍歷,不能確定另乙個遍歷序列。但對於滿二叉樹,任一結點的左右子樹均含有數量相等的結點,根據此性質,可將任一遍歷序列轉為另一遍歷序列(即任一遍歷序列均可確定一棵二叉樹)。
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)
2023年吉林省資料總結大綱
1 題目中要求矩陣兩行元素的平均值按遞增順序排序,由於每行元素個數相等,按平均值排列與按每行元素之和排列是乙個意思。所以應先求出各行元素之和,放入一維陣列中,然後選擇一種排序方法,對該陣列進行排序,注意在排序時若有元素移動,則與之相應的行中各元素也必須做相應變動。void translation f...
2023年吉林省資料總結大綱
1 本題要求建立有序的迴圈鍊錶。從頭到尾掃瞄陣列a,取出a i 0 ilinkedlist creat elemtype a,int n 由含n個資料的陣列a生成迴圈鍊錶,要求鍊錶有序並且無值重複結點 查詢a i 的插入位置 if p h p data a i重複資料不再輸入 for return ...
2023年吉林省資料總結大綱
1 題目中要求矩陣兩行元素的平均值按遞增順序排序,由於每行元素個數相等,按平均值排列與按每行元素之和排列是乙個意思。所以應先求出各行元素之和,放入一維陣列中,然後選擇一種排序方法,對該陣列進行排序,注意在排序時若有元素移動,則與之相應的行中各元素也必須做相應變動。void translation f...