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

การดำเนินการใดช้าในอาร์เรย์แต่เร็วที่ส่วนหัวของลิงก์ลิสต์

1. Aการแทรกที่จุดเริ่มต้น
2. Bการเข้าถึงสมาชิกตัวที่ 5
3. Cการอ่านสมาชิกตัวสุดท้ายด้วยดัชนี
4. Dการหาความยาวของอาร์เรย์ขนาดคงที่

ในลิงก์ลิสต์เชิงเดี่ยว (singly linked list) แต่ละโหนดประกอบด้วย

1. Aข้อมูลเท่านั้น
2. Bข้อมูลและการอ้างอิงไปยังโหนดถัดไป
3. Cข้อมูลและดัชนี
4. Dข้อมูลและการอ้างอิงไปยังโหนดอื่นทั้งหมด

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

1. Aสแตก (stack)
2. Bลิงก์ลิสต์ (linked list)
3. Cคิว (queue)
4. Dตารางแฮช (hash table)

วิธีแก้การชนกันแบบใดเก็บคีย์ที่ชนกันไว้ในลิสต์ที่ถังเดียวกัน

1. Aการแฮชซ้อน (double hashing)
2. Bการเชื่อมโซ่แยก (separate chaining)
3. Cการตรวจสอบเชิงเส้น (linear probing)
4. Dการตรวจสอบกำลังสอง (quadratic probing)

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

1. Ah²
2. B2^h+1 − 1
3. C2h + 1
4. D2^h

รายการประชิดใช้หน่วยความจำเท่าใดสำหรับกราฟที่มี V จุดยอดและ E เส้นเชื่อม

1. AO(V × E)
2. BO(E²)
3. CO(V + E)
4. DO(V²)

คุณต้องเก็บค่าที่น้อยที่สุด k ตัวจากสตรีมของตัวเลข n ตัวโดยใช้หน่วยความจำ O(k) แนวทางใดทำงานใน O(n log k)

1. Aคิว FIFO ของ k ค่าล่าสุด
2. Bอาร์เรย์เรียงลำดับของค่าทั้ง n
3. Cmin-heap ที่เก็บค่าทั้ง n ตัว แล้วดึงค่าที่น้อยที่สุด k ตัวออกมาตอนท้าย
4. Dmax-heap ขนาด k โดยแทนที่รากเมื่อมีค่าที่เล็กกว่ามา

การกลับลิงก์ลิสต์เชิงเดี่ยวในที่เดิมมีต้นทุนด้านเวลาและพื้นที่เพิ่มเติมเท่าใด

1. Aเวลา O(1) และพื้นที่เพิ่ม O(1)
2. Bเวลา O(n log n) และพื้นที่เพิ่ม O(1)
3. Cเวลา O(n) และพื้นที่เพิ่ม O(n)
4. Dเวลา O(n) และพื้นที่เพิ่ม O(1)