איך לתרגל שאלות Big-O במבני נתונים?

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

כמה שאלות Big-O יש במבני נתונים?

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

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

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

מבני נתונים - Big-O

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

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

תתי-נושאים של סיבוכיות

רמת קושי:

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

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

(ראו תרשים):

תרשים לשאלה

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

G_{i}

הוא

2 i

.

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

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

O (lo g n)

, כאשר

n

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

O (n lo g n)

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

יהי

A [1, \dots, n]

מערך של מספרים שלמים. לכל תת מערך

A [i, \dots, j]

עבור

1 \leq i \leq j \leq n

נגדיר את סכום תת המערך כ-

S_{i, j} = \sum_{ℓ = i}^{j} A [ℓ]

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

A

קלט: מערך $A [1, \dots, n]$ מערך של מספרים שלמים.
פלט: סכום תת המערך המקסימלי של המערך $A$ . כלומר, $max_{i, j \in [n], i \leq j} S_{i, j}$ .

למשל, עבור הקלט

A = [2, - 4, 1, 9, - 6, 7, - 3]

סכום תת המערך המקסימלי של

A

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

O (n^{3})

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

O (n lo g n)

.
3. (10 נקודות) הוכיחו שזמן הריצה של האלגוריתם שמצאתם הוא

O (n lo g n)

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

סיבוכיות זמןBig-Oרקורסיהנוסחת נסיגההפרד ומשול

א. (15 נקודות) הציעו מבנה נתונים

S

התומך בפעולות הבאות:
PUSH(S,x): הכנסת האיבר

x

ל-

S

.
POP(S): מחיקת האיבר האחרון שנכנס ל-

S

ADD(S,d): הוספת הערך הממשי

d

לכל איברי המבנה

S

SMALL(S): החזרת ערך המינימום במבנה

S

עלות כל אחת מהפעולות:

O (1)

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

O (1)

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

מחסניותסיבוכיות זמןBig-Oמיוןחסם תחתון למיון

כדי לזרז את החיפוש הבינארי במערך ממוין A בגודל n הוצע להוסיף מערך B בגודל

lo g n

שיכיל כל איבר

lo g n

של A, זאת אומרת

B [i] \leftarrow A [i \cdot \frac{n}{l o g n}]

לכל i. לכן שני ערכים עוקבים ב-B מייצגים את תחום הערכים של קטע באורך

\frac{n}{l o g n}

במערך A. החיפוש של מספר X יתנהל עכשיו בשני שלבים:
1. חיפוש ב-B לקביעת הקטע המתאים ב-A
2. חיפוש בינארי רק בקטע המתאים מהערך A למציאת המספר X.

א) האם שיטה זו עדיפה על חיפוש בינארי רגיל רק ב-A, בהנחה שהחיפוש ב-B בשלב 1 נעשה על ידי חיפוש סדרתי (כי גודלו של B הרבה יותר קטן מ-A?)

ב) האם שיטה זו עדיפה על חיפוש בינארי רגיל רק ב-A, בהנחה שהחיפוש ב-B נעשה על ידי חיפוש בינארי?

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

חיפוש בינאריסיבוכיות זמןניתוח אסימפטוטיBig-O

נתונות הפונקציות

f, g : N^{+} \to R^{+}

הוכח או הפרך

סעיף א':
אם

f (n) \in O (g (n))

אזי

f (n) \in o (g (n)) \cup Θ (g (n))

סעיף ב'
אם

f (n) \in Θ (g (n))

אזי

o (f (n)) = o (g (n))

(שימו לב – שיוויון קבוצות)

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

סימון אסימפטוטיBig-O

נתון מערך דו ממדי

A [1.. n, 1.. m]

, שכל שורה וכל עמודה בו ממוינות בסדר לא יורד, כלומר: לכל

1 \leq i < n, 1 \leq j \leq m

מתקיים

A [i, j] \leq A [i + 1, j]

ולכל

1 \leq i \leq n, 1 \leq j < m

מתקיים

A [i, j] \leq A [i, j + 1]

. בהינתן מספר

k

הצע אלגוריתם המוצא תא במערך

A

המכיל את הערך

k

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

(i, j)

או מחזיר שאין תא כזה, במידה והוא לא קיים. זמן ריצת האלגוריתם להיות צריך

O (n + m)

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

חיפושסיבוכיות זמןBig-Oאלגוריתמים

יהי

A

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

n

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

O (n)

המוצא את

k

האיברים ב

A

הקרובים ביותר לחציון של

A

. רמז: מותר להגדיר מערך עזר בגודל

n

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

סיבוכיות זמןBig-Oאלגוריתם בחירה

נתון מערך בגודל

n

של מספרים שלמים. נניח שידוע שמספר המספרים השונים במערך הוא

⌈ n / lo g n ⌉

. תאר/י אלגוריתם למיון המערך שיעבוד בזמן ממוצע

O (n)

כאשר כל הקלטים הם שווי הסתברות. הראה/י שהסיבוכיות אכן כנדרש.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

מיוןטבלאות גיבובסיבוכיות זמןסימון אסימפטוטיBig-O

מה ניתן להגיד על

\sum_{i = 1}^{n} i lo g i

? הסכום הזה הוא:

א(

Θ (n^{2} lo g n)

ב(

Θ (n^{2})

ג(

Θ (n lo g^{2} n)

ד(

Θ (n lo g n lo g lo g n)

ה( אף אחת מהתשובות א) עד ד) אינה נכונה.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

סיבוכיותסימון אסימפטוטיBig-O

שאלות Big-O במבני נתונים עם פתרונות

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