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

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

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

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

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

1.ง่าย

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

  1. ABig Theta
  2. BLittle omega
  3. CBig Omega
  4. DBig O
2.ง่าย

อัลกอริทึมที่มีลูปซ้อนกันสองชั้น แต่ละชั้นทำงาน n รอบ โดยทั่วไปมีความซับซ้อนเท่าใด

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

memoisation คืออะไร

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

ความซับซ้อนเชิงเวลาของอัลกอริทึมการโปรแกรมพลวัตมาตรฐานสำหรับสายอักขระย่อยร่วมที่ยาวที่สุด (LCS) ของสายอักขระที่ยาว m และ n คือเท่าใด

  1. AO(mn)
  2. BO(m + n)
  3. CO(mn log n)
  4. DO(2m+n)
5.ปานกลาง

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

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

อัลกอริทึมใดหาเส้นทางสั้นที่สุดจากต้นทางหนึ่งในกราฟที่น้ำหนักเส้นเชื่อมไม่เป็นลบ

  1. Aต้องใช้ Bellman–Ford ในทุกกรณี
  2. Bอัลกอริทึมของ Dijkstra
  3. Cการค้นหาในแนวลึก
  4. Dอัลกอริทึมของ Kruskal
7.ยาก

นิยามใดของคลาส NP ถูกต้อง

  1. Aปัญหาที่แก้ในเวลาพหุนามไม่ได้
  2. Bปัญหาการตัดสินใจที่คำตอบ "ใช่" ตรวจสอบได้ในเวลาพหุนามเมื่อมีใบรับรอง
  3. Cปัญหาที่ไม่มีอัลกอริทึมใดแก้ได้
  4. Dปัญหาที่ไม่ใช่พหุนาม
8.ยาก

ข้อใดเกี่ยวกับ P และ NP ถูกต้อง

  1. Aได้พิสูจน์แล้วว่า P ≠ NP
  2. Bปัญหา NP ตรวจสอบอย่างรวดเร็วไม่ได้
  3. CNP หมายถึง "ไม่ใช่พหุนาม"
  4. Dทุกปัญหาใน P อยู่ใน NP ด้วย

เฉลย

  1. 1. D · Big O
  2. 2. C · O(n²)
  3. 3. A · การเก็บผลลัพธ์ของการเรียกฟังก์ชันเพื่อตอบการเรียกซ้ำจากหน่วยความจำ
  4. 4. A · O(mn)
  5. 5. D · O(log n)
  6. 6. B · อัลกอริทึมของ Dijkstra
  7. 7. B · ปัญหาการตัดสินใจที่คำตอบ "ใช่" ตรวจสอบได้ในเวลาพหุนามเมื่อมีใบรับรอง
  8. 8. D · ทุกปัญหาใน P อยู่ใน NP ด้วย

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