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

ตารางแฮชเก็บข้อมูลเป็น

1. Aต้นไม้ที่คีย์เรียงลำดับ
2. Bสตริงความยาวคงที่
3. Cคู่คีย์–ค่าที่หาตำแหน่งด้วยฟังก์ชันแฮช
4. Dรายการที่เรียงลำดับเท่านั้น

กราฟมีทิศทาง (directed graph) คืออะไร

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

ในกราฟไม่มีทิศทาง ดีกรี (degree) ของจุดยอดคืออะไร

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

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

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

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

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

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

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

โครงสร้างใดช่วยคำนวณค่าสูงสุดของทุกหน้าต่างขนาด k ในอาร์เรย์ในเวลารวม O(n)

1. Aลิงก์ลิสต์เชิงเดี่ยวของสมาชิกในหน้าต่าง
2. Bอาร์เรย์เรียงลำดับที่อัปเดตด้วยการเลื่อน
3. Cmin-heap ที่สร้างใหม่ทุกหน้าต่าง
4. Ddeque ที่เก็บดัชนีเรียงตามค่าจากมากไปน้อย

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

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