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

ในกราฟไม่มีทิศทาง ดีกรี (degree) ของจุดยอดคืออะไร

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

ความสูงของต้นไม้มักถูกนิยามว่า

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

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

1. Aลิงก์ลิสต์ (linked list)
2. Bสแตก (stack)
3. Cคิว (queue)
4. Dตารางแฮช (hash table)

ต้นไม้ทวิภาคสมบูรณ์เต็ม (perfect binary tree) ที่มีความสูง h มีกี่โหนด เมื่อความสูงนับเป็นเส้นเชื่อม

1. A2^h+1 − 1
2. B2h + 1
3. Ch²
4. D2^h

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

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

ต้นทุนของการแทรกสมาชิกตรงกลางอาร์เรย์ที่มี n สมาชิกคือเท่าใด

1. AO(log n) เพราะการค้นหาแบบทวิภาค
2. BO(n) เพราะสมาชิกหลังจากนั้นต้องเลื่อน
3. CO(n²) เพราะแต่ละสมาชิกย้าย n ครั้ง
4. DO(1) เพราะทราบดัชนี

ในบัฟเฟอร์วงกลม front == rear อาจหมายถึงว่างหรือเต็ม วิธีทั่วไปในการแยกสองกรณีคืออะไร

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

เวลาทำงานของการค้นหาในแนวกว้างบนกราฟที่มี V จุดยอดที่เก็บเป็นเมทริกซ์ประชิดคือเท่าใด

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