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

ใบงาน อัลกอริทึมและความซับซ้อน ฟรีสำหรับพิมพ์: 8 ข้อ ตั้งแต่ระดับง่ายถึงระดับข้อสอบจริง พร้อมเฉลย พิมพ์หรือบันทึกเป็น PDF ได้

ใบงานใหม่ฝึกออนไลน์พร้อมคำใบ้

สำหรับผู้สอน: พิมพ์ ทำสำเนา และใช้ในชั้นเรียนได้ฟรี ใบงานใหม่แต่ละชุดมีค่าตัวเลขใหม่และเฉลยของตัวเอง หากใส่ลิงก์ไปยัง ExamProblems ในหน้ารายวิชาของคุณ เราจะขอบคุณมาก

ชื่อ: ____________________   วันที่: ____________

1.ง่าย

การเข้าถึงสมาชิกในอาร์เรย์ด้วยดัชนีใช้เวลา

  1. AO(1)
  2. BO(n²)
  3. CO(log n)
  4. DO(n)
2.ง่าย

ความซับซ้อนเชิงเวลาในกรณีดีที่สุดของ insertion sort บนอาร์เรย์ที่เรียงแล้วคือเท่าใด

  1. AO(n log n)
  2. BO(n)
  3. CO(1)
  4. DO(n²)
3.ง่าย

อัลกอริทึมคืออะไร

  1. Aภาษาโปรแกรมที่ออกแบบมาสำหรับเขียนสูตรทางคณิตศาสตร์
  2. Bโปรแกรมคอมพิวเตอร์ใด ๆ ที่มีส่วนต่อประสานกราฟิก
  3. Cโครงสร้างข้อมูลที่เก็บตัวเลข
  4. Dลำดับขั้นตอนจำกัดที่นิยามชัดเจนซึ่งแก้ปัญหาหนึ่ง
4.ปานกลาง

อัลกอริทึมละโมบ (greedy) คือ

  1. Aใช้การเรียกซ้ำเท่านั้น
  2. Bลองทุกคำตอบที่เป็นไปได้
  3. Cให้คำตอบที่เหมาะสมที่สุดเสมอ
  4. Dเลือกทางที่ดีที่สุดเฉพาะที่ในแต่ละขั้น
5.ปานกลาง

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

  1. AO(n)
  2. BO(n log n)
  3. CO(2ⁿ)
  4. DO(n²)
6.ปานกลาง

ความซับซ้อนเชิงเวลาของอัลกอริทึม Bellman–Ford บนกราฟที่มี V จุดยอดและ E เส้นเชื่อมคือเท่าใด

  1. AO(V + E)
  2. BO(E log V)
  3. CO(V × E)
  4. DO(V³ × E)
7.ยาก

การคูณแบบ Karatsuba ตรงตาม T(n) = 3T(n/2) + O(n) ผลเฉลยคืออะไร

  1. AΘ(n log n)
  2. BΘ(nlog₂ 3) ประมาณ n1.585
  3. CΘ(n3)
  4. DΘ(n²)
8.ยาก

โดยใช้ทฤษฎีบทหลัก T(n) = 8T(n/2) + O(n²) มีผลเฉลยเป็น

  1. AΘ(n² log n)
  2. BΘ(n log n)
  3. CΘ(n²)
  4. DΘ(n³)

เฉลย

  1. 1. A · O(1)
  2. 2. B · O(n)
  3. 3. D · ลำดับขั้นตอนจำกัดที่นิยามชัดเจนซึ่งแก้ปัญหาหนึ่ง
  4. 4. D · เลือกทางที่ดีที่สุดเฉพาะที่ในแต่ละขั้น
  5. 5. D · O(n²)
  6. 6. C · O(V × E)
  7. 7. B · Θ(nlog₂ 3) ประมาณ n1.585
  8. 8. D · Θ(n³)

เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com