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

I. (2 נק') נתון עץ בינארי עם הערכים הבאים: ``` 1 / \ 2 0 / / \ 0 2 3 \ 1 ``` מה תוצאת סריקת העץ הנתון ב-BFS? כתבו משמאל לימין. II. (2 נק') הניחו כי המספר שהתקבל לעיל הוא בייצוג בבסיס 4. מה הייצוג הבינארי שלו? III. (1 נק') מה הייצוג של המספר שהתקבל לעיל בבסיס 16?

רמז: BFS סורק רמה-רמה, משמאל לימין. כל ספרה בבסיס 4 שקולה ל-2 ביטים בבסיס בינארי. כל 4 ביטים בבסיס בינארי = ספרה אחת בבסיס 16.

פתרון: **I. BFS (רמה-רמה, שמאל לימין):** רמה 0: **1** רמה 1: **2, 0** רמה 2: **0, 2, 3** רמה 3: **1** תוצאה: **1 2 0 0 2 3 1** **II. $1200231_4$ בבסיס בינארי:** כל ספרה בבסיס 4 ← 2 ביטים: $1 = 01$, $2 = 10$, $0 = 00$, $0 = 00$, $2 = 10$, $3 = 11$, $1 = 01$ $$1200231_4 = 01\;10\;00\;00\;10\;11\;01_2$$ כערך עשרוני: $1 \times 4^6 + 2 \times 4^5 + 0 + 0 + 2 \times 4^2 + 3 \times 4 + 1 = 4096 + 2048 + 32 + 12 + 1 = 6189$ **III. בבסיס 16:** קיבוץ בינארי ל-4 ביטים (מימין): $01\;1000\;0010\;1101$ עם ריפוד: $0001\;1000\;0010\;1101$ $0001 = 1$, $1000 = 8$, $0010 = 2$, $1101 = D$ $$\boxed{182D_{16}}$$ $\blacksquare$