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

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

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

การคำนวณจำนวนฟีโบนักชีตัวที่ n ด้วยลูปที่เก็บเพียงสองค่าล่าสุดมีต้นทุนด้านเวลาและพื้นที่เท่าใด

  1. Aเวลา O(log n) และพื้นที่ O(n)
  2. Bเวลา O(2ⁿ) และพื้นที่ O(1)
  3. Cเวลา O(n) และพื้นที่ O(1)
  4. Dเวลา O(n) และพื้นที่ O(n)
3.โครงสร้างข้อมูลปานกลาง

ต้นไม้ AVL รักษาเงื่อนไขสมดุลใดที่ทุกโหนด

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

การกลับลิงก์ลิสต์เชิงเดี่ยวในที่เดิมมีต้นทุนด้านเวลาและพื้นที่เพิ่มเติมเท่าใด

  1. Aเวลา O(1) และพื้นที่เพิ่ม O(1)
  2. Bเวลา O(n) และพื้นที่เพิ่ม O(n)
  3. Cเวลา O(n) และพื้นที่เพิ่ม O(1)
  4. Dเวลา O(n log n) และพื้นที่เพิ่ม O(1)
5.ทฤษฎีกราฟปานกลาง
ABCDEวงจรออยเลอร์ทางเดินออยเลอร์ ไม่มีวงจรไม่ใช่ทั้งสองอย่าง

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

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

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

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

3สารละลาย

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

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

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

การเติมตารางจาก 0 ถึง n ใช้การบวกหนึ่งครั้งต่อช่อง งานจึงเป็นเชิงเส้นแทนที่จะเป็นเอกซ์โพเนนเชียล

คำตอบ

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

คำตอบ: C · เวลา O(n) และพื้นที่ O(1)

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

แต่ละขั้นต้องการเพียงสองค่าก่อนหน้า ตารางของวิธีล่างขึ้นบนจึงแทนที่ด้วยตัวแปรสองตัวได้

คำตอบ

C · เวลา O(n) และพื้นที่ O(1)
3.โครงสร้างข้อมูล

คำตอบ: C · ความสูงของต้นไม้ย่อยซ้ายและขวาต่างกันไม่เกิน 1

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

ตัวประกอบสมดุล (ความสูงซ้าย − ความสูงขวา) ต้องเป็น −1, 0 หรือ 1 การหมุนคืนสมดุลหลังการแทรกและการลบ

คำตอบ

C · ความสูงของต้นไม้ย่อยซ้ายและขวาต่างกันไม่เกิน 1
4.โครงสร้างข้อมูล

คำตอบ: C · เวลา O(n) และพื้นที่เพิ่ม O(1)

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

การเก็บตัวชี้สามตัว (previous, current, next) ทำให้กลับแต่ละลิงก์ในรอบเดียวโดยไม่จัดสรรโหนดใหม่

คำตอบ

C · เวลา O(n) และพื้นที่เพิ่ม O(1)
5.ทฤษฎีกราฟ

คำตอบ: ทางเดินออยเลอร์ ไม่มีวงจร

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

ดีกรี

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

จุดยอดคี่

C, D → 2
ทางเดินออยเลอร์ ไม่มีวงจร

คำตอบ

ทางเดินออยเลอร์ ไม่มีวงจร

ทางเดินออยเลอร์เริ่มที่จุดยอดคี่จุดหนึ่งและจบที่อีกจุดหนึ่ง

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
B: 0 0 1 1 1
C: 1 1 0 0 1
D: 0 1 0 0 1
E: 0 1 1 1 0

เพื่อนบ้านร่วม

(M²)DD = 0·0 + 1·1 + 0·0 + 0·0 + 1·1 = 2

คำตอบ

N = 2

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