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

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

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

ความลึก (depth) ของโหนดในต้นไม้คือ

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

การดำเนินการของคิวที่เอาสมาชิกด้านหน้าออกเรียกว่าอะไร

1. ADequeue
2. BInsert
3. CEnqueue
4. DPush

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

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

ต้นทุนของการแทรกสมาชิกตรงกลางอาร์เรย์ที่มี n สมาชิกคือเท่าใด

1. AO(log n) เพราะการค้นหาแบบทวิภาค
2. BO(n²) เพราะแต่ละสมาชิกย้าย n ครั้ง
3. CO(1) เพราะทราบดัชนี
4. DO(n) เพราะสมาชิกหลังจากนั้นต้องเลื่อน

extract-min ใน min-heap ทวิภาคทำงานอย่างไร

1. Aย้ายสมาชิกสุดท้ายไปที่รากและเลื่อนลง (sift down)
2. Bค้นหาใบทั้งหมดเพื่อหาค่าต่ำสุดใหม่
3. Cลบรากและเลื่อนสมาชิกทั้งหมดไปทางซ้ายหนึ่งตำแหน่ง
4. Dลบสมาชิกสุดท้ายของอาร์เรย์

Fenwick tree (binary indexed tree) บนอาร์เรย์ที่มีตัวเลข n ตัว รองรับการดำเนินการใดใน O(log n)

1. Aการแทรกสมาชิกที่ตำแหน่งใดก็ได้
2. Bการหามัธยฐานใน O(1)
3. Cการเรียงอาร์เรย์และการค้นหาแบบทวิภาค
4. Dคำถามผลรวมคำนำหน้าและการอัปเดตสมาชิกเดียว

โหนด AVL ไม่สมดุลเพราะต้นไม้ย่อยขวาของลูกซ้ายสูงเกินไป (กรณีซ้าย–ขวา) ใช้วิธีแก้ใด

1. Aหมุนขวาหนึ่งครั้งที่โหนด
2. Bหมุนซ้ายที่ลูกซ้าย แล้วหมุนขวาที่โหนด
3. Cหมุนขวาที่ลูกซ้าย แล้วหมุนซ้ายที่โหนด
4. Dหมุนซ้ายหนึ่งครั้งที่โหนด