Қарапайым таңдау әдісі көмегімен массивтың теріс элементтерін сұрыпта
Пән бойынша тапсырмалар: мәліметтерді өңдеудің құрылымдары мен алгоритмдері
Төменде пән аясындағы тапсырмалар екі бөлімге бөлініп берілген: біріншісі — деректер құрылымдары тақырыптары, екіншісі — сұрыптау және массив/матрицаға қатысты практикалық тапсырмалар. Мәтін мазмұны редакцияланып, терминдер мен сөйлем құрылымы реттелді.
1-тапсырма. Деректер құрылымдары тақырыптары
Сызықтық құрылымдар
Мәтіндерге тізбектеліп енгізілетін мәліметтердің сызықтық құрылымдық типтері.
Циклдік тізімдер
Элементтері шеңбер түрінде байланысатын тізімдер және олармен жұмыс істеу тәсілдері.
Стектер
LIFO қағидасы бойынша жұмыс істейтін деректер құрылымы.
Кезектер
FIFO қағидасы бойынша ұйымдастырылатын құрылымдар және қолданылуы.
Ағаштар және тармақтар
Иерархиялық құрылымдар: түйіндер, деңгейлер, ұрпақтар және өту алгоритмдері.
Екілік (бинарлық) ағаштар
Екілік ағаштардың құрылымы және негізгі операциялары.
Екілік іздеу ағаштары
Реттілік қасиеті бар екілік ағаштар: іздеу, қосу, жою.
Массив арқылы берілген бинарлық ағаштар
Ағашты массив индексі арқылы көрсету және артықшылық/шектеулері.
Пирамидалар (heap)
Heap құрылымы, heapify және қолданылатын негізгі амалдар.
Балансталған ағаштар
Биіктігі бақыланатын ағаштар және іздеуді жеделдету идеясы.
Графтар
Түйіндер мен қабырғаларға негізделген модель: бағытталған/бағытталмаған графтар, салмақтар, өту тәсілдері.
2-тапсырма. Сұрыптау және массив/матрица есептері
Сұрыптау процедурасын элементтер кему ретімен орындалатындай етіп өзгертіңіз.
Берілген бүтін сандар тізбегі кему ретімен сұрыпталғанын тексеріңіз. Егер сұрыпталмаған болса, сұрыптаңыз.
Массивті сұрыптаңыз және массивтегі қайталанбайтын сандардың санын есептеңіз.
Сұрыптау процедурасын i параметрінің мәні әр қадам сайын өсетіндей етіп өзгертіңіз.
Қарапайым таңдау әдісі (Selection sort) арқылы
Массивтің жұп элементтерін сұрыптаңыз.
Массивтің тақ орындарда тұрған элементтерін сұрыптаңыз.
Массивтің оң элементтерін сұрыптаңыз.
Массивтің теріс элементтерін сұрыптаңыз.
Матрица және қолданбалы есептер
n×m матрицасында бағандарды өсу ретімен сұрыптаңыз.
Футбол командаларының тізімі және әр команданың чемпионатта алған ұпайы берілген. Ұпайлар саны бірдей командалар жоқ. Жүлдегерлерді басып шығарыңыз.
Реттелмеген массивте қайталанатын элементтер болуы мүмкін. Бірдей элементтер тобының ішінен біреуін ғана қалдырыңыз.
Турнир кестесі және файлмен жұмыс
Жарыстың турнирлік кестесі A квадрат матрицасы арқылы берілген. Мұндағы Aij — i командасының j командасының қақпасына соққан голдар саны.
Командаларды диагональ бойымен келесі критерий бойынша орналастырыңыз: жеңістер саны − жеңілістер саны. Тең болған жағдайда — соғылған және жіберілген голдар айырмасы бойынша.
Енгізілетін мәліметтерді (алғашқы массивті) және шығатын мәліметтерді (сұрыпталған массивті) бүтін сандардан тұратын мәтіндік файл ретінде қалыптастырыңыз. Барлық нұсқалар үшін көпіршік сұрыптау (bubble sort) процедурасын қолданыңыз.
Ең жақсы және ең жаман жағдайларда орындалатын ауыстырулар мен салыстырулар санын есептеңіз.
Берілген қатардың алғашқы n элементін өсу ретімен орналастырыңыз, ал сол элементтерді кему ретімен басып шығарыңыз.
Біздің мысалда соңғы екі элемент алдын ала сұрыпталған болғандықтан, олардың орын ауыстыруы жалпы ретке әсер етпейді.
Сондықтан алгоритмді жақсарту үшін әр өтуде элементтердің ауыстырылған-ауыстырылмағанын белгілеп отырыңыз: егер ауыстыру болмаса, сұрыптауды ерте аяқтауға болады.
Назар аударатын негізгі талап
Көрсетілген сұрыптау тапсырмаларын орындау кезінде барлық нұсқаларда көпіршік сұрыптау процедурасын қолдану қажет, ал енгізу/шығару деректерін мәтіндік файл форматында рәсімдеу керек.