В-с 1

Результаты экзамена по курсу

Алгоритмы и алгоритмические языки.

Зима 2012г.

В-с 1

В-с 2

Задача

Оценка

Аипов_9

Ан_3

Давыдов_21

Денисова_5

Исраилов_13

Квон_15

КимАлександр_6

Ларгин_10

Мартынов_6

Мухамеджанов_05

Насретдинов_23

Сегаль_4

Тукфатуллина_14

Хайдаров_16

Шигабутдинов_10

Askarova_19

Cherkasova_15

Don_12

Garipov_11

Gurinov_22

Jamolov_17

Khotami_2

Kostyuk_16

Li_09

Solovyev_21

Suyarav_18

totrashvili_18

Usmanov_11

Uzokov_23

umarov_03

Гуламов_12

Тян_4

+/2

5 (отл)

4(хор)

3(удовл)

4(хор)

3(удовл)

5 (отл)

4(хор)

5 (отл)

5(отл)

4(хор)

3(удовл)

5(отл)

4(хор)

5 (отл)

3(удовл)

4(хор)

5 (отл)

4(хор)

5 (отл)

4(хор)

3(удовл)

Приношу извинения за способ написания фамилий. Исправить не сложно, но я боюсь внести при этом дополнительные ошибки (т.к. при этом надо будет переупорядочить строки таблицы, а у меня на все это сил уже нет), поэтому пусть все будет, как будет.

Многие вопросы написаны как под копирку и я, при этом, старался давать комментарии таким же способом.

Для того, чтобы увидеть работы, я прилагаю сканы ответов на теоретические вопросы и на задачи .

У вас есть несколько дней на исправление каких-то непоняток (на апелляцию). Безусловно, я мог где-то ошибиться и как-то не туда посмотреть или что-то не заметить.

Общие замечания по задачам

Откуда такая любовь к функции fscanf при работе с текстом? В задачах с #define лучше бы было что-то вроде следующего:

{char str[512],word1[512],word2[512]; FILE *f;

…

while(fgets(str,512,f))

{

if(sscanf(str,”%s %s”,word1,word2)==2 && strcmp(word1,”#define”)==0)

{//word2 – требуемое имя

…

}
}

Здесь, конечно, есть проблема с длиной строки, но я бы ее игнорировал, а если бы было очень нужно, то смог бы написать функцию, вводящую строку из текстового файла, на которую не налагается ограничений на длину.

Константы. Я про все это рассказывал. Константа, записанная десятичными числами, имеет тип int, но если она не умещается в этот тип, то ее размер может быть увеличен, если в данном языке есть целые переменные большего размера. Если первая цифра 0, то это – константа в восьмеричном представлении, иначе – в десятичном. Если перед цифрами стоит 0x, то представление шестнадцатеричное (еще раз: это представление, а не тип). После проверки этого экзамена я нашел в сети на неком сайте дословно слова: По умолчанию компилятор приписывает константе тип наименьшего размера, в ячейку которого может уместиться константа. Это не правда. Хотя, должен признать, это мало на что влияет. Замечу, что при прочтении этой ссылки вас должно было насторожить то, что там упоминаются 16-битные целые константы. На персоналках этого нет уже много лет. На современных компиляторах в современных ОС обычно размер переменных типа short int меньше размера переменных типа int (раньше эти размеры обычно совпадали).

Почему-то для сравнения строк все используют strstr(), вместо strcmp().

НИКТО не вспомнил про циклическую очередь, а ведь именно так ее всегда и реализуют.

Аипов_9

Задача:

Программа будет неправильно работать, если где-то в строковых константах встретиться слово #define, ну да ладно.

Чисто эмоциональное замечание: мне не нравятся следующие операции:

char* s2;

s2="#define";

Лучше:

char s2[]="#define";

Разница: в первом случае взят обычный указатель, который перенаправлен на кусок памяти, в котором содержатся символы "#define", а во втором случае создан обычный массив длины 8, инициализированный соотв. данными. В первом случае, на самом деле, статус памяти, на которую перенаправлен указатель, не очень ясен, что может привести к ошибкам при попытке записи по этому указателю (если это в дальнейшем сделать по ошибке). Кроме того (это важно, например для С++) происходит присваивание переменных разных типов: справа от знака присваивания стоит const char*, а слева – char*. Для С++ это может быть ошибкой (а может и не быть!).

Ан_3

2. Константа – не ячейка памяти! Это принципиально.

Это непонятно:

Это неверно:

Это не константы:

Символьные константы можно присвоить символьным переменным, а эти обозначения символьным переменным присвоить нельзя.

Задача.

Совершенно неоправданно использование ф-ции strstr. Это – ф-ция поиска, а здесь, вроде, подразумевается сравнение. Ну и, конечно, ошеломил цикл:

while(i,strlen(d))

{

fprintf(out,"%c",d[i]);

i++;

}

Здесь программа сразу же и упадет.

Давыдов_21

2. см замечания на предыдущей странице.

Задача. В целом все очень похоже на правду, но, к сожалению, программа работать не будет. Дело в том, что ф-ция realloc здесь в чистом виде неприменима. После ее применения кусок памяти с элементами списка переместится и все ссылки на предыдущие/следующие элементы станут недействительными. Более того, ф-ция realloc применяется неправильно по существу (указывается недостаточное количество требуемой памяти).

Денисова_5

1. Боюсь, это полная бессмыслица:

Объяснения сортировки подсчетом нет.

Цифровая сортировка: не сказано о самом главном: используемые сортировки должны быть устойчивыми, без этого алгоритм работать не будет.

Задача. Я, кажется, рассказывал, что так писать нельзя:

while(fscanf(fin,"%s",&s)==1)

так тоже:

scanf("%s",&fnameIn);

scanf("%s",&fnameOut);

Постарайтесь выяснить, почему!

Совершенно неоправданно использование ф-ции strstr. Это – ф-ция поиска, а здесь, вроде, подразумевается сравнение.

Исраилов_13

1. Ладно, допустим, Вы просто забыли написать, что всем вершинам надо изначально присвоить значение =-1.

Это не так. Вы нашли длину кратчайшего пути, но сам путь не нашли.

Даже если добавить недостающее для нахождения решения, у Вас не д-ва того, что то, что получилось – решение.

Квон_15

1. Это же не алгоритм:

Дальнейшее описание алгоритма на формальном языке дано без объяснений. Обоснований никаких нет.

А что это значит?

Это не точно:

С точки зрения операционных систем, в которых мы работаем, нет разницы между текстовыми и бинарными файлами, но мы их можем интерпретировать как текстовые или бинарные файлы. Т.е. ”rb” это просто задание способа интерпретации файла.

Такого параметра у ф-ции fprintf нет. Имя файла присутствует только в ф-ции fopen, а все остальные ф-ции ссылаются на переменную типа FILE*.

У ф-ции fscanf не три параметра, а переменное количество параметров.

Задача. В задаче не сделано, практически, ничего.

КимАлександр_6

В сортировке подсчетом даже нет указания, где получится отсортированный массив.

Маловато для объяснения алгоритма.

2. Содержательного определения рассматриваемых понятий нет.

Задача. К сожалению, программа работать не будет. Дело в том, что ф-ция realloc здесь в чистом виде неприменима. После ее применения кусок памяти с элементами списка переместится и все ссылки на предыдущие/следующие элементы станут недействительными. Более того, ф-ция realloc применяется неправильно по существу (указывается недостаточное количество требуемой памяти).

Ларгин_10

Так очередь не реализуется никогда. Это слишком медленно. Используется только циклическая реализация очереди. То же самое для дека.

Это не верно. Локальность относится к области видимости, но не к времени жизни. Локальные переменные могут быть как автоматическими, так и статическими.

Это не верно. Например, глобальные переменные – статические, но слова static перед их определением нет. У Вас полная путаница с понятиями.

Боюсь, к перегрузке это не имеет никакого отношения.

Задача.

Как ни странно следующее верно:

for (i=1; fscanf(in,"%d",&num)&&fscanf(in, "%d", &denum)==1; i++, counter+=2)

Но я, почему-то, уверен, что Вы не понимаете, почему.

Список в программе не создается. Функция realloc выделяет недостаточно памяти.

Мартынов_6

1. Сортировка подсчетом: yеверно практически все:

Ну подумайте, что Вы пишете! Зачем пересчитывать к-во элементов в исходном массиве??? А вы что, не знаете, сколько их там? Что такое n – вообще не объясняется, а то, что пишется в этой фразе в конце – к алгоритму отношения не имеет.

В общем, все списано из того же источника, что и у Денисовой. И ошибки те же.

Мухамеджанов_05

но это же – полная бессмыслица. Что имеется в виду под определенным числом? Зачем считается сумма элементов? И идущих до него где? Почему получается отсортированный массив?

Что имеется в виду под первым, вторым…? Если по порядку, то это не верно. Ничего не сказано про приоритеты.

вообще-то, левый от правого

Задача. Программа будет неправильно работать, если где-то в строковых константах встретиться слово #define.

Насретдинов_23

это не верно.

это не совсем так. Пример: следующие выражения не есть одно и то же:

y=(x++);

y=(x=x+1);

постарайтесь в этих примерах разобраться.

Задача.

Это не верно:

mass=(elem*)malloc(i+n*sizeof(elem)+1);

памяти выделяется недостаточно.

Непонятно, зачем было делать объединение. На 64-битной архитектуре это съест памяти вдвое больше, чем требовалось для решения задачи. Ну да ладно.

Сегаль_4

мы отрезаем элемент, а что потом с ним делать?

Задача. Эту задачу в принципе нельзя было решать по шаблону, по которому все делали задачи с поиском директив #define. Неправильно почти все. Директивы #const_char не существует. strstr используется не по делу. И т.д.

Тукфатуллина_14

Хайдаров_16

1. Нет определения бинарного дерева поиска. А без этого поиск элементов (в том виде, в котором он написан) невозможен. Ладно, простим.

Задача. Все похоже на правду, но УЖАСНО коряво. При таком стиле программирования правильно написать нормальную программу невозможно. Например, зачем писать

*(a+i+1)-*(a+i) если можно написать a [i+1]-a[i]. Зачем писать *(*(a+k)+j), если можно написать a[k][j].

Мысль класть целое число в указатель не очень хороша, хотя на всех последних компиляторах, на которых я работал, это будет работать. Проблема в том, что язык Вам не гарантирует, что указатель имеет размер не меньше размера целого числа (заметим, что в реальности их размеры могут и не совпадать, например, на 64-битной архитектуре это, скорее всего, будет так).

Шигабутдинов_10

1. Я не зачел этот вопрос, т.к. практически ничего не сказано про реализацию. А здесь это – самое важное. Следующее почти бессмысленно:

действительно, по логике в пунктах 1) и 2) должны стоять условия, а там почему-то стоит действие.

это не верно. Их можно объявлять где угодно вне всех блоков.

Задача. В ф-ции main при вводе данных с клавиатуры ф-ция решения задачи не вызывается.

К сожалению, программа работать не будет. Дело в том, что ф-ция realloc здесь в чистом виде неприменима. После ее применения кусок памяти с элементами списка переместится и все ссылки на предыдущие/следующие элементы станут недействительными. Более того, ф-ция realloc применяется неправильно по существу (указывается недостаточное количество требуемой памяти).

Askarova_19

Задача. До конца не доведена. Память, фактически, не выделена.

Cherkasova_15

1. Какая-то бессмыслица:

Что имеется в виду под какой-нибудь из вершин?

Если есть ближайшая к a вершина – что имеется в виду?

Что делает один шаг алгоритма?

Это не верно с любой точки зрения. И сообщений никаких не появляется, да и ошибкой это не всегда считается.

имя файла там нигде не записывается.

это не верно. При чем тут имя файла?

это, конечно, верно, но никаких упоминаний о буфере ранее не было, так что это как-то непонятно.

Задача. Количество элементов в массиве взято неизвестно откуда. В алгоритме можно только один раз отвести доп. память (с размером исходного массива), а в программе память отводится много раз. Переменная i во внутреннем цикле не инициализируется. И т.д.

Don_12

списано не полностью, поэтому выглядит, мягко говоря, странно.

что имеется в виду под именами? Синтаксис неверный.

это, вообще говоря, не так. Никакого присвоения может и не быть.

Задача.

В следующем сразу две ошибки:

m=(int**)malloc((count-1) * sizeof(int));

найдите, какие. А здесь ошибка одна:

m[i]=(int*)malloc((size-1)*sizeof(int));

Garipov_11

Задача. Требуется написать алгоритм сортировки слиянием с рекурсией. В программе рекурсии нет. Далее сразу же замечаем, что память отводим под одни указатели, а данные вводим по вообще неинициализированному указателю. Кстати, компилятор должен был замечание выдать. Дальше еще веселее. В массивы massiv_1 и massiv_2 заносятся данные, расположенные сразу ПОСЛЕ массива massiv2 (т.к. переменная k не инициализирована). И т.д.

Gurinov_22

1. Содержательного ответа нет.

2. Эх, как все хорошо написано. Не было бы последней фразы и было бы ощущение, что Вы все хорошо понимаете:

Объединение ничего общего с преобразованием типов не имеет!

Jamolov_17

Это не верно. Забыто условие на корневой элемент.

В поиске минимального элемента не рассмотрен случай, когда правого потомка нет.

2. Я обещал ОЧЕНЬ сильно ругаться, если кто-то скажет, что stdlib.h – библиотека:

Это не переводится никак, т.к. является сокращением memory allocation, а вот последнее уже можно переводить.

Задача. А зачем вызывать ф-цию решения задачи три раза???

Khotami_2

Это пишется про пузырек. Это верно, но требуется писать не это (опять же: в каком смысле в среднем ?).

2. На самом деле, неточности есть, но я упомяну только одну: Вы по определению не можете знать размер переменных. Использование этих данных делает Вашу программу абсолютно непереносимой на другие компиляторы/машины.

Задача.

Начнем с того, что пользоваться ф-цией fscanf в данном случае нельзя. Она считывает слова, а это не то, что нам надо (а надо нам выделать идентификаторы). Далее заметим, что если заглавная буква в слове не встретилась, то прочитанное слово вообще никуда не выводится. Далее:

if (isalpha(temp1[i])==1 && temp1[i]==toupper(temp1[i]))

{

temp2[j]='_'; j=j+1;

temp2[j]=tolower(temp1[i]); j=j+1;i=i+1;

}

isalpha(temp1[i]) нельзя сравнивать с 1 (можете почитать в документации, что эта штука возвращает [заметьте, я не написал функция])

Kostyuk_16

Как-то это очень грубо. input – не имя потока, а имя переменной, с которой поток ассоциируется. Файл не может содержаться в потоке. Поток – канал, по которому происходит связь с файлом.

*(m+i+1)-*(m+i) если можно написать m[i+1]-m[i]. Зачем писать *(*(m + rowNum) + j), если можно написать m[rowNum][j].

Li_09

1. Тут идет какая-то путаница. Есть структуры данных и есть структуры в языке С. Вообще-то, это разные понятия. С этой точки зрения, следующая фраза неверна:

Про реализацию структур данных вообще ничего не говориться, а это – основная часть билета.

Следующая фраза смысла не несет:

А вот это уже шедевр:

Внимательное прочтение следующего абзаца приводит к мысли, что в нем написана полная бессмыслица:

Переменная px никак не определена, вместо этого везде парит неведомый объект p. Кто, или что это?

Задача. Не сделана.

Solovyev_21

Любимый анекдот: эллипс – это круг, вписанный в квадрат размером 3 на 4.

Вы уж разберитесь, если константа – фиксированное значение, то как же ее можно изменить?

Черт, да почему все в этом так уверены? Откуда вы все это взяли? Это неверно.

Suyarav_18

1. Где доказательства?

Теорема о высоте сбалансированного дерева не сформулирована.

totrashvili_18

1. Где доказательства?

У меня было другое определение идеально-сбалансированного дерева. И данная теорема доказывалась для другого определения (я не утверждаю, что Ваша теорема неверна!).

Usmanov_11

Задача.

В данном случае использование округления бессмысленно:

tmp = (int)ceil((double)begin+middle)/2;

Внутри функции сортировки использовать отведение памяти нельзя, иначе функция сортировки будет слишком медленной и ее использование теряет смысл.

Uzokov_23

1. Доказательств никаких. Определения связного множества нет.

Задача.

Это не верно:

mass=(elem*)malloc(i+n*sizeof(elem)+1);

памяти выделяется недостаточно.

umarov_03

Все наоборот! Сначала выбирается некоторое значение и половины массива создаются так, чтобы элементы первой половины были бы меньше или равны данного значения, а элементы второй половины – больше или равны. И ИЗ ЭТОГО следует, что все элементы первой половины меньше или равны элементов второй половины.

2. Константа – не ячейка памяти! Это принципиально.

это не верно.

Задача. Программа будет неправильно работать, если где-то в строковых константах встретиться слово #define.

Гуламов_12

Это не верно. Это - определение смежных вершин (про это слово ничего не упоминается). Ничего не говорится про симметричность определений с точки зрений понятий вершины и ребра.

Хотелось бы видеть реализации, которые реально применяются. Массив ребер – слишком неудобная реализация, с которой работать слишком медленно. На лекциях были гораздо более содержательные реализации.

Синтаксис неверный. Везде вместо запятых должны быть точки с запятой.

???

Тян_4

1. Шаги алгоритма указаны (хоть и с неправильным обозначением), но самого алгоритма нет.