EECE 330 Final, Spring 2008

1. Which of the primitive sorting algorithms requires the least number of swaps? a) Bubble Sort b) Selection Sort c) Insertion Sort d) a and b e) The three mentioned algorithms require the same number of swaps 2. Given the array A={20,6,15,12,40,52,1,10} What is the array after applying insertion sort algorithm at i=3 ? a) 6,12,20,15,40,52,10 b) 6,12,15,20,40,52,1 yes or non of the above c) 1,6,12,15,20,40,52 d) 6,15,12,40,52,1 e) None of the above 3. Given the array A= {20,6,15,12,40,52,1,10} What is the array after applying bubble sort algorithm at i=1 ? is it i=0 ? a) 1,6,20,15,12,40,52,10 b) 1,20,6,15,12,40,52,10 c) 1,10,6,15,12,20,40,52 d) 1,6,10,15,12,20,40,52 e) None of the above 4. If the inner for loop in the Bubble Sort Algorithm was replaced with For(int j=n-1;j>0;j--) Which of the following statements would be correct? a) The bubble sort will not function b) Unneeded comparisons will be done c) Unneeded swaps will be done d) It will work in the same manner e) None of the above is correct 1. Suppose that a selectionsort of 100 items has completed 42 iterations of the main loop. How many items are now guaranteed to be in their final spot (never to be moved again)? o A. 21 o B. 41 o C. 42 o D. 43 2. Suppose we are sorting an array of eight integers using quicksort, and we have just finished the first partitioning with the array looking like this: 2 5 1 7 9 12 11 10 Which statement is correct? o A. The pivot could be either the 7 or the 9. o B. The pivot could be the 7, but it is not the 9. o C. The pivot is not the 7, but it could be the 9. o D. Neither the 7 nor the 9 is the pivot. 3. What is the minimum number of nodes in a complete binary tree with depth 3? o A. 3 o B. 4 o C. 8 o D. 11 o E. 15 Consider the binary tree: 14 / \ 2 11 / \ / \ 1 3 10 30 / / 7 40 4. Which statement is correct? o A. The tree is neither complete nor full. o B. The tree is complete but not full. o C. The tree is full but not complete. o D. The tree is both full and complete. 5 . Suppose you have a directed graph representing all the flights that an airline flies. What algorithm might be used to find the best sequence of connections from one city to another? o A. Breadth first search. o B. Depth first search. o C. A cycle-finding algorithm. o D. A shortest-path algorithm. 6. Suppose that a non-leaf node in a B-tree has 41 entries. How many children will this node have? o A. 2 o B. 40 o C. 41 o D. 42 o E. 82 QUESTION 1: Below is the merge sort function: void mergeSort(int A[], int temp[], int left, int right) { int mid=(left+right)/2; if(left==right) return; mergeSort(A, temp, left, mid); mergeSort(A, temp, mid+1, right); for(int i=left;i<=right;i++) temp[i]=A[i]; int i1=left; int i2=mid+1; for(int curr=left; curr<=right; curr++) { if(i1==mid+1) A[curr]=temp[i2++]; else if(i2>right) A[curr]=temp[i1++]; else if(temp[i1]<temp[i2]) A[curr]=temp[i1++]; else A[curr]=temp[i2++]; } } Suppose that you apply this function to the following array: a[10]={9,4,3,2,1,5,7,44,77,22}; What is the order of this array after entering the sixth recursive function call? A) 4,9,3,2,1,5,7,44,77,22 B) 3,4,9,2,1,5,7,44,77,22 C) 1,2,3,4,5,7,9,22,44,77 D) None of the above Hint: Make use of the computer! Create at the beginning of the function a static counter and display on the screen the array at every call!!! A is the correct answer. QUESTION 2: Assume that the platters’ tracks of a disk drive contain 128 sectors, and that the track to track seek time is 1.8 ms and that 4 sectors form a cluster. The disk rotation rate is 5400 rpm. The interleaving factor is 4. Assume that the file’s clusters are not spread randomly. Knowing that the time to read a file divided into 704 sectors is 297.5 ms, find the average seek time for random access! A) 11 ms B) 10.5 ms C) 10 ms D) 9.5 ms Answer is A (11ms): 11+1.8*5+44.4*5+11.1*6/2+44.4/2=297.5 QUESTION 3: If you apply buildheap, of the minheap structure, to the array of question 1 than you remove the minimum 10 times, what will you obtain? A) A sorted array in ascending order B) A sorted array in descending order C) A maxheap D) B and C B is the answer Elie … 1. Suppose root is a pointer to a B+ tree node, A is the array of key/pointer pairs for this node, n is the number of elements, k is the search key, and e is the pointer to the record we are searching for. Each element of A consists of the pair ky and ptr. If the functions: gle(PAIR A[],int n,KEY k) returns the greatest value in A less than or equal to k sge(PAIR A[],int n,KEY k) returns the smallest value in A greater than or equal to k Then, the following code fragment searches for the record whose key is k in an index file that uses a B+ tree, whose root node is pointed to by root a) bool find(BPNode *root, Key k, Elem *e){ cur=sge(root->A, root->n,k); if (root->isleaf()) if (root->A[cur].ky==k){ e= root->A[cur].ptr; return true;} else return false; else find(e= root->A[cur].ptr, k, e);} b) bool find(BPNode *root, Key k, Elem *e){ cur=sge(root->A, root->n,k); if (root->isleaf()) if (root->A[cur].ky==k){ e= root->A[cur].ptr; return true;} else find(e= root->A[cur].ptr, k, e);} c) bool find(BPNode *root, Key k, Elem *e){ cur=gle(root->A, root->n,k); if (root->isleaf()) if (root->A[cur].ky==k){ e= root->A[cur].ptr; return true;} else return false; else find(e= root->A[cur].ptr, k, e);} d) bool find(BPNode *root, Key k, Elem *e){ cur=gle(root->A, root->n,k); if (root->isleaf()) if (root->A[cur].ky==k){ e= root->A[cur].ptr; return true;} else find(e= root->A[cur].ptr, k, e);} 2. Assume that a computer system has disk clusters (blocks) of 256 bytes (¼KB) and the language used to develop software uses 4 bytes for integers, 4 bytes for pointers, 1 byte for characters, and 8 bytes for doubles, and 8 bytes for longs. Assume we have the following records (the name filed is 32 characters, ID is a long, and Pay is a double): Name Flor Saab Jaber Safa Flor Kadi Harb Harb Safa Harb Kadi Safa ID 2000 2010 2011 2100 2110 2017 2019 2155 2066 2022 2013 2090 Pay 56.2 57.8 56.0 55.0 60.1 58.4 57.6 56.16 59.4 63.1 62.9 45.6 If we use a two-dimensional linear index, using the Name as secondary key and ID as primary key, then the size of the index file in bytes will be: a) 256 bytes b) 512 bytes c) 528 bytes d) 768 bytes e) 1024 bytes 3. Suppose we use double hashing to generate probe sequences for a Hash table with 100 slots. If h1(k) is the first hash function and h2(k) is the second hash function, then when have 3 records to be searched for such that h1(k1)=337, h2(k1)=7, h1(k2)=145, h2(k2)=27, h1(k3)=97, h2(k3)=43, then the probe sequences for k1, k2, and k3 are a) [37,44,51,58,65], [45,72,99,26,53], and [97,40,83,26,69] b) [37,44,58,79,7], [45,72,26,7,15], and [9,7,40,26,55,27] c) [37,44,51,58,65], [45,72,99,126,153], and [97,140,183,226,269] d) [37,44,51,58,65], [45,72,99,128,53], and [97,140,183,126,169] 1 Consider this binary search tree” 14 / \ 2 16 / \ 1 5 / 4 Suppose we remove the root, replacing it with something from the left subtree. What will be the new root? A. 1 B. 2 C. 4 D. 5 E. 16 2 Select the one true statement. A. Every binary tree is either complete or full. B. Every complete binary tree is also a full binary tree. C. Every full binary tree is also a complete binary tree. D. No binary tree is both complete and full. 3 What additional requirement is placed on an array, so that binary search may be used to locate an entry? A. The array elements must form a heap. B. The array must have at least 2 entries. C. The array must be sorted. D. The array's size must be a power of two 4 Consider the following pseudocode: declare a stack of characters while ( there are more characters in the word to read ) { read a character push the character on the stack } while ( the stack is not empty ) { write the stack's top character to the screen pop a character off the stack } What is written to the screen for the input "carpets"? A. serc B. carpets C. steprac D. ccaarrppeettss 5 Suppose that we have implemented a priority queue by storing the items in a heap. We are now executing a reheapification downward and the out-of-place node has priority of 42. The node's parent has a priority of 72, the left child has priority 52 and the node's right child has priority 62. Which statement best describes the status of the reheapification. o A. The reheapification is done. o B. The next step will interchange the two children of the out-of-place node. o C. The next step will swap the out-of-place node with its parent. o D. The next step will swap the out-of-place node with its left child. o E. The next step will swap the out-of-place node with its right child. 1) Having the three types of sorting, Insertion, Bubble and Selection. What are there swapping costs respectively? a- n2, n2, n2 b- n2, n, n2 c- n2, n2, n (correct answer) d- n2, n2, log n e- n , log n, log n 2) Having the following array: 73 6 57 88 60 42 83 72 48 85 Suppose we need to sort using Heap sort, what would be the array after building the heap and after removing 2 elements from it. a- 88 85 83 72 73 42 57 6 48 60 b- 85 73 83 72 60 42 57 6 48 88 c- 85 48 83 72 60 42 57 6 73 88 d- 83 73 57 72 60 42 48 6 85 88 (correct answer) e- 6 42 48 57 60 72 73 83 85 88 3) Having the following B+ tree: After deleting 18 and 12, what would be the other numbers in the same node with 21? a- 20 and 22 (correct answer) b- 19, 20 and 22 c- 20, 22 and 23 d- 22 e- None of the above I- We have the following graph, find the minimum spanning tree using kruskal’s algorithm: A-) B-) C-) D-) E-)None of the above Answer is A II-) How many iterations are required for the array to be sorted using quick sort:(5 is the pivot and is already hidden): A-)10 B-)40 C-)50 D-)5 E-)None of the above Answer is E III-) This is the initial B+ tree: Delete in the following order: -25, 911, 217, 93, 413 and finally 10. While deleting, we have to merge in two occasions. Which deleted numbers will cause us a merge operation? A-)25,911. B-)217,10. C-)10,413 D-)413,93 E-)217,25 4-) Given that the track to track seek time is 3ms, the interleaving factor is 4, and that we want to read 9 contiguous tracks, and we know that the total reading time is 400ms, and the time to read the first track is 50ms, find the average seek time, and the rotational delay. A-)9.05555,9.25, B-)9.9876,9.00, C-)14.3333333,15.5555555555, D-)14.666666666,15.333333333, E-)none of the above 5-) Given that the average seek time is 10ms, the rotational delay is 12 and that we have 512 sectors, what is the time to read one sector? A-)17, B-)19, C-)20, D-)15.5, E-)None of the above 1. Suppose we have the following linked list. To make the fence point to the node whose element’s value is 54, how many step would it take? (step=moving the fence from one node to another or assigning it to another pointer). a) 4 steps b) 5 steps 33 44 55 66 fence 54 22 11 88 c) 6 steps d) 7 steps 2. When values are introduced one by one to a max heap, nodes are added top to bottom – left to right. Hence, for the maxheap on the right, values must have been introduced in the following sequence: a) 38,40, 26, 35, 30, 16, 11, 15, 9, 29, 7 b) 38,29, 44, 30, 16, 15, 11, 9, 26, 7 ,40 c) 40, 38, 29, 35, 30, 15, 11, 16, 9, 26, 7 d) 40,38, 29, 30, 35 , 15, 11, 9, 16, 26, 7 3. Consider the code fragment below. bool find (nodeptr, key, recordptr){ if (nodeptr is a leaf){ if (key==left key) recordptr=left keyptr; else if (key==right key) recordptr=right keyptr; else return false; return true;} if (key < left key) find (leftchildptr, key, recordptr); else if (key < right key) find (centerchildptr, key, recordptr); else if (key >= right key) find (rightchildptr, key, recordptr);} It is used to find a record in a: a) 2-3 tree b) B Tree c) B+ Tree d) All of the above e) None of the above 1. Mergesort makes two recursive calls. Which statement is true after these recursive calls finish, but before the merge step? A. The array elements form a heap. B. Elements in each half of the array are sorted amongst themselves. C. Elements in the first half of the array are less than or equal to elements in the second half of the array. D. None of the above. 2. Consider a complete binary tree with 1000 nodes, with the data stored in the elements a[0]..a[999] of an array. Where are the parent and the left child of the node stored at a[100]? A. Parent at 49, left child at 200 B. Parent at 49, left child at 201 C. Parent at 50, left child at 200 30 26 7 15 11 38 29 40 35 16 9 D. Parent at 50, left child at 201 E. None of the above 3. Which statement is true for a B-tree?  All entries of a node are greater than or equal to the entries in the node's children.  All leaves are at the exact same depth.  All nodes contain the exact same number of entres.  All non-leaf nodes have the exact same number of children. 4. A chained hash table has an array size of 512. What is the maximum number of entries that can be placed in the table? o A. 256 o B. 511 o C. 512 o D. 1024 o E. There is no maximum. 5. Which guideline is NOT suggested from from empirical or theoretical studies of hash tables:  Hash table size should be the product of two primes.  Hash table size should be the upper of a pair of twin primes.  Hash table size should have the form 4K+3 for some K.  Hash table size should not be too near a power of two. 1. If G is an directed graph with 20 vertices, how many boolean values will be needed to represent G using an adjacency matrix? o A. 20 o B. 40 o C. 200 o D. 400 2. How many linked lists are used to represent a graph with n nodes and m edges, when using an edge list representation, o A. m o B. n o C. m + n o D. m*n 3. chained hash table has an array size of 512. What is the maximum number of entries that can be placed in the table? o A. 256 o B. 511 o C. 512 o D. 1024 o E. There is no maximum. 4. Suppose you place m items in a hash table with an array size of s. What is the correct formula for the load factor? o A. s + m o B. s - m o C. m - s o D. m * s o E. m / s 5 Suppose that X is a B-tree leaf containing 41 entries and having at least one sibling. Which statement is true? o A. Any sibling of X is also a leaf. o B. Any sibling of X contains at least 41 entries. o C. The parent of X has exactly 42 entries. o D. X has at least 41 siblings. 1-Suppose that we delete the value 23 from the beap below. In which position will the key 49 appear after the deletion is complete? A. A B. B C. C D. D E. E 2-What is the worst-case time for quicksort to sort an array of n elements? o A. O(log n) o B. O(n) o C. O(n log n) o D. O(n²) 3-Which order is not a possible order in which depth first search could mark the vertices of the graph shown below as being visited? A. ABEFDC B. ACEFBD C. ABDFCE D. ABDFEC E. All of the above are possible depth first search orders 4. Which order is not a possible order in which breadth first search could mark the vertices of the graph of question 3 as being visited? A. ABCDEF B. ABCEDF C. ACBDEF D. ACBEDF E. ABDCEF 5-Suppose T is a binary tree with 14 nodes. What is the minimum possible depth of T? A. 0 B. 3 C. 4 D. 5 Question 1: Which statement is true for a B-tree? o A. All entries of a node are greater than or equal to the entries in the node's children. o B. All leaves are at the exact same depth. o C. All nodes contain the exact same number of entres. o D. All non-leaf nodes have the exact same number of children. Question 2: What is the best definition of a collision in a hash table? o A. Two entries are identical except for their keys. o B. Two entries with different data have the exact same key. o C. Two entries with different keys have the same exact hash value. o D. Two entries with the exact same key have different hash values. Question 3: Suppose we are sorting an array of ten integers using a some quadratic sorting algorithm. After four iterations of the algorithm's main loop, the array elements are ordered as shown here: 1 2 3 4 5 0 6 7 8 9 Which statement is correct? (Note: Our selectionsort picks largest items first.) o A. The algorithm might be either selectionsort or insertionsort. o B. The algorithm might be selectionsort, but could not be insertionsort. o C. The algorithm might be insertionsort, but could not be selectionsort. o D. The algorithm is neither selectionsort nor insertionsort. Question 4: Suppose you have a game with 5 coins in a row and each coin can be heads or tails. What number of vertices might you expect to find in the state graph? o A. 7 o B. 10 o C. 25 o D. 32 Question 5: 1. What additional requirement is placed on an array, so that binary search may be used to locate an entry? o A. The array elements must form a heap. o B. The array must have at least 2 entries. o C. The array must be sorted. o D. The array's size must be a power of two. 14 / \ 2 11 / \ / \ 1 3 10 30 / / 7 40 1. Consider the binary tree above. Which statement is correct? A. The tree is neither complete nor full. B. The tree is complete but not full. C. The tree is full but not complete. D. The tree is both full and complete. 2. Select the one FALSE statement about binary trees: A. Every binary tree has at least one node. B. Every non-empty tree has exactly one root node. C. Every node has at most two children. D. Every non-root node has exactly one parent. 3. What is the worst-case time for mergesort to sort an array of n elements? o A. O(log n) o B. O(n) o C. O(n log n) o D. O(n²) 4. Suppose you have a directed graph representing all the flights that an airline flies. What algorithm might be used to find the best sequence of connections from one city to another? A. Breadth first search. B. Depth first search. C. A cycle-finding algorithm. D. A shortest-path algorithm. 5. In the linked list implementation of the stack class, where does the push member function place the new entry on the linked list? A. At the head B. At the tail C. After all other entries that are greater than the new entry. D. After all other entries that are smaller than the new entry. 1. Suppose we have the list <15 4 | 20 55 10> and then execute the following C++ calls e=0; L1.remove(e); L1.append(e); L1.prev(); L1.insert(e); The result will be: a) <| 4 15 20 55 10 4> b) <15 | 4 20 55 10 20> c) <15 | 20 4 55 10 20> d) <15 4 | 20 55 10 20> 2. Suppose we have a disk with the following specifications: Speed is 8200RPM, average seek time is 7.9ms, and track to track seek delay is 1.8ms. The rotational delay is then a) About 14.634ms b) About 7.9ms c) About 7.31ms d) About 3.66ms 3. Suppose we use bucket Hashing with M=5 (M is the number of home positions), the number of slots per bucket is 5 (including the home slot), and the size of the overflow bucket is 50. Suppose we have the following hash function h(k)=k%M. if we have the following keys: 37,44,58,79,17,45,72,26,7,15,77,40,36,55,27,97,57,66,54,9 Then the number of records in the overflow bucket will be a) 0 b) 1 c) 2 d) 3 e) 4 f) 5 4. Suppose we have the following two disks: - Disk 1: 8200RPM, average seek time is 9.5ms, track to track seek time is 1.5ms - Disk 2: 5600RPM, average seek time is 5.2ms, track to track seek time is 1.75ms Given the same operating system, a) We will always read files faster from disk 1 b) We will always read files faster from disk 2 c) None of the above 1-What is the maximum number of nodes that a binary tree of height n can have? a- 2^n b- 2^(n) -1 c- 2^(n) +1 d- 2n + 1 e- 2^(n-1) 2- What is the minimum number of levels that a binary tree with n nodes requires? a- log(n) b- n c- log(n-1) d- n-1 e- log(n+1) 3- consider the following array 42 20 17 13 28 14 23 15 What is the index of the element 42 after iteration #4 assuming indexing starts from 0? a- 2 b- 3 c- 4 d- 5 e- 6 1) If initial node is 0 what are the process steps of the following graph using dijkstra’s algorithm? a) 0 1 2 3 4 Initial ¥ ¥ ¥ ¥ ¥ Process 0 ¥ 5 11 ¥ ¥ Process 1 ¥ 5 11 18 15 Process 2 ¥ 5 11 18 15 Process 4 ¥ 5 11 16 14 Process 3 ¥ 5 11 16 14 b) 0 1 2 3 4 Initial 0 ¥ ¥ ¥ ¥ Process 0 0 5 11 ¥ ¥ Process 1 0 5 11 18 15 Process 2 0 5 11 18 15 Process 4 0 5 11 18 15 Process 3 0 5 11 16 14 c) 0 1 2 3 4 Initial 0 ¥ ¥ ¥ ¥ Process 0 0 5 11 ¥ ¥ Process 1 0 5 11 18 15 Process 2 0 5 11 16 15 Process 4 0 5 11 16 15 Process 3 0 5 11 16 14 d) 0 1 2 3 4 Initial 0 ¥ ¥ ¥ ¥ Process 0 0 5 11 ¥ ¥ Process 1 0 5 11 18 15 Process 2 0 5 11 18 14 Process 4 0 5 11 16 14 Process 3 0 5 11 16 14 e) none of the above 2) Find the resulting MST using Prim’s algorithm: a) 0 3 2 7 6 9 1 5 3 7 2 3 8 4 4 4 1 5 6 7 6 8 b) c) d) e) none of the above 3) How will the following program sort? template< classElem, class Comp> void sort( Elem A[], Elem Temp[], int left, int right) { int mid = (left+right)/2; if (left == right) return; sort<Elem,Comp> (A, Temp, left, mid); sort<Elem,Comp> (A, Temp, mid+1, right); for (int i = left; i >= right; i++) temp[i] = A[i]; int i1 = left ; int i2 = mid+1 ; for ( int curr = left; curr >= right; curr++) { if( i1 == mid+1) A[curr] = temp[i2++]; else if (i2 < right) A[curr] = temp[i++]; else if (Comp::gt(temp[i1], temp[i2])) A[curr] = temp[i1++]; else A[curr] = temp [i2++]; } } a) doesn’t sort b) ascending order quick sort c) descending order mergesort d) ascending order mergesort e) descending order quick sort 0 3 2 7 6 9 1 5 3 7 2 3 8 4 4 4 1 5 6 7 6 8 4) How will the following numbers be stored in a five slot hash table using the hash function h (K) = K mod 5? 5679, 1212, 1999, 2005, 798, 650, 500, 229. a) b) c) d) e) none of the above 5) Which sorting relies on the exchange sorting? a) Quick sort, mergesort, bubble sort. b) Insertion sort, bubble sort, selection sort. c) Heap sort, mergesort, bubble sort. d) Insertion sort, bubble sort, selection sort, binsort. e) heap sort, radix sort.