exam Algorithm

Last updated 9 months ago

59 questions

Library

exam Algorithm

Last updated 9 months ago

59 questions

1

Algorithms I (CS214) - Final Exam
Exam Date: Saturday 20/5/2023    Allowed Time: 2 hours
Dr. Salwa Osama

1

What is a hash table?

1

If several elements are competing for the same bucket in the hash table, what is it called?

1

What is the hash function used in the division method?

1

What can be the value of m in the division method?

1

Using division method, in a given hash table of size 157, the key of value 172 is placed at position

1

What is the table size when the value of p is 7 in multiplication method of creating hash functions?

1

What is the average retrieval time when k has the same slot?

1

Collisions can be reduced by choosing a hash function randomly in a way that is independent of the keys that are actually to be stored.

1

What is indirect addressing?

1

What is the search complexity in direct addressing?

1

What is a hash function?

1

Which of the following is not a technique to avoid a collision?

1

What is the load factor?

1

What is simple uniform hashing?

1

In simple chaining, what data structure is appropriate?

1

A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below.
0:
1: 42
2:
3:
4: 23
5: 52
6:
7: 33
8: 34
9:
Which one of the following choices gives a possible order in which the key values could have been inserted in the table?

1

Maximum number of nodes in a binary tree with height k, where root is height 0, is

1

Quick sort algorithm is an example of

1

The minimum number of edges required to create a cyclic graph of n vertices is

Algorithms I (CS214) - Final Exam
Exam Date: Saturday 20/5/2023    Allowed Time: 2 hours
Dr. Salwa Osama

What is a hash table?

If several elements are competing for the same bucket in the hash table, what is it called?

What is the hash function used in the division method?

What can be the value of m in the division method?

Using division method, in a given hash table of size 157, the key of value 172 is placed at position

What is the table size when the value of p is 7 in multiplication method of creating hash functions?

What is the average retrieval time when k has the same slot?

Collisions can be reduced by choosing a hash function randomly in a way that is independent of the keys that are actually to be stored.

What is indirect addressing?

What is the search complexity in direct addressing?

What is a hash function?

Which of the following is not a technique to avoid a collision?

What is the load factor?

What is simple uniform hashing?

In simple chaining, what data structure is appropriate?

A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below.
0:
1: 42
2:
3:
4: 23
5: 52
6:
7: 33
8: 34
9:
Which one of the following choices gives a possible order in which the key values could have been inserted in the table?

Maximum number of nodes in a binary tree with height k, where root is height 0, is

Quick sort algorithm is an example of

The minimum number of edges required to create a cyclic graph of n vertices is

Which of the following is example of not in-place algorithm?

Time required to sort "n" identical items of size m and n, is

Which of the following uses memorization?

Heap is an example of

Access time of a binary search tree may go worse in terms of time complexity up to

What will be the Huffman code for the letters a,b,c,d,e? If the probability are ½,1/4, 1/8,1/16,1/32

From the following sorting algorithms which algorithm needs the minimum number of swaps

From the following sorting algorithms which has the lowest worst case complexity?

Match the following pairs
I. O(\log\ n) (M) Heap sort
II. O(n) (N) DFS
III. n\log(n) (O) Binary search
IV. O(n^2) (P) Selecting kth smallest elements

What shall be value of x in the following pseudocode? x = 0; For (t = t; t <= N; t++) For p = l; p <= t; p++) x = x+1; EndFor EndFor

Time complexity on merging three sorted lists of sizes m, n and p is

Which of the algorithm design approach is used by Mergesort

Which of the following shortest path algorithm cannot detect presence of negative weight cycle graph?

For the figure below, starting at vertex A, which is a correct order for Prim's minimum spanning tree algorithm to add edges to the minimum spanning tree?

Graph Algorithms Questions

For the figure below, which is a correct order for Kruskal's minimum spanning tree algorithm to add edges to the minimum spanning tree? ∑ ∧ | B

If G is an directed graph with 20 vertices, how many boolean values will be needed to represent G using an adjacency matrix?

What is the special property of red-black trees and what root should always be?

Why do we impose restrictions like . root property is black . every leaf is black . children of red node are black . all leaves have same black

What are the operations that could be performed in O(logn) time complexity by red-black tree?

Why Red-black trees are preferred over hash tables though hash tables have constant time complexity?

Pseudo Code
What is the below pseudo code trying to do, where pt is a node pointer an l root pointer?
redblack(Node root, Node pt) : if (root == NULL) return pt if (pt.data < root.data) { root.left = redblack(root.left, pt); root.left.parent = root; } else if (pt.data > root.data) { root.right = redblack(root.right, pt); root.right.parent = root; } return root

Dijkstra’s Algorithm is used to solve problems.

What is the time complexity of Dijkstra’s algorithm?

Dijkstra’s Algorithm cannot be applied on

How many priority queue operations are involved in Dijkstra's Algorithm?

How many times the insert and extract min operations are invoked per vertex

The maximum number of times the decrease key operation performed in Dijkstra's algorithm will be equal to

What is running time of Dijkstra's algorithm using Binary min- heap method?

Why Red-black trees are preferred over hash tables though hash tables have constant time complexity?

What will be the below pseudo code trying to do, where pt is a node pointer and root pointer?
redblack(Node root, Node pt) { if (root == NULL) return pt; if (pt.data < root.data) { root.left = redblack(root.left, pt); root.left.parent = root; } else if (pt.data > root.data) { root.right = redblack(root.right, pt); root.right.parent = root; } return root;
}

exam Algorithm

exam Algorithm

What is a hash table?

If several elements are competing for the same bucket in the hash table, what is it called?

What is the hash function used in the division method?

What can be the value of m in the division method?

Using division method, in a given hash table of size 157, the key of value 172 is placed at position

What is the table size when the value of p is 7 in multiplication method of creating hash functions?

What is the average retrieval time when k has the same slot?

Collisions can be reduced by choosing a hash function randomly in a way that is independent of the keys that are actually to be stored.

What is indirect addressing?

What is the search complexity in direct addressing?

What is a hash function?

Which of the following is not a technique to avoid a collision?

What is the load factor?

What is simple uniform hashing?

In simple chaining, what data structure is appropriate?

Maximum number of nodes in a binary tree with height k, where root is height 0, is

Quick sort algorithm is an example of

The minimum number of edges required to create a cyclic graph of n vertices is

Which of the following is example of not in-place algorithm?

Time required to sort "n" identical items of size m and n, is

Which of the following uses memorization?

Heap is an example of

Access time of a binary search tree may go worse in terms of time complexity up to

What will be the Huffman code for the letters a,b,c,d,e? If the probability are ½,1/4, 1/8,1/16,1/32

From the following sorting algorithms which algorithm needs the minimum number of swaps

From the following sorting algorithms which has the lowest worst case complexity?

Match the following pairsI. O(\log\ n) (M) Heap sortII. O(n) (N) DFSIII. n\log(n) (O) Binary searchIV. O(n^2) (P) Selecting kth smallest elements

What shall be value of x in the following pseudocode? x = 0; For (t = t; t <= N; t++) For p = l; p <= t; p++) x = x+1; EndFor EndFor

Time complexity on merging three sorted lists of sizes m, n and p is

Which of the algorithm design approach is used by Mergesort

Which of the following shortest path algorithm cannot detect presence of negative weight cycle graph?

For the figure below, starting at vertex A, which is a correct order for Prim's minimum spanning tree algorithm to add edges to the minimum spanning tree?

Graph Algorithms QuestionsFor the figure below, which is a correct order for Kruskal's minimum spanning tree algorithm to add edges to the minimum spanning tree? ∑ ∧ | B

If G is an directed graph with 20 vertices, how many boolean values will be needed to represent G using an adjacency matrix?

What is the special property of red-black trees and what root should always be?

Why do we impose restrictions like . root property is black . every leaf is black . children of red node are black . all leaves have same black

What are the operations that could be performed in O(logn) time complexity by red-black tree?

Why Red-black trees are preferred over hash tables though hash tables have constant time complexity?

Dijkstra’s Algorithm is used to solve problems.

What is the time complexity of Dijkstra’s algorithm?

Dijkstra’s Algorithm cannot be applied on

How many priority queue operations are involved in Dijkstra's Algorithm?

How many times the insert and extract min operations are invoked per vertex

The maximum number of times the decrease key operation performed in Dijkstra's algorithm will be equal to

What is running time of Dijkstra's algorithm using Binary min- heap method?

Why Red-black trees are preferred over hash tables though hash tables have constant time complexity?

Dijkstra's Algorithm is used to solve the following problems.

What is the time complexity of Dijkstra's algorithm?

Dijkstra's Algorithm cannot be applied on

How many priority queue operations are involved in Dijkstra's Algorithm?

How many times the insert and extract min operations are invoked per vertex?

The maximum number of times the decrease key operation performed in Dijkstra's algorithm will be equal to

What is running time of Dijkstra's algorithm using Binary min-heap method?

If b is the source vertex, what is the minimum cost to reach vertex f?

Identify the shortest path having minimum cost to reach vertex E if A is the source vertex

Dijkstra's Algorithm is the prime example for

What is a hash table?

If several elements are competing for the same bucket in the hash table, what is it called?

What is the hash function used in the division method?

What can be the value of m in the division method?

Using division method, in a given hash table of size 157, the key of value 172 is placed at position

What is the table size when the value of p is 7 in multiplication method of creating hash functions?

What is the average retrieval time when k has the same slot?

Collisions can be reduced by choosing a hash function randomly in a way that is independent of the keys that are actually to be stored.

What is indirect addressing?

What is the search complexity in direct addressing?

What is a hash function?

Which of the following is not a technique to avoid a collision?

What is the load factor?

What is simple uniform hashing?

In simple chaining, what data structure is appropriate?

Maximum number of nodes in a binary tree with height k, where root is height 0, is

Quick sort algorithm is an example of

The minimum number of edges required to create a cyclic graph of n vertices is

Which of the following is example of not in-place algorithm?

Time required to sort "n" identical items of size m and n, is

Which of the following uses memorization?

Heap is an example of

Match the following pairs
I. O(\log\ n) (M) Heap sort
II. O(n) (N) DFS
III. n\log(n) (O) Binary search
IV. O(n^2) (P) Selecting kth smallest elements

Graph Algorithms Questions

For the figure below, which is a correct order for Kruskal's minimum spanning tree algorithm to add edges to the minimum spanning tree? ∑ ∧ | B

Match the following pairs
I. O(\log\ n) (M) Heap sort
II. O(n) (N) DFS
III. n\log(n) (O) Binary search
IV. O(n^2) (P) Selecting kth smallest elements

Graph Algorithms Questions

For the figure below, which is a correct order for Kruskal's minimum spanning tree algorithm to add edges to the minimum spanning tree? ∑ ∧ | B