1.ง่าย
การดำเนินการใดเป็น O(1) สำหรับอาร์เรย์แต่เป็น O(n) สำหรับลิงก์ลิสต์เชิงเดี่ยว
- Aการลบสมาชิกหัว
- Bการเข้าถึงสมาชิกที่ดัชนี i
- Cการแทรกที่หัว
- Dการอ่านสมาชิกตัวแรก
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
ต้นไม้ที่มี n โหนดมีเส้นเชื่อมกี่เส้น
- A2n
- Bn + 1
- Cn − 1
- Dn
3.ง่าย
ตารางแฮชเก็บข้อมูลเป็น
- Aรายการที่เรียงลำดับเท่านั้น
- Bคู่คีย์–ค่าที่หาตำแหน่งด้วยฟังก์ชันแฮช
- Cต้นไม้ที่คีย์เรียงลำดับ
- Dสตริงความยาวคงที่
4.ปานกลาง
สมาชิกใหม่ถูกแทรกลงในฮีปทวิภาคอย่างไร
- Aสร้างฮีปใหม่ทั้งหมดตั้งแต่ต้น
- Bวางที่ท้ายอาร์เรย์และเลื่อนขึ้น (sift up) ตราบที่ยังละเมิดคุณสมบัติฮีป
- Cแทรกที่ตำแหน่งตามลำดับโดยเลื่อนสมาชิกที่ใหญ่กว่าทั้งหมดไปทางขวาหนึ่งตำแหน่ง
- Dวางที่รากและเลื่อนลง
5.ปานกลาง
วิธีแก้การชนกันแบบใดเก็บคีย์ที่ชนกันไว้ในลิสต์ที่ถังเดียวกัน
- Aการตรวจสอบเชิงเส้น (linear probing)
- Bการเชื่อมโซ่แยก (separate chaining)
- Cการตรวจสอบกำลังสอง (quadratic probing)
- Dการแฮชซ้อน (double hashing)
6.ปานกลาง
ต้นไม้ AVL รักษาเงื่อนไขสมดุลใดที่ทุกโหนด
- Aความสูงของต้นไม้ย่อยซ้ายและขวาต่างกันไม่เกิน 1
- Bต้นไม้ย่อยทั้งสองของทุกโหนดมีจำนวนโหนดเท่ากันพอดี
- Cทุกโหนดถูกระบายสีแดงหรือดำ
- Dใบทั้งหมดอยู่ที่ความลึกเดียวกันพอดี
7.ยาก
เพื่อให้ตารางแฮชทำงานถูกต้อง แฮชและความเท่ากันต้องเป็นไปตามกฎใด
- Aคีย์ที่ต่างกันต้องมีค่าแฮชต่างกัน
- Bค่าแฮชที่เท่ากันหมายถึงคีย์เท่ากัน
- Cคีย์ที่เท่ากันต้องมีค่าแฮชเท่ากัน
- Dค่าแฮชต้องเป็นจำนวนเฉพาะ
8.ยาก
การค้นหาคีย์ใด ๆ ในฮีป min ทวิภาคที่มี n สมาชิกใช้เวลาเท่าใด
- AO(1)
- BO(log log n)
- CO(n)
- DO(log n)
เฉลย
- 1. B · การเข้าถึงสมาชิกที่ดัชนี i
- 2. C · n − 1
- 3. B · คู่คีย์–ค่าที่หาตำแหน่งด้วยฟังก์ชันแฮช
- 4. B · วางที่ท้ายอาร์เรย์และเลื่อนขึ้น (sift up) ตราบที่ยังละเมิดคุณสมบัติฮีป
- 5. B · การเชื่อมโซ่แยก (separate chaining)
- 6. A · ความสูงของต้นไม้ย่อยซ้ายและขวาต่างกันไม่เกิน 1
- 7. C · คีย์ที่เท่ากันต้องมีค่าแฮชเท่ากัน
- 8. C · O(n)
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com