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

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

כמה שאלות עצי B יש במבני נתונים?

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

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

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

מבני נתונים - עצי B

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

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

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

רמת קושי:

הוכיחו או הפריכו:

א) מחיקת ערך כלשהו מתוך עץ 2-3 שבו בכל קודקוד מאוחסן רק ערך אחד תקטין את גובה העץ ב-1.

ב) הוספת ערך אחד X לעץ 2-3 שבו בכל הקודקודים במסלול ההכנסה של X מאוחסנים שני ערכים תגדיל את גובה העץ ב-1.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

עצי Bהוכחת נכונותעץ 2-3

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

"בסוף הוצע העץ כאופציה משלבת
והוא זכור לטוב מספר בראשית"

איזה עץ בינרי זכור מספר בראשית?

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

עצי B

א) נתון B-tree מסדר 9 בעל 4 רמות. האם הכנסת איבר חדש

x

, והוצאתו מיד אח"כ תחזיר אותנו תמיד לצורת העץ המקורית?

ב) נתון B-tree מסדר 9 בעל 4 רמות. האם הוצאת איבר

x

והכנסתו מיד אח"כ תחזיר אותנו תמיד לצורת העץ המקורית?

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

עצי B

סעיף א' (10 נקודות):
נתון עץ 2-3 הבא:
(שורש: 15, 30. בנים משמאל לימין: עץ שמאלי (5, 10) עם בנים (2), (7, 9), (12). עץ אמצעי (21) עם בנים (17), (26). עץ ימני (51, 58) עם בנים (34), (53), (67))

הצג את כל השלבים בביצוע פעולת הוצאת האיבר 30 מהעץ

סעיף ב' (15 נקודות):
הוכח או הפרך:
יהי

T_{0}

עץ פיבונאצ'י בגובה

h_{0} \geq 5

עם

n

ערכים ויהי

T_{1}

עץ 2-3 בגובה

h_{1}

עם

n^{3}

ערכים.
אם

T_{1}

עץ 2-3 הגבוה ביותר עם

n^{3}

ערכים (ז"א, לא קיים עץ 2-3 בגובה

h_{2}

עם

n^{3}

ערכים כך ש:

h_{2} > h_{1}

) אזי

h_{0} < h_{1}

.

שימו לב:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

עצי Bהוכחת נכונותסימון אסימפטוטי

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

54, 34, 78, 96, 102, 12, 45

ב. הוכח: אם

T

עץ חיפוש בינארי שלם בגובה

h > 2

אז ניתן לייצג את ערכי העץ

T

בעץ

T_{1}

מסוג 2-3 בגובה

h_{1}

כאשר

h_{1} < h

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

n

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

n

איברים שגובהו

θ (n)

ב) ברשימה מקושרת באורך

n

כדאי לשמור גם מצביע לאיבר האמצעי, כי בהשקעה של

O (1)

שטח, קיבלנו אפשרות לבצע חיפוש בינארי.
ג) באלגוריתם של Boyer & Moore בהגדרה של

Δ_{2}

, נחפש לכל סיפא מופע מוקדם יותר, אך נדרוש שהאות הקודמת לסיפא תהיה שונה. אם נוריד דרישה זאת, האלגוריתם יכול לשגות.
ד) בטבלת Hash בגודל 2500 הוכנסו 1000 איברים ע"י שימוש ב־Hashing Uniform. הזמן הממוצע לחיפוש מוצלח, כאשר לכל איבר שהוכנס הסתברות שווה להופיע בחיפוש, הוא

\frac{5}{2} ln \frac{5}{3}

.
ה) נתון B-tree מדרגה

m

שמכיל

k

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

n

ואחת באורך 3 הוא

n - 2

.
ז) לכל

n \in N

קיים עץ AVL המכיל

n

קודקודים שסריקת ה־post-order שלו היא סדרה ממוינת.
ח) בכל רשימה מקושרת, קיים איבר אליו ניתן לגשת ב־

O (1)

זמן.
ט) לכל

n \in N

קיים עץ בינארי המכיל בדיוק

n

עלים ו־

2 n

קודקודים פנימיים.
י) זמן חיפוש איבר ברשימת דילוגים (skip-list) הוא

O (n)

במקרה הגרוע.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

ניצול שטח האחסון בקדקודי B-Tree הוא כ־50%. כדי להעלות את אחוז הניצול, מוצע המבנה הבא: נגדיר

B^{'}

-Tree מסדר

m

בדומה ל־B-Tree מסדר

m

רק שעבור כל קדקוד שאינו השורש נדרוש שמספר בניו

k

יקיים

\frac{2}{3} m \leq k \leq m

ולא רק

\frac{1}{2} m \leq k \leq m

. כדי לטפל בפיצולים, לא נאפשר פיצול של קדקוד בודד ל־2 קדקודים, אלא תמיד נפצל קדקוד גולש (עם overflow) יחד עם אחד מאחיו המלאים (אך לא גולשים), דהיינו, 2 קדקודים יהפכו ל־3 קדקודים, כ"א מלא עד כדי 2/3. (לא נטפל במחיקות ואיחודים בשאלה זו.)
א) בדוגמה הבאה (בה מצוייר רק חלק מ־

B^{'}

-Tree), הנח/י

m = 7

:
(בתרשים נתון קודקוד אב

C

עם המפתחות 7, 110, 300, 350. לקודקוד זה בן שמאלי

A

עם המפתחות 10, 15, 20, 50, 70, 82, ובן ימני

B

עם המפתחות 200, 220, 230, 240, 250, 260).
נניח שנוסיף את הערך 60 מה שיגרום גלישה בקדקוד

A

. צייר/י את חלק העץ הרלוונטי אחרי פיצול 2 הקדקודים

A

ו־

B

ל־3 קדקודים, כולל התיקונים הדרושים בקדקוד

C

.
ב) מה עושים אם השכן של קדקוד גולש אינו מלא?
ג) לשורש אין אחים. אם נרצה שבניו של השורש אחרי פיצול גם יקיימו את התנאי ש־

\frac{2}{3} m \leq k

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

עצי B

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

n

קיים עץ AVL של

n

איברים שגובהו

Θ (n)

ב) קיימת ערימת מקסימום (בינארית) בה האיבר הקודם בגודלו לאיבר הקטן ביותר אינו עלה.
ג) בכל עץ AVL החציון של קבוצת האיברים יאוחסן בשורש.
ד) באלגוריתם של Boyer & Moore בהגדרה של

Δ_{2}

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

n

איברים ל-B-tree מסדר 101 שהיה ריק בהתחלה. מספר הפיצולים הכולל בהכנסת כל האיברים חסום ע"י מספר הקדקודים בסיום התהליך.
ו) אי אפשר למצוא חציון של

n

איברים בזמן

O (n)

, כי אחרת היה אפשר למיין ע"י מציאת חציון של הקבוצה, ואח"כ של חצאי הקבוצות, רבעי הקבוצות וכו' בזמן

O (n) + O (\frac{n}{2}) + O (\frac{n}{4}) + \dots = O (n)

, בסתירה לחסם התחתון של מיון.
ז) לכל

n > 1

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

n

קודקודים שסריקת ה-post-order שלו היא סדרה ממוינת.
ח) בכל רשימה מקושרת, ניתן לגשת אל כל איבר ב-

O (1)

זמן.
ט) הזמן הדרוש לפעולת קידום מונה בינארי הוא

O (1)

במקרה הגרוע.
י) לכל

n > 1

קיים גרף עם

n

קדקודים שיש לו

n!

מיונים טופולוגיים שונים.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

כתוב את עץ 2-3 לרצף הנתונים הבא (משמאל לימין):

5, 20, 7, 6, 1

. תאר את התהליך.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

עצי Bמעקב אחר אלגוריתם

נתון B-tree מדרגה 5 (זאת אומרת, מספר בניו של כל קודקוד בין 3 ל־5) שבציור. ברצוננו לבטל את הערך 198.
א. צייר/י את העץ אחרי ביצוע הביטול.
ב. איך תשובתך הייתה משתנה (אם בכלל) אם דרגת ה־B-tree הייתה 4?

          [ 88, 103, 220 ]
        /     |       |       \
[10,32,56] [90,101] [150,198] [237,497]

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

עצי Bמעקב אחר אלגוריתם

שאלות עצי B במבני נתונים עם פתרונות

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