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

ฟังก์ชันแฮชทำอะไรในตารางแฮช

1. Aเรียงคีย์ในตาราง
2. Bเข้ารหัสค่าในตาราง
3. Cนับว่ามีกี่คีย์ที่เก็บอยู่
4. Dแปลงคีย์เป็นดัชนีในตาราง

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

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

ลักษณะเด่นของเซต (set) ในฐานะชนิดข้อมูลนามธรรมคืออะไร

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

extract-min ใน min-heap ทวิภาคทำงานอย่างไร

1. Aย้ายสมาชิกสุดท้ายไปที่รากและเลื่อนลง (sift down)
2. Bลบสมาชิกสุดท้ายของอาร์เรย์
3. Cลบรากและเลื่อนสมาชิกทั้งหมดไปทางซ้ายหนึ่งตำแหน่ง
4. Dค้นหาใบทั้งหมดเพื่อหาค่าต่ำสุดใหม่

ทราย (trie หรือ prefix tree) มีประสิทธิภาพเป็นพิเศษสำหรับ

1. Aการเก็บเมทริกซ์
2. Bการเรียงตัวเลข
3. Cการหาเส้นทางสั้นที่สุด
4. Dการค้นหาด้วยคำนำหน้า เช่น autocomplete

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

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

radix tree (compressed trie) ปรับปรุง trie ธรรมดาอย่างไร

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

หากไม่มี union by rank หรือ path compression ต้นทุนในกรณีเลวร้ายที่สุดของ find หนึ่งครั้งในโครงสร้าง union-find ที่มี n สมาชิกคือเท่าใด

1. AO(α(n))
2. BO(log n)
3. CO(n)
4. DO(1)