א. נתון אלגוריתם הרץ באופן רקורסיבי. בכל שלב, האלגוריתם מבצע עבודה של n (לינארית בגודל הקלט), ומבצע קריאה רקורסיבית אחת לקלט בגודל n−2. 1. כתבו את נוסחת הנסיגה T(n). 2. פתרו את הנוסחה ומצאו חסם (Θ) מדויק. (שימו לב: משפט האב אינו ישים כאן ישירות). ב. סדרו מהקטן לגדול אסימפטוטית (ייתכנו שוויונות) עם נימוק קצר:
מערך A בגודל n נקרא "יוני-מודאלי" (Unimodal) אם הסדרה עולה עד לאיבר מקסימלי מסוים ("הפסגה") ואחריו יורדת. לדוגמה: {1,2,4,9,12,8,5} (הפסגה היא 12). מותר להניח שכל איברי המערך שונים זה מזה. הפסגה יכולה להיות גם בקצה (מקרה מונוטוני).
א. (10 נק') כתבו אלגוריתם המוצא את האינדקס של האיבר המקסימלי (הפסגה) במערך יוני-מודאלי בזמן O(logn). הסבירו בקצרה את נכונות האלגוריתם.
ב. (8 נק') נתון מערך יוני-מודאלי. תארו בקצרה אלגוריתם למיון המערך בזמן לינארי (O(n)). ניתן להשתמש במערך עזר. הסבירו בקצרה את נכונות האלגוריתם.
ג. (7 נק') נתון מערך כלשהו של n מספרים שונים (לאו דווקא יוני-מודאלי). הוכיחו שלא ניתן להפוך אותו ליוני-מודאלי (כלומר לשנות את סדר איבריו כך שהוא יהיה יוני-מודאלי) בזמן o(nlogn) (או קטנה של nlogn).
א. נניח שבונים עץ חיפוש בינרי על ידי כך שמכניסים לעץ, בזה אחר זה, ערכים השונים זה מזה. 1. מהו זמן הריצה של בניית העץ במקרה הגרוע? 2. היכן נמצא האיבר שהוכנס שני לעץ? 3. היכן נמצא האיבר שהוכנס שני לעץ אם לאחר סיום הבנייה בוצעה מחיקה של אחד הצמתים האחרים בעץ? פרטו. 4. היכן נמצא האיבר שהוכנס שני לעץ אם ההכנסות התבצעו לתוך עץ אדום שחור (ללא מחיקות)? ב. נתון מערך A של 2n מספרים שלמים ושונים זה מזה בתחום [0..nlogn]. בנוסף נתון עץ חיפוש בינארי T (לא עץ אדום שחור), ובו n צמתים. כתבו אלגוריתם הבודק בזמן O(n) האם כל האיברים בעץ T מופיעים במערך A.
העתק שאלה
שתף שאלה
סמן כחשוב
סמן כבוצע
האוניברסיטה הפתוחהמועד א2 · 2026 · סמסטר א
★★★★★
עצי חיפושעץ אדום-שחורטבלאות גיבובסיבוכיותאלגוריתמיםניתוח אלגוריתמיםמבנה נתונים
נתבונן בשגרה הבאה המקבלת כקלט מערך A של מספרים שונים זה מזה:
הסבר: בכל שלב של הלולאה השגרה בוחרת את ערך המיקום ה- ⌊n/2⌋ בתחום הנתון (1 עד n), ומשתמשת בו כאיבר ציר כדי לבצע חלוקה בתחום זה. בלולאה הבאה התחום מצטמצם בחצי.
הערה: השגרה partitionWithPivot מחליפה את איבר הציר עם האיבר האחרון וקוראת לשגרת החלוקה הרגילה.
א. מהו זמן הריצה של השגרה הנתונה? ב. נוסיף לתכונת ערימת המינימום את התכונה הבאה: כל איבר ברמה h קטן מכל האיברים ברמה h+1. הוכיחו או הפריכו: ניתן לבנות ערימת מינימום המקיימת את התכונה שלעיל בזמן לינארי.
העתק שאלה
שתף שאלה
סמן כחשוב
סמן כבוצע
האוניברסיטה הפתוחהמועד א1 · 2026 · סמסטר א
★★★★★
סיבוכיותניתוח אלגוריתמיםסטטיסטיקות סדרערימותמבנה נתוניםהוכחת נכונותתכנון מבנה נתונים
מערך נקרא "ממוין מסובב" (Rotated Sorted Array) אם הוא מתקבל ממערך ממוין (עולה ממש) שעבר הזזה ציקלית (סיבובים) ימינה מספר פעמים. כלומר, לקחו מערך ממוין, חתכו את הסוף שלו והדביקו אותו להתחלה. לדוגמה, המערך הבא הוא ממוין מסובב: [15,20,25,1,5,8,10] (המערך המקורי היה: [1,5,8,10,15,20,25] ועבר הזזה). שימו לב: גם מערך ממוין רגיל נחשב למערך מסובב (עם הזזה של 0). הניחו כי כל איברי המערך שונים זה מזה. א. (10 נק') כתבו אלגוריתם המוצא את האינדקס של האיבר המינימלי במערך (בדוגמה לעיל: האינדקס של 1). זמן הריצה הנדרש הוא לוגריתמי: O(logn). הסבירו בקצרה את נכונות האלגוריתם. ב. (8 נק') כתבו אלגוריתם המקבל מערך ממוין מסובב ומספר כלשהו: x. האלגוריתם יחזיר את האינדקס של x במערך (או יחזיר "לא קיים"). זמן הריצה הנדרש הוא לוגריתמי: O(logn). הסבירו בקצרה את נכונות האלגוריתם. ג. (7 נק') נניח כעת שאיברי המערך אינם בהכרח שונים (ייתכנו כפילויות), והמערך עדיין ממוין-מסובב. הראו שקיים קלט שעבורו האלגוריתם שכתבתם למציאת האיבר המינימלי יחזיר תשובה שגויה.
נתונה ערימת מקסימום בינארית H עם n איברים שונים, המיוצגת על-ידי מערך. א. (10 נק') נתון מספר x. תארו אלגוריתם שמחזיר את כל האיברים בערימה שגדולים מ-x בסדר יורד. האלגוריתם צריך להיות output-sensitive. כלומר, זמן הריצה יהיה O(mlogm), כאשר m הוא מספר הצמתים שהוחזרו. מותר זיכרון נוסף O(m). הסבירו בקצרה מדוע האלגוריתם נכון וכיצד תכונת הערימה מאפשרת "גיזום" תתי-עצים. ב. (8 נק') ידוע שהצומת y הוא עלה בערימה H. כתבו נכון/לא נכון: זמן הריצה למחיקת הצומת y מהערימה הוא O(1) במקרה הגרוע. נמקו את תשובתכם בקצרה. ג. (7 נק') הוכיחו שכל אלגוריתם המקבל את הערימה H ומספר k, וקובע בוודאות האם k נמצא בערימה חייב במקרה הגרוע לבקר Ω(n) צמתים. שימו לב: יש לספק הוכחה ולא להסתפק בהסבר כללי ש"ערימה אינה עץ חיפוש".
העתק שאלה
שתף שאלה
סמן כחשוב
סמן כבוצע
האוניברסיטה הפתוחהמועד א2 · 2026 · סמסטר א
★★★★★
ערימותתכנון מבנה נתוניםאלגוריתמיםסיבוכיותניתוח אלגוריתמיםחסם תחתוןהוכחת נכונות
נתונה ערימת מינימום בינרית H עם n איברים שונים, המיוצגת על-ידי מערך.
א. (10 נק') נתון מספר x. תארו אלגוריתם שמחזיר את כל האיברים בערימה שקטנים מ-x בסדר עולה. האלגוריתם צריך להיות output-sensitive. כלומר, זמן הריצה יהיה O(mlogm), כאשר m הוא מספר הצמתים שהוחזרו. מותר זיכרון נוסף O(m). הסבירו בקצרה מדוע האלגוריתם נכון וכיצד תכונת הערימה מאפשרת "גיזום" תתי-עצים.
ב. (8 נק') הוכיחו שלא ניתן לבצע את המשימה שבסעיף הקודם בזמן O(m) במקרה הגרוע.
ג. (7 נק') נתונות k ערימות מינימום שאורכם הכולל n. כתבו נכון/לא נכון והסבירו בקצרה: ניתן למזג את k הערימות למערך ממוין בגודל n בזמן O(nlogk).
העתק שאלה
שתף שאלה
סמן כחשוב
סמן כבוצע
האוניברסיטה הפתוחהמועד א1 · 2026 · סמסטר א
★★★★★
ערימותאלגוריתמיםסיבוכיותסריקת עציםרקורסיה
תכננו מבנה נתונים D המנהל אוסף של מספרים שלמים, ותומך בפעולות הבאות בסיבוכיות הזמן המצוינת:
Init(D) - אתחול מבנה ריק. זמן: O(1)
Insert(D, x) - הכנסת איבר x למבנה. זמן: O(logn)
Delete(D, x) - מחיקת איבר x מהמבנה (נתון מצביע לצומת למחיקה). זמן: O(logn)
Min-Gap(D) - החזרת ההפרש המינימלי בין שני מספרים סמוכים בגודלם הקיימים כרגע במבנה. לדוגמה: אם המבנה מכיל {1,5,9,20}, ההפרש המינימלי הוא 4 (בין 1 ל-5 או בין 5 ל-9). זמן ריצה נדרש: O(1) במקרה הגרוע.
הנחיות:
פרטו באילו מבני נתונים אתם משתמשים (ייתכן שצריך יותר מאחד).
הסבירו כיצד ממומשת כל פעולה, ובפרט כיצד נשמר המידע המאפשר לענות על Min-Gap בזמן קבוע.
שימו לב: ההכנסות והמחיקות צריכות לעדכן את ה-Min-Gap בהתאם.
העתק שאלה
שתף שאלה
סמן כחשוב
סמן כבוצע
האוניברסיטה הפתוחהמועד א1 · 2026 · סמסטר א
★★★★★
תכנון מבנה נתוניםעץ אדום-שחורמבני נתונים מורחביםעצי חיפושסיבוכיות
תכננו מבנה נתונים D המנהל אוסף של מספרים שלמים, ותומך בפעולות הבאות בסיבוכיות הזמן המצוינת:
Init(D) - אתחול מבנה ריק. זמן: O(1)
Insert(D, x) - הכנסת איבר x למבנה. זמן: O(logn)
Delete(D, x) - מחיקת איבר x מהמבנה (נתון מצביע לצומת למחיקה). זמן: O(logn)
Max-Gap(D) - החזרת ההפרש המקסימלי בין שני מספרים סמוכים בגודלם הקיימים כרגע במבנה. לדוגמה: אם המבנה מכיל {1,5,9,20}, ההפרש המקסימלי הוא 11 (בין 9 ל-20). זמן ריצה נדרש: O(1) במקרה הגרוע.
הנחיות:
פרטו באילו מבני נתונים אתם משתמשים (ייתכן שתצטרכו יותר מאחד).
הסבירו כיצד ממומשת כל פעולה, ובפרט כיצד נשמר המידע המאפשר לענות על Max-Gap בזמן קבוע.
שימו לב: ההכנסות והמחיקות צריכות לעדכן את ה-Max-Gap בהתאם.
שימו לב שלא מדובר בהפרש המקסימלי במבנה כולו אלא רק בין איברים סמוכים בגודלם.
העתק שאלה
שתף שאלה
סמן כחשוב
סמן כבוצע
האוניברסיטה הפתוחהמועד א2 · 2026 · סמסטר א
★★★★★
תכנון מבנה נתוניםמבני נתונים מורחביםעץ אדום-שחורסטטיסטיקות סדרסיבוכיות
מבני נתונים ומבוא לאלגוריתמים – סיבוכיות, מבני נתונים בסיסיים ואלגוריתמי מיון וחיפוש. נושאים מרכזיים: סיבוכיות, מיון, חיפוש, עצי חיפוש, גרפים. 282 שאלות ממבחנים עם פתרונות, ממוינות לפי נושא ורמת קושי. ניתן לתרגל לפי נושאים, לסנן שאלות חוזרות ולהריץ מבחני סימולציה לפני הבחינה. הכנה למבני נתונים ומבוא לאלגוריתמים מתמקדת בסיבוכיות, מיון ועצי חיפוש. לימוד עצמי עם שאלות ממבחנים - ממוינות לפי נושא ורמת קושי - הוא הדרך הכי יעילה לזהות את הנושאים שנכנסים למבחן. המאגר כולל שאלות מהאוניברסיטה הפתוחה.