[試題] 99下呂學一資料結構與演算法下期中考消失

看板NTU-Exam作者erodora時間13年前 (2011/04/23 20:20)推噓2(2推 0噓 4→)

留言6則, 4人參與討論串1/1

課程名稱︰資料結構與演算法下課程性質︰必修課程教師︰呂學一開課學院：電資所開課系所︰資訊系考試日期（年月日）︰2011/4/22 考試時限（分鐘）：180 是否需發放獎勵金：是（如未明確表示，則不予發放）試題 : 說明：每題卅分。可按任何順序答題，投影片、課本、作業可以直接引用，除非該題正是以上內容。題目難度不均，慎選答題順序。 == 第一題 Let G be an n-node m-edge undirected connected graph. A node u of G is an articulation point of G if deleting u and its incident edges from G disconnects G. Give an O(m+n)-time algorithm to output the articulation points of G. Justify your algorithm. == 第二題 Let G be an n-node m-edge directed graph with positive edge weights. Let r be a node of G. Let d(u) denote the distance of u from r in G. Assume that d(u) < ∞ holds for each node u of G. Give an O(m．log n)-time algorithm, originally due to Dijkstra, to compute d(u) for all nodes u of G. Justify your algorithm. == 第三題 Let G be an n-node m-edgs directed graph with general edge weights. Give an O(mn)-time algorithm, originally due to Bellman and Ford, to determine if G contains a negative cycle. Justify your algorithm. == 第四題 Let N be an n-node m-edge network with sourse s, sink t, and integral capacities. Let N+ be the n-node m-edge network with sourse s and sink t obtained from N by increasing the capacity of each edge by 1. Let f be a given maximum s,t-flow of N. Give an O(m+n)-time algorithm to compute a maximum s,t-flow of N+. Justify your algorithm. == 第五題 Let S be an n-bit binary string. For each i = 1,2,...,n, define Z(i) to be the largest nonnegative integer k such that S[1,...,k] = S[i,...,i+k-1]. Given an O(n)-time algorithm, originally due to Gusfield, to compute Z(i) for all i = 1,2,...,n. Justify your algorithm. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 125.227.197.228 ※ 編輯: erodora 來自: 125.227.197.228 (04/23 20:26)

推

yuricon

04/23 22:11, , 1^F

04/23 22:11, 1^F

→

andy74139

04/24 00:34, , 2^F

04/24 00:34, 2^F

推

hil

04/24 01:25, , 3^F

04/24 01:25, 3^F