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

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

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

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

1.ง่าย

ในลิงก์ลิสต์เชิงเดี่ยว (singly linked list) แต่ละโหนดประกอบด้วย

Aข้อมูลและการอ้างอิงไปยังโหนดอื่นทั้งหมด
Bข้อมูลและดัชนี
Cข้อมูลเท่านั้น
Dข้อมูลและการอ้างอิงไปยังโหนดถัดไป

2.ง่าย

โครงสร้างข้อมูลใดเหมาะที่สุดสำหรับฟีเจอร์ "ย้อนกลับ" (undo) ในโปรแกรมแก้ไขข้อความ

Aเซตแฮช (hash set)
Bคิว (queue)
Cสแตก (stack)
Dกราฟ (graph)

3.ง่าย

แมป (map หรือ dictionary) เก็บอะไร

Aคู่ของคีย์ที่เท่ากัน
Bคู่คีย์–ค่าที่คีย์ไม่ซ้ำกัน
Cค่าที่เรียงตามขนาด
Dค่าตามลำดับการแทรกเท่านั้น

4.ปานกลาง

ต้นไม้ทวิภาคมีราก 1 ลูกซ้าย 2 ลูกขวา 3 โหนด 2 มีลูก 4 (ซ้าย) และ 5 (ขวา) การท่องแบบ postorder คืออะไร

A4 2 5 1 3
B5 4 3 2 1
C1 2 4 5 3
D4 5 2 3 1

5.ปานกลาง

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

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

6.ปานกลาง

นิพจน์ postfix 3 4 + 2 * มีค่าเท่าใด

7.ยาก

เวลาทำงานของการค้นหาในแนวกว้างบนกราฟที่มี V จุดยอดที่เก็บเป็นเมทริกซ์ประชิดคือเท่าใด

AO(V²)
BO(E log V)
CO(V + E)
DO(V)

8.ยาก

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

เฉลย

1. D · ข้อมูลและการอ้างอิงไปยังโหนดถัดไป
2. C · สแตก (stack)
3. B · คู่คีย์–ค่าที่คีย์ไม่ซ้ำกัน
4. D · 4 5 2 3 1
5. C · จัดสรรตารางใหม่ที่ใหญ่กว่าและแทรกทุกคีย์ใหม่
6. B · 14
7. A · O(V²)
8. B · 60

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