איך לתרגל שאלות עץ החלטות במבני נתונים ומבוא לאלגוריתמים?

באתר prepd תמצאו שאלות עץ החלטות במבני נתונים ומבוא לאלגוריתמים ממבחנים אמיתיים של האוניברסיטה הפתוחה. השאלות ממוינות לפי רמת קושי.

כמה שאלות עץ החלטות יש במבני נתונים ומבוא לאלגוריתמים?

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

מה חשוב לדעת על עץ החלטות לקראת מבחן במבני נתונים ומבוא לאלגוריתמים?

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

מבני נתונים ומבוא לאלגוריתמים - עץ החלטות

סיבוכיות, מבני נתונים בסיסיים ואלגוריתמי מיון וחיפוש

סטטיסטיקות מבחנים

תתי-נושאים של מיון

רמת קושי:

א) (12 נקודות) נתון מערך

A

בגודל

n

של מספרים טבעיים עם התכונה הבאה:
כל אחד מהמפתחות במערך, מופיע בו שלוש פעמים לכל היותר.
פרופסור ידענוביץ' טוענת כי ישנו חסם תחתון

Ω (n lo g n)

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

ב) (13 נקודות) נתון מערך

A

בגודל

n

של מספרים טבעיים עם התכונה הבאה:
הערך המוחלט של ההפרש בין כל שני איברים סמוכים במערך הוא שלוש לכל היותר.
פרופסור ידענוביץ' טוענת כי ישנו חסם תחתון

Ω (n lo g n)

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

הערות:

אם אתם מפריכים טענה ע"י כתיבת אלגוריתם-

יש להקפיד על כתיבת רעיון, אלגוריתם, נכונות וסיבוכיות.

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד ב · 2025 · סמסטר ב

★★★★★

חסם תחתוןמיוןניתוח אלגוריתמיםסיבוכיותמיון מנייהעץ החלטות

נגדיר איבר רוב במערך בגודל

n

כאיבר שמופיע יותר מ-

\frac{n}{2}

פעמים.

א) (10 נק') בהינתן מערך

A

ממוין בגודל

n

-
הציעו רעיון לאלגוריתם שזמן ריצתו הוא

O (lo g n)

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

לנוחיותכם מצורפת שגרת חיפוש בינארי רקורסיבי:

ב) (15 נק') הוכיחו שהאלגוריתם שכתבתם בסעיף א' הוא אופטימלי. כלומר הוכיחו שלבעיית חיפוש איבר רוב במערך ממויין יש חסם תחתון

Ω (lo g n)

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א2 · 2025 · סמסטר א

★★★★★

חיפוש בינאריחסם תחתוןסיבוכיותאלגוריתמיםמערכיםעץ החלטות

נתון מערך

A

בגודל

n

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

1 < j < n

כך שלכל

1 \leq i < j

מתקיים

A [i] < A [i + 1]

, ולכל

j \leq i < n

מתקיים

A [i] > A [i + 1]

.

דוגמא:

j = 7

A = (1, 3, 4, 6, 77, 200, 509, 66, 3)

.

הערה: האינדקס הראשון במערך

A

הוא

1

א) (13 נקודות) תארו אלגוריתם למציאת

j

בזמן

O (lo g n)

.

ב) (12 נקודות) פרופסור מעינוביץ טוענת כי פיתחה אלגוריתם למציאת

j

, שבו

O (lo g lo g n)

השוואות. כתבו אלגוריתם כמו זה שמציעה הפרופסור, או הוכיחו כי היא טועה.

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד ב · 2025 · סמסטר א

★★★★★

אלגוריתמיםחיפושחיפוש בינאריסיבוכיותניתוח אלגוריתמיםחסם תחתוןעץ החלטותהוכחת נכונותשמורת לולאה

שאלות עץ החלטות במבני נתונים ומבוא לאלגוריתמים עם פתרונות

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