שאלת מבחן במבני נתונים - אוניברסיטת בר-אילן 2014 - טבלאות גיבוב

בדיוקנו להשתחום בטבלאה מתונות פטט (התשמורות בתרכות משנים וא"ס בהם שנוצו) פשוט ההשמורות הם פסגולים טבונים. אנו דורשים לעיתות על ממוצה השמורות הבא הלהם: בטבלה פסגל $j$ מצאת את ההשמורה $k$ הקלות ב-(km) / (צלוצר (km-1)) שטנופייס קריאתן פונקציית גיבוש שהיא כשתהיינה על השמורה על השמוליגה. א. בטבלה שונות שגודלה 10 מתעדות בטביעה שיהיה שיתביעה רצנות, השיד אחר שולחן השמוליגא השולחנת על השמוליגה שחן. ב. בטבלה שונות שגודלה 100 עם מאוחס וא 2GB, וכליאה מדויקת הוא 1GB של זומן קלידיגי של זומן שנה 2000, דיוק וידוע את הנתונות וא 2GB בטביעה הגודל הנתונות על השמוליגה שחן.

רמז: השאלה המקורית אינה ברורה. אם מדובר בהכנסה לטבלת גיבוב, יש לחשב את האינדקס הראשוני לכל מפתח. במקרה של התנגשות, יש להשתמש בשיטת פתרון ההתנגשויות (כגון בדיקה לינארית או ריבועית) כדי למצוא תא פנוי.

פתרון: השאלה כפי שנוסחה אינה קריאה. להלן פתרון לשאלה נפוצה בנושא, המבוססת על מילות המפתח שניתן היה לזהות (טבלת גיבוב, גודל 10, פונקציית גיבוב). **שאלה משוערת:** נתונה **טבלת גיבוב** בגודל $m=10$ המשתמשת בשיטת הכתובת הפתוחה עם **בדיקה ריבועית (quadratic probing)** לפתרון התנגשויות. **פונקציית הגיבוב** היא $h(k) = k \pmod{10}$, ורצף הבדיקה במקרה של התנגשות נתון על ידי $h(k, i) = (h(k) + i^2) \pmod{10}$ עבור ניסיון ה-$i$ (כאשר $i=0, 1, 2, \dots$). יש להכניס לטבלה ריקה את סדרת המפתחות הבאה: 89, 18, 49, 58, 69. יש להציג את מצב הטבלה לאחר כל הכנסה. **פתרון:** הטבלה ההתחלתית (אינדקסים 0 עד 9) ריקה: `[ , , , , , , , , , ]` 1. **הכנסת 89:** * $h(89) = 89 \pmod{10} = 9$. * תא 9 פנוי. נכניס את 89 לתא 9. * מצב הטבלה: `[ , , , , , , , , , 89]` 2. **הכנסת 18:** * $h(18) = 18 \pmod{10} = 8$. * תא 8 פנוי. נכניס את 18 לתא 8. * מצב הטבלה: `[ , , , , , , , , 18, 89]` 3. **הכנסת 49:** * $h(49) = 49 \pmod{10} = 9$. * תא 9 תפוס. זוהי **התנגשות**. * ניסיון $i=1$: $h(49, 1) = (9 + 1^2) \pmod{10} = 10 \pmod{10} = 0$. * תא 0 פנוי. נכניס את 49 לתא 0. * מצב הטבלה: `[49, , , , , , , , 18, 89]` 4. **הכנסת 58:** * $h(58) = 58 \pmod{10} = 8$. * תא 8 תפוס. **התנגשות**. * ניסיון $i=1$: $h(58, 1) = (8 + 1^2) \pmod{10} = 9 \pmod{10} = 9$. * תא 9 תפוס. **התנגשות**. * ניסיון $i=2$: $h(58, 2) = (8 + 2^2) \pmod{10} = 12 \pmod{10} = 2$. * תא 2 פנוי. נכניס את 58 לתא 2. * מצב הטבלה: `[49, , 58, , , , , , 18, 89]` 5. **הכנסת 69:** * $h(69) = 69 \pmod{10} = 9$. * תא 9 תפוס. **התנגשות**. * ניסיון $i=1$: $h(69, 1) = (9 + 1^2) \pmod{10} = 10 \pmod{10} = 0$. * תא 0 תפוס. **התנגשות**. * ניסיון $i=2$: $h(69, 2) = (9 + 2^2) \pmod{10} = 13 \pmod{10} = 3$. * תא 3 פנוי. נכניס את 69 לתא 3. * מצב הטבלה: `[49, , 58, 69, , , , , 18, 89]` **הטבלה הסופית היא:** `[49, , 58, 69, , , , , 18, 89]`. $\blacksquare$