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

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

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

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

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

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

מבני נתונים ומבוא לאלגוריתמים - מיון הכנסה

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

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

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

רמת קושי:

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

if p < r

בשורה הראשונה הוא כתב

if p < r - k

(שגרת מיון מהיר נמצאת בעמ' 122).

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

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

k

שונים.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמבחן סמסטר א · 2024 · סמסטר א

★★★★★

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

נתון מערך

A [1.. n]

המקיים את התנאי: אם

A [i] > A [j]

i < j

, אזי

j = i + 1

(עבור

1 \leq i, j \leq n

).

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

A

בזמן טוב יותר: מיון-הכנסה או מיון-מיזוג? הוכיחו את טענתכם.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמבחן סמסטר ב · 2023 · סמסטר ב

★★★★★

מיוןסיבוכיותמיון הכנסה

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

מהי סיבוכיות הזמן של מיון הכנסה? יש לתת חסם הדוק.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמבחן סמסטר א · 2023 · סמסטר א

★★★★★

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

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

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמבחן סמסטר א · 2023 · סמסטר א

★★★★★

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

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

n

זוגי):

2, 1, 4, 3, \dots, n - 2, n - 3, n, n - 1

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמבחן סמסטר ב · 2019 · סמסטר ב

★★★★★

מיוןסיבוכיותמיון הכנסה

A

הוא מערך ובו

n

תאים (

n

זוגי), שבהם הערכים הטבעיים מ-

1

עד

n

. תת-המערך השמאלי של

A

, מתא מס'

1

עד תא מס'

n /2

, מכיל את האיברים האי-זוגיים שב-

A

; תת-המערך הימני של

A

, מתא מס'

n /2 + 1

עד תא מס'

n

, מכיל את האיברים הזוגיים שב-

A

. נתון כי כל אחד משני תת-המערכים ממוין. (לדוגמה, עבור

n = 10

המערך נראה כך:

[1, 3, 5, 7, 9, 2, 4, 6, 8, 10]

)

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

A

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמבחן סמסטר ב · 2018 · סמסטר ב

★★★★★

מיוןסיבוכיותמיון הכנסה

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

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