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

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

การเรียกซ้ำของ merge sort สำหรับอาร์เรย์ n สมาชิกมีกี่ระดับ

  1. Aประมาณ n
  2. Bประมาณ √n
  3. Cประมาณ n / 2
  4. Dประมาณ log₂ n
2.อัลกอริทึมและความซับซ้อนยาก

จะเกิดอะไรขึ้นถ้ามีผู้พบอัลกอริทึมเวลาพหุนามสำหรับปัญหา NP-complete หนึ่งข้อ

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

แทรกคีย์ 50, 30, 70, 20, 40 ตามลำดับนี้ลงใน binary search tree ว่าง ลูกซ้ายของ 30 คืออะไร

  1. A40
  2. B70
  3. C20
  4. D50
4.โครงสร้างข้อมูลยาก

Fenwick tree (binary indexed tree) บนอาร์เรย์ที่มีตัวเลข n ตัว รองรับการดำเนินการใดใน O(log n)

  1. Aการหามัธยฐานใน O(1)
  2. Bการแทรกสมาชิกที่ตำแหน่งใดก็ได้
  3. Cคำถามผลรวมคำนำหน้าและการอัปเดตสมาชิกเดียว
  4. Dการเรียงอาร์เรย์และการค้นหาแบบทวิภาค
5.ทฤษฎีกราฟปานกลาง

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

4 × deg 43 × deg 2
L =
6.ทฤษฎีกราฟยาก
ABCDE

มีวอล์กความยาว 3 จาก A ไป E กี่วอล์ก วอล์กอาจซ้ำจุดยอดและเส้นเชื่อมได้ เรียกจำนวนนี้ว่า N

M = เมทริกซ์ประชิดL = 3
N =

3สารละลาย

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

คำตอบ: D · ประมาณ log₂ n

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

การแบ่งครึ่งจาก n ลงถึง 1 ใช้ประมาณ log₂ n ระดับ และแต่ละระดับทำงานผสาน O(n) ได้ O(n log n)

คำตอบ

D · ประมาณ log₂ n
2.อัลกอริทึมและความซับซ้อน

คำตอบ: A · ทุกปัญหาใน NP แก้ได้ในเวลาพหุนาม ดังนั้น P = NP

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

เนื่องจากทั้ง NP ลดรูปมาเป็นปัญหา NP-complete ใด ๆ ได้ในเวลาพหุนาม อัลกอริทึมเร็วสำหรับข้อหนึ่งจึงให้อัลกอริทึมเร็วสำหรับทั้งหมด

คำตอบ

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

คำตอบ: C · 20

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

20 น้อยกว่า 50 และน้อยกว่า 30 จึงเป็นลูกซ้ายของ 30 ส่วน 40 เป็นลูกขวา

คำตอบ

C · 20
4.โครงสร้างข้อมูล

คำตอบ: C · คำถามผลรวมคำนำหน้าและการอัปเดตสมาชิกเดียว

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

Fenwick tree เก็บผลรวมบางส่วนของช่วงที่กำหนดโดยบิตต่ำของแต่ละดัชนี ทั้งผลรวมคำนำหน้าและการอัปเดตจุดจึงใช้ O(log n)

คำตอบ

C · คำถามผลรวมคำนำหน้าและการอัปเดตสมาชิกเดียว
5.ทฤษฎีกราฟ

คำตอบ: L = 10

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

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

L + 22 = 2(L + 7) − 2
L = 10

คำตอบ

L = 10

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

6.ทฤษฎีกราฟ

คำตอบ: N = 3

ดีกรี: ดีกรีของจุดยอดคือจำนวนเส้นเชื่อมที่มาบรรจบที่จุดนั้น เส้นเชื่อมแต่ละเส้นมีสองปลาย ดังนั้นผลบวกของดีกรีเท่ากับสองเท่าของจำนวนเส้นเชื่อม: Σ deg(v) = 2|E| (เล็มมาการจับมือ) ดังนั้นจำนวนจุดยอดที่มีดีกรีคี่เป็นจำนวนคู่ Kn มีเส้นเชื่อม n(n − 1)/2 เส้น กราฟปรกติดีกรี k ที่มี n จุดยอดมี nk/2 เส้น และต้นไม้ที่มี n จุดยอดมี n − 1 เส้นเชื่อม

เมทริกซ์ประชิด

A: 0 1 1 0 0
B: 1 0 1 1 1
C: 1 1 0 0 1
D: 0 1 0 0 1
E: 0 1 1 1 0

อีกหนึ่งก้าว

(M³)AE = 2·0 + 1·1 + 1·1 + 1·1 + 2·0 = 3

คำตอบ

N = 3

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