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

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

ในปัญหาการเลือกกิจกรรม กฎละโมบข้อใดให้จำนวนกิจกรรมที่ไม่ทับซ้อนกันมากที่สุดเสมอ

  1. Aเลือกกิจกรรมที่สั้นที่สุดก่อน
  2. Bเลือกกิจกรรมที่ทับซ้อนกับผู้อื่นน้อยที่สุดก่อน แล้วทำซ้ำกับกิจกรรมที่เข้ากันได้
  3. Cเลือกกิจกรรมที่เสร็จเร็วที่สุด แล้วทำซ้ำกับกิจกรรมที่เข้ากันได้
  4. Dเลือกกิจกรรมที่เริ่มเร็วที่สุด
2.อัลกอริทึมและความซับซ้อนยาก

ปัญหาหนึ่งเป็น NP-complete ถ้ามัน

  1. Aแก้ได้ในเวลาพหุนาม
  2. Bอยู่นอก NP แต่ยากกว่าทุกปัญหา NP เช่น ปัญหาการหยุด
  3. Cแก้ไม่ได้เลย
  4. Dอยู่ใน NP และทุกปัญหา NP ลดรูปมาเป็นมันได้ในเวลาพหุนาม
3.โครงสร้างข้อมูลปานกลาง

แทรกคีย์ 50, 30, 70, 20, 40 ตามลำดับนี้ลงใน binary search tree ว่าง ลูกซ้ายของ 30 คืออะไร

  1. A70
  2. B50
  3. C20
  4. D40
4.โครงสร้างข้อมูลยาก

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

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

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

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

ขั้นตอนวิธีของไดก์สตราเริ่มจาก A ให้คลิกจุดยอดที่ถูกยืนยัน (ทำให้เป็นค่าถาวร) ในรอบที่ 3 โดย A เองคือรอบที่ 1

เริ่มต้น: Aรอบ 3
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
  7. 7G

3สารละลาย

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

คำตอบ: C · เลือกกิจกรรมที่เสร็จเร็วที่สุด แล้วทำซ้ำกับกิจกรรมที่เข้ากันได้

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

การเลือกเวลาเสร็จที่เร็วที่สุดพิสูจน์ได้ว่าเหมาะสมที่สุดด้วยข้อโต้แย้งการแลกเปลี่ยน ส่วนกฎอื่นมีตัวอย่างค้าน

คำตอบ

C · เลือกกิจกรรมที่เสร็จเร็วที่สุด แล้วทำซ้ำกับกิจกรรมที่เข้ากันได้
2.อัลกอริทึมและความซับซ้อน

คำตอบ: D · อยู่ใน NP และทุกปัญหา NP ลดรูปมาเป็นมันได้ในเวลาพหุนาม

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

ปัญหา NP-complete เป็นปัญหาที่ยากที่สุดใน NP ถ้ามีอัลกอริทึมพหุนามสำหรับปัญหาหนึ่ง ก็จะมีสำหรับทั้ง NP

คำตอบ

D · อยู่ใน NP และทุกปัญหา NP ลดรูปมาเป็นมันได้ในเวลาพหุนาม
3.โครงสร้างข้อมูล

คำตอบ: C · 20

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

20 น้อยกว่า 50 และน้อยกว่า 30 จึงเป็นลูกซ้ายของ 30 ส่วน 40 เป็นลูกขวา

คำตอบ

C · 20
4.โครงสร้างข้อมูล

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

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

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

คำตอบ

C · hash map ร่วมกับลิงก์ลิสต์สองทิศทาง
5.ทฤษฎีกราฟ

คำตอบ: k = 12

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

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

11 − 1 = 10

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

k = 22 − 10 = 12

คำตอบ

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

คำตอบ: C

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

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

1. A (0): B: 3
2. B (3): C: 13, D: 15, G: 17
3. C (13): E: 20
4. D (15): F: 22
5. G (17)
6. E (20)
7. F (22)

รอบ 3

C

คำตอบ

C

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