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

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

ความซับซ้อนเชิงเวลาของอัลกอริทึม Bellman–Ford บนกราฟที่มี V จุดยอดและ E เส้นเชื่อมคือเท่าใด

  1. AO(E log V)
  2. BO(V³ × E)
  3. CO(V × E)
  4. DO(V + E)
2.อัลกอริทึมและความซับซ้อนยาก

นิยามใดของคลาส NP ถูกต้อง

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

ใน min-heap ทวิภาคที่เก็บในอาร์เรย์ (ดัชนีเริ่มที่ 0) ลูกของโหนดที่ดัชนี i อยู่ที่

  1. Ai/2 และ i/2 + 1
  2. B2i และ 2i + 1
  3. Ci + 1 และ i + 2
  4. D2i + 1 และ 2i + 2
4.โครงสร้างข้อมูลยาก

เหตุใดเซิร์ฟเวอร์จึงเลือกฟังก์ชันแฮชแบบสุ่มจากตระกูลสากล (universal family)

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

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

|V| = 20|E| = 25
k =
6.ทฤษฎีกราฟยาก
2127171496181110ABCDEFG

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

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

3สารละลาย

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

คำตอบ: C · O(V × E)

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

แต่ละรอบจาก V − 1 รอบผ่อนคลายเส้นเชื่อมทั้ง E เส้น ได้ O(VE) แลกกับการรองรับน้ำหนักเส้นเชื่อมติดลบ

คำตอบ

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

คำตอบ: C · ปัญหาการตัดสินใจที่คำตอบ "ใช่" ตรวจสอบได้ในเวลาพหุนามเมื่อมีใบรับรอง

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

สำหรับปัญหา NP คำตอบที่เสนอ (ใบรับรอง) ตรวจได้อย่างรวดเร็ว เช่น การตรวจว่าการกำหนดค่าที่ให้มาทำให้สูตรบูลีนเป็นจริง

คำตอบ

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

คำตอบ: D · 2i + 1 และ 2i + 2

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

สำหรับอาร์เรย์ที่เริ่มที่ 0 ลูกซ้ายอยู่ที่ 2i + 1 ลูกขวาที่ 2i + 2 และแม่ที่ ⌊(i − 1)/2⌋

คำตอบ

D · 2i + 1 และ 2i + 2
4.โครงสร้างข้อมูล

คำตอบ: C · เพื่อทำให้ผู้โจมตีเลือกคีย์จำนวนมากที่ชนกันทั้งหมดได้ยากมาก

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

ด้วยการแฮชสากล จำนวนการชนกันคาดหมายน้อยสำหรับเซตคีย์ใด ๆ เพราะผู้โจมตีไม่ทราบว่าเลือกฟังก์ชันใด

คำตอบ

C · เพื่อทำให้ผู้โจมตีเลือกคีย์จำนวนมากที่ชนกันทั้งหมดได้ยากมาก
5.ทฤษฎีกราฟ

คำตอบ: k = 6

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

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

20 − 1 = 19

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

k = 25 − 19 = 6

คำตอบ

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

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

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

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

1. DF (6)
2. DE (9)
3. GE (10)
4. CE (14)
5. BC (7)
6. AB (2)

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

DE

คำตอบ

เส้นเชื่อม DE

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