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

Правильный ответ:

• # Выражение содержит числа, переменные, круглые скобки и знаки четырех арифметических операций. Его можно преобразовывать, пользуясь известными свойствами арифметических операций. Значения переменных сообщаются только после того, как выражение преобразовано в удобную для вычисления форму. Какой максимальной глубины стека достаточно, чтобы вычислить значение любого такого выражения с помощью стекового калькулятора (записывать промежуточные результаты на бумаге запрещено)?
• # Текст представляет собой последовательность строк. При этом строки можно изменять, удалять и добавлять в любое место текста. Какая структура данных лучше всего подходит для хранения и редактирования такого текста?
• # Указать, что произойдет с элементами массива a в результате выполнения следующего фрагмента программы: вещ a[100]; цел i; . . . i := 0; цикл пока i < 99 | a[i+1] := a[i]; | i := i+1; конец цикла a[0] := a[99];
• # Есть ли ограничение на длину текстовой строки в языке Си?
• # Пусть a — вещественный массив размера n (индекс элементов меняется от 0 до n-1). Определить, содержит ли следующий фрагмент программы ошибку (т.е. действительно ли тело цикла сохраняет инвариант): // Программа Быстрая сортировка дано: цел n; вещ a[n]; // вещественный массив размера n цел m; // индекс медианы утверждение: n >= 2 и 0 <= m и m < n; надо: // разделить массив на три части: // 1) слева элементы, меньшие медианы; // 2) в центре медиана; // 3) справа элементы, большие или равные медиане. цел i, j, k; вещ t; i := (-1); j := n; цикл пока i+1 < m или m < j-1 | инвариант: a[0], a[1], ..., a[i] < a[m] и | a[m] <= a[j], a[j+1], ..., a[n-1] и | i < m и m < j | | если i+1 < m | | то | | если a[i+1] < a[m] | | | то i := i+1; // расширяем левую часть | | иначе если j-1 > m | | | иначе | | | утверждение: a[i+1] >= a[m]; | | | // меняем местами элементы a[i+1] и a[j-1] | | | t := a[i+1]; a[i+1] := a[j-1]; a[j-1] := t; | | | если j-1 == m | | | | то m := i+1; // новое положение медианы | | | конец если | | | j := j-1; // расширяем правую часть | | конец если | | иначе | | утверждение: j-1 > m; | | . . . // этот случай рассматривается аналогично | | . . . // случаю i+1 < m | | | конец если конец цикла утверждение: 0 <= m и m < n и a[0], a[1], ..., a[m-1] < a[m] и a[m] <= a[m+1], a[m+2], ..., a[n-1]