oklp16>试卷(2014/11/23)

公職◆資料結構題庫 下載題庫

102 年 - 關務#18033 

选择:0题,非选:4题
立即測驗 
我要補題 回報試卷錯誤 試卷下載

【非選題】一、關於時間複雜度(time complexity): (一)下列那兩個敘述是錯的?(10分) 


(A) 0.5n2+100n=O(n2)
(B) 1000=O(1)
(C) 0.5n+5logn=O(n2) 
(D) 2n2+5n=O(2n)
(E) n7+1.5n=O(n7)
(F) 3n2+nlog4n=O(nlog4n) 
(二)承上,請把上題錯的敘述改正並且寫下。(20分)

#15705
公職◆資料結構- 102 年 - 關務#18033
編輯私有筆記

【非選題】二、已知一棵二元樹(binary tree)的前序走訪(preorder traversal)與中序走訪(inorder traversal)之結果分別如下:(每小題10分,共20分) 前序-A B D E G H C F I 中序-D B G E H A C I F (一)請繪出這棵二元樹。 (二)這棵二元樹的後序走訪(postorder traversal)結果為何?

#15706
公職◆資料結構- 102 年 - 關務#18033
編輯私有筆記

【非選題】三、請找出並且從小到大依序列出下列有向圖(directed graph)中,從頂點A到所有其他頂點的最短路徑(path)與路徑長度。(20分)

#15707
公職◆資料結構- 102 年 - 關務#18033
編輯私有筆記

【非選題】四、考慮排序(sort)的問題:(每小題10分,共30分) (一)如果要排序的資料很少,例如只有十幾筆資料,那麼你將採用快速排序法(quick sort)?合併排序法(merge sort)?還是氣泡排序法(bubble sort)?為什麼? (二)如果要排序的資料很多,例如多到超過主記憶體容量許多,那麼你將採用快速排序法?合併排序法?還是氣泡排序法?為什麼? (三)快速排序法、合併排序法以及氣泡排序法這三個排序法當中,那一(些)排序法是穩定的(stable)?或者都不穩定?

#15708
公職◆資料結構- 102 年 - 關務#18033
編輯私有筆記