CSIT-303 - Data Structure (DS)

Define Data Structures. With the aid of a neat diagram describe the classification of data structures.

What is asymptotic analysis? Explain Big-oh notation. Analyse and write the running time complexity of the following function. ```c A(){ int i, j, k, n; for(i = 1; i <= n; i++) for(j = 1; j * j <= n; j++) for(k = 1; 2 * k <= n; k++) printf("*"); } ```

Given an array with both positive and negative numbers, find the two elements such that their sum is closest to zero. For the below array, algorithm should give -80 and 85. Example: 1, 60, 10, 70, -80, 85. Also discuss the complexity of the process and suggest an alternate way to optimize the complexity.

Consider a two-dimensional array A of order [20*5]. The base address of the array is 840, words per memory cell is 8. Find the address of A [15, 3] using row major and column major addressing.

What is a link list? Discuss the advantages of using link list; also write about the various operations which can be performed on link list with their time complexities.

Suppose there are two singly linked lists both of which intersect at some point and become a single linked list as shown below: [Image: Diagram showing two separate singly linked lists merging into a single node with value '?', followed by another node pointing to NULL.] The head pointers of both the lists are known. Give an algorithm for finding the merging point and write the running time complexity.

Define Stack. What are the different operations, which can be performed on stack. Explain why Stack is a recursive data structure?

Write an algorithm for evaluating a postfix expression and apply the same for the given postfix expression: 4 - 5 * + 7 7 / + showing the content of stack at each step.

Explain the importance of queue. Describe why it is a bad idea to implement a linked list version a queue which uses the head of the list as the rear of the queue.

What is the advantage of circular queue over ordinary queue? Write a C program to simulate the working of circular queue of integers using array. Provide the following operations:

i) Insert

ii) Delete

iii) Display.

Show the steps of quick sort on the following set of elements. 26, 56, 47, 36, 13, 95, 85, 32. Assume the last element as the pivot element.

Design a data representation which sequentially map 'n' data objects into an array a [1, n], n_1 of these data objects are stacks and the remaining are queues. Write algorithms to add and delete elements from these objects.

What is collision? What are the methods to resolves collision? Using the hash function 'key mod 7', insert the following sequence of keys in the hash table- 32, 50, 700, 140, 76, 85, 46, 92, 70, 73 and 101. Use separate chaining technique for collision resolution.

What are L-L, L-R and R-R rotation? Write procedure for adding and deleting a node from the balanced tree and leave the resulting tree balanced.

What is the sequence of nodes visited for the following tree for a preorder, postorder, and breadth first traversal? [Image: A binary tree with root 'j', left child 'f', right child 'e'. 'f' has left child 'd'. 'd' has left child 'g'. 'e' has left child 'a', right child 'i'. 'a' has right child 'h'. 'i' has left child 'b'.]

What is Graph traversal? Discuss the difference between traversing a graph and a tree. Consider the following graph. Among the following sequences, which are the depth-first traversals of the above graph? Justify your answer by showing the adjacency list and stack contents for the traversals. [Image: A graph with vertices a, b, e, f, g, h. Edges exist between (a,e), (a,b), (a,f), (e,b), (e,g), (b,f), (b,h), (b,g), (f,h), (g,h).]

i) abeghf

ii) abfehg

iii) abfhge

iv) afghbe