CSIT-303 - Data Structure (DS)

What is a data structure? Differentiate between primitive and non-primitive data structures.

Discuss time complexity and space complexity in detail. Explain best-case, worst-case and average-case time complexity with appropriate examples.

Write an algorithm for Quick sort. Use Quick sort algorithm to sort the following elements: 2, 8, 7, 1, 3, 5, 6, 4.

Write a program in C language to implement binary search algorithm. Also discuss the average behavior of the algorithm.

Define an array. Explain the need for arrays in programming. Describe the declaration, initialization and storage of arrays with suitable examples.

What is B-Tree? Write the various properties of B-Tree. Show the results of inserting the keys F, S, Q, K, C, L, H, T, V, W, M, R, N, P, A, B in order into a empty B-Tree of order 5.

What is Stack? Write a C program for linked list implementation of stack.

Explain different types of queues. Discuss circular queue, double-ended queue and priority queue along with their functions and applications.

What is spanning tree? Write down the Prim's algorithm to obtain minimum cost spanning tree. Use Prim's algorithm to find the minimum cost spanning tree in the following graph: [Image: Undirected graph with vertices A, B, C, D, E, F, G and the following weighted edges: A-B with weight 3, A-C with weight 6, B-C with weight 2, B-D with weight 4, C-D with weight 1, C-E with weight 4, C-F with weight 2, D-E with weight 2, D-G with weight 4, E-F with weight 2, E-G with weight 1, and F-G with weight 1.]

Write the Dijkstra algorithm for shortest path in a graph and also find the shortest path from 'S' to all remaining vertices of graph in the following graph: [Image: Directed graph with vertices S, A, B, C, D, E, F and the following weighted directed edges: S to A with weight 3, S to C with weight 2, S to F with weight 6, A to B with weight 6, A to C with weight 2, A to D with weight 1, C to D with weight 3, B to E with weight 1, D to E with weight 4, and F to E with weight 2.]

How to represent the polynomial using linked list? Write a C program to add two polynomials using linked list.

Discuss doubly linked list. Write an algorithm to insert a node after a given node in singly linked list.

Convert the following infix expression into postfix form. Show stack contents at each step. (A+B)*(C-D)

Discuss left skewed and right skewed binary tree. Construct an AVL tree by inserting the following elements in the order of their occurrence: 60, 2, 14, 22, 13, 111, 92, 86.

Explain Red black trees also discuss the properties of red black tree.

Construct an expression tree for the expression and apply inorder, preorder and postorder traversals on tree. (a+bc)+((de+f)*g)