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

ใบงาน โครงสร้างข้อมูล ฟรีสำหรับพิมพ์: 8 ข้อ ตั้งแต่ระดับง่ายถึงระดับข้อสอบจริง พร้อมเฉลย พิมพ์หรือบันทึกเป็น PDF ได้

ใบงานใหม่ฝึกออนไลน์พร้อมคำใบ้

สำหรับผู้สอน: พิมพ์ ทำสำเนา และใช้ในชั้นเรียนได้ฟรี ใบงานใหม่แต่ละชุดมีค่าตัวเลขใหม่และเฉลยของตัวเอง หากใส่ลิงก์ไปยัง ExamProblems ในหน้ารายวิชาของคุณ เราจะขอบคุณมาก

ชื่อ: ____________________   วันที่: ____________

1.ง่าย

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

  1. Aสแตก (stack)
  2. Bคิว (queue)
  3. Cฮีป (heap)
  4. Dต้นไม้ทวิภาค (binary tree)
2.ง่าย

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

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

การดำเนินการของสแตกที่เพิ่มสมาชิกไว้ด้านบนเรียกว่าอะไร

  1. AEnqueue
  2. BPush
  3. CPop
  4. DPeek
4.ปานกลาง

จะเกิดอะไรขึ้นเมื่อตารางแฮช rehash หลังตัวประกอบการโหลดเกินเกณฑ์

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

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

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

เหตุใดฮีปทวิภาคจึงเก็บในอาร์เรย์ได้โดยไม่ต้องใช้ตัวชี้

  1. Aคีย์ทั้งหมดในฮีปเท่ากัน
  2. Bฮีปมีสมาชิกไม่เกิน 100 ตัวเสมอ
  3. Cเป็นต้นไม้ทวิภาคสมบูรณ์ ตำแหน่งจึงเป็นไปตามสูตรดัชนีง่าย ๆ
  4. Dอาร์เรย์เก็บคีย์ให้เรียงลำดับโดยอัตโนมัติ จึงไม่ต้องใช้ตัวชี้
7.ยาก

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

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

เหตุใดจึงลบสมาชิกออกจาก Bloom filter มาตรฐานโดยเพียงล้างบิตของมันไม่ได้

  1. ABloom filter เก็บสมาชิกเต็มรูป ซึ่งเมื่อถูกแฮชแล้วหาไม่พบอีก
  2. Bบิตเหล่านั้นอาจเป็นของสมาชิกอื่นด้วย ซึ่งจะทำให้เกิดผลลบเท็จ
  3. Cบิตใน Bloom filter เปลี่ยนไม่ได้หลังสร้าง
  4. Dการลบจะเพิ่มอัตราผลบวกเท็จเป็น 100%

เฉลย

  1. 1. B · คิว (queue)
  2. 2. B · อาร์เรย์พลวัตขยายได้โดยย้ายไปยังบล็อกหน่วยความจำที่ใหญ่กว่า
  3. 3. B · Push
  4. 4. D · จัดสรรตารางใหม่ที่ใหญ่กว่าและแทรกทุกคีย์ใหม่
  5. 5. A · สแตกการเรียก (call stack)
  6. 6. C · เป็นต้นไม้ทวิภาคสมบูรณ์ ตำแหน่งจึงเป็นไปตามสูตรดัชนีง่าย ๆ
  7. 7. B · คิว (หรือคอลเล็กชันใดก็ได้) ของจุดยอดที่มี in-degree เป็น 0
  8. 8. B · บิตเหล่านั้นอาจเป็นของสมาชิกอื่นด้วย ซึ่งจะทำให้เกิดผลลบเท็จ

เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com