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

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

อัลกอริทึมของ Prim สร้างต้นไม้ทอดข้ามที่น้อยที่สุดอย่างไร

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

ต้นทุนแบบกระจายของการเพิ่มค่าตัวนับฐานสองหนึ่งครั้งคือเท่าใด เมื่อการเพิ่มหนึ่งครั้งอาจพลิกหลายบิต

  1. AO(n log n) ต่อการเพิ่มหนึ่งครั้ง
  2. BO(1) ต่อการเพิ่มหนึ่งครั้ง
  3. CO(n) ต่อการเพิ่มหนึ่งครั้ง
  4. DO(log n) ต่อการเพิ่มหนึ่งครั้ง
3.โครงสร้างข้อมูลปานกลาง

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

  1. Aสแตก
  2. Bลิงก์ลิสต์ที่ไม่เรียงลำดับ
  3. Cตารางแฮช
  4. Dbinary search tree แบบสมดุล
4.โครงสร้างข้อมูลยาก

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

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

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

K4
H =
6.ทฤษฎีกราฟยาก
1571471166615ABCDEFG

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

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

3สารละลาย

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

คำตอบ: A · ขยายต้นไม้ต้นเดียวจากจุดยอดเริ่มต้น โดยเพิ่มเส้นเชื่อมที่ถูกที่สุดที่ออกจากต้นไม้

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

อัลกอริทึมของ Prim ที่ใช้คิวลำดับความสำคัญของเส้นเชื่อมที่ข้ามขอบเขตทำงานใน O(E log V) เมื่อใช้ฮีปไบนารี

คำตอบ

A · ขยายต้นไม้ต้นเดียวจากจุดยอดเริ่มต้น โดยเพิ่มเส้นเชื่อมที่ถูกที่สุดที่ออกจากต้นไม้
2.อัลกอริทึมและความซับซ้อน

คำตอบ: B · O(1) ต่อการเพิ่มหนึ่งครั้ง

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

ตลอดการเพิ่ม n ครั้ง บิต i พลิกประมาณ n / 2ⁱ ครั้ง ผลรวมจึงน้อยกว่า 2n การพลิก เฉลี่ย O(1) ต่อครั้ง

คำตอบ

B · O(1) ต่อการเพิ่มหนึ่งครั้ง
3.โครงสร้างข้อมูล

คำตอบ: D · binary search tree แบบสมดุล

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

BST สมดุลให้การค้นหา O(log n) และรักษาลำดับคีย์ การท่อง in-order และคำถามช่วงจึงทำได้ง่าย ตารางแฮชกระจายคีย์

คำตอบ

D · binary search tree แบบสมดุล
4.โครงสร้างข้อมูล

คำตอบ: A · เพื่อหลีกเลี่ยงการปรับขนาดซ้ำเมื่อ push และ pop สลับกันใกล้ขอบเขต

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

การหดที่ครึ่งหนึ่งอาจกระตุ้นการปรับขนาดทุกการดำเนินการในลำดับเช่นนั้น ช่องว่างระหว่าง 1/4 กับเต็มรักษาต้นทุนกระจายเป็น O(1)

คำตอบ

A · เพื่อหลีกเลี่ยงการปรับขนาดซ้ำเมื่อ push และ pop สลับกันใกล้ขอบเขต
5.ทฤษฎีกราฟ

คำตอบ: H = 3

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

นับ

H = (4 − 1)!/2 = 6/2 = 3

คำตอบ

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

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

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

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

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

A (0): B: 15
B (15): C: 22, D: 29, G: 21
G (21): D: 27, E: 36
C (22)
D (27): F: 34
F (34)
E (36)

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

A → B → G → D → F
d(F) = 34

คำตอบ

d(F) = 34

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