In linked list representation of tree the node is divided into how many parts MCQ

Data Structure MCQ (Multiple Choice Questions)

Data Structure MCQ

1) For sorting random linked list with the minimum time complexity, which of the following algorithm requires?

1. Merge Sort
2. Bubble
3. Selection Sort
4. Insertion Sort

2) Which of the following data structure used to implement priority queues efficiently?

1. Stack
2. Linked List
3. Binary Heap
4. None of Above

3) Which of the following data structure works on insertion at only one end but deletions at both ends of the list?

1. Priority Queues
2. Input - restricted deque
3. Output - restricted deque
4. Stack

4) For solving the N-Queens problem, which of the algorithm need to use?

1. Dynamic
2. Divide and Conquer
3. Backtracking
4. None of Above

5) Which of the following algorithm takes the same time in all three cases (e.g., best, average, and worst)?

1. Merge Sort
2. Quick Sort
3. Selection Sort
4. Bubble Sort

6) Which data structure is best for checking whether an expression has balanced parenthesis?

1. Tree
2. Linked List
3. Graph
4. Stack

7) The balance factor range of any node that can be accepted in the AVL tree?

1. [-2, -1, 0]
2. [-2, -1, 0, 1]
3. [-1, 0, 1]
4. None of the Above

8) The minimum time required to check if an integer appears more than n/2 times in the array, assume that the array is sorted?

1. O(log n)
2. O(n)
3. O(1)
4. None of the Above

9) For declaring an array, which of the following way is correct?

1. int arr;
2. int arr[10];
3. arr{10};
4. None of the above

10) For implementing a breadth-first search, which of the following data structure is used?

1. Stack
2. Linked List
3. Queue
4. None of the above

11) Which of the following condition is necessary for checking queue is full? Assume that the queue is circular.

1. Front == Rear+
2. Front == 0 && Rear == len-1
3. (Front == Rear+1) || (Front == 0 && Rear == len-1)
4. (Front == Rear+1) && (Front == 0 && Rear == len-1)

12) Which of the following scans the list by swapping the entries whenever pair of adjacent keys are out of the desired order?

1. Selection Sort
2. Insertion Sort
3. Merge Sort
4. Bubble Sort

13) In which linked list, No NULL link is there?

1. Null linked list
2. Doubly linked list
3. Circular linked list
4. None of the above

14) In stack, for accessing an nth element from the top, which command needs to use?

1. S [ Top-n ]
2. S[ Top+n ]
3. S[ Top-n+1 ]
4. None of the above

15) The result of prefix expression * / b + - d a c d, where a = 3, b = 6, c = 1, d = 5 is

1. 0
2. 5
3. 10
4. 8

16) Which of the following approach Recursive algorithms are worked on?

1. Bottom-up approach
2. Top-down approach
3. Hierarchical approach
4. All of the above

17) Which among the following data structures is best suited for storing very large numbers.

1. HashMap
2. Linked List
3. Tree
4. Stack

18) Suppose server and client are communicating with each other, and both are working at a different speed. Which of the following data structure is best suited for synchronization?

1. Graph
2. Tree
3. Queue
4. None of the above

19) How does breadth-first work?

1. Traverse each incident node along with its children
2. Traverse all node in random order
3. Is the same as backtracking
4. Traverse all neighbor nodes before moving to their child

20) Suppose we are working on heap data structure, so which of the following is used for storing the data of heap?

1. Tree
2. Array
3. Linked List
4. None of the above

21) Which of the following order is given by binary search tree if we traverse it in inorder?

1. Ascending order
2. Descending order
3. Random order
4. None of the above

22) Which of the following time complexity of bubble sort in best/worst case?

1. Best case: O(n), Worst case: O(n log(n))
2. Best case: O(n), Worst case: O(n^2)
3. Best case: O(n*log(n)), worst case: O(n*log(n))
4. None of the above

23) Which of the following is the aim of implementing prim's and kruskal's algorithms?

1. Maximum spanning tree
2. Spanning tree
3. Minimum Spanning tree
4. None of the above

24) Which of the following is the process of executing a correct program on data sets and measuring the time and space it takes to compute the results?

1. Testing
2. Combining
3. Profiling
4. All of the above

25) Which of the following is the time complexity if the graph is represented as an adjacency matrix in kruskal's algorithm?

1. O( E log V )
2. O( V log E)
3. O( V^2)
4. O( log E)

26) If there's no base criteria in a recursive program, the program will?

1. Gives Error
2. Execute until all conditions match
3. Execute infinitely
4. All of the above

27) If we want to convert infix notation to postfix notation, then which of the following data structure should we use?

1. Stack
2. Queue
3. Singly Linked List
4. HashMap

28) Which of the following is the sum of the degree of each vertex is equal to if there an undirected graph with n vertices and e edges?

1. 2*n
2. 2*e
3. (e^2+1) / 2
4. (2*n-1) / 2

29) What of the following is the time complexity to add a node at the end of the singly linked list, if the pointer is initially pointing to the head of the list?

1. O(1)
2. O(n)
3. ?(n)
4. ?(1)

30) If we compare array and linked - list then which of the following point is not true about linked list?

1. Linked - lists are dynamic in nature
2. Access of elements in linked list takes less time than compared to arrays
3. In linked list, random access is not allowed
4. It is easy to delete elements in Linked List

31) Which of the following operations are dependent on the length of the linked list if we have pointers to first and the last node of a singly linked list?

1. Delete the last element of the list
2. Insert a new element as a first element
3. Delete the first element
4. Add a new element at the end of the list

32) How can we define the memory-efficient doubly linked list?

1. Each node has only one pointer to traverse the list back and forth
2. The list has breakpoints for faster traversal
3. A singly linked list acts as a helper list to traverse through the doubly linked list
4. A doubly linked list that uses bitwise AND operator for storing addresses

33) Which of the following supports the statement, Array implementation of stack is not dynamic?

1. Space allocation for array is fixed and cannot be changed during run-time
2. Reduce time and space complexity
3. Compilation Error
4. Array implementation is flexible

34) Which of the following statement is true in linked list implementation of queue?

1. In push operation, if new nodes are inserted at the beginning, then in pop operation, nodes must be removed from the beginning
2. In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from the end
3. In a push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from beginning.
4. In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes must be removed from end

35) Which of the following operation is correct, while evaluating a postfix expression, when an operator is encountered?

1. Push it directly on to the stack
2. Pop 2 operands, evaluate them and push the result on to the stack
3. Pop the entire stack
4. Ignore the operator

36) Which of the following is the time complexity of converting a prefix notation to infix notation is?

1. O(n) where n is the length of the equation
2. O(n) where n is number of operands
3. O(1)
4. O(logn) where n is length of the equation

37) In a complete k-ary tree, every internal node has exactly k children or no child. The number of leaves in such a tree with n internal nodes is?

1. nk
2. (n-1)k + 1
3. n(k-1) + 1
4. n(k-1)

38) Which of the following statement is correct about deque?

1. A queue with insert and delete defined for both front and rear ends of the queue
2. Works on last in first order
3. A queue implemented with both singly and doubly linked lists
4. A queue with insert/delete defined for front side of the queue

39) What is the number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children?

1. n/2
2. (n-1)/3
3. (n-1)/2
4. (2n+1)/3

40) The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is?

1. 2h - 1
2. 2h - 1 - 1
3. 2h + 1 - 1
4. 2 * (h+1)

41) Which of the following is the graphical representation of an algorithm?

1. Pseudocode
2. Flow Chart
3. Graph Coloring
4. Dynamic Programming

42) Which of the following method will choose when sub-problems share sub-problems?

1. Backtracking
2. Greedy Method
3. Divide and Conquer
4. Dynamic Programming

43) The step by step procedure for a program is called?

1. Process
2. Greedy Method
3. Algorithm
4. Problem

44) Which of the following is the advantage of finding maximum and minimum using the divide and conquer method instead of conditional operators?

1. Reduce Space Complexity
2. For getting the consistent result
3. Reduce Time Complexity
4. All of the above

45) Which of the following data structure that contains a relationship between a pair of elements; this is not necessarily hierarchical in nature?

1. Tree
2. Graph
3. String
4. None of the above

46) Which of the following operations accesses each record exactly once?

1. Inserted
2. Deletion
3. Traversing
4. Searching

47) Which of the following is a set of data values and associated operations that are specified accurately, independent of any particular implementation?

1. Stack
2. Tree
3. Abstract Data Type
4. None of the above

48) Which of the following is something that has certain attributes or properties which may be assigned values?

1. Field
2. File
3. Record
4. Entity

49) Below C program that takes a number as an argument, and uses a stack S to do processing.

1. Prints binary representation of number in reverse order
2. Prints binary representation of number
3. Prints the value of number
4. Prints the value of number in reverse order

50) Below C program that takes a Queue as an argument, and uses a stack S to do processing.

1. Removes the last from Qu
2. Keeps the Qu same as it was before the call
3. Reverses the Qu
4. None of the above

51) If we want to implement a stack using queue then how many queues are needed? Consider the situation where no other data structure like arrays, linked list is there.

1. 1
2. 2
3. 3
4. 4

52) If an algorithm takes O(n) for some computing then which of the following is the meaning of it?

1. In this algorithm, the nested loop count is 'n'
2. The computation time taken by the algorithm is proportional to 'n'
3. If we compare it with the standard algorithm, then it is 'n' times faster than a standard algorithm
4. There are 'n' numbers of statements in the algorithm

53) It is possible if we want to read a data item at any location of a list within a constant time then how can we do it?

1. Yes, only if the list is implemented by stack
2. Yes, only if the list is implemented by an array
3. Yes, only if the list is implemented by (i.e. linked list)
4. No, we need O(n) computation steps on matter what kind of implementation is used

54) How many minimum number of spanning trees, one can have from a given connected graph with N nodes with different weights for the edges.

1. N-1
2. One
3. 1/ (N+1)
4. None of the above

55) Which are the following two phases of testing of program?

1. Best case and worst case
2. Space complexity and the time complexity
3. Validation and checking errors
4. Debugging and profiling

56) The applications of stack data structure is/are?

1. Backtracking
2. Memory management
3. Arithmetic expression evaluation
4. All of the above

57) In the arrays, the smallest element of its index also known as?

1. Lower bound
2. Upper bound
3. Range
4. All of the above

58) What happens when you push a new node in linked list representation of a stack?

1. The new node is placed at the front of linked list
2. The new node is placed at the back of the linked list
3. The new node is placed at the middle of the linked list
4. None of the above

59) Which of following is the advantage of using linked list?

1. For relatively permanent collections of data
2. Linked list is more flexible it can grow and shrink easily
3. Less time complexity
4. None of the above

60) Which of the following linear list is unidirectional or can be traversed in only one direction from starting to end?

1. Singly linked list
2. Array list
3. Null linked list
4. None of the above

61) Which of the following is another name of circular queue?

1. Curve buffer
2. Square Buffer
3. Ring buffer
4. None of the above

62) Which of following is contained by the header of the linked list?

1. The address of the first node
2. The address of the last node
3. Pointer to the last record of the actual data
4. Middle record of the actual data

63) Which of the following linear list in which the last node points to the first node?

1. Null linked list
2. Circular linked list
3. Doubly linked list
4. None of the above

64) In binary search algorithm, which of the following statement doesn't support the binary search properties?

1. Array must be sorted
2. Requirement of sorted array is expensive when a lot of insertion and deletions are needed
3. We can access middle element directly
4. If data items are more than 2000 then it will not be efficient.

65) Which of the following can be characterized of sorting algorithm?

1. Simple algorithm which require the order of n2 comparisons to sort n items.
2. Sophisticated algorithms that require the O(nlog2n) comparisons to sort items.
3. Both of the above
4. None of the above

66) In binary search algorithm, which of the following is not required condition?

1. The data items must be sorted
2. We can access to the middle element in any sub list
3. There should be a function to delete and/or insert elements in the list.
4. Number values should only be present in the list