Программирование - тест 151

Упражнение 1:

---

Номер 1

Рассмотрим следующий фрагмент программы  на C++:

    int a[2][3];
    const int *p = (const int *) a;
    int n;
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 3; ++j) {
            a[i][j] = 10*i + j;
        }
    }
    n = p[4];

Чему равно значение n
после выполнения этого фрагмента?

Ответ:

---

Номер 2

Рассмотрим следующий фрагмент программы  на C++:

    double a[5][3];
    const double *p = &(a[0][0]);
    const double *q = &(a[2][2]);
    int n = q - p;

Чему равно значение n
после выполнения этого фрагмента?

Ответ:

---

Номер 3

Рассмотрим следующий фрагмент программы на C++:

    int a[3][5];
    const int *p = &(a[1][1]);
    int n;
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 5; ++j) {
            a[i][j] = 10*i + j;
        }
    }
    n = p[6];

Чему равно значение n
после выполнения этого фрагмента?

Ответ:

---

Упражнение 2:

---

Номер 1

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

    typedef double* doubleptr;
    int m, n; // Размеры матрицы: число строк, столбцов
    . . .
    doubleptr* a = new doubleptr[m];
    for (int i = 0; i < m; ++i) {
        a[i] = new double[n];
    }
    // a[i][j] -- элемент i-й строки и j-го столбца

Сколько обращений к памяти необходимо сделать,
чтобы прочесть элемент матрицы в
i-й строке и j-м столбце
(считая, что значения i и j
уже находятся в регистрах процессора)?

Ответ:

---

Номер 2

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

    typedef double* doubleptr;
    int m, n; // Размеры матрицы: число строк, столбцов
    . . .
    doubleptr* a = new doubleptr[m];
    for (int i = 0; i < m; ++i) {
        a[i] = new double[n];
    }
    // a[i][j] -- элемент i-й строки и j-го столбца

Сколько памяти требуется для хранения прямоугольной
матрицы размером в 10 строк и 20 столбцов
в 32-разрядной архитектуре
(без учета памяти, используемой под описатели фрагментов кучи)?

Ответ:

---

Номер 3

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

    typedef int* intptr;
    int m, n; // Размеры матрицы: число строк, столбцов
    . . .
    intptr* a = new intptr[m];
    for (int i = 0; i < m; ++i) {
        a[i] = new int[n];
    }
    // a[i][j] -- элемент i-й строки и j-го столбца

Сколько памяти требуется для хранения прямоугольной
матрицы размером в 10 строк и 20 столбцов
в 64-разрядной архитектуре
(без учета памяти, используемой под описатели фрагментов кучи;
предполагаем, что размер элемента типа int равен 4)?

Ответ:

---

Упражнение 3:

---

Номер 1

Рассмотрим реализацию матрицы вещественных чисел
размера m строк на n столбцов
при помощи линейного массива,
в котором хранятся сначала элементы нулевой строки матрицы,
затем первой, второй и т.д., в конце - элементы (m-1)-й строки:

    int m, n; // Размеры матрицы: число строк, столбцов
    . . .
    double* a = new double[m*n];
    // a[i*n + j] -- элемент i-й строки и j-го столбца

Правильно ли работает следующая функция транспонирования
матрицы, при выполнении которой строки матрицы должны стать
столбцами, столбцы - строками, а матрица размера
m на n
превратиться в матрицу размера
n на m?

void transp(double* a, int m, int n) {
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            int idx0 = i*n + j;
            int idx1 = j*m + i;
            if (idx0 < idx1) {
                // Меняем местами 2 элемента
                double tmp = a[idx0];
                a[idx0] = a[idx1];
                a[idx1] = tmp;
            }
        }
    }
}

Ответ:

---

Номер 2

Рассмотрим реализацию матрицы вещественных чисел
размера m строк на n столбцов
при помощи линейного массива,
в котором хранятся сначала элементы нулевой строки матрицы,
затем первой, второй и т.д., в конце - элементы (m-1)-й строки:

    int m, n; // Размеры матрицы: число строк, столбцов
    . . .
    double* a = new double[m*n];
    // a[i*n + j] -- элемент i-й строки и j-го столбца

Пусть функция с прототипом

void transp(double* a, int m, int n);

реализует транспонирование
матрицы, при выполнении которого строки матрицы становятся
столбцами, столбцы - строками, а матрица размера
m на n
превращается в матрицу размера
n на m
Пусть эта функция применяется к прямоугольной матрице,
содержащей 2 строки и 4 столбца, элементы которой хранятся
в линейном массиве a Сколько элементов массива
a при этом останутся на своем месте?

Ответ:

---

Номер 3

Рассмотрим реализацию матрицы вещественных чисел
размера m строк на n столбцов
при помощи линейного массива,
в котором хранятся сначала элементы нулевой строки матрицы,
затем первой и т.д., в конце - элементы (m-1)-й строки:

    int m, n; // Размеры матрицы: число строк, столбцов
    . . .
    double* a = new double[m*n];
    // a[i*n + j] -- элемент i-й строки и j-го столбца

Пусть функция с прототипом

void transp(double* a, int m, int n);

реализует транспонирование
матрицы, при выполнении которого строки матрицы становятся
столбцами, столбцы - строками, а матрица размера
m на n
превращается в матрицу размера
n на m
Пусть эта функция применяется к прямоугольной матрице,
содержащей 3 строки и 5 столбцов, элементы которой хранятся
в линейном массиве a. Сколько элементов массива
a при этом останутся на своем месте?

Ответ:

---

Упражнение 4:

---

Номер 1

Чему равен ранг следующей матрицы:

1  2  3  4
5  6  7  8
9 10 11 12

Ответ:

---

Номер 2

Чему равен ранг следующей матрицы:

1  1  1  1
1 -1  1 -1
1  1 -1 -1

Ответ:

---

Номер 3

Чему равен ранг следующей матрицы:

0 1 1 1
1 1 1 1
1 1 1 0

Ответ:

---

Упражнение 5:

---

Номер 1

Какова асимптотическая оценка времени работы
алгоритма Гаусса приведения матрицы
к ступенчатому виду
для случая квадратной матрицы размера n?

Ответ:

---

Номер 2

Какое максимальное число операций деления может
быть выполнено в алгоритме Гаусса в процессе приведения
к ступенчатому виду квадратной матрицы размера
4?

Ответ:

---

Номер 3

Какое максимальное число операций деления может
быть выполнено в алгоритме Гаусса в процессе приведения
к ступенчатому виду прямоугольной матрицы, содержащей
3 строки и 4 столбца?

Ответ:

---

Упражнение 6:

---

Номер 1

Сколько раз в алгоритме Гаусса будет выполнена операция
перестановки местами двух строк
(с изменением знака одной из них) при приведении к
ступенчатому виду следующей матрицы:

1  2  3  4
0  1  2  3
2  5  8 11

Ответ:

---

Номер 2

Сколько раз в алгоритме Гаусса будет выполнена операция
перестановки местами двух строк
(с изменением знака одной из них) при приведении к
ступенчатому виду следующей матрицы:

1  2  3  4
0  1  2  3
2  7 10 14

Ответ:

---

Номер 3

Сколько раз в алгоритме Гаусса будет выполнена операция
перестановки местами двух строк
(с изменением знака одной из них) при приведении к
ступенчатому виду следующей матрицы:

0 1 2 3
4 5 6 7
1 2 3 4

Ответ:

---