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

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

בהצלחה !!!

שאלה 1 ( 25 נק' )

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

כתבו תוכנית הקולטת מספר טבעי n ורשומות של n מניות של חברות ישראליות ומדפיסה את הרשומות ממויינות בסדר יורד על פי שווי השוק של כל חברה.

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

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

stock *merge(stock a[],int n,stock b[],int m);
void sort(stock a[],int n);

הפונקציה merge מקבלת כקלט שני מערכים a ו-b של n ו-m רשומות של מניות, בהתאמה. נתון כי המערכים a ו-b ממויינים בסדר יורד ( מהגדול לקטן ). הפונקציה merge צריכה לבצע הקצאה דינמית של מערך בגודל n+m שיכיל את המיזוג של המערכים a ו-b למערך אחד הממויין בסדר יורד. הערך המוחזר של הפונקציה הוא מצביע למערך שהוקצה על ידה.
הפונקציה sort ממיינת מערך a של n רשומות של מניות בסדר יורד.

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

דוגמה:

קלט:

5
Bezeq		2986.9			7.39		575
Teva		18320.2		9.5		12080
ICL		2747.7			6.8		987
Leumi		4183.4			9.5		1346
Poalim		4531.1			9.5		1582

פלט: 

Teva		18320.200000		9.500000	12080
Poalim		4531.100000		9.500000	1582
Leumi		4183.400000		9.500000	1346
Bezeq		2986.900000		7.390000	575
ICL		2747.700000		6.800000	987

הערות:

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

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

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

שאלה 2 ( 25 נק' )

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

הפונקציה מקבלת כקלט מחרוזת s המכילה מספר המיוצג בשיטת המשלים ל-2 והערך המוחזר שלה שווה לערכו של מספר זה.

דוגמאות:

twos_complement(“001101”) תחזיר 13.
twos_complement(“101101”) תחזיר -19.
twos_complement(“1011”) תחזיר -5.

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

void negate(char *s);
void add_one(char *s);
int binary_value(char *s);

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

שאלה 3 ( 15 נק' )

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

int decimal_digits(int n);

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

דוגמאות:

decimal_digits(314) תחזיר 3.
decimal_digits(271828) תחזיר 6.

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

שאלה 4 ( 15 נק' )

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

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

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

1.	במערך יש לפחות איבר אחד שלילי.
2.	במערך יש לפחות איבר אחד השווה לאפס.
3.	במערך יש לפחות איבר אחד חיובי.

אחרת, הפונקציה מחזירה אפס.

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

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

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

שאלה 5 ( 10 נק' )

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

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

הפונקציה מחזירה 1 אם למחרוזת s יש אורך זוגי, ואפס אחרת.

הערות:

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

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

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

שאלה 6 ( 10 נק' )

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

הקלט לפונקציה הוא מטריצה 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.