כדי לגשת למבחני סימולציה ועוד המון שאלות נוספות, פתחו גישה מלאה
תתי-נושאים של אלגוריתמים
רמת קושי:
להלן נתונה השגרה הרקורסיבית הבאה, שהקלט שלה הוא תמורה של (1,2,...,n) (האינדקסים של A הם בין 1 לבין n, וכן מתקיים שלכל 1≤i≤n קיים 1≤j≤n יחיד כך ש A[j]=i), וכן שני אינדקסים 1≤p,r≤n. הקריאה הראשית לשגרת DoesItSort על מערך A הינה: DoesItSort(A, 1, n).
השגרה ReverseSort(A, i, j) ממיינת הפוך את תת המערך A[i...j], למשל ReverseSort(A, 2, 5) עבור A=[3,4,6,1,2,5] ישנה את A ל-A=[3,6,4,2,1,5].
Partition היא שגרת החלוקה המופיעה בעמוד 122 בספר.
א) (5 נקודות) הריצו את השגרה DoesItSort על המערך A=(7,5,1,3,2,4,6).
ב) (10 נקודות) הוכיחו או הפריכו: DoesItSort(A, 1, n) ממיינת את מערך A. אם לדעתכם השגרה ממיינת כל מערך A שהיא מקבלת- הסבירו מדוע בדיוק ובקצרה (אין צורך בהוכחה פורמאלית). אם לדעתכם השגרה היא לא שגרת מיון- הציעו קלט כללי A בגודל n שהוא תמורה של (1,...,n), שעבורו A בסוף ביצוע השגרה אינו ממויין.
ג) (10 נקודות) נתחו את זמן הריצה של DoesItSort(A, 1, n) במקרה הגרוע ביותר ובמקרה הטוב ביותר, בהנחה שסיבוכיות ReverseSort(A, 1, n) היא Θ(n2). יש לכתוב נוסחאות נסיגה עבור המקרה הגרוע ועבור המקרה הטוב ולפתור אותן.
העתק שאלה
שתף שאלה
סמן כחשוב
סמן כבוצע
האוניברסיטה הפתוחהמועד א1 · 2025 · סמסטר א
★★★★★
סיבוכיותרקורסיהנוסחת נסיגהמיוןניתוח אלגוריתמיםמעקב אחר אלגוריתםמיון מהירהוכחת נכונות
שאלות מעקב אחר אלגוריתם במבני נתונים ומבוא לאלגוריתמים עם פתרונות
שאלות תרגול במבני נתונים ומבוא לאלגוריתמים בנושא מעקב אחר אלגוריתם ממבחנים של האוניברסיטה הפתוחה. השאלות ממוינות לפי רמת קושי, עם פתרונות לבדיקה עצמית - כך שניתן ללמוד מטעויות ולהבין את דרך הפתרון לפני הבחינה. ניתן לאתר שאלות חוזרות ולהריץ מבחני סימולציה ממוקדים בנושא מעקב אחר אלגוריתם.