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

กราฟประกอบด้วย

1. Aรากและใบเท่านั้น
2. Bจุดยอด (โหนด) ที่เชื่อมต่อกันด้วยเส้นเชื่อม
3. Cคีย์และแฮชเท่านั้น
4. Dแถวและคอลัมน์

การดำเนินการของสแตกที่เพิ่มสมาชิกไว้ด้านบนเรียกว่าอะไร

1. APush
2. BEnqueue
3. CPeek
4. DPop

โครงสร้างข้อมูลใดทำงานตามหลักการ "เข้าก่อนออกก่อน" (first in, first out)

1. Aต้นไม้ทวิภาค (binary tree)
2. Bสแตก (stack)
3. Cคิว (queue)
4. Dฮีป (heap)

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

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

วิธีแก้การชนกันแบบใดเก็บคีย์ที่ชนกันไว้ในลิสต์ที่ถังเดียวกัน

1. Aการตรวจสอบเชิงเส้น (linear probing)
2. Bการตรวจสอบกำลังสอง (quadratic probing)
3. Cการแฮชซ้อน (double hashing)
4. Dการเชื่อมโซ่แยก (separate chaining)

ต้นไม้ AVL รักษาเงื่อนไขสมดุลใดที่ทุกโหนด

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

คุณต้องเก็บค่าที่น้อยที่สุด k ตัวจากสตรีมของตัวเลข n ตัวโดยใช้หน่วยความจำ O(k) แนวทางใดทำงานใน O(n log k)

1. Amin-heap ที่เก็บค่าทั้ง n ตัว แล้วดึงค่าที่น้อยที่สุด k ตัวออกมาตอนท้าย
2. Bอาร์เรย์เรียงลำดับของค่าทั้ง n
3. Cmax-heap ขนาด k โดยแทนที่รากเมื่อมีค่าที่เล็กกว่ามา
4. Dคิว FIFO ของ k ค่าล่าสุด

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

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