איך לתרגל שאלות רקורסיה במבוא למדעי המחשב?

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

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

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

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

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

מבוא למדעי המחשב - רקורסיה

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

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

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

רמת קושי:

מה הסיבוכיות ב-

Θ

של הנוסחה הבאה:

T (n, m) = \frac{T ( n - 1 , m )}{2} + nm

כאשר

T (1, m) = 1

, כפונקציה של

n, m

כאשר

m > 0

.

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

סיבוכיות זמןרקורסיה

שאלה 2 - סעיף ב (15 נקודות)

בשאלה זו נעסוק בעצים בינאריים של מספרים אי-שליליים. נתונות שתי המחלקות IntegerBinaryTree, IntegerBinaryNode, המחלקות את המרחיבות BinaryTree<Integer>, BinaryNode<Integer> בהתאמה.

השלימו במחלקה IntegerBinaryTree את השיטה הבוליאנית pathSum(int sum) אשר מקבלת מספר שלם sum ומחזירה ערך true אם קיים מסלול כלשהו בעץ מהשורש לעלה אשר סכום המספרים בקודקודי המסלול הוא בדיוק sum. אם לא קיים מסלול כזה השיטה מחזירה ערך false (5 נקודות).

לצורך משימה זו עליכם גם להשלים שיטה בעלת שם זהה במחלקה IntegerBinaryNode (10 נקודות).

דוגמאות:
בעץ המספרים הבא המכיל מספרים:

• קריאה לשיטה עם הערך 12 תחזיר true (כי

5 + 1 + 6 = 12

).
• קריאה לשיטה עם הערך 14 תחזיר false.
• קריאה לשיטה עם הערך 5 תחזיר false.

הערה: בעץ ריק לא קיים מסלול משורש לעלה ולכן השיטה מחזירה false.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

שאלה 1 - סעיף ב (10 נקודות)

השלימו את הפונקציה canFactorizeToTarget(int[] primes, int n) המקבלת מערך לא ריק של מספרים ראשוניים יחודיים ומספר n גדול או שווה ל-2, ומחזירה ערך true אם ניתן לייצג את n כמכפלת גורמים ראשוניים מהמערך primes (כלומר, כל הגורמים הראשוניים השונים של n נמצאים במערך primes). אחרת הפונקציה מחזירה false. כל גורם במערך יכול להופיע במכפלה מספר לא מוגבל של פעמים. המערך לא בהכרח ממויין.

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

דוגמאות:
• עבור

n = 3

והמערך

{3}

הפונקציה תחזיר ערך true.
• עבור

n = 15

והמערך

{2, 3, 5, 11}

הפונקציה תחזיר ערך true.
• עבור

n = 27

והמערך

{3}

הפונקציה תחזיר ערך true.
• עבור

n = 36

והמערך

{3, 7}

הפונקציה תחזיר ערך false.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

רקורסיהמערכיםלולאותתנאים

שאלה 2 - סעיף א (15 נקודות)

בהינתן איבר element, מחרוזת המתארת את מסלול החיפוש אחר element בעץ חיפוש בינארי היא מחרוזת מעל הא"ב

{L, R}

המתארת את ה"צעדים" שיש לבצע מהשורש בכדי למצוא את element בעץ. אם element לא נמצא בעץ, ובפרט כשהעץ ריק ולא מכיל אף איבר, לא קיימת מחרוזת כזו ואנו נייצג מקרה כזה כמחרוזת ששווה ל-null.

דוגמאות: בעץ החיפוש הבא המכיל מספרים:

תרשים לשאלה

• מחרוזת החיפוש אחר האיבר 2 היא LR.
• מחרוזת החיפוש אחר האיבר 1 היא L.
• מחרוזת החיפוש אחר האיבר 7 היא RLR.
• מחרוזת החיפוש אחר האיבר 5 היא המחרוזת הריקה.
• מחרוזת החיפוש אחר האיבר 11 היא מחרוזת ששווה ל-null.

עליכם לממש במחלקה BinarySearchTree את השיטה searchPathString(T element) אשר מקבלת איבר element ומחזירה את מחרוזת החיפוש של element בעץ.

לצורך משימה זו עליכם להשלים בנוסף שיטה בעלת שם זהה במחלקה BinarySearchNode. השיטה במחלקה זו מקבלת איבר element ופרמטר נוסף אותו עליכם לקבוע.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

שאלה 4 - סעיף א (15 נקודות)

נאמר שמחרוזת היא כמעט פלינדרום אם ניתן להפוך אותה לפלינדרום על-ידי מחיקה של לכל היותר תו אחד. השלימו את הפונקציה הבוליאנית almostPalindrome(String s) המקבלת מחרוזת s שונה מ-null, ובודקת האם היא כמעט פלינדרום.

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

דוגמאות:
• עבור המחרוזת "abba" יוחזר true.
• עבור המחרוזת "abca" יוחזר true.
• עבור המחרוזת "abbac" יוחזר true.
• עבור המחרוזת "abcda" יוחזר false.
• עבור המחרוזת "a" יוחזר true.
• עבור המחרוזת "" יוחזר true.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

רקורסיהמחרוזותפלינדרוםלולאותתנאיםOverloading

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

n o d e

בעץ נוסיף את השדה

k ey_r an g e

שהוא list המכיל זוג מספרים שלמים, אשר מייצגים את טווח המפתחות בתת העץ שלו. זאת אומרת,

k ey_r an g e [0]

יהיה שווה למפתח המינימלי בתת העץ של הצומת ו-

k ey_r an g e [1]

יהיה שווה למפתח המקסימלי בתת העץ של הצומת.

המחלקות TreeNode ו-BinarySearchTree יכילו את השדות הבאים (השינוי מהכיתה מסומן בקו תחתון):

לדוגמה, בעץ המצורף tree מוצמדים לכמה צמתים ערכי ה-key_range התקינים שלהם. העץ מכיל: שורש 18 עם key_range

[6, 38]

, ילד שמאלי 13 עם key_range

[6, 11]

, ילד ימני 29. תת-העץ השמאלי של 13: צומת 11, וילד שמאלי שלו 6. תת-העץ של 29: ילד שמאלי 24 (עם ילדים 19, 25), ילד ימני 38. לצומת 25 key_range

[25, 25]

.

הקוד הבא, בהינתן העץ tree מהדוגמה, ידפיס את הטווח עבור הבן הימני של השורש:
>>> print(tree.root.right.key_range) → (19, 38)

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

[N o n e, N o n e]

.

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

ב. (7 נק') כעת, נרצה להוסיף למחלקה BinarySearchTree את המתודה update_all_key_range(self) אשר מעדכנת את טווחי המפתחות בכל הצמתים בעץ, תוך שימוש במתודה שמומשה בסעיף א'. הקוד הבא מציע מימוש:

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

n

).
בנוסף, ציינו האם הקוד נכון, ואם אינו נכון הציעו תיקון (בקצרה).

ג. (5 נק') ממשו מחדש את המתודה update_key_range של המחלקה TreeNode. השם של המימוש החדש יהיה update_key_range_2.
הנחה שתקפה לסעיף זה בלבד: הילדים הישירים של הצומת אותו מעדכנים, כבר מכילים ערכים תקינים בשדה key_range.
הנחיה: על המימוש להיות יעיל ככל שניתן מבחינת סיבוכיות זמן אסימפטוטית כתלות במספר הצמתים בעץ.

ד. (7 נק') כעת נשנה את הקוד של update_all_key_range, אך ורק על ידי החלפת הקריאה ל-update_key_range בקריאה ל-update_key_range_2.

ציינו מה סיבוכיות זמן הריצה של המתודה המעודכנת update_all_key_range במקרה הגרוע כתלות בכמות הצמתים (

n

). בנוסף, ציינו האם הקוד נכון, ואם אינו נכון הציעו תיקון (בקצרה).

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

התכנית הבאה מתקמפלת ורצה.

I. (4 נק') מה פלט התכנית?

II. (4 נק') מה סיבוכיות f ב-

Θ

כפונקציה של

n

, כאשר

n

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

n

הוא חזקה של 2). הציגו את הנוסחה, הראו את דרך הפתרון ואת התוצאה הסופית.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

מעקב אחר קודסיבוכיות זמןרקורסיה

מחרוזת מוכלת היא מחרוזת שהאותיות שלה מופיעות לפי הסדר בתוך מחרוזת אחרת, לא בהכרח ברצף. למשל, המחרוזת "apchi" מוכלת במחרוזת "arrpyczhqweimm" במופע יחיד, והמחרוזת "abc" מוכלת ב-"aabcc" ביותר ממופע אחד אפשרי.

מחרוזת נשמרת באמצעות רשימה מקושרת של קדקדי Mystring המצביעים ל-Letter, כך שלכל אות יש עלות (גבוהה מ-0).

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

בדוגמה באיור, העלות הנמוכה ביותר של המחרוזת "abc" המוכלת במחרוזת "aabcc" השמורה במבנה הנתון (עם עלויות a:4, a:6, b:7, c:8, c:6) היא 4+7+6 = 17 (ה-a השמאלי, b באמצע וה-c הימני).

אם המחרוזת לא מוכלת כלל, הפונקציה תחזיר 0.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

רקורסיהרשימות מקושרותתת-סדרהמחרוזות

שאלה 2 (30 נקודות)

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

בשאלה זו נעסוק במימוש שתי שיטות במחלקה הגנרית BinarySearchNode<T>, כמפורט בסעיפים א' וב'. בנוסף, עומדות לרשותכם שתי שיטות בהן תוכלו להיעזר כרצונכם:

• השיטה T findMin() מחזירה את הערך המינימלי בתת-העץ המושרש בקודקוד הנוכחי.
• השיטה T findMax() מחזירה את הערך המקסימלי בתת-העץ המושרש בקודקוד הנוכחי.

סעיף א (15 נקודות)

השלימו את שיטת העזר הבוליאנית private boolean replace(T newData) אשר מקבלת ערך newData ובודקת האם ניתן להחליף בינו לערך השדה data כך שתת העץ המושרש בקודקוד הנוכחי נשאר עץ חיפוש בינארי. אם התשובה חיובית, השיטה מבצעת את ההחלפה ומחזירה true. אחרת השיטה מחזירה false, וערך השדה data אינו משתנה.

הנחיית חובה: בשיטה זו אין להוסיף פקודת return מעבר לפקודה הניתנת בתבנית (השורה האחרונה בשיטה).

דוגמאות:

בעץ החיפוש הבא המכיל מספרים:

• אם מפעילים את השיטה על השורש עם הערך

newData = 5

יוחזר הערך true כי אם מחליפים את ערכו של השורש ב-5 תת-העץ המושרש בו נשאר עץ חיפוש בינארי.

• אם מפעילים את השיטה על השורש עם הערכים

newData = 3

newData = 12

או

newData = 0

יוחזר הערך false והעץ לא ישתנה, כי תת-העץ המתקבל לאחר החלפת ערכו של השורש ב-3, 12 או 0 איננו עץ חיפוש בינארי.

סעיף ב (15 נקודות)

השלימו את השיטה הבוליאנית public boolean replace(T replaceMe, T newData) המקבלת שני ערכים replaceMe ו-newData.

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

אם לא ניתן לבצע את ההחלפה, השיטה אינה משנה את העץ ומחזירה false.

דוגמאות:

• בעץ החיפוש הבא המכיל מספרים נתייחס לשורש העץ כאל node:

תרשים לשאלה

node:
    7
   / \\
  2   11
 / \   \\
1   4   13
         \\
          14

node.replace(2,3):
    7
   / \\
  3   11
 / \   \\
1   4   13
         \\
          14

• בהפעלת השיטה node.replace(2, 3) יוחזר הערך true ויתקבל תת העץ מימין.

• בהפעלת השיטה node.replace(2, 6) יוחזר הערך false ולא יבוצע שינוי בעץ מאחר שאם תתבצע ההחלפה העץ לא יישאר עץ חיפוש בינארי.

• בהפעלת השיטה node.replace(5, 6) יוחזר false ולא יבוצע שינוי בעץ מאחר שלא קיים בתת-העץ שמושרש ב-node קודקוד שערכו 5.

הנחיית חובה: בשיטה זו אין להוסיף פקודת return מעבר לפקודה הניתנת בתבנית (השורה האחרונה בשיטה).

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

בהינתן מחרוזת

s t = s_{0} s_{1} \dots s_{n - 1}

בעלת

n

תווים, תת מחרוזת של

s t

מוגדרת להיות מילה

w = s_{i_{1}} s_{i_{2}} \dots s_{i_{k}}

כך ש-

0 \leq i_{1} < i_{2} < \dots < i_{k} \leq n - 1

.

לדוגמה, קבוצת תתי המחרוזות של המחרוזת

ab c

היא:

{ϵ, a, b, c, ab, a c, b c, ab c}

, וקבוצת תתי המחרוזות של המחרוזת

aa

היא

{ϵ, a, aa}

, כאשר הסימון

ϵ

מייצג את המחרוזת הריקה, שהיא תת מחרוזת חוקית של כל מחרוזת (המחרוזת הריקה היא תת מחרוזת חוקית גם של המחרוזת הריקה).

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

s t = ab c d

המילה

a c

היא תת מחרוזת של

s t

, אבל

c a

היא לא תת מחרוזת של

s t

.

בשאלה זו נפתור את בעיית תת המחרוזת המשותפת הארוכה ביותר (Longest Common Subsequence, LCS). בבעיה זו נתונות שתי מחרוזות

s t_{1}, s t_{2}

ועלינו למצוא את האורך המקסימלי של מילה

w

אשר מהווה תת מחרוזת גם של

s t_{1}

וגם של

s t_{2}

.

דוגמאות:

$L C S (b x c g, ab c d e f g) = 3$ (כאן המחרוזת המשותפת הארוכה ביותר היא $b c g$ ואורכה 3).
$L C S (aaa, aba) = 2$ (כאן המחרוזת המשותפת הארוכה ביותר היא $aa$ ואורכה 2).
$L C S (a x, x a) = 1$ (כאן מחרוזת משותפת ארוכה ביותר היא למשל $a$ ואורכה 1).
$L C S (bina r y, co m p u t er) = 1$ (כאן המחרוזת המשותפת הארוכה ביותר היא $r$ ואורכה 1).
$L C S (aaaa, x y z) = 0$ (כאן המחרוזת המשותפת הארוכה ביותר היא המחרוזת הריקה ואורכה 0).

לאורך השאלה ניתן להניח כי שני הקלטים

s t_{1}, s t_{2}

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

א. (10 נק') נתון פתרון רקורסיבי לבעיית LCS. השלימו את הקוד המטפל במקרי הקצה ובמקרה הכללי בשורות החסרות.
הנחיה: אסור להשתמש ב-slicing.

ב. (10 נק') נסמן

m = l e n (s t_{1})

n = l e n (s t_{2})

ונניח לצורך פשטות כי

m = n

. נסמן ב-

S (n)

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

l cs_r ec

.

(i) הקיפו בעיגול את התשובה המתארת את גודל עץ הרקורסיה במקרה הטוב ביותר עבור האלגוריתם שהוצג בסעיף א' כתלות ב-

n

.

האפשרויות:

S (n) = O (1)

S (n) = Θ (lo g n)

S (n) = Θ (n)

S (n) = Θ (n lo g n)

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

S (n) = Θ (n^{c})

עבור קבוע

c \geq 3

כלשהו,

c_{1} \cdot 2^{n} \leq S (n) \leq c_{2} \cdot 4^{n}

עבור קבועים

c_{1}, c_{2}

חיוביים כלשהם,

S (n) = Θ (n!)

.

(ii) הקיפו בעיגול את התשובה המתארת את גודל עץ הרקורסיה במקרה הגרוע ביותר עבור האלגוריתם שהוצג בסעיף א' כתלות ב-

n

.

ג. (5 נק') בסעיף זה נוסיף ממואיזציה למימוש הרקורסיבי משעיף א'. השלימו את הקוד של הפונקציה

l cs_m e m

למטה. הפונקציה מקבלת מחרוזת

s t

המורכבת מאותיות קטנות באנגלית.
הנחיות: (1) אסור להשתמש ב-slicing. (2) והפתרון צריך לרוץ בסיבוכיות זמן פולינומית בממוצע.

ד. (5 נק') נאמר שמחרוזת

s t

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

a ez

היא מונוטונית עולה, גם

aabb c

היא מונוטונית עולה, אבל

a d x c

היא לא מונוטונית עולה (מכיוון ש-

c

קטן למשל מ-

d

אבל מופיע אחריו).

השלימו את הקוד של הפונקציה longest_monotone למטה. הפונקציה מקבלת מחרוזת

s t

המורכבת מאותיות קטנות באנגלית ('a','b','c',...,'z'), ומחזירה את האורך המקסימלי של תת מחרוזת מונוטונית עולה של

s t

. דוגמאות:

$l o n g es t_m o n o t o n e (a x b y cz d) = 4$ (המחרוזת המונוטונית עולה הארוכה ביותר היא $ab c d$ ).
$l o n g es t_m o n o t o n e (aabaa) = 4$ (המחרוזת המונוטונית עולה הארוכה ביותר היא $aaaa$ ).
$l o n g es t_m o n o t o n e (x a) = 1$ (מחרוזת מונוטונית עולה ארוכה ביותר היא למשל $a$ ).

הנחיות: (1) על הפונקציה להשתמש בפונקציה

l cs_m e m

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

רקורסיהמחרוזותתת-סדרהסיבוכיות זמןmemoization

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

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