|
Национална академия по разработка на софтуер
Уеб сайт: http://academy.devbg.org
тел./факс: +359 (2) 958-9965
|
Практически изпит по програмиране за прием в “Национална академия по разработка на софтуер”
Практическият изпит за прием на студенти в НАРС има за цел да оцени уменията на кандидатите за справяне с реални задачи по програмиране. Очаква се всички кандидати да имат базови познания по структури от данни и обектно-ориентирано програмиране и да могат да програмират на поне един съвременен обектно-ориентиран език.
Изпитът изисква решаване на 3 задачи по програмиране на компютър за 4 часа. Допуска се използване на език за програмиране по избор (вж. Езици за програмиране и среди за разработка).
Конспект -
Структури от данни и алгоритми
-
бройни системи
-
примитивни типове данни и масиви
-
списъци, стекове, опашки, дървета, хеш-таблици
-
рекурсия
-
алгоритми за сортиране и търсене
-
Обектно-ориентирано програмиране (ООП)
-
принципи на ООП – абстракция, енкапсулация, наследяване, полиморфизъм
-
класове, обекти, интерфейси, наследяване, абстрактни класове
-
полета, методи, статични полета, статични методи
-
конструктори и деструктори
-
управление на изключенията
-
обектно-ориентирано моделиране
-
Базови умения по програмиране
-
вход/изход, работа с текстови файлове
-
обработка на символни низове
Примерна тема -
Да се напише програма, която намира всички думи от даден текстов файл words.in и за всяка от тях определя колко пъти се среща във файла. Намерените думи трябва да се подредят в намаляващ ред по честотата им на срещане (и по азбучен ред при еднаква честота) и да се запишат във файл words.out във формат <дума> <брой_срещания>. Програмата трябва да не прави разлика между малки и главни букви. Входният файл съдържа текст на кирилица с кодиране „windows-1251” и размерът му не надвишава 10 MB.
Примерен входен файл words.in:
Приемен изпит за НАРС. Комисията препоръчва на всички кандидати да четат внимателно условията на задачите и да спазват формата на входните и изходните файлове.
Успех на всички!
|
Примерен изходен файл words.out:
на 4
всички 2
да 2
и 2
внимателно 1
входните 1
за 1
задачите 1
изпит 1
изходните 1
кандидати 1
комисията 1
нарс 1
препоръчва 1
приемен 1
спазват 1
условията 1
успех 1
файлове 1
формата 1
четат 1
|
Примерно решение на C#:
using System;
using System.Collections;
using System.Globalization;
using System.IO;
using System.Text;
using System.Threading;
class WordAndCount : IComparable
{
public string mWord;
public int mCount;
public WordAndCount(string aWord, int aCount)
{
mWord = aWord;
mCount = aCount;
}
public int CompareTo(object aObject)
{
WordAndCount wordAndCount = (WordAndCount) aObject;
int compareResult = wordAndCount.mCount.CompareTo(mCount);
if (compareResult == 0)
{
compareResult = mWord.CompareTo(wordAndCount.mWord);
}
return compareResult;
}
}
class FindWordsAndCountsInTextFile
{
const string INPUT_FILE_NAME = "words.in";
const string OUTPUT_FILE_NAME = "words.out";
private static Hashtable mWords = new Hashtable();
private static void ProcessWord(string aWord)
{
if (aWord != "")
{
string wordLowerCase = aWord.ToLower();
WordAndCount wordAndCount = (WordAndCount) mWords[wordLowerCase];
if (wordAndCount != null)
{
wordAndCount.mCount++;
}
else
{
wordAndCount = new WordAndCount(wordLowerCase, 1);
mWords[wordLowerCase] = wordAndCount;
}
}
}
static void ExtractWords(TextReader aReader)
{
StringBuilder buffer = new StringBuilder();
while (true)
{
int nextValue = aReader.Read();
if (nextValue == -1)
{
string word = buffer.ToString();
ProcessWord(word);
break;
}
char nextChar = (char) nextValue;
if (Char.IsLetter(nextChar))
{
buffer.Append(nextChar);
}
else
{
string word = buffer.ToString();
ProcessWord(word);
buffer.Length = 0;
}
}
}
private static WordAndCount[] GetWordsAndCounts()
{
WordAndCount[] wordsAndCounts = new WordAndCount[mWords.Count];
int index = 0;
foreach (WordAndCount wordAndCount in mWords.Values)
{
wordsAndCounts[index] = wordAndCount;
index++;
}
return wordsAndCounts;
}
private static void PrintResults(TextWriter aWriter,
WordAndCount[] aWordsAndCounts)
{
foreach (WordAndCount wordAndCount in aWordsAndCounts)
{
aWriter.WriteLine("{0} {1}",
wordAndCount.mWord, wordAndCount.mCount);
}
}
static void Main()
{
Thread.CurrentThread.CurrentCulture = new CultureInfo("BG-bg");
StreamReader reader = new StreamReader(INPUT_FILE_NAME,
Encoding.GetEncoding("windows-1251"));
using (reader)
{
ExtractWords(reader);
}
WordAndCount[] wordsAndCounts = GetWordsAndCounts();
Array.Sort(wordsAndCounts);
StreamWriter writer = new StreamWriter(OUTPUT_FILE_NAME, false,
Encoding.GetEncoding("windows-1251"));
using (writer)
{
PrintResults(writer, wordsAndCounts);
}
}
}
|
Примерното решение пази в една хеш-таблица за всяка дума клас, в който записва самата дума и броя срещания. В началото се сканира входният файл буква по буква и при намиране на дума за нея се обновява информацията в хеш-таблицата. След това намерените думи заедно с броя им срещания се записват в масив и се сортират като се използва подходящ метод за сравнение (компаратор). Накрая се отпечатва сортираният масив.
-
Дадена е редица от N цели числа (1 < N < 10 000). Да се напише програма, която премахва 0 или повече от елементите на входната редица, така че оставащите елементи да образуват редица от нарастващи по големина елементи и дължината на получената редица да е максимална. Входният файл sequence.in съдържа числото N на първия си ред и N цели числа на следващите N реда. Изходният файл sequence.out трябва да съдържа на първия си ред числото L – дължина на намерената максимална подредица, а на следващите L реда трябва да стоят нейните елементи.
Примерен входен файл sequence.in:
Примерен изходен файл sequence.out:
Илюстрация на примера:
Примерно решение на C#:
using System;
using System.IO;
class MaximalIncreasingSequence
{
const string INPUT_FILE_NAME = "sequence.in";
const string OUTPUT_FILE_NAME = "sequence.out";
const int NO_PREVIOUS = Int32.MaxValue;
static void Main()
{
// Read the input sequence
int n;
int[] seq;
StreamReader reader = File.OpenText(INPUT_FILE_NAME);
using (reader)
{
string s = reader.ReadLine();
n = Int32.Parse(s);
seq = new int[n];
for (int i=0; i
{
string nextValue = reader.ReadLine();
seq[i] = Int32.Parse(nextValue);
}
}
// Find for each index the maximum sequence finishing in it
int[] max = new int[n];
int[] prev = new int[n];
int bestSequenceEnd = 0;
for (int i=0; i
{
max[i] = 1;
prev[i] = NO_PREVIOUS;
for (int j=0; j
{
if (seq[j] < seq[i] && max[j] >= max[i])
{
max[i] = max[j] + 1;
prev[i] = j;
if (max[i] > max[bestSequenceEnd])
{
bestSequenceEnd = i;
}
}
}
}
// Extract the best sequence from the initial sequence
int[] resultSeq = new int[n];
int len = 0;
int currentIndex = bestSequenceEnd;
while (currentIndex != NO_PREVIOUS)
{
resultSeq[len] = seq[currentIndex];
len++;
currentIndex = prev[currentIndex];
}
// Print the solution
StreamWriter writer = new StreamWriter(OUTPUT_FILE_NAME);
using (writer)
{
writer.WriteLine(len);
for (int i=len-1; i>=0; i--)
{
writer.WriteLine(resultSeq[i]);
}
}
}
}
|
Примерното решение сканира входната редица отляво надясно и за всяка позиция i от нея изчислява дължината на максималната нарастваща подредица max[i], започваща някъде преди позиция i и завършваща в позицията i. За изчислението на max[i] се търси елемент вляво от позиция i, който е по-малък от i-тия и е край на възможно най-дълга подредица. Сложността на решението е Θ(N2).
Забележка: За тази задача съществува и по-ефективно решение със сложност Θ(N*log(N)), но няма да се спираме на него.
-
Търговска фирма планира създаване на система за управление на личен състав и складови наличности. Фирмата има няколко склада. Във всеки склад работят служители на фирмата, като един от тях е началник на склада. Един служител може да е началник на няколко склада едновременно. За всеки служител се съхранява следната информация:
-
трите имена
-
ЕГН
-
адрес
-
телефон
-
заемана длъжност
-
началник (друг служител на фирмата)
За служителите, които заемат ръководна длъжност, се поддържа списък от пряко подчинените им служители.
За всеки склад фирмата съхранява следната информация:
-
адрес
-
телефон
-
списък от служителите, които работят в склада
-
управител на склада (служител на фирмата, пряк началник на другите служители от склада)
-
наличности в склада
Фирмата поддържа информация за наличностите от стоки във всеки склад. За всеки артикул в складовете се съхранява следната информация:
-
наименование на артикул (напр. „бира Загорка”)
-
фирма производител (име, адрес, телефон, факс, e-mail, web-сайт)
-
мерна единица (брой, килограм, литър и др.)
-
налично количество
Собственикът на фирмата е също неин служител. За него се поддържа списък от складовете и списък от всички началници.
Да се проектира съвкупност от класове с връзки между тях, които моделират данните за служителите и складовете във фирмата, както и наличностите във всеки склад.
Примерно решение на C#:
class Employee
{
string firstName;
string middleName;
string lastName;
string egn;
string address;
string phone;
string position;
Manager manager;
}
class Manager : Employee
{
Employee[] managedEmployees;
Warehouse[] managedWarehouses;
}
class Warehouse
{
string address;
string phone;
Employee[] employees;
Manager manager;
Product[] products;
}
class Product
{
string name;
Company manufacturerCompany;
Measure measure;
double ammountAvailable;
}
class Company
{
string name;
string addres;
string phone;
string email;
string fax;
string webSite;
}
enum Measure
{
Count,
Kilogram,
Liter
}
class Boss : Employee
{
Warehouse[] warehouses;
Manager[] managers;
}
| Оценяване
Критериите, по които се оценява работата на кандидатите (подредени са по важност):
-
коректност на решението – правилно ли работи програмата при всеки набор входни данни
-
чистота на програмния код – четим и разбираем ли е кодът
-
ефективност – работи ли програмата с приемлива скорост за всеки набор от входни данни
Езици за програмиране и среди за разработка
В изпитната зала на всяко работно място ще има инсталиран следният софтуер:
-
Microsoft Windows XP with SP2 – операционна система
-
Microsoft .NET Framework SDK 1.1 SP1 – компилатори и инструменти за разработка и изпълнение на .NET приложения
-
Microsoft Visual Studio .NET 2003 – компилатор и среда за разработка за езиците C, C++, C# и VB.NET
-
JDK 1.4.2 – компилатори и инструменти за разработка и изпълнение на Java приложения
-
Eclipse 3.1 – включва среда за разработка за езика Java
-
Delphi 2005 – компилатор и среда за разработка на езика Pascal за платформа Win32 и за езиците Pascal и C# за платформа .NET
-
Perl 5.8.7 – компилатори и инструменти за разработка и изпълнение на Perl приложения
-
PHP 5.0 – компилатори и инструменти за разработка и изпълнение на PHP приложения
-
Komodo 3.1 – среда за разработка за езиците Perl и PHP
-
Microsoft Visual Basic 6.0 – среда за разработка за VB6
Други условия
Изпитът се състои от 3 задачи, които трябва да се реализират в рамките на 4 часа.
На всяко работно място ще има достъп до Интернет. Разрешава се използване на книги и други помощни учебни материали.
По време на изпита се забранява използването на всякакви средства за комуникация – мобилни телефони, ICQ, MSN Messenger, e-mail, форуми и др.
При опит за преписване от някого, подсказване или използване на средства за комуникация изпитът на кандидата се анулира.
Литература за подготовка -
Робърт Седжуик, Алгоритми на C, СофтПрес, 2002, ISBN: 9546852171
-
Лендерт Амерал, Алгоритми и структури от данни в С++, Софтех, София, 2001, ISBN: 9548495252
-
Магдалина Тодорова, Програмиране на С++, част 1 и 2, Сиела, София, 2002, ISBN: 9546494542
-
Авторски колектив, Ръководство по програмиране и използване на компютри (част втора С++), Сиела, София, 2001, ISBN: 9546493716
-
Джон Монтаг, Ноа Суджанен, Интервюта за програмисти, Софтех, София, 2002, ISBN: 9548495260
-
Преслав Наков, Панайот Добриков, Програмиране=++Алгоритми; трето издание, TopTeam Co., 2004, ISBN 954890506
Сподели с приятели: |
