1.ง่าย
การดำเนินการ peek (หรือ top) บนสแตกทำอะไร
- Aคืนสมาชิกล่างสุดของสแตก
- Bเอาสมาชิกทั้งหมดออกจากสแตก
- Cเอาสมาชิกบนสุดออกและคืนค่า
- Dคืนสมาชิกบนสุดโดยไม่เอาออก
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
ในการแทนกราฟด้วยรายการประชิด (adjacency list) เก็บอะไรสำหรับแต่ละจุดยอด
- Aแถวของค่าบูลีน V ค่า
- Bเส้นทางสั้นที่สุดไปยังทุกจุดยอดอื่น
- Cจำนวนเส้นเชื่อมทั้งหมดในกราฟ
- Dรายการของจุดยอดข้างเคียง
3.ง่าย
ตัวประกอบการโหลด (load factor) ของตารางแฮชคืออะไร
- Aจำนวนการชนกันจนถึงตอนนี้
- Bเวลาที่ใช้โหลดตารางจากดิสก์
- Cจำนวนสมาชิกที่เก็บหารด้วยจำนวนถัง
- Dจำนวนถังหารด้วยความยาวเฉลี่ยของคีย์ที่เก็บ
4.ปานกลาง
การค้นหาคำความยาว L ใน trie ที่มีตัวอักษรคงที่ใช้เวลาเท่าใด
- AO(n) เมื่อ n คือจำนวนคำ
- BO(log n) เมื่อ n คือจำนวนคำ
- CO(L) ไม่ขึ้นกับจำนวนคำที่เก็บ
- DO(L × n)
5.ปานกลาง
ต้นไม้ทวิภาคมีราก 1 ลูกซ้าย 2 ลูกขวา 3 โหนด 2 มีลูก 4 (ซ้าย) และ 5 (ขวา) การท่องแบบ preorder คืออะไร
- A1 2 4 5 3
- B4 2 5 1 3
- C1 2 3 4 5
- D4 5 2 3 1
6.ปานกลาง
ในคิววงกลมที่เก็บในอาร์เรย์ความจุ n ตำแหน่งถัดจากดัชนี i คำนวณอย่างไร
- A2i + 1
- Bi + 1
- C(i + 1) mod n
- D(i − 1) mod n
7.ยาก
ภายใต้การแฮชสม่ำเสมออย่างง่าย เวลาคาดหมายของการค้นหาในตารางแฮชแบบ chaining ที่มี n คีย์และ m ถังคือเท่าใด
- AO(log n)
- BO(n)
- CO(m)
- DO(1 + α) เมื่อ α = n / m
8.ยาก
เวลาทำงานของการค้นหาในแนวกว้างบนกราฟที่มี V จุดยอดที่เก็บเป็นเมทริกซ์ประชิดคือเท่าใด
- AO(V + E)
- BO(V²)
- CO(E log V)
- DO(V)
เฉลย
- 1. D · คืนสมาชิกบนสุดโดยไม่เอาออก
- 2. D · รายการของจุดยอดข้างเคียง
- 3. C · จำนวนสมาชิกที่เก็บหารด้วยจำนวนถัง
- 4. C · O(L) ไม่ขึ้นกับจำนวนคำที่เก็บ
- 5. A · 1 2 4 5 3
- 6. C · (i + 1) mod n
- 7. D · O(1 + α) เมื่อ α = n / m
- 8. B · O(V²)
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com