Final Exam Cramming Up (Chapter 11-15)

Question 1

Which is the complexity of a bubble sort algorithm?

Answer 1

O(n2)

Question 2

Given the following list, which is the first step of a insertion sort?

{6, 2, 4, 3}

Answer 2

{2, 6, 4, 3}

Question 3

Given the following list, what is the number of passes to sort the elements using an insertion sort?

14, 12, 16, 6, 3, 10

Answer 3

5

Question 4

Given the following list, which is the first step of a selection sort?

{6, 4, 3, 1}

Answer 4

{1, 4, 3, 6}

Question 5

Which is the complexity of a selection sort algorithm?

Answer 5

O(n^2)

Question 6

Given the following list, which is not one of the possible “halves”?

{ 13, 32, 26, 9, 34, 18, 41, 43 }

Answer 6

18, 41

Question 7

Which is the complexity of a merge sort algorithm?

Answer 7

O(n log n)

Question 8

Which sorting algorithms has the lowest worst-case complexity?

Answer 8

Merge Sort

Question 9

Given the following list, the best candidate of “pivot” of a quick sort is __.

{ 2, 5, 1, 7, 4, 9, 12, 11, 10 }

Answer 9

4

Question 10

Given the following array, what will be the array after the first pass of bubble sort?

{5, 2, 8, 1, 9}

Answer 10

{2, 5, 1, 8, 9}

Question 11

The following is a sample code of __ sorting.

void Sort(int arr[], int n)
{
bool swapped;
for (int i = 0; i < n - 1; i++)
{
swapped = false;
for (int j = 0; j < n - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
swap(arr[j], arr[j + 1]);
swapped = true;
}
}
if (!swapped)
break;
}
}

Answer 11

Bubble

Question 12

The following is a sample code of __ sorting.

void Sort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
swap(arr[min_idx], arr[i]);
}
}

Answer 12

Selections

Question 13

Given the following array, what will be the array after the first pass of selection sort?

{5, 2, 8, 1, 9}

Answer 13

{1, 2, 8, 5, 9}

Question 14

Given the following array, what will be the array after the first pass of bubble sort?

{64, 34, 25, 12, 22, 11, 90}

Answer 14

{34, 25, 12, 22, 11, 64, 90}

Question 15

How many maximum children can a node of a tree structure have?

Answer 15

No limit.

Question 16

Which statement is not true about a tree structure?

Answer 16

The “root” node is the bottom-most node in a tree structure.

Question 17

The operation of processing or visiting each element in the list is called ____.

Answer 17

Traversal

Question 18

How many maximum children can a node of a “binary tree” have?

Answer 18

2

Question 19

Given the following tree, which is not a leaf?

 8    / | \   5  7  6  / \ 4  3

Answer 19

5

Question 20

The following “show()” function is an implementation of the __ traversal of a binary tree structure.

void show(bstnode *node)
{
if (node != NULL)
{
show(node->left);
cout &laquo_space;node->data &laquo_space;” “;
show(node->right);
}

Answer 20

in-order

Question 21

The following “show()” function is an implementation of the __ traversal of a binary tree structure.

void show(bstnode *node)
{
if (node != NULL)
{
show(node->left);
show(node->right);
cout &laquo_space;node->data &laquo_space;” “;
}
}

Answer 21

post-order

Question 22

The following is a __ tree.

 50     /    \    30      70   /  \    /  \  20   40  60   80

Answer 22

binary search

Question 23

If 26 is inserted to the following binary search tree, what will tree turn out to be?

 0    /   \   40   70  /     / \ 25    65 80

Answer 23

0
/ \
40 70
/ / \
25 65 80
\
26

Question 24

What is the defining characteristic of a Binary Search Tree (BST)?

Answer 24

The left child is always smaller than the parent, and the right child is always larger.

Question 25

What is the maximum number of children a node can have in a binary tree?

Answer 25

2

Question 26

Which traversal method visits the root node first, followed by the left subtree, and then the right subtree?

Answer 26

Preorder

Question 27

Which of the following is NOT a common application of trees?

Answer 27

Sorting algorithms

Question 28

Given the following values, what would be the root of the BST created from these values? 50, 30, 70, 20, 40, 60, 80

Answer 28

50

Question 29

Given an undirected graph G with V vertices and E edges, the sum of the degrees of all vertices is __.

Answer 29

2e

Question 30

__ is a sequence of vertices that connect two nodes in a graph.

Answer 30

Path

Question 31

The number of edges in a “complete directed graph” with 12 vertices is __.

Answer 31

12*11

Question 32

Given the following matrix, which statement is correct? \ A B C D E A 0 1 0 0 1 B 1 0 0 1 0 C 0 0 0 1 1 D 0 1 1 0 1 E 1 0 1 1 0

Answer 32

There is an edge between node C and node D.

Question 33

Given the following matrix, which edge has a value of 1 with "edges" being an array of all edges in a graph? i\j 0 1 2 3 4 0 0 1 0 0 1 1 1 0 0 1 0 2 0 0 0 1 1 3 0 1 1 0 1 4 1 0 1 1 0

Answer 33

edges[1][3]

Question 34

In C++, when a pointer will point to an array of pointers, the pointer must be declared with the __ sign.

Answer 34

**

Question 35

Which is the best candidate for being a data structure of a "weighted" directed graph?

Answer 35

struct node { int data; int cost; node* next; }

Question 36

Assuming "arrNode" is an array, which can deallocate it?

Answer 36

delete[] arrNode;

Question 37

Given the following that defines an array of "edge" type which is a structure for a directed graph, how many nodes are in the graph? edge edges[] = { {0, 1}, {0, 3}, {1, 2}, {1, 4}, {2, 3} };

Answer 37

5

Question 38

Given the following code in which "graph" is a structure for a "weighted" directed graph, which statement is true? graph edges[] = { {A,B,2}, {A,C,4}, {B,E,3}, {C,E,2}, {D,B,4}, {E,D,3} };

Answer 38

The cost between node B and E is 3.

Question 39

A graph is a non-linear data structure consisting of __.

Answer 39

nodes and edges

Question 40

Which of the following is an example of common graph representation?

Answer 40

Graphical matrix

Question 41

In an adjacency matrix representation of a graph, a value of 1 at index (i, j) indicates __.

Answer 41

There is an edge from vertex i to vertex j

Question 42

What is the fundamental difference between a directed and undirected graph?

Answer 42

The direction of edges in an undirected graph is bidirectional.

Question 43

In an adjacency matrix, what does a value of 0 at position (i, j) indicate?

Answer 43

There is no edge between vertices i and j

Question 44

In a hash table of size 13, which index positions would 29 and 135 be mapped to?

Answer 44

3, 5

Question 45

Given the following values and the hash function, h(x) = x%10, which of the following statements are true? 4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199

Answer 45

9679, 1989, 4199 hash to the same key

Question 46

Given the following values and a hash table of length 10 uses a hash function, h(k)=k%10, which keys are not in use? 42, 23, 34, 57, 46, 35

Answer 46

0, 1, 8, 9

Question 47

Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 1023?

Answer 47

h(i) = i % 10

Question 48

__ describes the situation that several values are hashed to the same key in the hash table.

Answer 48

Collision

Question 49

What is a hash function? It is function that __.

Answer 49

Computes the key for a value in the array

Question 50

A __ is a general-purpose data structure for storing a group of objects. A dictionary has a set of keys and each key has a single associated value.

Answer 50

dictionary

Question 51

Which is possible a hash function used by a linear probing (or open addressing) algorithm to find the next available slot?

Answer 51

h(x) = (x + i) % size

Question 52

Given the following array of values to be inserted into a hash table that holds exactly 11 values. Which of the following best demonstrates the contents of the hash table after all the keys have been inserted using linear probing? 113, 117, 97, 100, 114, 108, 116, 105, 99

Answer 52

99, 100, __, 113, 114, __, 116, 117, 105, 97, 108

Question 53

What is the term for when two different keys produce the same hash value?

Answer 53

Collision

Question 54

What is a hash function?

Answer 54

A function that maps keys to integer values.

Question 55

Given the following code, which function is the hash function? h1(int sz) { size = sz; } int h2(int key) { return key % size; } void h3(int key, int value) { int index = h2(key); } int h4(int key) { int index = h2(key); } void h5(int value) { cout << value; }

Answer 55

h2

Question 56

Which of the following statement best describes the following code? int hash(int key, int size) { return key % size; }

Answer 56

It divides the key by a prime number slightly larger than the hash table size and uses the remainder as the index.

Question 57

Hash values are a powerful tool that can be used to solve a variety of problems in computer science. Which is not an example of real-world use case?

Answer 57

Linear Search