โครงสร้างข้อมูลและอัลกอริทึม: แบบฝึกหัดและข้อสอบเก่า

สัญกรณ์ Big-O เวลาทำงานของอัลกอริทึมทั่วไป และข้อดีข้อเสียของอาร์เรย์ ลิงก์ลิสต์ ต้นไม้ ตารางแฮช และกราฟ

ฝึกรายวิชานี้ฟรีฝึกรายวิชานี้ทำข้อสอบจำลองโจทย์ฟรีวันละ 5 ข้อ ไม่ต้องใช้บัตร

ชุดสรุปเร่งรัด (PDF)สรุปสูตร ขั้นตอนวิธีทำ และโจทย์ฝึกพร้อมเฉลยละเอียด พร้อมพิมพ์

หัวข้อในรายวิชานี้

  1. อัลกอริทึมและความซับซ้อนศัพท์สำคัญและข้อเท็จจริง · การประยุกต์ใช้แนวคิด · กรณีศึกษาและการวิเคราะห์ปรนัย
  2. โครงสร้างข้อมูลศัพท์สำคัญและข้อเท็จจริง · การประยุกต์ใช้แนวคิด · กรณีศึกษาและการวิเคราะห์ปรนัย
  3. ทฤษฎีกราฟดีกรีและเส้นเชื่อม · ทางเดินออยเลอร์และต้นไม้ · เส้นทางที่สั้นที่สุดและต้นไม้ทอดข้ามโจทย์คำนวณ

เทคนิคทำข้อสอบวิชา โครงสร้างข้อมูลและอัลกอริทึม

  • สำหรับลูปซ้อนกัน ให้คูณจำนวนรอบ สำหรับลูปที่ต่อเนื่องกัน ให้เก็บพจน์ที่ใหญ่กว่า
  • รู้ต้นทุนของการค้นหา การแทรก และการลบของแต่ละโครงสร้างข้อมูล
  • การลดข้อมูลนำเข้าลงครึ่งหนึ่งในแต่ละขั้นให้เวลาแบบลอการิทึม

ตัวอย่างวิธีทำ

อัลกอริทึมและความซับซ้อนง่าย

สัญกรณ์ใดใช้อธิบายขอบเขตบนของอัตราการเติบโต

  1. ABig Omega
  2. BLittle omega
  3. CBig O
  4. DBig Theta
แสดงคำใบ้
  1. "มากที่สุดเท่ากับ"
  2. ตอนนี้ขีดฆ่าคำตอบที่ผิดสองข้อแล้ว หนึ่งในสองข้อที่เหลือเป็นคำตอบที่ถูก
แสดงคำตอบและคำอธิบาย

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

O ให้ขอบเขตบน Ω ให้ขอบเขตล่าง และ Θ ให้ขอบเขตที่แน่นพอดี

คำตอบ

C · Big O
โครงสร้างข้อมูลปานกลาง

extract-min ใน min-heap ทวิภาคทำงานอย่างไร

  1. Aลบสมาชิกสุดท้ายของอาร์เรย์
  2. Bย้ายสมาชิกสุดท้ายไปที่รากและเลื่อนลง (sift down)
  3. Cลบรากและเลื่อนสมาชิกทั้งหมดไปทางซ้ายหนึ่งตำแหน่ง
  4. Dค้นหาใบทั้งหมดเพื่อหาค่าต่ำสุดใหม่
แสดงคำใบ้
  1. รักษาต้นไม้ให้สมบูรณ์ แล้วซ่อมลำดับ
  2. ตอนนี้ขีดฆ่าคำตอบที่ผิดสองข้อแล้ว หนึ่งในสองข้อที่เหลือเป็นคำตอบที่ถูก
แสดงคำตอบและคำอธิบาย

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

สมาชิกสุดท้ายเติมช่องว่างที่ราก และสลับกับลูกที่เล็กกว่าจนคุณสมบัติฮีปเป็นจริง ใช้ O(log n)

คำตอบ

B · ย้ายสมาชิกสุดท้ายไปที่รากและเลื่อนลง (sift down)

การฝึกทำงานอย่างไร

  • “ฝึกรายวิชานี้” ผสมโจทย์จากทุกหัวข้อของวิชา เหมือนข้อสอบจริง
  • โจทย์ทุกข้อใช้ค่าใหม่ คุณจึงเรียนรู้วิธีทำ ไม่ใช่จำคำตอบ
  • ติดขัดใช่ไหม เปิดคำใบ้เล็ก ๆ ก่อน และเปิดคำอธิบายฉบับเต็มเมื่อจำเป็นเท่านั้น
  • ข้อสอบจำลองจับเวลาและไม่มีคำใบ้ และคุณจะได้คะแนนและการทบทวนฉบับเต็มเมื่อจบ

รายวิชาที่เกี่ยวข้อง

พื้นฐานวิทยาการคอมพิวเตอร์คณิตศาสตร์ไม่ต่อเนื่องเครือข่ายคอมพิวเตอร์
ฝึกรายวิชานี้ฟรีฝึกรายวิชานี้ทำข้อสอบจำลองโจทย์ฟรีวันละ 5 ข้อ ไม่ต้องใช้บัตร