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

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

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

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

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

1.ง่าย

ตัวประกอบการโหลด (load factor) ของตารางแฮชคืออะไร

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

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

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

สมาชิกของอาร์เรย์ถูกเก็บในหน่วยความจำอย่างไร

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

ในตารางแฮชที่ใช้ open addressing ตัวประกอบการโหลดสูงสุดที่เป็นไปได้คือเท่าใด

  1. A2
  2. B0.5
  3. C1
  4. Dไม่มีค่าสูงสุด
5.ปานกลาง

ทราย (trie หรือ prefix tree) มีประสิทธิภาพเป็นพิเศษสำหรับ

  1. Aการหาเส้นทางสั้นที่สุด
  2. Bการเรียงตัวเลข
  3. Cการค้นหาด้วยคำนำหน้า เช่น autocomplete
  4. Dการเก็บเมทริกซ์
6.ปานกลาง

แอปพลิเคชันต้องการค้นหาเร็ว และต้องแสดงรายการคีย์เรียงลำดับและตอบคำถามช่วง โครงสร้างใดเหมาะที่สุด

  1. Aสแตก
  2. Bตารางแฮช
  3. Cbinary search tree แบบสมดุล
  4. Dลิงก์ลิสต์ที่ไม่เรียงลำดับ
7.ยาก

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

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

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

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

เฉลย

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

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