Т.В. Руденко - Сборник задач и упражнений по языку Си, страница 8

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

Каждую из этих операций реализовать в виде функции.366.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) проверяет, идентичны ли два двоичных дерева;37Тип данных – int .6.47.

Описать функцию, которая в дерево двоичного поиска вставляетновый элемент (определение дерева двоичного поиска см. задачу 6.45(d)).6.48. Программа. Упорядочить по алфавиту и распечатать все словавходного текста.7. ВВОД-ВЫВОД7.1Стандартный ввод-вывод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 + … +anb) a1 ∗ a2 ∗ …∗ anc) среднее арифметическое a1, a2, …,and) a1 , a1 ∗ a2 , a1 ∗ a2 ∗ a3 ,…, a1 ∗ a2 ∗ …∗ ane) a1 + 2∗a2 + 3∗a3 + … + (n-1)∗an-1 + …n∗anf) | a1 - a2 |, | a2 - a3 | , … , | an-1 - an |, | an - a1 |7.4. Программа. Даны целые положительные числа n, a1, a2, …, an(n ≥ 4).

Считать, что a1, a2, …, an - это измеренные в сотых долях секунды результаты n спортсменов в беге на 100 метров. По этим результатам составитькоманду из четырех лучших бегунов для участия в эстафете 4×100, т.е. распечатать номера спортсменов, имеющих четыре лучших результата.7.5. Верно ли решена следующая задача: «читать символы из стандартного входного потока, пока код каждого следующего символа больше кода предыдущего; определить, сколько символов было прочитано»38a) ...

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) распечатать текст, удалив все слова, где есть символы, отличные отлатинских букв.397.11. Программа. Дана непустая последовательность слов, разделенныхпробелом; признак конца текста – точка.

Длина каждого слова – не более 20 литер. Распечатать данный текст следующим образом: все строки должны бытьодинаковой длины ( длина строки задается в командной строке ); каждое словодолжно быть распечатано в одной строке без переносов; если в строке несколько слов, то пробелы между ними должны быть равномерно распределены; еслив строке помещается только одно слово и его длина меньше длины строки, тооно должно быть выровнено по левому краю; если длина слова больше длиныстроки, то такие слова из текста удаляются, при этом после распечатки текста окаждом таком слове выдается предупреждение.7.12. Программа. Дана непустая последовательность слов из строчных(малых) латинских букв. Слова разделены пробелом; признак конца текста –точка. Напечатать все буквы, которыеa) чаще других встречаются в данном тексте;b) входят в каждое слово данного текста;c) входят в наибольшее количество слов данного текста;7.2Работа с файламиЗамечание: в задачах 7.13 – 7.21 содержимое файлов только анализируется; востальных задачах этого раздела создается новый файл(ы) либоизменяется содержимое данного.7.13.

Программа. Определить, сколько раз в данном файле f встречаетсясимвол ‘A’.7.14. Программа. Определить, сколько раз в данном файле g встречаетсястрока UNIX.7.15. Программа. Распечатать все строки данного файла, содержащиезаданную строку в качестве подстроки. Имя файла и строка задаются в командной строке.7.16. Написать программу, определяющую какой символ чаще другихвстречается в данном файле. Имя файла задается в командной строке.7.17.