Решение варианта демо версии егэ 2013 года (части a и B)




Скачать 372.82 Kb.
НазваниеРешение варианта демо версии егэ 2013 года (части a и B)
страница1/4
Дата25.11.2012
Размер372.82 Kb.
ТипРешение
  1   2   3   4

Решение варианта демо версии ЕГЭ 2013 года (части A и B)

Учитель информатики Батракова Л.В

.

ЧАСТЬ А


А1. Сколько единиц в двоичной записи десятичного числа 255?
1. 1 2. 2 3. 7 4. 8


Решение: Надо помнить, что 2k-1 это в двоичном представлении k единиц. Так как, 255=256 – 1=28 – 1, то в двоичной записи десятичного числа 255 будет 8 единиц.

Ответ: 4


A2. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
1. 11 2. 12 3. 13 4. 18


Решение: Сначала немного о графах (небольшая справка, можно пропустить, если знаете).

* * *

Граф — это множество точек (для удобства изображения — на плоскости) и попарно соединяющих их линий (не обязательно прямых). В графе важен только факт наличия связи между двумя вершинами. От способа изображения этой связи структура графа не зависит.

В графах не бывает петель — рёбер, соединяющих некоторую вершину саму с собой. Кроме того, в классическом графе не бывает двух различных рёбер, соединяющих одну и ту же пару вершин.

Ребро и вершина называются инцидентными друг другу, если вершина является одним из концов ребра.

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

Две вершины называются смежными, если они являются разными концами одного ребра (иными словами, эти вершины инцидентны одному ребру). Аналогично, два ребра называются смежными, если они инцидентны одной вершине.

Путь в графе — это последовательность вершин (без повторений), в которой любые две соседние вершины смежны. Например, в графе, изображённом на рисунке (рис.1), есть два различных пути из вершины a в вершину с: adbc и abc.




Рис. 1


Вершина v достижима из вершины u, если существует путь, начинающийся в u и заканчивающийся в v.

Граф называется связным, если все его вершины взаимно достижимы.

Длина пути — количество рёбер, из которых этот путь состоит. Например, длина уже упомянутых путей adbc и abc (см. рис. 1) — 3 и 2 соответственно.

Расстояние между вершинами u и v — это длина кратчайшего пути от u до v. Из этого определения видно, что расстояние между вершинами a и c в графе на рис. 1 равно 2.

Цикл — это замкнутый путь. Все вершины в цикле, кроме первой и последней, должны быть различны. Например, циклом является путь abda в графе на рис.1.

Ориентированный граф (орграф) — это граф, все рёбра которого имеют направление. Такие направленные рёбра называются дугами. На рисунках дуги изображаются стрелочками (см. рис.2).




Рис. 2

В отличие от рёбер, дуги соединяют две неравноправные вершины: одна из них называется началом  дуги (дуга из неё исходит), вторая — концом дуги (дуга в неё входит). Можно сказать, что любое ребро — это пара дуг, направленных навстречу друг другу.

Путь в орграфе — это последовательность вершин (без повторений), в которой любые две соседние  вершины смежны, причём каждая вершина является одновременно концом одной дуги и началом следующей дуги. «Двигаться» по орграфу можно только в направлениях, заданных стрелками.

Взвешенный (другое название: размеченныйграф (или орграф) — это граф (орграф), некоторым элементам которого (вершинамрёбрам или дугам) сопоставлены числа. Наиболее часто встречаются графы с помеченными рёбрами. Числа–пометки носят различные названия: вес,длинастоимость.

Замечание: Обычный (не взвешенный) граф можно интерпретировать как взвешенный, все рёбра которого имеют одинаковый вес 1.

Длина пути во взвешенном (связном) графе — это сумма длин (весов) тех рёбер, из которых состоит путьРасстояние между вершинами — это, как и прежде, длина кратчайшего пути. Например, расстояние от вершины a до вершины d во взвешенном графе, изображённом на рис.3, равно 6.




Рис.3

  1   2   3   4

Похожие:

Решение варианта демо версии егэ 2013 года (части a и B) iconРасписание егэ 2011
Демо-версии контрольно-измерительных материалов егэ 2012 года по математике, русскому языку, литературе, физике, биологии, химии,...
Решение варианта демо версии егэ 2013 года (части a и B) iconИзменения в егэ 2013
Фипи опубликовал планируемые изменения в кимах егэ 2013 года. Изменений было немного. Чтобы их увидеть, скачайте Демонстрационные...
Решение варианта демо версии егэ 2013 года (части a и B) iconТезисы «Особенности демонстрационного варианта ким егэ по математике 2011 года»
Егэ не влияет на аттестационную отметку выпускника. По результатам егэ устанавливается только пороговый балл, достижение которого...
Решение варианта демо версии егэ 2013 года (части a и B) iconО минимальном количестве баллов по предметам егэ в 2013 году
Накануне нового учебного года на официальном информационном портале егэ опубликовано распоряжение Рособрнадзора от 29. 08. 2012 №3499-10,...
Решение варианта демо версии егэ 2013 года (части a и B) iconФипи опубликовал планируемые изменения в кимах егэ 2013 года. Изменений было немного. Чтобы их увидеть, скачайте Демонстрационные варианты егэ 2013 по всем
Уточнены критерии проверки и оценки выполнения заданий с развернутым ответом (критерий К1)
Решение варианта демо версии егэ 2013 года (части a и B) iconСайта егэ изменения в кимах егэ 2012 года по сравнению с кимами 2011 года. Информатика
Ким 2012 года существенно переработан по сравнению с ким 2011 года. Изменено соотношение частей 1 и 2 работы (количество заданий...
Решение варианта демо версии егэ 2013 года (части a и B) iconИнструкция по организации и проведению пробного егэ по русскому языку (23 марта 2012 года)
Кима егэ в 15 экземплярах (демоверсию егэ-2012 не приносить). Актанышские сош №1, №2, гимназия – по 3 варианта. Полный пакет кимов...
Решение варианта демо версии егэ 2013 года (части a и B) iconОтменят ли егэ 2013?
В интернете ходит множество слухов о том, будет ли проводится егэ 2013, говорят, будто его собираются отменить и вроде бы даже уже...
Решение варианта демо версии егэ 2013 года (части a и B) iconЭкзамен
Экзамен по физике, 9 класс Демо 2008. Экзаменационная работа для проведения государственной (итоговой) аттестации выпускников IX...
Решение варианта демо версии егэ 2013 года (части a и B) icon1. Выписка из учебного плана Специальность химия
Демо-версии рабочих программ по биохимии для Специальности 011000 "Химия" (очная форма обучения)
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница