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

โครงสร้างข้อมูลใดใช้ท่องต้นไม้แบบ level-order

1. Aสแตก
2. Bคิว
3. Cคิวลำดับความสำคัญ
4. Dตารางแฮช

ฟังก์ชันแฮชทำอะไรในตารางแฮช

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

โครงสร้างข้อมูลใดเหมาะที่สุดสำหรับฟีเจอร์ "ย้อนกลับ" (undo) ในโปรแกรมแก้ไขข้อความ

1. Aสแตก (stack)
2. Bเซตแฮช (hash set)
3. Cคิว (queue)
4. Dกราฟ (graph)

ข้อใดเป็นจริงเกี่ยวกับเมทริกซ์ประชิดของกราฟไม่มีทิศทาง

1. Aเส้นทแยงมุมหลักมีเลขหนึ่งเสมอ
2. Bสมมาตรเทียบกับเส้นทแยงมุมหลัก
3. Cแต่ละแถวมี 1 เพียงตัวเดียวพอดี
4. Dเป็นเมทริกซ์สามเหลี่ยมบนเสมอ

จุดประสงค์ของโหนดยามเฝ้า (sentinel หรือ dummy) ในลิงก์ลิสต์คืออะไร

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

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

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

เหตุใดจึงใช้ B-tree ในฐานข้อมูลและระบบไฟล์

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

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

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