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

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

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

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

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

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

מבני נתונים ומבוא לאלגוריתמים - ערימות

סיבוכיות, מבני נתונים בסיסיים ואלגוריתמי מיון וחיפוש

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

תתי-נושאים של מבני נתונים

רמת קושי:

נתבונן בשגרה הבאה המקבלת כקלט מערך

A

של מספרים שונים זה מזה:

הסבר: בכל שלב של הלולאה השגרה בוחרת את ערך המיקום ה-

⌊ n /2 ⌋

בתחום הנתון (1 עד

n

), ומשתמשת בו כאיבר ציר כדי לבצע חלוקה בתחום זה. בלולאה הבאה התחום מצטמצם בחצי.

הערה: השגרה partitionWithPivot מחליפה את איבר הציר עם האיבר האחרון וקוראת לשגרת החלוקה הרגילה.

א. מהו זמן הריצה של השגרה הנתונה?
ב. נוסיף לתכונת ערימת המינימום את התכונה הבאה: כל איבר ברמה

h

קטן מכל האיברים ברמה

h + 1

.
הוכיחו או הפריכו: ניתן לבנות ערימת מינימום המקיימת את התכונה שלעיל בזמן לינארי.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א1 · 2026 · סמסטר א

★★★★★

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

נתונה ערימת מקסימום בינארית

H

עם

n

איברים שונים, המיוצגת על-ידי מערך.
א. (10 נק') נתון מספר

x

. תארו אלגוריתם שמחזיר את כל האיברים בערימה שגדולים מ-

x

בסדר יורד. האלגוריתם צריך להיות output-sensitive. כלומר, זמן הריצה יהיה

O (m lo g m)

, כאשר

m

הוא מספר הצמתים שהוחזרו. מותר זיכרון נוסף

O (m)

.
הסבירו בקצרה מדוע האלגוריתם נכון וכיצד תכונת הערימה מאפשרת "גיזום" תתי-עצים.
ב. (8 נק') ידוע שהצומת

y

הוא עלה בערימה

H

. כתבו נכון/לא נכון: זמן הריצה למחיקת הצומת

y

מהערימה הוא

O (1)

במקרה הגרוע. נמקו את תשובתכם בקצרה.
ג. (7 נק') הוכיחו שכל אלגוריתם המקבל את הערימה

H

ומספר

k

, וקובע בוודאות האם

k

נמצא בערימה חייב במקרה הגרוע לבקר

Ω (n)

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א2 · 2026 · סמסטר א

★★★★★

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

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

H

עם

n

איברים שונים, המיוצגת על-ידי מערך.

א. (10 נק') נתון מספר

x

. תארו אלגוריתם שמחזיר את כל האיברים בערימה שקטנים מ-

x

בסדר עולה. האלגוריתם צריך להיות output-sensitive. כלומר, זמן הריצה יהיה

O (m lo g m)

, כאשר

m

הוא מספר הצמתים שהוחזרו. מותר זיכרון נוסף

O (m)

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

ב. (8 נק') הוכיחו שלא ניתן לבצע את המשימה שבסעיף הקודם בזמן

O (m)

במקרה הגרוע.

ג. (7 נק') נתונות

k

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

n

. כתבו נכון/לא נכון והסבירו בקצרה:
ניתן למזג את

k

הערימות למערך ממוין בגודל

n

בזמן

O (n lo g k)

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א1 · 2026 · סמסטר א

★★★★★

ערימותאלגוריתמיםסיבוכיותסריקת עציםרקורסיה

א) (9 נקודות) נתונות שתי ערימות מינימום

A_{1}, A_{2}

בגדלים

n_{1}, n_{2}

בהתאמה.
כתבו אלגוריתם המאחד את שתי הערימות לערימת מינימום אחת

A_{3}

בגודל

n_{1} + n_{2}

.
פתרו בזמן

O (n_{1} + n_{2})

. מותר להקצות מקום נוסף בגודל

O (n_{1} + n_{2})

.
תזכורת: ערימה ממומשת ע"י מערך.

ב) (9 נקודות) נתונים שני עצי חיפוש בינאריים

T_{1}, T_{2}

בגדלים

n_{1}, n_{2}

בהתאמה.
כתבו אלגוריתם המאחד את שני העצים לעץ חיפוש בינארי אחד

T_{3}

בגודל

n_{1} + n_{2}

.
פתרו בזמן

O (n_{1} + n_{2})

. מותר להקצות מקום נוסף בגודל

O (n_{1} + n_{2})

.

ג) (7 נקודות) נתונים שני עצי ערכי מיקום

T_{1}, T_{2}

בגדלים

n_{1}, n_{2}

בהתאמה.
כתבו אלגוריתם המאחד את שני העצים לעץ ערכי מיקום אחד

T_{3}

בגודל

n_{1} + n_{2}

.
פתרו בזמן

O (n_{1} + n_{2})

. מותר להקצות מקום נוסף בגודל

O (n_{1} + n_{2})

.

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א2 · 2025 · סמסטר ב

★★★★★

ערימותמבנה נתוניםאלגוריתמים

א) (9 נקודות) נתונה ערימת מינימום

A

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

ב) (8 נקודות) נתון עץ חיפוש בינארי

T

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

ג) (8 נקודות) נתון עץ ערכי מיקום

T

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

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א1 · 2025 · סמסטר ב

★★★★★

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

נתונה ערימת מקסימום

A

בגודל

n

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

k < n

.

א) (12 נקודות) כתבו שגרה המדפיסה את

k

המספרים הגדולים ביותר בערימה.
פתרו בזמן

O (k^{2})

.
תוכלו להניח כי

k < lo g n

.
ניתן "להרוס" את הערימה המקורית.

תזכורת: אם אתם מניחים הנחה כלשהי לגבי מיקום

k

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

ב) (13 נקודות) כתבו שגרה המדפיסה את

k

המספרים הקטנים ביותר בערימה.
פתרו בזמן

O (n)

.
ניתן "להרוס" את הערימה המקורית.

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד ב · 2025 · סמסטר ב

★★★★★

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

א) (13 נקודות) נתונה ערימת מינימום

A

בגודל

n

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

C > 0

.
כתוב שגרה לתיקון המבנה

A

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

C

למפתחות המסויימים).
על השגרה לעבוד בזמן

O (lo g^{2} n)

.

הערה: "המסלול השמאלי" מוגדר להיות המסלול היוצא מהשורש וממשיך רק שמאלה (אין פניות לבן הימני לאורך כל המסלול).

דוגמא: בערימת המינימום שבאיור, המסלול השמאלי הוא המסלול 3-4-10-21.

ב) (12 נקודות) נתון עץ חיפוש בינארי

T

בגודל

n

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

x, y

בעץ

T

, המקיימים את התנאי

k ey [x] + k ey [y] = 2 k ey [r oo t [T]]

. אם אין שני צמתים המקיימים את התנאי האלגוריתם מחזיר

F A L S E

.
על השגרה לעבוד בזמן

O (n)

. מותר להקצות

O (1)

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

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד ב · 2025 · סמסטר א

★★★★★

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

נתונה טבלה

M

בגודל

m \times n

שאיברי

m

שורותיה ממוינים משמאל לימין ואיברי

n

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

א) (13 נקודות) כתבו שגרה המקבלת כקלט מספר

k

טבעי, ומחזירה רשימה עם

k

האיברים הקטנים ביותר בטבלה. נתון כי

k \leq mn

.
זמן הריצה הנדרש:

O (k lo g k)

.
הערה: אסור לשנות את מפתחות הטבלה, אבל במידת הצורך תוכלו להניח שכל איבר בטבלה

M

הוא רשומה, ושברשומה יש שדה בוליאני המאותחל ל-0 וניתן לעריכה.
ניתן להקצות מקום נוסף בגודל

O (k)

.

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

M

לתוך מערך

A

.
זמן הריצה הנדרש הוא

O (mn * lo g m)

, כאשר ידוע כי

m \leq n

.
ניתן להקצות מקום נוסף בגודל

O (m)

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א1 · 2025 · סמסטר א

★★★★★

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

נתון מערך

A

בן 1000000 (מיליון) מספרים טבעיים.
כתבו אלגוריתם שמדפיס את 50,000 האברים הקטנים ביותר ב-

A

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א1 · 2025 · סמסטר א

★★★★★

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

הסבירו בקצרה כיצד ניתן למחוק איבר כלשהו בערימה בזמן לוגריתמי. הדגימו את השיטה על הערימה

[450, 33, 155, 15, 28, 146, 34, 12, 14, 119]

. הראו כיצד ניתן למחוק את האיבר 15 (תארו את השלבים במחיקה; כמובן שלאחר המחיקה המערך המתקבל צריך להיות ערימה תקנית).

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמבחן סמסטר א · 2024 · סמסטר א

★★★★★

ערימות

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

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