1.ง่าย
การดำเนินการใดช้าในอาร์เรย์แต่เร็วที่ส่วนหัวของลิงก์ลิสต์
- Aการอ่านสมาชิกตัวสุดท้ายด้วยดัชนี
- Bการเข้าถึงสมาชิกตัวที่ 5
- Cการแทรกที่จุดเริ่มต้น
- Dการหาความยาวของอาร์เรย์ขนาดคงที่
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
แมป (map หรือ dictionary) เก็บอะไร
- Aคู่คีย์–ค่าที่คีย์ไม่ซ้ำกัน
- Bค่าที่เรียงตามขนาด
- Cคู่ของคีย์ที่เท่ากัน
- Dค่าตามลำดับการแทรกเท่านั้น
3.ง่าย
กราฟมีน้ำหนัก (weighted graph) คืออะไร
- Aกราฟที่แต่ละเส้นเชื่อมมีค่าตัวเลข เช่น ต้นทุนหรือระยะทาง
- Bกราฟที่มีเส้นเชื่อมมากกว่าจุดยอด
- Cกราฟที่จุดยอดบางจุดหนักกว่าจุดอื่นเพราะมีเส้นเชื่อมมากกว่า
- Dกราฟที่เก็บบนดิสก์
4.ปานกลาง
สมาชิกใหม่ถูกแทรกลงในฮีปทวิภาคอย่างไร
- Aวางที่ท้ายอาร์เรย์และเลื่อนขึ้น (sift up) ตราบที่ยังละเมิดคุณสมบัติฮีป
- Bสร้างฮีปใหม่ทั้งหมดตั้งแต่ต้น
- Cวางที่รากและเลื่อนลง
- Dแทรกที่ตำแหน่งตามลำดับโดยเลื่อนสมาชิกที่ใหญ่กว่าทั้งหมดไปทางขวาหนึ่งตำแหน่ง
5.ปานกลาง
ต้นทุนของการแทรกสมาชิกตรงกลางอาร์เรย์ที่มี n สมาชิกคือเท่าใด
- AO(log n) เพราะการค้นหาแบบทวิภาค
- BO(1) เพราะทราบดัชนี
- CO(n) เพราะสมาชิกหลังจากนั้นต้องเลื่อน
- DO(n²) เพราะแต่ละสมาชิกย้าย n ครั้ง
6.ปานกลาง
ในตารางแฮชที่ใช้ open addressing ตัวประกอบการโหลดสูงสุดที่เป็นไปได้คือเท่าใด
- Aไม่มีค่าสูงสุด
- B2
- C0.5
- D1
7.ยาก
ต้นไม้แดง–ดำ (red-black tree) ต้องมีคุณสมบัติใด
- Aทุกเส้นทางจากโหนดไปยังใบของลูกหลานมีจำนวนโหนดสีดำเท่ากัน
- Bรากต้องเป็นสีแดง
- Cทุกโหนดต้องเป็นสีแดง
- Dโหนดสีแดงทุกโหนดต้องมีลูกสีแดง โหนดสีแดงจึงต่อเป็นสายไม่ขาดตอนไปจนถึงใบ
8.ยาก
คีย์ 5, 3, 8, 1 ถูกแทรกตามลำดับนี้ลงใน min-heap ทวิภาคแบบอาร์เรย์ที่ว่าง อาร์เรย์สุดท้ายคืออะไร
- A[1, 3, 5, 8]
- B[3, 1, 8, 5]
- C[1, 5, 8, 3]
- D[1, 3, 8, 5]
เฉลย
- 1. C · การแทรกที่จุดเริ่มต้น
- 2. A · คู่คีย์–ค่าที่คีย์ไม่ซ้ำกัน
- 3. A · กราฟที่แต่ละเส้นเชื่อมมีค่าตัวเลข เช่น ต้นทุนหรือระยะทาง
- 4. A · วางที่ท้ายอาร์เรย์และเลื่อนขึ้น (sift up) ตราบที่ยังละเมิดคุณสมบัติฮีป
- 5. C · O(n) เพราะสมาชิกหลังจากนั้นต้องเลื่อน
- 6. D · 1
- 7. A · ทุกเส้นทางจากโหนดไปยังใบของลูกหลานมีจำนวนโหนดสีดำเท่ากัน
- 8. D · [1, 3, 8, 5]
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com