DSA Exam 2023 with verified questions and answers

Describe what a reference variable is in C++ accurately in your own words an alias of another variable, which must be initialized when declared, cannot be changed to refer to another variable, and has the same memory address as the original variable. Describe what a pointer is in C++ accurately in your own words A pointer is a variable that contains the memory address of another object or variable, which may be reassigned to another object of the same type or be assigned to NULL. Describe the differences between static and dynamic memory in a C++ runtime environment. Static memory is allocated at compile time, it is assigned to the stack automatically deallocated when an object is out of scope. Dynamic memory is allocated at run time, assigned to heap, goes beyond scope. Describe a dangling pointer in your own words accurately A dangling pointer is a pointer that once referenced a dynamic memory object that has since been deallocated using the delete operator. Describe how a memory leak can occur in a C++ program. A memory leak can occur when a pointer referencing a dynamically allocated object is reassigned to reference another object. Describe in your own words accurately a singly linked list. Distinguish a singly linked list from a doubly linked list. a linear data structure comprised of nodes encapsulating one or more data members and chained together using node pointers connecting one node to the next. A doubly linked list contains a second linking member for each node that points to the previous node. Describe the process of adding a new node to the head of a singly linked list. Use this to state and justify its worst-case time complexity In order to add a new node to the head of a singly linked list, the new node's next pointer should be assigned to the head of the linked list. Then the head pointer can be updated to be the new node. This constant number of operations leads to a worst-case time complexity of O(1). Discuss the advantages and disadvantages of dynamic arrays and linked lists in terms of access, insertion, and deletion Access - arrays are better, allow random access in constant time. Linked lists require sequential access. Insertion - linked lists are better, insertion at head/tail may be done in constant time. Copy over all the data. Deletion - they are very similar. Describe the queue data structure with its operations of enqueue and dequeue in your own words accurately A queue data structure is a linear data structure that implements the First-In-FirstOut (FIFO) principle. A new data element is added to the queue at the rear using the enqueue operation and a data element may be removed from the queue from the front using the dequeue operation. Describe how a (fixed size) circular queue may be implemented with constant run-time enqueue and dequeue operations on a static array of size n A circular queue may be implemented on a static array of size n by keeping track of the front and rear indexes. An empty queue may be encoded by the condition that the front and rear indexes are equal, and a full queue may be encoded by the condition that the front is one more than the rear, modulo n (meaning either front = rear + 1 if 0 front n, or front = 0 when rear = n-1). This allows a capacity of n-1 for the queue. Enqueueing is done when the queue is not full by adding the data element at the rear and then incrementing the rear index modulo n Describe the structure of a binary search tree ( A binary search tree (BST) is a nonlinear data structure comprised of nodes, each encapsulating data members, including an ordering identifier (often called the key), and linking members for left child and right child (and sometimes parent if a bidirectional tree is desired). A BST is a tree, where the data nodes are the vertices and the links are the edges. A node pointer called root references the only node with no parent Describe the process of adding a new node to a BST. Use this to state and justify its worst-case time complexity The key of the new node to be added is compared recursively to each existing node's key, starting with the root node, and progresses to the left child if the key of the new node is less than (or equal) to the existing node's key or progresses to the right child if the key of the new node is greater than the existing node's key. Describe an algorithm for finding the minimum key in a BST. Use this to state and justify its best-case and worst-case time complexity. Assuming a nonempty BST, a node pointer (current) may be used and initially be set to the root. The key of the root may be assigned as the min and a while loop may be set up that terminates when the left child of current is NULL such that inside the loop the min is updated as the current node's key and then current is updated to be its left child. Upon termination of the while loop the min variable is the minimum key of the BST. This algorithm in worst-case traverses the longest path from root to leaf node, so has a worst-case run time of O(h), where h is the height of the BST. Describe the difference between breadth-first and depth-first traversal of a binary tree Breadth-first traversal of a tree involves visiting the nodes of the tree layer by layer, and typically left to right. It is easiest to implement using a queue of node pointers. Depth-first traversal of a tree involves visiting nodes along a path from root to leaf node (typically visiting left children first) and recursively backtracking to visit the other child of each node once leaf nodes are encountered. Describe the differences between pre-order, in-order, and post-order traversal of a BST All of these traversal methods are depth-first, but differ by the order in which the node is processed (aka visited). For pre-order traversal, the node is visited first, and then its left child and finally its right child. For in-order traversal, first the left child is visited, then the node itself, and finally its right child. For post-order traversal, first the left child is visited, then the right child and lastly the node itself. For a BST, in-order traversal of the keys will process them in sorted order. Describe the three main cases of deleting a node from a BST The three cases are: (1) the node is a leaf node, (2) the node has one child, and (3) the node has two children. In case 1, the parent node may have the child pointer associated with the node to be deleted set to NULL and the node may simply be deleted. In case 2, the node should be replaced with its child, so the child's parent link should be set to match the node's parent link, and the associated child link of the parent should be updated to point to the child. Then the node may be deleted. In case 3, there are two subcases: (a) The successor is the right child of the node, or (b) it is not. In case 3a, the right child may replace the node. Since it is the successor, it will not have a left child, so its left child may be set to point to the left child of the node to be deleted. The parent link of the successor may be set to be the parent of the node to be deleted, and the parent's associated child link may be updated to point to the successor. Then the node may be deleted. In case 3b, the successor should first be replaced with its right child