 # AMCAT Previous Years Questions on Data Structures : Arrays, Linked Lists, Trees, Graphs Stacks, Queues Hash Tables Heaps

 Topics Sub- Topics Expected Questions Basic Programming 10 – 12 Questions Data Structures 6 – 8 Questions OOPs 4 – 6 Questions Miscellaneous 4 – 5 Questions

Question 1. In a Doubly Linked list how many nodes have atleast 1 node before and after it?
A. N+1
B. N
C. N-2
D. N-1

Correct Option: C

Question 2. Raman is 7 years old and he wants to color a book. The book happens to be about DSA and contains a Complete binary tree with 7 levels, he wants to use different color for every tree nodes. How many colors will he need?
A. 28
B. 31
C. 63
D. 127

Correct Option: A
to find the total no of nodes in nth level by 2^n-1 1 level 1 nodes, 2 level 3 nodes, 3 level 7 nodes, 4 level 15 nodes, 5 level 31 thus 7 has 127 nodes

Question 3. He again gets a book with x number of non-leaf nodes. How many total number of nodes will be there for hum color
A. 2x
B. x + 1
C. Log x
D. 2x + 1

Correct Option : D

Question 4. Which of the following is true about bipartite Graph?
A. no cycle of odd length
B. n^log n
C. n edges
D. a cycle of odd length

Correct Option : A

Question 5
What is Dynamic Allocation in Array?
A. Allocation that takes place at compile time
B.Allocation that take place as bipartite graph
C. memory allocation that takes place during run time rendering the resizing of an Array
D. All of these

Correct Option: C

Question 6. Raman is 7 years old and he wants to colour a book. The book happens to be about DSA and contains 8 vertices in an undirected graph with 7 levels, he wants to use a different colour for every node. How many colors will he need?
A. 63
B. 64
C. 28
D. 32

Correct Option: C
The formulae is n*(n-1)/2

Question 7. The height of a BST is given as h. Consider the height of the tree as the no. of edges in the longest path from root to the leaf. The maximum no. of nodes possible in the tree is?
A. 2h-1 -1
B. 2h+1 -1
C. 2h +1
D. 2h-1 +1

Correct Option: B

Question 8. Which type of traversal of binary search tree outputs the value in sorted order?
A. Post-order
B. Pre-order
C. In-order
D. None

Correct Option: C
Inorder gives in correct order

Question 9. the run time for traversing all the nodes of a binary search tree with n nodes and printing them in an order is a) b) c) d)
A. O(n)
B. O(√n)
C. O(log(n))
D. O(nlg(n))

Correct Option: A

Question 10
A binary search tree is generated by inserting in order the following integers: 50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24 The number of the node in the left sub-tree and right sub-tree of the root, respectively, is
A. (3, 8)
B. (8, 3)
C. (7, 4)
D. (4, 7)

Correct Option: C

Question 1
Which of the following is the correct postfix format for this infix format A + B – C + D
A. -+DC+BA
B. AB+CD+-
C. +BA-+CD
D. None of these

Correct Option: B

Question 2
Match the following –
Group A Group B
A. Stacks 1. Matrix Multiplication
B. Queue 2. Fastest Search
C. Arrays 3. FIFO
D. Trees 4. LIFO
A. A1, B3, C4, D2
B. A4, B3, C1, D2
C. A4, B3, C2, D1
D. A1, B3, C2, D4

Correct Option: B

Question 3
Priya has a box that looks like a stack and she does the following operations on empty box
PUSH(8)
PUSH(7)
POP
PUSH(1)
PUSH(3)
A. 31_8
B. 8_1_7
C. 8_1_
D. None of these

Correct Option: C

Question 4. Cloe has x number of stacks her father wants her to write a program that can perform as a queue. What will you suggest to her how many stacks must she use?
A. 1
B. 2
C. 4
D. 3

Correct Option: B

Question 5
Shalaka wants to implement a priority queue using stacks. What is the minimum number of stacks that she needs to be able to write a code for this
A. 1
B. 2
C. 3
D. 4

Correct Option: B

Question 6
These operations can be performed on which type of structure? Push, Pop, Peek
A. Queue
B. Priority Queue
C.Stack
D. Both 1 and 2

Correct Option: D
Only stack has these queue has enqueue and dequeue

Question 7
Which one of the following is an application of Queue Data Structure?
A. When a resource is shared among multiple consumers.
B. When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes
D. All the above

Correct Option: D
Queue has many applications like – 1) When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk Scheduling. 2) When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes. Examples include IO Buffers, pipes, file IO, etc.

Question 8
The retrieval of items in a stack is ……….. operation.
A. push
B. pop
C. retrieval
D. access

Correct Option: B

Question 9
In a queue, the initial values of front pointer f rare pointer r should be …….. and ……….. respectively.
A. -1, -1
B. 0, -1
C. 0, 0
D. -1, 0

Correct Option: B

Question 10
When new data are to be inserted into a data structure, but there is not available space; this situation is usually called …….
A. Memory Leak
B. Memory Full
C. OverLeak
D. Overflow

Correct Option: D

A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below. Which one of the following choices gives a possible order in which the key values could have been inserted in the table? Hash Tables Questions A. 46, 42, 34, 52, 23, 33
B. 46, 34, 42, 23, 52, 33
C. 34, 42, 23, 52, 33, 46
D. 42, 46, 33, 23, 34, 52

Correct Option: B
The sequence (A) doesn’t create the hash table as the element 52 appears before 23 in this sequence. The sequence (B) doesn’t create the hash table as the element 33 appears before 46 in this sequence. The sequence (C) creates the hash table as 42, 23 and 34 appear before 52 and 33, and 46 appears before 33. The sequence (D) doesn’t create the hash table as the element 33 appears before 23 in this sequence.

Question 2
What is a hash function? a)
A. A function has allocated memory to keys
B. A function that computes the location of the key in the array
C. A function that creates an array
D. None of the mentioned

Correct Option: B

In a hash table, there are fewer array positions than the keys, so the position of the key in the array has to be computed, this is done using the hash function.
Question 3
What is the search complexity in direct addressing?
A. O(n)
B. O(logn)
C. O(nlogn)
D. O(1)

Correct Option: D
Since every key has a unique array position, searching takes a constant time

Question 4
What is the best that can be the techniques to avoid collision?
A. Make the hash function appear random
B. Use the chaining method
C. Use uniform hashing
D. All of the mentioned

Correct Option: B
Making the hash function random is not really a good choice, although it is considered one of the techniques to avoid collisions along with chaining and simple uniform hashing. Chaining is the best

Question 5
Consider a hash function that distributes keys uniformly. The hash table size is 20. After hashing of how many keys will the probability that any new key hashed collides with an existing one exceed 0.5?
A. 40
B. 2
C. 5
D. 10

Correct Option: D
For each entry probability of collision is 1/20 {as possible total spaces =20, and an entry will go into only 1 place} Say after inserting x values probability becomes ½ (1/20).x = ½ X=10

Question 1
Which will be the best to implement the following a car comes at a petrol station and waits. The next car to get its Gas filled should be the one which has waited the longest time and thus is given priority?
A. Binary Trees
B. Heaps
C. m-way Trees
D. Binary Search Tree

Correct Option: B

Question 2
For a hashing table what is the time complexity?
A. O(1)
B. O(n2)
C. O(log n)
D. O(n)

Correct Option: A

Question 3
Every element of a data structure has an address and a key associated with it.A search mechanism deals with two or more values assigned to the same address by using the key. What is this search mechanism?
A. Linear Search
B. Binary search
C. Hash Coded Search
D. None of these

Correct Option: C

Question 4
A max-heap is a heap where the value of each parent is greater than or equal to the values of its children. Which of the following is a max-heap? A. A
B. B
C. C
D. D

Correct Option: B

Question 5
In a binary max heap containing n numbers, the smallest element can be found in time?
A. O(n)
B. O(log n)
C. O(log log n)
D. O(1)

Correct Option: A