DSA exam 2023 with complete solution questions and answers

pointer allocation type dynamic - must clean up afterwards arrow operator - - access members of object points to - same as dereferencing an object then using . operator array - contiguous memory - homogenous (one type) - static memory allocation stack - LIFO (undo mechanism) - push to top - pop from top - peek - if it does not contain enough space to add a new item, it overflows linked list - collection of nodes - linear ordering - contains pointer to next node - dynamic allocation double linked list - linked list - contains a pointer to next node and previous node queue - FIFO - enqueue on back - dequeue from front - peek circular queue 3 pointers: 1. to memory buffer 2. start of valid memory 3. end of valid memory bubble sort - bubbles largest to top - compares adjacent values, swaps - easy to implement, slower - good for small sets - uses a nested loops - looks at one less element each time insertion sort - leaves a sorted list as it passes - compares value with all previous values - inserts it into correct spot (rest slide down one) - only sorts if NECESSARY selection sort - finds min element - places it in right spot by SWAPPING - does not look at that element again merge sort - divide: into 2 parts until it cannot - recur: solve each subset by dividing it - conquer: merge them back together in order, 1 layer at a time quick sort - choose pivot - divide: into L, E, G than pivot - recur: keep dividing L and G - conquer: put back by inserting L, E, then G division hash number % size of set boundary folding hash - key is divided into several parts - key is folded on borders of a paper - every other part is put into reverse order = 123 + 456 + 789 sum = key shift folding hash - key is divided into several parts - put underneath one another 0= 123 + 654 + 789 sum = key mid-square hash squares the key, the middle portion is the key extraction hash part of key is used as key ex. first and last 2 nums radix hash - key is transformed into another base number - need additional computation map - key value pairs - key must be unique - elements can be located quickly dictonary - key value pairs (entries) - keys don't need to be unique (multiple definitions for one word) set - collection of distinct objects - all unique objects - automatically sorted in insertion multi-set set that can have duplicate elements length number of edges in a path level length of path + 1 height max level of a node in the tree - empty tree = 0 - single node = 1 AVL tree - height balanced binary tree - difference in height of left and right subtree must be = 1 for all nodes (same height or +1 difference) red-black tree - self-balanced binary tree - red = both children are black - black = leaves N-ary tree - each node cannot have more than N children in-order traversal left, root, right post-order traversal left, right, root pre-order traversal root, left, right graph way of representing relationships that exist between pairs of objects - set of nodes and a collection of pairs of vertices (edges) Verticies in graphs represent objects or states, positions, or are placeholders edge in a graph - pairs of vertices directed vs undirected graph undirected: { u, v } - pair is unorders - can go both ways directed: ( u, v ) - pair is ordered - goes -- direction - each node has a unique path from root with: - initial node: path indicates - terminal node: path terminates traversing a graph - cannot use tree traversal (would result in infinite loops) - each node is marked as visited to avoid revisiting - graphs can have isolated nodes depth first traversal - goes to deepest point (end of path) from root - then visits parent's other child - if no adjacent nodes or all have been visited, it backtracks to parent - finishes when backtracking leads to root - edges are pushed to STACK - pop vertex, visit it breadth-first traversal - level by level - goes to next level once all are visited - uses a QUEUE