Data Structures and Algorithms Online Test

You're designing an undo system for a text editor and need to choose a data structure to record user actions. Each action should be recorded so that the system can quickly reverse recent actions. The system has the following requirements:

• Every new user action must be recorded (for example, typing a character or deleting a line).
• The “undo” must retrieve and remove the most recent action in constant time O(1).

Your colleagues proposed using Stack or Queue based on the requirements. Write a short explanation on how the functionality of either data structure can or cannot fulfill the requirements.

(An answer up to 50 words is sufficient)

The function below is used to search for an element in a binary tree that contains linked nodes.

function treeContains(treeNode : Node, element : int) : bool
  if (treeNode == NULL)
    return false
  else if (treeNode.getValue() == element)
    return true
  else 
    left : bool = treeContains(treeNode.getLeft(), element)
    right : bool = treeContains(treeNode.getRight(), element) 
    return left || right 
  end if
end function

What can be said about the treeContains function?

The following pseudocode functions will be used for managing student data using a Hashtable:

function addStudent(table : Hashtable, id : int, name : string) : void
  table.add(id, name)
end function

function findStudentIdByName(table : Hashtable, name : string) : int?
  loop (for each entry in table)
    if entry.value == name
      return entry.key
    end if
  end loop

  return null
end function

What can be correctly said about the pseudocode?

Answer the questions below regarding correct usage of data structures.

For the following pseudocode functions, choose the big O notation that accurately describes its worst-case complexity.