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

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

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

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

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

1.ง่าย

f(n) = Θ(g(n)) หมายความว่าอย่างไร

  1. Af เติบโตเร็วกว่า g อย่างเด็ดขาด
  2. Bf เติบโตในอัตราเดียวกับ g โดยถูกจำกัดทั้งบนและล่างด้วยผลคูณคงที่ของ g
  3. Cf น้อยกว่า g เสมอทุกค่า n ดังนั้น g เป็นขอบเขตบนของ f แต่ไม่เคยเป็นขอบเขตล่าง
  4. Df เติบโตช้ากว่า g อย่างเด็ดขาด
2.ง่าย

memoisation คืออะไร

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

merge sort ใช้กลยุทธ์การออกแบบใด

  1. Aกำลังเดรัจฉาน (brute force)
  2. Bแบ่งแล้วเอาชนะ (divide and conquer)
  3. Cการโปรแกรมพลวัต
  4. Dการเลือกแบบละโมบ
4.ปานกลาง

ความซับซ้อนเชิงเวลาเฉลี่ยแบบกระจายต้นทุน (amortised) ของการต่อท้ายอาร์เรย์พลวัตที่เพิ่มความจุเป็นสองเท่าเมื่อเต็มคือเท่าใด

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

การค้นหาในแนวกว้าง (BFS) บนกราฟที่ไม่มีน้ำหนักให้ผลเป็น

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

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

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

เหตุใดการค้นหาแบบเปรียบเทียบใด ๆ ในอาร์เรย์ที่เรียงแล้วจึงต้องใช้ Ω(log n) การเปรียบเทียบในกรณีเลวร้ายที่สุด

  1. Aทุกสมาชิกต้องถูกเปรียบเทียบอย่างน้อยหนึ่งครั้ง
  2. Bการค้นหาแบบทวิภาคเป็นอัลกอริทึมเดียวที่เป็นไปได้ และต้องใช้ log₂ n การเปรียบเทียบ
  3. Cต้นไม้ตัดสินใจที่มีผลลัพธ์ที่เป็นไปได้ n แบบต้องมีความลึกอย่างน้อย log₂ n
  4. Dการเปรียบเทียบแต่ละครั้งใช้เวลาแบบลอการิทึม
8.ยาก

จะเกิดอะไรขึ้นถ้ามีผู้พบอัลกอริทึมเวลาพหุนามสำหรับปัญหา NP-complete หนึ่งข้อ

  1. Aปัญหาการหยุดจะตัดสินได้
  2. Bอัลกอริทึมเวลาเอกซ์โพเนนเชียลทั้งหมดจะทำงานในเวลาเชิงเส้นทันที
  3. Cทุกปัญหาใน NP แก้ได้ในเวลาพหุนาม ดังนั้น P = NP
  4. Dเฉพาะปัญหานั้นปัญหาเดียวที่ย้ายเข้า P

เฉลย

  1. 1. B · f เติบโตในอัตราเดียวกับ g โดยถูกจำกัดทั้งบนและล่างด้วยผลคูณคงที่ของ g
  2. 2. B · การเก็บผลลัพธ์ของการเรียกฟังก์ชันเพื่อตอบการเรียกซ้ำจากหน่วยความจำ
  3. 3. B · แบ่งแล้วเอาชนะ (divide and conquer)
  4. 4. B · O(1)
  5. 5. D · เส้นทางสั้นที่สุดในแง่จำนวนเส้นเชื่อมจากโหนดเริ่มต้น
  6. 6. D · Insertion sort มีภาระเพิ่มน้อยและเร็วกับอินพุตที่เล็กหรือเกือบเรียงแล้ว
  7. 7. C · ต้นไม้ตัดสินใจที่มีผลลัพธ์ที่เป็นไปได้ n แบบต้องมีความลึกอย่างน้อย log₂ n
  8. 8. C · ทุกปัญหาใน NP แก้ได้ในเวลาพหุนาม ดังนั้น P = NP

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