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

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

เหตุใดรูทีนการเรียงลำดับในไลบรารีจำนวนมากจึงเปลี่ยนไปใช้ insertion sort กับอาร์เรย์ย่อยที่เล็กมาก

  1. AInsertion sort เป็น O(n log n) ในกรณีเลวร้ายที่สุด
  2. Bอัลกอริทึมแบบเรียกซ้ำจัดการอาร์เรย์ที่เล็กกว่า 10 สมาชิกไม่ได้
  3. CInsertion sort มีภาระเพิ่มน้อยและเร็วกับอินพุตที่เล็กหรือเกือบเรียงแล้ว
  4. DInsertion sort ใช้หน่วยความจำน้อยกว่าอัลกอริทึมการเรียงลำดับอื่นทุกตัวกับอินพุตใหญ่
2.อัลกอริทึมและความซับซ้อนยาก

ข้อใดเกี่ยวกับ P และ NP ถูกต้อง

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

ทราย (trie หรือ prefix tree) มีประสิทธิภาพเป็นพิเศษสำหรับ

  1. Aการหาเส้นทางสั้นที่สุด
  2. Bการเรียงตัวเลข
  3. Cการเก็บเมทริกซ์
  4. Dการค้นหาด้วยคำนำหน้า เช่น autocomplete
4.โครงสร้างข้อมูลยาก

เหตุใดจึงลบสมาชิกออกจาก Bloom filter มาตรฐานโดยเพียงล้างบิตของมันไม่ได้

  1. Aบิตเหล่านั้นอาจเป็นของสมาชิกอื่นด้วย ซึ่งจะทำให้เกิดผลลบเท็จ
  2. BBloom filter เก็บสมาชิกเต็มรูป ซึ่งเมื่อถูกแฮชแล้วหาไม่พบอีก
  3. Cการลบจะเพิ่มอัตราผลบวกเท็จเป็น 100%
  4. Dบิตใน Bloom filter เปลี่ยนไม่ได้หลังสร้าง
5.ทฤษฎีกราฟปานกลาง

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

3 × deg 33 × deg 44 × deg 5
L =
6.ทฤษฎีกราฟยาก
611514914411ABCDEF

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

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

3สารละลาย

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

คำตอบ: C · Insertion sort มีภาระเพิ่มน้อยและเร็วกับอินพุตที่เล็กหรือเกือบเรียงแล้ว

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

เมื่อ n น้อย ลูปง่าย ๆ ของ insertion sort ชนะภาระการเรียกซ้ำของ quicksort หรือ merge sort แม้จะเป็น O(n²)

คำตอบ

C · Insertion sort มีภาระเพิ่มน้อยและเร็วกับอินพุตที่เล็กหรือเกือบเรียงแล้ว
2.อัลกอริทึมและความซับซ้อน

คำตอบ: A · ทุกปัญหาใน P อยู่ใน NP ด้วย

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

P ⊆ NP: ถ้าแก้ปัญหาได้เร็ว ก็ตรวจสอบคำตอบได้เร็ว ส่วนคำถามว่า P = NP หรือไม่ยังเป็นปัญหาเปิด

คำตอบ

A · ทุกปัญหาใน P อยู่ใน NP ด้วย
3.โครงสร้างข้อมูล

คำตอบ: D · การค้นหาด้วยคำนำหน้า เช่น autocomplete

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

Trie เก็บสตริงด้วยอักขระตามเส้นทาง การค้นหาและคำถามคำนำหน้าจึงใช้เวลาแปรผันตามความยาวคีย์

คำตอบ

D · การค้นหาด้วยคำนำหน้า เช่น autocomplete
4.โครงสร้างข้อมูล

คำตอบ: A · บิตเหล่านั้นอาจเป็นของสมาชิกอื่นด้วย ซึ่งจะทำให้เกิดผลลบเท็จ

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

การล้างบิตที่ใช้ร่วมกันจะทำให้สมาชิกอื่นดูเหมือนไม่อยู่ counting Bloom filter เก็บตัวนับแทนบิตเพื่อให้ลบได้

คำตอบ

A · บิตเหล่านั้นอาจเป็นของสมาชิกอื่นด้วย ซึ่งจะทำให้เกิดผลลบเท็จ
5.ทฤษฎีกราฟ

คำตอบ: L = 23

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

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

L + 41 = 2(L + 10) − 2
L = 23

คำตอบ

L = 23

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

6.ทฤษฎีกราฟ

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

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

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

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

A (0): B: 6
B (6): C: 7, D: 21, E: 17
C (7)
E (17): F: 21
D (21)
F (21)

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

A → B → D
d(D) = 21

คำตอบ

d(D) = 21

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