מבני נתונים ומבוא לאלגוריתמים האוניברסיטה הפתוחה – סטטיסטיקות מבחנים | prepd
מבני נתונים ומבוא לאלגוריתמים – סטטיסטיקות מבחנים
מבוסס על 239 שאלות מ-20 מבחנים (2016–2026)
סוגי השאלות הנפוצים ביותר
1
עיצוב מבני נתונים מבוססי BST מורחב
תכנון מבני נתונים התומכים בפעולות סטטיסטיות וכמותיות (סכום טווח, חציון, שכיחות, היפוכים, סדר-עצמה) בסיבוכיות לוגריתמית. מרחיבים עץ חיפוש מאוזן (כגון RB-Tree) בשדות עזר בכל צומת ומעדכנים אותם בזמן סיבוב ועדכון.
הופיע ב-17 שאלות על פני 9 שנים, לאחרונה 2024
201620172018201920202021202220232024
2
פתרון נוסחאות נסיגה רקורסיביות
פתרון נוסחאות נסיגה לקביעת סיבוכיות זמן ריצה. משתמשים במשפט האב (כולל זיהוי המקרה הרלוונטי), עץ רקורסיה, או החלפת משתנים — בהתאם למבנה הנסיגה (חלוקה, שורש, גורמים לוגריתמיים).
הופיע ב-14 שאלות על פני 8 שנים, לאחרונה 2024
20172018201920202021202220232024
3
הוכחה והפרכה של טענות סיבוכיות
טענות על קשרים אסימפטוטיים (O, Θ) בין פונקציות, במיוחד עם טרנספורמציות של לוגריתם ואקספוננט. מוכיחים באמצעות הגדרות פורמליות או מפריכים בנגדדוגמה, תוך זהירות ממעברים לא חוקיים בין סדרי גודל.
הופיע ב-12 שאלות על פני 6 שנים, לאחרונה 2024
201720192020202120222024
4
ערימות עם שדות נוספים ושינויי מבנה
בניה ועדכון של ערימות מקסימום ומינימום הכוללות שדות עזר (מינימום או מקסימום של תת-ערימה). משנים את MAX-HEAPIFY או MIN-HEAPIFY כך שבכל הורדה/העלאה מעדכנים את שדות העזר של הצמתים שנגעו בהם, תוך שמירה על סיבוכיות לינארית לבנייה ולוגריתמית להכנסה.
הופיע ב-16 שאלות על פני 6 שנים, לאחרונה 2024
201620192020202120222024
5
סיבוכיות מיון-מהיר ומיון-מיזוג
ניתוח זמן ריצה של אלגוריתמי מיון במקרים מיוחדים: בחירת ציר שאינה אקראית, מערכים כמעט-ממוינים או עם ערכים חוזרים. מוכיחים חסמים על ידי בניית יחס נסיגה ופתרונו, לרוב תוך שימוש במשפט המאסטר או עץ הרקורסיה.
הופיע ב-13 שאלות על פני 5 שנים, לאחרונה 2024
20162020202120232024
6
שחזור עץ חיפוש מסריקה
שחזור עץ חיפוש בינרי מסריקה תחילית או תוכית, כולל הוכחת יחידות או הפרכה בדוגמה נגדית. מנתחים אילו סריקות מאפשרות שחזור חד-משמעי ומתארים אלגוריתם רקורסיבי המנצל את תכונת הסדר של עח"ב.
הופיע ב-22 שאלות על פני 6 שנים, לאחרונה 2023
201720182020202120222023
7
עצי חיפוש בינרי עם שדה צובר
כתיבת אלגוריתמים על עצי חיפוש בינרי המכילים שדה אוגר/צובר: בדיקת תקינות BST, חיפוש, הכנסה ומחיקה. מחשבים את הערך האמיתי של כל מפתח תוך מעקב אחר סכום השדות הצוברים לאורך הנתיב מהשורש לצומת.