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

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

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

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

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

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

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

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

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

תתי-נושאים של סיבוכיות

רמת קושי:

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

n

(לינארית בגודל הקלט), ומבצע קריאה רקורסיבית אחת לקלט בגודל

n - 2

.
1. כתבו את נוסחת הנסיגה

T (n)

.
2. פתרו את הנוסחה ומצאו חסם (

Θ

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

(lo g n)^{3}, n \cdot lo g n, n / lo g n, n^{0.9}, lo g (n!)

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

מערך

A

בגודל

n

נקרא "יוני-מודאלי" (Unimodal) אם הסדרה עולה עד לאיבר מקסימלי מסוים ("הפסגה") ואחריו יורדת. לדוגמה:

{1, 2, 4, 9, 12, 8, 5}

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

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

O (lo g n)

. הסבירו בקצרה את נכונות האלגוריתם.

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

O (n)

). ניתן להשתמש במערך עזר. הסבירו בקצרה את נכונות האלגוריתם.

ג. (7 נק') נתון מערך כלשהו של

n

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

o (n lo g n)

(או קטנה של

n lo g n

).

הערה: המספרים בכל הסעיפים לאו דווקא שלמים.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

א. נניח שבונים עץ חיפוש בינרי על ידי כך שמכניסים לעץ, בזה אחר זה, ערכים השונים זה מזה.
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 · סמסטר א

★★★★★

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

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

[15, 20, 25, 1, 5, 8, 10]

(המערך המקורי היה:

[1, 5, 8, 10, 15, 20, 25]

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

O (lo g n)

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

x

. האלגוריתם יחזיר את האינדקס של

x

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

O (lo g n)

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

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

★★★★★

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

א) (13 נקודות) מצאו חסם אסימפטוטי הדוק עבור

T (n)

T (n) = {Θ (1) 2 T (\frac{n}{2}) + n lo g^{2} (n) if n < 100 if n \geq 100

ב) (12 נקודות) נתונות שתי פונקציות

f, g : N \to R^{+}

f (n) = 2^{l o g_{4} n}

g (n) = n^{2}

i. (6 נקודות) פרופסור אילוביץ' טענה כי השיטה הכי טובה להכריע מהו היחס האסימפטוטי בין

f (n)

ל-

g (n)

היא להחיל

lo g ()

על שתי הפונקציות, לבדוק מהו היחס האסימפטוטי בין

lo g (f (n))

ל-

lo g (g (n))

, ולטעון כי היחס האסימפטוטי נשמר.
הסבירו מהי הבעיה הלוגית בשיטתה של פרופסור אילוביץ'.

ii. (6 נקודות) יש לקבוע ולהוכיח האם מתקיים

f (n) = Θ (g (n))

או

f (n) = ω (g (n))

או

f (n) = o (g (n))

.
שימו לב לא לכתוב "מתקיים יחס

o

", אלא "מתקיים

f (n) = o (g (n))

" (למשל).

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

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