CS301 VU Current Final Paper Spring July 2012

Total 52 Q’s,40 mcq,s 120min
1) For a perfect binary tree of height 5,what will be the sum of heights of nodes? 2marks
2) Properties of equivalence class.
3) Two ways for the implementation of Queue data structure.
4) Worst case of selection sort
5) Max heap, add 24 3 marks
6) “is a sibling of” set of all human beings is equivalence relation or not? explain.
7) Linked memory
8) 3 5 9 8 1 7 0 2 6 4 , draw after the 1st iteration of large loop in a selection sort (smallest to largest)
9) Union commands 1, 2, 3, 4, 5 union(4,2),union(3,1),union(5,4) 5 marks
10) Code for removing an element froma linked list data structureif it is implementationby using linked memory methods.
11) Fill the hash table ofsize 11 that results when u insert the keys 19, 6, 16, 8, 5, 13, 1
12) Draw an heap that is created by removing VU solutions one item from the heap.
911
77 66
68 1 3 11

Paper 2

40 mcqs thy kuch past papers me sy ay or kuch new thy
2 no k 4 quiz thy
3 no k b 4 quiz thy
or 5 no k b 4 quiz thy
paper time 2 hours tha

long quiz jo mujhy yaad hy woh yeh hy:

1) How we can implement Table ADT using Linked List (marks 2)

2) which three basic operations are performed on AVL trees (mark 3)

3)write down the c++ code to impliment insertion sort algorithm (5)

4) 1 tree diya huwa tha us ki in-order or post-order traversing karni thi (marks 5)

5)Give the name of three Divide and Conquer algorithms. (marks 3)

6) 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! (marks 3)

7) Union or find ka code likhna tha (marks 5)

CS301 Fall 2011 Final Term 16 Feb 2012

TOTAL QUESTIONS: 52:
MCQs: 40:

Subjective paper is here:
Q: 41: How can we generate maze. Give an algorithm. MARKS: 2:
Q: 42: The relation “>” between real numbers is equivalence relation or not? Explain. MARKS: 2:
Q: 43: What is meant by the following statement in context of linked list data structure?

Node* new Node = new Node(9); MARKS: 2:
Q: 44: Give the names of any two Nlog(N) sorting algorithm. MARKS: 2:
Q: 45: Give any three characteristics of Union by weight methode. MARKS: 3:
Q: 46: “For smaller list linear insertion sort performs well, but for larger lists, quick sort is suitable to apply. Why? MARKS: 3:
Q: 47: The relation “is a sibling of” (used to pairs of distict people, who have the same Parents) on the set of all human beings is equivalence relation or not? Explain. MARKS: 3:
Q: 48: Write down the code for isEmpty() and isFull() functions of the stack data structure implemented through arrays.
MARKS: 3:
Q: 49: Give an array of ontegers. Draw a maximum heap and show the final updates array.
12 57 19 87 15 44 23 MARKS: 5:
Q: 50: Here is an array of 15 elements :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Suppose that we have Binary search tree for an element.
Indicate any element will be found by examining two or few numbers from the array. MARKS: 5:
Q: 51: If we use linked list implemented push and pop stack. What is the better side for Push an element and also for Pop an element in to the array. MARKS: 5:

CS301 Assignment No 5 Solution Spring July 2012

 CS301 Assignment No 5 Solution Spring July 2012

Question # 1:-
Consider the following MAX HEAP, represent this heap in the form of an array, start the array index from 1 instead of 0.

Solution:-

25

23

15

18

12

7

5

10

14

11

6

3

4

2

0       1       2       3       4     5   6     7    8       9       10   11    12      13     14

Question # 2:-
Consider the following array, the value on each index of this array represents the node value of a complete binary tree, you are required to create the complete binary tree from this array.
Solution:-


Hints:
If “i” is an index of a node then “2i”, “2i +1” and “i/2” represent the left child, right child and parent of the this node respectively.

GDB Cs301 spring 2012

GDB Cs301 spring 2012
 June 25, 2012

GDB
Suppose you are given a task to develop an electronic phone book in which you have to store   names   and   phone   numbers   of   employees   of   a   company.   The   data   structures available to you are linked list and Binary Search Tree (BST) and you have to choose only one data structure. Moreover, while selecting any data structure, you also have to keep in consideration insertion, deletion and search operations, because, the company can hire   some   new   employees,   search   for   an   employee’s   phone   number   and   some   old employees can also leave this company. Discuss which data structure do you think would be more suitable for the above discussed scenario. Also discuss the reason why would you prefer this data structure over the other?
Solution 1:
A binary search tree will provide logarithmic searching which is pretty good. Insertions or deletions will be more costly because they may require some tree re balancing. For your linked list, are you still going to keep the data in order or just stuff the nodes one after another. If you are putting them in no order, retrieval will be slow (linear) and insertions and deletions still won't be that fast. The problem with a linked list, if I remember correctly, is that you can't jump in the middle of a linked list. You start at the root and go to the next node then the next, etc. So you really can't perform a binary search or any kind of hashing on the data
Solution 2: 
the most popular variation of the Binary Tree is the Binary Search Tree (BST). BST,s are used to quickly and efficiently search for an item in a collection. Say, for example, that you had a linked list of 1000 items, and you wanted to find if a single item exists within the list. You would be required to linearly look at every node starting from the beginning until you found it. If you're lucky, you might find it at the beginning of the list. However, it might also be at the end of the list, which means that you must search every item before it. This might not seem like such a big problem, especially nowadays with our super fast computers, but imagine if the list was much larger, and the search was repeated many times. Such searches frequently happen on web servers and huge databases, which makes the need for a much faster searching technique much more apparent. Binary Search Trees aim to Divide and conquer the data, reducing the search time of the collection and making it several times faster than any linear sequential search.