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

สรุปสูตร ขั้นตอนวิธีทำที่สำคัญของทุกหัวข้อ และโจทย์ฝึก 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) = T(n − 1) + O(n) มีผลเฉลยเป็นเท่าใด

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

ความซับซ้อนเชิงเวลาของการสร้างฮีปไบนารีจากสมาชิก n ตัวที่ไม่เรียงลำดับด้วยวิธีล่างขึ้นบนคือเท่าใด

  1. AO(n²)
  2. BO(n)
  3. CO(log n)
  4. DO(n log n)
3.โครงสร้างข้อมูลปานกลาง

ความซับซ้อนเชิงเวลาของการค้นหาคีย์ใน binary search tree ที่สมดุลคือเท่าใด

  1. AO(log n)
  2. BO(1)
  3. CO(n)
  4. DO(n log n)
4.โครงสร้างข้อมูลยาก

กฎของต้นไม้แดง–ดำรับประกันอะไรเกี่ยวกับความสูงของต้นไม้ที่มี n คีย์

  1. Aความสูงเท่ากับ log2 n พอดี
  2. Bความสูงไม่เกิน log2 n + 1
  3. Cความสูงไม่เกิน n / 2
  4. Dความสูงไม่เกิน 2 log2(n + 1)
5.ทฤษฎีกราฟปานกลาง

กราฟบริบูรณ์ K7 มีวงจรแฮมิลตันที่แตกต่างกันกี่วงจร H วงจรที่ต่างกันเพียงจุดยอดเริ่มต้นหรือทิศทางนับเป็นวงจรเดียวกัน

K7
H =
6.ทฤษฎีกราฟยาก
61198316201414ABCDEFG

ขั้นตอนวิธีของพริมสร้างต้นไม้ทอดข้ามค่าน้อยที่สุดโดยเริ่มจากจุดยอด B ให้คลิกเส้นเชื่อมที่เพิ่มเป็นเส้นหมายเลข 2

เริ่มต้น: Bk = 2
  1. 1เส้นเชื่อม AB
  2. 2เส้นเชื่อม AC
  3. 3เส้นเชื่อม BC
  4. 4เส้นเชื่อม CE
  5. 5เส้นเชื่อม DF
  6. 6เส้นเชื่อม EF
  7. 7เส้นเชื่อม GB
  8. 8เส้นเชื่อม GC
  9. 9เส้นเชื่อม GD
  10. 10เส้นเชื่อม GE

3สารละลาย

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

คำตอบ: B · O(n²)

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

งานรวมได้ประมาณ n² / 2 ซึ่งเป็นความสัมพันธ์เวียนเกิดของ selection sort หรือของ quicksort เมื่อเลือกตัวหลักแย่ที่สุด

คำตอบ

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

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

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

การรวมต้นทุนการเลื่อนลงตามแต่ละระดับให้อนุกรมลู่เข้า การสร้างฮีปจึงทำงานในเวลาเชิงเส้น

คำตอบ

B · O(n)
3.โครงสร้างข้อมูล

คำตอบ: A · O(log n)

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

ต้นไม้สมดุลมีความสูงประมาณ log₂ n การค้นหาจึงตามหนึ่งเส้นทางจากรากถึงใบ

คำตอบ

A · O(log n)
4.โครงสร้างข้อมูล

คำตอบ: D · ความสูงไม่เกิน 2 log2(n + 1)

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

ทุกเส้นทางมีจำนวนโหนดดำเท่ากัน และโหนดแดงติดกันไม่ได้ เส้นทางที่ยาวที่สุดจึงไม่เกินสองเท่าของที่สั้นที่สุด ได้ความสูง O(log n)

คำตอบ

D · ความสูงไม่เกิน 2 log2(n + 1)
5.ทฤษฎีกราฟ

คำตอบ: H = 360

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

นับ

H = (7 − 1)!/2 = 720/2 = 360

คำตอบ

H = 360
6.ทฤษฎีกราฟ

คำตอบ: เส้นเชื่อม BC

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

ขั้นตอนวิธีของพริม

1. AB (6)
2. BC (9)
3. CE (8)
4. GE (4)
5. GD (1)
6. DF (3)

เส้นเชื่อมหมายเลข 2

BC

คำตอบ

เส้นเชื่อม BC

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