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

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

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

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

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

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

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

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

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

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

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

แอปพลิเคชันต้องการค้นหาเร็ว และต้องแสดงรายการคีย์เรียงลำดับและตอบคำถามช่วง โครงสร้างใดเหมาะที่สุด

1. Aตารางแฮช
2. Bสแตก
3. Cbinary search tree แบบสมดุล
4. Dลิงก์ลิสต์ที่ไม่เรียงลำดับ

เหตุใดจึงลบสมาชิกออกจาก Bloom filter มาตรฐานโดยเพียงล้างบิตของมันไม่ได้

1. Aการลบจะเพิ่มอัตราผลบวกเท็จเป็น 100%
2. Bบิตใน Bloom filter เปลี่ยนไม่ได้หลังสร้าง
3. Cบิตเหล่านั้นอาจเป็นของสมาชิกอื่นด้วย ซึ่งจะทำให้เกิดผลลบเท็จ
4. DBloom filter เก็บสมาชิกเต็มรูป ซึ่งเมื่อถูกแฮชแล้วหาไม่พบอีก

ในตารางแฮชที่ใช้ open addressing เหตุใดการลบจึงมักทำด้วยเครื่องหมาย "tombstone"

1. Aคีย์ที่ลบต้องเก็บไว้ตลอดไปเพื่อความปลอดภัย จึงใช้ช่องนั้นซ้ำไม่ได้
2. Bทำให้ตารางเรียงลำดับ
3. Cการทำให้ช่องว่างอาจทำลายลำดับการตรวจสอบสำหรับคีย์อื่น
4. Dtombstone เร่งการแฮช