Inha university in tashkent

INHA UNIVERSITY IN TASHKENT

School of Computers and Information Engineering

Fall semester 2018

Data Structures

Practice-1

Submission Date: 22 /10/ 2018 (17:00 Hr)

1. 
   Translate insertion sort into function INSERTION (A, N) which sort the array A with N elements. Test the program using:
   
   1. 
      44, 33, 11, 55, 77, 90, 40, 60, 99, 22, 88, 66
      
   2. 
      D, S, T, A, S, T, R, U, C, T, U, R, E, S
      

2. 
   Translate quicksort into a program QUICKSORT(A, N, NUMB) which sorts the array A with N elements and which also count the number NUMB of comparisons.
   

3. 
   Write a program in C++ to multiply every element of the linked list with 10.
   

4. 
   Write a program in C++ to insert a new node at the beginning of a Singly Linked List.
   

5. 
   Suppose you have a reference to a node in a singly linked list and this node is not the last one in the list.
   

(a) How could you remove the element at this node from the list, while maintaining a proper linked list data structure? Note that this would reduce the number of nodes by 1.

(b) How could you insert an element into the list at the position before this node?

6. 
   Suppose that T1(n) and T2(n) are the time complexities of two program fragments P1 and P2 where T1(n) = O(f(n)) and T2(n) = O(g(n)), what is the time complexity of program fragment P1 followed by P2.