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

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

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

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

הנחיות

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

[עריכה] 1

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

דוגמה:

[עריכה] 2

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

[עריכה] א'

אנא הראי מקרה שבו קיים צומת $\displaystyle u\in V$ , כך שאין מסלול יחיד זול ביותר מ $\displaystyle S$ ל $\displaystyle V$ .

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

[עריכה] ג'

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

[עריכה] 3

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

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

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

בכל שורת טקסט יש מקום ל $\displaystyle M$ תווים (אין מילה בעלת יותר מ $\displaystyle M$ תווים).
יש להדפיס רווח יחיד בין כל שתי מילים באותה שורה.

דוגמה:

נניח ש $\displaystyle M = 20$ , והמילים הן

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 תווים בשורה הראשונה).

אם בשורה יש $\displaystyle m'$ תווים (כולל הרווחים בין המילים), אז יופי השורה הוא $\displaystyle \frac{1}{(M - m' + 1)^2}$ . יופי הפסקה מוגדר כסכום היופי של השורות שלו, למעט השורה האחרונה.

דוגמה:

בפסקה

If they have no

rice, let them

eat ladoo.

יש 15 תווים בשורה הראשונה, ו14 תווים בשורה השניה. יופי הפסקה, לכן הוא $\displaystyle \frac{1}{(20 - 15 + 1)^2} + \frac{1}{(20 - 14 + 1)^2} = \frac{1}{6^2} + \frac{1}{7^2}$ .

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