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

การดำเนินการ peek (หรือ top) บนสแตกทำอะไร

1. Aเอาสมาชิกทั้งหมดออกจากสแตก
2. Bคืนสมาชิกล่างสุดของสแตก
3. Cเอาสมาชิกบนสุดออกและคืนค่า
4. Dคืนสมาชิกบนสุดโดยไม่เอาออก

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

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

สมาชิกของอาร์เรย์ถูกเก็บในหน่วยความจำอย่างไร

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

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

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

ในคิววงกลมที่เก็บในอาร์เรย์ความจุ n ตำแหน่งถัดจากดัชนี i คำนวณอย่างไร

1. A(i − 1) mod n
2. Bi + 1
3. C2i + 1
4. D(i + 1) mod n

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

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

segment tree มักใช้เพื่อ

1. Aเก็บเส้นเชื่อมของกราฟ
2. Bสร้างสแตก
3. Cตอบคำถามช่วง (เช่น ผลรวมช่วง) และอัปเดตใน O(log n)
4. Dเรียงสตริงตามตัวอักษรโดยเก็บแต่ละคำนำหน้าไว้ในโหนดต้นไม้แยกกัน

ข้อได้เปรียบหลักของ skip list เหนือลิงก์ลิสต์ที่เรียงลำดับคืออะไร

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