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

สรุปสูตร ขั้นตอนวิธีทำที่สำคัญของทุกหัวข้อ และโจทย์ฝึก 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, 3 และ 4 และยอด 6 วิธีละโมบ "หยิบเหรียญใหญ่สุดก่อน" ใช้เหรียญกี่เหรียญเมื่อเทียบกับค่าที่เหมาะสมที่สุด

  1. Aละโมบใช้ 2 เหรียญ ค่าที่เหมาะสมที่สุดคือ 2
  2. Bละโมบใช้ 4 เหรียญ ค่าที่เหมาะสมที่สุดคือ 3
  3. Cละโมบใช้ 3 เหรียญ ค่าที่เหมาะสมที่สุดคือ 3
  4. Dละโมบใช้ 3 เหรียญ ค่าที่เหมาะสมที่สุดคือ 2
2.อัลกอริทึมและความซับซ้อนยาก

ปัญหาความสอดคล้องข้อใดต่อไปนี้ทราบว่าแก้ได้ในเวลาพหุนาม

  1. ASAT ทั่วไปบนสูตรรูปแบบนอร์มัลเชิงเชื่อม
  2. B3-SAT ซึ่งแต่ละวลีมีลิเทอรัลสามตัวพอดี
  3. Cความสอดคล้องของวงจร
  4. D2-SAT ซึ่งแต่ละวลีมีลิเทอรัลไม่เกินสองตัว
3.โครงสร้างข้อมูลปานกลาง

โครงสร้างข้อมูลใดใช้ตรวจว่าวงเล็บใน "{[()]}" สมดุลหรือไม่

  1. Aตารางแฮช
  2. Bbinary search tree
  3. Cคิว
  4. Dสแตก
4.โครงสร้างข้อมูลยาก

ข้อได้เปรียบหลักของ skip list เหนือลิงก์ลิสต์ที่เรียงลำดับคืออะไร

  1. Aการค้นหา O(log n) คาดหมาย โดยใช้ตัวชี้ไปข้างหน้าหลายระดับ
  2. Bเก็บคีย์โดยไม่เรียงลำดับ
  3. Cรับประกันการค้นหา O(1) เพราะทุกโหนดเก็บตัวชี้ไปยังทุกโหนดอื่น
  4. Dไม่ใช้หน่วยความจำเพิ่ม
5.ทฤษฎีกราฟปานกลาง

ต้นไม้มี 2 จุดยอดดีกรี 4 และจุดยอดอื่นทั้งหมดเป็นใบ (ดีกรี 1) มีกี่ใบ L

2 × deg 4
L =
6.ทฤษฎีกราฟยาก
1117161218917ABCDEF

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

|V| = 6|E| = 8
W =

3สารละลาย

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

คำตอบ: D · ละโมบใช้ 3 เหรียญ ค่าที่เหมาะสมที่สุดคือ 2

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

วิธีละโมบหยิบ 4 + 1 + 1 = 3 เหรียญ แต่ 3 + 3 ใช้เพียง 2 วิธีละโมบจึงไม่เหมาะสมที่สุดสำหรับระบบเหรียญนี้ การโปรแกรมพลวัตทำได้

คำตอบ

D · ละโมบใช้ 3 เหรียญ ค่าที่เหมาะสมที่สุดคือ 2
2.อัลกอริทึมและความซับซ้อน

คำตอบ: D · 2-SAT ซึ่งแต่ละวลีมีลิเทอรัลไม่เกินสองตัว

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

2-SAT อยู่ใน P (เวลาเชิงเส้นผ่านส่วนประกอบเชื่อมโยงเข้มแข็ง) ส่วน 3-SAT เป็น NP-complete

คำตอบ

D · 2-SAT ซึ่งแต่ละวลีมีลิเทอรัลไม่เกินสองตัว
3.โครงสร้างข้อมูล

คำตอบ: D · สแตก

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

push วงเล็บเปิดแต่ละตัวและ pop เมื่อเจอวงเล็บปิด ต้องตรงกับวงเล็บที่ pop และสแตกต้องว่างเมื่อจบ

คำตอบ

D · สแตก
4.โครงสร้างข้อมูล

คำตอบ: A · การค้นหา O(log n) คาดหมาย โดยใช้ตัวชี้ไปข้างหน้าหลายระดับ

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

ระดับแบบสุ่มทำให้การค้นหาข้ามหลายโหนด ได้การค้นหา แทรก และลบ O(log n) คาดหมาย

คำตอบ

A · การค้นหา O(log n) คาดหมาย โดยใช้ตัวชี้ไปข้างหน้าหลายระดับ
5.ทฤษฎีกราฟ

คำตอบ: L = 6

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

เล็มมาการจับมือสำหรับต้นไม้

L + 8 = 2(L + 2) − 2
L = 6

คำตอบ

L = 6

ทางลัด: L = 2 + Σ (d − 2) ของจุดยอดที่มีดีกรี d ≥ 3

6.ทฤษฎีกราฟ

คำตอบ: W = 45

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

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

AB (1): เลือก
BC (7): เลือก
EF (9): เลือก
AC (11): ข้าม ทำให้เกิดวัฏจักร
CE (12): เลือก
BD (16): เลือก

น้ำหนักรวม

W = 1 + 7 + 9 + 12 + 16 = 45

คำตอบ

W = 45

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