איך לתרגל שאלות ערימות במבני נתונים?

באתר prepd תמצאו שאלות ערימות במבני נתונים ממבחנים אמיתיים של אוניברסיטת בר-אילן. השאלות ממוינות לפי רמת קושי.

כמה שאלות ערימות יש במבני נתונים?

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

מה חשוב לדעת על ערימות לקראת מבחן במבני נתונים?

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

מבני נתונים - ערימות

מבני נתונים, אלגוריתמים וסיבוכיות

סטטיסטיקות מבחנים

תתי-נושאים של ערימות

רמת קושי:

(בונוס – 3 נקודות) סמנו את התשובה הנכונה: מציאת ערך מינימום בערימת מקסימום לוקח זמן

O (n lo g n)

. נכון / לא נכון.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד ג · 2024 · סמסטר ב

★★★★★

ערימותערימה בינאריתסיבוכיות זמןBig-O

שאלה 1

1. (12 נקודות) נתון מערך בגודל

n

המכיל ערימת מקסימום בגודל לא ידוע. כלומר,

x

התאים הראשונים של המערך הם ערימה תקנית ושאר התאים מכילים את הערך אינסוף (וכאמור,

x

אינו ידוע). עליכם לקבוע את ערכו של

x

בזמן לוגריתמי ב־

x

. כלומר, אם

n = 2^{100}

וגודל הערימה הסתבר להיות 30 אזי יש לבצע כ־5 פעולות ולא כ־100 פעולות.

2. (13 נקודות) נתונה ערימת מינימום שבה בכל רמה כל האיברים זהים. לדוגמה, הערימה

[1, 2, 2, 5, 5, 5, 5, 7, 7, 7, 7]

.

כתבו שגרה בפסאדו־קוד המקבלת כקלט ערימה כנ״ל ואיבר נוסף

z

ומחזירה אינדקס של מופע כלשהו של

z

בערימה או

- 1

אם הוא לא קיים. זמן הריצה צריך להיות

O (lo g lo g n)

כאשר

n

הוא מספר האיברים בערימה.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד ג · 2024 · סמסטר ב

★★★★★

ערימותסיבוכיות זמןחיפושחיפוש בינארי

תהי

A

ערימת מקסימום בגודל

n

. יהי

x

צומת בערמה

A

בעומק

k

(עומק השורש הוא

0

, עומק קדקד אחר

x

הוא

1 +

עומקו של ההורה של

x

). מוסיפים לכל אחד מאברי תת הערמה של

A

המושרשת ב-

x

את הקבוע

c > 0

. ברצוננו לתקן את המבנה

A

כך שיחזור להיות ערימת מקסימום (ללא שינוי יתר ערכי האיברים במבנה

A

).

א) (8 נקודות) כתבו אלגוריתם לתיקון המבנה

A

, שזמן ריצתו הוא:

O (k \cdot lo g n)

, הסבירו את נכונות האלגוריתם.
ב) (8 נקודות) כתבו אלגוריתם לתיקון המבנה

A

, שזמן ריצתו הוא:

O (2^{l o g n - k} \cdot lo g n)

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

$k$ קבוע
$k = lo g lo g n$
$k = \frac{3}{4} lo g n$

(3 נקודות) בונוס: השאלה של סעיף ג' במקרה שההפרש

lo g n - k

הוא הקבוע

5

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד ב · 2023 · סמסטר ב

★★★★★

ערימותערימה בינאריתסיבוכיות זמןניתוח אלגוריתמיםמעקב אחר אלגוריתם

תהי ערימת מינימום בעלת n איברים, ואיבר עם ערך k. בנוסף ידוע כי מספר האיברים בערימה הקטנים מ-k היא m. תארו אלגוריתם המשיב את האיברים הקטנים מ-k בזמן

O (m)

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד ב · 2022 · סמסטר ב

★★★★★

ערימותערימה בינאריתBFSגרפיםסיבוכיות זמן

ברצוננו להדפיס את

m

האיברים הגדולים ביותר מתוך קבוצה של

n

איברים המאוחסנת בערימת מקסימום, כאשר

0 < m < n

וכן

O (lo g m) \neq = O (lo g n)

. הראה/י איך לעשות זאת בזמן

O (m lo g m)

. רמז: השתמש/י בערימת עזר.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד ב · 2018 · סמסטר ב

★★★★★

ערימותערימה בינאריתתור עדיפויותסיבוכיות זמן

ברצוננו לנהל אוסף של

n

מספרים שונים ע"י בניית מבני נתונים בזמן

O (n)

כך שנוכל אח"כ לבצע כל אחת מהמשימות הבאות בזמן ממוצע

O (lo g n)

: הוצאת האיבר המקסימאלי, הכנסת הערך

K

, הוצאת הערך

K

.
א) מדוע השימוש בערימה אינו עונה במלואו על הדרישות?
ב) הצע/י מבני נתונים שכן יכולים לתמוך בכל הנדרש.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד א · 2018 · סמסטר ב

★★★★★

ערימותערימה בינאריתטבלאות גיבובסיבוכיות זמןניתוח מופחתתור עדיפויות

ענה/י נכון/לא נכון לכל אחד מהסעיפים הבאים. מוותר אך לא חובה לכתוב הסבר עד אורך של שורה לכל סעיף.
א) לכל

n

קיים עץ AVL של

n

איברים שגובהו

Θ (n)

ב) קיימת ערימת מקסימום (בינארית) בה האיבר הקודם בגודלו לאיבר הקטן ביותר אינו עלה.
ג) בכל עץ AVL החציון של קבוצת האיברים יאוחסן בשורש.
ד) באלגוריתם של Boyer & Moore בהגדרה של

Δ_{2}

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

n

איברים ל-B-tree מסדר 101 שהיה ריק בהתחלה. מספר הפיצולים הכולל בהכנסת כל האיברים חסום ע"י מספר הקדקודים בסיום התהליך.
ו) אי אפשר למצוא חציון של

n

איברים בזמן

O (n)

, כי אחרת היה אפשר למיין ע"י מציאת חציון של הקבוצה, ואח"כ של חצאי הקבוצות, רבעי הקבוצות וכו' בזמן

O (n) + O (\frac{n}{2}) + O (\frac{n}{4}) + \dots = O (n)

, בסתירה לחסם התחתון של מיון.
ז) לכל

n > 1

קיים עץ חיפוש בינארי המכיל

n

קודקודים שסריקת ה-post-order שלו היא סדרה ממוינת.
ח) בכל רשימה מקושרת, ניתן לגשת אל כל איבר ב-

O (1)

זמן.
ט) הזמן הדרוש לפעולת קידום מונה בינארי הוא

O (1)

במקרה הגרוע.
י) לכל

n > 1

קיים גרף עם

n

קדקודים שיש לו

n!

מיונים טופולוגיים שונים.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד ב · 2018 · סמסטר ב

★★★★★

עצי AVLסימון אסימפטוטיערימותערימה בינאריתעץ חיפוש בינאריחיפושעצי Bחסם תחתון למיוןמיוןנוסחת נסיגהרשימות מקושרותסיבוכיות זמןניתוח מופחתגרפים

ניתן להגדיר ערימת מקסימום טרנרית כעץ טרנרי (לכל קדקוד 3 בנים) ולהכליל את ה heapify שנלמד ל heapify3 בהתאם.
א) ניתן לשכן ערימה טרנרית במערך. איך נעבור מהורה לשלושת בניו? איך מקדקוד לאביו?
ב) אחרי מחיקת האיבר המירבי משורש הערימה,
(i) כמה קריאות ל heapify3 נדרשות?
(ii) כמה השוואות צריך בכל רמה?
ג) מה המסקנה יחסית לשימוש בערימה בינרית?

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד ב · 2015 · סמסטר ב

★★★★★

ערימותערימה בינאריתסיבוכיותערימה טרנרית

נפעיל את heapsort עם ערימת מקסימום כדי למיין מערך

A

בגודל

n

. מה הסיבוכיות של הפעלת heapsort על המערך

A

אם
א)

A

נתון בסדר ממוין לא יורד? כמה השוואות יבוצעו? כמה החלפות (swaps)?
ב) שאלה דומה ל א), אבל כשנתון ש-

A

ממוין בסדר הפוך, לא עולה.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד א · 2015 · סמסטר ב

★★★★★

סיבוכיותסיבוכיות זמןערימותערימה בינאריתמיוןמעקב אחר אלגוריתם

יהי

T

עץ בינרי, שבו כל צומת מכיל 2 ערכים: מפתח

k

ועדיפות

p

. העץ

T

נקרא Treap אם

T

הוא עץ חיפוש בינרי ביחס למפתחות, וערימה ביחס לעדיפויות.
לדוגמא:
כאשר הערך השמאלי בכל צומת הוא המפתח, והערך הימני הוא העדיפות.
א. נתונה הקבוצה הבאה של זוגות סדורים כנ"ל:

{(5, 34), (2, 13), (8, 26), (6, 19), (7, 38), (9, 14), (11, 27), (10, 22)}

צייר/י Treap עבור הקבוצה הנ"ל.
ב. הוכח/י כי לכל קבוצה של זוגות סדורים המורכבים ממפתח ועדיפות קיים בדיוק Treap אחד. הנח/י שכל המפתחות שונים זה מזה, וכל העדיפויות שונות זו מזו.
ג. בהנתן קבוצה כזאת של זוגות סדורים

(k, p)

, כתוב/י אלגוריתם לבניית Treap.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד א · 2013 · סמסטר ב

★★★★★

עצים בינארייםעץ חיפוש בינאריערימותהוכחת נכונותרקורסיהטרייפ

שאלות ערימות במבני נתונים עם פתרונות

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