โครงสร้างข้อมูลและอัลกอริทึม: ชุดสรุปเร่งรัด

สรุปสูตร ขั้นตอนวิธีทำที่สำคัญของทุกหัวข้อ และโจทย์ฝึก 6 ข้อ พร้อมเฉลยละเอียดไว้ท้ายเล่ม

โจทย์ใหม่กลับไปที่รายวิชา

ในหน้าต่างพิมพ์ ให้เลือก “บันทึกเป็น PDF” เพื่อเก็บสำเนาไว้ในอุปกรณ์ของคุณ

1สูตรและวิธีทำ

ทฤษฎีกราฟ

เล็มมาการจับมือ
Σ deg(v) = 2|E|
กราฟบริบูรณ์
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
กราฟปรกติ
|E| = n·k/2
ต้นไม้และป่า
|E| = n − 1, |E| = n − c
ใบของต้นไม้
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
ออยเลอร์
วงจร: ดีกรีเป็นคู่ทุกจุดยอด; ทางเดิน: มีดีกรีคี่พอดี 2 จุดยอด
วงจรแฮมิลตันใน Kn
(n − 1)!/2
การปรับค่าของไดก์สตรา
d(v) = min(d(v), d(u) + w(u, v))
วอล์กความยาว L
(Mᴸ)ij

วิธีการ

  1. เขียนดีกรีของทุกจุดยอด ผลบวกของดีกรีเท่ากับสองเท่าของจำนวนเส้นเชื่อม
  2. สำหรับโจทย์ออยเลอร์ ให้ตรวจว่ากราฟเชื่อมโยงกัน และนับจุดยอดที่มีดีกรีคี่
  3. สำหรับต้นไม้ ให้ใช้ว่ามี n − 1 เส้นเชื่อม และเล็มมาการจับมือ
  4. สำหรับไดก์สตรา ให้เก็บตารางระยะทางชั่วคราว และยืนยันจุดยอดที่ยังไม่ยืนยันซึ่งมีค่าน้อยที่สุดในแต่ละรอบ
  5. สำหรับต้นไม้ทอดข้ามค่าน้อยที่สุด ให้เรียงเส้นเชื่อมตามน้ำหนักและข้ามทุกเส้นที่ทำให้เกิดวัฏจักร (ครัสคัล) หรือขยายต้นไม้ต้นเดียวจากจุดยอดเริ่มต้น (พริม)

2โจทย์ฝึก

1.อัลกอริทึมและความซับซ้อนปานกลาง

ความซับซ้อนเชิงเวลาของฟีโบนักชีแบบเรียกซ้ำตรง ๆ (fib(n) = fib(n−1) + fib(n−2)) คือ

  1. Aคงที่
  2. Bเชิงเส้น
  3. Cเอกซ์โพเนนเชียล
  4. Dลอการิทึม
2.อัลกอริทึมและความซับซ้อนยาก

การเรียงลำดับทอพอโลยีทำได้เฉพาะกับ

  1. Aกราฟที่มีน้ำหนักติดลบ
  2. Bกราฟบริบูรณ์
  3. Cกราฟไม่มีทิศทาง
  4. Dกราฟมีทิศทางแบบไม่มีวงจร (DAG)
3.โครงสร้างข้อมูลปานกลาง

ความซับซ้อนเชิงเวลาของการค้นหาคีย์ใน binary search tree ที่สมดุลคือเท่าใด

  1. AO(n log n)
  2. BO(log n)
  3. CO(n)
  4. DO(1)
4.โครงสร้างข้อมูลยาก

ใน BST ที่มีราก 50 ต้นไม้ย่อยซ้าย 30 (ลูก 20, 40) และต้นไม้ย่อยขวา 70 (ลูก 60, 80) ลบรากโดยใช้ in-order successor คีย์ใดกลายเป็นรากใหม่

  1. A70
  2. B40
  3. C60
  4. D80
5.ทฤษฎีกราฟปานกลาง

กราฟเชื่อมโยงมี 17 จุดยอดและ 22 เส้นเชื่อม ต้องเอาเส้นเชื่อมออกกี่เส้น k เพื่อให้เหลือต้นไม้ทอดข้าม

|V| = 17|E| = 22
k =
6.ทฤษฎีกราฟยาก
4191114171292520ABCDEFG

จงหาน้ำหนักรวม W ของต้นไม้ทอดข้ามค่าน้อยที่สุดของกราฟถ่วงน้ำหนัก

|V| = 7|E| = 10
W =

3สารละลาย

1.อัลกอริทึมและความซับซ้อน

คำตอบ: C · เอกซ์โพเนนเชียล

เหตุผลที่เป็นคำตอบนี้

ต้นไม้การเรียกเติบโตประมาณ φⁿ (ราว 1.618ⁿ) การทำ memoisation ลดเหลือ O(n)

คำตอบ

C · เอกซ์โพเนนเชียล
2.อัลกอริทึมและความซับซ้อน

คำตอบ: D · กราฟมีทิศทางแบบไม่มีวงจร (DAG)

เหตุผลที่เป็นคำตอบนี้

ลำดับทอพอโลยีมีอยู่ก็ต่อเมื่อกราฟมีทิศทางไม่มีวงจร และหาได้ใน O(V + E) ด้วย DFS หรืออัลกอริทึมของ Kahn

คำตอบ

D · กราฟมีทิศทางแบบไม่มีวงจร (DAG)
3.โครงสร้างข้อมูล

คำตอบ: B · O(log n)

เหตุผลที่เป็นคำตอบนี้

ต้นไม้สมดุลมีความสูงประมาณ log₂ n การค้นหาจึงตามหนึ่งเส้นทางจากรากถึงใบ

คำตอบ

B · O(log n)
4.โครงสร้างข้อมูล

คำตอบ: C · 60

เหตุผลที่เป็นคำตอบนี้

โหนดซ้ายสุดของต้นไม้ย่อยขวาคือ 60 ดังนั้น 60 แทนที่ 50 และตำแหน่งเดิมของมันถูกลบ ถ้าใช้ predecessor จะได้ 40

คำตอบ

C · 60
5.ทฤษฎีกราฟ

คำตอบ: k = 6

ออยเลอร์ แฮมิลตัน และต้นไม้: กราฟเชื่อมโยงมีวงจรออยเลอร์ (ผ่านทุกเส้นเชื่อมครั้งเดียวและกลับจุดเริ่มต้น) เมื่อทุกจุดยอดมีดีกรีคู่ และมีทางเดินออยเลอร์ที่ไม่ใช่วงจรเมื่อมีจุดยอดดีกรีคี่พอดีสองจุด ทางเดินนั้นไปจากจุดยอดคี่จุดหนึ่งถึงอีกจุดหนึ่ง วงจรแฮมิลตันผ่านทุกจุดยอดครั้งเดียว Kn มีวงจรแบบนี้ (n − 1)!/2 วงจร ต้นไม้ที่มี n จุดยอดมี n − 1 เส้นเชื่อม และกราฟเชื่อมโยงที่มี m เส้นเชื่อมจะเหลือต้นไม้ทอดข้ามหลังเอาเส้นเชื่อมออก m − n + 1 เส้น

เส้นเชื่อมของต้นไม้ทอดข้าม

17 − 1 = 16

เส้นเชื่อมที่ต้องเอาออก

k = 22 − 16 = 6

คำตอบ

k = 6
6.ทฤษฎีกราฟ

คำตอบ: W = 49

เส้นทางที่สั้นที่สุดและต้นไม้ทอดข้าม: ขั้นตอนวิธีของไดก์สตรายืนยันหนึ่งจุดยอดต่อรอบ: จุดยอดที่ยังไม่ยืนยันซึ่งมีระยะทางชั่วคราวน้อยที่สุด ระยะทางของมันเป็นค่าสุดท้ายแล้ว และเพื่อนบ้าน v ทุกจุดได้ d(v) = min(d(v), d(u) + w(u, v)) ขั้นตอนวิธีของครัสคัลสร้างต้นไม้ทอดข้ามค่าน้อยที่สุดโดยเลือกเส้นเชื่อมจากเบาไปหนักและข้ามเส้นที่ทำให้เกิดวัฏจักร ขั้นตอนวิธีของพริมขยายต้นไม้หนึ่งต้นจากจุดยอดเริ่มต้นโดยเพิ่มเส้นเชื่อมที่เบาที่สุดที่ออกจากต้นไม้เสมอ ต้นไม้ทอดข้ามที่มี n จุดยอดมี n − 1 เส้นเชื่อม

ขั้นตอนวิธีของครัสคัล

GC (2): เลือก
AB (4): เลือก
GD (5): เลือก
GB (9): เลือก
BC (11): ข้าม ทำให้เกิดวัฏจักร
EF (12): เลือก
BD (14): ข้าม ทำให้เกิดวัฏจักร
DF (17): เลือก

น้ำหนักรวม

W = 2 + 4 + 5 + 9 + 12 + 17 = 49

คำตอบ

W = 49

ExamProblems · examproblems.com/courses/data-structures-and-algorithms