Question 1)a) Write a detail note on big on notation used in time and space complexity.
b) Consider integer array int. a[5][4] declared in C program. If base address is 510, determine the address of the element a[3][2] with the row major and column major representation.
c) Describe the concept of ordered list with suitable example.
Question 2) Write pseudo C code to multiply two sparse matrices. What is the complexity of your code.
Question 3)a) How do you sort a linked list? Write C program to sort a linked list.
b) What are the advantages of circular linked list.
Question 4)a) Write the steps in Pseudo C code to insert an item in doubly linked list.
b) Write function to check whether two singly link lists are equal or not.
Question 5)a) Convert the following infix expression into postfix expression by showing contents of stack for every iteration.
(((A/(BΛC)) + (D&E)) - (A&C)).
Evaluate the postfix expression obtained by using stack for
A = 27, B = 3, C = 2, D = 3, E = 17.
b) Write applications of stack as a data structures.
Question 6)a) What is a queue? How is it represented in 'C' using array? What are the operations to be performed to implement a queue using array? Write pseudo codes in 'C' to implement these operations.
b) Give an ADT for queue.
Question 7)a) Write recursive 'C' function to Determine:
i) Height of a given binary tree.
ii) Width (breadth) of a given binary tree.
Question 8)a) Write a function for following:
i) Inorder traversal in a binary tree.
ii) Pre order traversal in a binary tree.
b) Define the following
i) Spanning tree.
ii) Graph.
Question 9)a) Describe index sequential search with example.
b) Write a non recursive algorithm for binary search and analyze its complexity.
Question 10)a) Write pseudo C code for bubble sort and calculate its time complexity.
b) Describe in detail Best, Worst and Average time complexity of the following
i) Quick sort.
ii) Merge sort