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

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

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

ในการแทนกราฟด้วยรายการประชิด (adjacency list) เก็บอะไรสำหรับแต่ละจุดยอด

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

ในต้นไม้ ใบ (leaf) คืออะไร

1. Aโหนดที่ไม่มีโหนดลูก
2. Bโหนดที่มีค่ามากที่สุด
3. Cโหนดที่มีลูกหนึ่งตัวพอดี
4. Dโหนดที่ไม่มีโหนดแม่

วิธีแก้การชนกันแบบใดเก็บคีย์ที่ชนกันไว้ในลิสต์ที่ถังเดียวกัน

1. Aการตรวจสอบกำลังสอง (quadratic probing)
2. Bการตรวจสอบเชิงเส้น (linear probing)
3. Cการเชื่อมโซ่แยก (separate chaining)
4. Dการแฮชซ้อน (double hashing)

เหตุใดการท่องอาร์เรย์จึงเร็วกว่าการท่องลิงก์ลิสต์ที่ยาวเท่ากันมากในทางปฏิบัติ

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

จุดประสงค์ของโหนดยามเฝ้า (sentinel หรือ dummy) ในลิงก์ลิสต์คืออะไร

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

อัลกอริทึมของ Kahn สำหรับการเรียงทอพอโลยีลบจุดยอดที่มี in-degree 0 ซ้ำ ๆ โครงสร้างใดเก็บจุดยอดเหล่านั้น

1. Aสแตกของเส้นเชื่อมที่เยี่ยมทั้งหมด
2. Bmax-heap เรียงตาม out-degree
3. Cคิว (หรือคอลเล็กชันใดก็ได้) ของจุดยอดที่มี in-degree เป็น 0
4. Dเมทริกซ์ประชิดที่บันทึกว่าจุดยอดใดถูกลบไปแล้ว

การค้นหาคีย์ใด ๆ ในฮีป min ทวิภาคที่มี n สมาชิกใช้เวลาเท่าใด

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