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

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

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

ข้อใดเกี่ยวกับการเลือกสมาชิกที่เล็กที่สุดอันดับที่ k ของอาร์เรย์ที่ไม่เรียงลำดับถูกต้อง

  1. Aการเลือกทำได้ใน O(n²) เท่านั้น
  2. BQuickselect ทำงานใน O(log n) ในกรณีเลวร้ายที่สุด เพราะเรียกซ้ำเพียงฝั่งเดียวของตัวหมุน
  3. CQuickselect ทำงานใน O(n) คาดหมาย และ median-of-medians รับประกัน O(n) ในกรณีเลวร้ายที่สุด
  4. Dการเลือกต้องใช้ Ω(n log n) เสมอเพราะต้องเรียงลำดับ
3.โครงสร้างข้อมูลปานกลาง

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

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

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

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

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

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

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

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

3สารละลาย

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

คำตอบ: A · O(2ⁿ)

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

จำนวนการเรียกเพิ่มเป็นสองเท่าในแต่ละระดับและมี n ระดับ ผลรวมจึงประมาณ 2ⁿ เช่นเดียวกับหอคอยฮานอย

คำตอบ

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

คำตอบ: C · Quickselect ทำงานใน O(n) คาดหมาย และ median-of-medians รับประกัน O(n) ในกรณีเลวร้ายที่สุด

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

งานคาดหมายของ Quickselect คือ n + n/2 + n/4 + ... = O(n) เมื่อสุ่มตัวหลัก การเลือกตัวหลักด้วย median of medians ทำให้กรณีเลวร้ายที่สุดเป็นเชิงเส้น

คำตอบ

C · Quickselect ทำงานใน O(n) คาดหมาย และ median-of-medians รับประกัน O(n) ในกรณีเลวร้ายที่สุด
3.โครงสร้างข้อมูล

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

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

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

คำตอบ

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

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

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

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

คำตอบ

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

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

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

ดีกรี

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

จุดยอดคี่

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

คำตอบ

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

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

6.ทฤษฎีกราฟ

คำตอบ: d(F) = 29

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

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

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

A (0): B: 12
B (12): C: 19, D: 15, E: 24
D (15): F: 29
C (19): E: 21
E (21)
F (29)

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

A → B → D → F
d(F) = 29

คำตอบ

d(F) = 29

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