ALL UNIVERSITIES AND SERVICE COMMISSIONS PAST PAPERS IN PAKISTAN: Complete Solved CS301- Data Structures Final term Past Paper Of VU

Monday, December 27, 2010

Complete Solved CS301- Data Structures Final term Past Paper Of VU

FINALTERM EXAMINATION

Fall 2009

CS301- Data Structures (Session - 1)

Time: 120 min

Marks: 75

http://www.allvupastpapers.blogspot.com/

Question No: 1 ( Marks: 1 ) - Please choose one

The data of the problem is of 2GB and the hard disk is of 1GB capacity, to solve this problem we should

► Use better data structures

► Increase the hard disk space

► Use the better algorithm

► Use as much data as we can store on the hard disk

Question No: 2 ( Marks: 1 ) - Please choose one

In an array list the current element is

► The first element

► The middle element

► The last element

► The element where the current pointer points to

Question No: 3 ( Marks: 1 ) - Please choose one

Which one of the following is a valid postfix expression?

► ab+c*d-

► abc*+d-

► abc+*d-

► (abc*)+d-

Question No: 4 ( Marks: 1 ) - Please choose one

In sequential access data structure, accessing any element in the data structure takes different amount of time. Tell which one of the following is sequential access data structure, Linked list

► Arrays

► Lists

► Both of these

► None of these

http://www.allvupastpapers.blogspot.com/

Question No: 5 ( Marks: 1 ) - Please choose one

I have implemented the queue with a circular array. If data is a circular array of CAPACITY elements, and last is an index into that array, what is the formula for the index after last?

► (last % 1) + CAPACITY

► last % (1 + CAPACITY)

► (last + 1) % CAPACITY

► last + (1 % CAPACITY)

Question No: 6 ( Marks: 1 ) - Please choose one

Which one of the following is TRUE about recursion?

► Recursion extensively uses stack memory.

► Threaded Binary Trees use the concept of recursion.

► Recursive function calls consume a lot of memory.

► Iteration is more efficient than iteration.

http://www.allvupastpapers.blogspot.com/

Question No: 7 ( Marks: 1 ) - Please choose one

Compiler uses which one of the following to evaluate a mathematical equation,

►Binary Tree

►Binary Search Tree

►Parse Tree

►AVL Tree

Question No: 8 ( Marks: 1 ) - Please choose one

Which one of the following is TRUE about iteration?

►Iteration extensively uses stack memory.

►Threaded Binary Trees use the concept of iteration.

►Iterative function calls consumes a lot of memory.

►Recursion is more efficient than iteration.

http://www.allvupastpapers.blogspot.com/

Question No: 9 ( Marks: 1 ) - Please choose one

If a max heap is implemented using a partially filled array called data, and the array contains n elements (n > 0), where is the entry with the greatest value? Data[0]

► data[1]

► data[n-1]

► data[n]

► data[2*n+1]

Question No: 10 ( Marks: 1 ) - Please choose one

If there are 56 internal nodes in a binary tree then how many external nodes this binary tree will have?

► 54

► 55

► 56

► 57

Question No: 11 ( Marks: 1 ) - Please choose one

Which of the following heap method increase the value of key at position ‘p’ by the amount ‘delta’?

► increaseKey(p,delta)

► decreaseKey(p,delta)

► preculateDown(p,delta)

► remove(p,delta)

http://www.allvupastpapers.blogspot.com/

Question No: 12 ( Marks: 1 ) - Please choose one

If we have 1000 sets each containing a single different person. Which of the following relation will be true on each set:

► Reflexive

► Symmetric

► Transitive

► Associative

Question No: 13 ( Marks: 1 ) - Please choose one

Which one of the following is not an example of equivalence relation:

► Electrical connectivity

► Set of people

► <= relation

► Set of pixels

Question No: 14 ( Marks: 1 ) - Please choose one

A binary tree of N nodes has _______.

► Log₁₀ N levels

► Log₂ N levels

► N / 2 levels

► N x 2 levels

http://www.allvupastpapers.blogspot.com/

Question No: 15 ( Marks: 1 ) - Please choose one

Binary Search is an algorithm of searching, used with the ______ data.

► Sorted

► Unsorted

► Heterogeneous

► Random

Question No: 16 ( Marks: 1 ) - Please choose one

Consider te following array

23 15 5 12 40 10 7

After the first pass of a particular algorithm, the array looks like

1. 5 12 23 10 7 40

Name the algorithm used

► Heap sort

► Selection sort

► Insertion sort

► Bubble sort

Question No: 17 ( Marks: 1 ) - Please choose one

Which of the following statements is correct property of binary trees?

► A binary tree with N internal nodes has N+1 internal links.

► A binary tree with N external nodes has 2N internal nodes.

► A binary tree with N internal nodes has N+1 external nodes.

► None of above statement is a property of the binary tree.

Question No: 18 ( Marks: 1 ) - Please choose one

Which of the following is a property of binary tree?

► A binary tree of N external nodes has N internal node.

► A binary tree of N internal nodes has N+ 1 external node.

► A binary tree of N external nodes has N+ 1 internal node.

► A binary tree of N internal nodes has N- 1 external node.

http://www.allvupastpapers.blogspot.com/

Question No: 19 ( Marks: 1 ) - Please choose one

Which of the following statement is true about dummy node of threaded binary tree?

► The left pointer of dummy node points to the itself while the right pointer points to the root of tree.

► The left pointer of dummy node points to the root node of the tree while the right pointer points itself i.e. to dummy node

► The left pointer of dummy node points to the root node of the tree while the right pointer is always NULL.

► The right pointer of dummy node points to the itself while the left pointer is always NULL.

Question No: 20 ( Marks: 1 ) - Please choose one

If the bottom level of a binary tree is NOT completely filled, depicts that the tree is NOT a

► Expression tree

► Threaded binary tree

► complete Binary tree

► Perfectly complete Binary tree

http://www.allvupastpapers.blogspot.com/

Question No: 21 ( Marks: 1 ) - Please choose one

In a selection sort of n elements, how many times the swap function is called to complete the execution of the algorithm?

► n-1

► n log n

► n²

► 1

Question No: 22 ( Marks: 1 ) - Please choose one

Which of the following statement is correct about find(x) operation:

► A find(x) on element x is performed by returning exactly the same node that is found.

► A find(x) on element x is performed by returning the root of the tree containing x.

► A find(x) on element x is performed by returning the whole tree itself containing x.

► A find(x) on element x is performed by returning TRUE.

http://www.allvupastpapers.blogspot.com/

Question No: 23 ( Marks: 1 ) - Please choose one

Which of the following statement is NOT correct about find operation:

► It is not a requirement that a find operation returns any specific name, just that finds on two elements return the same answer if and only if they are in the same set.

► One idea might be to use a tree to represent each set, since each element in a tree has the same root, thus the root can be used to name the set.

► Initially each set contains one element.

► Initially each set contains one element and it does not make sense to make a tree of one node only.

Question No: 24 ( Marks: 1 ) - Please choose one

Consider the following postfix expression S and the initial values of the variables.

S = A B - C + D E F - + ^

Assume that A=3, B=2, C=1, D=1, E=2, F=3

What would be the final output of the stack?

► 1

► 2

► 0

► -1

Question No: 25 ( Marks: 1 ) - Please choose one

The maximum number of external nodes (leaves) for a binary tree of height H is _________

► 2^H

► 2^H+1

► 2^H-1

► 2^H+2

http://www.allvupastpapers.blogspot.com/

Question No: 26 ( Marks: 1 ) - Please choose one

In threaded binary tree the NULL pointers are replaced by ,

► preorder successor or predecessor

► inorder successor or predecessor

► postorder successor or predecessor

► NULL pointers are not replaced

Question No: 27 ( Marks: 1 ) - Please choose one

In a min heap , preculateDown procedure will move smaller value______ and bigger value______.

► left,right

► right,left

► up,down

► down,up

http://www.allvupastpapers.blogspot.com/

Question No: 28 ( Marks: 1 ) - Please choose one

Which of the following statement is correct about union:

► To perform Union of two sets, we merge the two trees by making the root of one tree point to the root of the other.

► To perform Union of two sets, we merge the two trees by making the leaf node of one tree point to the root of the other.

► To perform Union of two sets, merging operation of trees in not required at all.

► None of the given options.

Question No: 29 ( Marks: 1 ) - Please choose one

Suppose A is an array containing numbers in increasing order, but some numbers occur more than once when using a binary search for a value, the binary search always finds ____________

► the first occurrence of a value.

► the second occurrence of a value.

► may find first or second occurrence of a value.

► None of the given options.

http://www.allvupastpapers.blogspot.com/

Question No: 30 ( Marks: 1 ) - Please choose one

Let heap stored in an array as H = [50, 40, 37, 32, 28, 22, 36, 13]. In other words, the root of the heap contains the maximum element. What is the result of deleting 40 from this heap

► [50,32, 37,13, 28, 22, 36]

► [37, 28, 32, 22, 36, 13]

► [37, 36, 32, 28, 13, 22]

► [37, 32, 36, 13, 28, 22]

Question No: 31 ( Marks: 1 )

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 that we find the inorder successor of this node and 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.

http://www.allvupastpapers.blogspot.com/

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.

http://www.allvupastpapers.blogspot.com/

0 1 2 3 4 5 6 7

Question No: 35 ( Marks: 3 )

What is an 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?

Quicksort sorts by employing a divide and conquer strategy to divide a list into two sub-lists.

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

http://www.allvupastpapers.blogspot.com/

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

2⁷=14 nodes

Question No: 38 ( Marks: 5 )

Remove the smallest element from the following array which represents a min-heap.

original min-heap

and show the resultant heap in the form of array as shown below,

after removal

http://www.allvupastpapers.blogspot.com/

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.

Question No: 40 ( Marks: 10 )

a) Write C++ algorithm for Binary Search

int isPresent(int *arr, int val, int N)

{

int low = 0;

int high = N - 1;

int mid;

while ( low <= high )

{

mid = ( low + high )/2;

if (arr[mid] == val)

return 1; // found!

else if (arr[mid] < val)

low = mid + 1;

else

high = mid - 1;

}

return 0; // not found

Example

http://www.allvupastpapers.blogspot.com/

int binarySearch(int sortedArray[], int first, int last, int key) {

// function:

// Searches sortedArray[first]..sortedArray[last] for key.

// returns: index of the matching element if it finds key,

// otherwise -(index where it could be inserted)-1.

// parameters:

// sortedArray in array of sorted (ascending) values.

// first, last in lower and upper subscript bounds

// key in value to search for.

// returns:

// index of key, or -insertion_position -1 if key is not

// in the array. This value can easily be

// transformed into the position to insert it.

while (first <= last) {

int mid = (first + last) / 2; // compute mid point.

if (key > sortedArray[mid])

first = mid + 1; // repeat search in top half.

else if (key < sortedArray[mid])

last = mid - 1; // repeat search in bottom half.

else

return mid; // found it. return position /////

}

return -(first + 1); // failed to find key

}

http://www.allvupastpapers.blogspot.com/

b) Consider the following array of values; show how the binary search algorithm would find the value -5. Clearly show/explain your work; that is, show the values of start, end, etc. for each step of the algorithm.

http://www.allvupastpapers.blogspot.com/

Question No: 41 ( Marks: 10 )

Show the result of following sequence of instructions

Union(1,2)

Union(3,4)

Union(3,5)

Union(1,7)

Union(3,6)

Union(8,9)

Union(1,8)

Union(3,10)

Union(3,11)

Union(3,12)

Union(3,13)

Union(14,15)

Union(16,17)

Union(14,16)

Union(1,3)

Union(1,14)

When the unions are performed by height

http://www.allvupastpapers.blogspot.com/

Note: You have to show only Final tree, No need to show all steps.

ALL UNIVERSITIES AND SERVICE COMMISSIONS PAST PAPERS IN PAKISTAN

Pages

PROMOTE MY BLOG: JUST CLICK BELOW BUTTON

Search Any Paper On This Blog

Monday, December 27, 2010

Complete Solved CS301- Data Structures Final term Past Paper Of VU

No comments:

Post a Comment