אילו שאלות מבחנים יש מאוניברסיטת בר-אילן במבני נתונים?

באתר prepd יש שאלות ממבחנים של אוניברסיטת בר-אילן (בר-אילן) במבני נתונים. ניתן לסנן לפי נושא ורמת קושי ולתרגל ממוקד לפני הבחינה.

איפה למצוא שאלות במבני נתונים אוניברסיטת בר-אילן?

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

כיצד ניתן להתכונן למבחן במבני נתונים באוניברסיטת בר-אילן?

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

האם יש פתרונות לשאלות מבחנים של אוניברסיטת בר-אילן במבני נתונים?

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

מבני נתונים אוניברסיטת בר-אילן

Q: האם יש מבחנים במבני נתונים באוניברסיטת בר-אילן משנים אחרונות?

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

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

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

רמת קושי:

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

G_{0}, G_{1}, G_{2}, \dots

(ראו תרשים):

תרשים לשאלה

סעיף א' (10 נקודות)
הוכיחו באינדוקציה על המבנה כי גובה העץ

G_{i}

הוא

2 i

.

סעיף ב' (15 נקודות)
הוכיחו כי משפחת העצים הרקורסיביים מסדר שני היא משפחה מאוזנת.

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

O (lo g n)

, כאשר

n

הוא מספר הצמתים בעץ.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

רקורסיהנוסחת נסיגההוכחת נכונותסימון אסימפטוטיBig-Oעצים בינאריים

נתון מערך לא ממוין

A

בגודל

n

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

x, x + 1, x + 2, \dots, x + k

כך שכל האיברים ברצף מופיעים במערך

A

, לאו דווקא ברצף אינדקסים.
מטרת השאלה היא למצוא את אורך הרצף העוקב הארוך ביותר המופיע במערך.
לדוגמה, עבור המערך:

A = (100, 4, 200, 1, 3, 2)

הרצף העוקב הארוך ביותר הוא

1, 2, 3, 4

.

סעיף א' (5 נקודות)
הציעו אלגוריתם המקבל מערך

A

לא ממוין מאורך

n

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

O (n lo g n)

.

סעיף ב' (5 נקודות)
הציעו מבנה נתונים שיאפשר ליישם את הפונקציות הבאות בתוחלת זמן

O (1)

.
פונקציית עוקב: הפונקציה מקבלת אינדקס

i

ומחזירה אמת אם האיבר

A [i] + 1

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

i

ומחזירה אמת אם האיבר

A [i] - 1

מופיע במערך, ושקר אחרת.

סעיף ג' (15 נקודות)
הציעו אלגוריתם המקבל מערך

A

לא ממוין מאורך

n

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

O (n)

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

סיבוכיות זמןסימון אסימפטוטימיוןטבלאות גיבובפונקציית גיבוב

שאלה 2:
נתונה מחרוזת

S

מעל האלפבית

Σ = {a_{1}, a_{2}, \dots, a_{n}}

נסמן ב-

f_{i}

את שכיחות הופעתה של האות

a_{i}

במחרוזת

S

.

סעיף א': (5 נקודות)
נניח כי

n \geq 2

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

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

n = 7

.
להלן נתון מבנה של עץ בינארי מלא:
[איור של עץ הושמט]

הציעו רשימת שכיחויות

f_{1}, \dots, f_{7}

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

סעיף ג': (15 נקודות)
הוכיחו כי לכל עץ בינארי מלא עם

n

עלים קיימת רשימת שכיחויות שעבורה

T

הוא עץ קוד תחיליות אופטימלי.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

A

באורך

n

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

k < n

.
פלט: האיבר המקסימלי לכל חלון, כאשר חלון הוא רצף של

k

איברים עוקבים במערך. כלומר, עבור כל אינדקס

i

מ-1 ועד

n - k + 1

עליך להחזיר את המקסימום מבין האיברים

A [i], A [i + 1], \dots, A [i + k - 1]

.

סעיף א' (10 נקודות):
הציעו אלגוריתם לפתרון בעיה בסיבוכיות זמן

O (n lo g k)

.

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

i

ו-

j

אינדקסים במערך

A

כך ש-

i < j

ומתקיים

A [i] \leq A [j]

.
אזי, לכל אינדקס

m

(המייצג את תחילת תת-המערך

A [m \dots m + k - 1]

) שעבורו

m \leq i

וגם

j \leq m + k - 1

מתקיים:

(i = m max m + k - 1 A [l]) \geq A [j] \geq A [i]

סעיף ג': (10 נקודות)
הציעו אלגוריתם לפתרון בעיה בסיבוכיות זמן

O (n)

.
רמז: חישבו על רשימה מקושרת דו כיוונית.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

שאלה 1:
ברצוננו לערוך מסע לאורך של מסלול ישר מנקודת-התחלה

s = 0

לנקודת-סיום

f > 0

.

נתון מערך

p

של מיקומי-מלונות

0 < p_{1} < \dots < p_{n} = f

, כך שמלון

i

ממוקם בדיוק

p_{i}

קילומטרים מנקודת תחילת המסלול.

להלן סרטוט המסלול עבור

n = 6

:
[איור הושמט]

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

t

ימים (נתון

t < n

).
המאמץ שנדרש ביום-הליכה הינה

d^{2}

, כאשר

d

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

הערה: הבעיה ניתנת לפתרון בעזרת תכנות דינמי.

סעיף א' (10 נקודות)
בהינתן נקודת-התחלה

s = 0

ונקודת-סיום

f > 0

ומערך

p

של מיקומי-מלונות וכן

t

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

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

t

וביחס ל-

n

.

סעיף ג' (5 נקודות)
מהו (א) זמן הריצה ומהו (ב) גודל המקום (זיכרון) של האלגוריתם שהצעתם בסעיף ב?

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

שאלה 3:
נתון מערך בגודל

n

.
רוצים למצוא את האיבר שהוא ה-

k

-י הקטן ביותר כאשר

k < \frac{n}{2}

.

מותר להשתמש ב SELECT רק על תתי מערכים בגודל לכל היותר \frac{n}{2}.

הראו אלגוריתם הרץ בזמן

O (n)

לפתרון הבעיה המוצגת. נמקו תשובתכם.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

סיבוכיותסיבוכיות זמןרקורסיהנוסחת נסיגההוכחת נכונותחיפוש

נתון מערך

A

באורך

N

(אין חשיבות לתוכן

A

). נאמר כי

P = {[1, i_{1}], [i_{1} + 1, i_{2}], \dots, [i_{k - 1} + 1, N]}

היא חלוקה

k

-רציפה של מיקומי המערך

A

, כלומר היא מחלקת את המערך ל-

k

תתי מערכים (רציפים).

דוגמה: עבור מערך

A

באורך

14

ו-

k = 4

, חלוקה 4-רציפה אפשרית של המערך

A

היא:

P = {[1, 3], [4, 8], [9, 10], [11, 14]}

נניח כי לכל זוג

1 \leq i \leq j \leq n

נתונה פונקציית עלות כללית

C (i, j)

המחזירה את העלות של תת המערך מהאינדקס

i

עד האינדקס

j

(כולל), קרי

[i, j]

.

נגדיר את מחיר החלוקה

P

cost (P) = C (1, i_{1}) + C (i_{k - 1}, N) + ℓ = 1 \sum k - 1 C (i_{ℓ} + 1, i_{ℓ + 1})

כלומר, מחיר החלוקה הוא סכום העלויות של חלקי החלוקה ה-

k

רציפה.

להלן הגדרת בעיית החלוקה ה-

k

-רציפה מינימלית:
קלט: מערך

A

באורך

N

, מספר טבעי

k

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

C (i, j)

, המחזירה את עלות החלק

[i, j]

.
פלט: חלוקה

k

-רציפה

P = {[1, i_{1}], [i_{1} + 1, i_{2}], \dots, [i_{k - 1} + 1, N]}

של המערך

A

(ל-

k

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

cost (P)

הוא מינימלי מבין כל החלוקות ה-

k

-רציפות האפשריות.

הערה: הבעיה ניתנת לפתרון בעזרת תכנות דינמי.

סעיף א' (10 נקודות)
בהינתן מערך

A

בגודל

N

, מספר טבעי

k

ופונקציית עלות כללית

C (i, j)

,
כתבו נוסחה רקורסיבית לחישוב העלות של מחיר החלוקה

k

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

סעיף ב' (10 נקודות)
הראו אלגוריתם תכנות דינמי לפתירת בעיית החלוקה

k

-רציפה מינימלית.

סעיף ג' (5 נקודות)
מהו (א) זמן הריצה ומהו (ב) גודל המקום (זיכרון) של האלגוריתם שהצעתם בסעיף ב?

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

נתון זרם (stream) אינסופי של מספרים טבעיים מהצורה:

x_{1}, x_{2}, x_{3}, \dots

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

m

.

נדרש לתכנן ולתחזק מבנה נתונים במקום

O (m)

התומך בפעולות הבאות:
א - MostFrequent()
מחזירה מספר טבעי אשר מופיע מספר הפעמים הגבוה ביותר מבין

m

האיברים האחרונים שנקלטו בזרם או לכל האיברים שנקלטו עד כה, אם טרם נקלטו

m

איברים.
זמן ריצה

O (1)

.

ב - Frequency(x)
מקבלת מספר טבעי

x

, ומחזירה את מספר הפעמים ש-

x

מופיע מבין

m

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

O (lo g m)

.

סעיף א': (15 נקודות)
הציעו מבנה נתונים המשתמש במקום

O (m)

ותומך בפעולות מעלה (Frequency ו- MostFrequent) בזמנים המבוקשים.
המלצה: קראו את סעיף ב' לפני פתרון סעיף א'.

סעיף ב': (10 נקודות)
לכל קריאת תו חדש, ה-"

m

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

(בונוס – 3 נקודות) סמנו את התשובה הנכונה: מציאת ערך מינימום בערימת מקסימום לוקח זמן

O (n lo g n)

. נכון / לא נכון.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

ערימותערימה בינאריתסיבוכיות זמןBig-O

(בונוס - 3 נקודות) סמנו את התשובה הנכונה: בעץ בינארי בעל

n

קודקודים פנימיים יש בהכרח

n + 1

עלים.
נכון / לא נכון

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

עצים בינארייםהוכחת נכונות

שאלות מבני נתונים באוניברסיטת בר-אילן עם פתרונות

מאגר מבחנים במבני נתונים מאוניברסיטת בר-אילן (בר-אילן) - 135 שאלות ממוינות לפי נושא ורמת קושי, עם פתרונות מלאים לבדיקה עצמית. השאלות מכסות מועדים לאורך השנים, כולל מבחנים מ-2023, 2024, 2025 ו-2026. נושאים מרכזיים: סיבוכיות, עצים בינאריים, ערימות, טבלאות גיבוב, גרפים. ניתן לסנן שאלות חוזרות, להתאמן על נושא ספציפי או להריץ סימולציית מבחן לפני הבחינה.