課程名稱︰資料結構與演算法
課程性質︰必修
課程教師︰張智星、林軒田
開課學院：電資學院
開課系所︰資訊系
考試日期（年月日）︰20160419
考試時限（分鐘）：約30分鐘
試題 :
1.About heaps:(2 pts)Given a heap of depth h, what are its minimum and maximum
number of nodes?
2.Complexity of operations on heaps:(4 pts)Given the time complexity of the
following operations on a heap of n nodes:(a)size(b)min(c)insert(d)removeMin
3.Insertion and deletion in heaps:(4 pts)Draw the max-heap tree after the
following operations are performed beginning with an empty heap:insert 43,
insert 31, insert 68, insert 24, delete-max, insert 51, insert 44, insert 53,
insert 69, insert 71, delete-max.
4.In-place heap sort:(10 pts)Given a vector of [8 5 1 3 7], how do you perform
in-place heap sort? Please plot the 5 heaps (both vector and tree
representations) during heap construction, and the other 5 during output.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.163.42.26
※ 文章網址: https://www.ptt.cc/bbs/NTU-Exam/M.1466947662.A.3B6.html