שאלון קודגורו 6 שלב ב' – סופי

רשומה רגילה

1. מה המשמעות המקובלת בתכנות של המילה VOID?

  • מולטימדיה מאוד חכמה
  • חלל או ריק
  • טיפוס לא מוגדר
  • בדיקה של עמידות

2. מה המשמעות המקובלת בתכנות של int?

  • לייצג מספרים שלמים
  • להגדרות בינלאומיות
  • לצורכי בנקאות מקוונת
  • לארגון הבריאות העולמי
3. (*) מהו מספר ההשוואות המינימלי הנחוץ, במקרה הקשה ביותר, למיון מערך בן 5 איברים שונים?
4. (**) רוצים למיין מערך במספר גדול ככל האפשר של השוואות, אבל אסור להשוות בין שני איברים אם ניתן להסיק את היחס ביניהם מהשוואות קודמות. מהו המספר הגדול ביותר של השוואות אליו ניתן להגיע במיון של 5 איברים שונים?

5. נתונה הפונקציה הבאה, בסביבת 16bit:ב – C:

int f(unsigned char a, unsigned char b, unsigned char c)
{
	return ((a*b)/c) == (a*(b/c));
}

בפסקל:

function f(a, b, c : byte) : boolean;
var
	a0, b0, c0 : word;
begin
	a0 := a; b0 := b; c0 := c;
	f := ( ((a0*b0) div c0) = (a0*(b0 div c0)) );
end;

פונקציה זו תחזיר "אמת" אם ורק אם:

  • a=1 או (b mod c) = 0 או a=0
  • a*(b mod c) < c
  • (b mod c) = 0
  • תחזיר אמת תמיד
6. (*) במדינה שמספר תושביה עצום יש שני מתמודדים על הנשיאות ו – 50 ערים שגודלי אוכלוסיותיהן שווים. הבחירות נערכות בכל עיר בנפרד, והמתמודד שניצח ברב הערים הוא הזוכה בבחירות. דני ניצח בבחירות עם כמות הקולות המינימלית המאפשרת ניצחון. כמה קולות קיבל בממוצע במדגם אקראי של 3600 בוחרים מרחבי המדינה (עגל למספר השלם הקרוב ביותר)?

7. דני ניסה לחשב ממוצע של רשימה של N מספרים (N > 2) בצורה הבאה: הוא חישב את הממוצע של שני המספרים הראשונים, ואז את הממוצע של התוצאה עם המספר השלישי, ואת הממוצע של התוצאה החדשה עם המספר הרביעי וכך הלאה. למרות ששיטה זו לחישוב ממוצע אינה נכונה בעוד שלדני לא היו טעויות חישוב, המורה (שיודע לחשב ממוצע בצורה נכונה) בדק את התוצאה ושיבח את דני על התשובה הנכונה. דני, שחשד שהשיטה שלו אינה נכונה עבור המקרה הכללי, החליף את אחד המספרים במספר אחר (וסיפר על כך למורה), חישב את הממוצע החדש (בדרכו השגויה), וביקש מהמורה שיבדוק את התוצאה. אך איזה פלא – שוב שיבח המורה את דני על התוצאה הנכונה! איזה טענה נכונה בהכרח?

  • אם יוציאו את המספר שהוחלף, יהיה בין המספרים שנותרו מספר מספר השווה לממוצע של שאר המספרים (ללא המספר שהוצא)
  • N הוא 4, 5 או 8
  • המספר שהוחלף הוא המספר ה – lg(N)-י מסוף הרשימה (כאשר lg מייצג לוגריתם בבסיס 2)
  • המצב המתואר אינו אפשרי

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

  • פחות מ – 1 למיליון
  • בערך 1 ל – 2,500
  • בערך 1 ל – 100
  • בדיוק 1 ל – 2

9. נתון הפסאודו-קוד הבא (עם שלוש פונקציות חסרות):

א >- 1000000000
כל-עוד (אמת) בצע:
	אם ק, אזי:
		א >- 1000000000
		בצע פ
	אם א שווה ל - 0, אזי:
		בצע ס
	א >- 1-א

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

  • הקצאת מספרים סידוריים
  • פירוק מספרים גדולים לגורמים
  • תפעול דלת הזזה אוטומטית
  • הגרלת מספרי לוטו

10. (*) הפונקציה הבאה אמורה להחזיר את המיקום של האיבר שערכו x במערך A שמכיל N איברים ממוינים בסדר עולה (ומכיל איבר שערכו x). אבל יש בה באג.ב – C:

int get_index(int x, int A[], int N)
{
	int L = 0, H = N-1;

	while (L != H) {
		int M = (L+H)/2;
		if (x >= A[M])
			L = M;
		else
			H = M-1;
	}

	return L;
}

בפסקל (כאשר האיבר הראשון במערך A הוא האיבר במיקום ה – 0):

function get_index(x : integer; A : array of integer; N : integer) : integer;
var
	L, H, M : integer;
begin
	L := 0; H := N-1;

	while L <> H do
	begin
		M := (L+H) div 2;
		if x >= A[M] then
			L := M
		else
			H := M-1;
	end;
	get_index := L;
end;

עבור כמה ערכים של N, הפונקציה, בכל זאת, תחזיר תשובה נכונה תמיד?

11. מה עושה קטע הקוד הבא בשפת אסמבלי בסביבת 16bit?:

	mov bx, offset var_ptr
	xor ax, ax
l:
	xchg [bx], ax
	or ax, ax
	jz l
  • מחשב את שורש שלוש
  • תופס בעלות על משאב
  • מבצע מיון בועות
  • הופך רשימה מקושרת

12. מה עושה קטע הקוד הבא בשפת אסמבלי בסביבת 32bit?:

	xor ebx, ebx
start:
	test eax, eax
	jz end
	xchg ebx, [eax]
	xchg ebx, eax
	jmp start
end:
  • מחשב את שורש שלוש
  • תופס בעלות על משאב
  • מבצע מיון בועות
  • הופך רשימה מקושרת

13. מהן שלוש הפונקציות הבאות בשפת C:

void a(type1* s)
{
	p[0] = (type2*) malloc(sizeof(type2));
	p[1] = (type2*) malloc(sizeof(type2));
	p[0].a = p[1]; p[1].a = p[0];
	p[1].b = s;
}
void b(type1* s)
{
	type2* n = (type2*) malloc(sizeof(type2));
	p[0].b = s;
	n.a = p[0]; p[0].a = p[1]^n;
	p[1] = p[0]; p[0] = n;
}
int c(int d)
{
	if (p[!d].a != p[d]) {
		p[d] ^= p[!d].a;
		swap(p[d], p[!d]);
		return 1;
	}
	return 0;
}
  • מערכת Undo ו – Redo
  • מימוש של ערימה
  • מנגנון garbage collection
  • בינה מלאכותית ל – "ארבע בשורה"

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

15. (**) דני מביט, ממרחק של מטר, במחיצת קרטון ממנה גזרו פס צר. דרך הפס הוא יכול לראות חלק קטן מכרזת פרסומת לקודגורו 6. הנקודה הנראית לדני כשמאלית ביותר בפס נמצאת במרחק של 260 ס"מ מהמחיצה. הנקודה הנראית לדני כימנית ביותר בפס נמצאת במרחק של 440 ס"מ מהמחיצה. המרחק בין שתי נקודות אלו הוא שני מטרים. מהו המרחק בסנטימטרים בין הנקודה הנראית לדני בצדו השמאלי של הפס לבין הנקודה הנראית לו במרכז הפס?

16. למה משמשות שלוש הפונקציות הבאות:

בשפת C
בשפת פסקל

void a()
{
	x1 = x2 = 0;
}
procedure a;
begin
 x1 := 0;
 x2 := 0;
end;
int b()
{
	if (x1) return F[--x1];
	return x2++;
}

 

function b : integer;
begin
 if x1 <> 0 then
 begin
 x1 := x1 - 1;
 b := F[x1];
 end
 else
 begin
 b := x2;
 x2 := x2 + 1;
 end;
end;
void c(int x)
{
	F[x1++] = x;
}
procedure c(x : integer);
begin
 F[x1] := x;
 x1 := x1 + 1;
end;
  • מימוש של תור מעגלי
  • התמרת פוריה בדידה
  • פעולות על מספרים גדולים
  • טיפול יעיל בהקצאת זיכרון

17. (*) נתונה הפונקציה הבאה בסביבת 32bit:ב – C:

unsigned int div_by_17(unsigned int a)
{
	return (MUL*a)>>SHIFT;
}

ניתן למצוא ערכים של MUL ו – SHIFT עבורם ערך החזרה של הפונקציה יהיה a חלקי 17 (מעוגל כלפי מטה), בהנחה ש – 16 הביטים העליונים של a כבויים.
מצא ערך מתאים של MUL:

18. (*) בהמשך לשאלה הקודמת, מצא ערך של SHIFT המתאים לערך של MUL שמצאת:

19. (**) המורה של דני השתמש בשיטה הבאה כדי לכווץ הודעה המורכבת מ – 26 אותיות ה – ABC (אותיות גדולות בלבד):

הגדרה:
	מילון0 הוא מילון היודע לקחת מחרוזת ולמצוא מספר שהותאם לה קודם לכן
	(או להגיד שעדיין לא הותאם לה מספר)

עבור כל אות מה - ABC, בצע:
	התאם למחרוזת המכילה את האות הזו בלבד את האינדקס שלה ב - ABC
	(כלומר, ל - "A" יותאם 1 ול - "Z" יותאם 26)

הכנס למשתנה קוד0 את המספר 26

קרא את התו הראשון מהמסר ושמור אותו ב - מחרוזת0

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

המסר המכווץ נראה כך (משמאל לימין):

3, 7, 27, 24, 29, 31, 7

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

20. נתונות שתי דרכים לממש פונקציה מסוימת:ב – C:

unsigned int f1(unsigned int n)
{
	unsigned int x = 1;
	for (unsigned int i = 1; i <= n; i++) {
		x *= i;
	}
	return x;
}

unsigned int f2(unsigned int n)
{
	if (n == 0) return 1;
	return n*f2(n-1);
}

בפסקל:

function f1(n : word) : word;
var
 x, i : word;
begin
 x := 1;
 for i := 1 to n do x := x*i;
 f1 := x;
end;

function f2(n : word) : word;
begin
 if n = 0 then f2 := 1
 else f2 := n*f2(n-1);
end;

בחר את הטענה הנכונה:

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

21. מה הקשר בין d – ממוצע הזמן בדקות בין פגיעת שני מטאורים, לבין m – ממוצע מספר המטאורים הפוגעים בדקה?

  • תמיד מתקיים m = d
  • יכול להיות ש m = 1/d
  • אף פעם לא d = 1/m
  • כל התשובות נכונות

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

  • 10 שניות
  • 42 דקות
  • 42 יום
  • אינסוף

23. אני מחפש ספגטי מסוים בסופרמרקט, יש לי את ה-Bar-Code שלו ואני מנסה להשוות מול המוצרים שעל המדף. איזו שיטה יעילה יותר?

  • לבדוק את הספרה הראשונה (msb) ורק אם מתאימה לבדוק את הספרות הבאות
  • לבדוק את הספרה האחרונה (lsb) ורק אם מתאימה לבדוק את הספרות הבאות
  • תלוי איזה רוטב אני מעדיף
  • כל התשובות נכונות

24. ולמה?

  • כי הספרות האחרונות הם ספרות ביקורת
  • כי הספרות הראשונות קבועות למוצרים רבים
  • כי יש קשר בין הרוטב המועדף ל-Bar-Code
  • כל התשובות נכונות

25. להלן אלגוריתם הפעולה של מיקרוגל

start:
 time = 0
loop:
 if (time == 0 and program_time) time = user_input
 if (time > 0) {heat; time--; wait_a_second; if (time == 0) beep_end}
 goto loop
 
On cancel_pressed Interrupt:
 if (time>0) beep_abort; time=0
 goto loop

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

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

26. האם יכול להיות ש-30% מהגברים בגילאים 30 עד 40 הם רווקים ו-40% מהגברים בגילאי 40 עד 50 הם רווקים?

  • לא, כי יציאה מרווקות היא תהליך בלתי הפיך (אלמן וגרוש אינם רווקים)
  • לא, כי 50% מהאוכלוסייה הן נשים (ו 30+40 > 50)
  • כן, כי המצב לא חייב להיות יציב (עוד 10 שנים המספרים ישתנו)
  • כן, אבל רק אם מתמקדים באוכלוסיית תל-אביב בלבד

27. לפני קו עצירה של רמזור יש מספר גלאי מתכת. מה יקרה אם תוכנת הרמזור מתחשבת רק בגלאי המרוחק ביותר מהרמזור המגלה מתכת?

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

28. מה מחשבת הנוסחא הבאה?

(x0*y1-x1*y0)/sqrt((x0*x0+y0*y0)*(x1*x1+y1*y1))
  • אורך של אלכסון במחומש משוכלל
  • חוצה זווית של משולש שווה שוקיים
  • מרחק ממנו רואים פסל בזוית מירבית
  • קוסינוס של זוית שקודקודה בראשית

29. מה מחשב הקטע הבא

xm=0
for x = 0 to 100 {
	xx = x*(y2-y1)/sqrt((x*x+y1*y1)*(x*x+y2*y2))
	if (xx > xm) xm = xx; a=x
}
  • אורך של אלכסון במחומש משוכלל
  • חוצה זווית של משולש שווה שוקיים
  • מרחק ממנו רואים פסל בזוית מירבית
  • קוסינוס של זוית שקודקודה בראשית

30. נתון קטע הקוד (החסר) הבא בשפת C++:

class A { ... };
class B { ... };
class C { ... };

class Container {
	Container() : a(), c(), b() {
		c.start();
		b.start();
		a.start();
	}
	A a;
	B b;
	C c;
};

כאשר יוצרים מופע של המחלקה Container, באיזה סדר ייקראו הבונים (constructors) של האובייקטים המוכלים a, b, c?

  • קודם a, אח"כ b ולבסוף c
  • קודם c, אח"כ b ולבסוף a
  • קודם a, אח"כ c ולבסוף b
  • קודם b, אח"כ a ולבסוף c

31. כיצד ניתן לבצע TLB Priming?

  • לקרוא את המילה האחרונה של העמוד ממנו רוצים לקרוא ומיד לקרוא את העמוד מתחילתו ועד סופו
  • לקרוא מילה כלשהי מעמוד אותו רוצים לקרוא, ואז לעבוד על זיכרון אחר לפני שניגשים לעמוד הנ"ל
  • לקרוא עמוד בצרור (burst) מתחילתו ועד סופו, ואז לעבור עליו מסופו לתחילתו
  • לקרוא מילה אחת מכל שורת מטמון (cache line) בעמוד לפני שעוברים עליו

32. (*) מה תחזיר התוכנית הבאה?ב – C:

int f(int p, int p1)
{
	int i,j,i1,j1;
	i =p >>3; j =p &7;
	i1=p1>>3; j1=p1&7;
	return (i-i1)*(i-i1)+(j-j1)*(j-j1) == 5;
}

בפסקל:

function f(p, p1 : integer) : boolean;
var
 i, j, i1, j1 : integer;
begin
 i := p shr 3; j := p and 7;
 i1 := p1 shr 3; j1 := p1 and 7;
 f := (i-i1)*(i-i1)+(j-j1)*(j-j1) = 5;
end;
  • האם p גדול מ p1 כמספרים מרוכבים
  • האם אפשר להגיע במהלך פרש מ – p אל p1
  • האם p ניתן לייצוג כ p1 ספרות בבסיס 7
  • כל התשובות נכונות

33. (**) מה תחזיר התוכנית הבאה?

int s(unsigned __int64 x){return (!x || x&(x-1));}

int r()
{
	unsigned __int64 i,m1,m2;
	int r = 0;
	int j;
	for (i=1; i; i++,r+=j==8)
		for (j=0,m1=0xff,m2=0x101010101010101; j<8; j++,m1<<=8, m2<<=1)
			if (s(i&m1) || s(i&m2)) break;
	return r;
}

 

34. מה ספרת העשרות הנפוצה בין מליון חזקות 2 הראשונות?

  • 1
  • 2
  • 9
  • כולן מופיעות בערך בשכיחות שווה

35. מה הספרה הנפוצה ביותר כספרה ראשונה (Most Significant) בין מיליון חזקות 2 הראשונות?

  • 1
  • 2
  • 9
  • כולן מופיעות בערך בשכיחות שווה

36. מה מיוחד במספר 26334878?

  • כשמתרגמים אותו לאוקטלית, לא מכיל את הספרות 0 ו-7
  • תרגום של שם התחרות מאנגלית לספרות
  • מכפלה של שני מספרים ראשוניים
  • כל התשובות נכונות

37. מדוע השורה הבאה בשפת C גורמת לתוכנית לקרוס בארכיטקטורת x86?

void*x=(*((void*(*)())&(x=(void*)0xfdeb58)))();
  • Access Violation
  • Stack Underflow
  • Invalid Opcode
  • ביט Mod R/M משובש

38. מה זה 2001:0db8:85a3:08d3:1319:8a2e:0370:7334?

  • כתובת בפרוטוקול IPv6
  • נגטיב של חתול
  • המספר הראשוני הגדול ביותר הידוע כיום, בייצוג הקסדצימלי
  • בקשה לסנכרון, בפרוטוקול V.42 (מודם)

39. איזו מהאפשרויות הבאות אינה מבנה נתונים ידוע?

  • ערימה בינארית
  • ערימה מקושרת
  • ערימה בינומית
  • ערימת פיבונאצ'י
40. (*) צריח נע על לוח שח-מט סטנדרטי מהפינה השמאלית-עליונה אל הפינה הימנית-תחתונה. בכל צעד, הצריח יכול לזוז משבצת אחת ימינה או משבצת אחת למטה. כמה מסלולים אפשריים יש לצריח?

41. מה המקור של הביטוי SPAM?

  • דואר זבל זה מגעיל כמו בשר משומר
  • Shit Posing As Mail
  • סקיצה של "מונטי פייטון"
  • אף תשובה אינה נכונה

42. לאחר הרצת הקוד הבא בשפת C:

FILE* fp = fopen("1.txt", "w");
char ch = 0xa;
fwrite(&ch, sizeof(ch), 1, fp);
fclose(fp);

גודל הקובץ שנוצר היה שני בתים ולא בית אחד, מדוע?

  • מכיוון ש – fwrite מיועד לכתיבת בלוקים
  • מכיוון ש – fclose מוסיף בית מסיים
  • מכיוון שהקובץ נפתח במצב כתיבה טקסטואלי
  • מכיוון שהקוד רץ על מעבד AMD

43. (***) מה עושה הפונקציה הבאה, למה זה שימושי?ב – C:

int B[1<<7];

void f()
{
	int c, i, j;
	for (c = 0; c < (1<<7); c++) {
		if (B[c] == 0) {
			printf("%d\n", c);
			B[c] = 1;
			for (i = 1<<6; i != 0; i>>= 1) {
				for (j = 1<<6; j != 0; j>>= 1) {
					B[c^(i|j)] = 1;
				}
			}
		}
	}
}

בפסקל:

var
	b : array[0..(1 shl 7)] of integer;

procedure f;
var
	i, j, c : integer;
begin
	for c := 0 to (1 shl 7)-1 do
	begin
		if B[c] = 0 then
		begin
			writeln(c);
			B[c] := 1;
			i := 1 shl 6;
			while i <> 0 do
			begin
				j := 1 shl 6;
				while j <> 0 do
				begin
					B[c xor (i or j)] := 1;
					j := j shr 1;
				end;
				i := i shr 1;
			end;
		end;
	end;
end;

44. (****) מה עושה הפונקציה הבאה:ב – C:

int O[4] = {1, -1, 128, -128};

void f(unsigned char A[1<<14], int B[1<<14])
{
	int C[1<<8] = {0x3F7E};
	unsigned char X = 0, Y = 1;
	int j, m;
	for (j = 0; j < 1<<14; j++)
		B[j] = -1;
	while (X != Y) {
		int c = C[X++];
		for (j = 0; j < 4; j++) {
			m = c + O[j];
			if ((A[m] == 0) && (B[m] == -1) && (m != B[c]))
				{B[m] = c; C[Y++] = m; }
		}
	}
}

בפסקל:

const
 O : array[0..3] of integer = (1, -1, 128, -128);

type
 typeA = array[0..(1 shl 14)-1] of byte;
 typeB = array[0..(1 shl 14)-1] of integer;

procedure f(var a : typeA; var b : typeB);
var
 C : array[0..(1 shl 8)-1] of integer;
 X, Y : byte;
 j, m, k: integer;
begin
 C[0] := $3F7E;
 X := 0; Y := 1;
 for j := 0 to (1 shl 14)-1 do
 B[j] := -1;
 while (X <> Y) do
 begin
 k := C[X]; X:=X+1;
 for j := 0 to 3 do
 begin
	 m := k + O[j];
	 if (A[m] = 0) and (B[m] = -1) and (m <> B[k]) then
 begin
		 B[m] := k; C[Y] := m; Y:=Y+1;
 end;
	 end;
 end;
end;

 

כתיבת תגובה