פורום מקיף עומר

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

שאלה 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