Лабораторная работа №8. Коллекции

  1. Дана строка, содержащая скобки трёх видов (круглые, квадратные и фигурные) и любые другие символы. Проверить, корректно ли в ней расставлены скобки. Например, в строке ([]{})[] скобки расставлены корректно, а в строке ([]] — нет. Указание: задача решается однократным проходом по символам заданной строки слева направо; для каждой открывающей скобки в строке в стек помещается соответствующая закрывающая, каждая закрывающая скобка в строке должна соответствовать скобке из вершины стека (при этом скобка с вершины стека снимается); в конце прохода стек должен быть пуст.
  2. Напечатать в порядке возрастания первые n натуральных чисел, в разложение которых на простые множители входят только числа 2, 3, 5. Указание: идея решения состоит в использовании трёх очередей, в которых хранятся числа, в 2 (3, 5) раз большие уже напечатанных, но не напечатанные; всякий раз из очередей выбирается наименьшее, расположенное в вершине одной из очередей значение, оно печатается, а в хвосты очередей добавляются соответствующие кратные ему; процесс запускается с печати числа 1.
  3. Дан список целых чисел (List<int>). Удалить из него все числа, делящиеся на первый элемент.
  4. Дан список целых чисел. Между любыми двумя элементами одной чётности вставить число 0.
  5. Решить две предыдущие задачи для двусвязного списка целых чисел (LinkedList<int>).
  6. Продемонстрировать использование классов List и LinkedList на примере следующего сценария:
    1. Генерируется длинный (100000 элементов) список случайных целых чисел.
    2. Выполняется проход по списку и из списка удаляются все числа, делящиеся на первый элемент.
    3. Между любыми двумя элементами одной чётности вставляется число 0.
    Организуйте сравнение времени решения предыдущей задачи с помощью классов List и LinkedList. Для сравнения удобно использовать методы класса Stopwatch.
  7. Даны несколько текстовых файлов, каждая срока которых содержит фамилию и имя студента. Найти студентов, имена которых присутствуют во всех файлах. Указание: в решении этой задачи удобно сформировать массив множеств HashSet с именами студентов, а затем вычислить их пересечение.
  8. Найти самое часто встречающееся слово в текстовом файле.
  9. Дан текстовый файл, каждая строка которого содержит а) идентификатор некоторой вершины ориентированного графа и б) список идентификаторов инцидентных ей вершин, то есть тех, в которые из вершины, указанной в начале строки, выходит дуга (идентификаторы — это последовательности латинских букв и цифр, идентификаторы разделяются пробелами, список вершин может быть пустым). Можно считать, что параллельных дуг (с совпадающими началами и концами) в графе нет. Пример файла:

    v1    v2 v3
    v2
    v3    v1
    Проверить, что граф задан этим файлом корректно, а именно:
    • идентификаторы вершин, указанных первыми, не повторяются;
    • все упомянутые в списках вершин идентификаторы в одной из строк указаны на первой позиции.
  10. Для графа, заданного файлом в формате из предыдущего упражнения, выполнить следующее:
    • посчитать общее количество дуг в графе;
    • построить матрицу инцидентности;
    • найти вершины, в которые не входит ни одной дуги.