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

อะไรคือนิยามของต้นไม้ทวิภาค (binary tree)

1. Aทุกโหนดมีลูกไม่เกินสองตัว
2. Bทุกโหนดมีลูกสองตัวพอดี
3. Cต้นไม้มีสองระดับพอดี
4. Dทุกโหนดเก็บเลขฐานสอง

โครงสร้างข้อมูลใดใช้ท่องต้นไม้แบบ level-order

1. Aตารางแฮช
2. Bคิว
3. Cสแตก
4. Dคิวลำดับความสำคัญ

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

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

ต้นทุนของการแทรกสมาชิกตรงกลางอาร์เรย์ที่มี n สมาชิกคือเท่าใด

1. AO(n) เพราะสมาชิกหลังจากนั้นต้องเลื่อน
2. BO(log n) เพราะการค้นหาแบบทวิภาค
3. CO(1) เพราะทราบดัชนี
4. DO(n²) เพราะแต่ละสมาชิกย้าย n ครั้ง

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

1. A1 2 4 5 3
2. B4 2 5 1 3
3. C4 5 2 3 1
4. D5 4 3 2 1

รายการประชิดใช้หน่วยความจำเท่าใดสำหรับกราฟที่มี V จุดยอดและ E เส้นเชื่อม

1. AO(V + E)
2. BO(E²)
3. CO(V²)
4. DO(V × E)

ภายใต้การแฮชสม่ำเสมออย่างง่าย เวลาคาดหมายของการค้นหาในตารางแฮชแบบ chaining ที่มี n คีย์และ m ถังคือเท่าใด

1. AO(n)
2. BO(log n)
3. CO(m)
4. DO(1 + α) เมื่อ α = n / m

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

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