DBMS(Data base management system)

DBMS(Data base management system)

1) In what kind of storage structure for strings, one can easily insert, delete, concatenate and rearrange substrings?

a)fixed length storage structure b) variable length storage with fixed maximum
c)linked list storage d) array type storage


2) What is the time required to search an element in a linked list of length n?

a) O(log2 n) b) O(n) c) O(1) d) O(n2)


1) Consider a linked list of n element which is pointed by an external pointer. What is the time taken to delete the element which is successor of the element pointed to by a given pointer

a) O(1) b) O(log2 n) c) O(n) d) O(n log2 n)


2) Consider a linked list of n elements. What is the time taker to insert an element after an element pointed by some pointer?

a) O(1) b) O(log2 n) c) O(n) d) O(n log2 n)


3) Consider an undirected graph G with n vertices and e edges. Whjat is the time taken by Depth First Search (DFS) if the graph is represented by (i) adjacency matrix, (ii) adjacency list?

a) O(n2), O(n) b) O(n2), O(e) c) O(e), O(n2) d) O(e+n), O(e)


4) An undirected graph G with n vertices and e edges is represented by adjacency list. What is the time required to generate all the connected components?

a) O(n) b) O(e) c) O(e + n) d) O(e2)


5) Which of the following statements is false?

a) every tree is a bipartite graph b) a tree contains a cycle
c) a tree with n.nodes contains n-1 edges d) a tree is a connected graph




6) A graph G with n nodes is bipartite if it contains

a) n edges b) a cycle of odd length c) no cycle of odd length d) n2 edges


7) In what tree, for every node the height of its left subtree and right subtree differ at least by one

a) binary search tree b) AVL – tree c) Complete tree d) Threaded binary tree


8) A complete binary tree with the property that the value at each node is at least as large as the values at its children is known as

a) binary search tree b) AVL tree c) completely balanced tree d) Heap


9) A full binary tree with n leaves contains

a) n nodes b) log2 n nodes c) 2n-1 nodes d) 2n nodes


10) A full binary tree with n non-leaf nodes contains

a) log2 n nodes b) n + 1 nodes c) 2 n nodes d) 2 n + 1 nodes


11) Preorder is nothing but

a) depth first order b)breadthfirstorder c) topological order d) linear order


12) What traversal techniques lists the notes of a binary search tree is ascending order?

a) post order b) inorder c) preorder d) none of the above


13) Consider a sorted binary insertion tree. What must be done to produce a sorted array of numbers (for printing) from the sorted binary insertion tree?

a) preoder traversal b)postorder traversal c) inorder traversal d) top-down traversal

14) The concatenation of two lists is to be performed in O(1) time. Which of the following implementations of a list should be used?

a) singly linked list b) doubly linked list
c) circular doubly linked list d) array implementation


15) Which of the follwing algorithm solves the all pairs shortest path problem

a) Greedy b) Depth-First search
c) Dyanamic programming d) Divide &Conquer


16) Which of the follwing algorithm solves the Quick Sort problem

a) Greedy b) Depth-First search
c) Dyanamic programming d) Divide &Conquer


17) Which of the follwing algorithm solves the Minimum weight spanning tree problem

a) Greedy b) Depth-First search
c) Dynamic programming d)Divide&Conquer

20) Which of the following algorithm solves the Connected components problem

a) Greedy b) Depth-First search
c) Dynamic programming d)Divide&Conquer

21) selection sort’s worst case Space complexity is …

a) 0 b) O(n) c) O(logn) d)None

22) Bubble sort ‘s worst case Space complexity is…

a) 0 b) O(n) c) O(logn) d)None

23) Insertion sort’s worstcase Space complexity is….

a) 0 b) O(n) c) O(logn) d)None

24) Merge sort’s worst case Space complexity is…

a) 0 b) O(n) c) O(logn) d)None.

25) Quick sort’s worstcase Space complexity is….

a) 0 b) O(n)
c) O(logn) d)None

26)selection sort’s average case Space complexity is …

a) 0 b) O(n)
c) O(logn) d)None


27)Bubble sort ‘s average case Space complexity is….

a) 0 b) O(n)
c) O(logn) d)None

28) Insertion sort’s average case Space complexity is….

a) 0 b) O(n)
c) O(logn) d)None

29) Merge sort’s average case Space complexity is…

a) 0 b) O(n)
c) O(logn) d)None.

30) Quick sort’s average case Space complexity is….

a) 0 b) O(n)
c) O(logn) d)None



Answers
1) C 2) B 3) A 4) A 5) B
6) C 7) B 8) C 9) B 10) D
11) C 12) D 13) A 14) B 15) A
16) D 17) B 18) D 19) C 20) B
21) A 22) A 23) A 24) B 25) B
26) A 27) A 28) A 29) B 30) B