Контрольная работа по «Языки и системы программирования»

Министерство образования Российской Федерации

Российский  государственный профессионально-педагогический университет

Институт  Электроэнергетики и информатики

Факультет Электроэнергетики

Кафедра микропроцессорной управляющей  вычислительной техники 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Контрольная работа

по дисциплине «Языки и системы программирования»

вариант 23 
 
 
 
 
 
 
 
 
 

Выполнил: студент гр. ВТ-203

Фазулов. Р.Н. 
 
 
 
 
 
 
 
 
 
 
 
 

Екатеринбург

2012

1. Дать графическую интерпретацию списковой структуры, заданной линейным выражением

((a),(b,( )),(c,( ),d),(e))

 

2. Построить алгоритм исключения элемента из очереди длиной m и занесения элемента в стек длиной n (значения m и n выбираются произвольно)

Очередь - длина m

Стек – длина  n

k – номер вершины стека

i – идентификатор начала очереди

j – идентификатор конца очереди 

Начало

    Если i<>j

        то начало

            Если k<>n

                то начало

                    a[k]:=g[i];

                    i:=i+1;

                    k:=k+1;

                конец

            иначе вывод «Стек переполнен»;

        конец

    иначе вывод «Очередь пуста»;

Конец. 
 
 
 
 
 

3. Написать процедуру преобразования арифметического выражения в обратную польскую запись. 

(a/c-b↑2)*(d-x)   – исходное выражение

ac/b2↑-dx-*   – вид в обратной польской записи 
 
 
 

1. Начать  работу
2. Поместить «a» в строку
3. Поместить «/» в стек
4. Поместить «c» в строку
5. Поместить «/» из стека в строку
6. Поместить «-» в стек
7. Поместить «b» в строку
8. Поместить «↑» в стек
9. Поместить «2» в строку
10. Поместить «↑» из стека в строку
11. Поместить «-» из стека в строку
12. Поместить «*» в стек
13. Поместить «d» в строку
14. Поместить «-» в стек
15. Поместить «x» в строку
16. Поместить «-» из стека в строку
17. Поместить «*» из стека в строку
18. Закончить работу

 

4. Построить матрицу, задающую отношение «X дружит с Y» на множестве студентов вашей группы. Определить, является ли это отношение рефлексивным. 

Фамилия	Бирюков	Дорогая	Дробинина	Кожемяко	Косарев	Кузнецов	Кожемяко	Медведев	Михалев	Перкин	Присяжнюк	Собенина	Cпирин	Стариков	Старкова	Тагирова	Ульянова	Юрченко
Бирюков	1	1	1	0	1	0	1	0	0	0	0	0	1	0	1	1	0	0
Дорогая	1	1	0	1	0	0	0	0	0	0	0	1	0	0	0	0	0	1
Дробинина	1	0	1	0	1	0	1	0	0	0	0	0	0	0	0	1	0	0
Кожемяко	0	1	0	1	0	0	0	0	0	0	0	1	0	0	0	0	0	0
Косарев	1	0	1	0	1	1	1	0	1	0	1	0	0	0	1	0	0	1
Кузнецов	0	0	0	0	1	1	0	0	0	0	0	0	0	0	0	0	0	1
Кожемяко	1	0	1	0	1	0	1	0	0	0	0	0	1	0	1	1	0	0
Медведев	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0
Михалев	0	0	0	0	1	0	0	0	1	0	1	0	0	0	1	1	0	1
Перкин	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0
Присяжнюк	0	0	0	0	1	0	0	0	1	0	1	0	0	0	0	0	0	1
Cобенина	0	1	0	1	0	0	0	0	0	0	0	1	0	0	0	0	0	0
Cпирин	1	0	0	0	0	0	1	0	0	0	0	0	1	1	1	0	0	0
Стариков	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1	0	0	0
Старкова	1	0	0	0	1	0	1	0	1	0	0	0	1	1	1	1	0	0
Тагирова	1	0	1	0	0	0	1	0	1	0	0	0	0	0	1	1	0	1
Ульянова	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1
Юрченко	0	1	0	0	1	1	0	0	1	0	1	0	0	0	0	1	1	1

 

Отношение рефлексивное, т.к. отражается относительно диагонали. 
 
 

5. Спроектировать алгоритм сравнения двух строк при различных способах хранения:

B) каждая строка хранится в последовательных полях памяти, началом которых служит специальное поле со счетчиком числа составляющих строку букв.

C) Способ, при котором действует специальный символ конца строки «X». 

Пусть сравниваются две строки a и b

строка a:  

5

т

е

к

с

т

                                                                     

строка b:  

т

е

к

с

т

X

                                                                       i – номер ячейки(счетчик)

1.Начать работу

2.Сравнивать ячейки (i+1) строки a с ячейками i строки b до тех пор пока ячейки равны и по достижении конца строки a или символа «X» строки b вывести на экран «Строки равны», иначе вывести на экран «Строки не равны»

3.Закончить работу.  

6. Сконструировать алгоритм построения списковой структуры графа G(U,X) по заданной матрице смежности

X1     0   1   0   0      8

X2     1   1   1   0      7

X3     1   0   0   1      2

X4     1   0   1   1      2

Графическое представление графа:

 

По графическому представлению графа можно вывести  представляющую его списковую структуру. На основе матрицы смежности построим следующую таблицу:

Идентификатор вершины	Число дуг, выходящих  из вершины	Указатель на 1-ю  вершину	Указатель на 2-ю  вершину	Указатель на 3-ю  вершину	Указатель на 4-ю  вершину
X1(8)	1	–	1	–	–
X2(7)	3	1	1	1	–
X3(2)	2	1	–	–	1
X4(2)	3	1	–	1	1

 
 

1. Начать  работу
2. Поместить вершину X1 в ячейку 1
3. Поместить вершину X2 в ячейку 2
4. Поместить вершину X3 в ячейку 3
5. Поместить вершину X4 в ячейку 4
6. Под 1-й вершиной указать число дуг, выходящих из нее(1)
7. Под 2-й вершиной указать число дуг, выходящих из нее(3)
8. Под 3-й вершиной указать число дуг, выходящих из нее(2)
9. Под 4-й вершиной указать число дуг, выходящих из нее(3)
10. Соединить 1-ю вершину со 2-й
11. Соединить 2-ю вершину с 1-й
12. Соединить 2-ю вершину с собой
13. Соединить 2-ю вершину с 3-й
14. Соединить 3-ю вершину с 1-й
15. Соединить 3-ю вершину с 4-й
16. Соединить 4-ю вершину с 1-й
17. Соединить 4-ю вершину с 3-й
18. Соединить 4-ю вершину с собой
19. Вывести результат
20. Закончить работу.

 

7. Дать графическое представление дерева сортировки, построить таблицу следов его вершин и создать алгоритм формирования дерева сортировки по заданной последовательности элементов.

54, 1, 9, 30, 15, 14, 2, 4, 7

Таблица следов вершин:

X1(54)	1
X2(1)	10
X3(9)	101
X4(30)	1011
X5(15)	10110
X6(14)	101100
X7(2)	1010
X8(4)	10101
X9(7)	101011

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

Т.к. в  таблице ASCII всего 255 символов, а W расположен под номером 87, то W:=87, min:=1, max:=255

1. Начало
2. i:=0
3. min:=1
4. max:=255
5. W:=87
6. f:=’ключ не найден’
7. пока min<max и i:=0
8.     Начало
9.         j:=(max+min)/2
10.         если W=C[j]
11.             то начало
12.                 f:=’ключ найден’
13.                 i:=j
14.             конец
15.         иначе, если W>C[j]
16.             то min:=j+1
17.         иначе max:=j-1
18.     Конец
19. Вывод (j,f)
20. Конец.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Использованные  источники:

1. Лекции по дисциплине Я и СП

2. Методические указания к выполнению контрольной работы по дисциплине «Языки и Системы Программирования»

3. Интернет