מדעי המחשב

2 יחידות לימוד

הוראות לנבחן

א. משך הבחינה: שלוש שעות.

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

פרק ראשון - בפרק זה חמש שאלות,

ועליך לענות על כולן. ( 5 ´ 10) - 50 נקודות

פרק שני - בפרק זה שלוש שאלות, מביניהן

עליך לענות על שתיים ( 2 ´ 15 ) - 30 נקודות

פרק שלישי - בפרק זה שתי שאלות, מביניהן

עליך לענות על אחת בלבד ( 1 ´ 20 ) - 20 נקודות

ג. חומר עזר מותר בשימוש: כל חומר עזר ( פרט למחשב הניתן לתכנות )

ד. הוראות מיוחדות: אין

בהצלחה !!!

פרק ראשון ( 50 נקודות )

ענה על כל השאלות 1 - 5 ( לכל שאלה - 10 נקודות ).

שאלה 1

נתונה התוכנית הבאה:

program Prog (input,output);

var

A ,B: integer;

procedure P(X:integer; var Y:integer);

begin

Y:=X*Y;

X:=X+1

end;

begin

A:=5;

B:=4;

P(A,B);

writeln( A, , ' ' B)

end.

א. מה יוצג כפלט בעקבות הרצת התוכנית ?

ב. שנה את כותרת הפרוצדורה P כך שבעקבות הרצת התוכנית יוצג הפלט הבא: 4 6

שאלה 2

נתון האלגוריתם הבא:

קלוט נתון ב - N

בצע עבור I מ- 1 עד N

בצע עבור K מ- 1 עד 5

אם K הוא כפולה של 3 אזי

הצג כפלט את I*10+K

א. מהו הפלט שיוצג עבור הקלט 4?

ב. מהו מספר הפעמים שיתבצע גוף הלולאה הפנימית עבור הקלט 4 ?

ג. כתוב אלגוריתם יעיל יותר מבחינת זמן ביצוע.

שאלה 3

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

נקבע את התו 'כ' עבור הצבע כחול, נקבע את התו 'י עבור הצבע ירוק,

נקבע את התו 'ח' עבור הצבע חום, נקבע את התו 'ש' עבור הצבע שחור.

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

PersonType = record

Stud_num :integer; {מספר תלמיד }

Eye : char {צבע עיניים }

end;

נתונה כותרת הפונקציה הבוליאנית Bright .

function Bright(P:PersonType):boolean;

{טענת כניסה: הפונקציה מקבלת כפרמטר רשומה מטיפוס Person }

{טענת יציאה: הפונקציה מחזירה true אם צבע העיניים בהיר, false אחרת }

begin

×

×

end; { Bright }

א. השלם את גוף הפונקציה במחברתך.

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

Student :PersonType; רשומה המתארת מספר סטודנט וצבע העיניים שלו } }

העזר בפונקציה שכתבת בסעיף א' והשלם במחברתך את התנאי הבא :

if ________________________ then

writeln (אין צבע עיניים בהיר ' ', _________________ , ' 'לתלמיד מספר )

שאלה 4

בכספת שבה 100 מדפים הממוספרים מ- 1 ועד 100 שמורים יהלומים.

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

לתכנית מחשב ניתן הקלט הבא: סדרה של 100 תווים שערך כל אחד מהם הוא Y או N, אשר מבטאים הימצאות או אי -הימצאות יהלומים על מדפי הכספת. ( כלומר, Y בתו ה I-י בסדרה מבטא - "יש יהלומים על המדף ה I-י "; ובאופן דומה, N בתו ה I-י בסדרה מבטא - "אין יהלומים על המדף ה I-י " ).

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

א. מספר המדפים שהנם באותו מצב כמו המדף הראשון.

ב. מספר המדפים שהנם באותו מצב כמו המדף האחרון.

ג. מספר המדפים עליהם יש יהלומים ומספר המדפים עליהם אין יהלומים.

שאלה 5

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

CodeArray = array [1..20] of char;

ונתונה כותרת הפונקציה הבאה:

function Count(Code:CodeArray):inetger;

{טענת כניסה: הפרמטר Code מכיל סדרה של תווים שכל אחד מהם הוא + או - }

{טענת יציאה: הפונקציה מחזירה ערך 1 אם בסדרה מופיעים רק סימני +, או רק סימני - }

ומחזירה ערך 2 אם בסדרה מופיעים גם + וגם - }

.

.

.

end; { Count }

השלם את הפונקציה על-פי הסעיפים א' ו ב'.

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

ב. כתוב את גוף הפונקציה בשפת פסקל.

פרק שני ( 30 נקודות)

ענה על שתיים מבין השאלות 6 - 8 (לכל שאלה - 15 נקודות).

שאלה 6

א. נתונה פונקציה בוליאנית בשם MidMax .

function MidMax(A,B,C: real):Boolean;

{ טענת כניסה: הפונקציה מקבלת כפרמטרים 3 ערכים מספריים C , B , A }

{ טענת יציאה: הפונקציה מחזירה true אם הערך האמצעי גדול משני שכניו, }

{ false אחרת }

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

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

ב. במסגרת הטיול השנתי של תלמידי כתה יא' בבית הספר סע_וחשב, החליטו התלמידים לספור

את מספר הפסגות שאותן עברו במסגרת הטיול .

פסגה מוגדרת כערך שגבוה מן השכן לו מימין ומן הערך השכן לו משמאל.

לדוגמה: בתרשים הבא נספרו סה"כ: 6 פסגות .

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

למשל, הגבהים שבתרשים ישמרו במערך הבא:

206

360

300

167

406

310

328

250

200

120

400

380

435

200

337

200

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

ArrayType = array [1..N] of integer;

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

הערה: הנקודות הראשונה והאחרונה אינן נחשבות לפסגות (כיוון שחסר להן שכן).

שאלה 7

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

const

N:=4;

type

MatrixType = Array [1..N,1..N] of integer;

נתונה הפרוצדורה Swap המבצעת את המתואר בטענות הכניסה והיציאה שלה.

procedure Swap ( var A,B : integer) ;

{ טענת כניסה: הפרוצדורה מקבלת כפרמטרים שני מספרים }

{ טענת יציאה: הפרוצדורה מחליפה בין ערכי הפרמטרים }

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

procedure Changing(var Mat : MatrixType);

{טענת כניסה: הפרוצדורה מקבלת כפרמטר מערך דו מימדי מטיפוס { MatrixType

{טענת יציאה : הפרוצדורה מחליפה את אברי המטריצה שמעל האלכסון הראשי }

{ באברי המטריצה שמתחת לאלכסון ( ראה דוגמה ) }

var

Row : integer; מספר השורה במטריצה } {

Col : integer; מספר העמודה במטריצה } }

begin { Changing }

for Row:=1 to N do

for Col:=1 to N do

Swap( Mat[ Row , Col ] , Mat[ Col , Row ] ) ;

end; { Changing }

לדוגמה: עבור המטריצה כפרמטר, אמורה להיות מוחזרת המטריצה:

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

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

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

לדוגמה: עבור המטריצה בדוגמה למעלה תחזיר הפונקציה את הערך 36.

שאלה מספר 8

נתונה ההצהרה type CharArray = array[1..100] of char;

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

procedure XXX (var Sentence : CharArray);

{טענת כניסה: הפרמטר Sentence מכיל סדרה של תווים המהווים משפט באנגלית, אשר}

{ בין כל זוג מילים בו מפריד רצף של אחד או יותר סימני +, ואחרי המלה }

{ האחרונה בו מופיע רצף של אחד או יותר סימני + }

{ טענת יציאה: ? ? ? }

var

I: integer;

begin

for I:=1 to 99 do

if not ((A[I]=A[I+1]) and ( A[I]='+')) then

write (A[I])

end;{XXX}

א. תאר את פלט הפרוצדורה עבור סדרת התווים הבאה כפרמטר:

I

+

A

M

+

+

H

E

R

E

+

+

.

.

.

+

ב. תן שתי דוגמאות שונות של סדרת תווים הניתנת כפרמטר, אשר עבור כל אחת מהן יתקבל הפלט: I+HAVE+A+SOLUTION

III.השלם את הפונקציה אשר כותרתה:

function Exists ( Sentence: CharArray ) : boolean;

{ טענת כניסה: הפרמטר Sentence מכיל סדרה של תווים מהא"ב הלועזי }

{ טענת יציאה: הפונקציה מחזירה ערך true אם רצף האותיות AB מופיע ב{ Sentence -

{ ו - false אחרת }

פרק שלישי ( 20 נקודות)

ענה על אחת מבין השאלות 9 - 10 (20 נקודות).

שאלה מספר 9

בכתה ט' בבית ספר "תהילה" 40 תלמידים. לכל תלמיד מספר סידורי מ- 1 ועד 40 המייצג אותו.

המורה לדרמה המלמד בכתה הנ"ל בחר תלמידים לשתי הצגות: הצגת "רומיאו ויוליה" והצגת "היפיפייה הנרדמת".

להלן דוגמה לשתי קבוצות השחקנים.

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

· כמה תלמידים נבחרו לשתי ההצגות ומהם מספריהם הסידוריים?

· מהם מספריהם הסידוריים של התלמידים שלא נבחרו אפילו להצגה אחת?

· כמה מתלמידי הכתה נבחרו בדיוק לאחת משתי ההצגות (או "רומיאו ויוליה" או "היפיפייה הנרדמת") ומהם מספריהם הסידוריים ?

הקלט הוא שתי רשימות של מספרים סידוריים. רשימה ראשונה כוללת את מספריהם הסידוריים של המשתתפים ב"רומיאו ויוליה" והרשימה השנייה כוללת את מספריהם הסידוריים של המשתתפים ב"יפיפייה הנרדמת" . כל אחת מהרשימות מסתיימת בזקיף 0 .

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

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

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

שאלה מספר 10

בטורניר כדורגל משתתפות חמש קבוצות ששמותיהן A , B , C , D , ו- E .

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

· עבור ניצחון במשחק זוכה הקבוצה המנצחת ב - 3 נקודות והמפסידה אינה זוכה בנקודות, ועבור תוצאת תיקו במשחק זוכה כל קבוצה בנקודה אחת.

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

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

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

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

לדוגמה: רביעיית הנתונים 5 3 B A מבטאת משחק שבו B ניצחה את A בתוצאה 5 : 3 . בעקבות משחק זה זוכה B ב- 3 נקודות, הפרש השערים של B גדל ב- 2 ( 5-3 ) והפרש השערים של A גדל ב- -2 ( 3-5 ) .

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

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

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

בהצלחה ! ! !