משך המבחן: שלוש שעות.

הנחיות כלליות:
1.	חומר עזר: דף A4 אחד הכתוב בשני צדדיו.
2.	יש לענות במחברת המבחן בלבד.
3.	טופס המבחן ישמש כטיוטא ולא יבדק.
4.	התשובה לכל שאלה תתחיל בעמוד חדש.
5.	יש לענות על כל השאלות.

בהצלחה !!!

שאלה 1 ( 25 נק' )

סעיף א' ( 17 נק' )

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

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

double average(player p[],int n);
double std(player p[],int n);

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

דוגמה:

קלט:

14
Fanan			4		1981		183		Israel
Baston			5		1976		206		USA
Sharp			6		1971		183		Israel
Vujcic			7		1978		211		Croatia
Parker			8		1975		198		USA
Shelef			9		1974		201		Israel
Burstein		10		1980		198		Israel
Halperin		11		1984		193		Israel
Dotan			12		1974		194		Israel
Jasikevicius		13		1976		193		Lithuania
Caspi			14		1988		203		Israel
Kommatos		20		1977		203		Greece
Thomas		25		1971		204		Israel
Green			41		1980		206		Israel

פלט: 

average = 198.285714		std = 8.048323
Fanan			4		1981		183		Israel
Sharp			6		1971		183		Israel
Vujcic			7		1978		211		Croatia

הערות:

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

סעיף ב' ( 8 נק' )

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

שאלה 2 ( 25 נק' )

כתבו פונקציה כדלהלן:
void print_binary(int n);

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

דוגמה:

print_binary(5) תדפיס:
001
010
011
100
101

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

int binary_digits(int n);
char *create_zeros_string(int k);
void add_one(char *s);

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

שאלה 3 ( 15 נק' )

כתבו פונקציה רקורסיבית כדלהלן:

int element(int n);

הפונקציה מקבלת כקלט מספר טבעי n והערך המוחזר שלה הוא האיבר ה-n בסידרה המוגדרת ע"י נוסחת הנסיגה הבאה:

איברי הסידרה הראשונים הם:
1,2,3,7,22,155,3411,528706,…

ניקוד חלקי ינתן למימוש שבו הפונקציה element איננה פונקציה רקורסיבית.

שאלה 4 ( 15 נק' )

סעיף א' ( 12 נק' )

כתבו פונקציה כדלהלן:
int positive_num(int a[],int n);

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

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

סעיף ב' ( 3 נק' )

מה סיבוכיות זמן הריצה של הפונקציה אותה מימשתם בסעיף א' כתלות בפרמטר n?
אין צורך לנמק את התשובה.

שאלה 5 ( 10 נק' )

סעיף א' ( 7 נק' )

כתבו פונקציה כדלהלן:
int is_alpha_blank(char *s);

הפונקציה מחזירה 1 אם המחרוזת s מכילה אך ורק אותיות אנגלית גדולות (התווים A עד Z) או רווחים, ואפס אחרת.

הערות:

1.	המימוש של הפונקציה יעשה ע"י שימוש במצביעים בלבד (אסור להגדיר משתנים מטיפוס שאינו מצביע, כמו למשל int או double).
2.	אסור לעשות שימוש בסוגריים מרובעים.  
3.	אין לבצע קריאה לפונקציות אחרות מתוך הפונקציה (בפרט, אסור להשתמש בפונקציות ספריה).

סעיף ב' ( 3 נק' )

נסמן ב-n את אורך המחרוזת s. מה סיבוכיות זמן הריצה של הפונקציה אותה מימשתם בסעיף א' כתלות בפרמטר n?
אין צורך לנמק את התשובה.

שאלה 6 ( 10 נק' )

כתבו פונקציה כדלהלן:
int positive_diagonals(int a[11][11]);

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

   
בהצלחה !!!

נספחים:

Precedence and Associativity of Operators

Table 1 summarizes the rules for precedence and associativity of all operators. Operators on the same line have the same precedence; rows are in order of decreasing precedence, so, for example, *, /, and % all have the same precedence, which is higher than that of binary + and -. 

Operators 	Associativity 	
() [] -> .	 left to right	
! ~ ++ -- + - * & (type) sizeof	 right to left	
* / % 	 left to right	
+ - 	 left to right	
<<  >> 	 left to right	
< <= > >= 	 left to right	
== != 	 left to right	
& 	 left to right	
^ 	 left to right	
| 	 left to right	
&&	 left to right	
|| 	 left to right	
?: 	 right to left	
= += -= *= /= %= &= ^= |= <<= >>=	 right to left	
, 	 left to right	
Unary &, +, -, and * have higher precedence than the binary forms. 
Table 1: Precedence and Associativity of Operators 

Standard Library Functions

Input and Output: <stdio.h>

int printf(const char *format, ...) 
The printf function provides formatted output conversion. 
int scanf(const char *format, ...) 
The scanf function deals with formatted input conversion. 

String Functions: <string.h>
In the following table, variables s is of type char *; cs and ct are of type const char *; and c is an int converted to char. 
char *strcpy(s,ct)	copy string ct to string s, including '\0'; return s.	
char *strcat(s,ct)	concatenate string ct to end of string s; return s.	
int strcmp(cs,ct)	compare string cs to string ct, return <0 if cs<ct, 0 if cs==ct, or >0 if cs>ct.	
char *strchr(cs,c)	return pointer to first occurrence of c in cs or NULL if not present.	
char *strstr(cs,ct)	return pointer to first occurrence of string ct in cs, or NULL if not present.	
size_t strlen(cs)	return length of cs.	
In the following table, s is of type void *; ct is of type const void *; n is of type size_t; and c is an int converted to an unsigned char. 
void *memcpy(s,ct,n)	copy n characters from ct to s, and return s.	
void *memset(s,c,n)	place character c into first n characters of s, return s.	

Mathematical Functions: <math.h>
In the following table, x and y are of type double, and all functions return double. 
exp(x) 	exponential function ex	
log(x) 	natural logarithm ln(x), x>0.	
log10(x) 	base 10 logarithm log10(x), x>0.	
pow(x,y) 	xy. A domain error occurs if x=0 and y<=0, or if x<0 and y is not an integer.	
sqrt(x) 	square root of x, x>=0.	
fabs(x) 	absolute value |x|	

Utility Functions: <stdlib.h>

double atof(const char *s) 
atof converts s to double. 
int atoi(const char *s) 
converts s to int. 
int rand(void) 
rand returns a pseudo-random integer in the range 0 to RAND_MAX, which is at least 32767. 
void srand(unsigned int seed) 
srand uses seed as the seed for a new sequence of pseudo-random numbers. The initial seed is 1. 
void *malloc(size_t size) 
malloc returns a pointer to space for an object of size size, or NULL if the request cannot be satisfied. The space is uninitialized. 
void free(void *p) 
free deallocates the space pointed to by p; it does nothing if p is NULL. p must be a pointer to space previously allocated by malloc. 
int abs(int n) 
abs returns the absolute value of its int argument. 

Date and Time Functions: <time.h>

time_t time(time_t *tp) 
time returns the current calendar time or -1 if the time is not available. If tp is not NULL, the return value is also assigned to *tp.