CSCA48 Final Exam
Fall 2020
PART 2
Consider a binary search tree where each node, in addition to its normal fields, also
contains a pointer to its parent node.
typedef struct BSTNode {
int data;
struct BSTNode* parent;
struct BSTNode* left;
struct BSTNode* right;
} BSTNode;
Write the following recursive functions:
insert(BSTNode *root, int x) insert x into the BST rooted at root
delete(BSTNode *root, int x) delete one occurrence of x from the BST rooted at root
Question #4 (15 marks)
What is the Big-O complexity of the following algorithm run on a graph
implemented as:
A) an adjacency list
B) an adjacency matrix
Explain your answers. Clearly state any assumptions you make.
1: start with an empty graph G
2: loop N times:
3: insert a new node
4: if ( G has at least 2 nodes):
5: insert a new edge between two random nodes
6: pick 2 random nodes X and Y
7: if ( X and Y are connected ):
8: remove all edges to and from X
9: remove X from the graph
Question #5 (10 marks)
In one sentence (no more than 50 words) each, explain the following terms:
? Dependency
? API
? Method Overloading
? Information Hiding
? Inheritance
Question #6 (5 marks)