קשיים של תלמידים בעיצוב תכנה

שאלה 3 משאלון בגרות 899205 קיץ תשס"ב

המבחן המלא נמצא כאן

 

נתון טיפוס נתונים מופשט מוט.

על מוט משחילים טבעות משני גדלים: טבעות גדולות וטבעות קטנות.

להלן נתונות כמה פעולות מתוך מימשק הטיפוס מוט בסביבת העבודה (כתובות בפסקל).

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

 

מימשק בפסקל

פעולה המחזירה מוט p ריק.

סיבוכיות זמן ריצה O(1)

Procedure pole_init (var p: pole_type)

הפעולה מכניסה טבעת r לראש מוט p.

הנחה: r,p מאותחלים.

סיבוכיות זמן ריצה O(1)

Procedure pole_insert

  (var p: pole_type; r: pole_info_type)

הפעולה מוציאה טבעת r מראש מוט p ומחזירה אותה.

הנחה: p מאותחל ולא ריק.

סיבוכיות זמן ריצה O(1)

Procedure pole_remove

(var p: pole_type; var r: pole_info_type)

הפעולה מחזירה "אמת" אם מוט p ריק אחרת הפעולה מחזירה "שקר"

הנחה: p מאותחל.

סיבוכיות זמן ריצה O(1)

Function pole_is_empty

 (p: pole_type): boolean

הפעולה מחזירה את התו "L" אם r טבעת גדולה ואת התו "S" אם r טבעת קטנה.

הנחה: r מאותחל

סיבוכיות זמן ריצה O(1)

Function ring_type

 (r: pole_info_type): char;

 

א. ממש בסביבת העבודה את הפעולה:

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

הנחה: p מאותחל.

סדר-מוט(p)

 

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

 

ניתוח השאלה ע"י אלה מריאנובסקי

ניתוח השאלה ע"י רחל שליסלברג

ניתוח השאלה ע"י ויקי שנקרמן

ניתוח השאלה ע"י אהובה שפרלינג ודורית ליקרמן

 

לאתר המרכז הארצי

לאתר עיצוב תכנה

למאגר קשיים

חזרה