כדי לגשת למבחני סימולציה ועוד המון שאלות נוספות, פתחו גישה מלאה
תתי-נושאים של ערימות
רמת קושי:
(בונוס – 3 נקודות) סמנו את התשובה הנכונה: מציאת ערך מינימום בערימת מקסימום לוקח זמן O(nlogn). נכון / לא נכון.
העתק שאלה
שתף שאלה
סמן כחשוב
סמן כבוצע
אוניברסיטת בר-אילןמועד ג · 2024 · סמסטר ב
★★★★★
ערימותערימה בינאריתסיבוכיות זמןBig-O
תהי A ערימת מקסימום בגודל n. יהי x צומת בערמה A בעומק k (עומק השורש הוא 0, עומק קדקד אחר x הוא 1+ עומקו של ההורה של x). מוסיפים לכל אחד מאברי תת הערמה של A המושרשת ב-x את הקבוע c>0. ברצוננו לתקן את המבנה A כך שיחזור להיות ערימת מקסימום (ללא שינוי יתר ערכי האיברים במבנה A).
א) (8 נקודות) כתבו אלגוריתם לתיקון המבנה A, שזמן ריצתו הוא: O(k⋅logn), הסבירו את נכונות האלגוריתם. ב) (8 נקודות) כתבו אלגוריתם לתיקון המבנה A, שזמן ריצתו הוא: O(2logn−k⋅logn), הסבירו את נכונות האלגוריתם. ג) (9 נקודות, לכל תת סעיף, 3 נקודות) איזה אלגוריתם יהיה עדיף אסימפטוטית מבחינת סיבוכיות זמן ריצה בכל אחד מהמקרים הבאים:
k קבוע
k=loglogn
k=43logn
(3 נקודות) בונוס: השאלה של סעיף ג' במקרה שההפרש logn−k הוא הקבוע 5.
העתק שאלה
שתף שאלה
סמן כחשוב
סמן כבוצע
אוניברסיטת בר-אילןמועד ב · 2023 · סמסטר ב
★★★★★
ערימותערימה בינאריתסיבוכיות זמןניתוח אלגוריתמיםמעקב אחר אלגוריתם
(25) הציגו אלגוריתם המקבל קבוע k וערימת מינימום בגודל n, המיוצגת במערך, ומחזיר רשימה ממוינת של k האיברים הקטנים במערך, מהקטן לגדול, בעלות זמן ריצה של O(min(k2,klogn)) וסיבוכיות זיכרון נוסף של O(1).
תהי ערימת מינימום בעלת n איברים, ואיבר עם ערך k. בנוסף ידוע כי מספר האיברים בערימה הקטנים מ-k היא m. תארו אלגוריתם המשיב את האיברים הקטנים מ-k בזמן O(m).
העתק שאלה
שתף שאלה
סמן כחשוב
סמן כבוצע
אוניברסיטת בר-אילןמועד ב · 2022 · סמסטר ב
★★★★★
ערימותערימה בינאריתBFSגרפיםסיבוכיות זמן
ברצוננו להדפיס את m האיברים הגדולים ביותר מתוך קבוצה של n איברים המאוחסנת בערימת מקסימום, כאשר 0<m<n וכן O(logm)=O(logn). הראה/י איך לעשות זאת בזמן O(mlogm). רמז: השתמש/י בערימת עזר.
העתק שאלה
שתף שאלה
סמן כחשוב
סמן כבוצע
אוניברסיטת בר-אילןמועד ב · 2018 · סמסטר ב
★★★★★
ערימותערימה בינאריתתור עדיפויותסיבוכיות זמן
ברצוננו לנהל אוסף של n מספרים שונים ע"י בניית מבני נתונים בזמן O(n) כך שנוכל אח"כ לבצע כל אחת מהמשימות הבאות בזמן ממוצע O(logn): הוצאת האיבר המקסימאלי, הכנסת הערך K, הוצאת הערך K. א) מדוע השימוש בערימה אינו עונה במלואו על הדרישות? ב) הצע/י מבני נתונים שכן יכולים לתמוך בכל הנדרש.
ענה/י נכון/לא נכון לכל אחד מהסעיפים הבאים. מוותר אך לא חובה לכתוב הסבר עד אורך של שורה לכל סעיף. א) לכל n קיים עץ AVL של n איברים שגובהו Θ(n)
ב) קיימת ערימת מקסימום (בינארית) בה האיבר הקודם בגודלו לאיבר הקטן ביותר אינו עלה. ג) בכל עץ AVL החציון של קבוצת האיברים יאוחסן בשורש. ד) באלגוריתם של Boyer & Moore בהגדרה של Δ2, בחיפוש אחר מופע מוקדם יותר, נאפשר גלישה של המופע מעבר להתחלת המחרוזת. אם לא נאפשר גלישה, האלגוריתם יכול לשגות. ה) נכניס n איברים ל-B-tree מסדר 101 שהיה ריק בהתחלה. מספר הפיצולים הכולל בהכנסת כל האיברים חסום ע"י מספר הקדקודים בסיום התהליך. ו) אי אפשר למצוא חציון של n איברים בזמן O(n), כי אחרת היה אפשר למיין ע"י מציאת חציון של הקבוצה, ואח"כ של חצאי הקבוצות, רבעי הקבוצות וכו' בזמן O(n)+O(2n)+O(4n)+⋯=O(n), בסתירה לחסם התחתון של מיון. ז) לכל n>1 קיים עץ חיפוש בינארי המכיל n קודקודים שסריקת ה-post-order שלו היא סדרה ממוינת. ח) בכל רשימה מקושרת, ניתן לגשת אל כל איבר ב-O(1) זמן. ט) הזמן הדרוש לפעולת קידום מונה בינארי הוא O(1) במקרה הגרוע. י) לכל n>1 קיים גרף עם n קדקודים שיש לו n! מיונים טופולוגיים שונים.
ניתן להגדיר ערימת מקסימום טרנרית כעץ טרנרי (לכל קדקוד 3 בנים) ולהכליל את ה heapify שנלמד ל heapify3 בהתאם. א) ניתן לשכן ערימה טרנרית במערך. איך נעבור מהורה לשלושת בניו? איך מקדקוד לאביו? ב) אחרי מחיקת האיבר המירבי משורש הערימה, (i) כמה קריאות ל heapify3 נדרשות? (ii) כמה השוואות צריך בכל רמה? ג) מה המסקנה יחסית לשימוש בערימה בינרית?
העתק שאלה
שתף שאלה
סמן כחשוב
סמן כבוצע
אוניברסיטת בר-אילןמועד ב · 2015 · סמסטר ב
★★★★★
ערימותערימה בינאריתסיבוכיותערימה טרנרית
נפעיל את heapsort עם ערימת מקסימום כדי למיין מערך A בגודל n. מה הסיבוכיות של הפעלת heapsort על המערך A אם א) A נתון בסדר ממוין לא יורד? כמה השוואות יבוצעו? כמה החלפות (swaps)? ב) שאלה דומה ל א), אבל כשנתון ש-A ממוין בסדר הפוך, לא עולה.
העתק שאלה
שתף שאלה
סמן כחשוב
סמן כבוצע
אוניברסיטת בר-אילןמועד א · 2015 · סמסטר ב
★★★★★
סיבוכיותסיבוכיות זמןערימותערימה בינאריתמיוןמעקב אחר אלגוריתם
נתון גרף G=(V,E) ומערך של מספרים D[v] המוגדר לכל v∈V. הגרף נתון בצורה של רשימת שכנים לכל קדקוד. נבצע לולאה כדי לבנות קבוצה S של קדקודים שבהתחלה מכילה רק קדקוד v0∈V בודד, S={v0}, ובכל איטרציה מתווסף עוד קדקוד עד ש-S=V. הקדקוד y שמתווסף ל-S בשלב מסוים הוא זה בעל ערך מינימלי ב-D באותו רגע. אחרי הוספת y ל-S מעודכנים כל הערכים D של השכנים של y שעדיין לא ב-S. פורמאלית:
מה הסיבוכיות של הלולאה במונחים של V ו-E? נמקו. רמז: הבחירה של מבני הנתונים לניהול המערך D תעשה בתלות ביחס בין E ל-V. בחישוב הסיבוכיות התחשבו גם בפעולות ההשוואה למציאת מינימום (אם צריך פעולות כאלה) וגם בפעולות ההשמה ב-new value, שכל אחת לוקחת זמן O(1).
שאלות תרגול במבני נתונים בנושא ערימה בינארית ממבחנים של אוניברסיטת בר-אילן. השאלות ממוינות לפי רמת קושי, עם פתרונות לבדיקה עצמית - כך שניתן ללמוד מטעויות ולהבין את דרך הפתרון לפני הבחינה. ניתן לאתר שאלות חוזרות ולהריץ מבחני סימולציה ממוקדים בנושא ערימה בינארית.