מתכונת יא שאלון +פיתרון

[רם מעיין]

אני אוסיף בשירשור פתרונות של רוב השאלות במבחן

[רם מעיין]

שאלה 15

[רם מעיין]

שאלה 16

השפה היא

{w|שפת כל המילים שבהם ההפרש בין מספר הבנים למספר הבנות הוא לכל היותר 1 }

[רם מעיין]

שאלה 2

סוד 1 - מספר חוליות ברשימה יעילות
    O(n) נסמן ב n את אורך הרשימה . הפעולה מכילה פקודות מיעילות O(1) כולל הפקודות על רשימה
הפעולה עוברת פעם אחת על כל איבר ברשימה. לכן היעילות היא O(n)

סוד4 מחזירה את מיקום החוליה לפני המיקום ש P מפנה אליו. יעילות o(n) מאותם נימוקים

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

[רם מעיין]

שאלה 2 יעילות

סוד, סוד 2 - יעילות של n בריבוע. כי סוד 2 מתבצעת n/2 פעמים,
 וכוללת בתוכה פקודות המזמנות פעולות שהיעילות שלהן
לכל היותר היא O(n)

[רם מעיין]

שאלה 1 א העץ הוא עץ סיגמה, כי כל תת העצים שלו מקיימים את הכלל
שערך השורש גדול מסכום הערכים של כל צאצאי תת העץ
נשנה את השורש ל 1 והעץ כבר לא יהיה עץ סיגמה.

ג היעילות של הפעולה היא o(n בריבוע כי עבור כל צומת בעץ אנו עוברים על כל הצמתים
הצאצאים שלו במקרה הגרוע של שרשרת צמתים נקבל את הסכום של
n,n-1,n-2n-3n-4,n.... לכן אנו מקבלים יעילות של n בריבוע

[רם מעיין]

שאלה 14

[רם מעיין]

שאלה 13 הוכחת ח"ה

[רם מעיין]

שאלה 4