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

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

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

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

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

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

מבני נתונים ומבוא לאלגוריתמים - סריקת עצים

סיבוכיות, מבני נתונים בסיסיים ואלגוריתמי מיון וחיפוש

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

תתי-נושאים של עצי חיפוש

רמת קושי:

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

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

★★★★★

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

א) (9 נקודות) נתונה ערימת מינימום

A

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

ב) (8 נקודות) נתון עץ חיפוש בינארי

T

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

ג) (8 נקודות) נתון עץ ערכי מיקום

T

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

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

א) (13 נקודות) נתונה ערימת מינימום

A

בגודל

n

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

C > 0

.
כתוב שגרה לתיקון המבנה

A

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

C

למפתחות המסויימים).
על השגרה לעבוד בזמן

O (lo g^{2} n)

.

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

דוגמא: בערימת המינימום שבאיור, המסלול השמאלי הוא המסלול 3-4-10-21.

ב) (12 נקודות) נתון עץ חיפוש בינארי

T

בגודל

n

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

x, y

בעץ

T

, המקיימים את התנאי

k ey [x] + k ey [y] = 2 k ey [r oo t [T]]

. אם אין שני צמתים המקיימים את התנאי האלגוריתם מחזיר

F A L S E

.
על השגרה לעבוד בזמן

O (n)

. מותר להקצות

O (1)

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

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

א) (15 נק') נתון עץ חיפוש בינארי

T

עם מפתחות ייחודיים, ונתונים מצביעים לשני צמתים

U, V

, כאשר נתון

U . k ey < V . k ey

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

[U \dots V]

:

הראו כי זמן הריצה של האלגוריתם הוא

O (h + k)

, כאשר

h

הוא גובה העץ, ו-

k

הוא מספר האיברים בתחום. הניחו כי Visit(X) מתבצע בזמן

O (1)

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

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

k

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

A

- המפתחות משמאל למסלול החיפוש.

B

- המפתחות במסלול החיפוש.

C

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

a \in A, b \in B, c \in C

מקיימים בהכרח

a \leq b \leq c

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

האם ניתן לשחזר עץ חיפוש בינרי (עח"ב)

T

מהסריקה התוכית (in-order) שלו?

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

עצי חיפושסריקת עצים

האם ניתן לשחזר עץ חיפוש בינרי (עח"ב)

T

מהסריקה התחילית (pre-order) שלו?

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

עצי חיפושסריקת עצים

בהנחה שהמפתחות של עץ חיפוש בינרי (עח"ב)

T

שונים זה מזה, האם ניתן לשחזר את

T

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

עצי חיפושסריקת עציםרקורסיה

נניח שעץ חיפוש בינרי (עח"ב)

T

נבנה מסדרת מפתחות

L

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

T

מהסריקה התחילית שלו?

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

עצי חיפושסריקת עציםרקורסיה

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

n = 2^{k} - 1

(עבור

k > 0

)?

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

עצי חיפושעץ אדום-שחורסריקת עציםסימון אסימפטוטי

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

עצי חיפושסריקת עצים

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

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