[go: up one dir, main page]
Scribd
Upload
29 views6 pages

Revision DSA

The document contains revision questions related to trees, graphs, sorting, searching, linked lists and other data structures. There are 30 multiple choice questions testing knowledge of tree traversals, graph representations, sorting algorithms, linked list operations and asymptotic analysis of algorithms.

Uploaded by

desugai123
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
29 views6 pages

Revision DSA

The document contains revision questions related to trees, graphs, sorting, searching, linked lists and other data structures. There are 30 multiple choice questions testing knowledge of tree traversals, graph representations, sorting algorithms, linked list operations and asymptotic analysis of algorithms.

Uploaded by

desugai123
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 6

Revision Questions

1. Given the tree below,

- Write the order in which the nodes are visited.


1- in-order traversal; 2- pre-order traversal; 3- post-order traversal
2. The tree in question 1 is:
a. B-Tree
b. Binary Tree
c. Binary Search Tree
d. Ternary Tree
e. AVL Tree

3. What is the depth of the tree in question 1?


a. 2
b. 3
c. 4
d. 8
e. None of the above
4. How many children does the root of the tree in question 1 have?
a. 2
b. 6
c. 10
d. 11
e. None of the above
5. Given the following tree,

- Write the order in which the nodes are visited.


1- in-order traversal; 2- pre-order traversal; 3- post-order traversal

- What is the depth of the tree?


6. What type is the tree below?

a. B-Tree
b. Binary Tree
c. Binary Search Tree
d. Ternary Tree
e. AVL Tree
f. None of the above

7. Given an array arr = {10, 20, 35, 47, 53, 66, 78, 82} and key = 53; What are the mid
values in the array that are generated in the first and second iterations if we are using
binary search?
a. 35 and 53
b. 47 and 53
c. 47 and 66
d. 53 and 66
8. How many swappings are required to sort the following array in descending order?
int arr [6] = {8, 22, 7, 0, 5, 13};
1- Bubble Sort; 2- Insertion Sort; 3- Selection Sort
9. How many swappings are required to sort the following array in ascending order?
int arr [6] = {8, 22, 7, 0, 5, 13};
1- Bubble Sort; 2- Insertion Sort; 3- Selection Sort
10. Given the graph below, how many paths are available to move from location 1 to 5?

11. Given the graph in question 10, which path is the best for moving 1 to 5 if the weights are a
cost?
12. Given below graph, provide the least costly simple path from 1 to 4

13. What is a graph data structure?

14. What are the components of a graph?

15. Explain BFS and Understand its usage/implementation.


16. Explain DFS and Understand its usage/implementation.

17. Explain Dijkstra's Algorithm and Understand its usage/implementation.

18. Explain Topological Sort and Understand its usage/implementation.

19. Explain Minimum Spanning Tree and Understand its usage/implementation.

20. Which of the following points is/are not true about Linked List data structure when it is
compared with an array?
a. Arrays have better cache locality that can make them better in terms of performance
b. It is easy to insert and delete elements in Linked List
c. Random access is not allowed in a typical implementation of Linked Lists
d. Access of elements in linked list takes less time than compared to arrays
21. The following C function takes a singly-linked list as an input argument. It modifies the list
by moving the last element to the front of the list and returns the modified list. A part of the code
is left blank. Choose the correct alternative to replace the blank line.

a. q = NULL; p->next = head; head = p;


b. q->next = NULL; head = p; p->next = head;
c. q->next = NULL; p->next = head; head = p;
d. head = p; p->next = q; q->next = NULL;
22. How do you insert a node at the beginning of the list?
a.

b.

c.

d.
23. What does the following function do for a given Linked List with the first node as head?

a. Prints all nodes of linked lists


b. Prints all nodes of linked list in reverse order
c. Prints alternate nodes of Linked List
d. Prints alternate nodes in reverse order
24. Which ADT uses FILO? What does FILO mean? What about FIFO? Which ADT uses it?
25. What is a merge Sort? Explain with an example sorting values in an array.
26. What is an ordered linear search? Explain with an example sorting values in an array and a
key.
27. a. What is a stack data structure? What are the main operations found in a stack
implementation? Explain with an example.

b. What is a queue data structure? What are the main operations found in a queue
implementation? Explain with an example.

28. What are the differences between singly, doubly and circular linked lists?

29. What are the advantages of arrays?


a. Objects of mixed data types can be stored
b. Elements in an array cannot be sorted
c. Easier to store elements of same data type
d. Index of first element of an array is 1
30. What would be the asymptotic time complexity to find an element in the linked list?
a. O(1)
b. O(n)
c. O(n2)
d. O(n4)

You might also like