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

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

ความซับซ้อนเชิงเวลาของการคำนวณจำนวนฟีโบนักชีตัวที่ n ด้วยตารางแบบล่างขึ้นบนคือเท่าใด

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

ปัญหาที่ตัดสินไม่ได้ (undecidable) ต่างจากปัญหาที่จัดการไม่ได้ (intractable) อย่างไร

  1. Aปัญหาที่ตัดสินไม่ได้อยู่ใน NP ส่วนปัญหาที่จัดการไม่ได้อยู่ใน P
  2. Bทั้งสองหมายถึงปัญหาไม่มีอัลกอริทึมเลย
  3. Cปัญหาที่จัดการไม่ได้ไม่มีอัลกอริทึมใดแก้ได้ ส่วนปัญหาที่ตัดสินไม่ได้ต้องการเพียงเวลาเอกซ์โพเนนเชียล
  4. Dปัญหาที่ตัดสินไม่ได้ไม่มีอัลกอริทึมสำหรับทุกอินพุต ส่วนปัญหาที่จัดการไม่ได้มีอัลกอริทึมแต่ช้าเกินไป
3.โครงสร้างข้อมูลปานกลาง

ต้นไม้ AVL และต้นไม้แดง–ดำ (red-black) รับประกัน

  1. Aไม่มีโหนดใดมีลูกสองตัว
  2. Bความสูง O(log n) ผ่านการปรับสมดุลใหม่
  3. Cการค้นหาในเวลาคงที่ทุกกรณี
  4. Dคีย์ถูกเก็บตามลำดับการแทรก
4.โครงสร้างข้อมูลยาก

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

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

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

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

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

k = 6
  1. 1เส้นเชื่อม AB
  2. 2เส้นเชื่อม AC
  3. 3เส้นเชื่อม BC
  4. 4เส้นเชื่อม BD
  5. 5เส้นเชื่อม CE
  6. 6เส้นเชื่อม DF
  7. 7เส้นเชื่อม GB
  8. 8เส้นเชื่อม GD
  9. 9เส้นเชื่อม GE

3สารละลาย

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

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

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

การเติมตารางจาก 0 ถึง n ใช้การบวกหนึ่งครั้งต่อช่อง งานจึงเป็นเชิงเส้นแทนที่จะเป็นเอกซ์โพเนนเชียล

คำตอบ

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

คำตอบ: D · ปัญหาที่ตัดสินไม่ได้ไม่มีอัลกอริทึมสำหรับทุกอินพุต ส่วนปัญหาที่จัดการไม่ได้มีอัลกอริทึมแต่ช้าเกินไป

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

ปัญหาการหยุดไม่มีอัลกอริทึมเลย ส่วนปัญหา NP-hard เช่น TSP แก้ได้ด้วยกำลังเดรัจฉาน เพียงแต่ไม่ได้ในเวลาพหุนามที่ทราบ

คำตอบ

D · ปัญหาที่ตัดสินไม่ได้ไม่มีอัลกอริทึมสำหรับทุกอินพุต ส่วนปัญหาที่จัดการไม่ได้มีอัลกอริทึมแต่ช้าเกินไป
3.โครงสร้างข้อมูล

คำตอบ: B · ความสูง O(log n) ผ่านการปรับสมดุลใหม่

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

ต้นไม้ปรับสมดุลตัวเองรักษาความสูงเป็นลอการิทึม การค้นหา แทรก และลบจึงเป็น O(log n) ในกรณีเลวร้ายที่สุด

คำตอบ

B · ความสูง O(log n) ผ่านการปรับสมดุลใหม่
4.โครงสร้างข้อมูล

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

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

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

คำตอบ

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

คำตอบ: ทางเดินออยเลอร์ ไม่มีวงจร

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

ดีกรี

deg(A) = 1, deg(B) = 2, deg(C) = 2, deg(D) = 4, deg(E) = 2, deg(F) = 1, deg(G) = 4

จุดยอดคี่

A, F → 2
ทางเดินออยเลอร์ ไม่มีวงจร

คำตอบ

ทางเดินออยเลอร์ ไม่มีวงจร

ทางเดินออยเลอร์เริ่มที่จุดยอดคี่จุดหนึ่งและจบที่อีกจุดหนึ่ง

6.ทฤษฎีกราฟ

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

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

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

1. BC (1)
2. GB (2)
3. GD (6)
4. AB (7)
5. CE (8)
6. DF (10)

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

DF

คำตอบ

เส้นเชื่อม DF

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