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

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

ความสัมพันธ์เวียนเกิด T(n) = 2T(n/2) + O(1) มีผลเฉลยเป็นเท่าใด

  1. AO(n²)
  2. BO(n log n)
  3. CO(log n)
  4. DO(n)
2.อัลกอริทึมและความซับซ้อนยาก

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

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

การท่องแบบ in-order ของ binary search tree เยี่ยมคีย์ตามลำดับ

  1. Aเรียงจากน้อยไปมาก
  2. Bตามระดับ
  3. Cตามลำดับการแทรก
  4. Dเรียงจากมากไปน้อยเสมอ
4.โครงสร้างข้อมูลยาก

โครงสร้างข้อมูลใดรองรับแคช LRU (least recently used) ที่ get และ put เป็น O(1)

  1. Aสแตกเท่านั้น
  2. Bhash map ร่วมกับลิงก์ลิสต์สองทิศทาง
  3. Cbinary search tree เท่านั้น
  4. Dอาร์เรย์เรียงลำดับเดียว
5.ทฤษฎีกราฟปานกลาง
ABCDEวงจรออยเลอร์ทางเดินออยเลอร์ ไม่มีวงจรไม่ใช่ทั้งสองอย่าง

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

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

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

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

3สารละลาย

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

คำตอบ: D · O(n)

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

โดยทฤษฎีบทหลัก nlog₂ 2 = n ครอบงำงานคงที่ จึงได้ T(n) = Θ(n) เช่น การหาค่ามากสุดโดยแบ่งครึ่งเรื่อย ๆ

คำตอบ

D · O(n)
2.อัลกอริทึมและความซับซ้อน

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

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

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

คำตอบ

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

คำตอบ: A · เรียงจากน้อยไปมาก

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

การเยี่ยมต้นไม้ย่อยซ้าย แล้วโหนด แล้วต้นไม้ย่อยขวา ให้คีย์ของ BST ตามลำดับเรียง

คำตอบ

A · เรียงจากน้อยไปมาก
4.โครงสร้างข้อมูล

คำตอบ: B · hash map ร่วมกับลิงก์ลิสต์สองทิศทาง

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

Hash map หาโหนดใน O(1) และลิงก์ลิสต์สองทิศทางย้ายรายการที่เข้าถึงไปด้านหน้าและขับออกจากด้านหลังใน O(1)

คำตอบ

B · hash map ร่วมกับลิงก์ลิสต์สองทิศทาง
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) = 13

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

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

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

A (0): B: 12, C: 14
B (12): C: 13, D: 16, G: 14
C (13): E: 19
G (14)
D (16): F: 28
E (19)
F (28)

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

A → B → C
d(C) = 13

คำตอบ

d(C) = 13

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