1.ง่าย
ข้อแตกต่างหลักระหว่างอาร์เรย์สถิตกับอาร์เรย์พลวัตคืออะไร
- Aอาร์เรย์สถิตเก็บได้เฉพาะตัวเลข
- Bอาร์เรย์พลวัตเก็บสมาชิกในโหนดที่เชื่อมกันจึงขยายได้ทีละหนึ่ง
- Cอาร์เรย์พลวัตขยายได้โดยย้ายไปยังบล็อกหน่วยความจำที่ใหญ่กว่า
- Dอาร์เรย์สถิตเข้าถึงด้วยดัชนีช้ากว่า
2.ง่าย
การดำเนินการใดช้าในอาร์เรย์แต่เร็วที่ส่วนหัวของลิงก์ลิสต์
- Aการอ่านสมาชิกตัวสุดท้ายด้วยดัชนี
- Bการหาความยาวของอาร์เรย์ขนาดคงที่
- Cการแทรกที่จุดเริ่มต้น
- Dการเข้าถึงสมาชิกตัวที่ 5
3.ง่าย
ตารางแฮชเก็บข้อมูลเป็น
- Aรายการที่เรียงลำดับเท่านั้น
- Bคู่คีย์–ค่าที่หาตำแหน่งด้วยฟังก์ชันแฮช
- Cสตริงความยาวคงที่
- Dต้นไม้ที่คีย์เรียงลำดับ
4.ปานกลาง
เมทริกซ์ประชิด (adjacency matrix) ของกราฟที่มี V จุดยอดใช้หน่วยความจำเท่าใด
- AO(V²)
- BO(E)
- CO(V + E)
- DO(log V)
5.ปานกลาง
สมาชิกใหม่ถูกแทรกลงในฮีปทวิภาคอย่างไร
- Aสร้างฮีปใหม่ทั้งหมดตั้งแต่ต้น
- Bแทรกที่ตำแหน่งตามลำดับโดยเลื่อนสมาชิกที่ใหญ่กว่าทั้งหมดไปทางขวาหนึ่งตำแหน่ง
- Cวางที่รากและเลื่อนลง
- Dวางที่ท้ายอาร์เรย์และเลื่อนขึ้น (sift up) ตราบที่ยังละเมิดคุณสมบัติฮีป
6.ปานกลาง
ตารางแฮชขนาด 7 ใช้ h(k) = k mod 7 และ linear probing หลังแทรก 10 แล้ว 17 ถูกเก็บที่ใด
- Aดัชนี 0
- Bดัชนี 3
- Cดัชนี 6
- Dดัชนี 4
7.ยาก
คุณสมบัติใดทำให้ B-tree ทุกต้นสมดุลอย่างสมบูรณ์
- Aใบทั้งหมดอยู่ที่ความลึกเดียวกัน
- Bทุกโหนดมีลูกสองตัวพอดี
- Cคีย์ถูกเก็บเฉพาะที่ราก
- Dแต่ละโหนดเก็บหนึ่งคีย์
8.ยาก
ในบัฟเฟอร์วงกลม front == rear อาจหมายถึงว่างหรือเต็ม วิธีทั่วไปในการแยกสองกรณีคืออะไร
- Aเก็บ front และ rear ในตัวแปรเดียวกัน
- Bเก็บจำนวนสมาชิกแยกต่างหาก หรือเว้นหนึ่งช่องไว้เสมอ
- Cล้างบัฟเฟอร์ทุกครั้งที่ front เท่ากับ rear ดังนั้นสถานะจึงเป็นว่าง
- Dทำให้ขนาดบัฟเฟอร์เป็นเลขกำลังสอง
เฉลย
- 1. C · อาร์เรย์พลวัตขยายได้โดยย้ายไปยังบล็อกหน่วยความจำที่ใหญ่กว่า
- 2. C · การแทรกที่จุดเริ่มต้น
- 3. B · คู่คีย์–ค่าที่หาตำแหน่งด้วยฟังก์ชันแฮช
- 4. A · O(V²)
- 5. D · วางที่ท้ายอาร์เรย์และเลื่อนขึ้น (sift up) ตราบที่ยังละเมิดคุณสมบัติฮีป
- 6. D · ดัชนี 4
- 7. A · ใบทั้งหมดอยู่ที่ความลึกเดียวกัน
- 8. B · เก็บจำนวนสมาชิกแยกต่างหาก หรือเว้นหนึ่งช่องไว้เสมอ
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com