CP264 MOCK FINAL

Struct DATA Size

• Given the struct DATA with a char array name[20] and a float marks, the sizeof(struct DATA) is 24.

Queue and Stack Implementation

• Both arrays and linked lists are suitable for implementing queue and stack data structures.

Efficient Random Access

• An array is a more efficient data structure for random access compared to linked lists, BST, and AVL trees.

Height Balanced Binary Tree Height

• The height of a height-balanced binary tree with n nodes is represented as O(log n).

BST Space Complexity

• The space complexity for search, insert, and delete operations on a Binary Search Tree (BST) with n nodes is O(h), where h is the height of the tree. This can be O(log n) in balanced trees or O(n) in skewed trees.

AVL Tree Time Complexity

• The time complexity for search, insert, and delete operations on an AVL tree with n nodes is O(log n).

Splay Tree Access Time

• For a splay tree, the time complexity of accessing the last inserted node is O(log n).

Binary Min-Heap Operation at O(1)

• The find min operation has a time complexity of O(1) on a binary min-heap.

Hash Table Search Time

• Assuming no collisions occur during hash table insertions, searching by key can be done in O(1) time.

Efficient Graph Representation

• An adjacency list is a more space-efficient graph representation for large, sparse graphs.

AVL Tree Construction

• An AVL tree can be built by inserting key values in a specific order, such as 5, 3, 4, 2, 1, and rebalancing the tree through rotations as needed. Refer to the original document for a visual depiction of this process.

Binary Tree Traversal

• To solve #1 pre-order, #2 in-order, and #3 post-order of the tree nodes requires performing said traversals of the binary tree. These algorithms visit nodes in a specific order. Review the original document for the a visual depiction of a binary tree.

Binary Min-Heap Insertion

• Inserting key values (e.g., 4, 3, 2, 1) into a binary min-heap involves adding the key to the heap and then heapifying to maintain the min-heap property. Review the original document for the a visual depiction of steps to build the heap.

Linked List Insertion Function

• A C function insert_end(NODE **startp, int num) can be written to insert a new node with value num at the end of a linked list. The list is accessed via a pointer startp to the first element.

Binary Tree Info Structure

• A structure type TREEINFO along with a function treeinfo(TNODE *roto) can be designed to compute and return the height and number of leaves of a binary tree. Root is passed as an argument. The implementation should use a single recursive function.

Binary Tree Breadth-First Search Function

• A C function TNODE *breadth_first_search(TNODE *root, int key) can be implemented to search a binary tree in breadth-first order for a node with a specific key. The function returns the node's address if found, otherwise NULL.

Heap Sort Function

• A C function void heap_sort(int a[], n) can sort an integer array a[] of n elements in decreasing order using heap sort. The function's implementation should include heapify-up/heapify-down operations within the function.