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

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

เหตุใดการโปรแกรมพลวัตจึงไม่ช่วยเร่ง merge sort ได้จริง

  1. AMerge sort ไม่มีโครงสร้างแบบเรียกซ้ำ
  2. Bการโปรแกรมพลวัตใช้ได้กับปัญหากราฟเท่านั้น ไม่ใช่กับอาร์เรย์
  3. CMerge sort เป็น O(n) อยู่แล้ว
  4. Dปัญหาย่อยของมันไม่ซ้อนทับกัน จึงไม่มีอะไรให้ใช้ซ้ำ
2.อัลกอริทึมและความซับซ้อนยาก

22n อยู่ใน O(2ⁿ) หรือไม่

  1. Aไม่ เพราะ 22n เติบโตช้ากว่า 2ⁿ
  2. Bใช่ เพราะตัวคูณคงที่ในเลขชี้กำลังถูกละไว้เสมอใน Big O
  3. Cใช่ เพราะทั้งสองเป็นเอกซ์โพเนนเชียล
  4. Dไม่ เพราะ 22n = 4ⁿ และ 4ⁿ / 2ⁿ = 2ⁿ เติบโตไม่มีขอบเขต
3.โครงสร้างข้อมูลปานกลาง

หาคีย์ที่น้อยที่สุดใน binary search tree ได้อย่างไร

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

Bloom filter ตอบคำถาม "สมาชิกนี้อยู่ในเซตหรือไม่" ได้ด้วย

  1. Aคำตอบสำหรับตัวเลขเท่านั้น
  2. Bคำตอบที่แม่นยำเสมอ
  3. Cอาจมีผลลบเท็จ แต่ไม่มีผลบวกเท็จ
  4. Dอาจมีผลบวกเท็จ แต่ไม่มีผลลบเท็จ
5.ทฤษฎีกราฟปานกลาง

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

|V| = 7|E| = 15
k =
6.ทฤษฎีกราฟยาก
761315315124ABCDEF

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

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

3สารละลาย

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

คำตอบ: D · ปัญหาย่อยของมันไม่ซ้อนทับกัน จึงไม่มีอะไรให้ใช้ซ้ำ

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

ครึ่งของ merge sort ไม่ซ้อนกันและแต่ละส่วนถูกแก้ครั้งเดียว DP ช่วยเฉพาะเมื่อปัญหาย่อยเกิดซ้ำ เช่น ฟีโบนักชี

คำตอบ

D · ปัญหาย่อยของมันไม่ซ้อนทับกัน จึงไม่มีอะไรให้ใช้ซ้ำ
2.อัลกอริทึมและความซับซ้อน

คำตอบ: D · ไม่ เพราะ 22n = 4ⁿ และ 4ⁿ / 2ⁿ = 2ⁿ เติบโตไม่มีขอบเขต

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

ค่าคงที่ที่บวกเข้ากับเลขชี้กำลังให้ตัวคูณคงที่ แต่ค่าคงที่ที่คูณเลขชี้กำลังเปลี่ยนฐานและอัตราการเติบโต

คำตอบ

D · ไม่ เพราะ 22n = 4ⁿ และ 4ⁿ / 2ⁿ = 2ⁿ เติบโตไม่มีขอบเขต
3.โครงสร้างข้อมูล

คำตอบ: A · ตามลูกซ้ายจากรากจนไม่มีลูกซ้าย

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

โหนดซ้ายสุดไม่มีคีย์ที่เล็กกว่าในต้นไม้ จึงเป็นค่าต่ำสุด ต้นทุนแปรผันตามความสูง

คำตอบ

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

คำตอบ: D · อาจมีผลบวกเท็จ แต่ไม่มีผลลบเท็จ

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

ถ้าบิตใดของรายการเป็น 0 รายการนั้นไม่อยู่แน่นอน ถ้าทั้งหมดเป็น 1 น่าจะอยู่ Bloom filter แลกความแม่นยำกับหน่วยความจำที่น้อยมาก

คำตอบ

D · อาจมีผลบวกเท็จ แต่ไม่มีผลลบเท็จ
5.ทฤษฎีกราฟ

คำตอบ: k = 9

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

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

7 − 1 = 6

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

k = 15 − 6 = 9

คำตอบ

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

คำตอบ: d(D) = 20

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

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

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

A (0): C: 7
C (7): B: 13, E: 22
B (13): D: 26, E: 17
E (17): D: 20, F: 29
D (20)
F (29)

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

A → C → B → E → D
d(D) = 20

คำตอบ

d(D) = 20

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