1.ง่าย
Big O ของ 3n² + 5n + 2 คืออะไร
- AO(n²)
- BO(n³)
- CO(5n)
- DO(3n²)
ใบงาน อัลกอริทึมและความซับซ้อน พร้อมเฉลย
2.ง่าย
อัลกอริทึมแบบแบ่งแล้วเอาชนะมีสามขั้นตอนใด
- Aเรียง ค้นหา คืนค่า
- Bเดา ตรวจ ทำซ้ำ
- Cอ่าน คำนวณ เขียน
- Dแบ่ง เอาชนะ รวม
3.ง่าย
กรณีฐานของฟังก์ชันเรียกซ้ำคืออะไร
- Aกรณีที่อินพุตใหญ่ที่สุด ซึ่งถูกจัดการก่อนการเรียกซ้ำใด ๆ
- Bการเรียกที่ใช้หน่วยความจำมากที่สุด
- Cกรณีที่ตอบได้โดยตรงโดยไม่ต้องเรียกซ้ำอีก
- Dบรรทัดแรกของฟังก์ชัน
4.ปานกลาง
การค้นหาในแนวกว้าง (BFS) บนกราฟที่ไม่มีน้ำหนักให้ผลเป็น
- Aต้นไม้ทอดข้ามที่น้อยที่สุด
- Bลำดับทอพอโลยีในทุกกราฟ
- Cเส้นทางสั้นที่สุดในแง่จำนวนเส้นเชื่อมจากโหนดเริ่มต้น
- Dเส้นทางสั้นที่สุดในกราฟที่มีเส้นเชื่อมน้ำหนักติดลบ
5.ปานกลาง
อัลกอริทึมของ Prim สร้างต้นไม้ทอดข้ามที่น้อยที่สุดอย่างไร
- Aเรียงเส้นเชื่อมทั้งหมดตามน้ำหนักและเพิ่มทีละเส้น เว้นแต่จะก่อวงจรในป่า
- Bรัน BFS และเก็บต้นไม้ BFS ไว้
- Cลบเส้นเชื่อมที่แพงที่สุดจนไม่เหลือวงจร
- Dขยายต้นไม้ต้นเดียวจากจุดยอดเริ่มต้น โดยเพิ่มเส้นเชื่อมที่ถูกที่สุดที่ออกจากต้นไม้
6.ปานกลาง
ความสัมพันธ์เวียนเกิด T(n) = T(n − 1) + O(n) มีผลเฉลยเป็นเท่าใด
- AO(n)
- BO(n log n)
- CO(n²)
- DO(2ⁿ)
7.ยาก
ข้อใดเกี่ยวกับ P และ NP ถูกต้อง
- Aทุกปัญหาใน P อยู่ใน NP ด้วย
- BNP หมายถึง "ไม่ใช่พหุนาม"
- Cปัญหา NP ตรวจสอบอย่างรวดเร็วไม่ได้
- Dได้พิสูจน์แล้วว่า P ≠ NP
8.ยาก
เวลาทำงานของอัลกอริทึมของ Dijkstra ที่ใช้ฮีปไบนารีบนกราฟที่มี V จุดยอดและ E เส้นเชื่อมคือเท่าใด
- AO(V³)
- BO(V + E)
- CO(V × E)
- DO((V + E) log V)
เฉลย
- 1. A · O(n²)
- 2. D · แบ่ง เอาชนะ รวม
- 3. C · กรณีที่ตอบได้โดยตรงโดยไม่ต้องเรียกซ้ำอีก
- 4. C · เส้นทางสั้นที่สุดในแง่จำนวนเส้นเชื่อมจากโหนดเริ่มต้น
- 5. D · ขยายต้นไม้ต้นเดียวจากจุดยอดเริ่มต้น โดยเพิ่มเส้นเชื่อมที่ถูกที่สุดที่ออกจากต้นไม้
- 6. C · O(n²)
- 7. A · ทุกปัญหาใน P อยู่ใน NP ด้วย
- 8. D · O((V + E) log V)
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com