1.ง่าย
ตารางแฮชเก็บข้อมูลเป็น
- Aสตริงความยาวคงที่
- Bต้นไม้ที่คีย์เรียงลำดับ
- Cคู่คีย์–ค่าที่หาตำแหน่งด้วยฟังก์ชันแฮช
- Dรายการที่เรียงลำดับเท่านั้น
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
ในลิงก์ลิสต์เชิงเดี่ยว ตัวชี้ next ของโหนดสุดท้ายมีค่าเป็น
- Aที่อยู่ของโหนดแรก
- Bที่อยู่ของโหนดก่อนหน้า
- CNull (ไม่มีโหนด)
- Dจำนวนโหนดในลิสต์
3.ง่าย
การดำเนินการของคิวที่เอาสมาชิกด้านหน้าออกเรียกว่าอะไร
- AInsert
- BEnqueue
- CDequeue
- DPush
4.ปานกลาง
แอปพลิเคชันต้องการค้นหาเร็ว และต้องแสดงรายการคีย์เรียงลำดับและตอบคำถามช่วง โครงสร้างใดเหมาะที่สุด
- Aสแตก
- Bลิงก์ลิสต์ที่ไม่เรียงลำดับ
- Cตารางแฮช
- Dbinary search tree แบบสมดุล
5.ปานกลาง
ข้อใดเป็นจริงเกี่ยวกับเมทริกซ์ประชิดของกราฟไม่มีทิศทาง
- Aแต่ละแถวมี 1 เพียงตัวเดียวพอดี
- Bสมมาตรเทียบกับเส้นทแยงมุมหลัก
- Cเป็นเมทริกซ์สามเหลี่ยมบนเสมอ
- Dเส้นทแยงมุมหลักมีเลขหนึ่งเสมอ
6.ปานกลาง
ในตารางแฮชที่ใช้ open addressing ตัวประกอบการโหลดสูงสุดที่เป็นไปได้คือเท่าใด
- A2
- B0.5
- C1
- Dไม่มีค่าสูงสุด
7.ยาก
เหตุใดจึงลบสมาชิกออกจาก Bloom filter มาตรฐานโดยเพียงล้างบิตของมันไม่ได้
- ABloom filter เก็บสมาชิกเต็มรูป ซึ่งเมื่อถูกแฮชแล้วหาไม่พบอีก
- Bบิตเหล่านั้นอาจเป็นของสมาชิกอื่นด้วย ซึ่งจะทำให้เกิดผลลบเท็จ
- Cการลบจะเพิ่มอัตราผลบวกเท็จเป็น 100%
- Dบิตใน Bloom filter เปลี่ยนไม่ได้หลังสร้าง
8.ยาก
โหนด AVL ไม่สมดุลเพราะต้นไม้ย่อยขวาของลูกซ้ายสูงเกินไป (กรณีซ้าย–ขวา) ใช้วิธีแก้ใด
- Aหมุนซ้ายหนึ่งครั้งที่โหนด
- Bหมุนซ้ายที่ลูกซ้าย แล้วหมุนขวาที่โหนด
- Cหมุนขวาที่ลูกซ้าย แล้วหมุนซ้ายที่โหนด
- Dหมุนขวาหนึ่งครั้งที่โหนด
เฉลย
- 1. C · คู่คีย์–ค่าที่หาตำแหน่งด้วยฟังก์ชันแฮช
- 2. C · Null (ไม่มีโหนด)
- 3. C · Dequeue
- 4. D · binary search tree แบบสมดุล
- 5. B · สมมาตรเทียบกับเส้นทแยงมุมหลัก
- 6. C · 1
- 7. B · บิตเหล่านั้นอาจเป็นของสมาชิกอื่นด้วย ซึ่งจะทำให้เกิดผลลบเท็จ
- 8. B · หมุนซ้ายที่ลูกซ้าย แล้วหมุนขวาที่โหนด
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com