數(shù)據(jù)結構期終考試試卷a-清華大學(完整版)
【正文】 序表的數(shù)據(jù)時， 關鍵碼的比較次數(shù)達到最?。?= n） 。 (1) 使用 Prim 算法 (2) e1 e5 e9 e7 e11 e15 e13 e2 e17 3 2 1 2 3 2 1 4 7 E F G A B C H I J D e2: 4 e3: 4 e8:4 e4:5 e6: 6 e12: 6 e17: 7 e19: 8 e10: 10 e14: 11 e18: 11 e1: 3 e11: 3 e16:3 e7: 2 e15: 2 e5: 2 e9: 1 e13: 1 E F G A B C H I J D e4:5 e2: 4 e3: 4 e8:4 e6: 6 e12: 6 e17: 7 e19: 8 e10: 10 e14: 11 e18: 11 e1: 3 e11: 3 e16:3 e7: 2 e15: 2 e5: 2 e9: 1 e13: 1 4 (2) 使用 Kruskal 算法 e9 e13 e5 e7 e15 e1 e11 e2 e17 1 1 2 2 2 3 3 4 7 (3) 這樣 選取的最小生成樹是唯 一的 。 //線索或子女指針 Type data。 (2) ThreadNodeType * getPreorderNext (ThreadNodeType *p) //尋找結點 *p 的在中序線索化二叉樹中前序下的后繼結點。amp。 } } 五、算法分析題（每小題 5 分，共 15 分） 下面給出一個 排序 算法，其中 n 是數(shù)組 A[ ]中元素總數(shù)。amp。 五、算法分析題（每小題 5 分，共 15 分） (1) 希爾排序 (2) 第一趟 while 循環(huán)內(nèi)各 for 循環(huán)結束時數(shù)組中數(shù)據(jù)的變化： 步 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 移動次數(shù) 77 44 99 66 33 55 88 22 44 11 1 33 77 3 2 44 55 2 3 88 99 3 4 22 66 3 5 44 77 3 6 11 44 55 4 (3) 各趟數(shù)據(jù)移動次數(shù)見表的最右一欄。 //判斷隊列空否， =1 為空 , =0 不空 Typeamp。 =1 ?？眨?=0 不空 void push ( const stackamp。 （ 5 分） (2) “判等”函數(shù) bool queue::operator== (const queueamp。 (tmp)。 bool finished = true。 break。 ()。 } } 9 (3) void queue::clear ( ) { //成員函數(shù) while ( !isEmpty() ) Pop()。 ()。 Pop()。 ()。（ 5 分） (3) “清空”函數(shù) void queue::clear ( )。 //將新元素進棧
公司管理相關推薦
鄂ICP備17016276號-1