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

ในลิงก์ลิสต์เชิงเดี่ยว ตัวชี้ next ของโหนดสุดท้ายมีค่าเป็น

1. Aที่อยู่ของโหนดก่อนหน้า
2. Bที่อยู่ของโหนดแรก
3. CNull (ไม่มีโหนด)
4. Dจำนวนโหนดในลิสต์

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

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

โครงสร้างใดมักใช้สร้างคิวลำดับความสำคัญ (priority queue)

1. Aลิงก์ลิสต์เชิงเดี่ยวที่ไม่เรียงลำดับ
2. Bสตริง
3. Cฮีป (heap)
4. Dสแตก (stack)

โปรแกรมที่ทำงานอยู่ใช้โครงสร้างข้อมูลใดติดตามการเรียกฟังก์ชันที่กำลังทำงานและตัวแปรท้องถิ่น

1. Aสแตกการเรียก (call stack)
2. Bbinary search tree ของเฟรม
3. Cตารางแฮชของฟังก์ชัน
4. Dคิวหน่วยความจำฮีป

ทราย (trie หรือ prefix tree) มีประสิทธิภาพเป็นพิเศษสำหรับ

1. Aการค้นหาด้วยคำนำหน้า เช่น autocomplete
2. Bการหาเส้นทางสั้นที่สุด
3. Cการเรียงตัวเลข
4. Dการเก็บเมทริกซ์

ต้นไม้ทวิภาคสมบูรณ์เต็ม (perfect binary tree) ที่มีความสูง h มีกี่โหนด เมื่อความสูงนับเป็นเส้นเชื่อม

1. A2^h
2. Bh²
3. C2^h+1 − 1
4. D2h + 1

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

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

คีย์ 5, 3, 8, 1 ถูกแทรกตามลำดับนี้ลงใน min-heap ทวิภาคแบบอาร์เรย์ที่ว่าง อาร์เรย์สุดท้ายคืออะไร

1. A[3, 1, 8, 5]
2. B[1, 5, 8, 3]
3. C[1, 3, 8, 5]
4. D[1, 3, 5, 8]