CS2604 Quizzes: Fall 2001, Dr. Shaffer's Sections Quiz 1 (Answer using asymptotic notation) Q1: If you are "at" the right place already, what is the cost (average case) to delete an element from: a) The array-based list implementation? A: Theta(n) b) The linked list implementation? A: Theta(1) Q2: What is the (average case) cost to get to an arbitrary position in a list of n elements for the: a) Array-based list implementation? A: Theta(1) b) Linked list implementation? A: Theta(n) ======================================================== Quiz 2 Show the Binary Search Tree that results from inserting the following values, in the given order: 5, 30, 15, 12, 20, 45, 70 A: 5 \ 30 / \ 15 45 / \ \ 12 20 70 ======================================================== Quiz 3 1) Which sorting algorithm is best when the input is sorted or nearly sorted? A: Insertion sort 2) Which sorting algorithm is best when we need to minimize the number of record swaps? A: Selection sort Quiz 4 1) What are the best, average, and worst case asymptotic costs for Mergesort? A: Theta(n log n) for best, average, and worst cases. 2) What is the asymptotic cost for the partition step of Quicksort on a subarray of i records? A: Theta(i). ======================================================== Quiz 5 1) How many ways can n records be arranged? A: n! 2) We proved that, in the general case, sorting costs at least: A: Omega(n log n) ======================================================== Quiz 6 List the three steps involved in reading data from disk. A: 1. Seek to the right track. 2. Rotational delay while the data come under the head. 3. Reading off the data that move under the head. ======================================================== Quiz 7 What are the two main steps for an external sorting algorithm? A: 1) Break the file into a series of runs (each run as large as possible). 2) Merge the runs together to sort the file. ======================================================== Quiz 8 Name two self-organizing list heuristics that we discussed in class. A: Two of the following: 1) List ordered by frequency (Count) 2) Move to Front 3) Transpose ======================================================== Quiz 9 [This quiz given by Dr. McCrickard to the morning section] Given a hash table with M = 13, and hash function h(k) = k mod 13, state the hash position (home slot) and the first three positions for K=21 under the following collision resolution policies. 1) Linear Probing A: 8, 9, 10, 11 2) Improved linear probing with c = 5 A: 8, 0, 5, 10 3) Pseudo-random probing with a permutation starting 1, 7, 12, 9, 5, 3 A: 8, 9, 2, 7 4) Quadratic probing A: 8, 9, 12, 4 5) Double hashing with h2(k) = (k mod 5) + 1 A: 8, 10, 12, 1 ======================================================== Quiz 10 1) Under what circumstances would linear indexing be a good choice for indexing a database? A: When the database is static, i.e., no insertions or deletions. 2) Under what circumstances would a B-tree be a good choice for indexing a database. A: For a large database that requires support for insertions and deletions as well as searches. ======================================================== Quiz 11 Show the result of inserting the value 30 into the following B+-tree. Assume that leaf nodes can hold at most 5 values, and that internal nodes can have at most 4 children.
A: The result is the tree of Figure 10.17 (d).