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

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

כמה שאלות מיון מיזוג יש במבני נתונים?

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

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

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

מבני נתונים - מיון מיזוג

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

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

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

רמת קושי:

א. (13 נקודות) מערך

A [1 \dots 2 n + 1]

הוא מפותל אם

A [1] \leq A [2], A [2] \geq A [3], A [3] \leq A [4], \dots, A [2 n - 1] \leq A [2 n], A [2 n] \geq A [2 n + 1]

בהינתן מערך לא ממוין

B [1 \dots 2 n + 1]

של מספרים, הציגו אלגוריתם יעיל ביותר שמוציא פרמוטציה

A [1 \dots 2 n + 1]

של

B

כך ש-

A

הוא מפותל. מהי סיבוכיות האלגוריתם?

ב. (12 נקודות) מערך של מספרים הוא

k

-זוגי-מעורבב אם קיימים בדיוק

k

מספרים זוגיים ב-

A

, והמספרים האי-זוגיים ב-

A

הם ממוינים. בהינתן מערך

k

-זוגי מעורבב

A

המכיל

n

מספרים שונים עבור

k = n / lo g n

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

O (n)

בכדי למיין את

A

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

נתונות

n

סדרות ממוינות

A_{1}, \dots, A_{n}

של

l_{1}, \dots, l_{n}

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

a + b

השוואות כדי למזג סדרה באורך

a

עם סדרה באורך

b

. אם

n = 2

, יש רק אפשרות אחת למיזוג. אם

n = 3

, אפשר למזג

(A_{1} A_{2}) A_{3}

או

A_{1} (A_{2} A_{3})

ומספר ההשוואות יהיה

(l_{1} + l_{2}) + (l_{1} + l_{2} + l_{3})

או

(l_{2} + l_{3}) + (l_{1} + l_{2} + l_{3})

. אם

n = 4

, יש 5 אפשרויות.

מה הקשר בין האפשרויות למיזוג $n$ סדרות ממוינות לבין עצים בינאריים?
כמה אפשרויות יש למיזוג 10 סדרות?

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

עצים בינארייםמיון מיזוג

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

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

★★★★★

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

שאלות מיון מיזוג במבני נתונים עם פתרונות

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