מבני נתונים ואלגוריתמים - מחברת קורס/מבחן סופי מועד א' סמסטר ב' 2007 - שאלות

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

< מבני נתונים ואלגוריתמים - מחברת קורס

קפיצה אל: ניווט, חיפוש

תבנית:התנצלות לשון זכר

הנחיות

החומר המותר בשימוש במבחן זה הוא כל דף (מודפס) שמקורו באתר הקורס, כולל דפים שעליהם הערות בכתב יד. כל חומר אחר אסור בשימוש במבחן. השימוש בכל מכשיר אלקטרוני (כולל מחשבון) אסור בשימוש במבחן.
אנא שים לב שלצד כל שאלה מופיע מספר הנקודות (המשוער) שלה, ושסכום הנקודות במבחן הוא 110.
1. שאלה מספר 5 היא קשה, וממומלץ שתפתור אותה לאחר שפתרת את שאר השאלות. ייתכן שמספר הנקודות שיוענק לשאלה יהיה נמוך ממה שכתוב (מבלי לפגוע בסכום הנקודות).
2. לא יינתנו פקטורים מעבר לכך.
בכל שאלה, אם תציין במפורש שאינך עונה עליה - תקבל 15% מערכה.
בתשובה שבה אתה משתמש בתכנון דינמי, 70% מהניקוד יוענק לפתרון נכון, מוכח, ויעיל, המוצא את מחיר הפתרון הטוב ביותר. 100% מהניקוד יוענק לפתרון העונה על הדרישות הנ"ל, אך מדפיס במפורט גם את פרטי הפתרון.

[עריכה] שאלה 1

(~20 נקודות)

בכיתה למדנו כבר על עצי חיפוש בינריים. שאלה זו עוסקת בווריאציה. עץ Foo-Bar מוגדר כך:

כל צומת הוא אחד משני סוגים: צומת Foo או צומת Bar.
1. צומת Bar מחזיק מפתח אחד ו(עד ל)2 ילדים (כמו הצמתים הרגילים שראינו).
2. צומת Foo מחזיק 2 מפתחות ו(עד ל3 ילדים.
העץ מקיים את את תכונת הFoo-Bar - לכל צומת x:
1. כל מפתח בתת-עץ שמאלי של מפתח כלשהו, קטן או שווה לו.
2. כל מפתח בתת-עץ ימני של מפתח כלשהו, גדול או שווה לו.
כל המסלולים משורש העץ לעלה ריק (Nil) בעל אותו אורך בדיוק.

דוגמה: צומת Bar

דוגמה: צומת Foo

דוגמה: עץ Foo-Bar

להלן דוגמה לעץ Foo-Bar תקין. בעץ זה 3 צמתים (2 מסוג Bar, ו1 מסוג Foo). יש לו 4 מפתחות, וגבהו 2.

אנא הוכח שעץ Foo-Bar הוא לוגריתמי: אם יש בו $\displaystyle n$ מפתחות וגבהו הוא $\displaystyle h$ , אז $\displaystyle h = O(\log(n))$ .

שימו לב:

אל תתייחס לשאלה כיצד ליצור עץ כזה, או כיצד להכניס ולהוציא מפתחות ממנו - זה לא רלוונטי.

[עריכה] שאלה 2

(~15 נקודות)

נתון גרף $\displaystyle G = (V, E)$ מכוון וקשיר מצומת $\displaystyle s \in V$ כלשהו. לכל קשת יש מחיר. רוצים למצוא את המסלול הזול ביותר מs לכל צומת u כלשהו, אך תחת העדפה למסלולים שארכם (כלומר, מספר קשתותיהם) זוגי. $\displaystyle x$ מציין גודל קנס כלשהו. אם מסלול כלשהו מ $\displaystyle s$ ל $\displaystyle u$ הוא אי-זוגי, יש להוסיף למחיר מסלול זה קנס בגובה $\displaystyle x$ .

אנא תאר אלגוריתם המקבל כקלט את הגרף, טבלת עלויות לקשתות, וגודל הקנס, ומוצא את מחיר המסלול הזול ביותר (במובן שאותו הסברנו כרגע) לכל צומת $\displaystyle u$ . אנא הוכח נכונות ונתח סיבוכיות.

[עריכה] שאלה 3

(~20 נקודות)

בשאלה זו עליך להוכיח חסם תחתון על $\displaystyle T(n)$ , מספר עצי החיפוש הבינריים השונים בעלי $\displaystyle n$ מפתחות שונים זה מזה.

דוגמה:

נניח שעץ החיפוש מכיל את המפתחות $\displaystyle 1, 2$ . יש 2 עצים מתאימים:

נניח שעץ החיפוש מכיל את המפתחות $\displaystyle 1, 2, 3$ . יש 5 עצים מתאימים:

עצי חיפוש בינריים בעלי המפתחות 1, 2, ו3.

מהדוגמה נוכל להסיק כי

$\displaystyle T(0) = T(1) = 1$ , $\displaystyle T(2) = 2$ , $\displaystyle T(3) = 5$ .

אנא הוכח ש $\displaystyle T(n) = \Omega(2^n)$ , כלומר שמספר עצי החיפוש הבינריים גדל בצורה אקספוננציאלית.

[עריכה] שאלה 4

(~35 נקודות)

רשת החומוסיות מק-לאפה מתכננת להקים סניפים רבים לאורך רחוב איבן-גבירול בתל אביב. $\displaystyle m_1, m_2, \ldots m_n$ מציינים את מספרי הבתים ברחוב בהם יש מקום פנוי להקמת סניף חדש. הרשת שוקלת היכן להקים את הסניפים החדשים:

מסקר שוק, הרשת מעריכה שבבית מספר $\displaystyle m_i$ רווחיה הצפויים יהיו $\displaystyle p_i$ ‏( $\displaystyle p_i$ הוא מספר חיובי כלשהו).
הרשת אינה מוכנה להקים שני סניפים שמרחקם זה מזה הוא פחות מ $\displaystyle k$ ‏ ( $\displaystyle k$ הוא מספר שלם חיובי כלשהו).

דוגמה:

אם $\displaystyle k = 20$ והרשת בוחרת להקים סניף בבית מספר 135, אסור לה להקים סניף בבית מספר 143, שכן $\displaystyle 143 - 135 < 20$ .

אנא כתוב אלגוריתם יעיל המקבל את המערך M (המכיל את מספרי הבתים), את המערך P (המכיל את הרווחים הצפויים), ואת המספר k (המציין את מגבלת המרחק), ומדפיס את מספרי הבתים שהקמת הסניפים בהם צפוייה למקסם את הרווחיות. אנא הוכח נכונות ונתח סיבוכיות.

[עריכה] שאלה 5

(~20 נקודות)

במסיבה כלשהי יש $\displaystyle n$ אנשים; חלקם לחץ ידיים זה עם זה. כעת יש להושיב אותם משני צידי שולחן. אנא הוכח שאפשר להושיב אותם באופן כזה כך שכל אחד יושב מול לפחות חצי מהאנשים שאתם לחץ יד.

דוגמה:

נניח שבמסיבה יש שלשה אנשים: 1,‏ 2,‏ ו3, ורק 1 ו2 לחצו ידיים זה עם זה. אכן אפשר להושיב את 1 ו3 בצד אחד של השולחן, ואת 2 בצד השני.

מבני נתונים ואלגוריתמים - מחברת קורס/מבחן סופי מועד א' סמסטר ב' 2007 - שאלות

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

תוכן עניינים

[עריכה] שאלה 1

[עריכה] שאלה 2

[עריכה] שאלה 3

[עריכה] שאלה 4

[עריכה] שאלה 5

צפיות

כלים אישיים

ניווט

קהילה

חיפוש

תיבת כלים

הדפסה/ייצוא