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

ต้นไม้ที่มี n โหนดมีเส้นเชื่อมกี่เส้น

1. A2n
2. Bn + 1
3. Cn − 1
4. Dn

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

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

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

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

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

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

โปรแกรมที่ทำงานอยู่ใช้โครงสร้างข้อมูลใดติดตามการเรียกฟังก์ชันที่กำลังทำงานและตัวแปรท้องถิ่น

1. Aคิวหน่วยความจำฮีป
2. Bสแตกการเรียก (call stack)
3. Cตารางแฮชของฟังก์ชัน
4. Dbinary search tree ของเฟรม

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

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

โครงสร้างใดช่วยคำนวณค่าสูงสุดของทุกหน้าต่างขนาด k ในอาร์เรย์ในเวลารวม O(n)

1. Aอาร์เรย์เรียงลำดับที่อัปเดตด้วยการเลื่อน
2. Bลิงก์ลิสต์เชิงเดี่ยวของสมาชิกในหน้าต่าง
3. Cmin-heap ที่สร้างใหม่ทุกหน้าต่าง
4. Ddeque ที่เก็บดัชนีเรียงตามค่าจากมากไปน้อย

ใน BST ที่มีราก 50 ต้นไม้ย่อยซ้าย 30 (ลูก 20, 40) และต้นไม้ย่อยขวา 70 (ลูก 60, 80) ลบรากโดยใช้ in-order successor คีย์ใดกลายเป็นรากใหม่

1. A80
2. B70
3. C40
4. D60