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

สรุปสูตร ขั้นตอนวิธีทำที่สำคัญของทุกหัวข้อ และโจทย์ฝึก 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.อัลกอริทึมและความซับซ้อนปานกลาง

อัลกอริทึม Floyd–Warshall คำนวณอะไรและเร็วเพียงใด

  1. Aต้นไม้ทอดข้ามที่น้อยที่สุดใน O(E log V)
  2. Bเส้นทางสั้นที่สุดระหว่างจุดยอดทุกคู่ใน O(V³)
  3. Cเส้นทางสั้นที่สุดจากจุดยอดต้นทางหนึ่งไปยังจุดยอดอื่นทั้งหมดใน O(V + E)
  4. Dลำดับทอพอโลยีใน O(V²)
2.อัลกอริทึมและความซับซ้อนยาก

โดยใช้ทฤษฎีบทหลัก T(n) = 8T(n/2) + O(n²) มีผลเฉลยเป็น

  1. AΘ(n²)
  2. BΘ(n² log n)
  3. CΘ(n³)
  4. DΘ(n log n)
3.โครงสร้างข้อมูลปานกลาง

แอปพลิเคชันต้องการค้นหาเร็ว และต้องแสดงรายการคีย์เรียงลำดับและตอบคำถามช่วง โครงสร้างใดเหมาะที่สุด

  1. Aลิงก์ลิสต์ที่ไม่เรียงลำดับ
  2. Bตารางแฮช
  3. Cbinary search tree แบบสมดุล
  4. Dสแตก
4.โครงสร้างข้อมูลยาก

เพื่อให้ตารางแฮชทำงานถูกต้อง แฮชและความเท่ากันต้องเป็นไปตามกฎใด

  1. Aค่าแฮชที่เท่ากันหมายถึงคีย์เท่ากัน
  2. Bคีย์ที่เท่ากันต้องมีค่าแฮชเท่ากัน
  3. Cคีย์ที่ต่างกันต้องมีค่าแฮชต่างกัน
  4. Dค่าแฮชต้องเป็นจำนวนเฉพาะ
5.ทฤษฎีกราฟปานกลาง
ABCDEวงจรออยเลอร์ทางเดินออยเลอร์ ไม่มีวงจรไม่ใช่ทั้งสองอย่าง

กราฟเชื่อมโยงนี้มีวงจรออยเลอร์ ทางเดินออยเลอร์ที่ไม่ใช่วงจร หรือไม่มีทั้งสองอย่าง ให้คลิกคำตอบของคุณ

|V| = 5|E| = 7
  1. 1วงจรออยเลอร์
  2. 2ทางเดินออยเลอร์ ไม่มีวงจร
  3. 3ไม่ใช่ทั้งสองอย่าง
6.ทฤษฎีกราฟยาก
14111271271555ABCDEFG

ใช้ขั้นตอนวิธีของไดก์สตราเพื่อหาความยาว d(C) ของเส้นทางที่สั้นที่สุดจาก A ไป C ในกราฟถ่วงน้ำหนัก

เริ่มต้น: Aสิ้นสุด: C
d(C) =

3สารละลาย

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

คำตอบ: B · เส้นทางสั้นที่สุดระหว่างจุดยอดทุกคู่ใน O(V³)

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

Floyd–Warshall เป็นอัลกอริทึมการโปรแกรมพลวัตที่อนุญาตให้ทีละจุดยอดเป็นจุดผ่านกลาง โดยใช้เวลา O(V³)

คำตอบ

B · เส้นทางสั้นที่สุดระหว่างจุดยอดทุกคู่ใน O(V³)
2.อัลกอริทึมและความซับซ้อน

คำตอบ: C · Θ(n³)

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

log₂ 8 = 3 และ n² เติบโตช้ากว่า n³ ใบจึงครอบงำ: Θ(n³)

คำตอบ

C · Θ(n³)
3.โครงสร้างข้อมูล

คำตอบ: C · binary search tree แบบสมดุล

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

BST สมดุลให้การค้นหา O(log n) และรักษาลำดับคีย์ การท่อง in-order และคำถามช่วงจึงทำได้ง่าย ตารางแฮชกระจายคีย์

คำตอบ

C · binary search tree แบบสมดุล
4.โครงสร้างข้อมูล

คำตอบ: B · คีย์ที่เท่ากันต้องมีค่าแฮชเท่ากัน

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

หากสองคีย์ที่เท่ากันแฮชต่างกัน จะถูกเก็บในถังต่างกันและการค้นหาจะล้มเหลว คีย์ที่ไม่เท่ากันยังใช้แฮชร่วมกันได้

คำตอบ

B · คีย์ที่เท่ากันต้องมีค่าแฮชเท่ากัน
5.ทฤษฎีกราฟ

คำตอบ: ทางเดินออยเลอร์ ไม่มีวงจร

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

ดีกรี

deg(A) = 2, deg(B) = 4, deg(C) = 3, deg(D) = 2, deg(E) = 3

จุดยอดคี่

C, E → 2
ทางเดินออยเลอร์ ไม่มีวงจร

คำตอบ

ทางเดินออยเลอร์ ไม่มีวงจร

ทางเดินออยเลอร์เริ่มที่จุดยอดคี่จุดหนึ่งและจบที่อีกจุดหนึ่ง

6.ทฤษฎีกราฟ

คำตอบ: d(C) = 25

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

ไดก์สตราทีละรอบ

แต่ละบรรทัด: จุดยอดที่ยืนยัน ระยะทางสุดท้ายของมัน และเพื่อนบ้านที่ระยะทางดีขึ้น

A (0): B: 14
B (14): C: 25, D: 26
C (25): E: 32, G: 40
D (26): G: 31
G (31)
E (32): F: 39
F (39)

เส้นทางที่สั้นที่สุด

A → B → C
d(C) = 25

คำตอบ

d(C) = 25

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