final exam_DIS

Question 1

In the graph given below, which of the following nodes will be visited last if you apply breadth-first search starting from A?

Answer 1

H

Question 2

An algorithm to traverse a directed graph must mark vertices when they have been visited.

Answer 2

True

Question 3

Shortest path problem can be solved with an easy modification of the depth-first search algorithm

Answer 3

False

Question 4

Depth-first search can use a queue for tracking visited nodes.

Answer 4

False

Question 5

Breadth-first search can use a queue for tracking visited nodes

Answer 5

True

Question 6

Adjacency matrix representation causes redundancy in undirected graphs since the matrix is always symmetric.

Answer 6

True

Question 7

Depth-first search starts from the root of the graph.

Answer 7

False

Question 8

Traveling salesman problem is an NP-complete problem.

Answer 8

True

Question 9

Red-Black Tree does not need rotations since recoloring always keeps the tree balanced

Answer 9

False

Question 10

If your application involves frequent insertions and deletions, then Red-Black tree should be preferred to AVL tree.

Answer 10

True

Question 11

Each node stores at most 4 data values in a 2-3-4 Tree

Answer 11

False

Question 12

The root of the tree is always red in a red-black tree.

Answer 12

False

Question 13

In a directed graph, there may not be a path from one node to another.

Answer 13

True

Question 14

There must be a root node in a directed graph which does not have an incoming arc

Answer 14

False

Question 15

All the leaves are on the same level in a 2-3-4 Tree

Answer 15

True

Question 16

Which of the following tree is used for external search?

Answer 16

B-Tree

Question 17

A rotation is needed in an AVL Tree when the balance factor of a node becomes -3 or +3 after insertion

Answer 17

False

Question 18

One simple rotation is sufficient to keep AVL Tree balanced after each insertion or deletion

Answer 18

False

Question 19

ASCII is a variable-length coding scheme.

Answer 19

False

Question 20

AVL Tree is a balanced binary search tree.

Answer 20

True

Question 21

The worst case search time in AVL Tree is O(log2n)

Answer 21

True

Question 22

The worst case computing time of merge sort is O(n*logn).

Answer 22

True

Question 23

Radix sort operates in O(n+w) time, where w is the number of digits.

Answer 23

False

Question 24

Quick sort requires more space than Radix sort.

Answer 24

False

Question 25

Merge sort can be used both as an internal and an external sort.

Answer 25

True

Question 26

Which of the following array is created after the first iteration of Radix sort, when the array contains {67,22,44,79,25,81,56,38}?

Answer 26

{81,22,44,25,56,67,38,79}

Question 27

Since Radix Sort depends on digits or letters, Radix Sort is much less flexible than other sorts.

Answer 27

True

Question 28

The worst case computing time of quick sort is O(n*logn).

Answer 28

False

Question 29

The best method to select a pivot in quick sort is selecting the first element as pivot.

Answer 29

False

Question 30

Which of the following array is the result of the split operation, when the array contains {20,22,14,19,25,12} and 20 is selected as pivot in quick sort?

Answer 30

{19,12,14,20,25,22}

Question 31

Which of the following array is created after the first iteration of binary merge sort, when the array contains {17,22,14,19,25,12,9,7}?

Answer 31

{17,22,14,19,12,25,7,9}

Question 32

A heap can be used to implement a priority queue efficiently.

Answer 32

True

Question 33

What is the worst case computing time of selection sort?

Answer 33

O(n2)

Question 34

What is the worst case computing time of heap sort?

Answer 34

O(nlog2n)

Question 35

What is the worst case computing time of bubble sort?

Answer 35

O(n2)

Question 36

What is the worst case computing time of inserting an element to a heap?

Answer 36

O(log2n)

Question 37

What is the worst case computing time of retrieving (without deleting) the maximum element in a heap?

Answer 37

O(1)