Words: 6489
Virtual University of Pakistan CS301 Data Structure File Version v3. 2. 0 Prepared For:Final Term Note: Use Table Of Content to view the Topics, In PDF(Portable Document Format) format , you can check Bookmarks menu Disclaimer: There might be some human errors, if you find please let me know at pak. nchd@gmail. com , duplication of data may be possible but at least possible level Your Feed Back is Highly Appreciated. Compiled and Prepared by: Muhammad Ishfaq (PakPattan) File updated on 7/14/2011 CS301 Data Structure_ Muhammad Ishfaq —-:Table of Content:—- Page No. 1
Table of Content TABLE OF CONTENT ………………………………………………………………………………………………………………………………………………… 1 SHORT QUESTIONS PAPER ……………………………………………………………………………………………………………………………………….. 5 SET-01 ……………………………………………………………………………………………………………………………………………………………………….. Convert the given infix form to postfix form. ………………………………………………………………………………………………………………. 5 A+B/C-D^E-F ………………………………………………………………………………………………………………………………………………………….. 5 How we can implement Table ADT using Linked List……………………………………………………………………………………………………. 5 If we allow assignment to constants what will happen? ……………………………………………………………………………………………… 5 How heap sort works to sort a set of data. ………………………………………………………………………………………………………………… 5 Give your comment on the statement that heap uses least memory in array representation of binary trees. Justify your answer in either case. ……………………………………………………………………………………………………………………………………………… How we can use concept of equivalence relations to generate a Maze. …………………………………………………………………………. 5 “For smaller lists, linear insertion sort performs well, but for larger lists, quick sort is suitable to apply. ” Justify why? ………… 5 6 9 5 0 4 1 7 3 2 ……………………………………………………………………………………………………………………………………………………… 5 Show the first five merging steps for Merge sort on this array. ……………………………………………………………………………………. 5 What is Disjoint Sets? Explain with an example. …………………………………………………………………………………………………………. 5 Write the code of the perculateDown() function and also comment it. ………………………………………………………………………….. 5 Here is an array with exactly 15 elements:…………………………………………………………………………………………………………………. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15. …………………………………………………………………………………………………………………………… 5 SET-02 ……………………………………………………………………………………………………………………………………………………………………….. 6 Give one example of Hashing …………………………………………………………………………………………………………………………………… 6 How heap sort works to sort a set of data. ……………………………………………………………………………………………………………….. 6 How we can implement Table ADT using Linked List……………………………………………………………………………………………………. 6 If we allow assignment to constants what will happen? ………………………………………………………………………………………………. 6 Explain the process of Deletion in a Min-Heap ……………………………………………………………………………………………………………. Give any three characteristics of Union by Weight method. …………………………………………………………………………………………. 6 “For smaller lists, linear insertion sort performs well, but for larger lists, quick sort is suitable to apply. ” Justify why? ………… 6 Write down the C++ code to implement Insertion Sort Algorithm. ………………………………………………………………………………… 6 Consider the following Threaded Binary Tree,…………………………………………………………………………………………………………….. What is Disjoint Sets? Explain with an example. …………………………………………………………………………………………………………. 7 SET-03 ……………………………………………………………………………………………………………………………………………………………………….. 7 Give the difference between strict and complete binary tree. ………………………………………………………………………………………. A complete binary tree can be stored in an array. While storing the tree in an array ………………………………………………………. 7 we leave the first position (0th index )of the array empty. Why? ………………………………………………………………….. ……………… 7 Give the name of two Divide and Conquer algorithms. ………………………………………………………………………………………………… 8 Give the effect of sorted data on Binary Search. ………………………………………………………………………………………………………… 8 Give any three characteristics of Union by Weight method. …………………………………………………………………………………………. 8 Here is an array of ten integers: ……………………………………………………………………………………………………………………………….. 8 Give your comment on the statement that heap uses least memory in array representation of binary trees. Justify your answer in either case. …………………………………………………………………………………………………………………………………………….. 8 Suppose we have the following representation for a complete Binary Search Tree, tell the Left and Right child nodes and Parent node of the node D ………………………………………………………………………………………………………………………………………. 9 Explain the following terms: …………………………………………………………………………………………………………………………………….. Here is an array with exactly 15 elements:……………………………………………………………………………………………………………….. 10 SET-04 ……………………………………………………………………………………………………………………………………………………………………… 10 How we can search an element in Skip List. ……………………………………………………………………………………………………………… 10 Share your feedback/comments at pak. chd@gmail. com to improve file|| Back to TOP || File Version v3. 2. 0 published for Final Term CS301 Data Structure_ Muhammad Ishfaq Page No. 2 What is the drawback of using arrays to store Binary Search Trees. …………………………………………………………………………… 10 Calculate the codes of the following characters in table below using the hoffman encoding tree, …………………………………… 10 “For smaller lists, linear insertion sort performs well, but for larger lists, quick sort is suitable to apply. ” Justify why? ………. 1 Give two different reasons to explain why the following binary tree is not a heap: ……………………………………………………….. 11 Here is an array of ten integers: ……………………………………………………………………………………………………………………………… 12 A long sequence of vowels needs to be transmitted efficiently so a programmer decides to use Huffman encoding to encode the vowels. A distribution count study of typical data yielded the following frequency table. …………………………………………. 2 Consider the following tree. …………………………………………………………………………………………………………………………………… 13 SET-05 ……………………………………………………………………………………………………………………………………………………………………… 13 How heap sort works to sort a set of data. ………………………………………………………………………………………………………………. 3 How we can apply Find operation on elements combined through Union operation. …………………………………………………….. 14 Suppose we are sorting an array of eight integers using a some quadratic sorting algorithm. After four iterations of the algori ………………………………………………………………….. … 14 How many leaf and non-leaf nodes are present in a complete binary tree if its depth is 7 ? ……………………………………………. 14 If we insert a new element into an AVL tree of height 4, is one rotation sufficient to re-establish balance?
Justify your ……………………………………………………………………………………………………………………………………………………………… 14 Write down the C++ code from Selection Sort Algorithm. …………………………………………………………………………………………… 14 Consider the following data: ………………………………………………………………………………………………………………………………….. 14 Suppose we have build a Skip list . Now we want to add and remove items from the list .
Give Algorithms for insert (item) and delete (item) methods of the Skip List……………………………………………………………………………………………………………………… 15 SET-06 ……………………………………………………………………………………………………………………………………………………………………… 16 How we can search an element in Skip List. ……………………………………………………………………………………………………………… 6 What is the drawback of using arrays to store Binary Search Trees. …………………………………………………………………………… 16 Calculate the codes of the following characters in table below using the hoffman encoding tree, …………………………………… 16 “For smaller lists, linear insertion sort performs well, but for larger lists, quick sort is suitable to apply. ” Justify why? ………. 17 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. ………………….. 17 Give two different reasons to explain why the following binary tree is not a heap: ……………………………………………………….. 17 Here is an array of ten integers: ……………………………………………………………………………………………………………………………… 7 A long sequence of vowels needs to be transmitted efficiently so a programmer decides to use Huffman encoding to encode the vowels. A distribution count study of typical data yielded the following frequency table. …………………………………………. 17 Consider the following tree. …………………………………………………………………………………………………………………………………… 18 SET-07 ……………………………………………………………………………………………………………………………………………………………………… 8 Give one example of Hashing …………………………………………………………………………………………………………………………………. 18 How heap sort works to sort a set of data. ………………………………………………………………………………………………………………. 18 How we can implement Table ADT using Linked List………………………………………………………………………………………………….. 19 If we allow assignment to constants what will happen? ……………………………………………………………………………………………. 19 Explain the process of Deletion in a Min-Heap ………………………………………………………………………………………………………….. 19 Give any three characteristics of Union by Weight method. ……………………………………………………………………………………….. 19 “For smaller lists, linear insertion sort performs well, but for larger lists, quick sort is suitable to apply. Justify why? ………. 19 Write down the C++ code to implement Insertion Sort Algorithm. ………………………………………………………………………………. 19 Consider the following Threaded Binary Tree,…………………………………………………………………………………………………………… 19 What is Disjoint Sets? Explain with an example. ……………………………………………………………………………………………………….. 0 SET-08 ……………………………………………………………………………………………………………………………………………………………………… 20 Q) How we can degenerate a binary tree …………………………………………………………………………………………………………………. 20 Q) Define the following ………………………………………………………………………………………………………………………………………….. 0 The Height of the Tree: ………………………………………………………………………………………………………………………………………….. 20 The balance of a node: ………………………………………………………………………………………………………………………………………….. 20 Q) Give preorder and post order traversal for the following ……………………………………………………………………………………….. 20 Share your feedback/comments at pak. chd@gmail. com to improve file|| Back to TOP || File Version v3. 2. 0 published for Final Term CS301 Data Structure_ Muhammad Ishfaq Page No. 3 Q) Balancing AVL after inserting a node…………………………………………………………………………………………………………………… 21 SET-09 ……………………………………………………………………………………………………………………………………………………………………… 21 Write down the C++ code from Selection Sort Algorithm. ………………………………………………………………………………………….. 22 ? Build frequency table for the above data. ………………………………………………………………………………………………………… 22 ? Create a Huffman tree to determine the binary codes for each character. ……………………………………………………………. 22 ? What will be the code of each letter? ………………………………………………………………………………………………………………. 2 Suppose we have build a Skip list . Now we want to add and remove items from the list . Give Algorithms for insert (item) and delete (item) methods of the Skip List……………………………………………………………………………………………………………………… 22 SET-10 ……………………………………………………………………………………………………………………………………………………………………… 22 How we can search an element in Skip List. …………………………………………………………………………………………………………….. 22 What is the drawback of using arrays to store Binary Search Trees. …………………………………………………………………………… 22 Calculate the codes of the following characters in table below using the hoffman encoding tree, …………………………………… 23 “For smaller lists, linear insertion sort performs well, but for larger lists, quick sort is suitable to apply. ” Justify why? ………. 3 SET-11 ……………………………………………………………………………………………………………………………………………………………………… 25 SET-12 ……………………………………………………………………………………………………………………………………….. ……………………………. 27 SET-13 ……………………………………………………………………………………………………………………………………………………………………… 4 SET-14 ……………………………………………………………………………………………………………………………………………………………………… 37 SET-15 ……………………………………………………………………………………………………………………………………………………………………… 38 SET-16 ……………………………………………………………………………………………………………………………………………………………………… 1 SET-17 ……………………………………………………………………………………………………………………………………………………………………… 43 SET-18 ……………………………………………………………………………………………………………………………………………………………………… 44 SET-19 ……………………………………………………………………………………………………………………………………………………………………… 6 SET-21 ……………………………………………………………………………………………………………………………………………………………………… 49 Question: …………………………………………………………………………………………………………………………………………………………….. 49 SET-22 ……………………………………………………………………………………………………………………………………………………………………… 9 Question: …………………………………………………………………………………………………………………………………………………………….. 49 SET-23 ………………………………………………………………….. …………………………………………………………………………………………………. 50 Question: …………………………………………………………………………………………………………………………………………………………….. 0 SET-24 ……………………………………………………………………………………………………………………………………………………………………… 50 Question: …………………………………………………………………………………………………………………………………………………………….. 50 SET-25 ……………………………………………………………………………………………………………………………………………………………………… 0 Question: …………………………………………………………………………………………………………………………………………………………….. 50 SET-26 ……………………………………………………………………………………………………………………………………………………………………… 50 Question: …………………………………………………………………………………………………………………………………………………………….. 0 SET-27 ……………………………………………………………………………………………………………………………………………………………………… 50 Question: …………………………………………………………………………………………………………………………………………………………….. 50 SET-28 ……………………………………………………………………………………………………………………………………………………………………… 0 Question: …………………………………………………………………………………………………………………………………………………………….. 50 SET-29 ……………………………………………………………………………………………………………………………………………………………………… 50 Question: …………………………………………………………………………………………………………………………………………………………….. 0 SET-30 ……………………………………………………………………………………………………………………………………………………………………… 50 Question: …………………………………………………………………………………………………………………………………………………………….. 50 SET-31 ……………………………………………………………………………………………………………………………………………………………………… 0 Question: …………………………………………………………………………………………………………………………………………………………….. 50 SET-32 ……………………………………………………………………………………………………………………………………………………………………… 50 Question: …………………………………………………………………………………………………………………………………………………………….. 0 SET-33 ……………………………………………………………………………………………………………………………………………………………………… 51 Question: …………………………………………………………………………………………………………………………………………………………….. 51 SET-34 ……………………………………………………………………………………………………………………………………………………………………… 1 Question: ……………………………………………………………………………………………………………………………………….. …………………… 51 Share your feedback/comments at pak. nchd@gmail. com to improve file|| Back to TOP || File Version v3. 2. 0 published for Final Term CS301 Data Structure_ Muhammad Ishfaq Page No. 4 SET-35 ……………………………………………………………………………………………………………………………………………………………………… 1 Question: …………………………………………………………………………………………………………………………………………………………….. 51 MULTIPLE CHOICE QUESTION …………………………………………………………………………………………………………………………………. 51 SET-01 ……………………………………………………………………………………………………………………………………………………………………… 1 SET-02 ……………………………………………………………………………………………………………………………………………………………………… 55 SET-03 ……………………………………………………………………………………………………………………………………………………………………… 59 SET-04 ……………………………………………………………………………………………………………………………………………………………………… 3 SET-05 ……………………………………………………………………………………………………………………………………………………………………… 68 SET-06 ……………………………………………………………………………………………………………………………………….. ……………………………. 71 SET-07 ……………………………………………………………………………………………………………………………………………………………………… 3 SET-08 ……………………………………………………………………………………………………………………………………………………………………… 82 SET-09 ……………………………………………………………………………………………………………………………………………………………………… 90 SET-10 ……………………………………………………………………………………………………………………………………………………………………… 2 SET-11 ……………………………………………………………………………………………………………………………………………………………………. 102 Empty Set…………………………………………………………………………………………………………………………………………………………… 102 SET-12 ……………………………………………………………………………………………………………………………………………………………………. 02 Empty Set…………………………………………………………………………………………………………………………………………………………… 102 SET-13 ……………………………………………………………………………………………………………………………………………………………………. 103 SET-14 ……………………………………………………………………………………………………………………………………………………………………. 08 SET-15 ……………………………………………………………………………………………………………………………………………………………………. 116 SET-16 ………………………………………………………………….. ……………………………………………………………………………………………….. 125 SET-17 ……………………………………………………………………………………………………………………………………………………………………. 25 SET-18 ……………………………………………………………………………………………………………………………………………………………………. 125 SET-19 ……………………………………………………………………………………………………………………………………………………………………. 125 SET-20 ……………………………………………………………………………………………………………………………………………………………………. 25 SET-21 ……………………………………………………………………………………………………………………………………………………………………. 125 SET-22 ……………………………………………………………………………………………………………………………………………………………………. 125 SET-23 ……………………………………………………………………………………………………………………………………………………………………. 26 SET-24 ……………………………………………………………………………………………………………………………………………………………………. 126 SET-25 ……………………………………………………………………………………………………………………………………………………………………. 126 SET-26 ……………………………………………………………………………………………………………………………………………………………………. 26 SET-27 ……………………………………………………………………………………………………………………………………………………………………. 126 SET-28 ……………………………………………………………………………………………………………………………………………………………………. 126 =========================================================> Share your feedback/comments at pak. nchd@gmail. com to improve file|| Back to TOP || File Version v3. 2. 0 published for Final Term CS301 Data Structure_ Muhammad Ishfaq
Short Questions Paper Set-01 Page No. 5 Question No: 41 ( Marks: 2 ) Convert the given infix form to postfix form. A+B/C-D^E-F Question No: 42 ( Marks: 2 ) How we can implement Table ADT using Linked List Question No: 43 ( Marks: 2 ) If we allow assignment to constants what will happen? Question No: 44 ( Marks: 2 ) How heap sort works to sort a set of data. Question No: 46 ( Marks: 3 ) Give your comment on the statement that heap uses least memory in array representation of binary trees. Justify your answer in either case. Question No: 47 ( Marks: 3 ) How we can use concept of equivalence relations to generate a Maze.
Question No: 48 ( Marks: 3 ) “For smaller lists, linear insertion sort performs well, but for larger lists, quick sort is suitable to apply. ” Justify why? Question No: 49 ( Marks: 5 ) 695041732 Show the first five merging steps for Merge sort on this array. Question No: 50 ( Marks: 5 ) What is Disjoint Sets? Explain with an example. Question No: 51 ( Marks: 5 ) Write the code of the perculateDown() function and also comment it. Question No: 52 ( Marks: 5 ) Here is an array with exactly 15 elements: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15. Suppose that we are doing a binary search for an element.
Indicate any elements that will be found by examining two or fewer numbers from the array. Share your feedback/comments at pak. nchd@gmail. com to improve file|| Back to TOP || File Version v3. 2. 0 published for Final Term CS301 Data Structure_ Muhammad Ishfaq Page No. 6 ===================================================================== Set-02 Question No: 27 ( Marks: 2 ) Give one example of Hashing Question No: 28 ( Marks: 2 ) How heap sort works to sort a set of data. Question No: 29 ( Marks: 2 ) How we can implement Table ADT using Linked List Question No: 30 ( Marks: 2 ) If we allow assignment to constants what will happen?
Question No: 31 ( Marks: 3 ) Explain the process of Deletion in a Min-Heap Question No: 32 ( Marks: 3 ) Give any three characteristics of Union by Weight method. Question No: 33 ( Marks: 3 ) “For smaller lists, linear insertion sort performs well, but for larger lists, quick sort is suitable to apply. ” Justify why? Question No: 34 ( Marks: 5 ) Write down the C++ code to implement Insertion Sort Algorithm. Question No: 35 ( Marks: 5 ) Share your feedback/comments at pak. nchd@gmail. com to improve file|| Back to TOP || File Version v3. 2. 0 published for Final Term CS301 Data Structure_ Muhammad Ishfaq
Consider the following Threaded Binary Tree, Page No. 7 You have to give the values that should be in the four variables given below, for the node 37 1. LTH (Left flag) 2. RTH (Right flag) 3. Left node pointer (->L) 4. Right node pointer (->R) Question No: 36 ( Marks: 5 ) What is Disjoint Sets? Explain with an example. ===================================================================== Set-03 Question No: 27 ( Marks: 2 ) Give the difference between strict and complete binary tree. Ans: A tree is a strictly binary tree if its each leaf node has non-empty left and right sub trees, and If there are left and right ub-trees for each node in a binary tree is known as complete binary tree. Question No: 28 ( Marks: 2 ) A complete binary tree can be stored in an array. While storing the tree in an array we leave the first position (0th index )of the array empty. Why? Ans Because we need a pointer in an array to point a position of node of tree. parent node and the children nodes. In case of having a node with left and right children, stored at position i in the array, the left 2i and the right child will be at 2i+1 position. If the value Share your feedback/comments at pak. nchd@gmail. com to improve file|| Back to TOP || File Version v3. . 0 published for Final Term CS301 Data Structure_ Muhammad Ishfaq Page No. 8 of i 2, the parent will be at position 2 and the left child will be at position 2i i. e. 4 . The right child will be at position 2i+1 i. e. 5. we have not started the 0th position. It is simply due to the fact if the position is 0, 2i will also become 0. So we will start from the 1st position, ignoring the 0th. Question No: 29 ( Marks: 2 ) Give the name of two Divide and Conquer algorithms. Ans: 1. Merge sort 2. Quick sort 3. Heap sort Question No: 30 ( Marks: 2 ) Give the effect of sorted data on Binary Search. Question No: 31 ( Marks: 3
Give any three characteristics of Union by Weight method. Ans: 1. 2. 3. 4. to This is also calles union by size. Maintain sizes (number of nodes) of all trees, and during union. Make smaller tree, the subtree of the larger one. for each root node i, instead of setting parent[i] to -1, set it -k if tree rooted at i has k nodes. ( Marks: 3 ) Question No: 32 Here is an array of ten integers: 5 3 8 9 1 7 0 2 6 4 Draw this array after the FIRST iteration of the large loop in an insertion sort (sorting from smallest to largest). This iteration has shifted at least one item in the array! Question No: 33 ( Marks: 3 )
Give your comment on the statement that heap uses least memory in array representation of binary trees. Justify your answer in either case. Question No: 34 ( Marks: 5 ) Share your feedback/comments at pak. nchd@gmail. com to improve file|| Back to TOP || File Version v3. 2. 0 published for Final Term CS301 Data Structure_ Muhammad Ishfaq Page No. 9 Suppose we have the following representation for a complete Binary Search Tree, tell the Left and Right child nodes and Parent node of the node D A 0 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8 I 9 J 1 0 K 1 1 L 1 2 M N 1 3 1 4 O 1 5 P 1 6 Q 1 7 R 1 8 S 1 9 T 2 0 … … Question No: 35 Marks: 5 ) Explain the following terms: 1. Collision 2. Linear Probing 3. Quadratic Probing Ans: Collision: it takes place when two or more keys (data items) produce the same index. Linear Probing when there is a collision, some other location in the array is found. This is known as linear probing. In linear probing, at the time of collisions, we add one to the index and check that location. If it is also not empty, we add 2 and check that position. Suppose we keep on incrementing the array index and reach at the end of the table. We were unable to find the space and reached the last location of the array.
Quadratic Probing In the quadratic probing when a collision happens we try to find the empty location at index + 12. If it is filled then we add 22 and so on. Quadratic probing uses different formula: Use F(i) = i2 (square of i) to resolve collisions 2. If hash function resolves to H and a search in cell H is inconclusive, try H + 12, H + 22, H + 32 1. Question No: 36 ( Marks: 5 ) Share your feedback/comments at pak. nchd@gmail. com to improve file|| Back to TOP || File Version v3. 2. 0 published for Final Term CS301 Data Structure_ Muhammad Ishfaq Here is an array with exactly 15 elements: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15.
Page No. 10 Suppose that we are doing a binary search for an element. Indicate any elements that will be found by examining two or fewer numbers from the array. ===================================================================== Set-04 Question No: 33 ( Marks: 2 ) How we can search an element in Skip List. Question No: 34 ( Marks: 2 ) What is the drawback of using arrays to store Binary Search Trees. Question No: 35 ( Marks: 3 ) Calculate the codes of the following characters in table below using the hoffman encoding tree, Share your feedback/comments at pak. nchd@gmail. com to improve file|| Back to TOP || File Version v3. . 0 published for Final Term CS301 Data Structure_ Muhammad Ishfaq charac ter NL SP o b i r Question No: 36 Code 10000 1111 001 0100 0101 110 ( Marks: 3 ) Page No. 11 “For smaller lists, linear insertion sort performs well, but for larger lists, quick sort is suitable to apply. ” Justify why? Question No: 37 ( Marks: 3 ) 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. A. The reheapification is done. B. The next step will swap the out-of-place node with its parent. C. The next step will swap the out-of-place node with its left child. D. The next step will swap the out-of-place node with its right child. E. None of these. Question No: 38 ( Marks: 5 ) Give two different reasons to explain why the following binary tree is not a heap: Share your feedback/comments at pak. nchd@gmail. com to improve file|| Back to TOP || File Version v3. 2. 0 published for Final Term CS301 Data Structure_ Muhammad Ishfaq Page No. 12 Question No: 39 Marks: 5 ) Here is an array of ten integers: 5389170264 Sort the array by using selection sort algorithm and show content of array after each step. 5 STEP 1 STEP 2 0 0 3 3 1 1 1 1 1 1 1 1 8 8 8 2 2 2 2 2 2 2 9 9 9 9 3 3 3 3 3 3 1 1 3 3 9 4 4 4 4 4 7 7 7 7 7 7 5 5 5 5 0 5 5 5 5 5 7 6 6 6 2 2 2 8 8 8 8 8 7 7 6 6 6 6 6 6 6 7 8 8 4 4 4 4 4 9 9 9 9 9 STEP3 0 STEP 4 0 STEP5 0 STEP6 0 STEP 7 0 STEP8 0 0 Question No: 40 ( Marks: 10 ) A long sequence of vowels needs to be transmitted efficiently so a programmer decides to use Huffman encoding to encode the vowels. A distribution count study of typical data yielded the following frequency table.
Frequency Table Share your feedback/comments at pak. nchd@gmail. com to improve file|| Back to TOP || File Version v3. 2. 0 published for Final Term CS301 Data Structure_ Muhammad Ishfaq character A E I O U Y frequency Huffman code 33978 20676 15814 21552 10324 4975 _______ _______ _______ _______ _______ _______ Page No. 13 A) Create a Huffman tree to determine the binary codes for each character. B) Fill the codes into the table above. C) Encode the following sequence EIYOUA Question No: 41 ( Marks: 10 ) Consider the following tree. a) Show that either it is a heap or not. b) If it is a heap then what type of heap is it? ) Add 40 in the heap and convert it in max heap. ===================================================================== Set-05 Question No: 33 ( Marks: 2 ) How heap sort works to sort a set of data. Question No: 34 ( Marks: 2 ) Share your feedback/comments at pak. nchd@gmail. com to improve file|| Back to TOP || File Version v3. 2. 0 published for Final Term CS301 Data Structure_ Muhammad Ishfaq Page No. 14 How we can apply Find operation on elements combined through Union operation. Question No: 35 ( Marks: 3 ) How we can use concept of equivalence relations to generate a Maze. Question No: 36 ( Marks: 3 )
Suppose we are sorting an array of eight integers using a some quadratic sorting algorithm. After four iterations of the algorithm’s main loop, the array elements are ordered as shown here: 2 4 5 7 8 1 3 6 Which statement is correct? (Note: Our selectionsort picks largest items first. ) A. The algorithm might be either selectionsort or insertionsort. B. The algorithm might be selectionsort, but it is not insertionsort. C. The algorithm is not selectionsort, but it might be insertionsort. (Correct) D. The algorithm is neither selectionsort nor insertionsort. E. None of these. Question No: 37 ( Marks: 3 )
How many leaf and non-leaf nodes are present in a complete binary tree if its depth is 7 ? Solution: Leaf nodes = 2^7=128 Non-leaf nodes =127 Question No: 38 ( Marks: 5 ) If we insert a new element into an AVL tree of height 4, is one rotation sufficient to reQuestion No: 39 ( Marks: 5 ) Write down the C++ code from Selection Sort Algorithm. Question No: 40 ( Marks: 10 ) Consider the following data: Share your feedback/comments at pak. nchd@gmail. com to improve file|| Back to TOP || File Version v3. 2. 0 published for Final Term CS301 Data Structure_ Muhammad Ishfaq the cat in the hat Page No. 15 ) Build frequency table for the above data. b) Create a Huffman tree to determine the binary codes for each character. c) What will be the code of each letter? a) Character Frequency c i n e a h t sp c) Question No: 41 ( Marks: 10 ) 1 1 1 2 2 3 4 4 Character Code c i n e a h t sp 0000 0001 0010 0011 010 011 10 11 Suppose we have build a Skip list . Now we want to add and remove items from the list . Give Algorithms for insert (item) and delete (item) methods of the Skip List. Solution: When we are going to insert (add) an item (x,0) into a skip list, we use a randomized algorithm. We send the item in a pair. nsert To insert an item (x, o) into a skip list, we use a randomized algorithm: • • • • delete Share your feedback/comments at pak. nchd@gmail. com to improve file|| Back to TOP || File Version v3. 2. 0 published for Final Term We repeatedly toss a coin until we get tails, and we denote with i the number of times the coin came up heads If i ? h, we add to the skip list new lists Sh+1, … , Si +1, each containing only the two special keys We search for x in the skip list and find the positions p0, p1 , …, pi of the items with largest key less than x in each list S0, S1, … , Si For j ? , …, i, we insert item (x, o) into list Sj after position pj CS301 Data Structure_ Muhammad Ishfaq To remove an item with key x from a skip list, we proceed as follows: • • • Page No. 16 We search for x in the skip list and find the positions p0, p1 , …, pi of the items with key x, where position pj is in list Sj We remove positions p0, p1 , …, pi from the lists S0, S1, … , Si We remove all but one list containing only the two special key ===================================================================== Set-06 Question No: 33 ( Marks: 2 ) How we can search an element in Skip List.
Question No: 34 Question No: 35 ( Marks: 2 ) ( Marks: 3 ) What is the drawback of using arrays to store Binary Search Trees. Calculate the codes of the following characters in table below using the hoffman encoding tree, charac ter NL SP code Share your feedback/comments at pak. nchd@gmail. com to improve file|| Back to TOP || File Version v3. 2. 0 published for Final Term CS301 Data Structure_ Muhammad Ishfaq o b i r Question No: 36 ( Marks: 3 ) Page No. 17 “For smaller lists, linear insertion sort performs well, but for larger lists, quick sort is suitable to apply. ” Justify why?
Question No: 37 ( Marks: 3 ) 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. A. The reheapification is done. B. The next step will swap the out-of-place node with its parent. C. The next step will swap the out-of-place node with its left child. D. The next step will swap the out-of-place node with its right child.
E. None of these. Question No: 38 ( Marks: 5 ) Give two different reasons to explain why the following binary tree is not a heap: Question No: 39 ( Marks: 5 ) Here is an array of ten integers: 5389170264 Sort the array by using selection sort algorithm and show content of array after each step. Question No: 40 ( Marks: 10 ) A long sequence of vowels needs to be transmitted efficiently so a programmer decides to use Huffman encoding to encode the vowels. A distribution count study of typical data yielded the following frequency table. Share your feedback/comments at pak. nchd@gmail. om to improve file|| Back to TOP || File Version v3. 2. 0 published for Final Term CS301 Data Structure_ Muhammad Ishfaq Frequency Table character frequency Huffman code A 33978 _______ E 20676 _______ I 15814 _______ O 21552 _______ U 10324 _______ Y 4975 _______ Page No. 18 A) Create a Huffman tree to determine the binary codes for each character. B) Fill the codes into the table above. C) Encode the following sequence EIYOUA Question No: 41 ( Marks: 10 ) Consider the following tree. d) e) f) Show that either it is a heap or not. If it is a heap then what type of heap is it?
Add 40 in the heap and convert it in max heap. ===================================================================== Set-07 Question No: 27 ( Marks: 2 ) Give one example of Hashing Question No: 28 ( Marks: 2 ) How heap sort works to sort a set of data. Question No: 29 ( Marks: 2 ) Share your feedback/comments at pak. nchd@gmail. com to improve file|| Back to TOP || File Version v3. 2. 0 published for Final Term CS301 Data Structure_ Muhammad Ishfaq Page No. 19 How we can implement Table ADT using Linked List Question No: 30 ( Marks: 2 ) If we allow assignment to constants what will happen?
Question No: 31 ( Marks: 3 ) Explain the process of Deletion in a Min-Heap Question No: 32 ( Marks: 3 ) Give any three characteristics of Union by Weight method. Question No: 33 ( Marks: 3 ) “For smaller lists, linear insertion sort performs well, but for larger lists, quick sort is suitable to apply. ” Justify why? Question No: 34 ( Marks: 5 ) Write down the C++ code to implement Insertion Sort Algorithm. Question No: 35 ( Marks: 5 ) Consider the following Threaded Binary Tree, Share your feedback/comments at pak. nchd@gmail. com to improve file|| Back to TOP || File Version v3. 2. 0 published for Final Term
CS301 Data Structure_ Muhammad Ishfaq Page No. 20 You have to give the values that should be in the four variables given below, for the node 37 5. 6. 7. 8. LTH (Left flag) RTH (Right flag) Left node pointer (-;L) Right node pointer (-;R) ( Marks: 5 ) Question No: 36 What is Disjoint Sets? Explain with an example. ===================================================================== Set-08 Q) How we can degenerate a binary tree Q) Why we use queue data structure for level order traversal? Q) Define the following The Height of the Tree: The balance of a node: Q) Give preorder and post order traversal for the following
Share your feedback/comments at pak. nchd@gmail. com to improve file|| Back to TOP || File Version v3. 2. 0 published for Final Term CS301 Data Structure_ Muhammad Ishfaq 50 Page No. 21 30 54 25 33 52 60 26 39 53 Q) Balancing AVL after inserting a node ===================================================================== Set-09 Question No: 33 ( Marks: 2 ) How heap sort works to sort a set of data. Question No: 34 ( Marks: 2 ) How we can apply Find operation on elements combined through Union operation. Question No: 35 ( Marks: 3 ) How we can use concept of equivalence relations to generate a Maze.
Question No: 36 ( Marks: 3 ) Suppose we are sorting an array of eight integers using a some quadratic sorting algorithm. After four iterations of the algorithm’s main loop, the array elements are ordered as shown here: 2 4 5 7 8 1 3 6 Which statement is correct? (Note: Our selectionsort picks largest items first. ) A. The algorithm might be either selectionsort or insertionsort. B. The algorithm might be selectionsort, but it is not insertionsort. C. The algorithm is not selectionsort, but it might be insertionsort. (Correct) D. The algorithm is neither selectionsort nor insertionsort. E. None of these.
Question No: 37 ( Marks: 3 ) Share your feedback/comments at pak. nchd@gmail. com to improve file|| Back to TOP || File Version v3. 2. 0 published for Final Term CS301 Data Structure_ Muhammad Ishfaq Page No. 22 How many leaf and non-leaf nodes are present in a complete binary tree if its depth is 7 ? Question No: 38 ( Marks: 5 ) If we insert a new element into an AVL tree of height 4, is one rotation sufficient to reestablish balance? Justify your answer. Question No: 39 ( Marks: 5 ) Write down the C++ code from Selection Sort Algorithm. Question No: 40 ( Marks: 10 ) Consider the following data: the cat in the hat ? ? Build frequency table for the above data. Create a Huffman tree to determine the binary codes for each character. What will be the code of each letter? ( Marks: 10 ) Question No: 41 Suppose we have build a Skip list . Now we want to add and remove items from the list . Give Algorithms for insert (item) and delete (item) methods of the Skip List. ===================================================================== Set-10 Question No: 33 ( Marks: 2 ) How we can search an element in Skip List. Question No: 34 ( Marks: 2 ) What is the drawback of using arrays to store Binary Search Trees.
Question No: 35 ( Marks: 3 ) Share your feedback/comments at pak. nchd@gmail. com to improve file|| Back to TOP || File Version v3. 2. 0 published for Final Term CS301 Data Structure_ Muhammad Ishfaq Page No. 23 Calculate the codes of the following characters in table below using the hoffman encoding tree, charac ter NL SP o b i r Question No: 36 code ( Marks: 3 ) “For smaller lists, linear insertion sort performs well, but for larger lists, quick sort is suitable to apply. ” Justify why? Question No: 37 ( Marks: 3 ) 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 Share your feedback/comments at pak. nchd@gmail. com to improve file|| Back to TOP || File Version v3. 2. 0 published for Final Term CS301 Data Structure_ Muhammad Ishfaq Page No. 24 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. A. The reheapification is done. B. The next step will swap the out-of-place node with its parent. C. The next step will swap the out-of-place node with its left child.
D. The next step will swap the out-of-place node with its right child. E. None of these. Question No: 38 ( Marks: 5 ) Give two different reasons to explain why the following binary tree is not a heap: Question No: 39 ( Marks: 5 ) Here is an array of ten integers: 5389170264 Sort the array by using selection sort algorithm and show content of array after each step. Question No: 40 ( Marks: 10 ) A long sequence of vowels needs to be transmitted efficiently so a programmer decides to use Huffman encoding to encode the vowels. A distribution count study of typical data yielded the following frequency table.
Frequency Table character frequency Huffman code A 33978 _______ E 20676 _______ I 15814 _______ O 21552 _______ U 10324 _______ Y 4975 _______ Share your feedback/comments at pak. nchd@gmail. com to improve file|| Back to TOP || File Version v3. 2. 0 published for Final Term CS301 Data Structure_ Muhammad Ishfaq Page No. 25 A) Create a Huffman tree to determine the binary codes for each character. B) Fill the codes into the table above. C) Encode the following sequence EIYOUA Question No: 41 ( Marks: 10 ) Consider the following tree. a) Show that either it is a heap or not. ) If it is a heap then what type of heap is it? c) Add 40 in the heap and convert it in max heap. ===================================================================== Set-11 Question No: 17 ( Marks: 2 ) AVL Tree is, > Non Linear data structure > Linear data structure > Hybrid data structure (Mixture of Linear and Non Linear) > None of the given options. Question No: 18 ( Marks: 2 ) How we can delete a node with two Childs in a binary search tree using its right sub tree. Question No: 19 ( Marks: 2 ) What is Function Call Stack Give short answer. Question No: 20 ( Marks: 3 ) Share your feedback/comments at pak. chd@gmail. com to improve file|| Back to TOP || File Version v3. 2. 0 published for Final Term CS301 Data Structure_ Muhammad Ishfaq Explain the two cases in which we apply double rotation in an AVL tree. Question No: 21 ( Marks: 3 ) Page No. 26 Here is a small binary tree. Write the order of the nodes visited in a) A Post-order traversal b) A level-order traversal Question No: 22 ( Marks: 5 ) Please consider the following AVL tree. 1. Insert new node 87 in this tree and make tree balance. 2. Write balance factor of each node after and before inserting node 87. Question No: 23 ( Marks: 5 )
Share your feedback/comments at pak. nchd@gmail. com to improve file|| Back to TOP || File Version v3. 2. 0 published for Final Term CS301 Data Structure_ Muhammad Ishfaq Consider the following binary tree Page No. 27 Show the state of the tree after deleting 24. ===================================================================== Set-12 Question No: 32 ( Marks: 3 ) Consider the following Min Heap apply operation delMin on it and show the resultant Heap,? 5 Solution: Delmin()//mean delete the min node in min heap we clearly see that min node vale is a 6 9 rood node so we apply as First delete the root node vale 8 7 1 2 13
After delete root we 6 compare the left and right node value and small value put in root as: 9 6 8 7 1 2 13 Repeat again above operation: 6 9 Share your feedback/comments at pak. nchd@gmail. com to improve file|| Back to TOP || File Version v3. 2. 0 published for Final Term CS301 Data Structure_ Muhammad Ishfaq Page No. 28 6 After delmin() resultant heap is: 9 Question No: 35 ( Marks: 5 ) Here is an array of ten integers: 5389170264 Show the first three merging steps for Merge sort on this array. Solution: 8 1 5 3 8 9 1 7 0 2 6 2 First Step: Split the list into two parts 5 3 8 |Second Step is : Sort the two parts 1 3 5 9 8 1 9 7 0 0 2 2 4 6 6 4 13 4 7 Third Step is: Merge the two parts together 1 3 5 8 9 0 2 4 6 7 Question No: 36 ( Marks: 5 ) Consider the following sequence of union commands on the set of elements {1,2,3,4, 5}: union(4,2) union(3,1) union(5,4) union(5,3) Show the result when the unions are performed Solution: 1 union(4,2) 2 4 3 4 5 union(3,1) union(5,4) 5 3 2 Share your feedback/comments at pak. nchd@gmail. com to improve file|| Back to TOP || File Version v3. 2. 0 published for Final Term 1 CS301 Data Structure_ Muhammad Ishfaq union(5,3) 5 Page No. 29 Question No: 31 ( Marks: 1 ) 4 Describe the conditions for second case of deletion in AVL Trees. Answer: The node to be deleted has either left child (subtree) or right child (subtree). In this case we bypass the node in such a way that2we find the inorder successor of this node and 1 then link the parent of the node to be deleted to this successor node. Thus the node was deleted. Question No: 32 ( Marks: 1 ) What is Table abstract data type. Answer: An abstract data structure is a mathematical model for a certain class of data structures that have similar behavior; or for certain data types of one or more programming languages that have similar semantics.
Question No: 33 ( Marks: 2 ) How we can generate a maze . Give an algorithm. Answer: A maze can be generated by starting with a predetermined arrangement of cells (most commonly a rectangular grid but other arrangements are possible) with wall sites between them. This predetermined arrangement can be considered as a connected graph with the edges representing possible wall sites and the nodes representing cells. The algorithm is as follows: • Randomly remove walls until the entrance and exit cells are in the same set. • Removal of the wall is the same as doing a union operation. Do not remove a randomly chosen wall if the cells it separates are already in the same set. Question No: 34 ( Marks: 2 ) Represent the following Binary tree using array representation. Share your feedback/comments at pak. nchd@gmail. com to improve file|| Back to TOP || File Version v3. 2. 0 published for Final Term CS301 Data Structure_ Muhammad Ishfaq Page No. 30 A 0 1 2 Question No: 35 B 3 C 4 5 D 6 E 7 What is an ( Marks: 3 ) Equivalent relation? Give any two examples. A binary relation R over a set S is called an equivalence relation if it has following Properties 1.
Reflexivity: for all element x ? S, x R x 2. Symmetry: for all elements x and y, x R y if and only if y R x 3. Transitivity: for all elements x, y and z, if x R y and y R z then x R z Question No: 36 ( Marks: 3 ) “For smaller lists, linear insertion sort performs well, but for larger lists, quick sort is suitable to apply. ” Justify why? http://vuattach. ning. com/ Quicksort sorts by employing a divide and conquer strategy to divide a list into two sublists. Full example of quicksort on a random set of numbers. The boxed element is the pivot. It is always chosen as the last element of the partition.
The steps are: 1. Pick an element, called a pivot, from the list. 2. Reorder the list so that all elements which are less than the pivot come before the pivot and so that all elements greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation. 3. Recursively sort the sub-list of lesser elements and the sub-list of greater elements Question No: 37 ( Marks: 3 ) How many leaf and non-leaf nodes are present in a complete binary tree if its depth is 7 ?
We know that the total number of nodes (leaf and non-leaf) of a complete binary tree of depth d is equal to 2d+1 – 1. It can be calculated as 27=14 nodes Question No: 38 ( Marks: 5 ) Share your feedback/comments at pak. nchd@gmail. com to improve file|| Back to TOP || File Version v3. 2. 0 published for Final Term CS301 Data Structure_ Muhammad Ishfaq Page No. 31 Remove the smallest element from the following array which represents a min-heap. original minheap 1 3 2 5 4 8 9 1 0 7 and show the resultant heap in the form of array as shown below, after removal 2 3 8 5 4 9 1 0 7 Question No: 39 Marks: 5 ) Here is an array with exactly 15 elements: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15. Suppose that we are doing a binary search for an element. Indicate any elements that will be found by examining two or fewer numbers from the array. http://vuattach. ning. com/ Question No: 31 ( Marks: 1 ) In merge sort do we need to have extra memory, justify your answer in either case. Ans: ? Merge sort requires additional memory proportional to the size of the input for scratch space, but, unlike heap sort, merge sort is stable, meaning that “equal” elements are ordered the same once sorting is complete ?
Merge sort works using the principle that if you have two sorted lists, you can merge them together to form another sorted list. Consequently, sorting a large list can be thought of as a problem of sorting two smaller lists and then merging those two lists together Question No: 32 ( Marks: 1 ) Where is Inorder Predecessor of a non leaf node is present in a Binary Search Tree? Ans: Inorder Predecessor of a non leaf node is present at rightmost child of left subtree present in a Binary Search Tree……. Question No: 33 ( Marks: 2 ) How we can search an element in Skip List. Ans:
Share your feedback/comments at pak. nchd@gmail. com to improve file|| Back to TOP || File Version v3. 2. 0 published for Final Term CS301 Data Structure_ Muhammad Ishfaq Page No. 32 skip list can be used as the underlying storage for a sorted set data structure. But, skip list can be directly used to implement some operations that are not efficient on a typical sorted set: ? Find the element in the set that is closest to some given value, in O(log N) time. ? Find the k-th largest element in the set, in O(log N) time. Requires a simple augmentation of the the skip list with partial counts. Count the number of elements in the set whose values fall into a given range, in O(log N) time. Also requires a simple augmentation of the skip list. Question No: 34 ( Marks: 2 ) What is the drawback of using arrays to store Binary Search Trees. Ans: We used the binary search algorithm to find data stored in an array. This method is very effective as each iteration reduced the number of items to search by one-half. However since data was stored in an array insertions and deletions were not efficient. Binary search trees store data in nodes that are linked in a tree-like fashion.
For randomly inserted data search time is O(lg n). Worst-case behavior occurs when ordered data is inserted. In this case the search time is O(n). Question No: 35 ( Marks: 3 ) Calculate the codes of the following characters in table below using the hoffman encoding tree, Share your feedback/comments at pak. nchd@gmail. com to improve file|| Back to TOP || File Version v3. 2. 0 published for Final Term CS301 Data Structure_ Muhammad Ishfaq Page No. 33 charac ter NL SP o b i r Ans: charac ter NL SP