איך לתרגל שאלות רשימות מקושרות במבני נתונים?

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

כמה שאלות רשימות מקושרות יש במבני נתונים?

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

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

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

מבני נתונים - רשימות מקושרות

מבני נתונים, אלגוריתמים וסיבוכיות

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

רמת קושי:

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

A

באורך

n

של מספרים ומספר שלם

k < n

.
פלט: האיבר המקסימלי לכל חלון, כאשר חלון הוא רצף של

k

איברים עוקבים במערך. כלומר, עבור כל אינדקס

i

מ-1 ועד

n - k + 1

עליך להחזיר את המקסימום מבין האיברים

A [i], A [i + 1], \dots, A [i + k - 1]

.

סעיף א' (10 נקודות):
הציעו אלגוריתם לפתרון בעיה בסיבוכיות זמן

O (n lo g k)

.

סעיף ב' (5 נקודות):
הוכיחו או סתרו:
יהיו

i

ו-

j

אינדקסים במערך

A

כך ש-

i < j

ומתקיים

A [i] \leq A [j]

.
אזי, לכל אינדקס

m

(המייצג את תחילת תת-המערך

A [m \dots m + k - 1]

) שעבורו

m \leq i

וגם

j \leq m + k - 1

מתקיים:

(i = m max m + k - 1 A [l]) \geq A [j] \geq A [i]

סעיף ג': (10 נקודות)
הציעו אלגוריתם לפתרון בעיה בסיבוכיות זמן

O (n)

.
רמז: חישבו על רשימה מקושרת דו כיוונית.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד ב · 2026 · סמסטר א

★★★★★

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

נתון זרם (stream) אינסופי של מספרים טבעיים מהצורה:

x_{1}, x_{2}, x_{3}, \dots

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

m

.

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

O (m)

התומך בפעולות הבאות:
א - MostFrequent()
מחזירה מספר טבעי אשר מופיע מספר הפעמים הגבוה ביותר מבין

m

האיברים האחרונים שנקלטו בזרם או לכל האיברים שנקלטו עד כה, אם טרם נקלטו

m

איברים.
זמן ריצה

O (1)

.

ב - Frequency(x)
מקבלת מספר טבעי

x

, ומחזירה את מספר הפעמים ש-

x

מופיע מבין

m

האיברים האחרונים שנקלטו בזרם.
זמן ריצה

O (lo g m)

.

סעיף א': (15 נקודות)
הציעו מבנה נתונים המשתמש במקום

O (m)

ותומך בפעולות מעלה (Frequency ו- MostFrequent) בזמנים המבוקשים.
המלצה: קראו את סעיף ב' לפני פתרון סעיף א'.

סעיף ב': (10 נקודות)
לכל קריאת תו חדש, ה-"

m

תווים האחרונים" משתנים.
הסבירו מה השינויים הדרושים במבנה נתונים שהצעתם כדי לעדכן את המבנה כדי שיהיה מוכן לענות על שאילתות של סעיף א'.
נתחו את זמן הריצה של הצעתכם.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד א · 2026 · סמסטר א

★★★★★

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

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

m

. (הנתון

m

נקבע בפעולת האתחול של המבנה).

המבנה תומך בפעולות הבאות:

● אתחול מקבוצה: מקבל פרמטר

m

וקבוצה

S \subseteq {1, ..., m}

בגודל

n

, כאשר

∣ S ∣ = n

.
זמן הריצה הדרוש -

O (n)

.

● הכנסת איבר חדש

x

בזמן

O (n lo g n)

.

● הוצאת איבר קיים

x

בזמן

O (n lo g n)

.

● חיפוש איבר

x

בזמן

O (n lo g n)

.

תארו מבנה נתונים התומך בפעולות הנדרשות.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד א · 2021 · סמסטר ב

★★★★★

רשימות מקושרותסיבוכיות זמן

ענה/י נכון/לא נכון לכל אחד מהסעיפים הבאים. מותר אך לא חובה לכתוב הסבר עד אורך של שורה לכל סעיף.
א) לכל

n

קיים עץ חיפוש בינארי של

n

איברים שגובהו

θ (n)

ב) ברשימה מקושרת באורך

n

כדאי לשמור גם מצביע לאיבר האמצעי, כי בהשקעה של

O (1)

שטח, קיבלנו אפשרות לבצע חיפוש בינארי.
ג) באלגוריתם של Boyer & Moore בהגדרה של

Δ_{2}

, נחפש לכל סיפא מופע מוקדם יותר, אך נדרוש שהאות הקודמת לסיפא תהיה שונה. אם נוריד דרישה זאת, האלגוריתם יכול לשגות.
ד) בטבלת Hash בגודל 2500 הוכנסו 1000 איברים ע"י שימוש ב־Hashing Uniform. הזמן הממוצע לחיפוש מוצלח, כאשר לכל איבר שהוכנס הסתברות שווה להופיע בחיפוש, הוא

\frac{5}{2} ln \frac{5}{3}

.
ה) נתון B-tree מדרגה

m

שמכיל

k

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

n

ואחת באורך 3 הוא

n - 2

.
ז) לכל

n \in N

קיים עץ AVL המכיל

n

קודקודים שסריקת ה־post-order שלו היא סדרה ממוינת.
ח) בכל רשימה מקושרת, קיים איבר אליו ניתן לגשת ב־

O (1)

זמן.
ט) לכל

n \in N

קיים עץ בינארי המכיל בדיוק

n

עלים ו־

2 n

קודקודים פנימיים.
י) זמן חיפוש איבר ברשימת דילוגים (skip-list) הוא

O (n)

במקרה הגרוע.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד א · 2018 · סמסטר ב

★★★★★

עץ חיפוש בינארירשימות מקושרותחיפוש בינאריאלגוריתמיםטבלאות גיבובעצי Bמיוןחסם תחתון למיוןעצי AVLעצים בינארייםסיבוכיות זמן

ענה/י נכון/לא נכון לכל אחד מהסעיפים הבאים. מוותר אך לא חובה לכתוב הסבר עד אורך של שורה לכל סעיף.
א) לכל

n

קיים עץ AVL של

n

איברים שגובהו

Θ (n)

ב) קיימת ערימת מקסימום (בינארית) בה האיבר הקודם בגודלו לאיבר הקטן ביותר אינו עלה.
ג) בכל עץ AVL החציון של קבוצת האיברים יאוחסן בשורש.
ד) באלגוריתם של Boyer & Moore בהגדרה של

Δ_{2}

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

n

איברים ל-B-tree מסדר 101 שהיה ריק בהתחלה. מספר הפיצולים הכולל בהכנסת כל האיברים חסום ע"י מספר הקדקודים בסיום התהליך.
ו) אי אפשר למצוא חציון של

n

איברים בזמן

O (n)

, כי אחרת היה אפשר למיין ע"י מציאת חציון של הקבוצה, ואח"כ של חצאי הקבוצות, רבעי הקבוצות וכו' בזמן

O (n) + O (\frac{n}{2}) + O (\frac{n}{4}) + \dots = O (n)

, בסתירה לחסם התחתון של מיון.
ז) לכל

n > 1

קיים עץ חיפוש בינארי המכיל

n

קודקודים שסריקת ה-post-order שלו היא סדרה ממוינת.
ח) בכל רשימה מקושרת, ניתן לגשת אל כל איבר ב-

O (1)

זמן.
ט) הזמן הדרוש לפעולת קידום מונה בינארי הוא

O (1)

במקרה הגרוע.
י) לכל

n > 1

קיים גרף עם

n

קדקודים שיש לו

n!

מיונים טופולוגיים שונים.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד ב · 2018 · סמסטר ב

★★★★★

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

כתוב את ה-skip list לרצף הנתונים הבא (משמאל לימין):

5, 20, 7, 6, 1

, כאשר תוצאות הטלת המטבע הן: tails, tails, tails, heads, tails, heads, tails, tails, heads, tails, tails, heads. (אנו מטילים את המטבע עד שנקבל heads ואז נוסיף לרשימה.)

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד ב · 2017 · סמסטר ב

★★★★★

רשימות מקושרותחיפושמעקב אחר אלגוריתםרשימת דילוגים

א) נתון המימוש הבא של וקטור

V

: רשימה מקושרת של האיברים ב-

V

שערכם שונה מ-

0

כאשר סדר האיברים ברשימה נקבע ע"י סדרם ב-

V

. כמו-כן לכל איבר ברשימה נשמור את מיקומו ב-

V

. נסמן ב-

s i z e (V)

את מספר האיברים ב-

V

שערכם שונה מ-

0

. הראה/י כיצד ניתן לממש מכפלה סקלרית של שני וקטורים

U

ו-

V

בזמן

O (s i z e (V) + s i z e (U) + 1)

.

ב) נאמר שמטריצה ריבועית

M

מסדר

n

היא דלילה אם רק

O (n)

מ-

n^{2}

האיברים במטריצה שונים מ-

0

. תאר/י כיצד ניתן לחשב את סכום איברי האלכסון של

M^{2}

בזמן

O (n)

.
הדרכה: ממש/י את המטריצה ע"י 2 מערכים של רשימות מקושרות אחת לשורות ואחת לעמודות של

M

, השתמש בא) והראה למה הזמן

O (n)

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד ב · 2012 · סמסטר ב

★★★★★

סיבוכיות זמןרשימות מקושרותמטריצה דלילה

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

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