מבני נתונים - 121111 - בחינה - 19/06/2023

# מבני נתונים, 121111 ## תאריך הבחינה: 19/06/2023 ## משך הבחינה: 3 שעות ## ללא חומר עזר למעט דפי העזר המצורפים לבחינה ## חלק א' ### שאלה מס' 1 (7 נק') מימשו את טיפוס הנתונים המופשט "קבוצות זרות" בעזרת יער של עצים שנשמר במערך (כפי שראינו בכיתה) עם האיברים ח,...,1, ללא השיפור של כיווץ מסלולים....

# מבני נתונים, 121111 ## תאריך הבחינה: 19/06/2023 ## משך הבחינה: 3 שעות ## ללא חומר עזר למעט דפי העזר המצורפים לבחינה ## חלק א' ### שאלה מס' 1 (7 נק') מימשו את טיפוס הנתונים המופשט "קבוצות זרות" בעזרת יער של עצים שנשמר במערך (כפי שראינו בכיתה) עם האיברים ח,...,1, ללא השיפור של כיווץ מסלולים. ביצעו ח פעולות MakeSet, לאחר מכן פעולות Union, ולאחר מכן פעולות Find. בטענות הבאות הניחו שאם המימוש הוא ללא השיפור של Union by size, נציג הקבוצה המאוחדת נבחר להיות הערך הקטן מבין הנציגים המשתתפים באיחוד. * **בר:** טוענת: אם מימשו ללא השיפור של Union by size, זמן הריצה הכולל לכל הפעולות שבוצעו הוא (nlogn) במקרה הטוב ביותר. * **גיא:** טוען: אם מימשו ללא השיפור של Union by size, זמן הריצה הכולל לכל הפעולות שבוצעו הוא (nlogn) במקרה הגרוע ביותר. * **שחר:** טוען: אם מימשו עם השיפור של Union by size, זמן הריצה הכולל לכל הפעולות שבוצעו הוא (1) במקרה הטוב ביותר. * **דבי:** טוענת: אם מימשו עם השיפור של Union by size, זמן הריצה הכולל לכל הפעולות שבוצעו הוא (nlogn) במקרה הגרוע ביותר. **מה מההיגדים הבאים נכון:** * **א:** כולם צודקים. * **ב:** כולם טועים. * **ג:** שחר ודבי צודקים, בר וגיא טועים. * **ד:** גיא ושחר צודקים, בר ודבי טועות. * **ה:** אף היגד מההיגדים האחרים אינו נכון. * **ו:** דבי צודקת, בר גיא ושחר טועים. ### שאלה מס' 2 (7 נק') יהי ד עץ חיפוש בינארי, ותהי H ערימת מקסימום. בכל אחד מהמבנים 100 <ח איברים שונים זה מזה. נתונות 5 טענות: * **טענה 1:** האיבר המינימלי ב T נמצא בהכרח בעלה. * **טענה 2:** האיבר השני בגודלו (השני הכי קטן) בד נמצא בהכרח בעלה. * **טענה 3:** האיבר השני בגודלו (השני הכי קטן) ב T בהכרח לא נמצא בעלה. * **טענה 4:** האיבר השני בגודלו (השני הכי קטן) ב H נמצא בהכרח בעלה. * **טענה 5:** האיבר השני בגודלו (השני הכי קטן) ב H בהכרח לא נמצא בעלה. **מה מההיגדים הבאים נכון:** * **א:** 1,3,4 נכונות והיתר שגויות. * **ב:** כל הטענות נכונות. * **ג:** כל הטענות שגויות. * **ד:** יש רק טענה נכונה אחת. * **ה:** 1,3 נכונות והיתר שגויות. * **ו:** אף היגד מההיגדים האחרים אינו נכון. ### שאלה מס' 3 (7 נק') נתונות 5 טענות, (הניחו שכל הלוגרתמים הם בבסיס 2) : * **טענה 1:** $n = 2^k$ * **טענה 2:** $\sqrt{n} = log(n)$ * **טענה 3:** $logn = O(n)$ * **טענה 4:** $nlogn = N(log(n)) \frac{log log n}{\sqrt{n}}$ * **טענה 5:** $logn^2 = O(log(n))$ **מה מההיגדים הבאים נכון:** * **א:** אף היגד מההיגדים האחרים אינו נכון. * **ב:** 2,3,5 נכונות והיתר שגויות. * **ג:** 2,3,4,5 נכונות והיתר שגויות. * **ד:** 2,3,4 נכונות והיתר שגויות. * **ה:** 1,3,4,5 נכונות והיתר שגויות. * **ו:** 1,4,5 נכונות והיתר שגויות. ### שאלה מס' 4 (7 נק') נתונה הפונקציה הבאה שעושה שימוש בפונקציה calc שתוגדר בהמשך: ```c++ int func (int A[ ], int n) { int i,j,k,sum; if (n<=1) return 1; k = calc(n); for (i=0; i<k; i++) sum += func(A, n/3); for (j=0; j<n; j+=2) sum++; return sum; } ``` הפונקציה נקראת עם מערך A וגודלו ח. הניחו שעלות חישוב הפונקציה calc היא (1) * **יפעת:** טוענת: אם הפונקציה calc(n) מחזירה את הערך 2, אז עלות func היא (O(n * **מורן:** טוענת: אם הפונקציה calc(n) מחזירה את הערך 2, אז עלות func היא (nlogn) * **גילי:** טוענת: אם הפונקציה calc(n) מחזירה את הערך 3, אז עלות func היא (nlogn) * **הילה:** טוענת: אם הפונקציה calc(n) מחזירה את הערך 3, אז עלות func היא (n) * **א:** יפעת גילי והילה צודקות, מורן טועה. * **ב:** אף היגד מההיגדים האחרים אינו נכון * **ג:** יפעת והילה צודקות, מורן וגילי טועות. * **ד:** מורן וגילי צודקות, יפעת והילה טועות. * **ה:** מורן גילי והילה צודקות, יפעת טועה. * **ו:** כולן טועות. ## חלק ב' ### שאלה מס' 5 (14 נק') נתון מערך של ח איברים, המחולק ל- א קבוצות ...$1,2 לפי סדרם במערך, כלומר $1 היא קבוצת האיברים השמאלית ביותר במערך, S1 היא קבוצת האיברים הימנית ביותר. k כל קבוצה מכילה k איברים. איברי כל קבוצה קטנים מאיברי הקבוצה הבאה וגדולים מאיברי הקבוצה הקודמת, כלומר כל איברי ;S גדולים מאיברי 5-1, וקטנים מאיברי 1+S. **א:** מצאו חסם תחתון לסדר גודל מספר ההשוואות הנדרש כדי למיין את ח האיברים במקרה הגרוע. הוכיחו תשובתכם. כלומר עליכם להוכיח ששום אלגוריתם לבעיה זו אינו יכול להסתפק בפחות השוואות (בסדר גודל) מהחסם שנתתם במקרה הגרוע. **ב:** הראו שהחסם התחתון שנתתם הדוק. כלומר, הראו חסם עליון באותו סדר גודל. ### שאלה מס' 6 (24 נק') ברצוננו לממש טיפוס נתונים מופשט מחסנית מינימום MinStack, ובו סט הפעולות הבא:. * ()Init - אתחול מבנה נתונים ריק (רק בהתחלה. לא ריקון מבנה קיים). יעילות הפעולה צריכה להיות (1) במקרה הגרוע. * .(Push(int x - הוספת האיבר א למחסנית. היעילות צריכה להיות (O(log n במקרה הגרוע. * .()Pop - הסרת האיבר החדש ביותר במבנה (כרגיל במחסנית. לפי סדר LIFO) ! ## היעילות צריכה להיות (O(log n במקרה הגרוע. * ()Min - מחזירה את האיבר הקטן ביותר מבין הנתונים שנמצאים כרגע במבנה (מבלי להסירו). יעילות הפעולה צריכה להיות (1) במקרה הגרוע. * ()RemoveMin - מסירה את האיבר הקטן ביותר מבין הנתונים שנמצאים כרגע במבנה. היעילות צריכה להיות (O(log n במקרה הגרוע. **שימו לב,** * בזמני הריצה הדרושים, ח הוא מספר הנתונים במבנה ברגע ביצוע הפעולה. * לא ניתן להניח חסם כלשהו על מספר הנתונים במבנה. * ניתן להניח שהאיברים הנכנסים למבנה יהיו שונים זה מזה. **תיאור כללי של מבנה הנתונים** **אלגוריתם של Init והסבר ליעילותו** **אלגוריתם של (Push(int x והסבר ליעילותו** **אלגוריתם של ()Pop והסבר ליעילותו** **אלגוריתם של ()Min והסבר ליעילותו** **אלגוריתם של ()RemoveMin והסבר ליעילותו** ## שאלה מס' 7 (24 נק') נתונה הבעיה הבאה. **קלט:** שני מערכים A,B. כל מערך מכיל n איברים. כל איבר מכל מערך נבחר בהתפלגות אחידה מתוך הקבוצה (1,...,3} **פלט:** האם קיים איבר שנמצא במערך A וגם במערך B? כתבו אלגוריתם לבעיה זו, שזמן הריצה הממוצע שלו טוב ככל האפשר. נכו את יעילותו של האלגוריתם במקרה הממוצע כפונקציה של גודל הקלט.