1.ง่าย
ในต้นไม้ ใบ (leaf) คืออะไร
- Aโหนดที่มีลูกหนึ่งตัวพอดี
- Bโหนดที่มีค่ามากที่สุด
- Cโหนดที่ไม่มีโหนดแม่
- Dโหนดที่ไม่มีโหนดลูก
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
ลักษณะเด่นของเซต (set) ในฐานะชนิดข้อมูลนามธรรมคืออะไร
- Aเก็บคู่คีย์–ค่า
- Bเก็บสมาชิกโดยไม่มีซ้ำ
- Cเข้าถึงได้เฉพาะที่ปลายด้านเดียว
- Dเก็บสมาชิกเรียงลำดับ
3.ง่าย
โครงสร้างข้อมูลใดทำงานตามหลักการ "เข้าก่อนออกก่อน" (first in, first out)
- Aสแตก (stack)
- Bต้นไม้ทวิภาค (binary tree)
- Cฮีป (heap)
- Dคิว (queue)
4.ปานกลาง
เครือข่ายถนนมี 100,000 ทางแยก แต่ละแห่งเชื่อมกับประมาณ 4 แห่ง การแทนแบบใดเหมาะที่สุด
- Aอาร์เรย์เรียงลำดับเดียวของจุดยอด
- Bรายการประชิด
- Cเมทริกซ์ประชิด
- Dฮีปทวิภาคของเส้นเชื่อม
5.ปานกลาง
เหตุใดฮีปทวิภาคจึงเก็บในอาร์เรย์ได้โดยไม่ต้องใช้ตัวชี้
- Aคีย์ทั้งหมดในฮีปเท่ากัน
- Bเป็นต้นไม้ทวิภาคสมบูรณ์ ตำแหน่งจึงเป็นไปตามสูตรดัชนีง่าย ๆ
- Cอาร์เรย์เก็บคีย์ให้เรียงลำดับโดยอัตโนมัติ จึงไม่ต้องใช้ตัวชี้
- Dฮีปมีสมาชิกไม่เกิน 100 ตัวเสมอ
6.ปานกลาง
จะเกิดอะไรขึ้นเมื่อตารางแฮช rehash หลังตัวประกอบการโหลดเกินเกณฑ์
- Aคีย์เก่าที่สุดถูกลบเพื่อให้มีที่ว่าง
- Bย้ายเฉพาะคีย์ที่ชนกันไปยังลิสต์ล้นใหม่ที่ท้ายตาราง
- Cจัดสรรตารางใหม่ที่ใหญ่กว่าและแทรกทุกคีย์ใหม่
- Dคีย์ที่มีอยู่ถูกเรียงในที่เดิม
7.ยาก
ข้อใดเกี่ยวกับ heapsort ถูกต้อง
- Aทำงานใน O(n) กับอินพุตใด ๆ
- Bเสถียรและต้องใช้หน่วยความจำเพิ่ม O(n)
- Cเรียงในที่เดิมใน O(n log n) กรณีเลวร้ายที่สุด แต่ไม่เสถียร
- Dต้องใช้ binary search tree เป็นที่เก็บเพิ่มเติม จึงใช้หน่วยความจำเพิ่ม O(n)
8.ยาก
segment tree มักใช้เพื่อ
- Aเรียงสตริงตามตัวอักษรโดยเก็บแต่ละคำนำหน้าไว้ในโหนดต้นไม้แยกกัน
- Bสร้างสแตก
- Cเก็บเส้นเชื่อมของกราฟ
- Dตอบคำถามช่วง (เช่น ผลรวมช่วง) และอัปเดตใน O(log n)
เฉลย
- 1. D · โหนดที่ไม่มีโหนดลูก
- 2. B · เก็บสมาชิกโดยไม่มีซ้ำ
- 3. D · คิว (queue)
- 4. B · รายการประชิด
- 5. B · เป็นต้นไม้ทวิภาคสมบูรณ์ ตำแหน่งจึงเป็นไปตามสูตรดัชนีง่าย ๆ
- 6. C · จัดสรรตารางใหม่ที่ใหญ่กว่าและแทรกทุกคีย์ใหม่
- 7. C · เรียงในที่เดิมใน O(n log n) กรณีเลวร้ายที่สุด แต่ไม่เสถียร
- 8. D · ตอบคำถามช่วง (เช่น ผลรวมช่วง) และอัปเดตใน O(log n)
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com