Data Structures & Algorithms Mid Term Exam Questions with Answers

Data Structures & Algorithms Mid Term Exam Questions with Answers Array - Correct Answers: a fixed length collection that holds elements of similar types Array access elements by _______ - Correct Answers: index Array elements are stored ________ in memory - Correct Answers: sequentially Elements are ________ at the left-most empty index - Correct Answers: inserted Locating values in an unordered array requires a ___________________. - Correct Answers: sequential search Deleting unordered arrays 1. ______, 2. _____, 3. ________ - Correct Answers: search, remove, shift Ordered Arrays - Correct Answers: same structure as unordered, but elements are sorted in natural order Unordered array search - Correct Answers: search sequentially left to right Linear search - Correct Answers: accessing elements by index Ordered array search - Correct Answers: linear search, binary search Binary search - Correct Answers: split into halves, decide whether target is higher or lower, repeat cutting Binary vs Linear - Correct Answers: Binary more efficient depending on array size Big O Notation - Correct Answers: shorthand for an algorithm's complexity, or how it responds to changes to the size of its inputs Big O Linear - Correct Answers: O(n) Big O Binary - Correct Answers: O(log(n)) Bubble sort - Correct Answers: beginning at left, compares to object to the right, swap if left is greater than right, repeat. start again at value lower than first value Bubble sort peformance - Correct Answers: O(N^2) aka slow Selection sort - Correct Answers: start at left, find lowest value, move it to position 0, repeat process after moving one to the right Selection sort performance - Correct Answers: = bubble, but less N Insertion sort performance - Correct Answers: fastest & most complex Insertion Sort - Correct Answers: Select left-most unsorted, temp remove, start at i-1 moving left, compare removed to next element, if smaller, shift item in array right once. repeat until smaller element encountered, or position 0 reached. removed element is then inserted Invariants - Correct Answers: Conditions that remain unchanged as an algorithm proceeds Abstract data structure - Correct Answers: Ex: stacks & queues Concrete data structure - Correct Answers: Arrays (due to specific implementation) Stacks - Correct Answers: collection of elements that only allows access to the last element added Queues - Correct Answers: a sequential collection of items with first in first out retrieval Circular Queue - Correct Answers: same as queues, but wraps around Deque - Correct Answers: elements may be added and removed from either end Priority Queues - Correct Answers: abstract type similar to queue, but elements are assigned a priority How does a linked list work? - Correct Answers: An item that has a reference to the next link Linked list components - Correct Answers: insertFirst, deleteFirst, displayLink Double-ended lists - Correct Answers: same as linked list, but has both first and last fields Linked List Performance - Correct Answers: insertion/deleting @ beginning: O(1). Search, delete, insert, next to specific item: O(N) Doubly linked list - Correct Answers: Links have references to previous and next links Data type - Correct Answers: Referred to primitive types, now you can create your own data types (classes) Abstraction - Correct Answers: considered apart from detailed specification or implementation ADT Lists/Linear List - Correct Answers: group of items arranged in a linear order Sorted List - Correct Answers: Items arranged in sorted order by key value Solving a recursive problem - Correct Answers: Use the solution of the same problem with progressively simpler values Divide and conquer algorithm - Correct Answers: Two sorted arrays, merge into final array (mergesort) Mergesort Efficiency - Correct Answers: n = 8 .File class - Correct Answers: abstract representation of a file or folder Scanner class - Correct Answers: used in reading a file Constructing a file object - Correct Answers: File myFile = new File(""); Text format - Correct Answers: human readable data representation as a sequence of characters Binary Format - Correct Answers: machine-readable data representation as a sequence of bytes