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

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

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

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

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

การดำเนินการใดช้าในอาร์เรย์แต่เร็วที่ส่วนหัวของลิงก์ลิสต์

1. Aการหาความยาวของอาร์เรย์ขนาดคงที่
2. Bการแทรกที่จุดเริ่มต้น
3. Cการอ่านสมาชิกตัวสุดท้ายด้วยดัชนี
4. Dการเข้าถึงสมาชิกตัวที่ 5

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

1. A4 5 2 3 1
2. B1 2 4 5 3
3. C4 2 5 1 3
4. D1 2 3 4 5

ความสูงในกรณีเลวร้ายที่สุดของ binary search tree ที่มี n โหนดคือเท่าใด ถ้าแทรกคีย์ตามลำดับที่เรียงแล้ว

1. A1
2. Bn (กลายเป็นลิงก์ลิสต์)
3. C√n
4. Dlog₂ n

บัฟเฟอร์วงกลม (circular buffer หรือ ring buffer) มักใช้สร้าง

1. Aฟังก์ชันแฮช
2. Bคิวขนาดคงที่
3. Cการท่องกราฟ
4. Dต้นไม้ค้นหาแบบทวิภาค

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

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

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

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