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

באתר 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 · סמסטר א

★★★★★

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

תכננו מבנה נתונים

D

המנהל אוסף של מספרים שלמים, ותומך בפעולות הבאות בסיבוכיות הזמן המצוינת:

Init(D) - אתחול מבנה ריק. זמן: $O (1)$
Insert(D, x) - הכנסת איבר $x$ למבנה. זמן: $O (lo g n)$
Delete(D, x) - מחיקת איבר $x$ מהמבנה (נתון מצביע לצומת למחיקה). זמן: $O (lo g n)$
Min-Gap(D) - החזרת ההפרש המינימלי בין שני מספרים סמוכים בגודלם הקיימים כרגע במבנה. לדוגמה: אם המבנה מכיל ${1, 5, 9, 20}$ , ההפרש המינימלי הוא 4 (בין 1 ל-5 או בין 5 ל-9). זמן ריצה נדרש: $O (1)$ במקרה הגרוע.

הנחיות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

תכננו מבנה נתונים

D

המנהל אוסף של מספרים שלמים, ותומך בפעולות הבאות בסיבוכיות הזמן המצוינת:

Init(D) - אתחול מבנה ריק. זמן: $O (1)$
Insert(D, x) - הכנסת איבר $x$ למבנה. זמן: $O (lo g n)$
Delete(D, x) - מחיקת איבר $x$ מהמבנה (נתון מצביע לצומת למחיקה). זמן: $O (lo g n)$
Max-Gap(D) - החזרת ההפרש המקסימלי בין שני מספרים סמוכים בגודלם הקיימים כרגע במבנה. לדוגמה: אם המבנה מכיל ${1, 5, 9, 20}$ , ההפרש המקסימלי הוא 11 (בין 9 ל-20). זמן ריצה נדרש: $O (1)$ במקרה הגרוע.

הנחיות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

S M

(

S t a c k M inim u m

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

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

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

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

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

S

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

הצבעה לאירוויזיון מיוצגת ע"י רשומה המכילה שני שדות:
זמן הצבעה Time - סדרה ייחודית של 6 ספרות המבטאת את שעת ההצבעה,
לדוגמא הסדרה 221015 מבטאת את שעת ההצבעה 22:10:15.
שדה בוליאני Vote - שערכו הוא TRUE אם ההצבעה הייתה עבור ישראל.

א) (4 נקודות) תארו את מבנה הנתונים: באיזה מבנה/מבנים תשתמשו? מהו גודלו/גודלם? מהם השדות והמפתחות בהם מהי משמעותם? מומלץ לשרטט.

ב) (8 נקודות) כתבו את שגרת BUILD(S, A).
אם אתם משתמשים בשיטת החציונים יש לפרט.

ג) (5 נקודות) כתבו את שגרת COUNT(S).

ד) (8 נקודות) כתבו את שגרת COUNT(S, Time1, Time2).

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

S

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

הצבעה לאירוויזיון מיוצגת ע"י רשומה המכילה שני שדות:
זמן הצבעה Time - סדרה ייחודית של 6 ספרות המבטאת את שעת ההצבעה,
לדוגמא הסדרה 221015 מבטאת את שעת ההצבעה 22:10:15.
שדה בוליאני Vote - שערכו הוא TRUE אם ההצבעה הייתה עבור ישראל.

א) (9 נקודות) תארו את מבנה הנתונים: באיזה מבנה/מבנים תשתמשו? מהו גודלו/גודלם? מהם השדות והמפתחות בהם מהי משמעותם? מומלץ לשרטט.
אם אתם משתמשים בשדות הרחבה לעץ א"ש הראו את העמידה בתנאי 14.1 ע"י נוסחא.

ב) (8 נקודות) כתבו את שגרת BUILD(S, A).
אם אתם משתמשים בשיטת החציונים יש לפרט.

ג) (8 נקודות) כתבו את שגרת COUNT(S, Time1, Time2).

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

(a, b)

a \leq b

, שהם נקודת ההתחלה והסיום שלו.
אורך של קטע:

L = b - a

הציעו מבנה

S

אשר מייצג קטעים על הישר הממשי, ושבאמצעותו ניתן לבצע את הפעולות הבאות עם זמני הריצה המצויים ליד כל שגרה.
INSERT(S, (a,b)): מכניס את הקטע

(a, b)

למבנה

S

, רק אם נקודת ההתחלה שלו

a

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

O (lo g n)

.
LONGEST(S, a): מחזיר את אורך הקטע (או קטעים) הארוך ביותר במבנה

S

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

a

, בזמן

O (lo g n)

.
הערה: לא ידוע אם קיים קטע עם נקודת ההתחלה המסוימת

a

.
RANGE(S, L_1, L_2): בהינתן שני מספרים שלמים

L_{1}, L_{2}

, מחזיר את מספר הקטעים באורך

L

, כך ש

L_{1} \leq L \leq L_{2}

, בזמן

O (lo g n)

.
הערה: לא ידוע אם קיימים קטעים באורך

L_{1}, L_{2}

במבנה.

א) (9 נקודות) תארו את מבנה הנתונים: באיזה מבנה/מבנים תשתמשו? מהו גודלו/גודלם? מהם השדות והמפתחות בהם ומהי משמעותם? מומלץ לשרטט.
אם אתם משתמשים בשדות הרחבה לעץ א"ש הראו את העמידה בתנאי 14.1 ע"י נוסחא.

ב) (8 נקודות) כתבו את שגרת LONGEST(S, a).

ג) (8 נקודות) כתבו את שגרת RANGE(S, L_1, L_2).

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

(a, b)

a \leq b

, שהם נקודת ההתחלה והסיום שלו.
אורך של קטע:

L = b - a

הציעו מבנה

S

(a, b)

למבנה

S

, רק אם נקודת ההתחלה שלו

a

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

O (lo g n)

.
LONGEST(S, a): מחזיר את אורך הקטע (או קטעים) הארוך ביותר במבנה

S

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

a

, בזמן

O (k + lo g n)

, כאשר

k

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

a

.
הערה: לא ידוע אם קיים קטע עם נקודת ההתחלה המסוימת

a

.
RANGE(S, L_1, L_2): בהינתן שני מספרים שלמים

L_{1}, L_{2}

, מחזיר את מספר הקטעים באורך

L

, כך ש

L_{1} \leq L \leq L_{2}

, בזמן

O (lo g n)

.
הערה: לא ידוע אם קיימים קטעים באורך

L_{1}, L_{2}

במבנה.

א. (9 נקודות) תארו את מבנה הנתונים: באיזה מבנה/מבנים תשתמשו? מהו גודלו/גודלם? מהם השדות והמפתחות בהם מהי משמעותם? מומלץ לשרטט.

ב. (8 נקודות) כתבו את שגרת LONGEST(S, a).

ג. (8 נקודות) כתבו את שגרת RANGE(S, L_1, L_2).

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

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