איך לתרגל שאלות עצים בינאריים במבוא למדעי המחשב?

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

כמה שאלות עצים בינאריים יש במבוא למדעי המחשב?

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

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

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

מבוא למדעי המחשב - עצים בינאריים

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

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

תתי-נושאים של עצים בינאריים

רמת קושי:

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

★★★★★

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

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

★★★★★

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

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

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

★★★★★

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

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

★★★★★

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

בכיתה ראינו מימוש של hash table (המשתמש ב-chaining לטיפול בהתנגשויות) אשר בממוצע מספקת זמן ריצה קבוע עבור הכנסה ושליפה. הבעיה הייתה במקרה הגרוע. נסמן ב-

n

כמות האיברים בהם נדרשים לטפל,

m

כמות התאים במילון. נניח כי

m = n

.

א. מה סיבוכיות זמן השליפה במקרה הגרוע?

ב. מה סיבוכיות זמן ההכנסה במקרה הגרוע?

דרור הציע להחליף את הרשימות בכל תא, בעצים בינאריים מאוזנים (הניחו כי אנחנו יודעים לשמור את העצים מאוזנים).

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

ג. מה תהיה כעת סיבוכיות זמן השליפה הממוצעת?

ד. מה תהיה סיבוכיות זמן השליפה במקרה הגרוע?

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

טבלאות גיבובסיבוכיות זמןעצים בינאריים

הקלט הוא עץ חיפוש בינארי

t r ee

שבו

n

צמתים (מתקיים

n \geq 1

) בו המפתחות הם מספרים שלמים חיוביים יחודיים, ומספר שלם חיובי

k

.

נאמר שעץ חיפוש בינארי הוא

k

-מאוזן-מפתחות אם מתקיים לכל

i, j

אי-שליליים שונים שקטנים מ-

k

(

i \neq = j

0 \leq i, j < k

), ההפרש בין מספר המפתחות בעץ ששארית החלוקה שלהם ב-

k

היא

i

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

k

היא

j

הוא

1, 0

או

- 1

.

באופן שקול, בכתיב מתמטי, עץ כזה מקיים לכל

0 \leq i, j < k

את הפסוק הבא:

{k ey \in t r ee ∣ k ey mod k = i} - {k ey \in t r ee ∣ k ey mod k = j} \in {- 1, 0, 1}

הערה: בכל סעיפי השאלה הניחו כי פעולות אריתמטיות הן מסיבוכיות זמן

O (1)

.

תזכורת: מחלקות

B ina r y_se a r c h_t r ee

ו-

T r ee_n o d e

מהכיתה.

סעיף א (7 נק'). השלימו את הפונקציה

i s_k ey_ba l an ce d 1 (t r ee, k)

. הפונקציה מקבלת מטיפוס

B ina r y_se a r c h_t r ee

ומספר שלם אי שלילי

k

, ומחזירה

T r u e

אם

t r ee

הוא

k

-מאוזן-מפתחות, אחרת מחזירה

F a l se

. הניחו כי נתונה לכם הפונקציה

co u n t_m o d k_e q_c (t r ee, k, c)

שבהינתן עץ

t r ee

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

k

היא

c

, וכי סיבוכיות הזמן של פונקציה זו היא

O (f (n))

וכי אינה מקצה זיכרון עזר נוסף. על הפונקציה להיות מסיבוכיות זמן

O (f (n) \cdot k)

במקרה הגרוע, ולא להקצות זיכרון עזר נוסף.

סעיף ב (10 נק'). השלימו את הפונקציה

i s_k ey_ba l an ce d 2 (t r ee, k)

שמחזירה

T r u e

אם

t r ee

הוא

k

-מאוזן-מפתחות, אחרת מחזירה

F a l se

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

r ec

. כמו כן על הפונקציה להיות מסיבוכיות זמן

O (n + k)

במקרה הגרוע. מותר לפונקציה

i s_k ey_ba l an ce d 2

להקצות זיכרון עזר (נוסף על הקלט) מסיבוכיות

O (k)

. הסבירו מדוע היא עומדת בדרישת הסיבוכיות הנ"ל.

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

n \leq k

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

O

), אחרת הותירו את התא ריק.

המימוש החדש משפר את זמן הריצה האסימפטוטי במקרה הגרוע: נכון / לא נכון
במידה שמשפר — רשמו את סיבוכיות זמן הריצה החדשה במקרה הגרוע.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

I. (2 נק') נתון עץ בינארי עם הערכים הבאים:

        1
       / \
      2    0
     /    / \
    0    2    3
     \
      1

מה תוצאת סריקת העץ הנתון ב-BFS? כתבו משמאל לימין.

II. (2 נק') הניחו כי המספר שהתקבל לעיל הוא בייצוג בבסיס 4. מה הייצוג הבינארי שלו?

III. (1 נק') מה הייצוג של המספר שהתקבל לעיל בבסיס 16?

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

עצים בינארייםייצוג מספרים

I. (2 נק') נתון גרף המיוצג ברשימה המקושרת שבצד שמאל (6 קדקודים, 0-5). ציירו את הגרף (השלימו קדקודים והקשתות ביניהם בצד ימין).

רשימת השכנויות:

קדקוד 0: → 2 → 3
קדקוד 1: → 2
קדקוד 2: → 5 → 0 → 1
קדקוד 3: → 4 → 0 → 5
קדקוד 4: → 3 → 5
קדקוד 5: → 2 → 3 → 4

II. (2 נק') נתון עץ בינארי עם ערכים 0 ו-1:

מה תוצאת סריקת העץ הבינארי הנתון ב-DFS post order?

III. (1 נק') מה המספר (בייצוג עשרוני) שהתקבל בסעיף II? הניחו שהמספר מופיע בייצוג בינארי בשיטת המשלים ל-1 ב-8 סיביות.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

גרפיםעצים בינארייםייצוג מספרים

נניח שהמחלקה Node שלהלן מממשת צומת בעץ בינרי.

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

נתון העץ הבינרי הבא, ששורשו הוא root:

        8
       / \
     11    6
    / \     \
   4   2    13
  /   / \
 10  3   25
     |
    19

ענו על הסעיפים הבאים:
סעיף א (1 נקודות):
מה תחזיר השיטה find1 בעקבות הקריאה BinaryTree.find1(root, 10)?

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

סעיף ג (2 נקודות):
מה תחזיר השיטה find2 בעקבות הקריאה BinaryTree.find2(root, 3, 2)?

סעיף ד (4 נקודות):
מה מבצעת השיטה find2 באופן כללי כשהיא מקבלת כפרמטרים: שורש של עץ בינרי root, שכל הערכים בצמתיו שונים זה מזה, ושני מספרים שלמים

x

ו-

y

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

סעיף ה (2 נקודות):
מה תחזיר השיטה find3 בעקבות הקריאה BinaryTree.find3(root, 3, 13)?

סעיף ו (4 נקודות):
מה מבצעת השיטה find3 באופן כללי כשהיא מקבלת כפרמטרים: שורש של עץ בינרי root, שכל הערכים בצמתיו שונים זה מזה, ושני מספרים שלמים

x

ו-

y

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

נניח שהמחלקה Node שלהלן מממשת צומת בעץ בינרי.

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

נתון העץ הבינרי הבא, ששורשו הוא root:

          100
         /    \
       50       6
      /  \       \
    120    2     13
   /   \    \
 10     3   25
         \
         19

ענו על הסעיפים הבאים:
סעיף א (2 נקודות):
מה תחזיר השיטה something בעקבות הקריאה BinaryTree.something(root)?

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

סעיף ג (4 נקודות):
מה תדפיס השיטה what בעקבות הפעלת שתי הפקודות להלן:

סעיף ד (6 נקודות):
מה מבצעת השיטה what באופן כללי כשהיא מקבלת כפרמטר שורש של עץ בינרי root ומספר שלם num כלשהו? שימו לב, עליכם לתת תיאור ממצה של מה עושה השיטה באופן כללי, ולא תיאור של מה עושה כל שורה בשיטה, או איך היא מבצעת זאת. כלומר, לכתוב בקצרה השיטה מדפיסה. התייחסו למקרי קצה.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

עצים בינארייםרקורסיהמעקב אחר קוד

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

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