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

ต้นไม้ที่มี n โหนดมีเส้นเชื่อมกี่เส้น

1. A2n
2. Bn + 1
3. Cn
4. Dn − 1

deque (double-ended queue) คืออะไร

1. Aคิวสองคิวที่ใช้อาร์เรย์ร่วมกัน
2. Bโครงสร้างที่อนุญาตให้แทรกและเอาออกที่ทั้งสองปลาย
3. Cคิวที่เรียงตามลำดับความสำคัญ
4. Dคิวที่อนุญาตให้เอาออกจากด้านหลังเท่านั้น

คุณสมบัติ max-heap คืออะไร

1. Aใบทั้งหมดมีคีย์สูงสุด
2. Bคีย์เรียงจากซ้ายไปขวา
3. Cคีย์ของลูกซ้ายทุกตัวมากกว่าหรือเท่ากับคีย์ของพี่น้องฝั่งขวา
4. Dคีย์ของแม่แต่ละตัวมากกว่าหรือเท่ากับคีย์ของลูก

ความซับซ้อนเชิงเวลาของการค้นหาคีย์ใน binary search tree ที่สมดุลคือเท่าใด

1. AO(1)
2. BO(n)
3. CO(log n)
4. DO(n log n)

ตารางแฮชขนาด 7 ใช้ h(k) = k mod 7 และ linear probing หลังแทรก 10 แล้ว 17 ถูกเก็บที่ใด

1. Aดัชนี 3
2. Bดัชนี 0
3. Cดัชนี 6
4. Dดัชนี 4

ทราย (trie หรือ prefix tree) มีประสิทธิภาพเป็นพิเศษสำหรับ

1. Aการเก็บเมทริกซ์
2. Bการค้นหาด้วยคำนำหน้า เช่น autocomplete
3. Cการหาเส้นทางสั้นที่สุด
4. Dการเรียงตัวเลข

เพื่อให้ตารางแฮชทำงานถูกต้อง แฮชและความเท่ากันต้องเป็นไปตามกฎใด

1. Aค่าแฮชต้องเป็นจำนวนเฉพาะ
2. Bคีย์ที่เท่ากันต้องมีค่าแฮชเท่ากัน
3. Cค่าแฮชที่เท่ากันหมายถึงคีย์เท่ากัน
4. Dคีย์ที่ต่างกันต้องมีค่าแฮชต่างกัน

ต้นไม้แดง–ดำ (red-black tree) ต้องมีคุณสมบัติใด

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