Data Structures Exam I Questions with Answers

Data Structures Exam I Questions with Answers Data Structures - Correct Answers: an arrangement of data in the computer's memory (or on a disk) Examples of Data Structures (9) - Correct Answers: arrays, linked lists, stacks, queues, binary trees, hash tables, red black trees, 2-3-4 trees, heaps, etc. T/F? Primitive variables are data structures - Correct Answers: FALSE Examples of primitive data types (9) - Correct Answers: char, byte, short, int, long, float, double, boolean, void Algorithms - Correct Answers: Sequences of steps used to manipulate the data in data structures in various ways. They are implemented by using program instructions. (so these are basically the things that happen during a program). Examples of algorithms (3) - Correct Answers: Build/create the data structure, add/remove data, search/manipulate the data T/F? One algorithm can build/create the data structure, add/remove data, and search/manipulate data - Correct Answers: FALSE; different algorithms are needed to carry out these tasks in data structures Fill in the blank: Many items in nature have a ______ ________ with their predecessor/successor (one before/one next) element. - Correct Answers: Natural Arrangement T/F? Data can be arranged/organized based on many different attributes. - Correct Answers: True What are attributes that data can be arranged by? (7) - Correct Answers: Age, size, non-ordinal (array), numeric/alphabetical order (sorted arrray), time order (stacks/queues), tree (like family tree), graphs What data structure can best represent a sequence of numbers? - Correct Answers: An array What if you need to search an array? - Correct Answers: 1. If the array is ordered/sorted and is large enough, use a binary search. 2. If the array is unordered/unsorted then sequential search is the only option. What data structure can best represent a family? - Correct Answers: A tree Advantages of an array (2) - Correct Answers: 1. Quick insertion 2. Very fast access if index of element is known Disadvantages of an array (3) - Correct Answers: 1. Slow search 2. Slow deletion 3. Fixed size Advantages of an ordered array (1) - Correct Answers: 1. Same as a normal array but it is a quicker search than an unsorted array Disadvantages of an ordered array (3) - Correct Answers: Same as array only difference is not a slow search but slow insertion. 1. Slow insertion 2. Slow deletion 3. Fixed size Advantages of a stack (1) - Correct Answers: Provides a last-in, first-out access Disadvantages of a stack (1) - Correct Answers: Slow access to other items (bc you have to take everything off in order to get to that one- like a pile of papers) Advantages of a queue (1) - Correct Answers: Provides a first-in, first-out access Disadvantages of a queue (1) - Correct Answers: Slow access to other items (you gotta go in line, turn by turn) Advantages of a linked list (2) - Correct Answers: 1. Quick insertion 2. Quick deletion Disadvantages of a linked list (1) - Correct Answers: Slow search Advantages of a binary tree (3) - Correct Answers: 1. Quick search 2. Quick insertion 3. Quick deletion (if tree remains balanced) Disadvantages of a binary tree (1) - Correct Answers: Deletion algorithm is complex/hard Advantages of red-black tree (4) - Correct Answers: 1. Quick search 2. Quick insertion 3. Quick deletion 4. Tree always balanced Disadvantages of red-black tree (1) - Correct Answers: COMPLEX. Advantages of 2-3-4 tree (5) - Correct Answers: 1. Quick search 2. Quick insertion 3. Quick deletion 4. Tree always balanced 5. Similar trees good for disk storage Disadvantages of 2-3-4 tree (1) - Correct Answers: COMPLEX. Advantages of a hash table (2) - Correct Answers: 1. Very fast access if key known 2. Fast insertion Disadvantages of a hash table (3) - Correct Answers: 1. Slow deletion 2. Access slow if key not known 3. Inefficient memory usage. Advantages of Heap (3) - Correct Answers: 1. Fast insertion 2. Fast deletion 3. Access to largest item Disadvantages of heap (1) - Correct Answers: Slow access to other items Advantages of a graph (1) - Correct Answers: Models real-world situations Disadvantages of a graph (1) - Correct Answers: Some algorithms are slow and complex. Database - Correct Answers: A structures set of related data. Fill in the blank: Each item in a database has a ____ format. - Correct Answers: Similar Example/analogy for a database - Correct Answers: Creating an address book using index cards. The cards make up a database. Sometimes called a file. Record - Correct Answers: The units into which a database is divided. They provide a format for storing the information. One record includes all the information about some entity. Use the analogy of a database and explain it further with a record - Correct Answers: Each index card would represent one record. So one index card holds all the information (name, address, phone number, etc.) about ONE person. The records collectively create the full address book (the database). Field - Correct Answers: A record is divided into several of these. These hold a particular kind of data Explain analogy with a field - Correct Answers: One field would be the name of a person. A person's telephone number would represent a different field. But this is a field for that ONE PERSON/RECORD. Not all of them. Key - Correct Answers: AKA search key. You designate one of these to search for a RECORD in a database. Analogy with Key - Correct Answers: You set the key to a student's N number so it will quickly pull up that student. Bdays and names are harder to use as keys because two people can have the same name or bday so it should be unique. Fill in the blank: In java, records are usually represented by _____ of a class. - Correct Answers: Objects Fill in the blank: Individual variables within an object represent data ______. - Correct Answers: Fields Fill in the blank: Fields within a class object are called ____ in Java but _____ in other languages like C++ - Correct Answers: fields; members Fill in the blank: The _________ paradigm allows easier modeling of the real world by combining data related to things and tasks associated with the things - Correct Answers: OO (object oriented) *Meaning from OOP Object Oriented Programming - Correct Answers: Inheritance, polymorphism, encapsulation, and abstraction Fill in the blank: A(n) _______ is a procedure for carrying out a particular task - Correct Answers: Algorithm Fill in the blank: An algorithm is usually implemented by a ____ _____. - Correct Answers: Class method Fill in the blank: A ____ is a unit of data storage composed of many similar records - Correct Answers: Database What is the most common data structure? - Correct Answers: An array T/F? An array can contain primitive data types - Correct Answers: True T/F? An array can contain object references? - Correct Answers: True T/F? Items in an array can be of different data types - Correct Answers: FALSE; they have to be of the same data type T/F? Items in an array are indexed using a simple index starting at 1. - Correct Answers: False; index starts at 0. What does an array object contain? - Correct Answers: The array list and one public instance variable What is an array length? - Correct Answers: The defined number of element locations in the array, NOT the number of items stored in the array T/F? Length is FINAL and cannot be changed - Correct Answers: True T/F? An entire array has one single name and each value has a numeric index - Correct Answers: True Fill in the blank: An array of size N is indexed from zero to ______ - Correct Answers: N-1 How do you declare an array explicitly? - Correct Answers: int [] array= new int [10]; Base_type[] array_name= NEW base_type[length]; Declare an array implicitly? - Correct Answers: int [] array= {1, 2, 3, 4, 5}; T/F? An array of objects is really an array of object references. - Correct Answers: TRUE T/F? Arrays are pre-initialized to zero or null objects - Correct Answers: TRUE T/F? Arrays can be intialized when declared/defined - Correct Answers: True int []array= {2, 3, 4}; Can you create an array of strings? - Correct Answers: YES: String [] array= {"run", "work", "play"}; Can you create an array of objects? - Correct Answers: YES: State [] myState= {new State(1), new State(2), new State(3)}; How do you insert an item in an unsorted array? - Correct Answers: Put the value in the next available space and increment the count of items in the array How do you insert an item in a sorted array? - Correct Answers: 1. Find the location that the new items goes (where it fits in the sorted items) 2. move the values in the array to make space 3. insert the value 4. increment the count of items in the array. How to delete an item in an array? - Correct Answers: 1. Find the element you want to delete 2. Move all the remaining elements up one position 3. Decrease the count How do you print out all the elements in an array? - Correct Answers: for (j=0; j<h-1; j++) { S(array[j]); Sln(""); } How do you find an element in an array? (hint: use a key) - Correct Answers: int searchKey=66; for (j=0; j<h-1; j++){ if (array[j]==searchKey){ Sln("Found item"); } else if (j==h-1) { Sln("Can't find" + searchKey); } How to delete item with key 55? - Correct Answers: int searchKey=55; count=10; for (j=0; j<h-1; j++){ if (array[j]== searchKey){ break; } for (int k=j; k<h-1; k++){ array[k]=array[k+1]; count--; T/F? It is good to separate the data from the user (clients) - Correct Answers: True T/F? It is good to keep data private so only certain methods have access to the data - Correct Answers: True T/f? it is good to not require clients to use objects - Correct Answers: False; it's good to require other clients to use objects T/f? It is good to make sure your classes have clearly define roles - Correct Answers: True Linear/Sequential searches - Correct Answers: Start at the first element, look at each element until the desired element is found or the end is reached. If the data is unsorted, you have to do a sequential search. -So you have to look at half of the elements ON AVERAGE to find the element you want if it's even there. If the data is sorted in an array what search can you perform? - Correct Answers: Binary search. You can still do a linear search if you want but binary is better. Binary Search - Correct Answers: Assumes the list of items in the search pool is SORTED -it first compares the middle element of the array with the target Example of binary search code - Correct Answers: a[middle] is the index of the middle element of the array *since it cuts the data in half to search: if (a[middle]==target){ return middle; } else if (a[middle]>target){ //go to LOWER half and look for target there } else if (a[middle]<target){ //go to UPPER half and look for target there } This keeps happening if the target wasn't met. So if you have to look in the lower half then you take the middle value of the lower half and compare it to the target, and then cut it in half again if not found, etc. So you don't look at the rest of the items like the ones in the upper half, just search within the possible ones left. Look at slide 26 in chapter 2 ppt for code. Fill in the blank: Each comparison in a binary search eliminates approximately ____ of the remaining data. - Correct Answers: Half Fill in the blank: ____ is expensive. - Correct Answers: Sorting What are the two disadvantages of an ordered array and why? - Correct Answers: Insertion and deletion are expensive. 1. Insertion you have to find the spot to insert, and then if a new items belongs in a lower position of array, movement of data items to insert in place can be horrific. 2. Deletion (bad in ordered and unordered arrays) because first it's found and then the remaining elements have to be moved up to cover the deleted element's location. T/F? If an array is large and ordered then search times are much faster than with linear searches. - Correct Answers: True bc you can use binary search T/F? If a company has to search alot and the data is large, then it is good to use an ordered array - Correct Answers: True; it saves a lot of time so you can do binary search Comparisons in sequential search vs. binary search - Correct Answers: 1. Sequential uses simple logic and more calculations. ex. for an array size of 1024, the worst can is that we need 1024 comparisons 2. Binary searches look at much fewer items. ex. for an array size of 1024, the max number of comparisons needed is 11 (since data is cut in half each time). But the data had to be sorted before this is applied. Look at slide 30 in ch2 ppt. How do you find the average number/maximum number of comparisons for a sequential search - Correct Answers: It would be half the size. ex. table size 100 so the average number of comparisons would be 50. Maximum number is the size of it so it would be 100 in that example. T/F? When comparing two strings in an array using == - Correct Answers: False, use the EQUALS method, not == Big O Notation - Correct Answers: Characterizes the efficiency of algorithms Big O notation for Linear search times (T) - Correct Answers: N (the number of elements) * a constant K T=K*N Big O notation for binary search times - Correct Answers: log2(N) T=K*log2(N) or K*log(N) T/F? We can always say something like algorithm A is twice as fast as algorithm B - Correct Answers: False; performance depends on many factors not just number of items or order. Sometimes it depends on the degree of unsortedness. What is the factor most significant in determining overall performance of an algorithm? - Correct Answers: Size!! Fill in the blank: Big O notation is read "___ ___" and is used to indicate ____ _____. - Correct Answers: Order of; relative efficiencies Linear Search Big O notation - Correct Answers: O(N) *read Order N search Which means that search time is directly proportional to the number of elements searched Binary Search Big O notation - Correct Answers: O (log2N) search *read order log base 2 N search Means that search time is proportional to log base 2 N Insertion unordered array (immediate) Big O notation - Correct Answers: O(1) Insertion in ordered array Big O notation - Correct Answers: O(N) Deletion in unordered array Big o notation - Correct Answers: O(N) Deletion in ordered array Big O notation - Correct Answers: O(N) T/F? Arrays in java are objects, created with the new operator - Correct Answers: True T/F? Unordered arrays offer fast insertion but slow searching and deletion - Correct Answers: True T/F? Wrapping an array in a class protects the array from being inadvertently altered - Correct Answers: True T/F? A class interface makes it harder for the class user - Correct Answers: False; it can make it easier for the class user T/F? A binary search can be applied to an unordered array - Correct Answers: False T/F? Binary searches require time proportional to the logarithm of the number of items - Correct Answers: True T/F? Linear searches require time proportional to 1 - Correct Answers: False; require time proportional to the number of items in an array T/F? O(log N) is the best time - Correct Answers: False; O(1) IS CONSTANT TIME SO IT IS THE BEST O (log N) is good O (N) is fair O (N2) is pretty bad Sorting - Correct Answers: Putting things in order Examples of sort algorithms (5) - Correct Answers: Bubble sort, selection sort, insertion sort, sorting objects, comparing sorts Basic sorting concepts - Correct Answers: 1. Compare two items 2. swap items or move data over to place and item 3. Repeat steps until list is sorted 4. Usually requires a loop within a loop 5. Lists of items can be more quickly sorted if the items in the list are ordered Bubble Sort - Correct Answers: Items "bubble up" to the top of the list -can start at either end of the list -Ascending order: 1. start at end of list 2. compare last element to the second to last 3. move up one in the list and repeat until start of the list is reached leaving the smallest item in the first position 4. repeat process starting at last item and stopping at second item, then again stopping at third item. 5. keep going until no more swaps or you reach the end of the list Look at slide 12 in chapter 3 part 1 ppt Bubble sort analysis - Correct Answers: 1. N (number of items)-1 passes 2. Comparisons: (N-1) + (N-2) + ..... 3. Swaps same as comparisons 4. Efficiency formula: N* (N-1)/2 5. Both Swaps and comparisons proportional to N^2 Big O notation: O(N^2) Selection Sort - Correct Answers: Scan all elements to be sorted to find smallest or largest item and put as first position in the array by swapping it with the item currently there. -find the smallest item in the remaining part and put it in the first position of the unsorted part of the array, swapping with the item there -repeat until end of array is reached *So you start with the element at position 0 and assume it is the smallest and compare it with the rest. Like start with 23 at position 0, then compare to next element 5 and make 5 the lowest. Then keep comparing 5 to all elements until something is smaller like 3. Then you keep going til you reach the end and let's say 3 was the lowest, then you would swap 3 with the 23 in position 0. Look at slide 17 in ch3p1 ppt and slide 23 for the code Selection Sort Analysis - Correct Answers: 1. Comparisons are N-1 + N-2 + .... 2. Swaps are 0 or 1 per pass so 0 to N-1 3. Efficiency formula: N* (N-1)/2 compares (N-1)/2 average swaps 4. Compares are prop to N^2 5. Swaps are prop to N 6. Big O: O(N^2) *but faster than bubble sort Insertion Sort - Correct Answers: Insert the next unsorted value into the sorted part of the list in the right place -can start at either end of list -Ascending order: 1. start at beginning of list 2. determine if second item should be placed before/after the first value 3. if should be before first value, move that value and put the new value there 4. Determine if third value should be placed before, in between, or after the first two. and shift as necessary to make space for them. 5. Repeat until all items are inserted into their place Look at slide 3 in ch3p2 ppt Insertion sort analysis - Correct Answers: 1. N-1 passes 2. Comparisons: 1+2+3+4.... 3. Moves are cheaper than swaps (bc a move is one move, a swap is three moves) 4. Swaps are prop to N^2 5. Big O: O(N^2) Bubble sort Compares: Swaps: Moves: - Correct Answers: N*(N-1)/2 N*(N-1)/2 3*N*(N-1)/4avg Selection sort Compares: Swaps: Moves: - Correct Answers: N*(N-1)/2 (N-1)/2avg 3*(N-1)/2avg Insertion sort Compares: Swaps: Moves: - Correct Answers: N*(N-1)/4avg N/A - no swaps N*(N-1)/4avg Fill in the blank: If compares are more expensive, then ___ sort is the fastest - Correct Answers: Insertion T/F? All three sorts bubble, selection and insertion are O(N^2) - Correct Answers: True T/F? The bubble, selection, and insertion sorts AKA SIMPLE SORTS - Correct Answers: TRUE What is the simplest of the simple sorts? - Correct Answers: Bubble sort (use only if you don't have other algorithms available and you have a small number of elements T/F? Selection sort minimizes number of swaps, but comparisons are still high. - Correct Answers: True T/F? Insertion sort is useful when amount of data is small and if swapping is very time consuming - Correct Answers: False; Selection sort T/F? Insertion sort is the most versatile and the best option in most situations if data is small or almost sorted - Correct Answers: True T/F? The three simple sorts require alot of space - Correct Answers: FALSE; they require very little space and they sort IN PLACE. T/F? When sorting an array of string objects use string method compareTo ex. reTo(s2) - Correct Answers: True compareTo method returns what? - Correct Answers: An integer: 0, positive integer, or negative integer Sort stability - Correct Answers: Data with the same keys are kept in initial order (AKA STABLE). T/F? bubble, selection, and insertion sorts are all STABLE - Correct Answers: TRUE How do stacks, queues, and priority queues differ from arrays? - Correct Answers: They are both data storage structures. BUT: stacks, queues, and priority queues are used to help solve a problem, not simply store data. They are often used for a specific task and then are discarded. In abstract data structures (stacks, queues, trees, priority queues) real access is: - Correct Answers: controlled by an interface normally not visible to the user. Usually abstracted via class, no direct access Stacks - Correct Answers: Give access to only one item at a time (the last item inserted) -think of a stack of dishes -It is a LIFO data structure (Last In First out) -Evaluate parenthesized expressions -Evaluate arithmetic expressions (even with alot of parentheses) -Traverse binary trees -search vertices of a graph, etc. T/F? Stack-based architecture are used in computers for function/method invocations. - Correct Answers: True T/F? Adding an item is a POP and removing is a PUSH - Correct Answers: False; Adding an item=Push Removing an item=POP Push - Correct Answers: Add an item to the top of a stack Pop - Correct Answers: Remove an item from the top of a stack Stack overflow - Correct Answers: The stack is full, cannot push! Stack underflow - Correct Answers: The stack is empty, cannot pop! Peek - Correct Answers: Look at an item without popping(removing) it Stack size - Correct Answers: The maximum number of items that have been in the stack T/F? Always check if there are items on the stack before POPPING the stack or if there is room before PUSHING the stack - Correct Answers: True Ask if full or empty before deleting/adding anything. Delimiters - Correct Answers: Normally special characters ex. commas, white space, braces, brackets, parentheses T/F? delimiters must always balance (meaning the first right parenthesis balances the most recent unbalanced left parenthesis - Correct Answers: True- BUT NOT WHITE SPACES Do the delimiters match? a{b(c) - Correct Answers: No, missing another } closing delimiter should match opening on the stack Algorithm for stacks - Correct Answers: 1. When an opening delimiter is encountered, it is pushed 2. When encounters closing delimiters, verifies that the delimiter on the top of the stack is the matching opening delimiter -if so, pop the stack -if not, delimiter mismatch occurred 3. If hit the end and stack is not empty, missing closing delimiter 4. The delimiter opened last must be closed first 5. If diff delimiters are used then the correct one must be fond, if syntax is valid. T/F? Once a stack is set up, you don't have to keep track of indices - Correct Answers: True Push and Pop Big o Notation - Correct Answers: O(1) constant time! No dependency on number of items in stack & no comparisons/moves needed. Queues - Correct Answers: FIFO (First In First Out) structure like a line! -It can be implemented using an array, linked list or other structure -Typically used to model waiting lines like waiting at Starbucks. Examples of queues in your operating system - Correct Answers: -print queues, job queues, ready queues, keyboard queues The concept of a queue - Correct Answers: People join the queue in the rear and leave at the front. Data is entered in one end and data is extracted from the other end. Queue operations are: - Correct Answers: Insert and remove 1. Insert at the rear (tail or back) of the queue 2. Remove at the front (head) of the queue Potential errors with queues - Correct Answers: 1. Attempting to remove an item from an empty queue- empty queue message should be returned. 2. Attempting to insert an item into a full queue- full queue message should be returned. As in a stack, we must ___ the queue - Correct Answers: Create T/ F? We can have circular queues - Correct Answers: True, but must be careful to keep track of front and rear so that they do not wrap! Insert and Remove in Queues Big o Notation - Correct Answers: O(1) constant time (immediate!!) -Always know the value of the appropriate index -minor change in value of front or rear Dequeus - Correct Answers: A double-ended queue -can insert and delete from either end -can insertLeft and insertRight, etc. -can implement a stack or queue -use only insertLeft and removeLeft and you have a stack. -use only insertLeft and removeRight and you have a queue ***check textbook for this... Priority Queue - Correct Answers: A more specialized queue, still remove from front but insert may not be at the end of the queue -items are ordered by some key -items with the lowest/highest key are always at the front -items are then inserted in proper position Example of priority queue - Correct Answers: -Emergency room (sometimes people are seen based on the severity of the issue) -Airline boarding (based on status and then position) -Job scheduling (based on process priority) -Print queues (based on number of pages) T/F? A priority queue is FIFO like a regular queue - Correct Answers: FALSE What two functions do priority queues have ? - Correct Answers: Remove and insert 1. remove- the first item has priority and can be retrieved(removed) quickly and returned to calling enviro. So this is easy and takes O(1) time 2. Insert- new item must go into proper position, must move items to make space, if using an array then slow to insert N/2 times, for small number of items and where speed isn't critical, this is simplest approach: speed is O(N) OR: do not keep queue sorted and search the queue for highest/lowest key on remove (slow) T/F? Always check to see if there are items on the pqueue before removing - Correct Answers: True, is it full, empty? Why doesn't pqueue code need to worry about wrap around? - Correct Answers: Front is always nItems-1 and rear is always 0. queue is full if nItems reaches array size LEFT OFF ON SLIDE 12 CH4P2 PPT - Correct Answers: