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

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

★★★★★

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

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

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

★★★★★

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

שאלה מותאמת לסמסטר הלימוד
שאלה 6 (25 נקודות) – השאלה מיועדת רק לסטודנטים שלמדו בשנת 2024

תכננו מבנה

S

, שהוא עץ א"ש, שמפתחותיו הם מספרים טבעיים, ושניתן לבצע עליו את הפעולות הבאות:

B U I L D (S, A)

: בניית

S

ממערך ממוין

A

בגודל

n

, בזמן ריצה

O (n)

I N S E R T (S, k)

: מכניס את המפתח

k

למבנה. זמן הריצה

O (lo g n)

H E A V I E S T - P A T H (S)

: החזרת סכום מפתחותיו של המסלול הפשוט הכבד ביותר שמתחיל בשורש, בזמן ריצה

O (n)

.
(מסלול פשוט = מסלול שאינו עובר באף צומת יותר מפעם אחת).

דוגמא: בעץ זה, המסלול הכבד ביותר המתחיל בשורש הוא המסלול 5-2-4-3, וסכום מפתחותיו הוא 14.
(הצמתים השחורים בעץ שחורים באיור והצמתים האדומים בעץ אפורים באיור)

א) (8 נקודות) הוכיחו בשלילה כי המסלול הפשוט הכבד ביותר שמתחיל בשורש חייב להסתיים בצומת ששני בניו הם

T [ni l l]

.

ב) (9 נקודות) כתבו את שגרת

H E A V I E S T - P A T H (S)

.

ג) (8 נקודות) כתבו את שגרת

B U I L D (S, A)

.

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

א) (10 נקודות) הוכיחו על פי ההגדרה את תכונת הטרנזיטיביות עבור היחס

Ω

:
לכל

f, g, h

פונקציות מהטבעיים לטבעיים,
אם

f (n) = Ω (g (n))

וגם

g (n) = Ω (h (n))

אזי

f (n) = Ω (h (n))

.

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

T (n)

. הניחו כי

T (0) = 1

T (n) = 2 T (n - 3) + 1

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

להלן נתונה השגרה הרקורסיבית הבאה, שהקלט שלה הוא תמורה של

(1, 2, ..., n)

(האינדקסים של

A

הם בין 1 לבין

n

, וכן מתקיים שלכל

1 \leq i \leq n

קיים

1 \leq j \leq n

יחיד כך ש

A [j] = i

), וכן שני אינדקסים

1 \leq p, r \leq n

.
הקריאה הראשית לשגרת DoesItSort על מערך

A

הינה: DoesItSort(A, 1, n).

השגרה ReverseSort(A, i, j) ממיינת הפוך את תת המערך $A [i ... j]$ , למשל ReverseSort(A, 2, 5) עבור $A = [3, 4, 6, 1, 2, 5]$ ישנה את $A$ ל- $A = [3, 6, 4, 2, 1, 5]$ .
Partition היא שגרת החלוקה המופיעה בעמוד 122 בספר.

א) (5 נקודות) הריצו את השגרה DoesItSort על המערך

A = (7, 5, 1, 3, 2, 4, 6)

.

ב) (10 נקודות) הוכיחו או הפריכו: DoesItSort(A, 1, n) ממיינת את מערך

A

.
אם לדעתכם השגרה ממיינת כל מערך

A

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

A

בגודל

n

שהוא תמורה של

(1, ..., n)

, שעבורו

A

בסוף ביצוע השגרה אינו ממויין.

ג) (10 נקודות) נתחו את זמן הריצה של DoesItSort(A, 1, n) במקרה הגרוע ביותר ובמקרה הטוב ביותר, בהנחה שסיבוכיות ReverseSort(A, 1, n) היא

Θ (n^{2})

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

נניח שנתונים

n

כדי מים אדומים ו-

n

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

א) (13 נק') הציעו אלגוריתם שתוחלת מספר ההשוואות בו היא

O (n lo g n)

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

ב) (12 נק') בהינתן שקיבולת הכדים הכחולים מוגבלת ב-

m

מ"ל, כאשר

m = O (n)

, ואין אף כד עם קיבולת

0

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

S

שעושה עבודת הכנה ב-

O (n)

, ולאחריה יכול לענות ב-

O (1)

על השאילתא:
RANGE(S, r1, r2) : בהינתן שני מספרים שלמים

r 1, r 2

, בטווח

[0 \dots m]

, מחזיר את מספר הכדים הכחולים עם קיבולת

X

, כך ש

r 1 < X \leq r 2

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

נתון יחס הנסיגה הבא לאלגוריתם רקורסיבי:

T (n) = 2 T (\frac{n}{2}) + n

פתרו את יחס הנסיגה בשתי שיטות:

א. שיטת עץ הרקורסיה.

ב. משפט האב (Master Theorem). ציינו לאיזה מקרה שייכת הנסיגה.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

רקורסיהסיבוכיותנוסחת נסיגה

נתון אלגוריתם מיון

M

הפועל באופן הבא:
בהינתן מערך

A

באורך

n

מוצאים את ערך המיקום ה- $n /3$ ;
מבצעים חלוקה סביבו;
ממיינים את החלק השמאלי (בעזרת אלגוריתם אופטימלי);
מפעילים את האלגוריתם $M$ על החלק הימני של החלוקה באופן רקורסיבי.

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

M

ופתרו אותה.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

מיוןנוסחת נסיגהסיבוכיותרקורסיה

נתון אלגוריתם מיון

M

הפועל באופן הבא:
בהינתן מערך

A

באורך

n

מוצאים את החציון שלו (בעזרת אלגוריתם אופטימלי);
מבצעים חלוקה סביב החציון (בעזרת אלגוריתם אופטימלי);
ממיינים את החלק השמאלי (בעזרת אלגוריתם אופטימלי);
מפעילים את האלגוריתם $M$ על החלק הימני של החלוקה באופן רקורסיבי.

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

M

ופתרו אותה.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

מיוןנוסחת נסיגהסיבוכיותרקורסיה

נתון אלגוריתם מיון

M

הפועל באופן הבא:
בהינתן מערך

A

באורך

n

מוצאים את החציון שלו (בעזרת אלגוריתם אופטימלי);
מבצעים חלוקה סביב החציון (בעזרת אלגוריתם אופטימלי);
ממיינים את החלק השמאלי (בעזרת אלגוריתם אופטימלי);
מפעילים את האלגוריתם $M$ על החלק הימני של החלוקה באופן רקורסיבי.

הוכיחו שהאלגוריתם

M

ממיין נכון את המערך.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

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