Data structures Viva2

What is the value of the postfix expression 6 3 2 4 + – *?

• 74

• 22

• 40

• -18

What is the advantage of a hash table as a data structure?

• easy to implement

• faster access of data

• exhibit good locality of reference

• very efficient for less number of entries

Consider an implementation of unsorted singly linked list. Suppose it has its representation with a head pointer only. Given the representation, which of the following operation can be implemented in O(1) time?

i) Insertion at the front of the linked list ii) Insertion at the end of the linked list iii) Deletion of the front node of the linked list iv) Deletion of the last node of the linked list

• I and II

• I and III

• I, II and III

• I, II and IV

What is the outcome of the prefix expression +, -, *, 3, 2, /, 8, 4, 1?

• 12

• 11

• 5

• 4

What would be the time complexity if user tries to insert the element at the end of the linked list (head pointer is known)?

• 1. O(1)

• 1. O(n)

• 1. O(logn)

• 1. O(nlogn)

Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree?

• 7 5 1 0 3 2 4 6 8 9

• 0 2 4 3 1 6 5 9 8 7

• 0 1 2 3 4 5 6 7 8 9

• 9 8 6 4 2 3 0 1 5 7

The average depth of a binary search tree is:

• O(n^0.5)

• O(n)

• O(log n)

• O(n log n)

The postorder traversal of a binary tree is 8, 9, 6, 7, 4, 5, 2, 3, 1. The inorder traversal of the same tree is 8, 6, 9, 4, 7, 2, 5, 1, 3. The height of a tree is the length of the longest path from the root to any leaf. The height of the binary tree above is ________ .

• 2

• 4

• 3

• 5

An advantage of chained hash table (external hashing) over the open addressing scheme is

• Worst case complexity of search operations is less

• Space used is less

• Deletion is easier

• None of the these

Given the preorder traversal of a binary tree is 1, 2, 4, 5, 3, and the inorder traversal is 4, 2, 5, 1, 3, what is the postorder traversal of the same tree?

• 4 5 2 3 1

• 5 4 2 1 3

• 4 2 5 3 1

• 2 4 5 1 3