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

อะไรคือนิยามของต้นไม้ทวิภาค (binary tree)

1. Aทุกโหนดมีลูกสองตัวพอดี
2. Bทุกโหนดเก็บเลขฐานสอง
3. Cทุกโหนดมีลูกไม่เกินสองตัว
4. Dต้นไม้มีสองระดับพอดี

ในต้นไม้ค้นหาแบบทวิภาค (binary search tree) ค่าในต้นไม้ย่อยซ้ายของโหนดมีค่า

1. Aน้อยกว่าค่าของโหนด
2. Bมากกว่าค่าของโหนด
3. Cเรียงลำดับแบบสุ่ม
4. Dเท่ากับค่าของโหนด

ข้อแตกต่างหลักระหว่างอาร์เรย์สถิตกับอาร์เรย์พลวัตคืออะไร

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

แทรกคีย์ 50, 30, 70, 20, 40 ตามลำดับนี้ลงใน binary search tree ว่าง ลูกซ้ายของ 30 คืออะไร

1. A40
2. B20
3. C50
4. D70

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

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

คิวถูกสร้างด้วยสแตกสองตัว: push ลงสแตก "in" และ pop จากสแตก "out" โดยเติมจาก "in" เมื่อว่าง ต้นทุนกระจายต่อการดำเนินการคือเท่าใด

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

ข้อได้เปรียบหลักของ skip list เหนือลิงก์ลิสต์ที่เรียงลำดับคืออะไร

1. Aเก็บคีย์โดยไม่เรียงลำดับ
2. Bการค้นหา O(log n) คาดหมาย โดยใช้ตัวชี้ไปข้างหน้าหลายระดับ
3. Cไม่ใช้หน่วยความจำเพิ่ม
4. Dรับประกันการค้นหา O(1) เพราะทุกโหนดเก็บตัวชี้ไปยังทุกโหนดอื่น

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

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