Data Structures MCQs
1. Rate yourself 0-5 in Data structures and algorithms.
2. Given a set of banned words, which one of the following data structures would you use to create a chat moderation system that flags these words?
3. Which one of the following is the overflow condition if a linear queue is implemented using an array with the size MAX_SIZE?
4. Which of the following properties is associated with a queue?
5. What is the term for inserting into a full queue known as?
6. Following is C like pseudo code of a function that takes a Queue as an argument, and uses a stack S to do processing. void fun(Queue *Q) { Stack S; // Say it creates an empty stack S // Run while Q is not empty while (!isEmpty(Q)) { // deQueue an item from Q and push the dequeued item to S push(&S, deQueue(Q)); } // Run while Stack S is not empty while (!isEmpty(&S)) { // Pop an item from S and enqueue the poppped item to Q enQueue(Q, pop(&S)); } } What does the above function do in general?
7. A circular queue has been implemented using a singly linked list where each node consists of a value and a single pointer pointing to the next node. We maintain exactly two external pointers FRONT and REAR pointing to the front node and the near node of the queue, respectively. Which of the following statements is/are CORRECT for such a circular queue, so that insertion and deletion operations can be performed in O(1) time? I. Next pointer of front node points to the rear node. II. Next pointer of rear node points to the front node.
8. A priority queue can efficiently be implemented using which of the following data structures? Assume that the number of inserts and peek (operation to see the current highest priority item) and extraction (remove the highest priority item) operations are almost the same.
9. What is the time complexity to initialize in a priority queue with the vector? Check out the code- priority_queue<int> pq(vec.begin(),vec.end());
10. One difference between a queue and a stack is:
11. Suppose top is called on a priority queue that has exactly two entries with equal priority. How is the return value of top selected?
12. An implementation of a queue Q, using two stacks S1 and S2, is given below: void insert(Q, x) { push (S1, x); } void delete(Q){ if(stack-empty(S2)) then if(stack-empty(S1)) then { print(“Q is empty”); return; } else while (!(stack-empty(S1))){ x=pop(S1); push(S2,x); } x=pop(S2); } Let n insert and m (<=n) delete operations be performed in an arbitrary order on an empty queue Q. Let x and y be the number of push and pop operations performed respectively in the process. Which one of the following is true for all m and n?
13. What does the below function do? (Assume that IntQueue is an integer queue.) void fun(int n) { IntQueue q = new IntQueue(); q.enqueue(0); q.enqueue(1); for (int i = 0; i < n; i++) { int a = q.dequeue(); int b = q.dequeue(); q.enqueue(b); q.enqueue(a + b); print(a); } }
14. If we insert 1, 2, 3, 4 in a queue in the given order (first 1 then 2 then 3 then 4), then what is the order of printing of values from the queue?
15. How many stacks are needed to implement a queue. Consider the situation where no other data structure like arrays, linked list is available to you.
16. A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer. Let n denote the number of nodes in the queue. Let 'enqueue' be implemented by inserting a new node at the head, and 'dequeue' be implemented by deletion of a node from the tail. Which one of the following is the time complexity of the most time-efficient implementation of 'enqueue' and 'dequeue, respectively, for this data structure?
17. Which of the following is true about linked list implementation of queue?
18. Suppose a circular queue of capacity (n – 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operation are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full and queue empty are
19. Which of the following conditions represents an empty condition in the circular queue?
20. Five people P, Q, R, S and T are standing in a queue. R is standing between P and T. P is just behind Q and Q is second in the queue. Who is second last in the queue?
21. Which of the following is not an advantage of a priority queue?
22. What does the function queue::swap() do?
23. A one-dimensional array containing one-dimensional arrays is called
24. How many distinct binary search trees can be created out of 4 distinct keys?
25. Given an undirected graph G with V vertices and E edges, the sum of the degrees of all vertices will be?
26. Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three?
27. What is the number of edges in an MST of a graph with N vertices and E edges?
28. What is the total number of spanning trees possible for a complete graph with N vertices?
29. In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity by?
30. How many undirected graphs (not necessarily connected) can be constructed out of a given set V = {v1, v2, ...., vn} of n vertices?
31. What is the maximum number of edges in an acyclic undirected graph with n vertices?
32. Which one of the following is an application of Queue Data Structure?
33. What is the space complexity of a linear queue having n elements?
34. Consider the implementation of the queue using a circular array. What goes wrong if we try to keep all the items at the front of a partially-filled array (so that data[0] is always the front).
35. What does the function queue::back() do?
36. What is the minimum number of stacks required to implement the queue?
37. What is the ideal initial value of front and rear in an array implementation of the queue?
38. What is the term for deleting into a empty queue known as?
39. A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT (n refers to the number of items in the queue)?
40. How many queues are needed to implement a stack. Consider the situation where no other data structure like arrays, linked list is available to you.
41. In linked list implementation of a queue, the important condition for a queue to be empty is?
42. The minimum number of stacks needed to implement a queue is
43. Consider a standard Circular Queue 'q' implementation (which has the same condition for Queue Full and Queue Empty) whose size is 11 and the elements of the queue are q[0], q[1], q[2].....,q[10]. The front and rear pointers are initialized to point at q[2] . In which position will the ninth element be added?
44. A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below: 10, 8, 5, 3, 2 Two new elements ”1‘ and ”7‘ are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the elements is:
45. To implement the queue with a linked list, keeping track of a front pointer and a rear pointer. Which of these pointers will change during an insertion into an EMPTY queue?
46. Consider the following statements: i. First-in-first out types of computations are efficiently supported by STACKS. ii. Implementing LISTS on linked lists is more efficient than implementing LISTS on an array for almost all the basic LIST operations. iii. Implementing QUEUES on a circular array is more efficient than implementing QUEUES on a linear array with two indices. iv. Last-in-first-out type of computations are efficiently supported by QUEUES. Which of the following is correct?
47. Which one of the following arrays represents a binary max-heap?
48. You are given a graph containing n vertices and m edges and given that the graph doesn’t contain a cycle of odd length. Time Complexity of the best known algorithm to find out whether the graph is bipartite or not is?
49. Given the following set of edges E for a directed graph, choose the correct statements: E = { {1, 2}, {2, 1}, {3, 1} }
50. In the development of "Plague Tale," the task of declaring variables for each rat individually could be overwhelming due to the sheer number of rats. How does the use of data structures alleviate this burden?
51. Which applications according to you use data structures?
52. Which of the following is NOT a property of arrays?
53. Which of the following operations are O(1) for arrays?
54. What would happen if you remove the this “window->clear(sf::Color::Blue);” line from the below code? - Explain the importance of clearing window #include <SFML/Graphics.hpp> int main() { // Define the video mode (dimensions) sf::VideoMode videoMode = *(new sf::VideoMode(800, 600)); // Create a window object with specific dimensions and a title sf::RenderWindow* window = new sf::RenderWindow(videoMode, "SFML Window"); // Game loop to keep the window open while (window->isOpen()) { sf::Event event; while (window->pollEvent(event)) { // Check for window closure if (event.type == sf::Event::Closed) window->close(); } // Clear the window window->clear(sf::Color::Blue); sf::Texture outscal_texture; outscal_texture.loadFromFile("assets/textures/outscal_logo.png"); sf::Sprite outscal_sprite; outscal_sprite.setTexture(outscal_texture); outscal_sprite.setPosition(200, 100); // Position outscal_sprite.setRotation(45); // Rotation in degrees outscal_sprite.setScale(0.5, 0.5); // Scale factor window->draw(outscal_sprite); // Display what was drawn window->display(); } return 0; }
55. What would be the size of an object of this class, considering only primary data structures like int and float? class Player { int health; int player_score; int movement_speed; float position_x; float position_y; }; Assume the size of int is 4 bytes and the size of float is 4 bytes
56. What is the purpose of using the const keyword in variables like game_window_title, game_window_width, game_window_height, and window_color in the GraphicService class?
57. Why does MainMenuUIController fetch the game_window from the GraphicService during initialization?
58. Given the following code snippet, what is the purpose of the setScale method as applied to a Sprite in SFML? #include <SFML/Graphics.hpp> int main() { sf::Texture texture; texture.loadFromFile("assets/textures/hero.png"); sf::Sprite sprite; sprite.setTexture(texture); sprite.setScale(2.0f, 2.0f); // Rest of the game loop return 0; }
59. What effect does the setRotation method have on a sprite, as demonstrated in the following code? #include <SFML/Graphics.hpp> int main() { sf::Texture texture; texture.loadFromFile("assets/textures/hero.png"); sf::Sprite sprite; sprite.setTexture(texture); sprite.setRotation(45.0f); // Rotate by 45 degrees // Rest of the game loop return 0; }
60. How does changing the position of a sprite affect its appearance on the screen, as shown in the following SFML code snippet? #include <SFML/Graphics.hpp> int main() { sf::Texture texture; texture.loadFromFile("assets/textures/hero.png"); sf::Sprite sprite; sprite.setTexture(texture); sprite.setPosition(100.0f, 150.0f); // Assume a window and game loop exists here }
61. What is the role of a sf::Sprite object in graphical applications?
A. 0
B. 1
C. 2
D. 5
E. 4
A. Array
B. Dictionary
C. Trees
D. List
A. rear=MAX_SIZE -1
B. rear = MAX_SIZE
C. rear = front+1
D. rear = front
A. First In Last Out
B. First In First Out
C. Last In First Out
D. Last In Last Out
A. overflow
B. underflow
C. null pointer exception
D. program won’t be compiled
A. Removes the last from Q
B. Keeps the Q same as it was before the call
C. Makes Q empty
D. Reverses the Q
A. I only
B. II only
C. Both I and II
D. Neither I and II
A. Array
B. Linked List
C. Heap Data Structures like Binary Heap, Fibonacci Heap
D. None of the above
A. O(nlogn)
B. O(logn)
C. O(n)
D. O(n2)
A. Queues require dynamic memory, but stacks do not.
B. Stacks require dynamic memory, but queues do not.
C. Queues use two ends of the structure; stacks use only one.
D. Stacks use two ends of the structure, queues use only one.
A. The implementation gets to choose either one.
B. the one which was inserted first.
C. The one which was inserted most recently.
D. This can never happen (violates the precondition)
A. n+m <= x < 2n and 2m <= y <= n+m
B. n+m <= x < 2n and 2m<= y <= 2n
C. 2m <= x < 2n and 2m <= y <= n+m
D. 2m <= x <2n and 2m <= y <= 2n
A. Prints numbers from 0 to n-1
B. Prints numbers from n-1 to 0
C. Prints first n Fibonacci numbers
D. Prints first n Fibonacci numbers in reverse order.
A. 2 1 3 4
B. 1 2 3 4
C. 4 3 2 1
D. 1 1 1 1
A. 3
B. 1
C. 2
D. 4
A. Θ(1), Θ(1)
B. Θ(1), Θ(n)
C. Θ(n), Θ(1)
D. Θ(n), Θ(n)
A. In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes must be removed from end.
B. In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from the beginning.
C. Both of the above
D. None of the above
A. Full: (REAR+1) mod n == FRONT, empty: REAR == FRONT
B. Full: (REAR+1) mod n == FRONT, empty: (FRONT+1) mod n == REAR
C. Full: REAR == FRONT, empty: (REAR+1) mod n == FRONT
D. Full: (FRONT+1) mod n == REAR, empty: REAR == FRONT
A. (Rear + 1)mod n = front
B. (front + 1)mod n = rear
C. front == rear
D. Rear = n - 1
A. T
B. S
C. R
D. P
A. Easy to implement
B. Processes with different priority can be efficiently handled
C. Applications with differing requirements
D. Easy to delete elements in any case
A. Insert a new element into the queue container, the new element is added to the end of the queue.
B. Deletes the first element of the queue.
C. Exchange the contents of two queues but the queues must be of the same type, although sizes may differ.
D. None
A. Two-dimensional array
B. Multi-casting array
C. Multi-dimensional array
D. Three-dimensional array
A. 14
B. 24
C. 5
D. 42
A. E
B. 2E
C. V + E
D. 2V
A. 1 / 8
B. 1
C. 7
D. 8
A. E - 1
B. N - 1
C. N + E - 1
D. N + E - 2
A. N^(N-1)
B. (N-2) ^ N
C. N^(N-2)
D. (N - 1) ^ N
A. Performing a BFS starting from S.
B. Performing a DFS starting from S.
C. Warshall’s algorithm
D. Dijkstra’s algorithm starting from S.
A. n(n-1) / 2
B. 2^n
C. n!
D. 2^( (n*(n-1)) / 2 )
A. n
B. n - 1
C. n + 1
D. 2n - 1
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
C. Load Balancing
D. All of the above
A. O(n)
B. O(nlogn)
C. O(logn)
D. O(1)
A. The constructor would require linear time.
B. The get_front function would require linear time.
C. The insert function would require linear time.
D. The is_empty function would require linear time.
A. Returns a reference to the last element of the queue.
B. Returns a reference to the first element of the queue.
C. Returns the size of the queue.
D. Returns whether the queue is empty.
A. 3
B. 4
C. 2
D. 1
A. 1 & 0
B. 0 & 1
C. -1 & -1
D. -1 & 0
A. overflow
B. underflow
C. null pointer exception
D. program won’t be compiled
A. Both operations can be performed in O(1) time
B. At most one operation can be performed in O(1) time but the worst case time for the other operation will be Ω(n)
C. The worst case time complexity for both operations will be Ω(n)
D. Worst case time complexity for both operations will be Ω(log n)
A. 1
B. 2
C. 3
D. 4
A. FRONT is null
B. REAR is null
C. LINK is empty
D. None
A. 3
B. 2
C. 1
D. 4
A. q[0]
B. q[1]
C. q[9]
D. q[10]
A. 10, 8, 7, 5, 3, 2, 1
B. 10, 8, 7, 2, 3, 1, 5
C. 10, 8, 7, 1, 2, 3, 5
D. 10, 8, 7, 3, 2, 1, 5
A. Neither changes
B. Only front_ptr changes
C. Both change
D. Only rear_ptr changes
A. (iii) is true
B. (i) and (ii) are true
C. (iii) and (iv) are true
D. (ii) and (iv) are true
A. [26, 13, 17, 14, 11, 9, 15]
B. [26, 15, 17, 14, 11, 9, 13]
C. [26, 15, 14, 17, 11, 9, 13]
D. [26, 15, 13, 14, 11, 9, 17]
A. O(1)
B. O(m + n)
C. O(mn)
D. O(n^2)
A. Graph contains 2 cycles
B. Graph doesn't contain any cycle
C. Graph have 2 connected components
D. Graph contains 1 cycle
A. By automating the process of rat creation through artificial intelligence algorithms.
B. By organizing the rats into a structured format, reducing the need for repetitive coding tasks.
C. By outsourcing rat management to a specialized team of rat handlers.
D. By implementing a time-traveling mechanism to prevent the rats from ever existing in the first place.
A. Sorting comments on Instagram Reels based on popularity
B. Showing the world rank 1 player on top of the leaderboard in Subway Surfers
C. Your browser’s History feature that stores the URLs of all the web pages visited
D. Displaying current weather and temperature on your smartphone
A. Continuous Memory Allocation
B. Dynamic Size
C. Non-Linear
D. Direct Accessing
A. Searching any element
B. Accessing any element
C. Inserting an element
D. deleting an element
A. Without clearing the window, previous frames' drawings will not be erased, causing objects to leave trails or overlap visually as they move or change.
B. Removing window->clear() will make the program run faster because it skips unnecessary operations.
C. Not clearing the window will change the window's default background color to black.
D. If the window is not cleared, the program will not be able to draw new sprites in each frame.
A. 16 bytes
B. 20 bytes
C. 12 bytes
D. 24 bytes
A. To indicate that these variables are static and cannot be changed at runtime
B. To prevent accidental modification of these values in the code
C. To ensure these variables are accessible globally within the program
D. To enforce constant time complexity for operations involving these variables
A. To double the pixel density of the texture for higher screen resolutions.
B. To rotate the sprite by 2 radians around the center of the texture.
C. To double the size of the sprite, making it twice as wide and twice as tall.
D. To move the sprite to a position that is twice its current coordinates.
A. It rotates the entire window contents by 45 degrees around the center of the window, affecting how all objects are rendered.
B. It rotates the sprite by 45 degrees around the center of the window, making the sprite orientation dependent on the window's dimensions.
C. It rotates the sprite by 45 degrees in 3D space, tilting it away from the screen around its center.
D. It rotates the sprite by 45 degrees around its origin point, which by default is the top-left corner (0, 0) relative to the sprite.
A. Moves the sprite to be centered at (100, 150) on the screen.
B. Resizes the sprite to have a width of 100 and a height of 150.
C. Rotates the sprite to an angle made by the vector (100, 150).
D. Sets the top-left corner of the sprite to be at (100, 150) in window coordinates.
A. It manages the game loop and event processing.
B. It acts as a lightweight wrapper to position, rotate, and scale 2D images.
C. It is used for creating and managing windows and views.
D. It handles audio and sound effects playback.
Introduction of the Data Structures
Data structures are crucial entities in programming that help organize and store data efficiently in a computer. They provide an efficient processing of data in terms of both time and space. Data structures also provide a low-level manipulation of data allowing insert and delete operations. The right choice of data structures depends on various factors such as the nature of the data, the operations to be performed, and the level of efficiency required in an application.
Data structures can be categorized into various types which are as follows:
- Arrays
- Linked Lists
- Stacks
- Queues
- Trees
- Graphs
- Hash Tables
What are algorithms
Algorithms are known as well-defined steps, logic, procedures, or instructions designed in such a way that they will perform specific tasks or solve partproblems. They are not independent programs that can work itself.
Some Characteristics of the algorithms are as follows:
- Definiteness
- Finiteness
- Input
- Output
- Effectiveness
Examples of Algorithmic Problems
- Searching
- Sorting
- Pathfinding
- Optimization
Conclusion
Being a master in Data Structures and Algorithms (DSA) is crucial for anyone who is pursuing a career in software or game development. This collection of DSA MCQ questions helps to enhance your basic understanding and application of DSA concepts. By answering these DSA MCQs, you will be able to identify your strengths and weaknesses in DSA.
Game Development Courses
Full-Stack Game Development
Game Development Advance
Game Development Fast Track
Other MCQs
Try out our Online Compilers
