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

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

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

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

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

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

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

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

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

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

רמת קושי:

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

★★★★★

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

לחברת Boeing יש מערכת ניהול ממוחשבת עבור פעילות המחסן המרכזי של החברה, המרכז מידע אודות חלקי חילוף למטוסים שלהם (allparts), כמו גם רשימת הטכנאים והטכנאיות עם כשירות לטיפול בתחזוקת המטוסים (techlist) ורשימת מטוסים שיש עבורם הזמנת עבודה (orders). המערכת מסוגלת לטפל בלכל היותר MAX מטוסים בו"ז. בזמן נתון יש curOrders מטוסים בטיפול, והמידע אודותם מרוכז באינדקסים 0, ..., curOrders-1 במערך ה-orders.

המידע השמור עבור כל פריט במחסן: המספר הסידורי שלו (serialNum, ייחודי במערכת), שמו (partName), הכמות שיש ממנו במחסן (quantity), המחיר של כל פריט (price), וההכשרה הנדרשת לטיפול בפריט (certR).

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

המידע השמור עבור כל טכנאי/ית במערכת: מספר ת.ז. (techID), שם (techName), וההכשרה של הטכנאי/ת (cert).

המידע אודות הטכנאים/ות במחסן שמור ברשימה מקושרת ממויינת לפי Cert מהגבוה לנמוך, כך שקודם יופיעו מי שהם Expert, אח"כ Senior, וכו'.

כאשר מגיע מטוס חדש לטיפול (לכל מטוס יש מספר זנב ייחודי – tailNum), מיוצר עבורו order המכיל מערך parts עם המספרים הסידוריים של הפריטים הנדרשים על מנת לתקן את המטוס (ניתן להניח כי ברשימה יש פריטים שונים), ומצביע לטכנאי/ת שיטפלו במטוס – ה-manager. ניתן לטפל במטוס רק אם קיימת הכשרה מתאימה לטיפול בכלל הפריטים (כלומר, חלק החילוף עם ה-certR הגבוה ביותר קובע את ההכשרה המינימלית של הטכנאי/ית לטיפול).

כל המידע שמור ללא בזבוז מקום כלל (למעט מה שמובא בהגדרות).

נתונות ההגדרות הבאות:

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

א. (3 נק') כתבו פונקציה המקבלת פרטי טכנאי/ת, מייצרת Technician עם הפרטים, ומחזירה את המצביע אליו.

ב. (2 נק') כתבו פונקציה המקבלת פרטי פריט, מייצרת עבורו SparePart עם הפרטים, ומחזירה את המצביע אליו.

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

ד. (6 נק') כתבו פונקציה המקבלת פרטי פריט, ומוסיפה אותו/ה למערכת המחסן באופן הבא:

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

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

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

אם התנאים מתקיימים, היא תעדכן את נתוני הטיפול ברשומות (order המתאים) באופן הבא: תכניס אותו לטיפול, תמצא עבורו טכנאי/ת עם הסמכה לטיפול – הראשון/ה בהסמכה הנדרשת, ותוריד ב-1 את מספר הפריטים שהשתמשנו בו עבור הטיפול מעץ הפריטים במחסן (אם נשארו 0 פריטים, משאירים את הפריט במבנה הנתונים עם כמות 0).

אם אין טכנאי/ת בהסמכה הנדרשת בדיוק, יש למצוא טכנאי/ת בהסמכה מעל (למשל Expert יכול/ה לטפל בהזמנה הדורשת Junior).
אם הפונקציה מצליחה להכניס לטיפול היא תחזיר 0, אם היא נכשלת היא תחזיר -1.

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

i. פונקציות adjustPrice המעדכנות את המחיר עם val, ו-printPart המדפיסה את פרטי חלקי החילוף, שתיהן מהסוג Scan:

שימו לב שהערך val של עדכון המחיר יכול להיות חיובי או שלילי. בכל מקרה, הערך החדש לא יהיה נמוך מ-0.

ii. פונקצית updateParts העוברת על allparts ב-DFS ב-Post Order ומעדכנת/מדפיסה את כל חלקי החילוף באמצעות הפונק' scan.

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

O (m + n)

כש-

m, n

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

ח. (7 נק') כתבו פונקציה המקבלת נתוני מחסן, עוברת על כל נתוני המערכת ומוחקת אותם. המלצה: השתמשו בפונקצית updateParts מסעיף ו', וכתבו פונקציית Scan רלוונטית שתעזור במחיקה.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

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. (3 נק') מה הייצוג העשרוני של המספרים המצוינים למטה? הניחו כי כולם מיוצגים ב-4 סיביות בשיטת המשלים ל-2.

המספר	הייצוג העשרוני
$1 1_{2}$
$2 2_{4} \oplus 1 1_{2}$
$2 3_{4}$
$1 0_{2}$
$1 2_{6}$
$1 3_{4}$

II. (2 נק') סדרו את המספרים שהתקבלו בסעיף I בעץ החיפוש הבינארי הנתון (מבלי לשנות את מבנה העץ).

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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 יכילו את השדות הבאים (השינוי מהכיתה מסומן בקו תחתון):

הערה: לאורך כל השאלה, אלא אם כן מצוין במפורש, אין להניח כי השדה

k ey_r an g e

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

[N o n e, N o n e]

.

א. (6 נק') השלימו את מימוש המתודה update_key_range() למחלקה TreeNode, שתעדכן את השדה

k ey_r an g e

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

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

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

n

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

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

k ey_r an g e

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

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

n

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

סעיפים א – ג להלן עוסקים בעץ חיפוש בינרי (binary search tree) המכיל

5

צמתים בדיוק, שהערכים שלהם הם כל המספרים השלמים בין

1

ל-

5

. (כל ערך מופיע פעם אחת בלבד בעץ).
ענו על השאלות הבאות:

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

ב. ציירו עץ חיפוש בינרי המכיל

5

צמתים שהם כל המספרים השלמים בין

1

ל-

5

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

1

ו-

4

2. לצומת שערכו הוא

2

יש נכד (בן של בן) שערכו הוא

3

.
אם לא יכול להיות עץ כזה, הסבירו מדוע אי אפשר.

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

5

צמתים שהם כל המספרים השלמים בין

1

ל-

5

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

1

–

5

3

צמתים בלבד.
נתונים שלושה ערכים

a, b, c

שונים זה מזה, כאשר

a

הוא הערך הקטן ביותר ו-

c

הוא הגדול ביותר. אלו הם הערכים שנמצאים בעץ.

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

a

.

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

b

.

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

c

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

עצים בינארייםעץ חיפוש בינארי

סעיפים א - ג להלן עוסקים ב עץ חיפוש בינרי (binary search tree) המכיל 5 צמתים בדיוק, שהערכים שלהם הם כל המספרים השלמים בין 1 ל- 5. (כל ערך מופיע פעם אחת בלבד בעץ).
ענו על השאלות הבאות:
א. מה הגובה (מספר הרמות) המינימלי ומה הגובה המקסימלי של עץ כזה? ציירו עצים מתאימים. אחד עם גובה מינימלי ואחד עם גובה מקסימלי.
ב. ציירו עץ חיפוש בינרי המכיל 5 צמתים שהם כל המספרים השלמים בין 1 ל- 5 (כל ערך מופיע פעם אחת בלבד בעץ), וכן מתקיימים בו שני התנאים הבאים:
1. בעץ קיים זוג אחים (שיש להם הורה משותף) שערכיהם הם 1 ו- 4
2. לצומת שערכו הוא 2 יש נכד (בן של בן) שערכו הוא 3.
אם לא יכול להיות עץ כזה, הסבירו מדוע אי אפשר.
ג. אם מוסיפים לעץ חיפוש בינרי המכיל 5 צמתים שהם כל המספרים השלמים בין 1 ל- 5 (שכל ערך מופיע פעם אחת בלבד בעץ), צומת נוסף עם אחד מהערכים

1 - 5

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

עצים בינארייםעץ חיפוש בינארי

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

השלימו את המחלקה הבאה המממשת איטראטור על עץ בינארי המחזיר את האיברים בסדר In-order הפוך.

כלומר, ביחס לשורש העץ, האיטראטור מחזיר קודם את אברי תת העץ הימני (בסדר In-order הפוך), אחר כך את האיבר שבשורש ולבסוף את אברי תת העץ השמאלי (בסדר In-order הפוך).

לדוגמה, עבור העץ שבאיור, האיטראטור יחזיר את האיברים בסדר הבא (8 תחילה, -1 בסוף):
8, 6, 5, 4, 2, -1

תרשים לשאלה

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

נתון כי במחלקה BinaryTree<T> נתונה כעת השיטה reversedInOrderIterator() המחזירה עצם מהמחלקה הנתונה בסעיף א.

זאת בנוסף לשיטה inOrderIterator() המחזירה איטראטור In-order רגיל.

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

לדוגמה, עבור העץ bst שבאיור, הקוד הבא ידפיס את התשובות שבהערה:

הערות והנחיות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

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