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

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

איפה למצוא שאלות במבוא למדעי המחשב אוניברסיטת תל אביב?

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

כיצד ניתן להתכונן למבחן במבוא למדעי המחשב באוניברסיטת תל אביב?

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

האם יש פתרונות לשאלות מבחנים של אוניברסיטת תל אביב במבוא למדעי המחשב?

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

מבוא למדעי המחשב אוניברסיטת תל אביב

Q: האם יש מבחנים במבוא למדעי המחשב באוניברסיטת תל אביב משנים אחרונות?

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

תכנות, רקורסיה, מערכים, מחרוזות, עצים בינאריים ורשימות מקושרות

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

רמת קושי:

(שאלת בונוס המיועדת לקבוצות חרבות ברזל B/C/G בלבד, 5 נקודות)

הקיפו בעיגול את התשובה שמתארת בצורה הנכונה את ההתנהגות האסימפטוטית של הביטוי

\sum_{i = 1}^{n} 4^{i}

:

א.

Θ (4^{n})

ב.

Θ (lo g (n) \cdot 4^{n})

ג.

Θ (n \cdot 4^{n})

ד.

Θ (n^{2} \cdot 4^{n})

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

סיבוכיות זמן

בשאלה זו 4 סעיפים שאינם קשורים זה לזה.

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

א. עבור הקלט

l s t = [1, 3, 5, 5, 5, 5, 6, 7]

k ey = 5

, מה תחזיר הפונקציה?

ב. נסמן ב-

n

את אורך רשימת הקלט

l s t

. ציינו את סיבוכיות זמן הריצה במקרה הגרוע כתלות ב-

n

.

סעיף ב' (5 נק'):
נתון האל"ב

{a, b, c, d}

וכן נתונים חמישה קידודים. לכל קידוד סמנו האם הוא prefix free, uniquely decodable but not prefix free, או not uniquely decodable. סמנו ב-X את המשבצת המתאימה.

1.

a = 0, b = 00, c = 000, d = 0000

a = 00, b = 01, c = 10, d = 11

a = 00, b = 01, c = 101, d = 110

a = 10, b = 101, c = 1011, d = 11

a = 0, b = 01, c = 011, d = 0111

סעיף ג' (10 נק'):
נזכר בהגדרה של hash_mod מתוך המחלקה hashtable שראינו בכיתה:
self.hash_mod = lambda key: hash_func(key) % m

נסמן ב-

n

את כמות האיברים שמכניסים ל-hashtable, וב-

m

את גודל הטבלה. נתון כי

n = 1024 \cdot m

, ומכניסים את כל המספרים מ-1 עד

n

ל-hashtable.

עבור המימושים הבאים ל-hash_func, ציינו עבור כל מימוש האם הוא:
1. מאפשר הכנסה וחיפוש תקינים בסיבוכיות זמן ממוצעת

O (1)

(כתלות ב-

n

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

O (1)

(כתלות ב-

n

).
3. לא מאפשר הכנסה או חיפוש תקינים.

סמנו X במשבצת הנכונה. הניחו כי פעולות אריתמטיות ופונקציות מהספרייה math ו-random רצות בזמן

O (1)

. לזכירכם, הפונקציה math.log(x,b) מחזירה float המייצג (בקירוב) את הערך של

lo g_{b} (x)

lambda x: x%10
lambda x: random.randint(x)
lambda x: 1
lambda x: -1*x
lambda x: int(math.log(x,2))

סעיף ד' (5 נק'):
נתונה הפונקציה הבאה המבוססת על הפונקציה page rank אשר ראינו בכיתה, אך אינה זהה לה:

עבור כל אחת מהטענות הבאות, קבעו האם היא נכונה או לא נכונה בסוף ריצת הפונקציה:

1. עבור

G = [[1], [2], [0]]

t = 30

— הרשימה counters תכיל את אותו מספר בכל האינדקסים.
2. עבור

G = [[1], [2], [0]]

t = 35

— הרשימה counters תכיל את אותו מספר בכל האינדקסים.
3. עבור

G = [[1, 3], [2], [0], [1]]

t = 30

— הרשימה counters תכיל את אותו מספר באינדקסים

0, 1, 2

.
4. עבור

G = [[1, 2], [3], [3], [0]]

t = 30

— הרשימה counters תכיל את אותו מספר באינדקסים

0, 3

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

n o d e

בעץ נוסיף את השדה

k ey_r an g e

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

k ey_r an g e [0]

יהיה שווה למפתח המינימלי בתת העץ של הצומת ו-

k ey_r an g e [1]

יהיה שווה למפתח המקסימלי בתת העץ של הצומת.

המחלקות TreeNode ו-BinarySearchTree יכילו את השדות הבאים (השינוי מהכיתה מסומן בקו תחתון):

לדוגמה, בעץ המצורף tree מוצמדים לכמה צמתים ערכי ה-key_range התקינים שלהם. העץ מכיל: שורש 18 עם key_range

[6, 38]

, ילד שמאלי 13 עם key_range

[6, 11]

, ילד ימני 29. תת-העץ השמאלי של 13: צומת 11, וילד שמאלי שלו 6. תת-העץ של 29: ילד שמאלי 24 (עם ילדים 19, 25), ילד ימני 38. לצומת 25 key_range

[25, 25]

.

הקוד הבא, בהינתן העץ tree מהדוגמה, ידפיס את הטווח עבור הבן הימני של השורש:
>>> print(tree.root.right.key_range) → (19, 38)

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

[N o n e, N o n e]

.

א. (6 נק') השלימו את מימוש המתודה update_key_range() למחלקה TreeNode, שתעדכן את השדה key_range של הצומת לערכיו התקינים לפי ההגדרה שצוינה.
הנחיה: על המימוש להיות יעיל ככל שניתן מבחינת סיבוכיות זמן אסימפטוטית כתלות בעומק העץ.

ב. (7 נק') כעת, נרצה להוסיף למחלקה BinarySearchTree את המתודה update_all_key_range(self) אשר מעדכנת את טווחי המפתחות בכל הצמתים בעץ, תוך שימוש במתודה שמומשה בסעיף א'. הקוד הבא מציע מימוש:

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

n

).
בנוסף, ציינו האם הקוד נכון, ואם אינו נכון הציעו תיקון (בקצרה).

ג. (5 נק') ממשו מחדש את המתודה update_key_range של המחלקה TreeNode. השם של המימוש החדש יהיה update_key_range_2.
הנחה שתקפה לסעיף זה בלבד: הילדים הישירים של הצומת אותו מעדכנים, כבר מכילים ערכים תקינים בשדה key_range.
הנחיה: על המימוש להיות יעיל ככל שניתן מבחינת סיבוכיות זמן אסימפטוטית כתלות במספר הצמתים בעץ.

ד. (7 נק') כעת נשנה את הקוד של update_all_key_range, אך ורק על ידי החלפת הקריאה ל-update_key_range בקריאה ל-update_key_range_2.

ציינו מה סיבוכיות זמן הריצה של המתודה המעודכנת update_all_key_range במקרה הגרוע כתלות בכמות הצמתים (

n

). בנוסף, ציינו האם הקוד נכון, ואם אינו נכון הציעו תיקון (בקצרה).

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

[m, k]

, כאשר

m

הוא ההיסט לאחור ו-

k

מייצג את אורך החזרה.

המחרוזת הנדחסת היא רצף של תווים, כאשר כל תו מיוצג ב-7 ביטים (קוד ASCII ועוד ביט מפריד). נכניס את השינוי הבא: בעת חיפוש חזרות בטקסט נאפשר גם חיפוש חזרות "לאחור". כלומר, בדומה לפונקציה maxmatch מהכיתה שמחפשת חזרה "קדימה" (התאמה), כעת יש גם הפונקציה maxmatch_back שמחפשת חזרה "אחורה".

הוסיפו עוד ביט לקידוד: במקום

[m, k]

, החזרה תהיה

[m, k, b]

, כאשר

b = 0

עבור חזרה רגילה ו-

b = 1

עבור חזרה לאחור. ערכי ברירת המחדל:

W = 2^{12} - 1

L = 2^{5} - 1

. באלגוריתם הישן חזרה דרשה

1 + 12 + 5 = 18

ביטים, ובחדש

2 + 12 + 5 = 19

ביטים.

סעיף א' (10 נק'):

א. מהו אורך חזרה מינימלי שמשתלם לדחוס?

ב. נסמן ב-

n

את אורך המחרוזות. נתונות 3 מחרוזות בייצוג כדלהלן:
1. את המחרוזת "abcdeabcde" נדחוס בייצוג הביניים

[^{'} a^{'},^{'} b^{'},^{'} c^{'},^{'} d^{'},^{'} e^{'}, [5, 5, 0]]

.
2. את המחרוזת "abcdeedcba" נדחוס בייצוג הביניים

[^{'} a^{'},^{'} b^{'},^{'} c^{'},^{'} d^{'},^{'} e^{'}, [1, 5, 1]]

.
3. את המחרוזת "aaaalxbxaaaa" נדחוס בייצוג הביניים שהאלגוריתם החדש יייצר.

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

"aaaa"
"abccba"

סעיף ב' (10 נק'):
עליכם להשלים את מימוש הפונקציה LZW_compress_new בשורות הריקות בהתאם לשינוי המתואר בשאלה. הניחו שמומשה לכם הפונקציה:
maxmatch_back(text, p, W=2**12-1, L=2**5-1)
שמחפשת חזרות "לאחור". בדומה ל-maxmatch, מקבלת אותם פרמטרים ומחזירה זוג

[m, k]

המקיים

t e x t [p : p + k] = t e x t [p - m : p - m + k : - 1]

כאשר

k

מקסימלי.

לנוחותכם, מצורף המימוש המקורי של הפונקציה LZW_compress שראינו בכיתה:

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

קידודמחרוזותמעקב אחר קודסיבוכיות זמן

בהינתן מחרוזת

s t = s_{0} s_{1} \dots s_{n - 1}

בעלת

n

תווים, תת מחרוזת של

s t

מוגדרת להיות מילה

w = s_{i_{1}} s_{i_{2}} \dots s_{i_{k}}

כך ש-

0 \leq i_{1} < i_{2} < \dots < i_{k} \leq n - 1

.

לדוגמה, קבוצת תתי המחרוזות של המחרוזת

ab c

היא:

{ϵ, a, b, c, ab, a c, b c, ab c}

, וקבוצת תתי המחרוזות של המחרוזת

aa

היא

{ϵ, a, aa}

, כאשר הסימון

ϵ

מייצג את המחרוזת הריקה, שהיא תת מחרוזת חוקית של כל מחרוזת (המחרוזת הריקה היא תת מחרוזת חוקית גם של המחרוזת הריקה).

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

s t = ab c d

המילה

a c

היא תת מחרוזת של

s t

, אבל

c a

היא לא תת מחרוזת של

s t

.

בשאלה זו נפתור את בעיית תת המחרוזת המשותפת הארוכה ביותר (Longest Common Subsequence, LCS). בבעיה זו נתונות שתי מחרוזות

s t_{1}, s t_{2}

ועלינו למצוא את האורך המקסימלי של מילה

w

אשר מהווה תת מחרוזת גם של

s t_{1}

וגם של

s t_{2}

.

דוגמאות:

$L C S (b x c g, ab c d e f g) = 3$ (כאן המחרוזת המשותפת הארוכה ביותר היא $b c g$ ואורכה 3).
$L C S (aaa, aba) = 2$ (כאן המחרוזת המשותפת הארוכה ביותר היא $aa$ ואורכה 2).
$L C S (a x, x a) = 1$ (כאן מחרוזת משותפת ארוכה ביותר היא למשל $a$ ואורכה 1).
$L C S (bina r y, co m p u t er) = 1$ (כאן המחרוזת המשותפת הארוכה ביותר היא $r$ ואורכה 1).
$L C S (aaaa, x y z) = 0$ (כאן המחרוזת המשותפת הארוכה ביותר היא המחרוזת הריקה ואורכה 0).

לאורך השאלה ניתן להניח כי שני הקלטים

s t_{1}, s t_{2}

לפונקציה הם משתנים חוקיים מטיפוס str (ייתכן כי מדובר במחרוזת ריקה).

א. (10 נק') נתון פתרון רקורסיבי לבעיית LCS. השלימו את הקוד המטפל במקרי הקצה ובמקרה הכללי בשורות החסרות.
הנחיה: אסור להשתמש ב-slicing.

ב. (10 נק') נסמן

m = l e n (s t_{1})

n = l e n (s t_{2})

ונניח לצורך פשטות כי

m = n

. נסמן ב-

S (n)

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

l cs_r ec

.

(i) הקיפו בעיגול את התשובה המתארת את גודל עץ הרקורסיה במקרה הטוב ביותר עבור האלגוריתם שהוצג בסעיף א' כתלות ב-

n

.

האפשרויות:

S (n) = O (1)

S (n) = Θ (lo g n)

S (n) = Θ (n)

S (n) = Θ (n lo g n)

S (n) = Θ (n^{2})

S (n) = Θ (n^{c})

עבור קבוע

c \geq 3

כלשהו,

c_{1} \cdot 2^{n} \leq S (n) \leq c_{2} \cdot 4^{n}

עבור קבועים

c_{1}, c_{2}

חיוביים כלשהם,

S (n) = Θ (n!)

.

(ii) הקיפו בעיגול את התשובה המתארת את גודל עץ הרקורסיה במקרה הגרוע ביותר עבור האלגוריתם שהוצג בסעיף א' כתלות ב-

n

.

ג. (5 נק') בסעיף זה נוסיף ממואיזציה למימוש הרקורסיבי משעיף א'. השלימו את הקוד של הפונקציה

l cs_m e m

למטה. הפונקציה מקבלת מחרוזת

s t

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

ד. (5 נק') נאמר שמחרוזת

s t

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

a ez

היא מונוטונית עולה, גם

aabb c

היא מונוטונית עולה, אבל

a d x c

היא לא מונוטונית עולה (מכיוון ש-

c

קטן למשל מ-

d

אבל מופיע אחריו).

השלימו את הקוד של הפונקציה longest_monotone למטה. הפונקציה מקבלת מחרוזת

s t

המורכבת מאותיות קטנות באנגלית ('a','b','c',...,'z'), ומחזירה את האורך המקסימלי של תת מחרוזת מונוטונית עולה של

s t

. דוגמאות:

$l o n g es t_m o n o t o n e (a x b y cz d) = 4$ (המחרוזת המונוטונית עולה הארוכה ביותר היא $ab c d$ ).
$l o n g es t_m o n o t o n e (aabaa) = 4$ (המחרוזת המונוטונית עולה הארוכה ביותר היא $aaaa$ ).
$l o n g es t_m o n o t o n e (x a) = 1$ (מחרוזת מונוטונית עולה ארוכה ביותר היא למשל $a$ ).

הנחיות: (1) על הפונקציה להשתמש בפונקציה

l cs_m e m

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

רקורסיהמחרוזותתת-סדרהסיבוכיות זמןmemoization

נתון דקדוק חסר-הקשר הבא, כאשר

S

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

ϵ

המחרוזת הריקה.

תזכורת: כלל גרירה מהצורה

X \to Y ∣ Z

משמעו שניתן לגזור מ-

X

את המשתנים

Y

או

Z

S \to A B S ∣ c C ∣ c

A \to a A ∣ a

B \to b B ∣ b

C \to c C ∣ c

הקיפו, לכל אחת מהמחרוזות הבאות, האם ניתן לגזור אותה מהדקדוק הנתון או לא:

1.

ϵ

aaabbb c

ab

abaabb cc

ab c aabb cc

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד א · 2025 · סמסטר ב

★★★★★

דקדוק חסר-הקשר

בכיתה ראינו מימוש של hash table (המשתמש ב-chaining לטיפול בהתנגשויות) אשר בממוצע מספקת זמן ריצה קבוע עבור הכנסה ושליפה. הבעיה הייתה במקרה הגרוע. נסמן ב-

n

כמות האיברים בהם נדרשים לטפל,

m

כמות התאים במילון. נניח כי

m = n

.

א. מה סיבוכיות זמן השליפה במקרה הגרוע?

ב. מה סיבוכיות זמן ההכנסה במקרה הגרוע?

דרור הציע להחליף את הרשימות בכל תא, בעצים בינאריים מאוזנים (הניחו כי אנחנו יודעים לשמור את העצים מאוזנים).

תזכורת: נקרא לעץ בינארי "מאוזן" אם מתקיים שעומקו לוגריתמי בכמות הצמתים שלו.

ג. מה תהיה כעת סיבוכיות זמן השליפה הממוצעת?

ד. מה תהיה סיבוכיות זמן השליפה במקרה הגרוע?

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד א · 2025 · סמסטר ב

★★★★★

טבלאות גיבובסיבוכיות זמןעצים בינאריים

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

1.

1^{2} + 2^{2} + 3^{2} + \dots + n^{2} = O (n^{3.5})

9^{n l o g_{3} n} = Θ (n^{2 n})

n^{l o g_{2} n} = O (n^{l o g_{3} n})

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד א · 2025 · סמסטר ב

★★★★★

סיבוכיות זמן

הקיפו את התשובה הנכונה ביותר מבין האופציות הבאות, עבור מה שיודפס בהרצת הקוד משמאל:

אפשרויות:

1. יודפס False, ולאחר מכן יודפס True.
2. יודפס True, ולאחר מכן יודפס True.
3. יודפס False ולאחר מכן תזרק שגיאה.
4. יודפס True ולאחר מכן תזרק שגיאה.
5. תוחזר שגיאה לפני שיודפס ערך כלשהו.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד א · 2025 · סמסטר ב

★★★★★

מעקב אחר קודמערכים

נתונים שני מימושים לפונקציות מיון המבוססים על selection-sort. לנוחיותכם, מסומן ההבדל ביניהם.

השלימו בטבלה את סיבוכיות זמן הריצה האסימפטוטית במקרה הנתון (במונחי

O (\cdot)

), כפונקציה של

n

, במקרים הבאים:

1.

l s t = [i for i in range (n)]

l s t = [(i mod 100) for i in range (n)]

l s t = [(i mod int (n^{0.5})) for i in range (n)]

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד א · 2025 · סמסטר ב

★★★★★

מיוןסיבוכיות זמןמעקב אחר קוד

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

מאגר מבחנים במבוא למדעי המחשב מאוניברסיטת תל אביב (תל אביב) - 969 שאלות ממוינות לפי נושא ורמת קושי, עם פתרונות מלאים לבדיקה עצמית. השאלות מכסות מועדים לאורך השנים, כולל מבחנים מ-2023, 2024, 2025 ו-2026. נושאים מרכזיים: רקורסיה, מערכים, מחרוזות, יעילות, עצים בינאריים. ניתן לסנן שאלות חוזרות, להתאמן על נושא ספציפי או להריץ סימולציית מבחן לפני הבחינה. הכנה למבוא למדעי המחשב מתמקדת בתרגול רקורסיה, מערכים ועצים בינאריים - הנושאים הנפוצים ביותר במבחנים. לימוד עצמי עם שאלות ממבחנים, בדגש על מעקב אחר קוד, מכין ביעילות לבחינה.