EGR227 final practice cards

1) Which collision resolution technique places the item in another empty bucket?

a. Chaining

b. Open hashing

c. Open addressing

d. Closed addressing

c

2) A hash function uses an item's ___ to compute the item's bucket index.

a. bucket

b. key

c. function

d. location

b

3) What operation is used to compute a bucket index in the range 0 to 16 from a key?

a. key * 17

b. key - 17

c. key / 17

d. key % 17

d

4) Consider a hash table with items 10, 31, 23, 54, 66, 88, and 9, and a hash function of key % 10. Which of the following items will result in a collision if the numbers are inserted in order? 55, 46, 77, 99, 93, 92, 97

a. 55, 77, 99, 92

b. 55, 77, 92, 97

c. 46, 99, 93, 97

d. 46, 77, 99, 93

c

5) A 5-bucket hash table has the items 45, 56, and 67. The hash table's items will be positive integers. Which of the following is the correct way of representing the hash table?

a. 0, 45, 56, 67, 0

b. 45, 56, 67, 0, 0

c. -1, 45, 56, 67, 1

d. 45, 56, 67, -1, -1

d

6) Consider a hash table using chaining with 10 buckets and a hash function of key % 10. What would bucket 3’s list be after the following operations? HashInsert(hashTable, item 12)

HashInsert(hashTable, item 23) HashInsert(hashTable, item 34) HashInsert(hashTable, item 45) HashInsert(hashTable, item 33) HashInsert(hashTable, item 31) HashInsert(hashTable, item 30)

a. 23, 33

b. 23, 30, 31, 33

c. 34, 33

d. 24, 33, 31, 30

a

7) Consider the following hash table, and a hash function of key % 5. What would bucket 3’s list be after the following operations?

HashRemove(hashTable, 25) HashRemove(hashTable, 48) HashInsert(hashTable, item 53)

a. 33, 53

b. 68, 33, 53

c. 68, 33, 48

d. 68, 33, 48, 53

b

8) Consider the following hash table, and a hash function of key % 10. How many list items will be compared for the search operations?

HashInsert(newTable, item 25) HashInsert(newTable, item 54) HashRemove(newTable, 27) HashInsert(newTable, item 84) HashInsert(newTable, item 83) HashSearch(newTable, 72) HashSearch(newTable, 77) HashSearch(newTable, 63)

a. 2; 0; 2

b. 2; 0; 3

c. 1; 0; 3

d. 2; 0; 1

d

9) Given the following hash table, how many items are compared when searching for item 45 using the following search algorithm?

PICTURE NEEDED

a. 3 items: 25, 45 and 65

b. 4 items: 47, 28, 25, and 45

c. 2 items: 25 and 45

d. 1 item: only 45

c

10) Consider a hash table named marksTable that uses linear probing and a hash function of key % 5. What would be the location of the item 46?

HashInsert(marksTable, item 49) HashInsert(marksTable, item 41) HashInsert(marksTable, item 42) HashInsert(marksTable, item 44) HashInsert(marksTable, item 46)

a. Bucket 0

b. Bucket 1

c. Bucket 2

d. Bucket 3

d

11) Consider a hash table named numTable that uses linear probing and a hash function of key % 5. What is the status of bucket 4 after the following operations?

HashInsert(numTable, item 24) HashInsert(numTable, item 33) HashInsert(numTable, item 51) HashInsert(numTable, item 44) HashInsert(numTable, item 52) HashRemove(numTable, 44) HashInsert(numTable, item 50)

a. empty-since-start

b. empty-after-removal

c. occupied

d. removed from table

c

12) Consider a hash table named idTable that uses linear probing and a hash function of key % 10. What is printed after the following operations?

HashInsert(idTable, item 45) HashInsert(idTable, item 67) HashInsert(idTable, item 76) HashInsert(idTable, item 78) HashInsert(idTable, item 79) HashInsert(idTable, item 92) HashInsert(idTable, item 87)

Print HashSearch(idTable, 67) Print HashSearch(idTable, 77) Print HashSearch(idTable, 87)

a. 67, 87

b. 67, null, 87

c. 67, false, 87

d. true, false, true

b

13) Which XXX completes the following algorithm? PICTURE NEEDED

a. return hashTable[key]

b. return hashTable[bucket]

c. return bucket

d. return key

b

15) A hash table named numTable uses a hash function of key % 10 and quadratic probing with c1 = 1 and c2 = 2. Into which bucket is item 44 inserted?

HashInsert(numTable, item 1) HashInsert(numTable, item 12) HashInsert(numTable, item 23) HashInsert(numTable, item 34) HashInsert(numTable, item 44)

a. 5

b. 6

c. 7

d. 8

c

16) If (𝐻 + 𝑐1 ∗ 𝑖 + 𝑐2 ∗ 𝑖 ! )\bmod(𝑡𝑎𝑏𝑙𝑒𝑠𝑖𝑧𝑒) maps to an occupied bucket, then the item’s index (i) is incremented by _____.

a. 5

b. 1

c. 10

d. 2

b

17) Consider a hash table, a hash function of key % 10. Which of the following programmer-defined constants for quadratic probing cannot be used in a quadratic probing equation?

a. c1 = 1 and c2 = 0

b. c1 = 5 and c2 = 1

c. c1 = 1 and c2 = 5

d. c1 = 10 and c2 = 10

d

18) Given the following table, where a hash function returns key % 11 and quadratic probing is used with c1 = 1 and c2 = 1, which values can be inserted sequentially without collision? PICTURE NEEDED

a. 22, 33, 44

b. 23, 34, 45

c. 23, 35, 47

d. 22, 34, 45

c

19) Which XXX completes the quadratic probing search function?

PICTURE NEEDED

a. bucket = (Hash(key) + c1 * c2 + i * i * i) / N

b. bucket = (Hash(key) + c1 + i + c2 / i * i) / N

c. bucket = (Hash(key) + c1 / i + c2 / i * i) % N

d. bucket = (Hash(key) + c1 * i + c2 * i * i) % N

d

20) How many vertices are there in the graph? PICTURE NEEDED

a. 6

b. 7

c. 11

d. 12

b

21) How many edges are there in the graph? PICTURE NEEDED

a. 5

b. 7

c. 8

d. 10

b

22) Identify the shortest path between vertices B and D. PICTURE NEEDED

a. x6, x3, x7

b. x1, x5

c. x2, x3, x4

d. x7, x4

b

23) Identify the adjacent pair of vertices. PICTURE NEEDED

a. A and E

b. B and E

c. A and C

d. B and D

b

24) Which is a valid path between D and E? PICTURE NEEDED

a. x11, x12, x9

b. x6, x7, x12

c. x5, x1, x3

d. x9, x12, x10

d

25) In the following graph, which city is not directly connected to City 1? PICTURE NEEDED

a. City 5

b. City 2

c. City 7

d. City 6

c

26) What is the shortest time taken to travel between A and G? PICTURE NEEDED

a. 17 min

b. 14 min

c. 15 min

d. 16 min

b

27) Which cities are connected to City 6 directly? PICTURE NEEDED

a. City 4, City 7, and City 1

b. City 4, City 3, and City 2

c. City 5, City 7, and City 1

d. City 4, City 7, and City 2

a

28) How many different paths from A to F take 15 minutes? PICTURE NEEDED

a. 1

b. 2

c. 3

d. 4

c

29) Identify the vertices adjacent to C. PICTURE NEEDED

a. B and E

b. D

c. B, D, and E

d. A, B, and E

c

30) Which of the following best represents a sparse graph? PICTURE NEEDED

b

31) The following adjacency list represents the friendship between people. Identify the correct statement. PICTURE NEEDED

a. Harry is directly friends with Rody

b. Bob is directly friends with Hank

c. Hank can introduce Tim to Bob

d. Rita can introduce Bella to Tina

a

32) Which of the following is the size of an adjacency list graph representation? V refers to the number of vertices, E the number of edges.

a. O(V + E)

b. O(V - E)

c. O(V * E)

d. O(V * 2E)

a

a

34) Identify the vertices adjacent to C. PICTURE NEEDED

a. A and D

b. B and D

c. D and E

d. A and E

d

c

36) Identify the graph for the given adjacency matrix. PICTURE NEEDED

d

37) Identify the breadth-first search traversal from vertex C.

b

38) In which order might vertices be visited when doing a breadth-first search that starts at D? PICTURE NEEDED

a. B, F, G, H

b. B, H, G, F

c. B, H, F, G

d. F, B, H, G

b

39) If a breadth-first search starts at vertex E, the last vertex to be visited will be vertex _____. PICTURE NEEDED

a. A

b. B

c. C

d. D

d

40) Assuming that a breadth-first search starts at E, which vertices are in the frontierQueue after vertices E, G, and D have been visited? PICTURE NEEDED

a. E, G

b. A, C

c. A, C, G

d. A, C, E, G

b

41) Identify the DFS traversal of the graph if the starting vertex is B. PICTURE NEEDED

a. B, E, A, C, D

b. B, C, E, A, D

c. B, A, D, E, C

d. B, D, C, E, A

c

42) A DFS traversal starting from vertex C will visit _____ last. PICTURE NEEDED

a. vertex A

b. vertex C

c. either vertex A or vertex D

d. either vertexA, vertex B, or vertex E

d

43) Which statement would replace XXX in the given depth-first search traversal algorithm?

PICTURE NEEDED

a. Push adjV to stack

b. currentV = adjV

c. Pop adjV

d. Push adjV to visitedSet

a

44) Assuming A is the starting vertex for DFS and B is at the top of the stack after the first iteration of the while loop, which vertices are in the stack after the second iteration of the while loop? PICTURE NEEDED

a. A, E, C

b. A, C, D

c. A, C, E

d. A, D, E

b

45) Recursive DFS is run on the following graph. Assuming E is the starting vertex, which of the following is the call to the function? PICTURE NEEDED

a. RecursiveDFS(C)

b. RecursiveDFS(E)

c. RecursiveDFS(A)

d. RecursiveDFS(A, E)

b

46) Which array stores the following heap? PICTURE NEEDED

a. 9 6 7 5 4 3 1

b. 9 6 5 4 7 3 1

c. 1 3 4 5 6 7 9

d. 4 5 6 9 7 3 1

a

47) What are the parent and child indices for node 7 in the following max-heap? PICTURE NEEDED

a. Parent index: 1; child indices: 6, 7

b. Parent index: 0; child indices: 2, 3

c. Parent index: 0; child indices: 5, 6

d. Parent index: 0; child indices: 3, 4

c

48) Identify the correct definition of the MaxHeapPercolateUp() function.

a. MaxHeapPercolateUp(node, heapArray)

b. MaxHeapPercolateUp(node, Array)

c. MaxHeapPercolateUp(nodeIndex, heapArray)

d. MaxHeapPercolateUp(parentIndex, heapArray)

c

49) Which XXX would replace the missing statement in the given MaxHeapPrecolateDown() function?

PICTURE NEEDED

a. for (i = 0; i < 2 && i + childIndex > arraySize; i++)

b. for (i = 0; i < 2 && i + childIndex < arraySize; i++)

c. for (i = 0; i < 2 && i + childIndex > arraySize; i--)

d. for (i = 3; i > 2 && i + childIndex < arraySize; i--)

b

50) For a heap node with an index of 3 and a parent index of 1, identify the child node indices.

a. 1, 2

b. 0, 1

c. 5, 6

d. 7, 8

d

51) Identify the binary tree that satisfies the max-heap property. PICTURE NEEDED

c

52) Identify the binary tree that satisfies the min-heap property. PICTURE NEEDED

b

53) Identify the binary tree that satisfies the max-heap property. PICTURE NEEDED

a

54) Identify the new binary max-heap after inserting 60 in the following max-heap. PICTURE NEEDED

b

55) Identify the new priority queue after enqueueing 40.

26 36 42 54

a. 29 36 42 54 40

b. 40 29 36 42 54

c. 29 36 40 42 54

d. 29 36 42 40 54

c

56) Identify the number returned by the dequeue operation on the following priority queue.

21 36 45 54 60 73 90

a. 21

 b.  36

 c.  54

 d.  90

a

57) Identify the number returned by the peek operation on the following priority queue.

1 3 4 5 6 7 9
a.  9

b.  5

c.  7

d. 1

d

58) What is the worst-case runtime complexity of a peek operation on a priority queue?

a. 𝑂(𝑙𝑜𝑔𝑁)

b. 𝑂(1)

c. 𝑂(𝑁)

d. 𝑂(𝑁𝑙𝑜𝑔𝑁)

b

60) Is this an AVL tree? Justify your answer. PICTURE NEEDED

a. Yes, as the tree is a binary search tree (BST)

b. Yes, as both the left and right subtrees have height 0

c. No, as the tree is not a binary search tree (BST)

d. No, as both the left and right subtrees have height 0

c

61) Identify the AVL tree. PICTURE NEEDED

a

62) What is the minimum possible height of an AVL tree with the following nodes in order? 320, 470, 500, 540, 700, 650, 870

a. 1

b. 2

c. 3

d. 4

b

63) Identify the equation to calculate the balance factor, B, of an AVL tree node N.

a. 𝐵 = 𝑚𝑖𝑛(𝐻𝑒𝑖𝑔ℎ𝑡(𝑅𝑖𝑔ℎ𝑡𝑆𝑢𝑏𝑇𝑟𝑒𝑒(𝑁)), 𝐻𝑒𝑖𝑔ℎ𝑡(𝐿𝑒𝑓𝑡𝑆𝑢𝑏𝑇𝑟𝑒𝑒(𝑁)))

b. 𝐵 = 𝑚𝑎𝑥(𝐻𝑒𝑖𝑔ℎ𝑡(𝑅𝑖𝑔ℎ𝑡𝑆𝑢𝑏𝑇𝑟𝑒𝑒(𝑁)), 𝐻𝑒𝑖𝑔ℎ𝑡(𝐿𝑒𝑓𝑡𝑆𝑢𝑏𝑇𝑟𝑒𝑒(𝑁)))

c. 𝐵 = 𝐻𝑒𝑖𝑔ℎ𝑡(𝐿𝑒𝑓𝑡𝑆𝑢𝑏𝑇𝑟𝑒𝑒(𝑁)) + 𝐻𝑒𝑖𝑔ℎ𝑡(𝑅𝑖𝑔ℎ𝑡𝑆𝑢𝑏𝑇𝑟𝑒𝑒(𝑁))

d. 𝐵 = 𝐻𝑒𝑖𝑔ℎ𝑡(𝐿𝑒𝑓𝑡𝑆𝑢𝑏𝑇𝑟𝑒𝑒(𝑁)) − 𝐻𝑒𝑖𝑔ℎ𝑡(𝑅𝑖𝑔ℎ𝑡𝑆𝑢𝑏𝑇𝑟𝑒𝑒(𝑁))

d

64) Which is the worst-case height of AVL?

a. Less than or equal to 1.5 times compared to minimum binary tree height

b. Greater than or equal to 1.5 times compared to minimum binary tree height

c. Less than or equal to 1.5 times compared to maximum binary tree height

d. Greater than or equal to 1.5 times compared to maximum binary tree height

a

65) Which is not a valid AVL tree due to being unbalanced? PICTURE NEEDED

a

66) Identify the correct rotation to maintain the height balance of the AVL tree. PICTURE NEEDED

c

67) Identify the correct rotation to maintain the height balance of the AVL tree. PICTURE NEEDED

a

68) Which XXX would replace the missing statement in the following algorithm for updating the height of an AVL tree? PICTURE NEEDED

a. node⇢height = max(leftHeight, rightHeight) + 2

b. node⇢height = max(leftHeight, rightHeight) + 1

c. node⇢height = max(leftHeight, rightHeight)

d. node⇢height = max(leftHeight, rightHeight) – 1

b

69) Which XXX will complete the following partial algorithm for the right rotation of an AVL tree. PICTURE NEEDED

a. AVLTreeSetChild(node⇢right, "right", node) AVLTreeSetChild(node, "right", leftRightChild)

b. AVLTreeSetChild(node⇢left, "left", node) AVLTreeSetChild(node, "right", leftRightChild)

c. AVLTreeSetChild(node⇢root, "right", node) AVLTreeSetChild(node⇢right, "right", leftRightChild)

d. AVLTreeSetChild(node⇢left, "right", node) AVLTreeSetChild(node, "left", leftRightChild)

d

70) Identify the correct rotation to rebalance the given tree after the new node is inserted. PICTURE NEEDED

a

71) Identify the balanced tree when 5, 7, 9, 11 are inserted in sequence to the given tree. PICTURE NEEDED

c

73) Which XXX would replace the missing statement in the algorithm for inserting a new node in an empty AVL tree?

PICTURE NEEDED

a. if (node⇢left == null)

b. if (tree⇢root == null)

c. if (node⇢left != null)

d. if (tree⇢root != null)

b

74) Which statement is true about the insertion of a new node in an AVL tree?

a. AVLTreeInsert updates heights on all child nodes before inserting the node

b. AVLTreeInsert updates heights on all child nodes after inserting the node

c. AVLTreeInsert updates heights on all ancestors before inserting the node

d. AVLTreeInsert updates heights on all ancestors after inserting the node

d

75) Identify the rebalanced AVL tree after removing 60. PICTURE NEEDED

d

77) Identify the rebalanced AVL tree after the following operations: AVLTreeRemoveKey(tree, 20) AVLTreeRemoveKey(tree, 41) AVLTreeRemoveKey(tree, 67)

PICTURE NEEDED

a

79) In the AVLTreeRemoveNode algorithm, identify the correct statements that check and remove the root node with 1 or 0 children. PICTURE NEEDED

d

80) Identify which nodes are printed first and last. PICTURE NEEDED

a. F and D

b. F and C

c. F and A

d. F and S

a

81) Which XXX completes the BST in order traversal algorithm?

a. BSTPrintInorder(node)

b. BSTPrintInorder(node⇢left)

c. BSTPrintInorder(node⇢right)

d. BSTPrintInorder(null)

b

83) What happens when a leaf node is removed?

a. The root node becomes null

b. The parent node becomes null

c. The parent’s left or right child node becomes null

d. The internal node becomes null

c

84) What is the tree when node 4 is removed? PICTURE NEEDED

b

85) What is the tree when node 300 is removed? PICTURE NEEDED

c

87) Where will a new node with key 5 be inserted into the following BST?

a. As 2's right child

b. As 4’s left child

c. As 4's right child

d. As 7’s left child

c

88) If a new node with key 50 is inserted into the following BST, what sequence of nodes is visited and where is the new node inserted?

a. 40, as 40's right child

b. 40 ⇢ 80 ⇢ 70, as 70’s right child

c. 40 ⇢ 80 ⇢ 70 ⇢ 60, as 60’s left child

d. 40 ⇢ 80 ⇢ 70 ⇢ 60, as 60’s right child

c

89) The space complexity of a BST insertion algorithm is _____.

a. 𝑂(𝑁)

b. 𝑂(log 𝑁)

c. 𝑂(log ! 𝑁)

d. 𝑂(1)

d

90) Which XXX completes the BST search algorithm? PICTURE NEEDED

a. if (key < cur⇢key)

b. if (key > cur⇢key)

c. if (key < cur⇢left⇢key)

d. if (key > cur⇢right⇢key)

a

91) What is the second node that is visited when searching for 7? PICTURE NEEDED

a. 5

b. 7

c. 10

d. 15

a

93) If search key = 60, identify the sequence of nodes that are visited and the outcome.

a. 100 ⇢ 70 ⇢ 60 ⇢ 60

b. 100 ⇢ 70 ⇢ 60

c. 100 ⇢ 70 ⇢ 60⇢ 60⇢ null

d. 100 ⇢ 70 ⇢ null

b

94) What is the maximum number of loop iterations when searching for “S” in the BST below? PICTURE NEEDED

a. 6

b. 5

c. 4

d. 3

c

95) Which of the following is a valid binary search tree?

PICTURE NEEDED

a

97) Identify the sequence of nodes that are visited to search for 150.

PICTURE NEEDED

a. 250, 200, 190

b. 250, 200, 190, 210

c. 200, 190

d. 190, 210, 290, 310

a

98) What is the largest number of comparisons for searching the following BST? PICTURE NEEDED

a. 5

b. 4

c. 3

d. 1

b

99) What is the sequence of ordering for the nodes of the following BST? PICTURE NEEDED

a. 190 ⇢ 210 ⇢ 200 ⇢ 250 ⇢ 300 ⇢ 290 ⇢ 310

b. 190 ⇢ 210 ⇢ 290 ⇢ 310 ⇢ 200 ⇢ 300 ⇢ 250

c. 250 ⇢ 200 ⇢ 300 ⇢ 190 ⇢ 210 ⇢ 290 ⇢ 310

d. 190 ⇢ 200 ⇢ 210 ⇢ 250 ⇢ 290 ⇢ 300 ⇢310

d

100) What is the parent of the “Theory.doc” node? PICTURE NEEDED

a. Science

b. Mark

c. Students

d. Tom

a

101) What is the depth of the “Practical.jpg” node? PICTURE NEEDED

a. 1

b. 2

c. 3

d. 4

c

102) What type of node is “English”? PICTURE NEEDED

a. Root

b. Parent

c. Internal node

d. Leaf

d

103) In a tree representing a file system, _____.

a. leaf nodes represent only empty directories

b. leaf nodes represent only non-empty directories

c. leaf nodes represent either files or empty directories

d. leaf nodes represent only files

c

104) Identify the correct statement about binary space partitioning.

a. Regions are always split down the middle either horizontal or vertical.

b. Half the objects are eliminated each level while traversing down a BSP tree.

c. BSP tree can be used to store all objects in a two-dimensional world.

d. In animation only one region is analyzed at a time.

c

105) Which is an internal node? PICTURE NEEDED

a. X

b. Y

c. P

d. Q

a

106) Identify the ancestor(s) of node P. PICTURE NEEDED

a. X

b. X, A

c. X, Y

d. X, Y, A

b

107) Identify the depth of node Q. PICTURE NEEDED

a. 0

b. 1

c. 2

d. 3

c

108) Identify the type of the following binary tree. PICTURE NEEDED

a. Not full, complete, not perfect

b. Full, not complete, not perfect

c. Full, complete, not perfect

d. Full, complete, perfect

b

109) Identify the type of the following binary tree. PICTURE NEEDED

a. Not full, complete, not perfect

b. Full, not complete, not perfect

c. Full, complete, not perfect

d. Full, complete, perfect

d