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

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

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

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

ความสัมพันธ์เวียนเกิด T(n) = 2T(n/2) + n log n มีผลเฉลยเป็นเท่าใด

  1. AΘ(n log² n)
  2. BΘ(n)
  3. CΘ(n log n)
  4. DΘ(n²)
3.โครงสร้างข้อมูลปานกลาง

ความสูงในกรณีเลวร้ายที่สุดของ binary search tree ที่มี n โหนดคือเท่าใด ถ้าแทรกคีย์ตามลำดับที่เรียงแล้ว

  1. A√n
  2. Blog₂ n
  3. C1
  4. Dn (กลายเป็นลิงก์ลิสต์)
4.โครงสร้างข้อมูลยาก

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

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

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

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

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

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

3สารละลาย

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

คำตอบ: A · O(n)

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

ถ้าผลรวมน้อยเกินไปตัวชี้ซ้ายเลื่อนไปขวา ถ้ามากเกินไปตัวชี้ขวาเลื่อนไปซ้าย จึงมีไม่เกิน n ขั้น

คำตอบ

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

คำตอบ: A · Θ(n log² n)

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

ระดับที่ k ทำงานประมาณ n log(n / 2ᵏ) และผลรวมตลอด log n ระดับได้ Θ(n log² n) ซึ่งเป็นกรณีที่สองแบบขยายของทฤษฎีบทหลัก

คำตอบ

A · Θ(n log² n)
3.โครงสร้างข้อมูล

คำตอบ: D · n (กลายเป็นลิงก์ลิสต์)

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

การแทรกตามลำดับสร้างต้นไม้เสื่อมที่มีความสูง n ทำให้การค้นหาเป็น O(n) ต้นไม้สมดุลป้องกันเรื่องนี้

คำตอบ

D · n (กลายเป็นลิงก์ลิสต์)
4.โครงสร้างข้อมูล

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

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

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

คำตอบ

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

คำตอบ: L = 14

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

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

L + 24 = 2(L + 6) − 2
L = 14

คำตอบ

L = 14

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

6.ทฤษฎีกราฟ

คำตอบ: N = 2

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

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

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

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

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

คำตอบ

N = 2

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