Главна страница

Упражнение 10 - Контролна 2

2010 година

Задачите от 2011 година

Контролна 1 - поправка

Информатично интерпретативно съчинение

– кошмарът на студентите от втори курс

(информатично интерпретативно съчинение)

Кошмарът се повтаряше всяка нощ. Заспивах с надеждата да се озова в прекрасната страна на сънищата, там където радостта и спокойствието властват над хаоса. Но уви! В мига щом затворех очи, пред мен се появяваше огромна,черна стена. Тръгнах да търся пролука, за да я заобиколя, но така и не можех да мина от другата страна. Вървях, може би, километри. Стори ми се цяла вечност. И изведнъж (както става обикновено в сънищата) пред мен изгрява слънце. А, защо ли? Озовала съм се на върха на огромното черно „Нещо“, което е толкова високо, че пред мен и навсякъде наоколо се открива страховита гледка. Обширно, бяло поле с мигаща, черна черта в единия край. „Намирам се в най-страшния си кошмар“ – помислям си аз, все още сънувайки. Гонят ме срокове, имам много малко време, за да изпълня полето със символи.

Чак сега осъзнавам случващото се. Намирам се на върха на стек (същият, който асистентът по АСД рисуваше на бялата дъска). От толкова високо си е доста страшно. А аз изнемогвам, нямам сили да вдигна огромната цифра и да я поставя в стека. „Спомни си! Спомни си!“ – си казвам. Да. Изведнъж в съзнанието ми изплува методът „push“. Използвайки го, няма да е нужно да правя дори минимално физическо усилие. Методът, методът!? А, какво беше това метод? Трябва да си спомня това, което говореше асистентът. Само думи и думи, и думи... Някакви редове проблясват в ума ми и започвам мислено да пиша на бялото поле. Съзнанието ми сякаш с магия изрисува символите ->

	push(const T &a){
		Elem* temp=new Elem;
		temp->data=a;
		temp->next=top;
		top=temp;
	}

Това трябва да свърши работа. (Нали все пак съм в сън. Използвам компилатор, който разчита мислите ми и самият метод беше достатъчен. Явно подсъзнанието ми е било запаметило класа стек и другите методи.)

Всичко започва да се обърква, картините се размазват. Нещо започва да се надига. Извисявам се в небесата, защото методът „pop“ се е задействал. Не си спомням да съм му казвала да се появява. И полетях. Рея се аз из небесата върху цифрата 7 и срещам летящи оператори. Завалява дъжд от &&&&......

Не мога да си спомня метод за приземяване. Страх ме е от височината.

В този момент огромни, пъстри, зелени очи се появяват пред летящата цифра. И тъкмо да се сблъскам с тях..., се събуждам.

След като отворих очи, се замислих. Защо ли сънувах този страшен сън? Нима структурите от данни са кошмар за мен?

Катерина Ташева


Вдъхновена, може би от горното съчинение и от желанието да си вземе изпита, Нина Хъркова написа следното информатично интерпретативно съчинение:

Беше последната седмица преди сесията. Всеки ме притискаше да уча, даваше ми крайни срокове, а на мен ми беше дотегнало вече от всичко. Направих си чаша студен чай и седнах на терасата. Времето точно беше започнало да се затопля. Във въздуха се носеше мирис на пролет, а слънцето нежно галеше с топлите си лъчи. „Е, какво пък! - казах си - Ще поуча още малко!“. Знаех си, че да учиш по АСД е кошмарно, но все пак ми предстоеше изпит и трябваше да се подготвя добре. В този момент вратата се отвори и сестра ми влезе. Прибираше се отнякъде и носеше със себе си някаква игра. Погледнах обложката, но бързо изгубих интерес, защото върху нея имаше символи от АСД. Продължих да уча и съм се унесла!

Колко беше красиво! Голяма зелена поляна, разделена от дълга пътека, чийто край не се виждаше! Тръгнах по нея и се възхищавах на красивата природа! Изведнъж пред мен се появи сестра ми и носеше със себе си мистериозната игра. Любопитството ми надделя и ми се прииска да поиграем! Сестра ми отвори кутията и се озовахме в голяма стая с бели стени! На една от стените пишеше нещо. Приближих се и прочетох следното: „Последен влязъл, първи излязъл. Що е то? Ако не отговорите правилно ще се случи нещо лошо с вас.“ Внезапно стените започнаха да се движат една срещу друга и стаята започна да се смалява. Стъписах се и погледнах към сестра ми. Тя беше много уплашена и плачеше. „Влязъл-излязъл“. Какво беше това? Знаех го! Мислите се въртяха из главата ми. Метод „push“ , метод „pop“… Сетих се, сетих се - „Стек“. Изкрещях го силно. Стените спряха да се движат. Отдъхнах си. Това беше „стек“. Същият „стек“, който учихме по АСД.

Изведнъж на стената се появи друг надпис: „Първи влязъл, първи излязъл“ - Що ето? Стените започнаха пак да се движат. Приближаваха се към нас. На другата стена се появи монитор. На него се появи mail сървър, в който имаше писма. Първото от тях се изпращаше най-напред. О, да! Но това е „опашка“. „Опашка“! Изкрещях го и стените изчезнаха!

Но какво става? Това шега ли е? Пак АСД ни спаси. Огледах се. Бяхме в друга стая. По средата ѝ имаше голяма маса с два стола. Приближихме се и седнахме. На една от стените се появи врата и през нея влезе един мъж. В ръката си той държеше лаптоп. „О, не това вече е абсурдно! Пак ли компютри!“. Мъжът се приближи и каза „Помогнете ми!“. Остави лаптопа на масата и сякаш се изпари. Погледнахме към лаптопа. На монитора пишеше: „Това е игра и има две нива. За да се измъкнете от този кошмар трябва да ги преминете!“. Натиснахме „Yes“. Имахме ли друг избор.

И ето го и първо ниво: Имаме дадени данни в масиви, чийто брой не знаем. Как да ги съхраним?:
А) чрез пермутация;
Б) чрез динамичен масив;
В) чрез опашка.
„Имате 30 секунди за отговор.“

„Леле това го знаех. Мисли! Разделяме по-голям блок от памет и чак когато масивът се запълни заделяме нова.“ Да точно така. А секундите текат 10, 9, 8, 7, 6, 5, 4… Знам го!Б) Отговорът е Б) чрез динамичен масив. На екрана се изписва „correct“ на косъм бяхме на 3-тата секунда. „Първо ниво преминато!“ Следва второ. Какво? Това наистина ли се случва или сънувам?

„Второ ниво“: Какво е свързан списък? Имате 1 минута!

Мисли… мисли… Четох го… Знам го… О, не 35 секунди… Сетих се! Свързаният списък е структура от данни изградена от елементи, всеки от които съдържа някакви данни + информация, къде се намира следващият елемент от списъка. ................

„Нина, Нина, събуди се. Сънуваш кошмар!“ Събудих се и видях сестра ми над мен. Гледаше ме и се смееше. Наистина да си студент втори курс си е кошмар!

Нина Хъркова


Контролна 2

Група 1

Задача 1

Заменете x с числото образувано от последните 3 цифри от факултетния ви номер. Така полученото дърво, дърво за двоично търсене ли е?

Задача дърво

Задача 2

Заменете x с последната цифра от факултетния си номер.
Така получената структура от данни дърво или граф е, или и двете?
Ако е дърво го обходете постфиксно и запишете възлите в реда, в който са обходени.
Ако е граф запишете матрицата му на съседство.

Задача граф, дърво

Задача 3

Заменете x с числото образувано от последните 3 цифри от факултетния ви номер. Пресметнете стойността на получения обратен полски запис: 9 3 x * - 2 x * -

Отговори

Задача 1: 32 < x < 64 - да

Задача 2: Граф, но не и дърво. В дървото няма възли с 2 родителя. Матрица на съседство:

	0 1 1 0 0 0 0 0
	0 0 0 1 1 0 0 0
	0 0 0 0 0 1 1 0
	0 0 0 0 1 0 0 0
	0 0 0 0 0 0 0 0
	0 0 0 0 0 0 0 1
	0 0 0 0 0 0 0 1
	0 0 0 0 0 0 0 0

Задача 3: В инфиксен запис обратният полски запис изглежда така: 9 - 3 * x - 2 * x

Група 2

Задача 1

Заменете x с числото образувано от последните 3 цифри от факултетния ви номер. Така полученото дърво, дърво за двоично търсене ли е?

Задача дърво

Задача 2

Структурата от данни дърво или граф е, или и двете?
Ако е граф запишете матрицата му на съседство.

Задача граф, дърво

Задача 3

Заменете x с числото образувано от последните 3 цифри от факултетния ви номер. Пресметнете стойността на получения обратен полски запис: x 7 5 - * 2 / 9 +

Отговори

Задача 1: > 132 - да

Задача 2: И граф, и дърво. Матрица на съседство:

	0 1 1 0 0 0 0
	0 0 0 1 1 0 0
	0 0 0 0 0 1 1
	0 0 0 0 0 0 0
	0 0 0 0 0 0 0
	0 0 0 0 0 0 0
	0 0 0 0 0 0 0

Задача 3: В инфиксен запис обратният полски запис изглежда така: x * (7 - 5) / 2 + 9, което е еквивалентно на x + 9

Група 3

Задача 1

Заменете x с числото образувано от последните 3 цифри от факултетния ви номер. Така полученото дърво, дърво за двоично търсене ли е?

Задача дърво

Задача 2

Заменете x с последната цифра от факултетния си номер.
Така получената структура от данни дърво или граф е, или и двете?
Ако е дърво го обходете постфиксно и запишете възлите в реда, в който са обходени.
Ако е граф запишете матрицата му на съседство.

Задача граф, дърво

Задача 3

Заменете x с числото образувано от последните 3 цифри от факултетния ви номер. Пресметнете стойността на получения обратен полски запис: 3 x + 3 x * 2 / -

Отговори

Задача 1: Не, защото десният наследник на 299 е по-малък от него.

Задача 2: Граф, но не и дърво. В дървото няма възли с 2 родителя. Матрица на съседство:

	0 1 0 1 0 0
	0 0 0 1 0 0
	1 0 0 0 0 0
	0 0 0 0 0 0
	0 1 0 0 0 0
	0 0 1 0 1 0

Задача 3: В инфиксен запис обратният полски запис изглежда така: 3 + x - (3 * x) / 2

Група 4

Задача 1

Заменете x с числото образувано от последните 3 цифри от факултетния ви номер. Така полученото дърво, дърво за двоично търсене ли е?

Задача дърво

Задача 2

Заменете x с последната цифра от факултетния си номер.
Така получената структура от данни дърво или граф е, или и двете?
Ако е дърво го обходете постфиксно и запишете възлите в реда, в който са обходени.
Ако е граф запишете матрицата му на съседство.

Задача граф, дърво

Задача 3

Заменете x с числото образувано от последните 3 цифри от факултетния ви номер. Пресметнете стойността на получения обратен полски запис: 2 6 x - * x 2 * 2 / +

Отговори

Задача 1: 85 < x < 140 - да

Задача 2: Граф, но не и дърво. В дървото няма възли с 2 родителя. Матрица на съседство:

	0 0 0 0 0 0
	0 0 1 0 0 0
	1 0 0 0 0 0
	0 1 1 0 1 0
	0 0 0 0 0 0
	0 0 0 1 0 0

Задача 3: В инфиксен запис обратният полски запис изглежда така: 2 * (6 - x) + x * 2 / 2, което е еквивалентно на 12 - x

Резултати


Зад 1 - 7т. Зад 2 - 8т. Зад 3 - 10т. Общо
0701261033       0
0801261001       0
0801261002 7 8 10 25
0801261003       0
0801261004 7 8 8 23
0801261005 7 8 8 23
0801261006 0 8 0 8
0801261007 7 8 8 23
0801261008 7 8 3 18
0801261010 0 3 10 13
0801261011 7 8 10 25
0801261013       0
0801261014 7 8 0 15
0801261015       0
0801261017 7 8 10 25
0801261018 7 8 0 15
0801261019 0 8   8
0801261021 7 8 0 15
0801261022 7 6 3 16
0801261024 7 8 10 25
0801261025 7 8 10 25
0801261026 7 8 0 15
0801261027 7 8 0 15
0801261029 0 8 10 18
0801261032       0
0801261033       0
0801261034 7 8 8 23
0801261036 7 8 10 25
0801261037 7 7 0 14
0801261038       0
0801261040 7 8 10 25
0801261042       0
0801261043 0 8 0 8
0801261044       0
0801261045       0
0801261046       0
0801261047 7 8 3 18
0801261048 0 8 0 8
0801261049 7 8 10 25
0801261051 0 8 10 18
0801261052       0
0801261053 7 8 0 15
0801261054 7 8 8 23
0801261055 7 8 10 25
0801261056 0 8 10 18
0801261057 0 8 3 11
0801261058       0
0801261059 0 8 10 18
0801261061 0 8 8 16
0801261062 7 8 0 15
0801261063 7 8 10 25
0801261064 7 8 10 25
0801261065 7 8 8 23
0801261066 0 8 0 8
0801261067 7 8 10 25
0801261068 7 8 5 20
0801261069 0 8 0 8
0801261071 7 8 10 25
0801261072 0 8 0 8
0801261073 0 8 3 11
0801261075 7 5 5 17
0801261076 7 8 8 23
0801261077 7 8 0 15
0801261078 7 8 0 15
0801261079 0 8 0 8
0801261080 7 8 7 22
0801261081 0 8 0 8
0801261083 7 8 0 15
0801261084 7 8 0 15
0801261086 7 3 8 18
0801261087 7 8 0 15
0801261088       0
0801261089 7 8 8 23
0801261090 7 8 0 15
0801261093 7 8 0 15
0801261094 0 8 10 18
0801261096       0
0801261097 7 8 0 15
0801261098       0
0801261099 7 8 0 15
0801261100 7 8 0 15
0801261101 7 5 0 12
0801261102       0
0801261103 7 8 0 15
0801261104       0
0801261105 7 5 0 12
0801261106 0 8 0 8
0801261107       0
0801261108 0 7 10 17
0801261109 0 8 0 8
0801261110 0 7 10 17
0801261111 0 8 0 8
0801261113 0 7 10 17
0801261114 7 8 10 25
0801261116 7 5 0 12
0801261117 7 8 10 25
0801261118       0
0801261119       0
0801261120 0 8 0 8
0801261121 0 8 0 8
0801261122 0 8 5 13
0801261124 7 5 0 12
0801261125 7 0 10 17
0801261126       0
0801261127 7 8 0 15
0801261128       0
0801261129 7 8 10 25
0801261130       0
0801261132       0
0801261133 7 5 3 15
0801261134       0
0801261135 7 8 10 25
0801261136 0 8 3 11
0801261137 7 5 0 12
0801261138 7 8 10 25
0801261140 7 8 0 15
0801261141       0
0801261142 7 8 0 15
0801261143 7 8 0 15
0801261144 0 8 10 18
0801261145 7 8 10 25
0801261146 0 5 0 5
0801261147 0 5 0 5
0801261148 7 8 10 25
0801261151 7 8 10 25
0801261152       0
0801261153 7 8 10 25
0801261155       0
0801261156 0 5 10 15
0801261162 7 8 0 15
0801261165       0
0901261038 0 5 10 15
0901261056 3 8 0 11
0901261076 7 8 8 23
0901261124 7 8 0 15
0901261131 7 0 0 7
0901261132 7 7 3 17
0701261104 7 8 0 15
0701261097       0
0226062       0

Главна страница