Practice Set III: Data Structures and Algorithms (47 Questions)
01. Recursive procedures are implemented by
1) queues
2) stacks
3) linked lists
4) strings
02. A linear list of elements in which deletion can be done from one end (front) and Insertion can take place only at the other end (rear) is known as
1) queue
2) stack
3) tree
4) deque
03. A linear list in which elements can be added or removed at either end but not in the middle is known as
1) queue
2) deque
3) stack
4) tree
04. A list of integers is read in, one at a time, and a binary search tree is constructed. Next the tree is traversed and the integers are printed. Which traversal would result in a printout which duplicates the original order of the list of integers
1) preorder
2) postorder
3) inorder
4) none
05. The five items : A,B,C,D and E are pushed in a stack, one after the other starting from A. The stack is popped four times and each element is inserted in a queue. The two elements are deleted from the queue and pushed back on the stack. The popped item is
1) A
2) B
3) C
4) D
06. The time required to search an element in a binary search tree having n elements is
1) O(n)
2) O(1)
3) O(log n)
4) O(n log n)
07. Consider that n elements are to be sorted. What is the worst case time complexity of bubble sort
1) O(n)
2) O(log n)
3) O(n²)
4) O(n log n)
08. Consider that n elements are to be sorted. That is the worst case time complexity of shell sort
1) O(n)
2) O(n log n)
3) O(n¹.²)
4) O(n²)
09. What is the worst case time complexity of straight insertion sort algorithm to sort n elements
1) O(n)
2) O(n log n)
3) O(n¹.²)
4) O(n²)
10. What is the worst case time complexity of binary insertion sort algorithm to sort n elements
1) O(n)
2) O(n log n)
3) O(n¹.²)
4) O(n²)
11. If each node in a tree has value greater than every value in its left subtree and has value less than every value in its right subtree, the tree is known as
1) complete tree
2) full binary tree
3) binary search tree
4) threaded tree
12. Which of the following procedure is the slowest
1) quick sort
2) heap sort
3) shell sort
4) bubble sort
13. The infix expression A+(B-C)*D is correctly represented in prefix notation as
1) A+B-C*D
2) +A*-BCD
3) A+B-C-D*
4) A+BC-D*
14. What is the postfix expression of the following tree represented in prefix notation as
A+BC-D*
1) 655321++*++
2) 1+2*3+4*5+6
3) 12+34+56+**
4) *+12*+34+56
15. A list of data items usually words or bytes, with the accessing restriction that elements can be added or removed at one end of the list only, is known as
1) stack
2) memory
3) linked list
4) heap
16. In what order the elements of a pushdown stack are accessed
1) FIFO
2) LIFO
3) LILO
4) none
17. Which of the following is a tabular listing of contents of certain registers and Memory locations at different times during the execution of a program
1) loop program
2) program trace
3) subroutine program
4) sorting program
18. How many values can be held by an array A(-1..1, 1..m)
1) l m
2) 2m
3) m(l+1)
4) m(l+2)
19. An undirected graph with n vertices and e edges are represented by Adjacency Matrix. What is the time required to determine the whether the graph is connected
1) O(e)
2) O(n²)
3) O(n² log n)
4) O(e+n)
20. An undirected graph with n vertices and e edges are represented by adjacency Matrix. What is the time required to determine the degree of any vertex
1) O(e)
2) O(n)
3) O(n² log n)
4) O(e+n)
21. A directed graph with n vertices and e edges are represented by adjacency Matrix. What is the time required to determine the in-degree of any vertex
1) O(e)
2) O(n)
3) O(n² log n)
4) O(e+n)
22. Which of the following statements is false
1) every tree is bipartite graph
2) a tree contains a cycle
3) a tree with n nodes contains n-1 edges
4) a tree is a connected graph
23. A graph G with n nodes is bipartite if it contains
1) no edges
2) a cycle of odd length
3) no cycle of odd length
4) none
24. In what tree, for every node the height of its left subtree and right subtree differ atleast by one
1) complete tree
2) AVL tree
3) binary search tree
4) threaded tree
25. Which of the following sorting method is stable
1) straight insertion sort
2) binary insertion sort
3) shell sort
4) heap sort
26. A complete binary tree with the property that the value at each node is atleast as large as the values at its children is known as
1) binary search tree
2) AVL tree
3) complete tree
4) Heap
27. The time required to find the shortest path in a graph with n vertices and e edges is
1) O(e)
2) O(n)
3) O(e+n)
4) O(n²)
28. In which of the following sorting algorithm the number of comparision needed is the minimum if the items are initially in reverse order and is the maximum if the items are in order
1) straight insertion sort
2) binary insertion sort
3) heap sort
4) bubble sort
29. Which of the following best describes sorting
1) accessing and processing each record exactly once
2) finding the location of the record with a given key
3) arranging the data in some given order
4) adding a new record to the data structure
30. The order of magnitude of the worst case performance of the binary search over n elements is
1) n log n
2) n²
3) log n
4) n log n
31. A search procedure which associates an address with a key value and provides a Mechanism for dealing with two or more values assigned to the same address is called
1) linear search
2) binary search
3) hash coded search
4) radix search
32. The order of magnitude of the worst case performance of a hash coded search over n elements is
1) log n
2) n log n
3) O(n)
4) not dependent on n
33. A characteristic of the data that binary search uses but the linear search ignores is
1) order of the list
2) length of the list
3) maximum value of the list
4) mean of data values
34. A sort which compares adjacent elements in a list and switches where necessary is
1) insertion sort
2) heap sort
3) quick sort
4) bubble sort
35. A full binary tree with n leaves contains
1) n nodes
2) n log n nodes
3) 2n-1 nodes
4) 2n+1 nodes
36. A full binary tree with n leaves contains
1) log n nodes
2) n+1 nodes
3) 2n-1 nodes
4) 2n+1 nodes
37. Which of the following sorting algorithms does not have the worst case running time of O(n²)
1) insertion sort
2) merge sort
3) quick sort
4) bubble sort
38. Which of the following sorting algorithms has a worst case running time of O(n²) where n<=100
1) bubble sort
2) insertion sort
3) shell sort
4) merge sort
39. What is the maximum number of fields with each node of doubly linked list
1) 1
2) 2
3) 3
4) 4
40. Given two sorted list of size m and n respectively. The number of comparisons needed in the worst case by the merge sort algorithm will be
1) m n
2) max(m,n)
3) min(m,n)
4) m+n-1
41. Preorder is nothing but
1) depth first order
2) breadth first order
3) topological order
4) linear order
42. Which traversal techniques lists the nodes of a binary search tree in ascending order
1) post order
2) in order
3) pre order
4) none
43. The initial configuration of queue is a,b,c,d (a at the front). To get the configuration d,c,b,a one needs a minimum of
1) 2 deletions and 3 insertions
2) 3 deletions and 2 insertions
3) 3 deletions and 3 insertions
4) 3 deletions and 4 insertions
44. The number of swappings need to sort the numbers 8,22,7,9,31,19,5,13 in Ascending order, using bubble sort is
1) 11
2) 12
3) 13
4) 14
45. There are four algorithms A1, A2, A3, A4 with time complexities O(log n), O(n log n), O(n log n), O(n / log n) respectively. Which is the best algorithm
1) A1
2) A2
3) A3
4) A4
46. Queues serve a major role in
1) simulation of recursion
2) simulation of arbitrary linked list
3) simulation of limited resource allocation
4) expression evaluation
47. What is the number of nodes in a complete binary tree of level 5
1) 15
2) 25
3) 63
4) 71
Submit Quiz