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

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

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

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

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

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

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

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

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

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

רמת קושי:

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

A

של

2 n

מספרים שלמים ושונים זה מזה בתחום

[0.. n lo g n]

.
בנוסף נתון עץ חיפוש בינארי

T

(לא עץ אדום שחור), ובו

n

צמתים.
כתבו אלגוריתם הבודק בזמן

O (n)

האם כל האיברים בעץ

T

מופיעים במערך

A

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

A

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

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

⌊ n /2 ⌋

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

n

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

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

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

h

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

h + 1

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א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 · סמסטר ב

★★★★★

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

א) נגדיר "מחסנית מינימום"

S M

(

S t a c k M inim u m

), כמבנה המכיל מספרים טבעיים ותומך בפעולות הבאות:

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

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

הוכיחו שהפרופסור טועה.

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

מבנה נתוניםמחסניותתכנון מבנה נתוניםסיבוכיותחסם תחתוןהוכחת נכונותמיון

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

A

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

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

T

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

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

T

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

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

נתון מערך

A

בגודל

n

של מספרים ממשיים, שבו יכולות להיות כפילויות.
נסמן ב-

m

את מספר הערכים השונים המופיעים במערך

A

(

m < n

m

לא ידוע מראש).

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

A

לתוך מערך

B [1.. n]

בסדר הבא:

m

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

O (n lo g m)

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

O (n)

.

דוגמא:
בהינתן המערך

A

הבא-

5 7 3 1 1 5 5 3 1 3 3 2 4

נקבל-

1 2 3 4 5 7 1 3 5 1 3 5 3

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

A

לתוך מערך

B [1.. n]

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

O (n lo g n)

.
מותר להקצות רק מערך אחד- מערך הפלט

B

באורך

n

. אבל מותר שכל איבר בו יכיל כמה שדות.

דוגמא:
בהינתן המערך

A

הבא-

5 7 3 1 1 5 5 3 1 3 3 2 4

נקבל-

3 3 3 3 1 1 1 5 5 5 2 4 7

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

נתון מערך

A

בגודל

n

. המערך מכיל

O (lo g n)

ערכים שונים, שאינם ידועים מראש.

א) (15 נקודות) כתבו אלגוריתם למיון המערך בזמן

O (n lo g lo g n)

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

O (n)

.

ב) (10 נקודות) הוכיחו שלא קיים אלגוריתם למיון המערך בזמן

O ((lo g n)^{2})

.

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

A

בגודל

n

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

k < n

.

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

k

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

O (k^{2})

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

k < lo g n

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

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

k

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

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

k

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

O (n)

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

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

א) (13 נקודות) נגדיר "תור מינימום" QM (Queue Minimum), כמבנה המכיל מספרים טבעיים ותומך בפעולות הבאות:
CREATE(QM): אתחול מבנה ריק, בזמן

O (1)

.
INSERT(QM,x): הכנסת המספר

x

למבנה QM, בזמן

O (n)

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

O (1)

.
MIN(QM): החזרת המספר הקטן ביותר במבנה QM (ללא הוצאתו), בזמן

O (1)

.

הציעו מימוש ל"תור מינימום", שבו זמן הריצה הכולל של

n

פעולות INSERT, ללא קשר לפעולות אחרות שיכולות להתבצע ביניהן, יהיה

O (n)

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

n

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

ב) (12 נקודות) נגדיר "סופר מחסנית" SS (Super Stack), כמבנה המכיל מספרים טבעיים, תומך בכל פעולות המחסנית, ובנוסף תומך בפעולה SUPER_POP(SS):
CREATE(SS): אתחול מבנה SS ריק, בזמן

O (1)

.
STACK_EMPTY(SS): מחזיר TRUE אם המבנה SS ריק, בזמן

O (1)

.
PUSH(SS,x): הכנסת המספר

x

למבנה SS, בזמן

O (1)

.
POP(SS): הוצאת המספר שהוכנס אחרון למבנה SS והחזרתו, בזמן

O (1)

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

O (n)

.

הציעו מימוש למבנה "סופר מחסנית", שבו זמן הריצה הכולל של כל סדרה של

n

פעולות תהיה

O (n)

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

n

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

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

n

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

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

S

התומך בפעולות הבאות בזמני הריצה המצוינים:

I N S E R T (s a l a r y, am o u n t)

: הכנסת סטודנט חדש שהכנסתו החודשית היא

s a l a r y

, ושערך המלגה הנוכחית שהאוניברסיטה מעניקה לו היא

am o u n t

, בזמן

O (lo g n)

I N C R E A S E - A M O U N T (s a l a r y, in cr e a se)

: הוספת הסכום החיובי

in cr e a se

למלגת כל סטודנט שהכנסתו החודשית קטנה או שווה ל-

s a l a r y

ונמצא במבנה, בזמן

O (lo g n)

. תוכלו להניח שקיים במבנה סטודנט שהכנסתו החודשית היא

s a l a r y

A S S E S S - A M O U N T (s a l a r y)

: החזרת המלגה הכוללת לסטודנט שהכנסתו החודשית היא

s a l a r y

, בזמן

O (lo g n)

. תוכלו להניח שקיים במבנה סטודנט שהכנסתו היא

s a l a r y

.

כדי לפתור את הבעיה נחזיק עץ אדום-שחור

T

עם

n

איברים. כל צומת

V

מייצג סטודנט, ומכיל:

V . s a l a r y

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

V . am o u n t

: המלגה הראשונית שהסטודנט מקבל.

V . in cr e a se

: תוספת מלגה לכל האיברים בתת העץ השמאלי של

V

. לא כולל

V

עצמו.

א) (5 נקודות) קבעו האם השדה

V . in cr e a se

עומד בתנאי 14.1. אם כן כתבו נוסחא.
ב) (10 נקודות) הראו שהשדה

V . in cr e a se

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

I N C R E A S E - A M O U N T (s a l a r y, in cr e a se)

.

דוגמא: שחר נמצא בתוכנית המלגות, עם הכנסה חודשית 52 ₪, ומלגה ראשונית 600 ₪.
נבצע

I N C R E A S E - A M O U N T (60, 1000)

ואז

I N C R E A S E - A M O U N T (75, 100)

.
כעת

A S S E S S - A M O U N T (52)

יחזיר 1700 ₪ (כי הכנסתו של שחר קטנה מ-60 ₪, ומ-75 ₪).
כעת נכניס את דניאל לתוכנית. הכנסתה החודשית של דניאל היא 59 ש"ח, והמלגה הראשונית שהיא מקבלת היא 1200 ₪. כעת

A S S E S S - A M O U N T (59)

יחזיר 1200 ₪.

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

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