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

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

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

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

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

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

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

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

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

רמת קושי:

בשאלה זו 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גרפיםהסתברות

I. (2 נק') נתון גרף מכוון המיוצג ברשימה המקושרת. רשימת השכנויות (adjacency list) של הגרף בעל 8 קדקודים (0 עד 7) היא:

קדקוד 3: → 1 → 6
קדקוד 1: → 0 → 2
קדקוד 4: → 5
קדקוד 6: → 4 → 7
שאר הקדקודים (0, 2, 5, 7): ללא קשתות יוצאות

ציירו את קשתות הגרף וסמנו את מספר הקדקוד (מ-0 עד 7).

II. (2 נק') ציירו את מטריצת השכנויות המתאימה לגרף הנ"ל.

III. (1 נק') בסריקה והדפסה של הגרף הנ"ל ב-DFS ב-post-order החל מקדקד 3, מה תהיה התוצאה? (רשמו משמאל לימין)

IV. (2 נק') הניחו כי התוצאה שהתקבלה בסעיף הקודם היא מספר בייצוג לפי בסיס 8. מה ייצוגו של המספר בבסיס בינארי?

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

שאלה :4 ] 25 נקודות [

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

0, 1, 2, 3, \dots, N - 1

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

N \times N

המייצגת את כל המסלולים הקיימים. אם קיים מעבר ממדינה

i

למדינה

j

אזי routes[i][j] יהיה מחיר המעבר. אם לא קיים מעבר, routes[i][j] יהיה

0

.

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

i

j

אך לא קיים מעבר מ

j

i

, או שהמחיר שונה.

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

אשר מחזירה את מחיר המסלול הזול ביותר שמקיים את כל הדרישות, ו-

0

אם לא קיים מסלול כזה.

למשל, עבור

N = 3

(3 מדינות) ומטריצת המעברים הבאה:

	$j = 0$	$j = 1$	$j = 2$
$i = 0$	0	200	300
$i = 1$	50	0	25
$i = 2$	150	0	0

יוסי יכול לטייל במסלול הבא: לצאת ממדינה 1 למדינה 2 (עולה 25) ואז ממדינה 2 למדינה 0 (עולה 150). סה"כ יוסי ישלם 175.

מסלול אחר יכול להיות ממדינה 0 למדינה 1 (עולה 200) וממדינה 1 למדינה 2 (עולה 25). סה"כ המחיר 250, יקר יותר מהאפשרות הראשונה.

קיימים עוד מסלולים, כולם יקרים יותר.

עבור 3 מדינות ומטריצת המעברים הבאה:

	$j = 0$	$j = 1$	$j = 2$
$i = 0$	0	200	0
$i = 1$	0	0	0
$i = 2$	0	100	0

אם נתחיל ממדינה 0 או מדינה 2, נוכל לעבור רק למדינה 1 וממנה אין מעבר לאף מדינה. אם נתחיל ממדינה 1 לא נוכל לעבור לאף מדינה. לכן לא קיים מסלול העובר בכל המדינות והפונקציה תחזיר 0.

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

I. (2 נק') נתון גרף המיוצג ברשימה המקושרת שבצד שמאל (6 קדקודים, 0-5). ציירו את הגרף (השלימו קדקודים והקשתות ביניהם בצד ימין).

רשימת השכנויות:

קדקוד 0: → 2 → 3
קדקוד 1: → 2
קדקוד 2: → 5 → 0 → 1
קדקוד 3: → 4 → 0 → 5
קדקוד 4: → 3 → 5
קדקוד 5: → 2 → 3 → 4

II. (2 נק') נתון עץ בינארי עם ערכים 0 ו-1:

מה תוצאת סריקת העץ הבינארי הנתון ב-DFS post order?

III. (1 נק') מה המספר (בייצוג עשרוני) שהתקבל בסעיף II? הניחו שהמספר מופיע בייצוג בינארי בשיטת המשלים ל-1 ב-8 סיביות.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

גרפיםעצים בינארייםייצוג מספרים

נתונה הפונקציה הבאה המבוססת על הפונקציה 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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

מעקב אחר קודגרפיםPageRankהסתברות

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

n

. המספרים ב- mat הם חיוביים ממש בלבד (ללא אפסים).
המסלולים בהם נעבור במערך מתחילים תמיד בתא הראשון

(0, 0)

ועד לתא האחרון שהוא התא

(ma t . l e n g t h - 1, ma t . l e n g t h - 1)

, כאשר אפשר לעבור מתא

(i, j)

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

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

דוגמאות:

נתונים המערכים הבאים:

בכל אחד מהמערכים

A

ו-

B

יש שני מסלולים מהתא הראשון לאחרון:

המסלול הראשון עובר בתאים [0][0] -> [0][1] -> [1][1]
המסלול השני עובר בתאים [0][0] -> [1][0] -> [1][1]

במערך

A

המספר המקסימלי במסלול הראשון הוא

4

, והמספר המקסימלי במסלול השני הוא

4

. לכן יוחזר

4

.
במערך

B

המספר המקסימלי במסלול הראשון הוא

3

, והמספר המקסימלי במסלול השני הוא

4

. לכן יוחזר

3

אם המערכים הם:

D =
4   5   8   2
3  12  16   7
13  1  10  14
15 11   9   6

C =
4   5   8   2
3  12   7  16
13  1  10  14
15 11   9   6

אז במערך

C

המספר שיוחזר יהיה

10

, שהוא המקסימום במסלול המסומן, והוא המינימלי מבין כל ערכי המקסימום של כל המסלולים האחרים.
אבל אם נחליף את התאים [1][3] שבו יש

16

ואת [1][2] שבו יש

7

(זה המערך

D

), המספר שיוחזר יהיה

12

, שהוא המקסימום במסלול המסומן. שימו לב ש-

12

הוא המקסימום גם במסלול הזה: [0][0] -> [0][1] -> [1][1] -> [1][2] -> [2][2] -> [2][3] -> [3][3]

אם המערכים הם:

D =
4   1   9   3  25
24 23   2  21   5
13 12  15  16  22
17 11  18  19  20
10 14   8   7   6

C =
4   1   9   3  25
24 23  22  21   5
13 12  15  16  14
17 11  18  19  20
10  2   8   7   6

אז במערך

C

המספר שיוחזר יהיה

21

, שהוא המקסימום במסלול המסומן, והוא המינימלי מבין כל ערכי המקסימום של כל המסלולים האחרים. שימו לב ש-

21

הוא המקסימום בעוד כמה מסלולים. לדוגמא:
1. [0][0] -> [0][1] -> [0][2] -> [0][3] -> [1][3] -> [3][2] -> [3][3] -> [3][4] -> [4][4]
2. [0][0] -> [0][1] -> [0][2] -> [0][3] -> [1][3] -> [3][2] -> [2][2] -> [2][3] -> [2][4] -> [3][4] -> [4][4]
אבל אם נחליף את התאים

14, 22, 2

במערך (זה המערך

D

), המספר שיוחזר יהיה

15

, שהוא המקסימום במסלול המסומן.

חתימת השיטה היא:

השיטה צריכה להיות רקורסיבית ללא שימוש בלולאות כלל. כך גם כל שיטות העזר שתכתבו (אם תכתבו) לא יכולות להכיל לולאות.

מותר לשנות את המטריצה במהלך השיטה, אבל המטריצה צריכה לחזור לקדמותה לאחר ביצוע השיטה.
המטריצה בהכרח ריבועית. כלומר, מספר השורות שווה למספר העמודות.
מותר להשתמש בשיטות Math.max ו- Math.min מהמחלקה Math וכן בקבועים Integer.MAX_VALUE, Integer.MIn_VALUE מהמחלקה Integer.
מותר להשתמש בהעמסת-יתר (Overloading).
אין צורך לדאוג ליעילות השיטה! אבל כמובן שצריך לשים לב לא לעשות קריאות רקורסיביות מיותרות!
אל תשכחו לתעד את מה שכתבתם!

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

רקורסיהרקורסיה עם מעקבמערך דו-ממדיחיפוש בינאריגרפים

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

הערים נשמרות במערך של MapItem-ים. כל איבר ב-MapItem מכיל מצביע לעיר אחת (City), כמו גם מצביע לרשימה מקושרת המכילה מידע לגבי ערים המחוברות בכביש ישיר עם העיר הנתונה, ומספר הכבישים המחוברים ישירות לעיר. מידע לגבי כביש בין העיר A לעיר B נשמר כ-ListRoad בשתי רשימות: ברשימה היוצאת מ-MapItem השומר את נתוני עיר A (ושם הכביש יופיע כיוצא מעיר A ומגיע לעיר B), וברשימה היוצאת מ-MapItem השומר על נתוני עיר B (ושם הכביש יופיע כיוצא מעיר B ומגיע לעיר A). ראו דוגמה מתחתית העמוד.

כל המידע שמור ללא בזבוז מקום כלל.

נתונות ההגדרות הבאות:

א. (2 נק') כתבו פונקציה המייצרת ומאתחלת את מפת העולם.

ב. (2 נק') כתבו פונקציה המקבלת פרטי עיר מסוימת, מייצרת עבורה אובייקט City (כולל הקצאת זכרון עבור העיר כאן בפונקציה). המקום שהוקצה עבור ה-City יוחזר דרך toCreate.

ג. (4 נק') כתבו פונקציה המקבלת פרטי עיר חדשה ואת המפה, מוסיפה את העיר לעולם ול-cityList של המפה. העיר מתווספת ללא כבישים. אם הפונקציה הצליחה, היא תחזיר את מספר הערים במפה. אם היא נכשלה (למשל, אם מבקשים להוסיף עיר שכבר קיימת), היא מחזירה -1. ניתן להניח כי myMap שונה מ-NULL.

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

ה. (6 נק') כתבו פונקציה המקבלת שם של שתי ערים ואת מפת העולם, ומוחקת את הכביש בין שתי הערים האלו. זכרו כי הכביש מופיע בשתי רשימות שונות. הפונקציה תחזיר 0 אם הצליחה, או -1 אם נכשלה.

ו. (8 נק') כתבו פונקצית מיון גנרית המקבלת מפה וממיינת את התאים ב-cityList שלה לפי אחד מהקריטריונים: שם העיר (בסדר עולה), או מס' התושבים בעיר, או מספר הכבישים המובילים אליה/ממנה. לצורך כך, יש לממש 3 פונקציות עזר (compName, compPopulation, compRoads) המתאימות להגדרה הבאה:

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

ח'. (5 נק') כתבו פונקציה המקבלת מפה נתונה, ומוחקת את כל נתוניה (כולל כבישים, ערים, וכו').

ט. (5 נק') כתבו תכנית main המקבלת דרך ה-command line שמות של ערים (ניתן להניח כי יועברו לכל הפחות 3 ערים, ואולי אף יותר). שאר הנתונים עבור כל עיר – מומצאים כרצונכם. התכנית יוצרת מפה עם כל הערים (אחת אחרי השניה), ומוסיפה כבישים באופן הבא: בין העיר הראשונה לשנייה, ובין העיר השנייה לשלישית. כלומר, סה"כ 2 כבישים. לאחר מכן התכנית ממיינת את המפה לפי שמות הערים, ולבסוף משחררת את כלל הזכרון שהוקצה (לפני היציאה מהתכנית).

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

נתונה ההרצה הבאה:

עבור כל אחת משורות הקוד הבאות, סמנו האם ערך הביטוי הוא בוודאות True, בוודאות False, או לא ניתן לקבוע בוודאות (ייתכן שהוא True וייתכן שהוא False):

1. res[1] + res[2] == 1
2. res[1] + res[2] > 0.2
3. res[4] <= res[3]
4. (res[0] == res[4]) or (res[4] == res[3])

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

מעקב אחר קודגרפיםPageRankהסתברות

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

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