איך לתרגל שאלות הוכחת נכונות במבני נתונים?

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

כמה שאלות הוכחת נכונות יש במבני נתונים?

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

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

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

מבני נתונים - הוכחת נכונות

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

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

רמת קושי:

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

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

(ראו תרשים):

תרשים לשאלה

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

G_{i}

הוא

2 i

.

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

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

O (lo g n)

, כאשר

n

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

שאלה 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הוכחת נכונותרשימות מקושרותתוריםניתוח מופחתמעקב אחר אלגוריתם

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

n

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

k

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

k < \frac{n}{2}

.

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

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

O (n)

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

n

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

n + 1

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

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

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

א. לעץ טרינרי מושלם תמיד מספר עלים אי זוגי.

ב. לעץ טרינרי מושלם עם

n

עלים יש

(n - 1) /2

קודקודים פנימיים.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

הוכחת נכונותרקורסיהעצים

יהי

A

מערך עם

n

איברים שונים. נאמר כי

A

מערך ממוין באופן מעגלי אם קיים

k

כך שאחרי הזזת האיברים

k

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

לדוגמא: המערך

A

הבא הוא מערך ממוין מעגלי כאשר

k = 2

.

א. כתוב/י אלגוריתם המקבל מערך

A

עם

n

איברים שונים ממוין באופן מעגלי ואינדקס

i \in {1, \dots, n}

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

i

(כולל, ז"א ב-

A [1 \dots i]

) אחרת, יחזיר 1. זמן הריצה

O (1)

.
ב. כתוב/י אלגוריתם המקבל מערך

A

עם

n

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

O (lo g n)

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

ענו על שתי השאלות הבאות:

א. נתון מערך של

n

מספרים שלמים

A [1, ..., n]

ונתון ש

∣ A [i + 1] - A [i] ∣ \leq 1

.
נניח ש

n

חזקה של 2. נגדיר

A [1] = a

A [n] = b

ונתון ש

a < b

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

c

כך ש

b \geq c \geq a

, ימצא אינדקס

j

כך ש

A [j] = c

.

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

n

).
רמז: היעזרו בעץ החלטות.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

סעיף א' (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הוכחת נכונותסימון אסימפטוטי

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

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