ใบงาน โครงสร้างข้อมูล พร้อมเฉลย

ในลิงก์ลิสต์เชิงเดี่ยว ตัวชี้ next ของโหนดสุดท้ายมีค่าเป็น

1. Aที่อยู่ของโหนดแรก
2. Bที่อยู่ของโหนดก่อนหน้า
3. Cจำนวนโหนดในลิสต์
4. DNull (ไม่มีโหนด)

สมาชิกของอาร์เรย์ถูกเก็บในหน่วยความจำอย่างไร

1. Aในต้นไม้ของหน้าหน่วยความจำ
2. Bในบล็อกต่อเนื่องเดียว ต่อกันทีละตัว
3. Cในตำแหน่งสุ่มที่เลือกด้วยแฮช
4. Dกระจัดกระจาย เชื่อมด้วยตัวชี้

ในตารางแฮช การชนกัน (collision) คืออะไร

1. Aคีย์ที่เท่ากันสองตัวถูกเก็บสองครั้ง
2. Bคีย์สองตัวที่ต่างกันแปลงเป็นดัชนีเดียวกัน
3. Cคีย์ไม่สามารถแฮชได้เลย
4. Dตารางหน่วยความจำหมด

โครงสร้างข้อมูลใดใช้ตรวจว่าวงเล็บใน "{[()]}" สมดุลหรือไม่

1. Aคิว
2. Bสแตก
3. Cbinary search tree
4. Dตารางแฮช

แอปพลิเคชันต้องการค้นหาเร็ว และต้องแสดงรายการคีย์เรียงลำดับและตอบคำถามช่วง โครงสร้างใดเหมาะที่สุด

1. Aลิงก์ลิสต์ที่ไม่เรียงลำดับ
2. Bตารางแฮช
3. Cสแตก
4. Dbinary search tree แบบสมดุล

ต้นไม้ทวิภาคมีราก 1 ลูกซ้าย 2 ลูกขวา 3 โหนด 2 มีลูก 4 (ซ้าย) และ 5 (ขวา) การท่องแบบ preorder คืออะไร

1. A1 2 3 4 5
2. B4 2 5 1 3
3. C4 5 2 3 1
4. D1 2 4 5 3

ภายใต้การแฮชสม่ำเสมออย่างง่าย เวลาคาดหมายของการค้นหาในตารางแฮชแบบ chaining ที่มี n คีย์และ m ถังคือเท่าใด

1. AO(m)
2. BO(1 + α) เมื่อ α = n / m
3. CO(n)
4. DO(log n)

กฎของต้นไม้แดง–ดำรับประกันอะไรเกี่ยวกับความสูงของต้นไม้ที่มี n คีย์

1. Aความสูงไม่เกิน n / 2
2. Bความสูงเท่ากับ log₂ n พอดี
3. Cความสูงไม่เกิน log₂ n + 1
4. Dความสูงไม่เกิน 2 log₂(n + 1)