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

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

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

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

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

1.ง่าย

ความซับซ้อนเชิงเวลาของการค้นหาแบบทวิภาค (binary search) บนอาร์เรย์ที่เรียงลำดับแล้วคือเท่าใด

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

ความซับซ้อนเชิงเวลาของการค้นหาเชิงเส้นในอาร์เรย์ที่ไม่เรียงลำดับซึ่งมี n สมาชิก (กรณีเลวร้ายที่สุด) คือเท่าใด

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

merge sort แบบมาตรฐานที่ใช้อาร์เรย์ใช้หน่วยความจำเพิ่มเติมเท่าใด

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

การเรียกซ้ำของ merge sort สำหรับอาร์เรย์ n สมาชิกมีกี่ระดับ

  1. Aประมาณ √n
  2. Bประมาณ n / 2
  3. Cประมาณ log₂ n
  4. Dประมาณ n
5.ปานกลาง

ด้วยเหรียญ 1, 3 และ 4 และยอด 6 วิธีละโมบ "หยิบเหรียญใหญ่สุดก่อน" ใช้เหรียญกี่เหรียญเมื่อเทียบกับค่าที่เหมาะสมที่สุด

  1. Aละโมบใช้ 3 เหรียญ ค่าที่เหมาะสมที่สุดคือ 3
  2. Bละโมบใช้ 3 เหรียญ ค่าที่เหมาะสมที่สุดคือ 2
  3. Cละโมบใช้ 4 เหรียญ ค่าที่เหมาะสมที่สุดคือ 3
  4. Dละโมบใช้ 2 เหรียญ ค่าที่เหมาะสมที่สุดคือ 2
6.ปานกลาง

เหตุใดรูทีนการเรียงลำดับในไลบรารีจำนวนมากจึงเปลี่ยนไปใช้ insertion sort กับอาร์เรย์ย่อยที่เล็กมาก

  1. Aอัลกอริทึมแบบเรียกซ้ำจัดการอาร์เรย์ที่เล็กกว่า 10 สมาชิกไม่ได้
  2. BInsertion sort ใช้หน่วยความจำน้อยกว่าอัลกอริทึมการเรียงลำดับอื่นทุกตัวกับอินพุตใหญ่
  3. CInsertion sort เป็น O(n log n) ในกรณีเลวร้ายที่สุด
  4. DInsertion sort มีภาระเพิ่มน้อยและเร็วกับอินพุตที่เล็กหรือเกือบเรียงแล้ว
7.ยาก

ปัญหาความสอดคล้องข้อใดต่อไปนี้ทราบว่าแก้ได้ในเวลาพหุนาม

  1. ASAT ทั่วไปบนสูตรรูปแบบนอร์มัลเชิงเชื่อม
  2. B2-SAT ซึ่งแต่ละวลีมีลิเทอรัลไม่เกินสองตัว
  3. C3-SAT ซึ่งแต่ละวลีมีลิเทอรัลสามตัวพอดี
  4. Dความสอดคล้องของวงจร
8.ยาก

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

  1. Aเวลา O(n) และพื้นที่ O(1)
  2. Bเวลา O(n) และพื้นที่ O(n)
  3. Cเวลา O(log n) และพื้นที่ O(n)
  4. Dเวลา O(2ⁿ) และพื้นที่ O(1)

เฉลย

  1. 1. B · O(log n)
  2. 2. B · O(n)
  3. 3. A · O(n)
  4. 4. C · ประมาณ log₂ n
  5. 5. B · ละโมบใช้ 3 เหรียญ ค่าที่เหมาะสมที่สุดคือ 2
  6. 6. D · Insertion sort มีภาระเพิ่มน้อยและเร็วกับอินพุตที่เล็กหรือเกือบเรียงแล้ว
  7. 7. B · 2-SAT ซึ่งแต่ละวลีมีลิเทอรัลไม่เกินสองตัว
  8. 8. A · เวลา O(n) และพื้นที่ O(1)

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