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

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

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

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

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

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

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

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

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

רמת קושי:

שאלה 2

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

1. דחיפה

Push (x)

: מכניס את האיבר

x

למחסנית.
2. הוצאה

Pop ()

: הוצא את האיבר העליון מהמחסנית.
3. ביטול

Undo (k)

: החזר את המחסנית למצב שבו היתה לפני

k

פעולות דחיפה/הוצאה אחרונות (כלומר, מבצעים ביטול של

k

הפעולות Pop/Push האחרונות. הניחו שבמידה והפעולה נקראת עם

k

אז אכן יש

k

כאלו פעולות שעוד לא עשו להן Undo).

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

א. (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מיוןחסם תחתון למיון

א. הצע מבנה נתונים למימוש "מחסנית-מינימום" התומך בפעולות המחסנית הרגילות של הכנסת איבר לראש המחסנית והוצאת האיבר שבראש המחסנית (האיבר אינו נשאר במבנה לאחר פעולת ההוצאה).
בנוסף, המבנה תומך בפעולה: החזרת איבר המינימום (ללא הוצאה מהמבנה).

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

O (1)

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

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

n

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

n /2

איברים, מקצים מערך חדש בגודל

n /2

, מעתיקים את האיברים למערך החדש, ומשחררים את המערך הישן.

לסעיפים הבאים, השתמש/י בפונקצית הפוטנציאל הבאה:

ϕ (D_{i}) = size - num

, כאשר

num

הוא מספר האיברים כרגע במערך, ו-

size

הוא גודלו הנוכחי של המערך.

א. הוכח/י: לכל

i

ϕ (D_{i}) \geq ϕ (D_{0})

. הנח/י לשם כך כי במצב ההתחלתי

D_{0}

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

n

, ויש בו בדיוק

n

איברים (המערך מלא). הסק/י: לכל

m

מתקיים:

i = 1 \sum m c_{i} \geq i = 1 \sum m \overset{c}{^}_{i}

ב. הנח/י סידרה של

m

פעולות הוצאה. מהי העלות לשיעורין של כל פעולה? הוכח/י בעזרת שיטת הפוטנציאל.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

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