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

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

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

ตารางแฮชเก็บข้อมูลเป็น

1. Aรายการที่เรียงลำดับเท่านั้น
2. Bสตริงความยาวคงที่
3. Cคู่คีย์–ค่าที่หาตำแหน่งด้วยฟังก์ชันแฮช
4. Dต้นไม้ที่คีย์เรียงลำดับ

โครงสร้างข้อมูลใดทำงานตามหลักการ "เข้าก่อนออกก่อน" (first in, first out)

1. Aฮีป (heap)
2. Bคิว (queue)
3. Cสแตก (stack)
4. Dต้นไม้ทวิภาค (binary tree)

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

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

ในฮีปทวิภาคที่เก็บในอาร์เรย์เริ่มที่ดัชนี 0 แม่ของโหนดที่ดัชนี i อยู่ที่ใด

1. Aที่ดัชนี i − 1
2. Bที่ดัชนี 2i + 1
3. Cที่ดัชนี ⌊i / 2⌋ + 1
4. Dที่ดัชนี ⌊(i − 1) / 2⌋

ข้อใดเป็นจริงเกี่ยวกับเมทริกซ์ประชิดของกราฟไม่มีทิศทาง

1. Aเป็นเมทริกซ์สามเหลี่ยมบนเสมอ
2. Bแต่ละแถวมี 1 เพียงตัวเดียวพอดี
3. Cสมมาตรเทียบกับเส้นทแยงมุมหลัก
4. Dเส้นทแยงมุมหลักมีเลขหนึ่งเสมอ

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

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

โครงสร้าง union-find (เซตไม่เชื่อมกัน) ที่ใช้ union by rank และ path compression มีต้นทุนกระจายต่อการดำเนินการเป็น

1. AO(n)
2. BO(n²)
3. CO(log n) พอดี
4. DO(α(n)) ซึ่งเป็นฟังก์ชันผกผันของอัคเคอร์มันน์ ที่แทบเป็นค่าคงที่ในทางปฏิบัติ