איך לתרגל שאלות סיבוכיות זמן במבוא למדעי המחשב?

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

כמה שאלות סיבוכיות זמן יש במבוא למדעי המחשב?

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

מה חשוב לדעת על סיבוכיות זמן לקראת מבחן במבוא למדעי המחשב?

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

מבוא למדעי המחשב - סיבוכיות זמן

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

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

תתי-נושאים של יעילות

רמת קושי:

(שאלת בונוס המיועדת לקבוצות חרבות ברזל 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גרפיםהסתברות

רשמו את הפונקציה

f (n)

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

Θ

) שלה?

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

מה הסיבוכיות ב-

Θ

של הנוסחה הבאה:

T (n, m) = \frac{T ( n - 1 , m )}{2} + nm

כאשר

T (1, m) = 1

, כפונקציה של

n, m

כאשר

m > 0

.

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

שאלה 2 - סעיף ב (15 נקודות)

בשאלה זו נעסוק בעצים בינאריים של מספרים אי-שליליים. נתונות שתי המחלקות IntegerBinaryTree, IntegerBinaryNode, המחלקות את המרחיבות BinaryTree<Integer>, BinaryNode<Integer> בהתאמה.

השלימו במחלקה IntegerBinaryTree את השיטה הבוליאנית pathSum(int sum) אשר מקבלת מספר שלם sum ומחזירה ערך true אם קיים מסלול כלשהו בעץ מהשורש לעלה אשר סכום המספרים בקודקודי המסלול הוא בדיוק sum. אם לא קיים מסלול כזה השיטה מחזירה ערך false (5 נקודות).

לצורך משימה זו עליכם גם להשלים שיטה בעלת שם זהה במחלקה IntegerBinaryNode (10 נקודות).

דוגמאות:
בעץ המספרים הבא המכיל מספרים:

• קריאה לשיטה עם הערך 12 תחזיר true (כי

5 + 1 + 6 = 12

).
• קריאה לשיטה עם הערך 14 תחזיר false.
• קריאה לשיטה עם הערך 5 תחזיר false.

הערה: בעץ ריק לא קיים מסלול משורש לעלה ולכן השיטה מחזירה false.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

שאלה 4 - סעיף ב' (10 נקודות)

השלימו את הגדרת הפונקציה difference המקבלת מערך ממוין של מספרים array ומספר חיובי נוסף diff. אם קיימים שני מספרים שונים במערך שההפרש בינהם שווה ל-diff הפונקציה מחזירה ערך true, אחרת היא מחזירה ערך false.

הניחו כי אורך המערך גדול או שווה ל-2. המערך ממוין בסדר לא יורד.

דוגמאות:

עבור המערך

array = {1, 3, 6, 10}

ומספר

diff = 4

, הפונקציה תחזיר ערך true.

עבור המערך

array = {1, 3, 6, 10}

ומספר

diff = 8

, הפונקציה תחזיר ערך false.

שימו לב: יש לשים דגש רב על יעילות הפתרון. פתרון נכון ולא יעיל יקבל 3 נקודות לכל היותר.

הנחיית חובה עבור סעיף זה: אין לשנות את ערכי המערך array או להגדיר (או ליצור) משתנים מורכבים (כגון מערך וכדומה).

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

מערכיםיעילותסיבוכיות זמןחיפושלולאות

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

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 · סמסטר א

★★★★★

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

התכנית הבאה מתקמפלת ורצה.

I. (4 נק') מה פלט התכנית?

II. (4 נק') מה סיבוכיות f ב-

Θ

כפונקציה של

n

, כאשר

n

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

n

הוא חזקה של 2). הציגו את הנוסחה, הראו את דרך הפתרון ואת התוצאה הסופית.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

שאלה 4 - סעיף ב (10 נקודות)

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

הגדרה: הזזה מעגלית של מערך ב-

x

מקומות היא סידור של אברי המערך כך שכל איבר במערך זז

x

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

0 \leq i < n

האיבר בתא

i

עובר לתא

(i + x) % n

. כאשר

n

הוא אורך המערך.

דוגמאות להגדרה: המערכים הבאים עברו הזזה מעגלית ב-

•

x = 0

מקומות: array1 = {1, 3, 6, 7, 8, 10}
•

x = 2

מקומות: array2 = {8, 10, 1, 3, 6, 7}
•

x = 5

מקומות: array3 = {3, 6, 7, 8, 10, 1}

השלימו את הפונקציה findMinIndex(int[] array) המקבלת מערך לא ריק וממויין בעל איברים יחודיים שעבר הזזה מעגלית ומחזירה את האינדקס של האיבר הקטן ביותר במערך.

דוגמאות:
• עבור המערך array1 הפונקציה תחזיר את הערך 0.
• עבור המערך array2 הפונקציה תחזיר את הערך 2.
• עבור המערך array3 הפונקציה תחזיר את הערך 5.

הנחיות:
• אלגוריתם שיבצע מספר ליניארי של פעולות (בדומה לאלגוריתם חיפוש ליניארי) יקבל 5 נקודות לכל היותר.
• בשאלה זו ניתן (אך בהחלט לא חובה) להשתמש בפונקצית עזר אחת. מי שבוחר להשתמש בפונקצית עזר רשאי להגדיר פונקצית עזר אחת כרצונו.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בן גוריוןמועד ב · 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 · סמסטר א

★★★★★

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

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

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