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

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

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

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

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

ลักษณะเด่นของเซต (set) ในฐานะชนิดข้อมูลนามธรรมคืออะไร

1. Aเก็บคู่คีย์–ค่า
2. Bเก็บสมาชิกเรียงลำดับ
3. Cเข้าถึงได้เฉพาะที่ปลายด้านเดียว
4. Dเก็บสมาชิกโดยไม่มีซ้ำ

การตรวจว่ามีเส้นเชื่อม (u, v) หรือไม่ด้วยเมทริกซ์ประชิดใช้เวลาเท่าใด

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

แอปพลิเคชันต้องการค้นหาเร็ว และต้องแสดงรายการคีย์เรียงลำดับและตอบคำถามช่วง โครงสร้างใดเหมาะที่สุด

1. Aลิงก์ลิสต์ที่ไม่เรียงลำดับ
2. Bตารางแฮช
3. Cbinary search tree แบบสมดุล
4. Dสแตก

จะเกิดอะไรขึ้นเมื่อตารางแฮช rehash หลังตัวประกอบการโหลดเกินเกณฑ์

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

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

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

วัตถุถูกเก็บเป็นคีย์ใน hash map จากนั้นฟิลด์ที่ฟังก์ชันแฮชใช้ถูกเปลี่ยน ผลลัพธ์ที่น่าจะเกิดคืออะไร

1. Aการค้นหาวัตถุอาจล้มเหลว เพราะมันอยู่ในถังของแฮชเก่า
2. Bmap ย้ายคีย์ไปถังใหม่โดยอัตโนมัติ
3. Cไม่มีอะไรเปลี่ยน เพราะแฮชของคีย์คำนวณเพียงครั้งเดียวตอนโปรแกรมเริ่มทำงาน
4. Dmap โยนข้อผิดพลาดทันทีที่ฟิลด์เปลี่ยน