[試題] 99上 呂學一 資料結構與演算法上 期末考消失
課程名稱︰資料結構與演算法上
課程性質︰系內必修
課程教師︰呂學一
開課學院：電機資訊學院
開課系所︰資訊工程學系
考試日期（年月日）︰2011/01/14
考試時限（分鐘）：180
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
貳零壹壹年壹月拾肆日玖點拾分起參小時
說明：每題三十分。可按任何順序答題，投影片、課本、作業可以直接引用，
除非該題正是以上內容。
第一題
Given n points in the 2-dimensional plane, please design an Ο(n log n)-time
algorithm to compute two closest points. Do not forget to justify and analyze
your algorithm.
第二題
Given n points in the 2-dimensional plane, please design an Ο(n log n)-time
algorithm to compute two farthest points. You may assume that the convex hull
of these n points can be obtained in Ο(n log n) time. You may also assume
that no three points are collinear i.e. 任三點不共線. Do not forget to
justify and analyze your algorithm.
第三題
Let R be a given array consisting of n distinct positive integers. We say that
i is an XD-index for R if there is an j with n ≧ i ＞ j ≧ 1 and R[i] ＜ R[j].
（提示： i 是小餅， j 是大餅。） Please design an Ο(n)-time algorithm to
output all the XD-indices for R. Do not forget to justify and analyze your
algorithm.
第四題
Let S be a dynamic set consisting of at most n distinct positive integers.
Let H be an Ο(1)-time computable function mapping the elements of S to
{1, 2, ..., n}. Suppose that the given function H has magic property that
for each index i in {1, 2, ..., n}, only Ο(1) distinct elements of S can be
mapped to i by H. Please design an Ο(n)-time space data structure for S
such that each of the (1) creation and initialization operation, (2) insertion
operation, (3) deletion operation, and (4) membership query can be supported
in Ο(1) time. Do not forget to justify and analyze your implementation.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.117.140.91
※ 編輯: paul112004 來自: 59.117.140.91 (01/14 14:53)
→
01/14 20:42, , 1F
01/14 20:42, 1F
※ 編輯: paul112004 來自: 59.117.140.53 (01/15 11:32)
→
01/15 11:33, , 2F
01/15 11:33, 2F
→
01/17 18:01, , 3F
01/17 18:01, 3F