1.ง่าย
ในลิงก์ลิสต์เชิงเดี่ยว ตัวชี้ next ของโหนดสุดท้ายมีค่าเป็น
- Aที่อยู่ของโหนดก่อนหน้า
- BNull (ไม่มีโหนด)
- Cที่อยู่ของโหนดแรก
- Dจำนวนโหนดในลิสต์
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
รากของต้นไม้ (root) คืออะไร
- Aโหนดใดก็ได้ตรงกลาง
- Bโหนดที่ไม่มีโหนดลูก
- Cโหนดที่มีค่ามากที่สุด
- Dโหนดบนสุดที่ไม่มีโหนดแม่
3.ง่าย
กราฟมีทิศทาง (directed graph) คืออะไร
- Aกราฟที่เส้นเชื่อมมีทิศทางจากจุดยอดหนึ่งไปอีกจุดหนึ่ง
- Bกราฟที่ทุกคู่ของจุดยอดที่ต่างกันเชื่อมกันด้วยเส้นเชื่อม
- Cกราฟที่ไม่มีวงจร
- Dกราฟที่เส้นเชื่อมทุกเส้นมีน้ำหนัก
4.ปานกลาง
หาคีย์ที่น้อยที่สุดใน binary search tree ได้อย่างไร
- Aตามลูกขวาจากรากจนไม่มีลูกขวา
- Bตามลูกซ้ายจากรากจนไม่มีลูกซ้าย
- Cดูเฉพาะราก
- Dเยี่ยมทุกใบและเปรียบเทียบกัน
5.ปานกลาง
เครือข่ายถนนมี 100,000 ทางแยก แต่ละแห่งเชื่อมกับประมาณ 4 แห่ง การแทนแบบใดเหมาะที่สุด
- Aเมทริกซ์ประชิด
- Bฮีปทวิภาคของเส้นเชื่อม
- Cรายการประชิด
- Dอาร์เรย์เรียงลำดับเดียวของจุดยอด
6.ปานกลาง
ต้นไม้ทวิภาคมีราก 1 ลูกซ้าย 2 ลูกขวา 3 โหนด 2 มีลูก 4 (ซ้าย) และ 5 (ขวา) การท่องแบบ preorder คืออะไร
- A1 2 4 5 3
- B4 2 5 1 3
- C4 5 2 3 1
- D1 2 3 4 5
7.ยาก
radix tree (compressed trie) ปรับปรุง trie ธรรมดาอย่างไร
- Aเรียงลูกของแต่ละโหนดตามความถี่
- Bเก็บแต่ละคำไว้ในตารางแฮชที่ราก แทนที่จะเก็บในโหนดแยกกัน
- Cรวมโซ่ของโหนดที่มีลูกตัวเดียวเป็นเส้นเชื่อมเดียวที่ติดป้ายด้วยสตริง
- Dเก็บเฉพาะตัวอักษรแรกของแต่ละคำ
8.ยาก
ในตารางแฮชที่ใช้ open addressing เหตุใดการลบจึงมักทำด้วยเครื่องหมาย "tombstone"
- Aทำให้ตารางเรียงลำดับ
- Bการทำให้ช่องว่างอาจทำลายลำดับการตรวจสอบสำหรับคีย์อื่น
- Cคีย์ที่ลบต้องเก็บไว้ตลอดไปเพื่อความปลอดภัย จึงใช้ช่องนั้นซ้ำไม่ได้
- Dtombstone เร่งการแฮช
เฉลย
- 1. B · Null (ไม่มีโหนด)
- 2. D · โหนดบนสุดที่ไม่มีโหนดแม่
- 3. A · กราฟที่เส้นเชื่อมมีทิศทางจากจุดยอดหนึ่งไปอีกจุดหนึ่ง
- 4. B · ตามลูกซ้ายจากรากจนไม่มีลูกซ้าย
- 5. C · รายการประชิด
- 6. A · 1 2 4 5 3
- 7. C · รวมโซ่ของโหนดที่มีลูกตัวเดียวเป็นเส้นเชื่อมเดียวที่ติดป้ายด้วยสตริง
- 8. B · การทำให้ช่องว่างอาจทำลายลำดับการตรวจสอบสำหรับคีย์อื่น
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com