2011 год Системы счисления (с с.)



Скачать 58.85 Kb.
Дата03.05.2018
Размер58.85 Kb.
ТипЭкзаменационные вопросы

Экзаменационные вопросы по курсу

Программирование на языке высокого уровня

2011 год
1. Системы счисления (с.с.)

Алгоритмы перевода действительных чисел из одной b-с.с. в другую:

- из произвольной b-c.с. в 10-с.с.;

- из 10-с.с. в произвольную b-с.с.;

- из произвольной b1-с.с в произвольную b2-с.с.;

- между кратными с.с.



2. Модели машинной арифметики с конечной разрядностью

2.1. Беззнаковые целые числа конечной разрядности, примеры их использования в Си. Формулы для min и max.

2.2. Знаковые целые числа конечной разрядности, примеры их использования в Си. Дополнительный код. Знаковый разряд. Формулы для мин и макс цеого числа со знаком.

2.3. Представление вещественных чисел с фиксированной точкой.

2.4. Представление вещественных чисел с плавающей точкой. Нормализованное представление вещественного числа. Мантисса и порядок, их вид. Разрядность мантиссы и порядка.
3. Вопросы по С

3.1. Базовые типы языка С. Представление значений базовых типов в памяти. Диапазоны значений базовых типов.

3.2. Базовые типы языка С. Операции над значениями базовых типов. Перенос и переполнение. Преобразования между базовыми типами языка С.

3.3. Массивы. Многомерные массивы. Индексация многомерных массивов. Распределение памяти в многомерных массивах. Связь понятия указателя и массива. Инициализаторы

массивов.

3.4. Понятие времени жизни и области видимости переменных. Глобальные и локальные переменные. Модификаторы области видимости и времени жизни.

3.5. Арифметические и логические выражения. Разбор порядка вычисления выражения, приоритеты операций.

3.6. Понятие типа/преобразование типов.

3.7. Синтаксис описания структур. Обращение к полям структур для объектов и к полям по указателю на объект типа структура. Инициализатор структур.

3.8. Функции. Описание функций. Возвращаемые значения. Передаваемые параметры. Порядок передачи параметров через стек.

3.9. Функции с переменным числом параметров. Получение переменных передаваемых после фиксированных параметров.

3.10. Функции printf, sprintf, fprintf, scanf, sscanf, fscanf. Форматная строка (целые знаковые и беззнаковые в десятичном и шестнадцатеричном виде, числа с плавающей запятой, буквы, строки). Возвращаемое значение.

3.11. Строки в языке С. Понятие длины строки. Инициализаторы строк. Функции работы со строками: определение длины строки, копирование строк, слияние строк.

3.12. Основные стандартные функции языка Си для работы с файлами. Текстовые и бинарные файлы.

3.13. Понятие указателя в С. Операции над указателями.

3.14. Препроцессор языка С. Включаемые файлы. Макроопределения и условная компиляция.

3.15. Выделение памяти под локальные переменные (класс памяти auto в языке С). Стек вызовов.
4. Управление памятью:

4.1. Классы памяти переменных в языке C. Cрок жизни переменных для каждого из классов памяти.

4.2. Динамическая память. Функции работы с ДП.
5. Алгоритмы: основные понятия, перестановки, поиск, сортировки

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

5.2. Основные методы программирования: повторение, ветвление и рекурсия. Рекурсивный переход, правила выхода, ветвящаяся и хвостовая рекурсия. Примеры использования для каждого метода.

5.3. Перестановки набора. Подсчет числа перестановок.

- Инверсии. Число инверсий, как мера сложности упорядочения набора; таблицы инверсий; алгоритм восстановления перестановки по таблице инверсий;

- Таблица инверсий как число в особой с.с.; итерационный алгоритм генерации всех таблиц инверсий.

- Алгоритмы перебора перестановок: рекурсивный, итерационный с лексикографическим упорядочением (Дейкстры).

5.4. Постановка задач поиска (П) и сортировки (С) записей в произвольном наборе данных. Внешняя и внутренняя постановка задачи П/С (при не/доступности всего набора).

- Методы простого поиска в массиве: линейный поиск, бинарный поиск, оценки сложности.

- Методы поиска подстроки в строке: алгоритм прямого перебора, алгоритм Бойера-Мура, Рабина-Карпа, оценки сложности.

- Методы сортировки массива:

метод простых вставок;

метод бинарных вставок;

метод простого выбора;

метод "пузырька";

шейкер-сортировка;

метод Шелла;

быстрая сортировка Хоара;

пирамидальная сортировка;

сортировка слиянием;

оценки сложности.

5.5. Cортировка файлов простым двухпутевым слиянием


6. Элементы теорий вероятностей, информации и кодирования.
Метод Хаффмана построения кода типа А-{0,1}* с минимальной избыточностью. Реализация проекта по созданию архиватора.


7. Классические модели динамической памяти.

7.1. Список; как универсальная модель структур данных последовательного доступа; разновидности списков: одно/двусвязные; циклические; иерархические

7.2. Операции над списками, алгоритмы поиска и включения для списков, анализ их эффективности, способы реализации списков (статика, динамика), реализация алгоритма топологической сортировки на иерархических списках.

7.3. Стек, преобразование инфиксной формы записи выражения в постфиксную и вычисление значения полученного выражения.

7.4. Очередь, реализация обхода дерева методом в ширину.

7.5. Основные операции со стеком и очередью, способы реализации на различных базовых представлениях.


8. Абстрактные структуры данных.

8.1. Граф. Модели представления в ЭВМ: матрицы смежности и инцидентности, динамическая структура со списками дуг, табличное представление.

8.2. Дерево двоичного поиска, создание орфографического словаря по заданному набору слов. Алгоритмы включения и удаления, сравнение их эффективности с известными алгоритмами на массивах.

8.3. Сбалансированные (АВЛ) деревья. Алгоритм вставки элемента в АВЛ-дерево на уровне схемы.

8.4. Левое\правое скобочное представление деревьев.

8.5. Б-деревья. Алгоритмы поиска и включения элемента в Б-дерево.


9. Алгоритмы перебора на абстрактных динамических структурах

9.1. Алгоритмы с возвратом - обход шахматной доски конем, поиск всех гамильтоновых циклов.

9.2. Алгоритмы обхода графа методами в глубину и в ширину.

9.3. Алгоритмы обхода деревьев (в ширину, слева направо, в глубину: в ре/пост/инфиксном порядке).

9.5. Поиск кратчайших путей в графе: алгоритмы Дейкстры, Беллмана-Форда, Флойда-Уоршелла.

9.6. Транзитивное замыкание графа. Алгоритм Флойда.

9.7. Система непересекающихся множеств, операции определения представителя множества и объединения двух множеств. Реализация операций на Си.

9.8. Каркасы графа. Алгоритм Краскала, Прима.

9.9. Эйлеровы графы. Алгоритм Флери, алгоритм поиска эйлерова цикла с использованием стека (O(n+m)).

9.10. Двусвязные компоненты графа, точки сочленения, алгоритм нахождения двусвязных компонент и точек сочленения.

9.11. Раскраска графа, алгоритм последовательной раскраски.
10. Динамическое программирование

10.1. Динамическое программирование как решение задач с помощью табличной техники.

10.2. Примеры задач: о рюкзаке, об умножении матриц, о делимости, о гангстерах.

ЛИТЕРАТУРА

1. В.А.Цикоза, Т.Г.Чурина. Методическое пособие к курсу "Методы программирования" (часть первая). Новосибирск: 2003г.

2. В.А.Цикоза, Т.Г.Чурина. Методическое пособие к курсу "Методы программирования: перестановки, поиск, сортировка" (часть вторая). Новосибирск: 2006г.

3. Кнут Д. Искусство Программирования для ЭВМ. Т.3. Сортировка и Поиск.

4. Кнут Д. Искусство Программирования для ЭВМ. Т.1. Основные алгоритмы.

5. А.Ахо, Д.Хопкрофт, Д. Ульман. Построение и анализ вычислительных алгоритмов.

6. Т.Кормен, Ч.Лейзерсон, Р.Ривест. Алгоритмы: построение и анализ.

7. Б. Керниган, Д. Ричи. Язык Си

8. Хэзфилд Р., Кирби Л. Искусство программирования на C: Фундаментальные алгоритмы, структуры данных и примеры приложений



9. А. Ахо, Р. Сети, Дж. Хопкрофт. Коипиляторы

10. Ватолин Д., Ратушпяк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео.

11. В.В. Подбельский, С.С.Фомин Программирование на языке С. , 2007.

12. Т.А., Павловская С/С++ Программирование на языке высокого уровня. Питер, 2005


Каталог: fit -> courses -> Programming -> data
fit -> Полное описание Интернет-проекта
fit -> Министерство экономики
fit -> Элт монитор. Жк монитор. Принцип работы и характеристики
fit -> Рабочая программа «Фитнес. Силовая физическая подготовка»
fit -> Наименование Web-документа
fit -> Aerobics classic – классическая аэробика для начинающих Basic Step
fit -> Показания описание ухода
data -> Вопросы по курсу Программирование на языке высокого уровня
courses -> Лабораторная работа Обозначение границ моделируемой системы


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©vossta.ru 2019
обратиться к администрации

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