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

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

1. Aสแตก (stack)
2. Bคิว (queue)
3. Cต้นไม้ทวิภาค (binary tree)
4. Dฮีป (heap)

ข้อแตกต่างหลักระหว่างอาร์เรย์สถิตกับอาร์เรย์พลวัตคืออะไร

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

ในกราฟ วงจร (cycle) คืออะไร

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

สมาชิกใหม่ถูกแทรกลงในฮีปทวิภาคอย่างไร

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

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

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

แทรกคีย์ 50, 30, 70, 20, 40 ตามลำดับนี้ลงใน binary search tree ว่าง ลูกซ้ายของ 30 คืออะไร

1. A40
2. B50
3. C20
4. D70

โครงสร้างข้อมูลใดรองรับแคช LRU (least recently used) ที่ get และ put เป็น O(1)

1. Ahash map ร่วมกับลิงก์ลิสต์สองทิศทาง
2. Bสแตกเท่านั้น
3. Cbinary search tree เท่านั้น
4. Dอาร์เรย์เรียงลำดับเดียว

การแฮชซ้อน (double hashing) ลดปัญหาใดของ linear probing เป็นหลัก

1. Aความจำเป็นต้องมีฟังก์ชันแฮช
2. Bการจับกลุ่มปฐมภูมิ (primary clustering) ซึ่งช่องที่ถูกใช้ต่อกันเป็นสายยาว
3. Cต้นทุน O(n) ในการอ่านค่าของคีย์
4. Dความจำเป็นต้องเก็บคีย์ในตาราง