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

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

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

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

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

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

מבני נתונים ומבוא לאלגוריתמים - עץ סדר סטטיסטי

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

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

תתי-נושאים של עצי חיפוש

רמת קושי:

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

S

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

הצבעה לאירוויזיון מיוצגת ע"י רשומה המכילה שני שדות:
זמן הצבעה Time - סדרה ייחודית של 6 ספרות המבטאת את שעת ההצבעה,
לדוגמא הסדרה 221015 מבטאת את שעת ההצבעה 22:10:15.
שדה בוליאני Vote - שערכו הוא TRUE אם ההצבעה הייתה עבור ישראל.

א) (4 נקודות) תארו את מבנה הנתונים: באיזה מבנה/מבנים תשתמשו? מהו גודלו/גודלם? מהם השדות והמפתחות בהם מהי משמעותם? מומלץ לשרטט.

ב) (8 נקודות) כתבו את שגרת BUILD(S, A).
אם אתם משתמשים בשיטת החציונים יש לפרט.

ג) (5 נקודות) כתבו את שגרת COUNT(S).

ד) (8 נקודות) כתבו את שגרת COUNT(S, Time1, Time2).

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

בשאלה זו נתייחס לקטע על הישר הממשי באמצעות ההגדרות הבאות:
קטע על הישר הממשי נתון ע"י זוג נקודות-

(a, b)

a \leq b

, שהם נקודת ההתחלה והסיום שלו.
אורך של קטע:

L = b - a

הציעו מבנה

S

אשר מייצג קטעים על הישר הממשי, ושבאמצעותו ניתן לבצע את הפעולות הבאות עם זמני הריצה המצויים ליד כל שגרה.
INSERT(S, (a,b)): מכניס את הקטע

(a, b)

למבנה

S

, רק אם נקודת ההתחלה שלו

a

היא ייחודית, כלומר שונה מכל נקודת התחלה אחרת במבנה, בזמן

O (lo g n)

.
LONGEST(S, a): מחזיר את אורך הקטע (או קטעים) הארוך ביותר במבנה

S

, מבין כל הקטעים שנקודות ההתחלה שלהם גדולות או שוות ל-

a

, בזמן

O (lo g n)

.
הערה: לא ידוע אם קיים קטע עם נקודת ההתחלה המסוימת

a

.
RANGE(S, L_1, L_2): בהינתן שני מספרים שלמים

L_{1}, L_{2}

, מחזיר את מספר הקטעים באורך

L

, כך ש

L_{1} \leq L \leq L_{2}

, בזמן

O (lo g n)

.
הערה: לא ידוע אם קיימים קטעים באורך

L_{1}, L_{2}

במבנה.

א) (9 נקודות) תארו את מבנה הנתונים: באיזה מבנה/מבנים תשתמשו? מהו גודלו/גודלם? מהם השדות והמפתחות בהם ומהי משמעותם? מומלץ לשרטט.
אם אתם משתמשים בשדות הרחבה לעץ א"ש הראו את העמידה בתנאי 14.1 ע"י נוסחא.

ב) (8 נקודות) כתבו את שגרת LONGEST(S, a).

ג) (8 נקודות) כתבו את שגרת RANGE(S, L_1, L_2).

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

בשאלה זו נתייחס לקטע על הישר הממשי באמצעות ההגדרות הבאות:
קטע על הישר הממשי נתון ע"י זוג נקודות-

(a, b)

a \leq b

, שהם נקודת ההתחלה והסיום שלו.
אורך של קטע:

L = b - a

הציעו מבנה

S

(a, b)

למבנה

S

, רק אם נקודת ההתחלה שלו

a

היא ייחודית, כלומר שונה מכל נקודת התחלה אחרת במבנה, בזמן

O (lo g n)

.
LONGEST(S, a): מחזיר את אורך הקטע (או קטעים) הארוך ביותר במבנה

S

, מבין כל הקטעים שנקודות ההתחלה שלהם גדולות או שוות ל-

a

, בזמן

O (k + lo g n)

, כאשר

k

הוא מספר הקטעים שנקודות ההתחלה שלהם גדולות או שוות ל-

a

.
הערה: לא ידוע אם קיים קטע עם נקודת ההתחלה המסוימת

a

.
RANGE(S, L_1, L_2): בהינתן שני מספרים שלמים

L_{1}, L_{2}

, מחזיר את מספר הקטעים באורך

L

, כך ש

L_{1} \leq L \leq L_{2}

, בזמן

O (lo g n)

.
הערה: לא ידוע אם קיימים קטעים באורך

L_{1}, L_{2}

במבנה.

א. (9 נקודות) תארו את מבנה הנתונים: באיזה מבנה/מבנים תשתמשו? מהו גודלו/גודלם? מהם השדות והמפתחות בהם מהי משמעותם? מומלץ לשרטט.

ב. (8 נקודות) כתבו את שגרת LONGEST(S, a).

ג. (8 נקודות) כתבו את שגרת RANGE(S, L_1, L_2).

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

n

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

לפרקים האוניברסיטה מגדילה את גודל המלגה הניתנת לסטודנטים מסוימים, ע"י השגרה

I N C R E A S E - A M O U N T (s a l a r y)

להלן. נסמן את מספר ההגדלות הכולל במשתנה

m

.

הציעו מבנה נתונים

S

התומך בפעולות הבאות בזמני ריצה המצויינים:

I N S E R T (s a l a r y, am o u n t)

: הכנסת סטודנט חדש שהכנסתו החודשית היא

s a l a r y

, ושערך המלגה הנוכחית שלו היא

am o u n t

, בזמן

O (lo g n + lo g m)

I N C R E A S E - A M O U N T (s a l a r y)

: תוספת 1000 ₪ למלגת כל סטודנט שהכנסתו החודשית קטנה או שווה ל-

s a l a r y

ונמצא במבנה, בזמן

O (lo g m)

. תוכלו להניח שהשגרה

I N C R E A S E - A M O U N T

לא נקראת פעמיים עם אותו

s a l a r y

A S S E S S - A M O U N T (s a l a r y)

: החזרת המלגה הכוללת לסטודנט שהכנסתו החודשית היא

s a l a r y

, בזמן

O (lo g n + lo g m)

. תוכלו להניח שקיים במבנה סטודנט שהכנסתו החודשית היא

s a l a r y

.

א) (9 נקודות) תארו את מבנה הנתונים: באיזה מבנה/מבנים תשתמשו? מהו גודלו/גודלם? מהם השדות והמפתחות בהם מהי משמעותם? מומלץ לשרטט.
ב) (8 נקודות) כתבו את שגרת

I N S E R T (s a l a r y, am o u n t)

.
ג) (8 נקודות) כתבו את שגרת

A S S E S S - A M O U N T (s a l a r y)

.

דוגמא: שחר נמצא בתוכנית המלגות, עם הכנסה חודשית 52 ₪, ומלגה ראשונית 600 ₪.
נבצע

I N C R E A S E - A M O U N T (60)

ואז

I N C R E A S E - A M O U N T (75)

.
כעת

A S S E S S - A M O U N T (52)

יחזיר 2600 ₪ (כי הכנסתו של שחר קטנה מ-60 ₪, ומ-75 ₪).
כעת נכניס את דניאל לתוכנית. הכנסתה החודשית של דניאל היא 59 ש"ח, והמלגה הראשונית שהיא מקבלת היא 1200 ₪. כעת

A S S E S S - A M O U N T (59)

יחזיר 1200 ₪.

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

תכנון מבנה נתוניםמבני נתונים מורחביםעץ סדר סטטיסטיעצי חיפושסיבוכיות

הציעו מבנה-נתונים

S

אשר מתחזק

n

מספרים שונים זה מזה ותומך בשגרות הבאות בזמני הריצה המצוינים ליד כל שגרה:

$Build (S, A)$ : בניית המבנה $S$ מתוך מערך ממוין $A$ של $n$ מספרים ייחודיים, זמן ריצה: $O (n)$ .
$Insert (S, k)$ : הכנסת המספר השלם $k$ למבנה $S$ , זמן ריצה: $O (l g n)$ .
$Delete (S, x)$ : מחיקת האיבר אליו מצביע $x$ מהמבנה $S$ , זמן ריצה: $O (l g n)$ .
$Search (S, k)$ : חיפוש המפתח $k$ במבנה $S$ , זמן ריצה: $O (l g n)$ .
$Median (S)$ : החזרת חציון המפתחות במבנה $S$ , זמן ריצה: $O (1)$ .
$Between (S, k_{1}, k_{2})$ : החזרת כמות המפתחות במבנה $S$ המקיימים $k_{1} \leq k \leq k_{2}$ , זמן ריצה: $O (l g n)$ .

הערה: המפתחות

k_{1}, k_{2}

לאו דווקא חלק מהמבנה

S

.

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמבחן סמסטר א · 2024 · סמסטר א

★★★★★

עצי חיפושסיבוכיותערימותעץ סדר סטטיסטיסטטיסטיקות סדרסטטיסטיקת סדרחציון

תַּכְננו מבנה נתונים

S

שבאמצעותו ניתן לבצע את הפעולות הבאות בסיבוכיות זמן ריצה של

Θ (lo g n)

, כאשר

n

מציין את מספר האיברים במבנה. הניחו כי כל האיברים במבנה שונים זה מזה.

$in ser t (S, k)$ - הכנסת איבר בעל המפתח $x$ ל- $S$ .
$f in d (S, k)$ - החזרת איבר בעל המפתח $x$ ב- $S$ , אם קיים. אחרת, מחזירה $N I L$ .
$in v er s i o n s (S, k)$ - אם קיים במבנה איבר בעל המפתח $k$ , השגרה תחזיר את מספר ההיפוכים עבור $k$ .

הגדרת היפוך: כל איבר בעל מפתח

l

שהוכנס לפני

k

(כלומר לפני האיבר שערך המפתח שלו הוא

k

) והמקיים

l > k

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמבחן סמסטר א · 2019 · סמסטר א

★★★★★

עצי חיפושסיבוכיותעץ אדום-שחורעץ סדר סטטיסטי

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

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