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

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

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

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

1.ง่าย

ฟังก์ชันแฮชทำอะไรในตารางแฮช

Aนับว่ามีกี่คีย์ที่เก็บอยู่
Bเรียงคีย์ในตาราง
Cเข้ารหัสค่าในตาราง
Dแปลงคีย์เป็นดัชนีในตาราง

2.ง่าย

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

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

3.ง่าย

ในลิงก์ลิสต์เชิงเดี่ยว ตัวชี้ next ของโหนดสุดท้ายมีค่าเป็น

ANull (ไม่มีโหนด)
Bที่อยู่ของโหนดก่อนหน้า
Cจำนวนโหนดในลิสต์
Dที่อยู่ของโหนดแรก

4.ปานกลาง

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

AO(n)
BO(1)
CO(n log n)
DO(log n)

5.ปานกลาง

ใน min-heap ทวิภาคที่เก็บในอาร์เรย์ (ดัชนีเริ่มที่ 0) ลูกของโหนดที่ดัชนี i อยู่ที่

A2i + 1 และ 2i + 2
B2i และ 2i + 1
Ci/2 และ i/2 + 1
Di + 1 และ i + 2

6.ปานกลาง

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

7.ยาก

คุณสมบัติใดทำให้ B-tree ทุกต้นสมดุลอย่างสมบูรณ์

Aแต่ละโหนดเก็บหนึ่งคีย์
Bคีย์ถูกเก็บเฉพาะที่ราก
Cใบทั้งหมดอยู่ที่ความลึกเดียวกัน
Dทุกโหนดมีลูกสองตัวพอดี

8.ยาก

เพื่อให้ตารางแฮชทำงานถูกต้อง แฮชและความเท่ากันต้องเป็นไปตามกฎใด

Aค่าแฮชต้องเป็นจำนวนเฉพาะ
Bคีย์ที่ต่างกันต้องมีค่าแฮชต่างกัน
Cค่าแฮชที่เท่ากันหมายถึงคีย์เท่ากัน
Dคีย์ที่เท่ากันต้องมีค่าแฮชเท่ากัน

เฉลย

1. D · แปลงคีย์เป็นดัชนีในตาราง
2. C · ในบล็อกต่อเนื่องเดียว ต่อกันทีละตัว
3. A · Null (ไม่มีโหนด)
4. D · O(log n)
5. A · 2i + 1 และ 2i + 2
6. C · 14
7. C · ใบทั้งหมดอยู่ที่ความลึกเดียวกัน
8. D · คีย์ที่เท่ากันต้องมีค่าแฮชเท่ากัน

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