Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Структуры со сылками на себя
Замечание: в задачах 6.27 – 6.40 речь идет об однонаправленных списках без заглавного звена (если не сказано особо в постановке задачи); struct lnode { type data; /* поле данных */ struct lnode *next; /*указатель на следующее звено списка */ } Здесь struct lnode определяет структуру звена списка. Термин “элемент” будем использовать и для звена, и для поля данных в звене, если это не приводит к неоднозначности. Тип данных type уточняется в каждой задаче.
6.27. Описать функцию, которая a) находит сумму всех элементов списка; b) находит максимальный элемент в заданном непустом списке; c) проверяет, упорядочены ли по возрастанию элементы списка. d) находит сумму минимального и максимального элементов в Тип данных – int.
6.28. Описать функцию, которая a) меняет местами первый и последний элементы списка; b) удаляет из списка первое вхождение элемента с заданным значением (если оно есть); 1) список с заглавным звеном; 2) список без заглавного звена;
c) удаляет из списка все вхождения элемента с заданным значением (если они есть); 1) список с заглавным звеном; 2) список без заглавного звена;
d) после каждого звена с заданным значением вставляет еще одно звено с таким же значением. Тип данных - double*, анализируются вещественные числа.
6.29. Описать функцию, которая определяет, есть ли в заданном списке хотя бы два одинаковых элемента. Тип данных – int.
6.30. Описать функцию, которая печатает в обратном порядке значения элементов списка. Тип данных - double.
6.31. Описать функцию, которая заменяет в списке все вхождения данного слова на удвоенное. Тип данных - char*.
6.32. Описать функцию, которая строит список L2 - копию списка L1. struct lnode { struct data *p; struct lnode *next; }; struct data { double f; char *s[2];};
6.33. Описать функцию, которая переворачивает список, изменяя ссылки. struct lnode { struct data *p; struct lnode *next; }; struct data { double f; char *s[2];};
6.34. Описать функцию, которая проверяет, входит ли список L1 в список L2. Тип данных - char*, анализируются строки, указатели на которые хранятся в звеньях списка.
6.35. Описать функцию, которая выполняет слияние двух упорядоченных по возрастанию списков L1 и L2, строя третий список L3: a) список L3 состоит из звеньев списков L1и L2; b) список L3 строится из копий звеньев списков L1 и L2; списки L1 и L2 не изменяются.
Тип данных - int*.
6.36. Описать функцию, которая после последнего вхождения элемента E (структуры типа data) в список L1 вставляет список L2, изменяя ссылки. struct lnode { struct data * dtpr; struct lnode *next; }; struct data { int i; char *s; };
6.37. Описать функцию, которая в упорядоченный по возрастанию список вставляет элемент, сохраняя упорядоченность. Тип данных - char*.
6.38. Описать функцию, которая формирует список L3, включая в него элементы списка L1, которые не входят в список L2. a) список L3 состоит из звеньев списка L1; b) список L3 строится из копий звеньев списка L1; список L1 не изменяется. Тип данных - int*.
6.39. Описать функцию, которая формирует список L3, включая в него в одном экземпляре элементы, входящие в список L1 и в список L2. Список L3 формируется из копий звеньев списков L1 и L2; списки L1 и L2 не изменяются. Тип данных - char*.
6.40. Описать функцию, которая формирует список L3, включая в него элементы, которые входят в один из списков (L1 или L2), но при этом не входят в другой. Список L3 формируется из копий звеньев списков L1 и L2; списки L1 и L2 не изменяются. Тип данных - char*.
Замечание: в задачах 6.41 – 6.44 требуется разработать и реализовать несколько абстрактных типов данных (АТД). Абстрактный тип данных – это тип, определяемый программистом, для которого он описывает структуру значений этого типа и множество операций с такими данными. Детали реализации АТД по возможности максимально скрыты от пользователя, и оперировать с такими данными можно только с помощью предоставленных операций (аналогично тому, как пользователь работает с предопределенными в языке типами данных). Поэтому, создавая АТД, надо тщательно продумать, какие операции предоставить пользователю, чтобы их было достаточно для выполнения традиционных действий с этими типами данных.
6.41. Разработать способ представления «разреженных» многочленов (многочленов с целыми коэффициентами, большинство из которых равно нулю). Продумать набор операций для работы с данными такого типа (создание такого многочлена, вычисление значения многочлена в некоторой точке, сложение двух многочленов с приведением подобных членов, дифференцирование многочлена и т.п.). Каждую из этих операций реализовать в виде функции.
6.42. Описать эффективный способ представления АТД «очередь»: описать структуру этого типа данных, разработать и реализовать набор операций для данных этого типа (в частности, позаботиться о действиях при переполнении очереди).
6.43. Описать способ представления АТД «стек»: описать структуру этого типа данных, разработать и реализовать набор операций для данных этого типа.
6.44. Описать способ представления АТД «набор» Набор – это аналог множества, но в наборе (в отличие от множества) может содержаться несколько экземпляров одного элемента. Разработать и реализовать набор операций для данных этого типа.
Замечание: в задачах 6.45 – 6.47 речь идет о двоичных деревьях; struct tnode { type data; /* поле данных */ struct tnode *left; /*указатель на левый узел */ struct tnode *right; /*указатель на правый узел */ } Здесь struct tnode определяет структуру узла дерева. Термин “элемент” будем использовать и для узла, и для поля данных в узле, если это не приводит к неоднозначности. Тип данных type уточняется в каждой задаче.
6.45. Используя определенные в задачах 6.42 и 6.43 АТД «очередь» и «стек», описать нерекурсивную функцию, которая a) определяет число вхождений данного элемента в двоичное дерево; b) вычисляет сумму элементов двоичного дерева; c) находит длину (количество узлов) на пути от корня дерева до ближайшего узла, содержащего данный элемент (если такого узла в дереве нет, то считать результат равным -1); d) определяет, является ли данное дерево деревом двоичного поиска (т.е. по отношению к любому узлу в этом дереве его левое поддерево содержит только те данные, значения которых меньше значения данного узла, а его правое поддерево содержит только те данные, значения которых больше значения данного узла);
e) подсчитывает количество узлов на N-ом уровне непустого двоичного дерева (корень считать узлом нулевого уровня); f) печатает все элементы двоичного дерева по уровням, начиная с корня, на каждом уровне – слева направо. Тип данных – int.
6.46. Описать рекурсивную функцию, которая a) определяет число вхождений данного элемента в двоичное дерево; b) вычисляет сумму элементов двоичного дерева; с) определяет, входит ли данный элемент в двоичное дерево; d) печатает значения данных из всех узлов дерева, не являющихся листьями; e) проверяет, идентичны ли два двоичных дерева; Тип данных – int.
6.47. Описать функцию, которая в дерево двоичного поиска вставляет новый элемент (определение дерева двоичного поиска см. задачу 6.45(d)).
6.48. Программа. Упорядочить по алфавиту и распечатать все слова входного текста.
ВВОД-ВЫВОД
Стандартный ввод-вывод
7.1. Программа. Даны натуральные числа i, n (i £ n), вещественные числа a1, a2, …,an. Найти среднее арифметическое всех чисел, кроме ai.
7.2. Программа. Даны вещественные числа a1, a2, …,a50. Распечатать “сглаженные” значения a1, a2, …,a50, заменив в исходной последовательности все члены, кроме первого и последнего, по формуле ai = (ai-1 + ai + ai+1)/3 i = 2, 3, …,49; считая, что a) после того, как получено новое значение некоторого члена последовательности, оно используется для вычисления нового значения следующего за ним члена последовательности;
b) при “сглаживании” используются лишь старые члены последовательности.
7.3. Программа. Даны вещественные числа a1, a2, … Известно, что a1 > 0 и что среди a2, a3, … есть хотя бы одно отрицательное число. Пусть a1, a2, …,an - члены данной последовательности, предшествующие первому отрицательному члену (n заранее неизвестно). Распечатать a) a1 + a2 + … +an b) a1 * a2 * …* an c) среднее арифметическое a1, a2, …,an d) a1, a1 * a2, a1 * a2 * a3,…, a1 * a2 * …* an e) a1 + 2*a2 + 3*a3 + … + (n-1)*an-1 + …n*an f) | a1 - a2 |, | a2 - a3 |, …, | an-1 - an |, | an - a1 |
7.4. Программа. Даны целые положительные числа n, a1, a2, …, an
7.5. Верно ли решена следующая задача: «читать символы из стандартного входного потока, пока код каждого следующего символа больше кода предыдущего; определить, сколько символов было прочитано» a)... i = 0; while (getchar() < getchar()) i = i + 2; b) … i = 0; c = getchar(); while (c < (c = getchar())) i++; c) … i = 0; c = getchar(); while (c < (d = getchar())) { i++; c = d;} d) … i = 0; c = getchar(); while (d = getchar(), c<d)) { i++; c = d; } e) … i = 0; c = getchar(); while (c!= EOF && (d = getchar())!= EOF && c<d) { i++; c=d; }
7.6. Сравнить следующие фрагменты программы: a) while (c = getchar() = EOF) b) while (c = getchar() == EOF) c) while ((c = getchar()) == EOF) d) while ((c = getchar()) = -1)
7.7. Допустимо ли в Си? Если "да" - опишите семантику этих действий; если "нет" - объясните почему. int i,k,sum; for (i=1; scanf("%d",&k) == 1; i++) printf("i = %d, k = %d, sum = %d\n", i, k, sum+=k);
7.8. Программа. Дана непустая последовательность слов, разделенных одним или несколькими пробелами. Признак конца текста – точка. Распечатать этот текст, удалив из него лишние пробелы (каждую группу из нескольких пробелов заменить одним пробелом).
7.9. Программа. Дана непустая последовательность слов из прописных (больших) латинских букв. Слова разделены пробелом; признак конца текста – точка. a) подсчитать количество слов в этом тексте; b) подсчитать количество слов, у которых совпадают первая и последняя буквы; c) подсчитать количество слов, являющихся некоторым фрагментом латинского алфавита; d) подсчитать количество слов, содержащих все буквы, которые входят в состав слова UNIX.
7.10. Программа. Дана непустая последовательность слов, разделенных пробелом; признак конца текста – точка. Длина каждого слова – не более 20 литер.
a) распечатать все слова, у которых не совпадают первая и последняя буквы; b) распечатать все слова, являющиеся «перевертышами», т.е. словами, одинаково читающимися слева направо и справа налево; c) распечатать текст, оставив из рядом стоящих одинаковых слов только одно; d) распечатать текст, удалив все слова, где есть символы, отличные от латинских букв.
7.11. Программа. Дана непустая последовательность слов, разделенных пробелом; признак конца текста – точка. Длина каждого слова – не более 20 литер. Распечатать данный текст следующим образом: все строки должны быть одинаковой длины (длина строки задается в командной строке); каждое слово должно быть распечатано в одной строке без переносов; если в строке несколько слов, то пробелы между ними должны быть равномерно распределены; если в строке помещается только одно слово и его длина меньше длины строки, то оно должно быть выровнено по левому краю; если длина слова больше длины строки, то такие слова из текста удаляются, при этом после распечатки текста о каждом таком слове выдается предупреждение.
7.12. Программа. Дана непустая последовательность слов из строчных (малых) латинских букв. Слова разделены пробелом; признак конца текста – точка. Напечатать все буквы, которые a) чаще других встречаются в данном тексте; b) входят в каждое слово данного текста; c) входят в наибольшее количество слов данного текста;
Работа с файлами
Замечание: в задачах 7.13 – 7.21 содержимое файлов только анализируется; в остальных задачах этого раздела создается новый файл(ы) либо изменяется содержимое данного.
7.13. Программа. Определить, сколько раз в данном файле f встречается символ ‘A’. 7.14. Программа. Определить, сколько раз в данном файле g встречается строка UNIX. 7.15. Программа. Распечатать все строки данного файла, содержащие заданную строку в качестве подстроки. Имя файла и строка задаются в командной строке. 7.16. Написать программу, определяющую какой символ чаще других встречается в данном файле. Имя файла задается в командной строке.
7.17. Написать программу, определяющую сколько строк, состоящих из одного, двух, трех и т.д. символов, содержится в данном файле. Считать, что длина каждой строки - не более 80 символов. Имя файла задается в командной строке. 7.18. Программа. Определить, какая строка является самой длинной в заданном файле. Если таких строк несколько, то в качестве результата выдать первую из них. Имя файла задается в командной строке.
7.19. Программа. Даны два непустых файла. Определить номер строки и номер символа в этой строке, где встречается первый символ, отличающий содержимое одного файла от другого. Если содержимое файлов полностью совпадает, то результат – 0, 0 и соответствующее сообщение; если один из файлов является началом другого, то результат - n+1, 1, где n - количество строк в коротком файле, и соответствующее сообщение. Имена файлов задаются в командной строке.
7.20. Программа. В файле записана непустая последовательность целых чисел (целое число – это непустая последовательность десятичных цифр, возможно начинающаяся знаком + или -). Имя файла задается в командной строке. a) найти наибольшее из этих чисел; b) определить, сколько четных чисел содержится в файле; c) определить, составляют ли эти числа арифметическую прогрессию; d) определить, образуют ли эти числа возрастающую последовательность; e) определить, сколько чисел этой последовательности являются точными квадратами;
7.21. Написать программу, определяющую, какая из строк чаще других встречается в данном файле.
7.22. Написать программу, создающую файл - копию заданного файла. Имена файлов задаются в командной строке.
7.23. Программа. Создать файл, являющийся конкатенацией других файлов. Имена файлов задаются в командной строке: fres f1 f2 …, где fres - имя файла-результата, f1, f2, … - файлы, содержимое которых должно быть записано в файл-результат.
7.24. Программа. Дан файл f. Создать файл g, полученный из файла f заменой всех его прописных латинских букв соответствующими строчными.
7.25. Программа. Дан файл f. Создать два файла f1 и f2 следующим образом: в файл f1 записать в том же порядке все строки из файла f, состоящие только из латинских букв (прописных и строчных);в файл f2 – строки файла f, состоящие только из цифр; все остальные строки файла f не записываются ни в один из этих файлов. 7.26. Программа. В конец файла f приписать строку FINISH.
7.27. Программа. В конец файла f приписать содержимое файла g.
7.28. Программа. Даны два файла, строки в которых упорядочены по алфавиту. Написать программу, осуществляющую слияние этих двух файлов в третий, строки которого тоже упорядочены по алфавиту. Имена всех трех файлов задаются в командной строке.
7.29. Программа. Дан файл и две строки. Все вхождения первой строки в файл заменить второй строкой (вхождения первой строки в качестве подстроки не рассматривать). Имя файла и строки задаются в командной строке.
7.30. Программа. Дан файл и две строки. Все вхождения первой строки в файл (в том числе и в качестве подстроки) заменить второй строкой. Имя файла и строки задаются в командной строке.
7.31. Программа. В данном файле символы каждой строки упорядочить по алфавиту. Имя файла задается в командной строке.
7.32. Программа. Строки данного файла упорядочить по алфавиту. Имя файла задается в командной строке.
7.33. Программа. В данном файле упорядочить все строки по возрастанию их длин. Имя файла и максимальная длина строки задаются в командной строке. 7.34. Программа. В файле записана непустая последовательность целых чисел, являющихся числами Фибоначчи (см. задачу 3.34). Приписать еще одно, очередное число Фибоначчи.
7.35..Программа. В файле записана непустая последовательность целых чисел (целое число – это непустая последовательность десятичных цифр, возможно начинающаяся знаком + или -). Создать новый файл, где a) все отрицательные числа заменены нулем; b) минимальный элемент последовательности поставлен в ее начало, а максимальный – в конец; c) переставлены максимальный и минимальный элементы этой последовательности; d) удалены все числа, являющиеся полными квадратами. Имена файлов задаются в командной строке.
ИНТЕРФЕЙС С СИСТЕМОЙ UNIX Низкоуровневый ввод-вывод
Замечание: во всех задачах этого раздела при вводе-выводе использовать низкоуровневые средства системы UNIX.
8.1. Верно ли решена задача: «написать версию функции a) int getchar (void) { char c; return (read (0, &c, 1) == 1)? c: EOF); } b) int getchar (void) { int c; return (read (0, &c, 1) == 1)? c: EOF); } c) int getchar (void) { char c; return (read (0, &c, 1) == 1)? (unsigned char)c: EOF); } d) int getchar (void) { char c; return (read (0, &c, 1) == 1)? (int)c: EOF); }
8.2. Написать буферизованный вариант функции int getchar(void), когда функция осуществляет ввод большими порциями, но при каждом обращении к ней выдает только одну литеру.
8.3. Используя низкоуровневый ввод-вывод, реализовать следующие функции: a) int putchar (int c) b) char *gets (char *s) c) int puts (const char *s)
8.4. Написать программу, копирующую свой стандартный ввод в стандартный вывод.
8.5. Написать программу, создающую файл - копию заданного файла. Имена файлов задаются в командной строке. a) копирование по одной литере; b) копирование блоками;
8.6. Программа. Создать файл, являющийся конкатенацией других файлов. Имена файлов задаются в командной строке (см. задачу 7.23).
8.7. Описать функцию, удваивающую в заданном файле каждую очередную четверку байт.
8.8. Программа. В каждом из данных файлов удалить те N–ки байт, в которых первый байт равен коду символа s. Имена файлов, символ s и величина N задаются в командной строке.
8.9. Описать функцию, определяющую количество символов s в тексте, состоящем из нечетных N-ок байт заданного файла. Имя файла, символ s и величина N – параметры функции.
8.10. Программа. Создать файл, содержащий значения функции sin(x)*cos(x)*exp(x) на отрезке [a,b] в точках xi = a+i*h, h = (b-a)/n, i = 0,1,…,n; имя файла и значения a, b, n задаются в командной строке.
8.11. Программа. В файле записана последовательность целых чисел. Создать файл, состоящий из чисел данного файла, значения которых меньше N. Имена файлов и величина N задаются в командной строке.
8.12. Программа. В конец файла f приписать a) число 1234; b) строку “end”;
8.13. Программа. В конец файла f приписать содержимое файла g.
8.14. Написать программу, приписывающую в конец файла f его содержимое. 8.15. Описать функцию char *get (char *f, int n, int pos), читающую n байт из файла f, начиная с позиции pos.
8.16. Программа. Содержимое файлов, длина которых меньше N байт, переписать в новый файл-результат и удалить такие файлы. Файлы, длина которых больше либо равна N байт, не изменяются и не удаляются. Имена файлов и величина N задаются в командной строке: fres f1 f2 …, где fres - имя файла-результата, f1, f2, … - файлы, содержимое которых должно быть проанализировано. 8.17. Написать программу слияния двух файлов в третий. Файл -результат формируется чередованием N-ок символов первого и второго файлов (если один из файлов длиннее другого, то его оставшаяся часть приписывается в конец файла-результата). Имена файлов и величина N задаются в командной строке.
Процессы, сигналы
|
|||||||||
Последнее изменение этой страницы: 2017-02-05; просмотров: 470; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.12.161.77 (0.114 с.) |