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

แมป (map หรือ dictionary) เก็บอะไร

1. Aคู่ของคีย์ที่เท่ากัน
2. Bค่าตามลำดับการแทรกเท่านั้น
3. Cคู่คีย์–ค่าที่คีย์ไม่ซ้ำกัน
4. Dค่าที่เรียงตามขนาด

ในลิงก์ลิสต์เชิงเดี่ยว ตัวชี้ next ของโหนดสุดท้ายมีค่าเป็น

1. Aที่อยู่ของโหนดก่อนหน้า
2. Bจำนวนโหนดในลิสต์
3. Cที่อยู่ของโหนดแรก
4. DNull (ไม่มีโหนด)

คุณสมบัติ max-heap คืออะไร

1. Aคีย์ของลูกซ้ายทุกตัวมากกว่าหรือเท่ากับคีย์ของพี่น้องฝั่งขวา
2. Bใบทั้งหมดมีคีย์สูงสุด
3. Cคีย์เรียงจากซ้ายไปขวา
4. Dคีย์ของแม่แต่ละตัวมากกว่าหรือเท่ากับคีย์ของลูก

รายการประชิดใช้หน่วยความจำเท่าใดสำหรับกราฟที่มี V จุดยอดและ E เส้นเชื่อม

1. AO(V + E)
2. BO(V²)
3. CO(V × E)
4. DO(E²)

เหตุใดฮีปทวิภาคจึงเก็บในอาร์เรย์ได้โดยไม่ต้องใช้ตัวชี้

1. Aอาร์เรย์เก็บคีย์ให้เรียงลำดับโดยอัตโนมัติ จึงไม่ต้องใช้ตัวชี้
2. Bฮีปมีสมาชิกไม่เกิน 100 ตัวเสมอ
3. Cคีย์ทั้งหมดในฮีปเท่ากัน
4. Dเป็นต้นไม้ทวิภาคสมบูรณ์ ตำแหน่งจึงเป็นไปตามสูตรดัชนีง่าย ๆ

การค้นหาคำความยาว L ใน trie ที่มีตัวอักษรคงที่ใช้เวลาเท่าใด

1. AO(log n) เมื่อ n คือจำนวนคำ
2. BO(L) ไม่ขึ้นกับจำนวนคำที่เก็บ
3. CO(L × n)
4. DO(n) เมื่อ n คือจำนวนคำ

สำหรับแต่ละสมาชิกของอาร์เรย์ คุณต้องการสมาชิกที่ใหญ่กว่าถัดไปทางขวา ในเวลารวม O(n) โครงสร้างใดช่วยได้

1. Abinary search tree ที่สร้างใหม่สำหรับแต่ละสมาชิก
2. Bสแตกที่เก็บสมาชิกที่รอคำตอบ
3. Cคิวที่เก็บทุกคู่ของสมาชิก
4. Dตารางแฮชของสมาชิกทั้งหมด

Fenwick tree (binary indexed tree) บนอาร์เรย์ที่มีตัวเลข n ตัว รองรับการดำเนินการใดใน O(log n)

1. Aการเรียงอาร์เรย์และการค้นหาแบบทวิภาค
2. Bการหามัธยฐานใน O(1)
3. Cการแทรกสมาชิกที่ตำแหน่งใดก็ได้
4. Dคำถามผลรวมคำนำหน้าและการอัปเดตสมาชิกเดียว