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

הנחיות

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

1 עריכה

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





דוגמה:

 
בתים.
 
קו הרקיע.


2 עריכה

נתון גרף מכוון  , צומת  ,וטבלת מחירים חיוביים לקשתות  . בשאלה זו אנו מתעניינים במסלול הזול ביותר מ-s לכל צומת  .

א' עריכה

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

ב' עריכה

אנא מצאי אלגוריתם יעיל המקבל את הגרף, צומת המוצא, וטבלת העלויות, ומחזיר מערך בוליאני Unique. Unique[u] יכיל את הערך True אמ"ם יש מסלול יחידי מ  ל . אנא הוכיחי את נכונות האלגוריתם ונתחי סיבוכיותו.

ג' עריכה

אנא מצאי אלגוריתם יעיל המקבל את הגרף, צומת המוצא, וטבלת העלויות, ומחזיר מערך Shortest-Cheapest. ּShortest-Cheapest[u] יכיל את מספר הצמתים במסלול הקצר ביותר מבין המסלולים הזולים ביותר מ  ל . אנא הוכיח את נכונות האלגוריתם ונתחי סיבוכיותו.

3 עריכה

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



ברצוננו להדפיס פסקת טקסט בצורה יפה.

נתונות לנו   מילים, Word[1], Word[2], ..., Word[n]. עלינו להחליט היכן לסיים כל שורה בפסקה, לפי הכללים הבאים:

  1. בכל שורת טקסט יש מקום ל  תווים (אין מילה בעלת יותר מ  תווים).
  2. יש להדפיס רווח יחיד בין כל שתי מילים באותה שורה.



דוגמה:

נניח ש , והמילים הן

If they have no rice, let them eat ladoo.

נוכל לבנות פסקה כך:

If they have no

rice, let them

eat ladoo.

אך לא כך:

If they have no rice, let them eat

ladoo.

(בדוגמה השניה יש יותר מ20 תווים בשורה הראשונה).


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



דוגמה:

בפסקה

If they have no

rice, let them

eat ladoo.

יש 15 תווים בשורה הראשונה, ו14 תווים בשורה השניה. יופי הפסקה, לכן הוא  .


אנא מצא אלגוריתם יעיל למציאת הפסקה היפה ביותר. הנח ש  הוא משתנה גלובלי נתון, ושקיימת פונקציה Length המקבלת מספר   ומחזירה את מספר התווים במילה ה .

4 עריכה

א' עריכה

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



 
צביעה אפשרית של עץ אדום-שחור.

ב' עריכה

פתור את נוסחת הנסיגה הבאה:  

ג' עריכה

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



 
זרימה אפשרית בגרף נתון.

ד' עריכה

פתור את נוסחת הנסיגה הבאה: