1.ง่าย
การดำเนินการใดเป็น O(1) สำหรับอาร์เรย์แต่เป็น O(n) สำหรับลิงก์ลิสต์เชิงเดี่ยว
- Aการอ่านสมาชิกตัวแรก
- Bการแทรกที่หัว
- Cการเข้าถึงสมาชิกที่ดัชนี i
- Dการลบสมาชิกหัว
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
ในต้นไม้ โหนดพี่น้อง (sibling) คืออะไร
- Aโหนดที่มีแม่เดียวกัน
- Bโหนดและแม่ของมัน
- Cโหนดที่ไม่มีลูก
- Dโหนดที่ระดับความลึกเดียวกันในต้นไม้ย่อยต่างกัน
3.ง่าย
โครงสร้างข้อมูลใดทำงานตามหลักการ "เข้าหลังออกก่อน" (last in, first out)
- Aตารางแฮช (hash table)
- Bลิงก์ลิสต์ (linked list)
- Cสแตก (stack)
- Dคิว (queue)
4.ปานกลาง
อัลกอริทึมของ Dijkstra ใช้ชนิดข้อมูลนามธรรมใดเลือกจุดยอดถัดไปที่จะประมวลผล
- Aคิว FIFO
- Bเซตที่ไม่มีลำดับ
- Cสแตก
- Dคิวลำดับความสำคัญแบบค่าต่ำสุด (min-priority queue)
5.ปานกลาง
ความสูงในกรณีเลวร้ายที่สุดของ binary search tree ที่มี n โหนดคือเท่าใด ถ้าแทรกคีย์ตามลำดับที่เรียงแล้ว
- Alog₂ n
- Bn (กลายเป็นลิงก์ลิสต์)
- C1
- D√n
6.ปานกลาง
ในคิววงกลมที่เก็บในอาร์เรย์ความจุ n ตำแหน่งถัดจากดัชนี i คำนวณอย่างไร
- A(i + 1) mod n
- Bi + 1
- C2i + 1
- D(i − 1) mod n
7.ยาก
ข้อได้เปรียบหลักของ skip list เหนือลิงก์ลิสต์ที่เรียงลำดับคืออะไร
- Aการค้นหา O(log n) คาดหมาย โดยใช้ตัวชี้ไปข้างหน้าหลายระดับ
- Bไม่ใช้หน่วยความจำเพิ่ม
- Cรับประกันการค้นหา O(1) เพราะทุกโหนดเก็บตัวชี้ไปยังทุกโหนดอื่น
- Dเก็บคีย์โดยไม่เรียงลำดับ
8.ยาก
วัตถุถูกเก็บเป็นคีย์ใน hash map จากนั้นฟิลด์ที่ฟังก์ชันแฮชใช้ถูกเปลี่ยน ผลลัพธ์ที่น่าจะเกิดคืออะไร
- Aไม่มีอะไรเปลี่ยน เพราะแฮชของคีย์คำนวณเพียงครั้งเดียวตอนโปรแกรมเริ่มทำงาน
- Bmap ย้ายคีย์ไปถังใหม่โดยอัตโนมัติ
- Cmap โยนข้อผิดพลาดทันทีที่ฟิลด์เปลี่ยน
- Dการค้นหาวัตถุอาจล้มเหลว เพราะมันอยู่ในถังของแฮชเก่า
เฉลย
- 1. C · การเข้าถึงสมาชิกที่ดัชนี i
- 2. A · โหนดที่มีแม่เดียวกัน
- 3. C · สแตก (stack)
- 4. D · คิวลำดับความสำคัญแบบค่าต่ำสุด (min-priority queue)
- 5. B · n (กลายเป็นลิงก์ลิสต์)
- 6. A · (i + 1) mod n
- 7. A · การค้นหา O(log n) คาดหมาย โดยใช้ตัวชี้ไปข้างหน้าหลายระดับ
- 8. D · การค้นหาวัตถุอาจล้มเหลว เพราะมันอยู่ในถังของแฮชเก่า
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com