איך לתרגל שאלות מעקב אחר קוד במבוא למדעי המחשב?

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

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

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

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

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

מבוא למדעי המחשב - מעקב אחר קוד

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

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

רמת קושי:

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

בסעיף זה כל המספרים מיוצגים כמחרוזת בשיטת lsbf (Least Significant Bit First) בכל הפונקציות הנתונות.

הסבר מפורט על שיטת ייצוג זו מופיע בסוף הסעיף.

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

• private static String decimalDouble(String s){…}
הפונקציה מקבלת מחרוזת המייצגת מספר בבסיס 10, מכפילה את המספר ב-2 ומחזירה מחרוזת המייצגת את התוצאה בבסיס 10.

• private static String decimalIncrement(String s){…}
הפונקציה מקבלת מחרוזת המייצגת מספר בבסיס 10, מוסיפה למספר 1 ומחזירה מחרוזת המייצגת את התוצאה בבסיס 10.

ממשו את הפונקציה public static String binaryToDecimal(String s) המקבלת מחרוזת s המייצגת מספר בבסיס 2 ומחזירה מחרוזת המייצגת את אותו מספר בבסיס 10.

דוגמאות:
• עבור הקלט "0", על הפונקציה להחזיר "0"
• עבור הקלט "11001", על הפונקציה להחזיר "19"
כיוון שהמספר העשרוני 19 ("91" כמחרוזת lsbf), מיוצג בבינארי על ידי המספר 10011 ("11001" כמחרוזת lsbf).

יש להניח כי הקלט הוא קלט תקין, כלומר מהווה מחרוזת מספרית מבסיס 2:
1. המחרוזת אינה null ואינה ריקה.
2. כל התווים במחרוזת הם ספרות חוקיות בבסיס 2 ('0' או '1').
3. התו האחרון במחרוזת אינו הספרה '0', אלא רק במקרה שיש במחרוזת ספרה אחת.

תזכורת ייצוג מספרים בשיטת Least Significant Bit First:

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

b

- התו הראשון במחרוזת מייצג כפולה של

b^{0}

, התו השני במחרוזת מייצג כפולה של

b^{1}

, התו השלישי מייצג כפולה של

b^{2}

, וכך הלאה.

לדוגמא, המחרוזת "0111" שהיא מחרוזת מספרית בבסיס 2, מייצגת את המספר 14 שכן

14 = 0 \times 2^{0} + 1 \times 2^{1} + 1 \times 2^{2} + 1 \times 2^{3}

כמו כן, המחרוזת "129" היא מחרוזת מספרית בבסיס 10 מייצגת את המספר 921.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

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

ב. (4 נק') תארו את תמונת הזכרון (מה נמצא איפה ומה הערכים) בקריאה בסוף הפונקציה funcB, לפני החזרה.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

הקוד הבא, השמור בקובץ file.c, מתקמפל ורץ ללא בעיות.

הרצנו את הפקודות הבאות ב-command line:

> gcc file.c -o tst
> ./tst Emily Daniel 100

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

II. (2 נק') האם יהיה שינוי בפלט ו/או בהתנהלות התכנית אם נשים את השורה המסומנת בחץ בפונקציה modifyRecordA בהערה? (פקודת ה-malloc). אם כן, מה השינוי. אם לא – הסבירו מדוע אין שינוי.

III. (2 נק') האם יש בתכנית, כפי שהיא מופיעה במקור (ללא שינויים), זליגות זכרון? אם כן, תארו מהן.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

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

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

Θ

כפונקציה של

n

, כאשר

n

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

n

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

שאלה 3 (25 נקודות)

תזכורת: בייצוג של גרפים בקורס זה כל קודקוד מיוצג כמספר – ומספר זה הוא השם שלו.

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

באופן פורמלי: בהינתן קודקוד

v

בגרף

G

, "מסלול שכן מינימלי מ-

v

" הוא סדרת קודקודים

⟨ v_{0}, v_{1}, v_{2}, \dots, v_{k} ⟩

כך ש:

•

v_{0}

הוא הקודקוד הראשון בסדרה (כלומר

v_{0} = v

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

v_{k}

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

v_{i}

שמספרו הוא שמי במסלול שאינו הקודקוד האחרון, הקודקוד העוקב

v_{i + 1}

הוא שכן של

v_{i}

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

דוגמאות: בהנתן הגרף

G

באיור משמאל וקודקוד

v

ב-

G

• עבור

v = 1

מסלול שכן מינימלי מ-1 יהיה:

⟨ 1, 0, 5 ⟩

• עבור

v = 2

מסלול שכן מינימלי מ-2 יהיה:

⟨ 2 ⟩

• עבור

v = 6

מסלול שכן מינימלי מ-6 יהיה:

⟨ 6, 3, 1, 0, 5 ⟩

• עבור

v = 3

הסדרה

⟨ 3, 1, 0 ⟩

אינה מסלול שכן מינימלי מ-3 כיוון שניתן להוסיף אליה את 5.
• עבור

v = 3

הסדרה

⟨ 3, 4, 1, 6 ⟩

אינה מסלול שכן מינימלי מ-3 כיוון שמבין שכניו של 1 שלא הופיעו לפניו בסדרה, 4 אינו בעל המספר הקטן ביותר.

בשאלה זו תשלימו את המחלקה GraphMinimalNeighbourPathIterator המממשת את הממשק Iterator ומייצגת איטראטור של מספרים בגרף לא מכוון

G

.

בנאי האיטרטור מקבל גרף

G

וקודקוד

v

ב-

G

. האיטרטור מחזיר בכל קריאה ל-next() את הקודקוד הבא ב-"מסלול שכן מינימלי מ-

v

".

למחלקה 3 שדות: גרף graph, מספר שלם nextVertex ושדה נוסף אותו עליכם להגדיר.

סעיף א (3 נקודות) - השלימו את בנאי המחלקה המקבל גרף graph וקודקוד vertex. יש להניח כי בגרף יש לפחות קודקוד אחד.

סעיף ב (2 נקודות) - השלימו את השיטה hasNext().

סעיף ג (15 נקודות) - השלימו את השיטה findNextVertex() המעדכנת את השדה nextVertex. קריאה לשיטה זו מתרחשת בעת קידום האיטרטור – בשיטה next().

סעיף ד (5 נקודות) - השלימו את השיטה next().

מה מייצג המשתנה?
_______________________________

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

שאלה 3 (25 נקודות)

הגדרה:
יהי

G = (V, E)

גרף לא מכוון ובו n קודקודים. בהינתן שתי קבוצות לא ריקות ומשלימות של קודקודים ב-G:

W

- תת-קבוצה של קודקודים לבנים.

B

- תת-קבוצה של קודקודים שחורים.

W \cup B = V W \cap B = \emptyset

קשת

(u, v)

תיקרא קשת לבנה-שחורה אם

u \in W, v \in B

או ההיפך:

u \in B, v \in W

.

בשאלה זו תשלימו את המחלקה GraphBlackAndWhiteEdgesIterator המממשת את הממשק Iterator<Edge> ומתארת איטרטור שעובר על כל הקשתות בגרף G שהן קשתות לבנות-שחורות (ורק עליהן). לא מוגדר סדר מסויים לפיו האיטרטור מחזיר את הקשתות.

למחלקה 3 שדות: גרף graph, מערך בוליאני whiteVertices וקשת nextEdge.

הדרכה: לרשותכם עומדת המחלקה MysteryGraph (ראו נספח) ולה בנאי מעתיק המקבל פרמטר מטיפוס Graph (ראו נספח) ויוצר גרף בעל אותו מספר קודקודים וקשתות.

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

סעיף ב (2 נקודות):
השלימו את השיטה hasNext().

סעיף ג (15 נקודות):
השלימו את השיטה findNextEdge המעדכנת את השדה nextEdge.

סעיף ד (5 נקודות):
השלימו את השיטה next().

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

N

שולחנות של 5 אנשים כל אחד. סה"כ מספר הסועדים הוא בדיוק

5 N

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

N

השולחנות. לשם כך יש להתחשב באילוצים הבאים:

כל סועד סימן מראש שלוש מנות מתוך תפריט של $K$ מנות, כאשר לכל מנה יש מספר שונה החל מ-0 ועד $K - 1$ . יש להכין לו בדיוק מנה אחת מתוך השלוש שסימן.
משיקולים קולינריים, ישנן מנות שלא יכולות להיות יחד באותו שולחן. אילוצים אלו מתוארים במטריצת אילוצים בגודל $K \times K$ , בה האיבר במקום $[i] [j]$ הוא 0 אם מנה $i$ לא יכולה להיות עם מנה $j$ באותו שולחן, ו-1 אם הן יכולות להיות יחד.

עליכם לממש את הפונקציה הבאה:

int e x am_q 4 (int ma t 1 [] [3], int ma t 2 [K] [K]);

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

ma t 1

(שורות 0 עד 4 הסועדים בשולחן הראשון, שורות 5 עד 9 הסועדים בשולחן השני, וכך הלאה), ואת מטריצת האילוצים

ma t 2

.

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

למשל, עבור 2 שולחנות ו-6 מנות, אם בחירת הסועדים היא:

ומטריצת האילוצים היא:

כלומר כל המנות יכולות להיות על אותו שולחן, מלבד מנות 0 ו-5 שלא יכולות להיות על אותו שולחן.

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

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

הטכניוןמועד א · 2025 · סמסטר קיץ

★★★★★

רקורסיהרקורסיה עם מעקבמערכיםמערך דו-ממדימעקב אחר קוד

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

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