Определить, является ли самоприменимым следующий алгоритм W. в расширенном алфавите A={a, b}.

в расширенном алфавите A={a, b}.

W:

Дать ответ (ДА\НЕТ) и привести его обоснование.

 

 

4. Для заданной последовательности ключей 1, 2, 3, 4, 5, 6, 7 - построить АВЛ-дерево в соответствии с алгоритмом построения АВЛ-деревьев. Проставить характеристики в узлах дерева.

 

 

5. Определить, что будет выдано на печать:
program B (output);

var x, y, z: integer;

procedure Q (x: integer; var y: integer);
begin z:= x; x:= y; y:= z end;
begin x:= 1; y:= 2; z:= 3; Q(x, x); writeln(x, ‘ ‘, y, ‘ ‘, z) end.

 

 

6. В перемешанную таблицу Т[0..12] с функцией первичного перемешивания

I = K mod 13, функцией вторичного перемешивания I = (I+3) mod 13,(K – ключ) записаны ключи. Каким может быть минимальное число ключей, хранящихся в таблице Т, если известно, что ключ 41 записан по адресу 8, а ключ 24 - по адресу 7. Ответ обосновать.

 

3. Разработка критериев оценки при реализации первого этапа письменного тестирования по специальности.

 

3.1. Решения и критерии оценки задач для тематических задач варианта – образца письменного тестирования

 

1. Ответ: 1 5 6

Критерии: за каждое неправильное число, за непонимание параметра вывода вида x: n – снижать на 1/3

2. function Nmax(var f: T): integer;

var max, k, x: integer;

begin reset(f);

read(f,max); k:=1;

while not eof(f) do

begin read(f,x);

if x>max then begin max:=x; k:=1 end else

if x=max then k:=k+1

end;

Nmax:=k

end;

Критерии:

ошибки в алгоритме поиска максимального значения (не умеет искать максимум), более одного просмотра файла – сразу минус

за каждую другую ошибку при работе с параметрами и файлами (нет var перед f, нет reset и т.п.) – снижать на 1/3

3. Для поиска вершины с максимальным элементом (max) необходимо «идти» от корня всё время вправо до вершины, из которой нет ветви вправо. Для реализации удаления этой вершины необходимо в предыдущей вершине заменить правую ссылку на левую ссылку из вершины с max. Если max – в корне, то надо менять Т.

procedure Del(var T: дерево);

var p: дерево;

begin

if T­.прав=nil then begin p:=T; T:= T­.лев; dispose(p) end

else Del(T­.прав)

end;

 

Критерии:

непонимание определения дерева поиска и, как следствие, усложнение задачи, сведение алгоритма к перебору всех вершин – сразу минус

неумение применить рекурсию (есть цикл или оператор перехода) – сразу минус

не рассматривается случай нахождения максимального значения (max) в корне дерева, нет var перед Т – снижать на 2/3

за каждую другую ошибку – снижать на 1/3

 

4.

 

 

Критерии:

высота дерева не равна 4, неправильная структура дерева – сразу минус

правильную структуру дерева (без учета ключей) – оценивать в 1/3

правильную расстановку ключей – оценивать в 2/3

за один или за пару взаимно неправильно расставленных ключей – снижать на 1/3

 

5. Указанный вид таблицы возможен при С=7. Последние записываемые в таблицу три ключа выделены.

 

I
K

 

Критерии:

за ответ «невозможный вид» – ставить минус

за каждый неправильно размещенный ключ – снижать на 1/3

 

6. В соответствии с приведенным определением, < прим > – это слова вида aⁿb^m, где n > m ³ 0

Критерии:

неправильная обработка слов, где b находится слева от a (b ⁿ a ^m, … ab … ab … и т.п.) – сразу минус

оценку снижать по 1/3 за:

– останов хотя бы на одном слове вида a ⁿ b ^m, где n £ m, в том числе на пустом слове

– зацикливание хотя бы на одном слове вида a ⁿ b ^m, где n > m

– каждую лишнюю формулу постановки

 

--------------------------------------------------------------------------------------------------------

 

Доц. Корухова Л.С.

 

Доц. Пильщиков В.Н.

 

“_____” ________________ 2006 г.