Узел списка

A B C D E F 10 11 12 13

02DC1E 000000 749E31 0000FF 390000 000010 66885A 00000C 00ADC0 000006

Признак конца списка голова списка h

Рис. 8. Содержимое Spis после создания и сортировки. Поле link каждого узла содержит смещение в Spis, заданное как индекс слова ГМ

На рис. 9 показана работа программы при различных значениях параметра fw.

a)fw=8

Отсортированный список

E 1E 33 50 8E B8 BD C0 D8

б)fw=35

Отсортированный список

CD10BA 00033442D0 003C0F680D 0056E01740 00F19E0285 01C815A04E 03000B707B 03484187AE 05278C5C80 062F44E3B6

в)fw=48

Отсортированный список

CD10BA77 03B409CD2106 06B000B707BA 10B402B700BA 138ED81E07B4 1E33C050B8BD 1EB8BD138EC0 4F18B90000CD 8ED8BE0000FC BF4800B8F813

г)fw=61

Отсортированный список

A2175320B68 0273484187AE2F44 03C6780A1717A271 09A01E7483E0EAF7 0CD10B402B700BA0 148ED8BE0000FCB9 1B60781ED01AC002 1B83DD278C5C8000 1C2003F0CB02E420 1C7605FB0005C0D0

Рис. 9. Создание и прохождение списка для различных форматов слов ГМ

Варианты курсового проекта

В предлагаемых вариантах курсовой работы значения fw кратны 4 или 8. Это обстоятельство должно учитываться студентом при разработке структуры данных и алгоритмов команд с целью адаптации программы к конкретному значению fw и получения более эффективной ее реализации на реальной ЭВМ. Кратность fw особенно сильно может повлиять на алгоритмы чтения и записи слов ГМ в память.

1. fw=60 бит; Nr=3; Fk={ S1,S2; S,R1,R2 }; Nop=1,2,3. k1: команда сравнения; k2: команда пересылки; k3: команда условного перехода (ОР S1,S2,S3).

Задача. Отсортировать массив данных методом выбора.

2. fw=36 бит; Nr=4; Fk={ S1,S2; S,R }; Nop=2. k1: команда создания нового узла; к2: команда удаления узла списка; к3: команда перехода к следующему узлу списка;

Задача. Создать линейный список целых чисел и удалить из него все отрицательные числа.

3. fw=44 бит; Nr=3; Fk={ S1,S2; S,R }; Nop=2. k1: команда чтения элемента матрицы А[I,j]; к2: команда записи элемента матрицы А[I,j]; к3: команда суммирования двух слов;

Задача. В матрице A[1..5,1..7] переставить столбцы по возрастанию сумм столбцов матрицы.

4. fw=60 бит; Nr=3; Fk={R1,R2; S1,S2; R,S}; Nop=2. k1: команда условного перехода вида: OP S1,S2,S3; k2: команда чтения-записи слова; k3: команда нахождения минимального из 2-х слов.

Задача. Выполнить слияние 2-х отсортированных списков в третий отсортированный список.

5. fw=52 бит; Nr=4; Fk={ S1,S2; S,R }; Nop=2. k1: команда чтения элемента матрицы А[I,j]; к2: команда записи элемента матрицы А[I,j]; к3: команда сравнения двух элементов матрицы;

Задача. В матрице A[1..8,1..6] в строках, содержащих нуль, расположить элементы по убыванию.

6. fw=44 бит; Nr=4; Fk={ S1,S2; S,R }; Nop=2. k1: команда чтения элемента матрицы А[I,j]; к2: команда записи элемента матрицы А[I,j]; к3: команда сравнения двух элементов матрицы;

Задача. В матрице А(n,m) отсортировать столбец с максимальным элементом.

7. fw=28 бит; Nr=4; Fk={ S1,S2; S,R }; Nop=2. k1: команда чтения элемента матрицы А[I,j]; к2: команда записи элемента матрицы А[I,j]; к3: команда сравнения двух элементов матрицы;

Задача. В матрице А(6,6) обменять строку и столбец, на пересечении которых находится максимальный элемент матрицы.

8. fw=52 бит; Nr=4; Fk={ S1,S2; S,R }; Nop=2. k1: команда создания нового узла; к2: команда удаления узла списка; к3: команда перехода к следующему узлу списка;

Задача. Создать линейный список целых чисел и удалить из него все нечетные числа.

9. fw=44 бит; Nr=4; Fk={ S1; S1,S2; S1,S2,S3 }; Nop=1,2,3. k1: команда сравнения; k2: команда пересылки; k3: команда условного перехода (ОР S1,S2,S3).

Задача. Отсортировать массив данных методом вставок.

10. fw=44 бит; Nr=3; Fk={ R,S }; Nop=2. k1: команда чтения элемента 2-мерного массива по значениям его индексов I,J; k2: команда записи элемента 2-мерного массива по значениям его индексов I,J; k3: команда сравнения 2-х слов.

Задача. В заданном 2-мерном массиве определить номер строки и номер столбца MAX и MIN элементов.

11. fw=52 бит; Nr=4; Fk={ S1; S1,S2; S1,S2,S3 }; Nop=1,2,3. k1: команда сравнения; k2: команда пересылки; k3: команда условного перехода (ОР S1,S2,S3).

Задача. Отсортировать массив данных методом “пузырька”.

12. fw=36 бит; Nr=3; Fk={ R,S }; Nop=2. k1: команда чтения элемента 2-мерного массива по значениям его индексов I,J; k2: команда записи элемента 2-мерного массива по значениям его индексов I,J; k3: команда сложения 2-х слов. K4: команда вычитания 2-х слов.

Задача. В матрице A[1..8,1..8] сумму элементов над главной диагональю поделить на сумму элементов под побочной диагональю.

13. fw=20 бит; Nr=3; Fk={ R,S }; Nop=2. k1: команда чтения элемента 2-мерного массива по значениям его индексов I,J; k2: команда записи элемента 2-мерного массива по значениям его индексов I,J; k3: команда сравнения 2-х слов.

Задача. В созданном двумерном массиве A[1..m,1..n] заменить нулями элементы, стоящие в строках или столбцах, где имеются нули.

14. fw=44 бит; Nr=3; Fk={ S1,S2; S,R }; Nop=2. k1: команда чтения элемента матрицы А[I,j]; к2: команда записи элемента матрицы А[I,j]; к3: команда суммирования двух слов;

Задача. В матрице А(n,n) две ее диагонали образуют 4 сектора. Вычислить суммы элементов в каждом секторе без учета диагональных элементов матрицы.

15. fw=36 бит; Nr=3; Fk={S1,S2; R,S}; Nop=1,2. k1: команда извлечения элемента из стека; k2: команда выполнения арифметических операций +, -, *, / для любых целых аргументов; k3: команда чтения слова памяти.

Задача. Вычислить значение выражения, записанного в стеке польской записью.

16. fw=60 бит; Nr=3; Fk={ R1,R2; R,S; S1,S2 }; Nop=2. k1: команда нахождения минимального элемента в строке матрицы;

k2: команда нахождения максимального элемента в столбце матрицы;

k3: команда чтения слова памяти.

Задача. Найти седловое число в матрице и его индексы.

17. fw=12 бит; Nr=3; Fk={ S1,S2; R,S; S,I }; Nop=1,2. k1: команда добавления элемента в стек(1 операнд); k2: команда формирования польской записи выражения во внутренних скобках; k3: команда чтения слова памяти.

Задача. Записать выражение в стек в формате польской записи.

18. fw=12 бит; Nr=3; Fk={S1,S2; R,S}; Nop=1,2. k1: команда извлечения элемента из стека; k2: команда выполнения арифметических операций +, -, *, / для любых целых аргументов; k3: команда чтения слова памяти.

Задача. Вычислить значение выражения, записанного в стеке польской записью.

19. fw=44 бит; Nr=4; Fk={ S1; S1,S2; S1,S2,S3 }; Nop=1,2,3. k1: команда сравнения; k2: команда пересылки; k3: команда условного перехода (ОР S1,S2,S3).

Задача. Вычеркнуть k строку и m столбец, содержащие минимальное значение матрицы A[1..7,1..5], записав в новую матрицу B[1..6,1..4].

20.fw=52 бит; Nr=3; Fk={ R1,R2; R,S; S1,S2 }; Nop=2. k1: команда выборки элемента матрицы A[i,j];

k2: команда записи элемента матрицы A[i,j];

k3: команда чтения слова памяти.

Задача. Создать массив A[1..7,1..5]. Известно, что среди его элементов два и только два равны между собой. Напечатать их индексы.

21. fw=68 бит; Nr=4; Fk={ S1; S1,S2; }; Nop=1,2. k1: логическая команда AND; k2: логическая команда OR; k3: логическая команда NOT; k4: логическая команда XOR.

Задача. 1.Для k1,k2,k3,k4 провести тестирование

2. Пример побитовой обработки с массивом данных.

22. fw=44 бит; Nr=3; Fk={ S1,S2; S,R }; Nop=2. k1: команда чтения элемента матрицы А[I,j]; к2: команда записи элемента матрицы А[I,j]; к3: команда суммирования двух слов;

Задача. В матрице А(n,n) две ее диагонали образуют 4 сектора. Вычислить суммы элементов в каждом секторе без учета диагональных элементов матрицы.

23. fw=12 бит; Nr=3; Fk={ S1,S2,s3; S,I }; Nop=2,3. k1: команда удаления символа из строки; k2: команда поиска подстроки; k3: команда записи символа в строку.

Задача. В символьной строке удалить все вхождения заданной подстроки. Все операции удаления осуществить в рамках исходной строки.

24. fw=52 бит; Nr=4; Fk={S1; S1,S2 }; Nop=1,2. k1: циклический сдвиг вправо на n разрядов; k2: циклический сдвиг влево на n разрядов; k3: арифметический сдвиг вправо на один разряд; k4: арифметический сдвиг влево на один разряд.

Задача. 1. Для k1,k2,k3,k4 всех форматов провести тестирование с фиксацией всех особых случаев.

2. Пример побитовой обработки с массивом данных.

25. fw=20 бит; Nr=4; Fk={ S1,S2; S,I }; Nop=2. k1: команда сравнения 2-х символов; k2: команда вставки символа в слово; k3: команда удаления слова из символьной строки.

Задача. Удалить слова со сдвоенными буквами («анна», «класс» и т. п.) в символьном массиве. В оставшихся словах в середину каждого слова вставить букву «а».

26. fw=60 бит; Nr=3; Fk={ S1,S2; S,R1,R2 }; Nop=1,2,3. k1: команда сравнения; k2: команда пересылки; k3: команда условного перехода (ОР S1,S2,S3).

Задача. Отсортировать массив данных методом выбора.

27. fw=36 бит; Nr=4; Fk={ S1,S2; S,R }; Nop=2. k1: команда создания нового узла; к2: команда удаления узла списка; к3: команда перехода к следующему узлу списка;

Задача. Создать линейный список целых чисел и удалить из него все отрицательные числа.

28. fw=44 бит; Nr=3; Fk={ S1,S2; S,R }; Nop=2. k1: команда чтения элемента матрицы А[I,j]; к2: команда записи элемента матрицы А[I,j]; к3: команда суммирования двух слов;

Задача. В матрице A[1..5,1..7] переставить столбцы по возрастанию сумм столбцов матрицы.

29. fw=44 бит; Nr=3; Fk={ S1,S2; S,R }; Nop=2. k1: команда чтения элемента матрицы А[I,j]; к2: команда записи элемента матрицы А[I,j]; к3: команда суммирования двух слов;

Задача. В матрице А(n,n) две ее диагонали образуют 4 сектора. Вычислить суммы элементов в каждом секторе без учета диагональных элементов матрицы.

30. fw=44 бит; Nr=3; Fk={ S1,S2; S,R }; Nop=2. k1: команда чтения элемента матрицы А[I,j]; к2: команда записи элемента матрицы А[I,j]; к3: команда суммирования двух слов;

Задача. В матрице A[1..5,1..7] переставить столбцы по возрастанию сумм столбцов матрицы.