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

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

ฟังก์ชันหนึ่งรันลูป n รอบ แล้วรันอีกลูป n รอบแยกต่างหาก ความซับซ้อนเชิงเวลาของมันคือเท่าใด

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

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

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

ต้นทุนของการแทรกสมาชิกตรงกลางอาร์เรย์ที่มี n สมาชิกคือเท่าใด

  1. AO(n²) เพราะแต่ละสมาชิกย้าย n ครั้ง
  2. BO(log n) เพราะการค้นหาแบบทวิภาค
  3. CO(1) เพราะทราบดัชนี
  4. DO(n) เพราะสมาชิกหลังจากนั้นต้องเลื่อน
4.โครงสร้างข้อมูลยาก

การแทรกคีย์ในต้นไม้ AVL ทำให้ต้นไม้ย่อยซ้ายของโหนดสูงเกินไป และคีย์ใหม่อยู่ในต้นไม้ย่อยซ้ายของลูกซ้าย (กรณีซ้าย–ซ้าย) ใช้วิธีแก้ใด

  1. Aหมุนซ้ายหนึ่งครั้งที่โหนดที่ไม่สมดุล
  2. Bหมุนขวาหนึ่งครั้งที่โหนดที่ไม่สมดุล
  3. Cเปลี่ยนสีโหนดและลูกของมัน
  4. Dหมุนซ้ายที่ลูก แล้วหมุนขวาที่โหนด
5.ทฤษฎีกราฟปานกลาง
ABCDEFGวงจรออยเลอร์ทางเดินออยเลอร์ ไม่มีวงจรไม่ใช่ทั้งสองอย่าง

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

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

ขั้นตอนวิธีของไดก์สตราเริ่มจาก A ให้คลิกจุดยอดที่ถูกยืนยัน (ทำให้เป็นค่าถาวร) ในรอบที่ 4 โดย A เองคือรอบที่ 1

เริ่มต้น: Aรอบ 4
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F

3สารละลาย

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

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

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

n + n = 2n และตัดตัวคูณคงที่ทิ้ง ฟังก์ชันนี้จึงเป็น O(n)

คำตอบ

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

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

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

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

คำตอบ

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

คำตอบ: D · O(n) เพราะสมาชิกหลังจากนั้นต้องเลื่อน

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

สมาชิกทั้งหมดหลังจุดแทรกเลื่อนไปทางขวาหนึ่งตำแหน่ง ซึ่งใช้เวลาแปรผันตาม n

คำตอบ

D · O(n) เพราะสมาชิกหลังจากนั้นต้องเลื่อน
4.โครงสร้างข้อมูล

คำตอบ: B · หมุนขวาหนึ่งครั้งที่โหนดที่ไม่สมดุล

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

ในกรณีซ้าย–ซ้าย การหมุนขวาหนึ่งครั้งยกลูกซ้ายขึ้นและคืนสมดุล กรณีซิกแซกต้องหมุนสองครั้ง

คำตอบ

B · หมุนขวาหนึ่งครั้งที่โหนดที่ไม่สมดุล
5.ทฤษฎีกราฟ

คำตอบ: ไม่ใช่ทั้งสองอย่าง

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

ดีกรี

deg(A) = 1, deg(B) = 3, deg(C) = 3, deg(D) = 4, deg(E) = 2, deg(F) = 1, deg(G) = 2

จุดยอดคี่

A, B, C, F → 4
ไม่ใช่ทั้งสองอย่าง

คำตอบ

ไม่ใช่ทั้งสองอย่าง
6.ทฤษฎีกราฟ

คำตอบ: E

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

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

1. A (0): B: 11, C: 13
2. B (11): D: 24, E: 18
3. C (13)
4. E (18): F: 32
5. D (24): F: 31
6. F (31)

รอบ 4

E

คำตอบ

E

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