1.ง่าย
ข้อแตกต่างหลักระหว่างอาร์เรย์สถิตกับอาร์เรย์พลวัตคืออะไร
- Aอาร์เรย์สถิตเข้าถึงด้วยดัชนีช้ากว่า
- Bอาร์เรย์สถิตเก็บได้เฉพาะตัวเลข
- Cอาร์เรย์พลวัตขยายได้โดยย้ายไปยังบล็อกหน่วยความจำที่ใหญ่กว่า
- Dอาร์เรย์พลวัตเก็บสมาชิกในโหนดที่เชื่อมกันจึงขยายได้ทีละหนึ่ง
2.ง่าย
ต้นไม้ที่มี n โหนดมีเส้นเชื่อมกี่เส้น
- An − 1
- B2n
- Cn
- Dn + 1
3.ง่าย
โครงสร้างใดมักใช้สร้างคิวลำดับความสำคัญ (priority queue)
- Aสตริง
- Bฮีป (heap)
- Cสแตก (stack)
- Dลิงก์ลิสต์เชิงเดี่ยวที่ไม่เรียงลำดับ
4.ปานกลาง
โครงสร้างข้อมูลใดที่การค้นหาในแนวลึก (DFS) แบบวนซ้ำใช้
- Aฮีป
- Bสแตก
- Cคิว
- Dตารางแฮชเท่านั้น
5.ปานกลาง
การค้นหาคำความยาว L ใน trie ที่มีตัวอักษรคงที่ใช้เวลาเท่าใด
- AO(L × n)
- BO(L) ไม่ขึ้นกับจำนวนคำที่เก็บ
- CO(n) เมื่อ n คือจำนวนคำ
- DO(log n) เมื่อ n คือจำนวนคำ
6.ปานกลาง
ความสูงในกรณีเลวร้ายที่สุดของ binary search tree ที่มี n โหนดคือเท่าใด ถ้าแทรกคีย์ตามลำดับที่เรียงแล้ว
- A√n
- Bn (กลายเป็นลิงก์ลิสต์)
- Clog₂ n
- D1
7.ยาก
ตรวจว่าลิงก์ลิสต์เชิงเดี่ยวมีวงจรหรือไม่โดยใช้หน่วยความจำเพิ่ม O(1) ได้อย่างไร
- Aเรียงลิสต์และหาตัวซ้ำ
- Bนับโหนดจนเกินกว่าฟิลด์ความยาวของลิสต์
- Cเก็บทุกโหนดที่เยี่ยมในเซตแฮช
- Dเลื่อนตัวชี้หนึ่งทีละหนึ่งก้าวและอีกตัวสองก้าว แล้วตรวจว่าพบกันหรือไม่
8.ยาก
ข้อได้เปรียบหลักของ skip list เหนือลิงก์ลิสต์ที่เรียงลำดับคืออะไร
- Aการค้นหา O(log n) คาดหมาย โดยใช้ตัวชี้ไปข้างหน้าหลายระดับ
- Bรับประกันการค้นหา O(1) เพราะทุกโหนดเก็บตัวชี้ไปยังทุกโหนดอื่น
- Cเก็บคีย์โดยไม่เรียงลำดับ
- Dไม่ใช้หน่วยความจำเพิ่ม
เฉลย
- 1. C · อาร์เรย์พลวัตขยายได้โดยย้ายไปยังบล็อกหน่วยความจำที่ใหญ่กว่า
- 2. A · n − 1
- 3. B · ฮีป (heap)
- 4. B · สแตก
- 5. B · O(L) ไม่ขึ้นกับจำนวนคำที่เก็บ
- 6. B · n (กลายเป็นลิงก์ลิสต์)
- 7. D · เลื่อนตัวชี้หนึ่งทีละหนึ่งก้าวและอีกตัวสองก้าว แล้วตรวจว่าพบกันหรือไม่
- 8. A · การค้นหา O(log n) คาดหมาย โดยใช้ตัวชี้ไปข้างหน้าหลายระดับ
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com