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

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

★★★★★

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

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

★★★★★

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

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

★★★★★

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

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

T (n)

T (n) = {Θ (1) 2 T (\frac{2 n}{3}) + 5 n \cdot lo g^{3} (n) i f n = 1 i f n > 1

ב) (12 נקודות) הוכיחו או הפריכו כל אחת מהטענות הבאה:

i.

2^{n} = Θ (2^{2 + n})

ii.

2^{n} = Θ (2^{2 \cdot n})

הערה: ניתן להפריך יחס

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

ע"י הוכחה שמתקיים יחס

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

, או יחס

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

.

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

A

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

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

T

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

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

T

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

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

T (n)

T (n) = {Θ (1) 4 T (\frac{n}{4}) + n + \frac{1}{n} i f n = 1 i f n > 1

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

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

. יש לקבוע ולהוכיח האם מתקיים

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

או

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

או

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

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

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

" (למשל).

f (n) = n^{10 l o g n}

g (n) = (lo g n)^{n}

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

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