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

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

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

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

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

  1. A50
  2. B40
  3. C70
  4. D20
4.โครงสร้างข้อมูลยาก

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

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

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

4 × deg 32 × deg 43 × deg 5
L =
6.ทฤษฎีกราฟยาก
ABCDEF

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

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

3สารละลาย

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

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

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

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

คำตอบ

C · O(n)
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.โครงสร้างข้อมูล

คำตอบ: D · 20

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

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

คำตอบ

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

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

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

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

คำตอบ

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

คำตอบ: L = 19

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

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

L + 35 = 2(L + 9) − 2
L = 19

คำตอบ

L = 19

ทางลัด: 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 0 1 0 0 0
B: 0 0 1 1 0 0
C: 1 1 0 0 1 0
D: 0 1 0 0 1 1
E: 0 0 1 1 0 1
F: 0 0 0 1 1 0

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

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

คำตอบ

N = 2

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