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

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

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

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

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

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

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

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

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

תתי-נושאים של מיון

רמת קושי:

שאלה 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

[2] יהיו

A, B

אלגוריתמי מיון מבוססי השוואות.

הוכיחו או הפריכו כל אחת מהטענות הבאות:

א) (10 נקודות) יתכן שזמן הריצה של האלגוריתם A במקרה הגרוע הוא

n \cdot lo g n \cdot lo g (lo g n)

.
ב) (15 נקודות) במרבית המקרים (כלומר על יותר ממחצית הקלטים בגודל

n

) האלגוריתם B ירוץ בזמן לינארי.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

מיוןחסם תחתון למיוןסיבוכיות זמןסימון אסימפטוטי

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

א( (16) נתונה קבוצה של

n

מספרים. הראו, בשתי דרכים שונות, איך לבנות בזמן

O (n lo g n)

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

ב( (9) הראו שאי אפשר לבנות את עץ החיפוש בינארי בסעיף הקודם בזמן

o (n lo g n)

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

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

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 · סמסטר ב

★★★★★

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

ענה/י נכון/לא נכון לכל אחד מהסעיפים הבאים. מותר אך לא חובה לכתוב הסבר עד אורך של שורה לכל סעיף.
א) לכל

n

קיים עץ חיפוש בינארי של

n

איברים שגובהו

θ (n)

ב) ברשימה מקושרת באורך

n

כדאי לשמור גם מצביע לאיבר האמצעי, כי בהשקעה של

O (1)

שטח, קיבלנו אפשרות לבצע חיפוש בינארי.
ג) באלגוריתם של Boyer & Moore בהגדרה של

Δ_{2}

, נחפש לכל סיפא מופע מוקדם יותר, אך נדרוש שהאות הקודמת לסיפא תהיה שונה. אם נוריד דרישה זאת, האלגוריתם יכול לשגות.
ד) בטבלת Hash בגודל 2500 הוכנסו 1000 איברים ע"י שימוש ב־Hashing Uniform. הזמן הממוצע לחיפוש מוצלח, כאשר לכל איבר שהוכנס הסתברות שווה להופיע בחיפוש, הוא

\frac{5}{2} ln \frac{5}{3}

.
ה) נתון B-tree מדרגה

m

שמכיל

k

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

n

ואחת באורך 3 הוא

n - 2

.
ז) לכל

n \in N

קיים עץ AVL המכיל

n

קודקודים שסריקת ה־post-order שלו היא סדרה ממוינת.
ח) בכל רשימה מקושרת, קיים איבר אליו ניתן לגשת ב־

O (1)

זמן.
ט) לכל

n \in N

קיים עץ בינארי המכיל בדיוק

n

עלים ו־

2 n

קודקודים פנימיים.
י) זמן חיפוש איבר ברשימת דילוגים (skip-list) הוא

O (n)

במקרה הגרוע.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

יהי

D

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

n

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

Ω (lo g n)

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

ענה/י נכון/לא נכון לכל אחד מהסעיפים הבאים. מוותר אך לא חובה לכתוב הסבר עד אורך של שורה לכל סעיף.
א) לכל

n

קיים עץ AVL של

n

איברים שגובהו

Θ (n)

ב) קיימת ערימת מקסימום (בינארית) בה האיבר הקודם בגודלו לאיבר הקטן ביותר אינו עלה.
ג) בכל עץ AVL החציון של קבוצת האיברים יאוחסן בשורש.
ד) באלגוריתם של Boyer & Moore בהגדרה של

Δ_{2}

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

n

איברים ל-B-tree מסדר 101 שהיה ריק בהתחלה. מספר הפיצולים הכולל בהכנסת כל האיברים חסום ע"י מספר הקדקודים בסיום התהליך.
ו) אי אפשר למצוא חציון של

n

איברים בזמן

O (n)

, כי אחרת היה אפשר למיין ע"י מציאת חציון של הקבוצה, ואח"כ של חצאי הקבוצות, רבעי הקבוצות וכו' בזמן

O (n) + O (\frac{n}{2}) + O (\frac{n}{4}) + \dots = O (n)

, בסתירה לחסם התחתון של מיון.
ז) לכל

n > 1

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

n

קודקודים שסריקת ה-post-order שלו היא סדרה ממוינת.
ח) בכל רשימה מקושרת, ניתן לגשת אל כל איבר ב-

O (1)

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

O (1)

במקרה הגרוע.
י) לכל

n > 1

קיים גרף עם

n

קדקודים שיש לו

n!

מיונים טופולוגיים שונים.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

(20 נקודות) לכל אחת מהטענות הבאות קבע אם היא נכונה או שקרית. ערכי הצמתים בכל העצים להלן הם ברים.

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

Ω (n lo g lo g n)

פעולות להשוואה למיון מערך של

n

איברים.

ב. קיים עץ חיפוש בינארי שה-pre-order scan שלו נותן סדרה עולה הולכת וגדלה.

ג. קיים עץ חיפוש בינארי עם יותר מצומת אחד שה-pre-order וה-post-order scans שלו שווים.

ד. אפשר ליישם טבלת גיבוב עם linear-probing בלי להשתמש בדגל "deleted".

ה. לכל מספר טבעי

n

קיים מערך של מספרים שעליו insertion-sort מסדר בזמן

O (n)

.

ו. אלגוריתם Quicksort (כפי שנלמד בהרצאה) הוא אלגוריתם מיון לא יציב.

ז. כאשר גודל קבוצת המפתחות אינו ידוע שיטת chaining טובה יותר מהשיטת open addressing.

ח. בהינתן in-order scan של עץ Cartesian ניתן להחזיר את העץ.

ט. בהינתן pre-order וגם post-order scans של עץ בינארי ניתן להחזיר את העץ.

י. קיים instance של Binomial heap כאשר extract-min מסדר בזמן

O (1)

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

חסם תחתון למיוןסימון אסימפטוטימיון

בבעיית הוקטור הפרבולי נתון מערך

A

בגודל

n

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

לכל $1 < i \leq ⌈ \frac{n}{2} ⌉$ , $A [i] \leq A [i - 1]$ .
לכל $n \geq i \geq ⌈ \frac{n}{2} ⌉ + 1$ , $A [i] \leq A [i + 1]$ .

מערך המקיים תנאים אלה נקרא וקטור פרבולי. לדוגמא המערך הבא הינו וקטור פרבולי:

א. בהינתן וקטור פרבולי, תארו אלגוריתם הממיין את הוקטור בזמן

O (n)

.
ב. תנו חסם תחתון (במונחים של

Ω

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

מיוןסיבוכיות זמןסיבוכיות מקוםחסם תחתון למיוןמיון מיזוג

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

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