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

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

อัลกอริทึม Floyd–Warshall คำนวณอะไรและเร็วเพียงใด

  1. Aลำดับทอพอโลยีใน O(V²)
  2. Bเส้นทางสั้นที่สุดจากจุดยอดต้นทางหนึ่งไปยังจุดยอดอื่นทั้งหมดใน O(V + E)
  3. Cเส้นทางสั้นที่สุดระหว่างจุดยอดทุกคู่ใน O(V³)
  4. Dต้นไม้ทอดข้ามที่น้อยที่สุดใน O(E log V)
2.อัลกอริทึมและความซับซ้อนยาก

Insertion sort ทำงานใน O(n) บนอินพุตที่เรียงแล้ว สิ่งนี้ขัดกับขอบเขตล่าง Ω(n log n) ของการเรียงแบบเปรียบเทียบหรือไม่

  1. Aขัด แต่เฉพาะอาร์เรย์ที่สั้นกว่า 100
  2. Bไม่ขัด ขอบเขตล่างใช้กับกรณีเลวร้ายที่สุดเหนือทุกอินพุต ไม่ใช่ทุกอินพุต
  3. Cขัด ดังนั้นขอบเขตล่างจึงผิด
  4. Dไม่ขัด เพราะ insertion sort ไม่ใช่การเรียงแบบเปรียบเทียบ
3.โครงสร้างข้อมูลปานกลาง

โปรแกรมที่ทำงานอยู่ใช้โครงสร้างข้อมูลใดติดตามการเรียกฟังก์ชันที่กำลังทำงานและตัวแปรท้องถิ่น

  1. Aคิวหน่วยความจำฮีป
  2. Bสแตกการเรียก (call stack)
  3. Cตารางแฮชของฟังก์ชัน
  4. Dbinary search tree ของเฟรม
4.โครงสร้างข้อมูลยาก

ในตารางแฮชที่ใช้ open addressing เหตุใดการลบจึงมักทำด้วยเครื่องหมาย "tombstone"

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

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

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

จงหาน้ำหนักรวม W ของต้นไม้ทอดข้ามค่าน้อยที่สุดของกราฟถ่วงน้ำหนัก

|V| = 7|E| = 9
W =

3สารละลาย

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

คำตอบ: C · เส้นทางสั้นที่สุดระหว่างจุดยอดทุกคู่ใน O(V³)

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

Floyd–Warshall เป็นอัลกอริทึมการโปรแกรมพลวัตที่อนุญาตให้ทีละจุดยอดเป็นจุดผ่านกลาง โดยใช้เวลา O(V³)

คำตอบ

C · เส้นทางสั้นที่สุดระหว่างจุดยอดทุกคู่ใน O(V³)
2.อัลกอริทึมและความซับซ้อน

คำตอบ: B · ไม่ขัด ขอบเขตล่างใช้กับกรณีเลวร้ายที่สุดเหนือทุกอินพุต ไม่ใช่ทุกอินพุต

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

ขอบเขตนี้บอกว่าการเรียงแบบเปรียบเทียบทุกชนิดต้องใช้ประมาณ n log n การเปรียบเทียบกับอินพุตบางแบบขนาด n อินพุตพิเศษอาจเร็วกว่ามาก

คำตอบ

B · ไม่ขัด ขอบเขตล่างใช้กับกรณีเลวร้ายที่สุดเหนือทุกอินพุต ไม่ใช่ทุกอินพุต
3.โครงสร้างข้อมูล

คำตอบ: B · สแตกการเรียก (call stack)

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

แต่ละการเรียก push เฟรมสแตกและแต่ละการคืนค่า pop ออก จึงเป็นเหตุที่การเรียกล่าสุดเสร็จก่อน

คำตอบ

B · สแตกการเรียก (call stack)
4.โครงสร้างข้อมูล

คำตอบ: B · การทำให้ช่องว่างอาจทำลายลำดับการตรวจสอบสำหรับคีย์อื่น

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

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

คำตอบ

B · การทำให้ช่องว่างอาจทำลายลำดับการตรวจสอบสำหรับคีย์อื่น
5.ทฤษฎีกราฟ

คำตอบ: วงจรออยเลอร์

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

ดีกรี

deg(A) = 2, deg(B) = 2, deg(C) = 2, deg(D) = 2, deg(E) = 2

จุดยอดคี่

0
วงจรออยเลอร์

คำตอบ

วงจรออยเลอร์
6.ทฤษฎีกราฟ

คำตอบ: W = 68

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

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

DE (3): เลือก
GD (9): เลือก
CE (10): เลือก
AB (12): เลือก
GB (14): เลือก
BD (15): ข้าม ทำให้เกิดวัฏจักร
AC (17): ข้าม ทำให้เกิดวัฏจักร
BC (19): ข้าม ทำให้เกิดวัฏจักร
DF (20): เลือก

น้ำหนักรวม

W = 3 + 9 + 10 + 12 + 14 + 20 = 68

คำตอบ

W = 68

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