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

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

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

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

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

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

מבני נתונים - רקורסיה

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

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

תתי-נושאים של רקורסיה

רמת קושי:

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

G_{0}, G_{1}, G_{2}, \dots

(ראו תרשים):

תרשים לשאלה

סעיף א' (10 נקודות)
הוכיחו באינדוקציה על המבנה כי גובה העץ

G_{i}

הוא

2 i

.

סעיף ב' (15 נקודות)
הוכיחו כי משפחת העצים הרקורסיביים מסדר שני היא משפחה מאוזנת.

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

O (lo g n)

, כאשר

n

הוא מספר הצמתים בעץ.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד א · 2026 · סמסטר א

★★★★★

רקורסיהנוסחת נסיגההוכחת נכונותסימון אסימפטוטיBig-Oעצים בינאריים

שאלה 3:
נתון מערך בגודל

n

.
רוצים למצוא את האיבר שהוא ה-

k

-י הקטן ביותר כאשר

k < \frac{n}{2}

.

מותר להשתמש ב SELECT רק על תתי מערכים בגודל לכל היותר \frac{n}{2}.

הראו אלגוריתם הרץ בזמן

O (n)

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד ב · 2026 · סמסטר א

★★★★★

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

יהי

A [1, \dots, n]

מערך של מספרים שלמים. לכל תת מערך

A [i, \dots, j]

עבור

1 \leq i \leq j \leq n

נגדיר את סכום תת המערך כ-

S_{i, j} = \sum_{ℓ = i}^{j} A [ℓ]

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

A

קלט: מערך $A [1, \dots, n]$ מערך של מספרים שלמים.
פלט: סכום תת המערך המקסימלי של המערך $A$ . כלומר, $max_{i, j \in [n], i \leq j} S_{i, j}$ .

למשל, עבור הקלט

A = [2, - 4, 1, 9, - 6, 7, - 3]

סכום תת המערך המקסימלי של

A

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

O (n^{3})

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

O (n lo g n)

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

O (n lo g n)

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד ב · 2024 · סמסטר ב

★★★★★

סיבוכיות זמןBig-Oרקורסיהנוסחת נסיגההפרד ומשול

[1] ראינו כיצד להכפיל שני מספרים

X, Y

, כל אחד בעל

n

סיביות בשיטת הפרד ומשול בזמן

O (n^{2})

, כאשר כל מספר חולק לשני חלקים באורך

n /2

סיביות כל אחד. כאשר צמצמנו את מספר הקריאות הרקורסיביות מ 4 ל 3, הסיבוכיות ירדה ל

O (n^{1.58})

. שאלה זאת דנה בהצעה לחלק כל מספר ל3 חלקים באורך שווה, במקום רק ל2.

סעיף 5 נקודות.

א) הגדירו את

X

Y

כל אחד כפונקציה של שלושת חלקיהם

X_{1}, X_{2}, X_{3}

Y_{1}, Y_{2}, Y_{3}

ב) הראו איך ניתן לחשב את

X * Y

ע"י 9 קריאות רקורסיביות (הפרד) ועוד עבודת איסוף התוצאות שעלותה לינארית ב

n

(ומשול)
ג) מה הסיבוכיות של שיטה זו?
ד) בדומה למה שראינו במקרה של חלוקה ל2 חלקים, הראו איך, ע"י חישוב שלושת הערכים הבאים:

G = (X_{1} + X_{3}) (Y_{1} + Y_{3})

F = (X_{2} + X_{3}) (Y_{2} + Y_{3})

E = (X_{1} + X_{2}) (Y_{1} + Y_{2})

ניתן להוריד את מספר הקריאות הרקורסיביות מ9 ל 6.
ה) מה הנוסחה המתקבלת עבור הסיבוכיות?

(3 נקודות) בונוס: האם כדאי לחלק ל3?

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד א · 2023 · סמסטר ב

★★★★★

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

[3]
א. (10 נקודות) יהי

T

עץ AVL עם

n

קודקודים.
מצאו

n

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

ב. (15 נקודות) הוכח שקיים אלגוריתם הבונה מכל סדרה בת

n

איברים לאו דווקא שונים מהתחום

[1.. n]

עץ AVL בזמן

O (n)

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד א · 2023 · סמסטר ב

★★★★★

עצי AVLעץ חיפוש בינארימיון ספירהרקורסיהסיבוכיות זמן

א( (16) נתונה קבוצה של

n

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

O (n lo g n)

עץ חיפוש בינארי שבקודקודיו שמורים הערכים שבתוך הקבוצה. בדרכים שונות − הכוונה עם רעיונות שונים ולא רק על ידי שינוי פרמטרים.

ב( (9) הראו שאי אפשר לבנות את עץ החיפוש בינארי בסעיף הקודם בזמן

o (n lo g n)

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד א · 2022 · סמסטר ב

★★★★★

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

עץ טרינרי מושלם הוא עץ שלכל קודקוד פנימי בו יש 3 בנים.
הוכיחו את הטענות הבאות באינדוקציה על מבנה העץ:

א. לעץ טרינרי מושלם תמיד מספר עלים אי זוגי.

ב. לעץ טרינרי מושלם עם

n

עלים יש

(n - 1) /2

קודקודים פנימיים.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד א · 2021 · סמסטר ב

★★★★★

הוכחת נכונותרקורסיהעצים

יהי

T

עץ בינארי. נאמר כי

T

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד ב · 2021 · סמסטר ב

★★★★★

עצים בינארייםרקורסיהסיבוכיותסיבוכיות זמן

יהי

A

מערך עם

n

איברים שונים. נאמר כי

A

מערך ממוין באופן מעגלי אם קיים

k

כך שאחרי הזזת האיברים

k

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

לדוגמא: המערך

A

הבא הוא מערך ממוין מעגלי כאשר

k = 2

.

א. כתוב/י אלגוריתם המקבל מערך

A

עם

n

איברים שונים ממוין באופן מעגלי ואינדקס

i \in {1, \dots, n}

ומחזיר 0 אם האיבר הגדול ביותר במערך נמצא משמאל לאינדקס

i

(כולל, ז"א ב-

A [1 \dots i]

) אחרת, יחזיר 1. זמן הריצה

O (1)

.
ב. כתוב/י אלגוריתם המקבל מערך

A

עם

n

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

O (lo g n)

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד ב · 2021 · סמסטר ב

★★★★★

חיפוש בינאריסיבוכיות זמןרקורסיהנוסחת נסיגההוכחת נכונות

להלן תיאור בעית אורך תת הסדרה שותפת משולשת הארוכה ביותר:

קלט: שלוש הסדרות:

X, Y, Z

כל אחת באורך

n

.
פלט: אורך הסדרה

A

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

X, Y, Z

.

הבעיה ניתנת לפתרון בעזרת תכנון דינמי

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

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד א · 2020 · סמסטר ב

★★★★★

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

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

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