איך לתרגל שאלות תור עדיפויות במבני נתונים?

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

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

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

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

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

מבני נתונים - תור עדיפויות

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

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

תתי-נושאים של ערימות

רמת קושי:

(25) הציגו אלגוריתם המקבל קבוע

k

וערימת מינימום בגודל

n

, המיוצגת במערך, ומחזיר רשימה ממוינת של

k

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

O (min (k^{2}, k lo g n))

וסיבוכיות זיכרון נוסף של

O (1)

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

ברצוננו להדפיס את

m

האיברים הגדולים ביותר מתוך קבוצה של

n

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

0 < m < n

וכן

O (lo g m) \neq = O (lo g n)

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

O (m lo g m)

. רמז: השתמש/י בערימת עזר.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

ערימותערימה בינאריתתור עדיפויותסיבוכיות זמן

ברצוננו לנהל אוסף של

n

מספרים שונים ע"י בניית מבני נתונים בזמן

O (n)

כך שנוכל אח"כ לבצע כל אחת מהמשימות הבאות בזמן ממוצע

O (lo g n)

: הוצאת האיבר המקסימאלי, הכנסת הערך

K

, הוצאת הערך

K

.
א) מדוע השימוש בערימה אינו עונה במלואו על הדרישות?
ב) הצע/י מבני נתונים שכן יכולים לתמוך בכל הנדרש.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

יהי

D

מבנה נתונים כלשהו שמנהל קבוצה של

n

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

Ω (lo g n)

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

נתון גרף

G = (V, E)

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

D [v]

המוגדר לכל

v \in V

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

S

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

v_{0} \in V

בודד,

S = {v_{0}}

, ובכל איטרציה מתווסף עוד קדקוד עד ש-

S = V

. הקדקוד

y

שמתווסף ל-

S

בשלב מסוים הוא זה בעל ערך מינימלי ב-

D

באותו רגע. אחרי הוספת

y

ל-

S

מעודכנים כל הערכים

D

של השכנים של

y

שעדיין לא ב-

S

. פורמאלית:

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

V

ו-

E

? נמקו. רמז: הבחירה של מבני הנתונים לניהול המערך

D

תעשה בתלות ביחס בין

E

ל-

V

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

O (1)

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

הצע/י מבנה נתונים

S

התומך בביצוע הפעולות הבאות בסיבוכיות הנדרשת: נתונה רשימת נתוני קלט

L

ובה

n

איברים.
a.

B u i l d (S, L)

– בניית המבנה

S

מרשימת נתוני הקלט

L

בזמן

O (n)

M a x (S)

– החזרת ערך מקסימלי בזמן

O (1)

M in (S)

– החזרת ערך מינימלי בזמן

O (1)

d e l e t e - ma x (S)

– מחיקת איבר מקסימלי בזמן

O (lo g n)

d e l e t e - min (S)

– מחיקת איבר מינימלי בזמן

O (lo g n)

הסבר/י בקצרה כיצד תתבצע כל פעולה.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

ערימותערימה בינאריתתור עדיפויותסיבוכיות זמן

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

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