JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B.Tech II DATA STRUCTURES Previous Question Paper (November/December - 2018 - R13)

Define Time and Space Complexity.

What is data structure? What are the factors that influence the choice of a particular data structure?

Differentiate between Dequeue and Priority queue.

Given the following arithmetic expression in infix notation as 12/(7-3)+2*(3+8)-7. Translate this expression into postfix notation and then evaluate it.

If there are 27 nodes in a complete binary tree, what will be its height and how many nodes will be in the last level?

What is the time complexity of DFS traversal as an n-vertex simple graph that is represented with adjacent matrix structure?

What is hash collision? Explain with an example.

Compare linear search with binary search.

What is Trie? Explain the suffix trie with an example.

What are the properties of B-Tree?

Define Double linked list. Write an algorithm to delete an element from the existing linked list.

Explain the algorithm specifications and various notations used to analyze the performance of an algorithm.

Describe the Asymptotic notations with an example.

Write an algorithm that appends two lists together. Use linked list.

What is circular queue? Write a C function to insert an item in the circular queue.

Define stack. Explain the operations of stack with an example.

Write a C program which converts the infix expression into postfix expression.

What is Dequeue? Explain the operations of Dequeue with an example.

Write insertion and deletion algorithm of Max Heap.

From the following graph find the traversal of nodes using BFS and DFS.

Explain various graph representations with an example and mention the pros and cons of each representation.

Construct the Max heap of the following elements {60, 10, 40, 20, 90, 30, 50, 70, 80}

Write the algorithm for Insertion sort. Explain their best case and worst case complexities.

Insert the following list of elements into the Hash table by using Quadratic probing (size of the table is 10) {89, 56, 9, 20, 45, 36, 11, 77}

Sort the following list of elements by using Quick sort, show the contents of the list at the end of each pass. {75, 10, 20, 70, 80, 90, 100, 40, 30, 50}

Explain the complexity of quick sort algorithm.

Construct the Splay tree for the following list of elements (Splay node is 89) {22, 55, 6, 7, 66, 49, 3, 34, 67, 56, 89}

Write algorithms for rotations of an AVL.

Construct the Red-Black tree for following elements {45, 32, 78, 56, 13, 27, 19, 82, 14}

Draw the flow chart for KMP algorithm.