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

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

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

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

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

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

הנחיות

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

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

(~24 נקודות)

אנא כתוב אלגוריתם יעיל המקבל כקלט מערך A של מספרים שלמים חיוביים, ומספר שלם חיובי t כלשהו, ומוציא כפלט True או False בהתאם לשאלה האם קיימת תת-קבוצה של הערכים בA שסכום איבריה הוא בדיוק t.

דוגמה:

נניח שהמערך הוא $\displaystyle A = [2, 1, 10, 40, 20]$ , ו $\displaystyle t = 52$ . התשובה היא True, מפני ש $\displaystyle 2 + 10 +40 = 52$ .

אנא הבע סיבוכיות תשובתך במונחי $\displaystyle n$ ו $\displaystyle t$ .

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

(~24 נקודות)

נתון גרף לא-מכוון וקשיר $\displaystyle G = (V, E)$ , וכן טבלת עלויות לקשתות Weights. ידוע שאין שתי קשתות בעלות אותו המשקל: לכל שתי קשתות $\displaystyle e_1$ ו $\displaystyle e_2$ , בהכרח Weights[e1] ≠ Weights[e2]. אנא הוכח או הפרך את הטענה הבאה: לגרף קיים עץ פורש מינימום יחידי.

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

(~24 נקודות)

נתונה מטריצה בת $\displaystyle n$ עמודות ו $\displaystyle m = 2^n - 1$ שורות. כל כניסה במטריצה היא 0 או 1, ולכן כל שורה מתארת מספר בינרי בעל $\displaystyle n$ ביטים. השורות אינן מסודרות בסדר ידוע, אך ידוע שאין שתי שורות זהות. מכאן נובע שחסרה שורה להשלמת כל $\displaystyle 2^n$ המספרים האפשריים בעלי $\displaystyle n$ ביטים.

דוגמה:

עבור $\displaystyle n = 2$ , ייתכן שהשורה הראשונה היא המערך [0, 1] (המתאר בבינרית את המספר 1), השורה השנייה היא המערך [1, 1] (המתאר בבינרית את המספר 3), והשורה השלישית היא המערך [0, 0] (המתאר בבינרית את המספר 0). השורה החסרה היא המערך [1, 0] (המתאר בבינרית את המספר 2).

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

רמז

נסה להפוך את הבעיה לבעיה קטנה בחצי (בערך) בזמן לינארי.

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

(~24 נקודות)

באפליקציה מסויימת, יש צורך במבנה נתונים התומך בפעולות Insert(pq, v),‏ Delete-Min(pq),‏ וMin(pq).‏ משמעות פעולות אלו היא בדיוק זו של תור קדימויות - מדובר במבנה נתונים המשתמש באיזושהי השוואה כדי לספק את האיבר הקטן בכל עת.

ידוע שבאפליקציה זו, מספר הפעולות הצפוי מסוג Delete-Min(pq) וMin(pq) הוא זניח יחסית למספר הפעולות הצפוי מסוג Insert(pq, v).‏ אנא הצע מימוש כך שInsert(pq, v) יהיה יעיל ככל האפשר. מה סיבוכיות שתי הפעולות האחרות במימוש שהצעת?
האם ייתכן מימוש לתור קדימויות בו הן Insert(pq, v) והן Delete-Min(pq) יעבדו בזמן $\displaystyle O(1)$ ?

שימו לב:

בסעיף הראשון, עליך למצוא יעיל ככל האפשר לInsert(pq, v). אין צורך למצוא מימוש יעיל במיוחד לשתי הפעולות האחרות.
אפשר לפתור את הסעיף השני גם מבלי לפתור את הסעיף הראשון.

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

(~14 נקודות)

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

דוגמה:

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

רמז

צייר גרף שבו כל אדם הוא צומת. מה יקרה אם תמחק צומת כלשהו והקשתות היוצאות ממנו?

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

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

תוכן עניינים

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

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

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

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

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

צפיות

כלים אישיים

ניווט

קהילה

חיפוש

תיבת כלים

הדפסה/ייצוא