1.ง่าย
เวลาทำงานในกรณีเลวร้ายที่สุดของอัลกอริทึมอธิบายสิ่งใด
- Aเวลาที่ใช้กับอินพุตที่เล็กที่สุด
- Bเวลามากที่สุดที่ใช้ตลอดทุกอินพุตขนาด n
- Cเวลาคาดหมายที่ใช้กับอินพุตสุ่มขนาด n
- Dเวลาที่ใช้บนคอมพิวเตอร์ที่ช้า
ใบงาน อัลกอริทึมและความซับซ้อน พร้อมเฉลย
2.ง่าย
อัลกอริทึมการเรียงลำดับใดเลือกตัวหลักแล้วแบ่งอาร์เรย์เป็นสมาชิกที่เล็กกว่าและใหญ่กว่า
- AQuicksort
- BMerge sort
- CBubble sort
- DInsertion sort
3.ง่าย
ความซับซ้อนเชิงเวลาของการค้นหาในแนวลึก (DFS) บนกราฟที่เก็บเป็นรายการประชิดคือเท่าใด
- AO(V²)
- BO(V × E)
- CO(V + E)
- DO(E log V)
4.ปานกลาง
ความซับซ้อนเชิงเวลาของการคำนวณจำนวนฟีโบนักชีตัวที่ n ด้วยตารางแบบล่างขึ้นบนคือเท่าใด
- AO(log n)
- BO(2ⁿ)
- CO(n²)
- DO(n)
5.ปานกลาง
ข้อใดเกี่ยวกับฟังก์ชันเรียกซ้ำที่ไม่มีกรณีฐานที่ไปถึงได้ถูกต้อง
- Aคอมไพเลอร์แปลงเป็นลูปที่จบอย่างปลอดภัยเสมอ
- Bเรียกตัวเองต่อไปจนสแต็กการเรียกล้น
- Cคืนค่า 0 โดยอัตโนมัติ
- Dทำงานในเวลา O(1)
6.ปานกลาง
การโปรแกรมพลวัต (dynamic programming) มีประโยชน์เมื่อปัญหามี
- Aอินพุตสุ่มเท่านั้น
- Bลูปเพียงชั้นเดียว
- Cไม่มีปัญหาย่อยเลย จึงแก้ได้ในขั้นตอนเดียว
- Dปัญหาย่อยที่ซ้อนทับกันและโครงสร้างย่อยเหมาะสมที่สุด
7.ยาก
นิยามใดของคลาส NP ถูกต้อง
- Aปัญหาที่ไม่ใช่พหุนาม
- Bปัญหาการตัดสินใจที่คำตอบ "ใช่" ตรวจสอบได้ในเวลาพหุนามเมื่อมีใบรับรอง
- Cปัญหาที่แก้ในเวลาพหุนามไม่ได้
- Dปัญหาที่ไม่มีอัลกอริทึมใดแก้ได้
8.ยาก
ความสัมพันธ์เวียนเกิด T(n) = 2T(n/2) + n log n มีผลเฉลยเป็นเท่าใด
- AΘ(n)
- BΘ(n log n)
- CΘ(n²)
- DΘ(n log² n)
เฉลย
- 1. B · เวลามากที่สุดที่ใช้ตลอดทุกอินพุตขนาด n
- 2. A · Quicksort
- 3. C · O(V + E)
- 4. D · O(n)
- 5. B · เรียกตัวเองต่อไปจนสแต็กการเรียกล้น
- 6. D · ปัญหาย่อยที่ซ้อนทับกันและโครงสร้างย่อยเหมาะสมที่สุด
- 7. B · ปัญหาการตัดสินใจที่คำตอบ "ใช่" ตรวจสอบได้ในเวลาพหุนามเมื่อมีใบรับรอง
- 8. D · Θ(n log² n)
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com