UNIT I: Arrays and Sequential Representations

MCQs

1. What is the time complexity to access an c) Last-in, first-out

element in an array? d) Supports enqueue and dequeue
a) O(n) b) O(1) c) O(log n) (Correct answer: c)
d) O(n log n) (Correct answer: b) 12. How do you calculate the middle
2. Which data structure is suitable for index in a binary search?
reversing a string? a) (low+high)/2(low+high)/2
a) Queue b) Stack c) Linked List b) (low+high+1)/2(low+high+1)/2
d) Binary Tree (Correct answer: b) c) (low+high)>>1(low+high)>>1
3. In a circular queue, how is the rear d) (low+high−1)/2(low+high−1)/2
updated? (Correct answer: a)
a) (rear + 1) % size 13. What is the condition for overflow in
b) (rear - 1) % size a circular queue?
c) (rear * 2) % size a) rear == front
d) rear + 1 (Correct answer: a) b) (rear + 1) % size == front
4. What is the primary difference between an c) (front + 1) % size == rear
array and a linked list? d) rear == size (Correct answer: b)
a) Array elements are stored in contiguous 14. What is the main advantage of a
memory locations; linked list nodes are not. circular queue over a regular queue?
b) Linked lists have a fixed size, arrays do a) Faster access time
not. b) It prevents memory wastage
c) Arrays allow dynamic memory allocation, c) It uses a stack internally
linked lists do not. d) It allows dynamic memory allocation
d) Arrays are slower in traversal than linked (Correct answer: b)
lists. 15. In a linked list, the pointer field of
(Correct answer: a) the last node contains:
5. Which of the following is a valid postfix a) NULL
expression? b) Address of the first node
a) AB+CD+* b) ABC+*D c) Address of the last node
c) +AB*CD d) AB+C* (Correct d) A random value (Correct answer: a)
answer: a) 16. Which of the following is NOT true
6. The condition for an empty queue in a about singly linked lists?
circular queue implementation is: a) They require more memory than arrays
a) front == rear b) They support dynamic memory allocation
b) (rear + 1) % size == front c) Deletion at the head is efficient
c) (front + 1) % size == rear d) Random access is possible (Correct
d) rear == size (Correct answer: a) answer: d)
7. Which operation is used to add an element 17. Which data structure is best suited
to a stack? for undo functionality?
a) Push b) Pop c) a) Stack b) Queue c) Linked List
Enqueue d) Array (Correct answer: a)
d) Dequeue (Correct answer: a) 18. The postfix expression for
8. What is the time complexity of searching for A+(B×C)−DA+(B×C)−D is:
an element in an unsorted array? a) ABC×+D−ABC×+D−
a) O(1) b) O(n) c) O(log n) b) ABC×D−+ABC×D−+
d) O(n log n) c) A+BC×−DA+BC×−D
(Correct answer: b) d) A+B×C−DA+B×C−D (Correct
9. What is the time complexity of answer: a)
inserting an element at the end of an array? 19. In polynomial addition using linked
a) O(1) b) O(n) c) O(log n) lists, which part of the node stores the
d) O(n log n) (Correct answer: a) degree of the term?
10. In a stack, which of the following a) Coefficient field b) Exponent field
operations results in removing the top c) Link field d) Head pointer
element? (Correct answer: b)
a) Push b) Pop c) Peek
d) Enqueue (Correct answer: b) 20. How many stacks are required to
11. Which of the following is NOT a evaluate a postfix expression?
characteristic of a queue? a) 1 b) 2 c) 3 d) 4
a) FIFO structure b) Linear data (Correct answer: a)
structure
21. Which of the following is true for a stack 28. Which operation is least efficient in an
implemented using an array? array-based queue implementation?
a) Memory is dynamically allocated a) Enqueue
b) Overflow cannot occur b) Dequeue
c) Top pointer always points to the topmost c) Peek
element d) Checking if the queue is empty
d) It is implemented using doubly linked (Correct answer: b)
lists 29. Which of the following is TRUE for a
(Correct answer: c) circular linked list?
22. In a doubly linked list, the deletion of a a) The last node points to the head of the
node at position pp takes: list.
a) O(1) b) O(p) c) b) Every node contains an additional
O(log p) circular pointer.
d) O(p^2) (Correct answer: b) c) It cannot contain duplicate values.
23. The maximum number of elements a d) It has no NULL pointers.
queue can hold, if implemented using an (Correct answer: a)
array of size nn, is:
a) n−1n−1 b) nn c) n+1n+1
d) Unlimited (Correct answer: b)
24. Which of the following is NOT a type of 30. What is the best-case time complexity for
linked list? searching an element in a singly linked
a) Singly linked list b) Doubly list?
linked list a) O(1)
c) Circular linked list d) Queue-linked b) O(n)
list c) O(log n)
(Correct answer: d) d) O(n log n)
25. The primary purpose of a "dummy head" (Correct answer: a)
in a linked list is to: 31. Which type of memory allocation is used in
a) Mark the end of the list linked lists?
b) Store the length of the list a) Static memory allocation
c) Simplify insertion and deletion b) Contiguous memory allocation
operations c) Dynamic memory allocation
d) Indicate the start of the list d) Sequential memory allocation
(Correct answer: c) (Correct answer: c)
26. What does the stack pointer contain in an 32. What is the postfix equivalent of the
array-based stack implementation? expression (A+B)×C−D(A+B)×C−D?
a) The address of the last element a) AB+C×D−AB+C×D−
pushed onto the stack b) AB+CD×−AB+CD×−
b) The total size of the stack c) AB+CD−×AB+CD−×
c) The maximum capacity of the stack d) A+BC×D−A+BC×D−
d) The number of elements in the stack (Correct answer: a)
(Correct answer: a) 33. When traversing a linked list, what
27. If a stack has a capacity of nn elements condition indicates the end of the list?
and currently contains kk elements, how a) The link pointer is NULL.
many additional elements can be pushed? b) The data field is NULL.
a) n−kn−k b) k−nk−n c) c) The current node is the head.
n+kn+k d) The current node is the tail.
d) k×nk×n (Correct answer: a) (Correct answer: a)

Two-Marks Questions

1. Define Data Structure

2. Define Array
3. Define Stack
4. Define Queue
5. Define Linked List
6. Differentiate between linear and circular queues.
7. What is the advantage of using a linked list over an array?
8. Write the expression for finding the middle element of a stack.
9. List the applications of multiple stacks.
10. Define an ordered list. Provide an example.
11. How do you differentiate between a stack and a queue?
12. What is the significance of the top pointer in a stack?
13. Write a simple algorithm to traverse an array.
14. Describe the applications of circular queues.
15. What is the use of a linked stack over an array-based stack?
16. Explain how to check for overflow in a stack.
17. What are the steps to perform polynomial addition using a linked list?
18. How does a multiple stack implementation work?
19. Differentiate between a singly and doubly linked list.
20. Define Polynomial

Five-Marks Questions

1. Explain about Sequential Representation

2. Explain the process of evaluating postfix expressions with an example.
3. Describe the structure and applications of a singly linked list.
4. Write the algorithm to implement a queue using arrays.
5. Write the algorithm to implement a stack.
6. Write the algorithm to implement linked list.
7. Explain how polynomial addition can be performed using linked lists.
8. Discuss the advantages of using multiple stacks.
9. Write a note on expression
10. Differentiate between linked stack and Queue
11. Write the algorithm to implement polynomial addition.
12. Write the algorithm to evaluate a postfix expression using stacks.
13. Write the algorithm to evaluate a prefix expression using stacks
14. Write the algorithm to evaluate a infix expression using stacks
15. Explain the procedure to add a node at the beginning of a singly linked list.
16. Discuss the implementation of a queue using arrays, including enqueue and dequeue
operations.
17. Describe the concept of a circular queue and its advantages over a linear queue.
18. Write an algorithm to convert an infix expression to a postfix expression.
19. Illustrate polynomial addition with an example.
20. Explain the advantages and disadvantages of array-based stacks.
21. Discuss the importance of sequential representation of data structures.
22. How is a linked queue implemented? Discuss with an algorithm.
23. Describe the process of merging two linked lists.

Ten-Marks Questions

1. Write a program to implement stack operations (push, pop, and display) using arrays.
2. Explain in detail the differences between stacks and queues.
3. Write an algorithm to evaluate a postfix expression. Explain with an example.
4. Discuss the implementation and applications of a circular queue.
5. Explain polynomial addition using an example.
6. Write a C program to implement stack operations (push, pop, and display) using arrays.
7. Explain the implementation of a queue using linked lists, along with algorithms for
enqueue and dequeue.
8. Discuss in detail how polynomial addition is performed using a singly linked list, with a
step-by-step example.
9. Explain how multiple stacks can be implemented in a single array. Provide an algorithm
for the same.
10. Write a program to implement infix to postfix conversion and evaluate the postfix
expression using stacks.
 UNIT II: Trees and Graphs

1. Which traversal method visits nodes in the a) Node iii is connected to node jjj
order: left, root, right? b) Node iii has a self-loop
a) Pre-order b) In-order c) Node iii and node jjj are not connected
c) Post-order d) Level-order d) None of the above (Correct answer:
(Correct answer: b) a)
2. What is the maximum number of nodes in a 14. The depth of a node in a tree is:
binary tree of height hhh? a) The number of edges from the root to the
a) 2h−12^h - 12h−1 b) 2h2^h2h node
c) h2h^2h2 d) h+1h + 1h+1 b) The number of edges from the node to the
(Correct answer: a) leaf
3. Which algorithm is used to find the shortest c) The height of the subtree rooted at the node
path in a graph? d) None of the above
a) Dijkstra’s b) Prim’s (Correct answer: a)
c) Kruskal’s d) Floyd-Warshall 15. What is the time complexity of DFS on a graph
(Correct answer: a) with VVV vertices and EEE edges?
4. What is the height of a tree with only one a) O(V + E) b) O(V * E) c) O(V^2)
node? d) O(E^2) (Correct answer: a)
a) 0 b) 1 c) -1 d) Undefined 16. Which traversal method is best for finding the
(Correct answer: b) shortest path in an unweighted graph?
5. In a binary tree, which traversal method uses a a) BFS b) DFS c) In-order
stack internally? traversal
a) In-order traversal d) Pre-order traversal (Correct answer:
b) Pre-order traversal a)
c) Post-order traversal 17. What is a spanning tree?
d) Level-order traversal a) A graph with all nodes connected
(Correct answer: b) b) A subgraph containing all nodes with no
6. Which of the following algorithms is used for cycles
finding the minimum spanning tree? c) A graph with cycles
a) Prim’s Algorithm b) Kruskal’s Algorithm d) A tree with weights (Correct answer:
c) Both a and b d) Dijkstra’s Algorithm b)
(Correct answer: c) 18. Dijkstra's algorithm does NOT work on graphs
7. A complete binary tree of depth ddd has how with:
many nodes? a) Weighted edges b) Negative edges
a) 2d−12^d - 12d−1 b) 2d2^d2d c) Cyclic edges d) Directed edges
c) 2d+1−12^{d+1} - 12d+1−1 (Correct answer: b)
d) d2−1d^2 - 1d2−1 (Correct answer: 19. A threaded binary tree allows traversal without
c) using:
8. Which data structure is used in breadth-first a) A queue b) A stack
traversal of a graph? c) Both a and b d) None of the above
a) Stack b) Queue c) Linked List (Correct answer: b)
d) Array (Correct answer: b) 20. In a tree, which traversal ensures visiting all
9. What is the height of an empty tree? nodes at the same depth before moving
a) -1 b) 0 c) 1 d) Undefined deeper?
(Correct answer: a) a) Pre-order b) In-order
10. In a binary tree, the number of leaf nodes is c) BFS d) DFS (Correct answer: c)
always: 21. Which algorithm is used for finding all-pairs
a) n/2n/2n/2 b) n−1n - 1n−1 shortest paths?
c) n+1n + 1n+1d) Greater than n/2n/2n/2 a) Prim’s algorithm b) Dijkstra’s algorithm
(Correct answer: d) c) Floyd-Warshall algorithm
11. What is a graph with no cycles called? d) Kruskal’s algorithm (Correct answer: c)
a) Connected graph b) Weighted graph 22. Which traversal method visits nodes in the
c) Acyclic graph d) Null graph order: root, left subtree, right subtree?
(Correct answer: c) a) Pre-order b) In-order c) Post-order
12. Which traversal technique is used for d) Level-order (Correct answer: a)
topological sorting? 23. What does a self-loop in a graph indicate?
a) BFS b) DFS c) In-order traversal a) The vertex is isolated.
d) Post-order traversal (Correct answer: b) b) The vertex is connected to itself.
13. In an adjacency matrix representation of a c) The graph is acyclic.
graph, what does a value of 1 at position (i,j) d) The graph has a spanning tree.
(i, j)(i,j) indicate? (Correct answer: b)
24. How many minimum spanning trees can a b) The number of edges originating from the
graph have? node
a) Always 1 b) At most 1 c) At least 1 c) The total degree of the node
d) Cannot be determined (Correct answer: d) The number of connected components
c) (Correct answer: a)
25. The binary representation of a graph using 30. Which algorithm is used to calculate transitive
adjacency lists requires: closure?
a) O(V) space b) O(V^2) space a) Floyd-Warshall algorithm
c) O(E + V) space d) O(V * E) space b) Dijkstra’s algorithm
(Correct answer: c) c) Kruskal’s algorithm
26. In Kruskal’s algorithm, the edges are sorted d) Bellman-Ford algorithm (Correct answer:
based on: a)
a) Number of vertices b) Weights of 31. A graph is considered strongly connected if:
edges a) There is a path between every pair of
c) Degree of nodes d) Topological order vertices.
(Correct answer: b) b) Every node has the same degree.
27. Which traversal algorithm is used to determine c) It has no cycles.
connected components of a graph? d) It contains at least one spanning tree.
a) BFS or DFS b) Topological sorting (Correct answer: a)
c) Spanning tree d) Shortest path 32. The shortest path from a source node to all
algorithms other nodes can be computed using:
(Correct answer: a) a) Dijkstra’s algorithm
28. What does the critical path in an activity b) Floyd-Warshall algorithm
network represent? c) Prim’s algorithm
a) The shortest time to complete the project d) Kruskal’s algorithm (Correct answer: a)
b) The longest path of activities in the network 33. A graph where every vertex is directly
c) The total cost of the project connected to every other vertex is called:
d) The maximum number of nodes in the graph a) Complete graph b) Directed graph
(Correct answer: b) c) Weighted graph d) Acyclic graph
29. In a directed graph, the in-degree of a node is: (Correct answer: a)
a) The number of edges pointing to the node

Two-Marks Questions

1. Define a binary tree.

2. What is a spanning tree?
3. What is sub tree ?
4. Define height of a tree
5. Define level of a tree
6. What is leaf node ?
7. What is the purpose of a topological sort?
8. Write a short note on threaded binary trees.
9. What is the purpose of a threaded binary tree?
10. Explain the difference between BFS and DFS.
11. Define a connected component in a graph.
12. What is an adjacency list?
13. Define graph
14. What is directed graph?
15. What is undirected graph?
16. Write a short note on topological sorting.
17. What is the significance of a critical path in activity networks?
18. Differentiate between a rooted tree and a binary tree.
19. Define the transitive closure of a graph.
20. What are the applications of spanning trees?

Five-Marks Questions

1. Explain the process of pre-order traversal of a binary tree.

2. Discuss the adjacency matrix and adjacency list representations of graphs.
3. Write the algorithm for DFS traversal of a graph.
4. What are critical paths, and how are they determined?
5. Discuss the transitive closure of a graph.
6. Write and explain the algorithm for pre-order traversal of a binary tree.
7. Discuss the adjacency matrix representation of a graph with an example.
8. Explain the process of creating a spanning tree using Prim’s algorithm.
9. Write the algorithm for depth-first search (DFS) of a graph.
10. Discuss the advantages and disadvantages of threaded binary trees.
11. Explain Dijkstra’s algorithm with an example.
12. Write a program for topological sorting of a graph.
13. What is a critical path? Explain its significance in project management.
14. Discuss the differences between BFS and DFS with use cases.
15. Describe the process of finding the shortest path in a graph using Floyd-Warshall
algorithm.

Ten-Marks Questions

1. Write a program to implement BFS and DFS traversals of a graph.

2. Explain the threaded binary tree with its advantages.
3. Discuss topological sorting in detail with its applications.
4. Explain in detail how activity networks are constructed and used.
5. Explain the concept of a spanning tree and its applications with examples.
6. Describe the binary tree traversal methods (pre-order, in-order, and post-order) with
algorithms and examples.
7. Discuss topological sorting and its importance in activity networks. Provide a detailed
example.