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

กราฟมีทิศทาง (directed graph) คืออะไร

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

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

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

แต่ละโหนดในลิงก์ลิสต์สองทิศทาง (doubly linked list) มีอะไร

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

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

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

ความซับซ้อนเชิงเวลาของการค้นหาคีย์ใน binary search tree ที่สมดุลคือเท่าใด

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

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

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

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

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

คุณต้องเก็บค่าที่น้อยที่สุด k ตัวจากสตรีมของตัวเลข n ตัวโดยใช้หน่วยความจำ O(k) แนวทางใดทำงานใน O(n log k)

1. Aคิว FIFO ของ k ค่าล่าสุด
2. Bmin-heap ที่เก็บค่าทั้ง n ตัว แล้วดึงค่าที่น้อยที่สุด k ตัวออกมาตอนท้าย
3. Cอาร์เรย์เรียงลำดับของค่าทั้ง n
4. Dmax-heap ขนาด k โดยแทนที่รากเมื่อมีค่าที่เล็กกว่ามา