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

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

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

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

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

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

מבני נתונים - סיבוכיות

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

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

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

רמת קושי:

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

n

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

k

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

k < \frac{n}{2}

.

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

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

O (n)

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

נגדיר מבנה נתונים

S

התומך בפעולות הבאות:

Insert(x): מכניס את האיבר $x$ לתוך מבנה הנתונים $S$ . ניתן להניח ש- $x$ הוא מספר ממשי.
DeleteLargestHalf(): מוחק את $∣ S ∣/2$ האיברים הגדולים ביותר הנמצאים כרגע במבנה $S$ .

הציעו מימוש למבנה נתונים

S

כך שהעלות לשיעורין של כל פעולה על המבנה תהיה מינימלית. יש לפרט את (1) תיאור המבנה, (2) תיאור מימוש כל אחת מהפעולות, (3) ניתוח עלות כל פעולה במקרה הגרוע ביותר, (4) ניתוח עלות לשיעורין של כל פעולה על המבנה.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

שאלה 4

נתון מערך

A

בגודל

n

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

S

בגודל

n

כך שבכל אינדקס

i

במערך

S

יהיה את כמות האיברים שנמצאים משמאל ל־

i

וקטנים או שווים מ־

A [i]

במערך המקורי. לדוגמה,

A = [2, 7, 4, 5, 15, 9, 12]

S = [0, 1, 1, 2, 4, 4, 5]

1. (13 נקודות) הראו שכל אלגוריתם לביצוע המשימה ייקח לפחות

Ω (n lo g n)

פעולות. רמז: הראו תחילה שאם ניתן לבצע את המשימה שבשאלה בזמן

T

כלשהו, אזי בעזרת עבודה מקדימה בזמן

O (T)

, ניתן לקבוע לכל איבר את ערך המיקום שלו בזמן

O (1)

.

2. (12 נקודות) תארו אלגוריתם לביצוע המשימה שרץ בזמן אופטימלי לבעיה.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

[1] ראינו כיצד להכפיל שני מספרים

X, Y

, כל אחד בעל

n

סיביות בשיטת הפרד ומשול בזמן

O (n^{2})

, כאשר כל מספר חולק לשני חלקים באורך

n /2

סיביות כל אחד. כאשר צמצמנו את מספר הקריאות הרקורסיביות מ 4 ל 3, הסיבוכיות ירדה ל

O (n^{1.58})

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

סעיף 5 נקודות.

א) הגדירו את

X

Y

כל אחד כפונקציה של שלושת חלקיהם

X_{1}, X_{2}, X_{3}

Y_{1}, Y_{2}, Y_{3}

ב) הראו איך ניתן לחשב את

X * Y

ע"י 9 קריאות רקורסיביות (הפרד) ועוד עבודת איסוף התוצאות שעלותה לינארית ב

n

(ומשול)
ג) מה הסיבוכיות של שיטה זו?
ד) בדומה למה שראינו במקרה של חלוקה ל2 חלקים, הראו איך, ע"י חישוב שלושת הערכים הבאים:

G = (X_{1} + X_{3}) (Y_{1} + Y_{3})

F = (X_{2} + X_{3}) (Y_{2} + Y_{3})

E = (X_{1} + X_{2}) (Y_{1} + Y_{2})

ניתן להוריד את מספר הקריאות הרקורסיביות מ9 ל 6.
ה) מה הנוסחה המתקבלת עבור הסיבוכיות?

(3 נקודות) בונוס: האם כדאי לחלק ל3?

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

יהי

T

עץ בינארי. נאמר כי

T

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

עצים בינארייםרקורסיהסיבוכיותסיבוכיות זמן

נתונים

m

מערכים לא ממוינים

A_{1}, A_{2}, \dots, A_{m}

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

[1, k]

. יהי

n

המספר הכולל של איברים בכל המערכים ביחד, כלומר

n = ∣ A_{1} ∣ + ∣ A_{2} ∣ + \dots + ∣ A_{m} ∣

. כתוב אלגוריתם הממיין את כל

m

המערכים

A_{1}, A_{2}, \dots, A_{m}

בזמן כולל של

O (k + n)

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

מיוןמיון ספירהסיבוכיותסיבוכיות זמן

מיון מהיר (quicksort או QS בקיצור) פועל ע"י (1) בחירת איבר חלוקה

K

(שמטעמי עצלות נבחר לעיתים קרובות כ־

K = A [1]

), (2) חלוקת

n

האיברים במערך

A

ל־2 קבוצות

S_{1}

ו־

S_{2}

שמכילות, בהתאמה, את האיברים הקטנים מ־

K

ואת האיברים הגדולים מ־

K

וסידור המערך מחדש ל־

S_{1}, K, S_{2}

, ז"א

K

במקומו המיועד, משמאלו איברי

S_{1}

ומימינו איברי

S_{2}

, ו־(3) המשך רקורסיבי על

S_{1}

ועל

S_{2}

.

הוכח/י שמיון מהיר אופטימלי בממוצע, כאשר בכל השאלה הממוצע מתייחס לכך שהמיקום בסידור הממויין של איבר החלוקה יכול להיות בכל אחד מ־

n

המקומות, בהסתברות שווה.

הדרכה: נגדיר

T (n)

- מספר השוואות ממוצע כדי למיין

n

איברים ע"י QS.
א)

T (n) = a (n) + b (n) \sum_{i = 1}^{n} c (i)

כאשר

a (n) = n + 1

הוא מספר ההשוואות לביצוע החלוקה,

b (n) = \frac{1}{n}

היא ההסתברות שאיבר החלוקה יפול למקום ה־

i

, ו־

c (i)

היא עלות ההמשך הרקורסיבי במקרה שאיבר החלוקה יפול למקום ה־

i

, ועליכם למצוא את

c (i)

במונחים של

T

. רשמו את הנוסחה הרקורסיבית שמתקבלת עבור

T (n)

.
ב) הכפל/י את 2 צידי המשוואה ב־

n

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

n - 1

במקום

n

.
ד) צרו משוואה חדשה ע"י חיסור אגף אגף של המשוואות הקודמות, וסידור מחדש.
ה) חלקו את שני האגפים ב־

(n + 1) n

.
ו) הגדירו

H (n) = \frac{T ( n )}{n + 1}

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

H (n)

.
ז) פתרו עבור

H (n)

והסיקו ל־

T (n)

. מה המסקנה בענין האופטימליות של QS?

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

כתוב מחרוזת באורך

n

על אלפבית

Σ = {A, B, C}

כאשר ה-trie של הסופיקסים שלה הוא בגודל

Θ (n^{2})

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

סיבוכיותסיבוכיות מקוםהוכחת נכונותטרי

(20 נקודות) נתח את העלות לשיעורין לפעולת increment על מונה טרינארי (בבסיס 3) שמאותחל באפס.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

ניתוח מופחתסיבוכיות

האלגוריתם

se l ec t

שנלמד בכיתה מקבל כקלט מערך

A

לא ממוין בגודל

n

, ומספר

i

בטווח 1 עד

n

, ומחזיר את האיבר ה-

i

בגודלו במערך. באלגוריתם חילקנו את המערך ל-

n /5

קבוצות בנות 5 איברים בכל קבוצה, ואיבר החלוקה

K

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

n /5

הקבוצות. היה הרי פשוט יותר לבחור את

K

כחציון של תת-קבוצה אחרת של

A

, למשל

K \leftarrow se l ec t (A [1 : \frac{n}{5}], \frac{n}{10})

וגם זה היה גורר ששתי הקבוצות

S_{1}, S_{2}

המתקבלות מהחלוקה יחסית ל-

K

, ז"א

S_{1} \leftarrow {x \in A ∣ x < K}

ו-

S_{2} \leftarrow {x \in A ∣ x > K}

מקיימות ש

max (∣ S_{1} ∣, ∣ S_{2} ∣) \leq \frac{3}{4} n

. אז מה רע בבחירה הזאת, שנראית פשוטה יותר ליישום?

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

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