mcqs on dsps

MCQ for DSPS

1. On which principle does stack work?

A. FILO B. FIFO C. LILO D. Both a and c above

2. Items in a priority queue are entered in a _______________ order

A. random B. order of priority C. as and when they come D. none of the above

3. A tree cannot contain cycles

A. False B. True

4. In graphs, A hyperedge is an edge that is allowed to take on any number of _____________

A. Vertices B. Edges C. Both a and b above D. Labels

5. Key value pairs is usually seen in

A. Hash tables B. Heaps C. Both a and b D. Skip list

6. Breadth First Search is used in

A. Binary trees B. Stacks C. Graphs D. Both a and c above

7. Which of the following ways below is a pre order traversal?

A. Root->left sub tree->right sub tree B. Root-> right sub tree ->left sub tree

C. right sub tree->left sub tree->Root D. left sub tree->right sub tree->Root

8. AVL trees have a faster ________________

A. Insertion B. Deletion C. Updation D. Retrival

9. Which of the following statements hold true for binary trees?

A. The left subtree of a node contains only nodes with keys less than the node’s key

B. The right subtree of a node contains only one nodes with key greater than the node’s key.

C. Both a and b above

D. Noth left and right subtree nodes contains only nodes with keys less than the node’s key

10. Which of the following linked list below have last node of the list pointing to the first node?

A. circular doubly linked list B. circular linked list

C. circular singly linked list D. doubly linked list

11. Which of the following ways below is a In order traversal?

A. Root->left sub tree->right sub tree B. Root-> right sub tree ->left sub tree

C. right sub tree->left sub tree->Root D. left sub tree->right sub tree->Root

12. Can stack be describe as a pointer?

A. Yes B. No

13. The time required in best case for search operation in binary tree is

A. O(n) B. O(log n) C. O(2n) D. O(log 2n)

14. In ______________ tree, the heights of two child subtree of any node differ by at most one

A. Binary tree B. Red black tree C. Splay tree D. AVL tree

15.A binary tree can have

A.. two nodes B. any number of nodes C. maximum of two nodes

16.Number of nodes in a strictly binary tree with N leaves is

A. 2N - 1 B. N C. 2N

17.A binary tree in which every non-leaf node has non-empty right and left subtrees is said to be A. strictly binary tree B. complete binary tree C. almost complete binary tree

16. In the inorder tree traversal the root is visited

A. before left subtree visit B. in between subtree visits C .before right subtree visit

18.In the sequential representation of binary tree implementation each node of the tree will have

A no link field B. info, left, right and father fields

C. three fields, data and the pointers to left and right subtrees.

19.The binary tree in which the descendent points to the ancestor is called

A. linked tree B. threaded tree C. pointer tree

20.In a decision tree each decision taken is represented by a

A. node B. branch C. leaf

21.A game tree represents the

A. moves made B. decisions taken C. comparisions done

/ \

2 11

/ \ / \

1 3 10 30

/ /

7 40

Fig 1

Consider Fig 1 to give answer of Ques 22 to 27

22. How many leaves does it have?

A. 2 B. 4 C. 6 D. 8

23.How many of the nodes have at least one sibling?

A. 5 B. 6 C. 7 D. 8

24.What is the value stored in the parent node of the node containing 30?

A. 10 B. 11 C. 14 D. 40

25.How many descendants does the root have?

A. 0 B. 2 C. 4 D. 8

26.What is the depth of the tree?

A. 2 B. 3 C. 4 D. 8

27. How many children does the root have?

A. 2 B. 4 C. 6 D. 8

28. Which statement is correct?

A. The tree is neither complete nor full. B. The tree is complete but not full.

C. The tree is full but not complete. D. The tree is both full and complete.

29.What is the minimum number of nodes in a full binary tree with depth 3?

A. 3 B. 4 C. 8 D. 11

30.What is the minimum number of nodes in a complete binary tree with depth 3?

A. 3 B. 4 C. 8 D. 15

31.Select the one true statement.

A. Every binary tree is either complete or full.

B. Every complete binary tree is also a full binary tree.

C. Every full binary tree is also a complete binary tree.

D. No binary tree is both complete and full.

32.Suppose T is a binary tree with 14 nodes. What is the minimum possible depth of T?

A. 0 B. 3 C. 4 D. 5

33.Select the one FALSE statement about binary trees:

A. Every binary tree has at least one node.

B. Every non-empty tree has exactly one root node.

C. Every node has at most two children.

D. Every non-root node has exactly one parent.

34.Consider the binary_tree_node from page 465. Which expression indicates that t represents an empty tree?

A. (t == NULL) B. (t->data( ) == 0) C. (t->data( ) == NULL)

D. ((t->left( ) == NULL) && (t->right( ) == NULL))

35.Consider the node of a complete binary tree whose value is stored in data[i] for an array implementation. If this node has a right child, where will the right child's value be stored?

A. data[i+1] B. data[i+2] C. data[2*i + 1] D. data[2*i + 2]

/ \

2 11

/ \ / \

1 3 10 30

/ /

7 40

Fig 2

Consider Fig 2 to give answer of Ques 36 to 38

36.What is the order of nodes visited using a pre-order traversal?

A. 1 2 3 7 10 11 14 30 40 B. 1 2 3 14 7 10 11 40 30

C. 1 3 2 7 10 40 30 11 14 D. 14 2 1 3 11 10 7 30 40

37.What is the order of nodes visited using an in-order traversal?

A. 1 2 3 7 10 11 14 30 40 B. 1 2 3 14 7 10 11 40 30

C. 1 3 2 7 10 40 30 11 14 D. 14 2 1 3 11 10 7 30 40

38. What is the order of nodes visited using a post-order traversal?

A. 1 2 3 7 10 11 14 30 40 B. 1 2 3 14 7 10 11 40 30

C. 1 3 2 7 10 40 30 11 14 D. 14 2 1 3 11 10 7 30 40

39.Suppose we remove the root, replacing it with something from the left subtree. What will be the new root?

A. 1 B. 2 C. 4 D. 5

Explanation: Minimum spanning tree for 2 nodes would be

(v1) _ (v2)

Total weight 3

Minimum spanning tree for 3 nodes would be

(v1) _ (v2)

(v3)

Total weight= 3 + 4 = 7

Minimum spanning tree for 4 nodes would be

(v1) _ (v2) _ (v4)

(v3)

Total weight= 3 + 4 + 6 = 13

Minimum spanning tree for 5 nodes would be

(v1) _ (v2) _ (v4)

(v3)

(v5)

Total weight= 3 + 4 + 6 + 8 = 21

Minimum spanning tree for 6 nodes would be

(v1) _ (v2) _ (v4) _ (v6)

(v3)

(v5)

Total weight= 3 + 4 + 6 + 8 + 10 = 31

We can observe from above examples that when we add kth node, the weight of spanning tree increases by 2k-2. Let T(n) be the weight of minimum spanning tree. T(n) can be written as

T(n) = T(n-1) + (2n-2) for n > 2
T(1) = 0, T(2) = 0 and T(2) = 3

The recurrence can be written as sum of series (2n – 2) + (2n-4) + (2n-6) + (2n-8) + …. 3 and solution of this recurrence is n^2 – n + 1.

40. The length of the path from v5 to v6 in the MST of previous question with n = 10 is
(A) 11 (B) 25 (C) 31 (D) 41

Explanation: Any MST which has more than 5 nodes will have the same distance between v5 and v6 as the basic structure of all MSTs (with more than 5 nodes) would be following.

(v1) _ (v2) _ (v4) _ (v6) _ . . (more even numbered nodes)

(v3)

(v5)

(more odd numbered nodes)

Distance between v5 and v6 = 3 + 4 + 6 + 8 + 10 = 31

41.Let w be the minimum weight among all edge weights in an undirected connected graph.Let e be a specific edge with weight w. Which of the following is false?

A.There is minimum spanning tree containing edge e

B.If e is not in minimum spanning tree T, then the cycle is formed by adding e to T, all edge have the same weight

C.Every minimum spanning tree has an edge of weight w

D.e is present in every minimum spanning tree

42.An advantage of chained hash table over open addressing scheme is

A.Worst case complexity of search algorithm is less

B.Space used is less C.Deletion is easier D.None of these

43.The average search time of hashing with linear probing will be less if laod factor

A.is far less than 1 B.Equals 1 C.is far greater than 1 D.None of these

44. A hash function f is defined as f(key)=key mod 7, with linear probing, is used to insert keys 37, 38, 7248, 98, 11, 56 into a table indexed from 0-6. What will be the location of key 11?

A.3 B. 4 C. 5 D. 6

45.What would be the hash address for the following function by using the folding method

H_k = H(4326)?

A.69 B. 32 C. 46 D. 105

46.Which of the following is generated by Folding method?

A. hash function B.Index function for a triangular matrix

C. Linking the tail node to the head node in linked list D. Linear probing

47. Which of the following has a desired key is searched, starting itself from hash address, sequentially in a table?

A.Quadratic probing B. Random probing C.Linear probing D.Chaining

48.The number of loop(s) of a node in a simple graph of ‘N’ nodes is

A. 1 B.0 C. N D. Exactly one

49. To calculate c(i, j )’s, w( i, j)’s and r(i, j)’s; Howmuch time does the OBST algorithm in worst case takes?

A.log n B. n⁴C.n³ D.nlogn

50.What of the following cases is a so-called "collision"?

A.A hash function produces the same address for two different keys:

h( key1 ) = h( key2 ) where key1 =\= key2

B.Two different hash functions produce the same address for a given key:

h1( key ) = h2( key )

C.Two different hash functions produce the same address for two different keys:

h1( key1 ) = h2( key2 ) where key1 =\= key2

D.A hash function produces the same address for two different keys with different lengths:

h( key1 ) = h( key2 ) where length(key1) =\= length (key2)

51. Hashing collision resolution techniques are

A.Huffman coding, linear hashing B.Bucket addressing, Huffman coding

C. Chaining, Huffman coding D.Chaining, Bucket addressing

52.Number of vertices of odd degree in a simple graph is

A.Always even B.Always odd C.Either even or odd D.Always zero

53.Two isomorphic graphs must have

A.Equal number of vertices B.Same number of edges

C.Same number of vertices D.All

54.A graph in which all nodes are of equal degrees is known as

A.Complete graph B.Regular graph C.Non regular graph D.Multigraph

55.A simple graph in which there exists an edge between every pair of vertices is called

A.Complete B. Eular C.Planar D.Regular

56.The most common hash functions use the__________to compute hash address.

A.Division B.Union C.Subtraction D.None of these

57. The goal of hashing is to produce a search that takes

A.O(1) B.O(n) C.O(log n) D.O(nlog n)

58.If h is any hashing function and is used to hash n keys in to a table of size m, where n<=m, the expected number of collisions involving a particular key x is

A. less than 1 B. less than n C. less than m D.less than n/2

59. What is the hash key of 954 if the number being used to divide is 3?

A. 9 B. 2 C. 5 D. 0

60.What is a restriction of the regular 'Direct Address Tables'?

A. The range of the key must be severely bounded B. The range of the key is unlimited.

C. It takes up too much memory on the hard drive D.It is far too slow

61. What is the best definition of a collision in a hash table?

A. Two entries are identical except for their keys.

B. Two entries with different data have the exact same key.

C. Two entries with different keys have the same exact hash value.

D. Two entries with the exact same key have different hash values.

62. Which guideline is NOT suggested from empirical or theoretical studies of hash tables:

A. Hash table size should be the product of two primes.

B. Hash table size should be the upper of a pair of twin primes.

C. Hash table size should have the form 4K+3 for some K.

D. Hash table size should not be too near a power of two.

63. What kind of initialization needs to be done for an open-address hash table?

A. The key at each array location must be initialized.

B. The head pointer of each chain must be set to NULL.

C. Both A and B must be carried out.

D.None.

64. What kind of initialization needs to be done for an chained hash table?

A. The key at each array location must be initialized

B. The head pointer of each chain must be set to NULL.

C. Both A and B must be carried out.

D. None

65. A chained hash table has an array size of 512. What is the maximum number of entries that can be placed in the table?

A. 256

B. 511

C. 512

D. There is no maximum.

67. Suppose you place m items in a hash table with an array size of s. What is the correct formula for the load factor?

A. s + m

B. s - m

C. m - s

D. m * s

E. m / s

68. What causes a collision?

A.The program you are running crashes

B.There are too many hash keys in the array

C.Two hash keys are the same

D.The program is out of memory

69. What are the three types of collision solutions?

A. Overflow, underflow and undertow B. Chaining, overflow and probing

C. Probing, underflow and chaining D. Noflow, fastflow and chaining

E. None of the above

70. What does hashing improve?

A. Speed B.Hard drive space C.None D.All

71. What does hashing do?

A. Delete old files B.Create new files

C.Improve the air quality of the room D.None of the above

72. How is a hash key computed?

A. Subtraction B.Random number generation C. Modulo division D.All of the above

73. What can be done to compute the hash key value of a string?

a. Convert them all to their ASCII values

b. Generate random numbers for the letters every time

c. Give them each a value according to their place in the alphabet

A. a and b only B. a and c only C. b and c only

Explanation: consider a string "ace"

key=1*26²+3*26¹+5*26⁰(place of a is 1, c is 3 and e is 5)

address=key%size

74. Items in a priority queue are entered in a ________orde

a. Random b. order of priority c. as & when they come d. none

75. A _______ tree is a tree where for each parent node, there is only one associated child node.

a. Balanced binary tree c. complete binary tree

b. Rooted complete binary tree d. degenerated tree

76. In _______ tree, the heights of two child sub trees of any node differ by at most one.

a. Binary tree b. red black tree c. splay tree d. AVL tree

77. Key value pair is usually seen in

a. Hash tables b. heaps c. both a & b d.None

78. which principle does queue works

a. FILO b. FIFO c. LIFO d. both b & c

79. In graphs, a hyperedge is the edge that is allowed to take any number of

a. Vertices b. edges c. both a & b d. labels

80. The time required in the best case for search operation in binary tree

a. O(n) b. O(2n) c. O(log n) d. O(log2n)

81. On which principle does stack works

a. FIFO b. LIFO c. FILO d. both FILO & LIFO

82. Given a traversal of tree, which traversal type would print the values in the nodes in sorted order

a. Preorder b. Postorder c. Inorder d.None

83. What is the running time of the following code fragment?

for(int i=0; i<10; i++)

for(int j=0; j<N; j++)

for(int k=N-2; k<N+2; k++)

cout << i << " " << j << endl;

a. O(log N) b. O(N log N) c.O(N) d.O(N²⁾

84. Suppose we’re debugging a quicksort implementation that is supposed to sort an array in ascending order. After the first partition step has been completed, the contents of the array are in the following order:

3 9 1 14 17 24 22 20

Which of the following statements is correct about the partition step?

a. The pivot could have been either 14 or 17

b. The pivot could have been 14, but could not have been 17

c. The pivot could have been 17, but could not have been 14

d. Neither 14 nor 17 could have been the pivot

74. Which of the following statements about binary trees is NOT true?

a. Every binary tree has at least one node

b. Every non-empty tree has exactly one root node.

c. Every node has at most two children.

d. Every non-root node has exactly one parent.

75. In lecture we defined a class IntStack to implement a stack of integers:

class IntStack {

public:

IntStack( );

bool isEmpty( );

void push(int item);

int pop( );

int top( );

}

What happens if we execute the following statements?

IntStack s;

int n1, n2, n3;

s.push(17);

s.push(143);

s.push(42);

n1 = s.pop( );

n2 = s.top( );

s.push(n1);

n3 = s.pop( );

n1 = s.top( );

a. Stack contains 143 (top), 17 (bottom); n1=42, n2=42, n3=42

b. Stack contains 42 (top), 42, 143, 17 (bottom); n1=42, n2=42; n3=42

c. Stack is empty; n1=17, n2=143, n3=42

d. Stack contains 42 (top), 17 (bottom); n1=42, n2=143, n3=143

e. Stack contains 143 (top), 17 (bottom); n1=143, n2=143, n3=42

76. Is this a binary search tree?

/ \

17 60

/ \ / \

5 20 42 105

/ \ \

3 9 53

a. True b. False

77. What is the expected time required to search for a value in a binary search tree containing n nodes?

a. O(1) b. O(log n) c. O(n) d. O(n log n) e. O(n²)

78. If we use mergesort to sort an array with n elements, what is the worst case time required for the sort?

a. O(1) b. O(log n) c. O(n) d. O(n log n) e. O(n²)

79. There are several factors that affect the efficiency of lookup operations in a hash table.

Which of the following is not one of those factors?

a. Number of elements stored in the hash table

b. Size of elements stored in the hash table

c. Number of buckets in the hash table

d. Quality of the hash function

e. All of the above factors affect the efficiency of hash table lookups

80. What is the complexity of the following code expressed in O( ) notation? If more than one answer is correct, choose the smallest one.

for (int j = n; j > 0; j--) {

for (int k = 1; k < j; k = k+k) {

cout << j+k << “ ”;

}

cout << endl;

}

a. O(log n) b. O(n) c. O(n log n) d. O(n²) e. O(2ⁿ)

81. What is the infix version of the following postfix expression?

x 12 + z 17 y + 42 * / +

Hint: Try using a stack to evaluate the postfix expression and see what happens.

a. (x + 12 + z) / (17 + y * 42)

b. x + 12 + z / 17 + y * 42

c. x + 12 + z / (17 + y) * 42

d. x + 12 + z / ((17 + y) * 42)

e. x + (12 + z) / (17 + y * 42)

82. Which of the following statements about binary trees is NOT true?

a. Every binary tree has at least one node

b. Every non-empty tree has exactly one root node.

c. Every node has at most two children.

d. Every non-root node has exactly one parent

83. In lecture we defined a class IntStack to implement a stack of integers:

class IntStack {

public:

IntStack( );

bool isEmpty( );

void push(int item);

int pop( );

int top( );

}

What happens if we execute the following statements?

IntStack s;

int n1, n2, n3;

s.push(17);

s.push(143);

s.push(42);

n1 = s.pop( );

n2 = s.top( );

s.push(n1);

n3 = s.pop( );

n1 = s.top( );

a. Stack contains 143 (top), 17 (bottom); n1=42, n2=42, n3=42

b. Stack contains 42 (top), 42, 143, 17 (bottom); n1=42, n2=42; n3=42

c. Stack is empty; n1=17, n2=143, n3=42

d. Stack contains 42 (top), 17 (bottom); n1=42, n2=143, n3=143

e. Stack contains 143 (top), 17 (bottom); n1=143, n2=143, n3=42

84. Is this a binary search tree?

/ \

17 60

/ \ / \

5 20 42 105

/ \ \

3 9 53

a. True b. False

85. What is the expected time required to search for a value in a binary search tree containing n nodes?

a. O(1) b. O(log n) c. O(n) d. O(n log n) e. O(n²)

Search This Blog

Data Structures, Programming and Algorithms

mcqs on dsps

MCQ for DSPS

Comments

Post a Comment

Popular posts from this blog

python

Mathematical Model