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

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

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

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

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

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

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

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

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

תתי-נושאים של תכנות מונחה עצמים

רמת קושי:

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

נתון הממשק Filter<T> המכיל שיטה בוליאנית accept(T element) המחזירה ערך true אם"ם האיבר element מתקבל על ידי הפילטר.

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

ניתן להניח כי הארגומנטים אינם null, העצם someFilters מכיל לפחות איבר אחד והעצם someElements מכיל לפחות איבר אחד.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

לולאותתנאיםתכנות מונחה עצמיםשיטות סטטיותגנרטורים

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

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

הפונקציה מקבלת מערך

arr

באורך

n

של מספרים שלמים ללא חזרות, תו סידור

c

ומספר

x

. עליכם למצוא האם התו

c

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

- 1

.

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

c

התו $c$	סידור המערך
$^{'} u^{'}$	המערך ממוין בסדר עולה
$^{'} d^{'}$	המערך ממוין בסדר יורד

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

לפונקציה

exam_q2

אסור להשתמש במשתנה

c

פרט להעברתו כפרמטר ל- compare. אסור להגדיר פונקציות עזר נוספות.

דוגמאות:

תוכן המערך	$c$	$x$	ערך החזרה
1, 2, 3, 4, 5	$^{'} u^{'}$	3	2
10, 5, 2, -1, -3	$^{'} d^{'}$	7	-1
12, 0, -2	$^{'} d^{'}$	0	1

הערות:

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

דרישות סיבוכיות:

סיבוכיות זמן עבור הפונקציה compare: $Θ (1)$ .
סיבוכיות זמן כוללת: $O (lo g (n))$ .
סיבוכיות מקום נוסף: $O (1)$ .

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

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

הפונקציה מקבלת מערך של ספרים שלמים בעלות הסדר עולה arr בדוגל

n

, ושלוש ספרים שלמים a,b,c. הפונקציה משמממת היצקנופה ממשהם סטופורצית רבעית על כל רביא בעלות arr ויתל בדוגל הנוסחא:

a \cdot a r r [i]^{2} + b \cdot a r r [i] + c

ניתן לשמר על המערך על ידי כך שהפונקציה שתתיה בעלות הסדר עולה.

זמר: לפונקציה ריבועית בעלות נקודה של קיצון אקסטרימום -

- \frac{b}{2 a}

, כאשר

a \neq = 0

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

דרישות (שימו לב לתרחישים האפשריים):

קלט	תוכן משרך בדיוקנו	הסבר
`arr = [-4, -2, 2, 4]`, `a=1, b=3, c=5`	`[3, 9, 15, 33]`	לאחר שינוי לכל רביא בעלות המערך: $a r r [0] = 1 \cdot (- 4)^{2} - 4 \cdot 3 + 5 = 9$ , $a r r [1] = 1 \cdot (- 2)^{2} - 2 \cdot 3 + 5 = 3$ , $a r r [2] = 1 \cdot 2^{2} + 2 \cdot 3 + 5 = 15$ , $a r r [3] = 1 \cdot 4^{2} + 4 \cdot 3 + 5 = 33$ , וגם המערך בדיוקנו בעלות תוכן הינו: `arr=[3, 9, 15, 33]`
`arr = [-2, -1, 0, 1, 2]`, `a=0, b=2, c=1`	`[-3, -1, 1, 3, 5]`	לאחר שינוי לכל רביא בעלות המערך: $a r r [0] = - 2 \cdot 2 + 1 = - 3$ , $a r r [1] = - 1 \cdot 2 + 1 = - 1$ , $a r r [2] = 0 \cdot 2 + 1 = 1$ , $a r r [3] = 1 \cdot 2 + 1 = 3$ , $a r r [4] = 2 \cdot 2 + 1 = 5$ , וגם המערך בדיוקנו בעלות תוכן הינו: `arr=[-3, -1, 1, 3, 5]`

תורעה:

• נתונה לך קוראת שחובך משחמשם את המערך, אוכן, הסור ושלוש הספרים a,b,c. הפונקציה מדספיא נתונים בעלות arr משרך בדיוקנו exam_q3 בעלות עוצוב בעלות מממן.

• ניתן להניח כי טלקהש ניתן כי

0 \leq a

.

• ניתן להניח לך שלטחן אל יירומ ל-overflow בשמתשמן במשנים בעלות int בדוגל.

דרישות סיבוכיות:

• סיבוכיות זמן:

Θ (n)

.
• סיבוכיות מקום:

Θ (n)

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

מערכיםלולאותסיבוכיות זמןסיבוכיות מקוםשיטות סטטיות

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

אם למדת את הקורס בסמסטר 2024א או 2024ב – חובה עליך לענות על שאלה מס' 5
אם למדת את הקורס בסמסטר 2025א או לפני 2024א – חובה עליך לענות על שאלה מס' 6

שאלה 5 (18 נקודות) – רק למי שלמד/ה את הקורס בסמסטר 2024א/ב
במחלקה Q5 נתונה השיטה הסטטית secret הבאה, המקבלת כפרמטרים מערך חד-ממדי a המלא במספרים שלמים, ושני מספרים שלמים

x

ו-

y

.

נתון המערך a:
0 1 2 3 4 5 6 7 8 9
1 3 5 4 8 2 4 3 6 5

ענו על הסעיפים הבאים:
סעיף א (2 נקודות):
מה תחזיר השיטה secret בעקבות הקריאה secret(a, 6, 2)?

סעיף ב (2 נקודות):
מה תחזיר השיטה secret בעקבות הקריאה secret(a, 2, 6)?

סעיף ג (2 נקודות):
האם יש זוג פרמטרים

x

ו-

y

כך שאם נפעיל את השיטה secret עם הפרמטרים a (המערך לעיל),

x

ו-

y

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

סעיף ד (2 נקודות):
האם יש זוג פרמטרים

x

ו-

y

כך שאם נפעיל את השיטה secret עם הפרמטרים a (המערך לעיל),

x

ו-

y

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

סעיף ה (3 נקודות):
האם יש זוג פרמטרים

x

ו-

y

כך שאם נפעיל את השיטה secret עם הפרמטרים a (המערך לעיל),

x

ו-

y

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

סעיף ו (3 נקודות)
השיטה secret שונתה קצת, והיא נקראת secret1. כל השינויים מודגשים בתוך הקוד להלן:

מה תחזיר השיטה secret1 בעקבות הקריאה secret1(a, 1, 6)?

סעיף ז (4 נקודות)
מה מבצעת השיטה secret באופן כללי, כאשר היא מקבלת כפרמטרים מערך חד-ממדי a מלא במספרים שלמים, ושני מספרים שלמים

x

ו-

y

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

כל מספר טבעי (שלם חיובי)

n u m

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

f a c t or

כלשהו, כאשר כל חזקה מופיעה פעם אחת לכל היותר.

דוגמאות:

את המספר $9 = n u m$ אפשר להציג כך:

2^{0} + 2^{3} = 1 + 8 = 9 f a c t or = 2

וגם כך

3^{2} = 9 f a c t or = 3

את המספר $19 = n u m$ אפשר להציג כך:

2^{0} + 2^{1} + 2^{4} = 1 + 2 + 16 = 19 f a c t or = 2

את המספר $28 = n u m$ אפשר להציג כך:

2^{2} + 2^{3} + 2^{4} = 4 + 8 + 16 = 28 f a c t or = 2

3^{0} + 3^{3} = 1 + 27 = 28 f a c t or = 3

את המספר $42 = n u m$ אפשר להציג כך:

2^{1} + 2^{3} + 2^{5} = 2 + 8 + 32 = 42 f a c t or = 2

וגם כך

6^{1} + 6^{2} = 6 + 36 = 42 f a c t or = 6

את המספר $73 = n u m$ אפשר להציג כך:

2^{0} + 2^{3} + 2^{6} = 1 + 8 + 64 = 73 f a c t or = 2

וגם כך

8^{0} + 8^{1} + 8^{2} = 1 + 8 + 64 = 73 f a c t or = 8

את המספר $273 = n u m$ אפשר להציג כך:

2^{0} + 2^{4} + 2^{8} = 1 + 16 + 256 = 273 f a c t or = 2

וגם כך

4^{0} + 4^{2} + 4^{4} = 1 + 16 + 256 = 273 f a c t or = 4

וגם כך

1 6^{0} + 1 6^{1} + 1 6^{2} = 1 + 16 + 256 = 273 f a c t or = 16

שימו לב –
ברור שאפשר להציג כל מספר

a

כחזקה 1 של המספר

a

(כלומר

a^{1}

), וגם כך:

(a - 1)^{0} + (a - 1)^{1}

.
לדוגמא, את המספר 7 אפשר להציג כך:

1 + 6 = 6^{0} + 6^{1} = 7

. אנחנו לא מתכוונים לסכום הזה! את המספר 7 אנחנו רוצים להציג כך:

1 + 2 + 4 = 2^{0} + 2^{1} + 2^{2} = 7

כתבו שיטה סטטית רקורסיבית המקבלת כפרמטר מספר שלם חיובי

n u m

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

f a c t or

הגדול ביותר מבין המספרים 2 ל-

n u m - 2

כך שאפשר לקבל את

n u m

כסכום חזקות של

f a c t or

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

f a c t or

שסכומן הוא

n u m

. ראו דוגמא בהמשך.

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

בדוגמאות לעיל,

אם $n u m = 9$ – המספר שיוחזר יהיה 3 (כי הוא הגדול מבין 2, 3), ויודפס: 9
אם $n u m = 73$ – המספר שיוחזר יהיה 8 (כי הוא הגדול מבין 2, 8), ויודפס: 1 8 64
אם $n u m = 273$ – המספר שיוחזר יהיה 16 (כי הוא הגדול מבין 2, 4, 16), ויודפס: 1 16 256
אם $n u m = 3$ – המספר שיוחזר יהיה 0 (כי אין $f a c t or$ אפשרי) ולא יודפס כלום.

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

(n - 1)^{1} + (n - 1)^{0}

(כפי שהסברנו לעיל).

הדרכה: (אין חובה להשתמש בה)
כדאי לכתוב שיטת עזר (רקורסיבית כמובן) שמקבלת את

n u m

ומספר נוסף

f a c t or

, ובודקת אם אפשר להציג את

n u m

כסכום חזקות של

f a c t or

.

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

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

רקורסיהשיטות סטטיותOverloadingמעקב אחר קודייצוג מספרים

נניח שהמחלקה Node שלהלן מממשת צומת בעץ בינרי.

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

נתון העץ הבינרי הבא, ששורשו הוא root:

        8
       / \
     11    6
    / \     \
   4   2    13
  /   / \
 10  3   25
     |
    19

ענו על הסעיפים הבאים:
סעיף א (1 נקודות):
מה תחזיר השיטה find1 בעקבות הקריאה BinaryTree.find1(root, 10)?

סעיף ב (3 נקודות):
מה מבצעת השיטה (הציבורית) find1 באופן כללי כשהיא מקבלת כפרמטרים: שורש של עץ בינרי root, שכל הערכים בצמתיו שונים זה מזה, ומספר שלם num כלשהו? שימו לב, עליכם לתת תיאור ממצה של מה עושה השיטה באופן כללי, ולא תיאור של מה עושה כל שורה בשיטה, או איך היא מבצעת זאת. כלומר, לכתוב בקצרה מה משמעות הערך שהשיטה מחזירה. התייחסו למקרי קצה.

סעיף ג (2 נקודות):
מה תחזיר השיטה find2 בעקבות הקריאה BinaryTree.find2(root, 3, 2)?

סעיף ד (4 נקודות):
מה מבצעת השיטה find2 באופן כללי כשהיא מקבלת כפרמטרים: שורש של עץ בינרי root, שכל הערכים בצמתיו שונים זה מזה, ושני מספרים שלמים

x

ו-

y

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

סעיף ה (2 נקודות):
מה תחזיר השיטה find3 בעקבות הקריאה BinaryTree.find3(root, 3, 13)?

סעיף ו (4 נקודות):
מה מבצעת השיטה find3 באופן כללי כשהיא מקבלת כפרמטרים: שורש של עץ בינרי root, שכל הערכים בצמתיו שונים זה מזה, ושני מספרים שלמים

x

ו-

y

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

הגדרה: נאמר שהמספר השלם

a

מחלק את המספר השלם

b

, אם כשמחלקים את

b

ב-

a

אין שארית. כלומר,

b % a == 0

. (לדוגמא, 3 מחלק את 12, 7 מחלק את 21 וכד').
כאשר אחד מהמספרים (או שניהם) שליליים, אנחנו אומרים ש-

a

הוא מחלק של

b

אם הערך המוחלט של

a

הוא מחלק של הערך המוחלט של

b

. (לדוגמא, המספר -4 מחלק את 20, וגם את -20, וכן 5 מחלק את 15 וגם את -15).

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

דוגמאות:

אם המערך הוא ${60, - 100, 10, 5, - 20, 25}$

השיטה צריכה להחזיר את הערך 5 כי הוא מחלק את כל שאר האיברים במערך.

אם המערך הוא ${- 100, - 10, 30, 3, 5, - 20, 25}$

השיטה צריכה להחזיר את הערך -1 כי אין במערך אף איבר שמחלק את כל שאר האיברים שבמערך.

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

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

מערכיםלולאותסיבוכיות זמןסיבוכיות מקוםיעילותשיטות סטטיות

במחלקה Q5 נתונה השיטה הסטטית secret הבאה, המקבלת כפרמטרים מערך חד-ממדי a המלא במספרים שלמים 1 ו- 0 בלבד, ומספר שלם אי-שלילי k.

נתון המערך a הבא:
[1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0] במקומות 0 עד 11.

ענו על הסעיפים הבאים:
סעיף א (3 נקודות):
מה תחזיר השיטה secret בעקבות הקריאה secret(a, 0)? נמקו את תשובתכם.

סעיף ב (3 נקודות):
עבור איזה תחום ערכים של

k

, הקריאה secret(a, k) תחזיר את הערך הכי גדול (מתוך כל הערכים שיוחזרו מקריאה לשיטה עם כל ערכי ה-

k

האפשריים)? נמקו את תשובתכם.

סעיף ג (3 נקודות):
מלאו את המערך להלן בערכים כך שלכל

k

בין 0 ל- 9, הערך שיוחזר מהקריאה לשיטה secret(a, k) יהיה שווה ל-

k

.
אם זה לא יתכן, נמקו מדוע.
[מערך באורך 10 מקומות ריקים]

סעיף ד (3 נקודות):
מלאו את המערך להלן בערכים כך שלכל

k

בין 0 ל- 9, הערך שיוחזר מהקריאה לשיטה secret(a, k) יהיה זהה.
אם זה לא יתכן, נמקו מדוע.
[מערך באורך 10 מקומות ריקים]

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

k

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

הגדרה: נאמר שהמספר השלם

a

מחלק את המספר השלם

b

, אם כשמחלקים את

b

ב-

a

אין שארית. כלומר,

b % a == 0

. (לדוגמא, 3 מחלק את 12, 7 מחלק את 21 וכד').

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

2 * n u m + 1

איברים, השיטה תחזיר -1.

דוגמאות:
נניח שהמערך arr הוא
[25, 10, 5, 20, 40] במקומות 0 עד 4.

אם $n u m = 1$ , אז יש 3 איברים פוטנציאלים שימלאו את התנאי.

1. האיבר arr[1]. סכום התת-מערך שהוא באמצעו ומשמאלו ומימינו יש איבר אחד בכל צד הוא

a r r [0] + a r r [1] + a r r [2] = 25 + 10 + 5 = 40

.
ואמנם, 10 מחלק את 40.
2. האיבר arr[2]. סכום התת-מערך שהוא באמצעו ומשמאלו ומימינו יש איבר אחד בכל צד הוא

a r r [1] + a r r [2] + a r r [3] = 10 + 5 + 20 = 35

.
ואמנם, 5 מחלק את 35.
3. האיבר arr[3]. סכום התת-מערך שהוא באמצעו ומשמאלו ומימינו יש איבר אחד בכל צד הוא

a r r [2] + a r r [3] + a r r [4] = 5 + 20 + 40 = 65

.
אבל, 20 אינו מחלק את 65.
לכן השיטה תחזיר 2.

אם $n u m = 2$ , אז יש איבר אחד פוטנציאלי למלא את התנאי.

האיבר arr[2]. סכום התת-מערך שהוא באמצעו ומשמאלו ומימינו יש שני איברים בכל צד הוא

a r r [0] + a r r [1] + a r r [2] + a r r [3] + a r r [4] = 25 + 10 + 5 + 20 + 40 = 100

.
ואמנם, 5 מחלק את 100.
לכן השיטה תחזיר 1.

כמו כן, נניח שהמערך arr הוא
[1, 9, 3, 2, 5, 6, 7, 8, 9, 10, 3] במקומות 0 עד 10.

אם $n u m = 1$ , 5 איברים ימלאו את התנאי:

1. האיבר arr[3]=2. סכום =

a r r [2] + a r r [3] + a r r [4] = 3 + 2 + 5 = 10

. ואמנם, 2 מחלק 10.
2. האיבר arr[5]=6. סכום =

a r r [4] + a r r [5] + a r r [6] = 5 + 6 + 7 = 18

. ואמנם, 6 מחלק 18.
3. האיבר arr[6]=7. סכום =

a r r [5] + a r r [6] + a r r [7] = 6 + 7 + 8 = 21

. ואמנם, 7 מחלק 21.
4. האיבר arr[7]=8. סכום =

a r r [6] + a r r [7] + a r r [8] = 7 + 8 + 9 = 24

. ואמנם, 8 מחלק 24.
5. האיבר arr[8]=9. סכום =

a r r [7] + a r r [8] + a r r [9] = 8 + 9 + 10 = 27

. ואמנם, 9 מחלק 27.
לכן השיטה תחזיר 5.

אם $n u m = 2$ , 2 איברים ימלאו את התנאי:

1. האיבר arr[6]=7. סכום =

a r r [4] + a r r [5] + a r r [6] + a r r [7] + a r r [8] = 5 + 6 + 7 + 8 + 9 = 35

. ואמנם, 7 מחלק 35.
2. האיבר arr[7]=8. סכום =

a r r [5] + a r r [6] + a r r [7] + a r r [8] + a r r [9] = 6 + 7 + 8 + 9 + 10 = 40

. ואמנם, 8 מחלק 40.
לכן השיטה תחזיר 2.

אם $n u m = 3$ , 2 איברים ימלאו את התנאי:

1. האיבר arr[4]=5. סכום =

a r r [1] + a r r [2] + a r r [3] + a r r [4] + a r r [5] + a r r [6] + a r r [7] = 9 + 3 + 2 + 5 + 6 + 7 + 8 = 40

. ואמנם, 5 מחלק 40.
2. האיבר arr[7]=8. סכום =

a r r [4] + a r r [5] + a r r [6] + a r r [7] + a r r [8] + a r r [9] + a r r [10] = 5 + 6 + 7 + 8 + 9 + 10 + 3 = 48

. ואמנם, 8 מחלק 48.
לכן השיטה תחזיר 2.

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

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

נתון 2 מערכים חד-ממדיים

a

ו-

b

, שניהם באורך זהה, המכילים מספרים שלמים.

סעיף א (20 נקודות):
כתבו שיטה סטטית המקבלת כפרמטרים את שני המערכים

a

ו-

b

ומוצאת זוג איברים, אחד מהמערך

a

והשני מהמערך

b

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

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

סעיף ב (5 נקודות):
כתבו שיטה סטטית המקבלת כפרמטרים את שני המערכים

a

ו-

b

ומוצאת זוג איברים, אחד מהמערך

a

והשני מהמערך

b

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

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

לדוגמא, אם המערכים הם:

a = 0 15 - 2 62 1234 b = 083712

השיטה smallestDiffPair תחזיר את הערך 1 ותדפיס את האיברים 2---3 או את 6---7.
השיטה biggestDiffPair תחזיר את הערך 10 ותדפיס את האיברים -2---8.

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

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