Green-sell.info

Новые технологии
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

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

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

1) Что такое алгоритм. Дайте определение, приведите примеры.

2) Перечислите виды исполнителей, в чем их отличие друг от друга, аргументируйте ответ.

3) Перечислите основные факторы влияющие на правильность исполнения алгоритма.

4) Можно ли сохранять порядок действий при выполнении алгоритма. В каких случаях его можно нарушать, аргументируйте ответ и приведите примеры.

5) Какие действия выполняет исполнитель при выполнении алгоритма. Перечислите шаги и приведите пример по этим шагам.

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

7) Что такое дискретность. Приведите пример использования данного свойства на практике.

8) Что такое детерминированность как это применимо к алгоритмам. Как его можно использовать в алгоритмах.

9) Что такое массовость. Опишите и приведите пример. Как это можно использовать в теории алгоритмов.

10) Что такое конечность. Опишите и приведите пример. Как это можно использовать в теории алгоритмов.

11) Что такое формальность. Опишите и приведите пример. Как это можно использовать в теории алгоритмов.

12) Что такое результатность. Опишите и приведите пример. Как это можно использовать в теории алгоритмов.

13) Что такое однозначная определенность . Как это можно использовать в теории алгоритмов.

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

15) Опишите действия при постановке задачи. Перечислите шаги и приведите пример по этим шагам. На сколько важен этап, в каких случаях его можно пропустить. Приведите пример.

16) Опишите действия при разработке метода решения задач. Перечислите шаги и приведите пример по этим шагам. На сколько важен этап, в каких случаях его можно пропустить. Приведите пример.

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

18) Опишите действия при разработке алгоритма. Перечислите шаги и приведите пример по этим шагам. На сколько важен этап, в каких случаях его можно пропустить. Приведите пример.

19) Опишите действия при составлении программы. Перечислите шаги и приведите пример по этим шагам. На сколько важен этап, в каких случаях его можно пропустить. Приведите пример.

20) Опишите действия при отладке программы. Перечислите шаги и приведите пример по этим шагам. На сколько важен этап, в каких случаях его можно пропустить. Приведите пример.

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

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

23) Опишите особенности написания алгоритма на естественном языке. Приведите пример описания какого ни будь алгоритма.

24) Что такое псевдокод, как его можно использовать в теории алгоритма. Приведите пример использования.

25) Как используют графическую запись алгоритма. Опишите элементы используемые при этом. Приведите свой пример записи.

26) Что такое структур граммы. Для чего они используются в теории алгоритмов. Приведите свой пример.

27) Что такое синтаксические диаграммы. Опишите элементы используемые при этом. Приведите свой пример записи.

28) Опишите основные виды алгоритмов. Приведите пример каждого вида описанный на одном из языков алгоритма известном вам.

29) Дайте определение линейного алгоритма. Перечислите его особенности, достоинства и недостатки Приведите пример каждого вида описанный на одном из языков алгоритма известном вам.

30) Дайте определение алгоритма ветвления. Перечислите его особенности, достоинства и недостатки. Приведите пример каждого вида описанный на одном из языков алгоритма известном вам.

31) Дайте определение алгоритма ветвления. Какие виды алгоритмов ветвления вам известны Перечислите особенности, достоинства и недостатки. Приведите пример каждого вида описанный на одном из языков алгоритма известном вам.

32) Как называют алгоритм проверяющий одно условие и в зависимости от результата сравнения выполняющий одно или другое действие. Приведите пример.

33) Как называют алгоритм который получает в качестве параметра значение которое нужно сравнить с несколькими вариантами и выполняет тот вариант где значение совпало. Приведите пример описанный на одном из языков алгоритма известном вам.

34) Как называется управляющая структура, организующая многократное выполнение указанного действия. Перечислите основные виды данных структур и приведите примеры.

35) Как называется управляющая структура, организующая выполнение лишь одного из двух указанных действий в зависимости от справедливости некоторого условия. Перечислите основные виды данных структур и приведите примеры.

36) Дайте определение циклическим алгоритмам, перечислите известные вам виды циклических алгоритмов. Приведите пример использования каждого из них.

37) Что такое цикл с пред условием. К какому виду алгоритмов относиться цикл с пред условием. Приведите пример данного алгоритма.

38) Перечислите основные методы сортировки известные вам. Приведите пример сортировки 4 значений каждым из методов.

39) Опишите особенности метода пузырьковой сортировки, Приведите пример сортировки 4 значений этим методом.

40) Опишите особенности метода сортировки вставками, Приведите пример сортировки 4 значений этим методом.

41) Опишите особенности метода сортировки выборкой, Приведите пример сортировки 4 значений этим методом.

Экзаменнационные вопросы по дисциплине «Основы алгоритмизации и программирования»»

Как организовать дистанционное обучение во время карантина?

Помогает проект «Инфоурок»

Вопросы к экзамену

по дисциплине «Основы алгоритмизации и программирования» для студентов 2 курса по специальности 09.02.01

Переменные. Типы данных в С++.

Структура программы. Команда присваивания в С++ .

Ввод-вывод данных. Формат выводимых данных.

Ввод-вывод данных. Стандартные потоки ввода и вывода . Примеры.

Алгоритм линейной структуры в Си++. .

Структура IF , классификация в С++ . Примеры.

Структура switch (выбор) и ее программирование в С++. Примеры.

Алгоритмы циклической итерационной структуры. Оператор цикла While в С++. Примеры использования.

Алгоритмы циклической итерационной структуры. Оператор цикла do … while в С++. Примеры использования.

Алгоритмы циклической итерационной структуры. Оператор цикла For в С++. Примеры использования.

Операторы break и continue в С++. Примеры использования.

Одномерные массивы в С++. Задание массивам первоначальных значений.

Операции над массивами и их совместимость. Ввод-вывод массивов в С++.

Случайные числа в языке программирования С++.

Понятие подпрограммы в С++. Описание подпрограммы.

Формальные и фактические параметры в С++.

Понятие о локальных и глобальных переменных в С++.

Основные математические функции в С++. Примеры.

Определение алгоритма. Свойства алгоритма. Формы записи алгоритмов. Примеры.

Запись алгоритмов блок-схемами. Основные элементы блок-схем.

Алгоритмы с ветвлением. Пример алгоритма.

Алгоритм цикла с предусловием. Пример алгоритма.

Алгоритм цикла с постусловием. Пример алгоритма.

Алгоритм цикла с управляющей переменной. Пример алгоритма.

Переменные. Типы данных в Python .

Структура программы. Команда присваивания в Python .

Ввод-вывод данных. Формат выводимых данных в Python .

Алгоритм линейной структуры в Python .

Структура IF , классификация в Python . Примеры.

Алгоритмы циклической итерационной структуры. Оператор цикла While в Python . Примеры использования.

Строки как последовательности символов в Python . Примеры использования.

Алгоритмы циклической итерационной структуры. Оператор цикла обхода For в Python . Примеры использования.

Оператор break в Python . Примеры использования.

Оператор continue в Python . Примеры использования.

Списки – изменяемые последовательности в Python . Примеры использования.

Словари в Python . Примеры использования.

Понятие подпрограммы в Python . Описание подпрограммы.

Формальные и фактические параметры в Python .

Читать еще:  Технология объектно ориентированного программирования

Понятие о локальных и глобальных переменных в Python .

Функции в Python .

Рассмотрено методической цикловой комиссией по укрупненной группе специальностей ______________________________________________________

Протокол №___ от _____________ 201 ___ г.

Выберите книгу со скидкой:

ЕГЭ. География. Новый полный справочник для подготовки к ЕГЭ

350 руб. 163.00 руб.

350 руб. 171.00 руб.

ЕГЭ-2019. География. Теория и практика

350 руб. 213.00 руб.

ОГЭ. География. Большой сборник тематических заданий для подготовки к основному государственному экзамену

350 руб. 197.00 руб.

География. 10-11 классы. Атлас. (Традиционный комплект) (РГО)

350 руб. 106.00 руб.

География. 7 класс. Атлас. (Традиционный комплект)(РГО)

350 руб. 106.00 руб.

География. 5 класс. Атлас. (Традиционный комплект).

350 руб. 106.00 руб.

География. 10-11 классы. Контурные карты. (Традиционный комплект) (РГО)

350 руб. 59.00 руб.

География. 6 класс. Атлас. (Традиционный комплект)(РГО)

350 руб. 106.00 руб.

География. Материки, океаны, народы и страны. 7класс. Атлас

350 руб. 184.00 руб.

География. 9 класс. Контурные карты. (Традиционный комплект) (РГО)

350 руб. 59.00 руб.

География. Начальный курс географии. 6класс. Контурные карты

350 руб. 101.00 руб.

БОЛЕЕ 58 000 КНИГ И ШИРОКИЙ ВЫБОР КАНЦТОВАРОВ! ИНФОЛАВКА

Инфолавка — книжный магазин для педагогов и родителей от проекта «Инфоурок»

Бесплатный
Дистанционный конкурс «Стоп коронавирус»

  • Маркова Анна Викторовна
  • Написать
  • 1070
  • 21.05.2018

Номер материала: ДБ-1620414

Добавляйте авторские материалы и получите призы от Инфоурок

Еженедельный призовой фонд 100 000 Р

  • 21.05.2018
  • 322
  • 21.05.2018
  • 311
  • 21.05.2018
  • 128
  • 21.05.2018
  • 128
  • 21.05.2018
  • 95
  • 21.05.2018
  • 110
  • 21.05.2018
  • 118
  • 21.05.2018
  • 114

Не нашли то что искали?

Вам будут интересны эти курсы:

Все материалы, размещенные на сайте, созданы авторами сайта либо размещены пользователями сайта и представлены на сайте исключительно для ознакомления. Авторские права на материалы принадлежат их законным авторам. Частичное или полное копирование материалов сайта без письменного разрешения администрации сайта запрещено! Мнение редакции может не совпадать с точкой зрения авторов.

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

Вопросы к экзамену по дисциплине «Программирование»

ВОПРОСЫ К ЭКЗАМЕНУ ПО ДИСЦИПЛИНЕ

для студентов направления «МОиАИС»

за 1 семестр 1 курса, учебный год

1. Основные подходы программирования. Процедурный, структурный, объектно-ориентированный. Преимущества и недостатки каждого подхода.

2. Алфавит, синтаксис и семантика языка Turbo Pascal.

3. Структура программы на языке Turbo Pascal. Характеристика процедурных языков программирования.

4. Типы данных. Описание констант и переменных стандартных типов. Приведение типов. Локальные и глобальные переменные.

5. Типы данных. Структурированные типы. Множества.

6. Полная и неполная форма ветвления. Оператор безусловного перехода goto.

7. Структура множественного выбора Case.

8. Структуры повторения (цикл с предусловием, цикл с постусловием, структура повторения for). Операторы break и continue.

9. Подпрограммы. Описание процедур. Формальные и фактические параметры. Директива forward.

10. Подпрограммы. Описание функций. Формальные и фактические параметры. Директива forward.

11. Статические массивы в Turbo Pascal. Примеры работы с одномерными массивами.

12. Статические массивы в Turbo Pascal. Примеры работы с двумерными массивами.

13. Символьный тип в Turbo Pascal. Примеры использования функций Chr и Ord.

14. Строковый тип в Turbo Pascal. Процедуры и функции работы со строками.

15. Текстовый вывод на экран. Модуль CRT.

16. Рекурсивные подпрограммы.

17. Указатели. Ссылочные типы данных. Примеры работы.

18. Динамические массивы. Создание и уничтожение массива.

19. Динамические структуры. Списки. Стеки. Очереди.

20. Тип Record (запись) в Turbo Pascal. Описание полей и вариантная часть.

21. Файловый ввод-вывод в Turbo Pascal. Типизированные файлы. Назначение процедур Seek, Truncate, Filepos, FileSize. Примеры.

22. Файловый ввод-вывод в Turbo Pascal. Текстовые файлы. Специфика текстовых файлов. Назначение процедуры Append. Примеры.

23. Файловый ввод-вывод в Turbo Pascal. Нетипизированные файлы. Назначение процедур BlockRead, BlockWrite. Примеры.

24. Графика в Turbo Pascal. Инициализация графического режима. Основные процедуры графического режима.

25. Графика в Turbo Pascal. Инициализация графического режима. Основные функции графического режима.

ЗАДАЧИ К ЭКЗАМЕНУ ПО ДИСЦИПЛИНЕ

для студентов направления «МОиАИС»

за 1 семестр 1 курса, учебный год

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

2. Вычислить длины сторон треугольника по заданным координатам его вершин в трехмерном пространстве.

3. Для параллелограмма с заданными сторонами и острым углом между ними определить его площадь, высоты и длины диагоналей.

4. Проверить, есть ли среди введенных трех целых чисел одинаковые.

5. Даны три точки A, B, C на числовой оси. Найти длины отрезков AC и BC и их сумму.

6. Решить линейное уравнение Ax + B = 0, заданное своими коэффициентами A и B (коэффициент A не равен 0).

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

8. Дано целое число N (> 0). Найти сумму 1 + 1/2 + 1/3 + … + 1/N.

9. Найти значение факториала заданного числа N.

10. Найти все простые числа в диапазоне от a до b (вводятся с клавиатуры), или сообщить, что в указанном диапазоне таких чисел нет.

11. Число, сумма всех делителей которого (исключая его само) равна этому числу, называется совершенным. Например: 6=1+2+3, 28=1+2+4+7+14. Найти все совершенные числа в диапазоне от a до b (вводятся с клавиатуры).

12. Дано целое число N (> 0). Найти сумму 12 + 22 + 32 + … + N2. Чтобы избежать целочисленного переполнения, вычислять слагаемые этой суммы с помощью вещественной переменной и выводить результат как вещественное число.

13. Дано целое число N (> 0). Найти наименьшее целое положительное число K, квадрат которого превосходит N: K2 > N. Функцию извлечения квадратного корня не использовать.

14. Задана последовательность целых чисел. Сформировать на основе нее массив, содержащий номера отрицательных элементов последовательности. Если таких элементов нет, – вывести сообщение об этом.

15. Задана последовательность действительных чисел. Подсчитать количество чисел последовательности, расположенных на отрезке, концами которого являются два последних элемента массива.

16. Задан одномерный массив вещественных чисел. Найти в нем максимальный и минимальный элементы, и вывести их с указанием их индексов.

17. Задана последовательность, содержащая натуральные числа. Найти сумму максимального элемента (среди четных чисел) и минимального элемента (среди нечетных чисел) заданной последовательности.

18. В двумерном массиве найти позиции всех максимальных элементов, если таких элементов несколько. Если максимальный элемент только один, — вывести его значение.

19. Даны матрица A размером N х N и вектор B размером N. Записать на главную диагональ элементы вектора, а в вектор – элементы главной диагонали.

20. В трехмерном пространстве заданы координаты N точек. Составить программу, определяющую пару точек, расстояние между которыми максимально.

21. Задан массив символов. Вывести на печать те из них, которые являются цифрами.

22. Задана строка текста. Определить, сколько раз встречается в ней заданный символ.

23. Во введенной строке символов найти пары, состоящие из одинаковых символов и заменить второй из них цифрой «1».

24. Составить программу, которая из заданной строки символов выводит буквы по алфавиту. Например: строка – «программирование», результат – «аавгеииммноопррр».

Читать еще:  Какие группы безопасности

25. Имеются данные о квартирах в новом строящемся доме: номер квартиры, этаж, общая площадь, количество комнат, стоимость квадратного метра жилья каждой из квартир. Составить программу, которая сортирует квартиры по возрастанию общей стоимости, а также позволяет по указанной сумме денег у покупателя вывести список квартир, которые он мог бы приобрести.

26. На складе медикаментов решили провести проверку лекарственных препаратов на истечение срока годности. Информация о препаратах заносится в запись, состоящую из следующих полей: название лекарства, производитель, дата выпуска, срок годности, стоимость. Организовать ввод сведений о лекарственных препаратах, а также сформировать список препаратов с истекающим сроком годности. Предусмотреть поиск по названию лекарственного препарата и по годам выпуска.

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

28. Записать в типизированный файл массив целых чисел, после чего считать данные из файла и найти максимальный элемент.

Список вопросов к экзамену по курсу «Технология программирования»

Primary tabs

Forums:

Список вопросов к экзамену
по курсу «Технология программирования»
для специальности «Информационные системы и технологии» (соответствует лекциям , следовательно -актуально для студентов всех специальностей ,которые прослушали курс)

  • 1. Критерии качества программного средства. Определение качества ПО в стандарте ISO 9126. Многоуровневая модель качества ПО. Оценочные характеристики качества про-граммного продукта
  • 2. Жизненный цикл программного продукта, фазы жизненного цикла. Этапы классического жизненного цикла, их содержание.
  • 3. Фаза разработки, этапы процесса разработки. Стратегии конструирования ПО: линейная, инкрементная, эволюционная.
  • 4. Стандарт ISO/IEC 12207-95: основные определения – система, модель жизненного цик-ла, квалификационные требования. Основные процессы, их содержание, работы и задачи процесса разработки.
  • 5. Стандарт ISO/IEC 15504 (SPICE): оценка возможностей разработчика. Связь этого стан-дарта с моделью зрелости предприятия SEI CMM.
  • 6. Прогностические модели процесса разработки: каскадная, RAD, спиральная.
  • 7. Адаптивные модели процесса разработки: экстремальное программирование, Scrum.
  • 8. Руководство программным проектом. Предварительные оценки проекта. Системный анализ и анализ требований. Анализ рисков. Планирование процесса разработки. Типо-вая структура распределения работ.
  • 9. Контроль процесса разработки. Размерно- и функционально-ориентированные метрики. Метрические характеристики объектно-ориентированных систем.
  • 10. Структурный и объектно-ориентированный подходы к разработке ПО. Их сравнитель-ный анализ. Сущность объектного подхода к разработке программных средств.
  • 11. Анализ предметной области: цели и задачи. Модели предметной области. Формальные определения. Классификация моделей. Методология IDEF0, синтаксис IDEF0-моделей.
  • 12. Диаграммы потоков данных (DFD-диаграммы) и диаграммы потоков работ (IDEF3-диаграммы), их использование при моделировании предметной области.
  • 13. Объектно-ориентированный анализ предметной области. Методика определения границ системы и ключевых абстракций. Пример проведения анализа. Функциональные и не-функциональные требования к системе.
  • 14. Функциональные требования к системе. Способ их представления в виде UML-диаграммы. Пример диаграммы с использованием отношений «расширяет» и «включа-ет». Понятие прецедента и сценария.
  • 15. Концептуальная модель системы: концептуальные классы, системные события и систем-ные операции. Способ их представления в виде UML-диаграмм. Пример концептуаль-ного описания прецедента.
  • 16. Диаграммы взаимодействия как элементы концептуальной модели. Синтаксис диаграмм взаимодействия.
  • 17. Проектирование программных средств. Цели и задачи этапа проектирования. Понятие модели проектирования, ее отличия от концептуальной модели. Стадии проектирования, их краткая характеристика.
  • 18. Задачи, решаемые на стадии эскизного проектирования. Понятие архитектуры ПС. Про-блема выбора архитектуры. Влияние архитектуры на качественные характеристики ПС.
  • 19. Понятие модуля и модульного программирования. Преимущества модульного подхода к разработке ПО. Модули как средство физического структурирования ПО. Свойства мо-дулей.
  • 20. Задачи, решаемые на стадии детального проектирования. Цели и задачи проектирования пользовательского интерфейса.
  • 21. Понятие шаблона. Классификация шаблонов. Стандарт описания шаблонов.
  • 22. Идентификация методов программных классов. Диаграммы классов, способы отображе-ния отношений ассоциации и зависимости. Пример диаграммы классов.
  • 23. Тестирование и отладка программного средства. Стадии тестирования и их характери-стика. Основные принципы тестирования. Тесты и тестовые наборы. Понятие тестового покрытия.
  • 24. Отладочное тестирование. Соотношение структурного и функционального подходов. Примеры реализации.
  • 25. Интеграционное тестирование. Виды интеграционного тестирования. Критерии полноты тестовых наборов. Регрессионное тестирование. Критерии завершения отладочного тестирования.
  • 26. Системное тестирование. Виды системного тестирования. Критерии полноты тестовых наборов.
  • 27. Особенности объектно-ориентированного тестирования. Расширение области примене-ния тестирования. Критерии тестирования моделей. Тестирование классов. Тестирование кластеров и потоковое тестирование.
  • 28. Понятие автоматизированного тестирования. Автотесты. Достоинства и недостатки ав-томатизированного тестирования. Средства автоматизированного тестирования.
  • 29. Утилита модульного тестирования NUnit. Средства описания тестов. Утверждения, па-раметры утверждений.
  • 30. Понятие версии программного продукта и системы контроля версий. Модели версиони-рования, их сравнение.
  • 31. Система Subversion, ее архитектура. Хранилище, его структура, правки. Команды SVN для работы с хранилищем. Понятия рабочей копии и служебного каталога. Сценарий объединения правок. Конфликты и способы их разрешения.
  • 32. Понятие сборки, манифест сборки. Сборка приложения, системы автоматизации сборки.
  • 33. Утилита NAnt, файл сборки и его структура. Цели, зависимость целей, описание целей.
  • 34. Документирование процесса разработки. Типы документов управления.
  • 35. Документирование программного продукта. Документация сопровождения, ее назначе-ние и состав. Пользовательская документация, ее назначение и состав.


Литература

  • 1. Орлов С.А. Технологии разработки программного обеспечения: Учебник для вузов. 3-е изд. ¬– СПб.: Питер, 2004. – 527 с.: ил.
  • 2. Принципы проектирования и разработки программного обеспечения. Учебный курс MCSD.: Пер. с англ.: – М.: Издательско-торговый дом «Русская Редакция», 2000. – 608 с.: ил.
  • 3. Лингер, Р. Теория и практика структурного программирования / Ричард Лингер, Хэрлан Миллс, Бернард Уитт.: Пер. с англ.: – М.: Мир, 1982. – 406 с.: ил.
  • 4. Грис, Дэвид. Наука программирования.: Пер. с англ.: – М.: Мир, 1984. – 416 с.: ил.
  • 5. Буч, Грейди. Объектно-ориентированный анализ и проектирование с примерами прило-жений на C++. 2-е изд.: Пер. с англ.: – СПб.: Невский диалект, 1998. – 560 с.: ил.
  • 6. Оберг, Роберт, Дж. Технология COM+. Основы и программирование.: Пер. с англ.: Уч. пос. – М.: Издательский дом «Вильямс», 2000. – 480 с.: ил.
  • 7. Уоткинз, Д. Программирование на платформе .Net / ДеймьенУоткинз, Марк Хаммонд, Брэд Эйбрамз.

Вопросы к экзамену по программированию в НГУ

Нашли в сети список экзаменационных вопросов по программированию и решили, что возможно кому то пригодится. Вопросы к экзамену по программированию в НГУ.

Вопросы к экзамену по программированию в НГУ (Новосибирский государственный университет)

Вопросы по курсу Программирование на языке высокого уровня (ЯВУ)

  1. Системы счисления (с.с.)

1.1. Запись чисел цифрами и числовые значения. С.с. как система правил записи чисел.

1.2. Правила записи значений целых и действительных чисел в позиционных с.с. по основанию b (b-с.с.).

1.3. Рекурентные функции перевода «число-запись» и «запись-число». Вычисления по схеме Горнера с минимальным числом операций.

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

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

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

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

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

1.4.1. Модификации этих алгоритмов для перевода действительных чисел.

1.4.2. Кратные с.с. Приемы использования кратных с.с. для ускорения перевода чисел между произвольными b-с.с.

1.5. Операции сложения и умножения для произвольных b-с.с.

1.6. Достаточное условие бесконечности представления рациональной дроби в произвольной b-с.с.

1.7. Понятие символьных вычислений. Формальное определение вычислений как преобразование цепочек символов по заданным правилам (на примере определения арифметических операций таблицами значений).

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

2.1. Модель машинной памяти как однородного линейно-адресуемого массива ячеек фиксированной разрядности.

Читать еще:  Что такое лексема в программировании

2.2. Понятие разрядной сетки и характеризующие параметры: разрядность и формат.

2.3. Модель целых чисел конечной разрядности. Понятие переноса и переполнения.

2.4. Беззнаковые целые числа конечной разрядности. Формулы для min и max. Дополнительный код. Знаковый разряд. Формулы для мин и макс целого числа со знаком.

2.5. Правила представления чисел и арифметика в дополнительном коде.

2.6. Единообразие правил знаковой и беззнаковой арифметики. Примеры.

2.6. Модель вещественной арифметики с фиксированной точкой (равномерная точность представления). Формулы для max и точности.

2.7. Модель вещественной арифметики с плавающей точкой.

2.7.1. Экспоненциальное (нормализованное, с плавающей точкой) представление вещественного числа. Мантисса и порядок, их вид. Нормализация. Особенности арифметики с плавающей точкой:

— денормализация аргументов при сложении;

— расширение разрядной сетки при денормализации и округлении.

Разрядность мантиссы и порядка. Формулы для max.

2.7.2. Источники погрешности при арифметике с плавающей точкой. Приведите примеры

Вопросы по C

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Управление памятью:

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

каждого из классов памяти?

4.2. Динамическая память. Функции работы с ДП. Основные ошибки: утечка памяти, висящие указатели.

4.3. Стратегии выделения памяти. (first fit, best fit, worst fit).

Какие структуры данных используются для реализации first fit (линейный

список) и worst fit (heap).

4.4. Что такое внешняя фрагментация и при каких условиях она возникает?

4.5. Что такое внутренняя фрагментация и при каких условиях она

4.6. Выделение памяти алгоритмом парных меток.

4.7. Выделение памяти алгоритмом близнецов. Каковы преимущества этого

4.8. Слабовые аллокаторы. Где они используются?

4.9. Сборка мусора: область применения, основные методы.

Алгоритмы: перестановки, поиск, сортировки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 Элементы теорий вероятностей, информации и кодирования.

6.1. Модель информационной системы связи Шеннона. Источник; приемник; канал; де/кодер. Алфавит источника как формализация языка сообщений. Кодирование как преобразование сообщения при переходе в среду с другим алфавитом.

6.2. Префиксный код. Однозначная декодируемость префиксного кода. Примеры непрефиксного однозначно декодируемого кода.

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

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

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

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

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

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

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

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

8.1. Графы, граф как наиболее общая модель данных последовательного доступа, пути и маршруты по графу, определения различных типов графов: (не)ориентированного, (а)циклического, много/односвязного.

8.2. Представление графа, как отношения на множестве вершин.

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

8.3. Дерево, как частный вид графа.

— Терминология для деревьев: отец, сын, корень, лист, глубина и др.

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

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

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

Алгоритмы перебора на абстрактных динамических структурах (с обсуждением способов реализации)

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

9.2. Обход графа методом в ширину. Реализация, примеры задач.

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

9.4. Обход всех вершин графа — метод поиска в глубину.

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

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

9.7. Каркас графа минимальной стоимости, алгоритмы Краскала и Прима.

9.8. Эйлеров граф. Способ определения Эйлерова цикла (теорема). Алгоритм Флери. Поиск Эйлерова цикла за время O(n+m).

9.9 Потоки в сетях, алгоритмы поиска максимального потока, теорема о максимальном потоке и минимальном разрезе.

Динамическое программирование

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

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

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

— Символьные формализмы для описания синтаксиса языков: БНФ, РБНФ.

— Формальные грамматики. Классификация грамматик по Хомскому. Примеры грамматик.

— Синтаксический анализатор. Нисходящий и восходящий разбор. Полный перебор правил подстановки.

Ссылка на основную публикацию
Adblock
detector