CS301 Past Mid Term Paper

CS301 Past Mid Term Paper

Spring 2011

CS301- Data Structures

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

 

Which one of the following calling methods does not change the original value of the argument in the calling function? 

       ► None of the given options

       ► Call by passing the value of the argument

       ► Call by passing reference of the argument

       ► Call by passing the address of the argument

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

 

Which one is a self- referential data type?                                                                    

       ► Stack

       ► Queue

       ► Link list

       ► All of these

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

 

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: 4      ( Marks: 1 ) - Please choose one

 

We access elements in AVL Tree in,

       ► Linear way only

       ► Non Linear way only

       ► Both linear and non linear ways

       ► None of the given options.

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

 

“+” is a _________operator.

       ► Unary

       ► Binary

       ► Ternary

       ► None of the above

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

 

“--” is a _________operator.

       ► Unary

       ► Binary

       ► Ternary

       ► None of the above

Question No: 7      ( 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: 8      ( Marks: 1 ) - Please choose one

 What is the maximum depth of recursive calls a function may make?

       ► 1

       ► 2

       ► n (where n is the argument)

       ► There is no fixed maximum

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

 Suppose n is the number of nodes in a complete Binary Tree then maximum steps required for a search operation are,

       ► Log₂ (n+1) -1

       ► Log₂ (n+1)

       ► Log₂ (n) – 1

       ► Log₂ (n)

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

 _________ is a binary tree where every node has a value, every node's left subtree contains only values less than or equal to the node's value, and every node's right subtree contains only values that are greater then or equal ?                                                                    

►Strictly Binary Tree

►Binary Search tree

►AVL tree

►All of these

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

 Below is a binary search tree. If we delete the value 50 using the algorithm we discussed, what value will be in the root of the remaining tree?

       ► 50

       ► 60

       ► 70

       ► 80

   

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

 

Four statements about trees are below. Three of them are correct. Which one is INCORRECT?

       ► Trees are recursively defined multi-dimensional data structures

       ► The order of a tree indicates a maximum number of childen allowed at each node of the tree

       ► A search tree is a special type of tree where all values (i.e. keys) are ordered

       ► If Tree1's size is greater than Tree2's size, then the height of Tree1 must also be greater than Tree2's height.

Question No: 21      ( Marks: 2 )

 

Define Complete Binary tree

Question No:      ( Marks: 2 )

 

Write APPLIICATION  OF BST

 Question No:      ( Marks: 3 )

 What normally is the sequence of operations while constructing an AVL tree?

Question No:       ( Marks: 3 )

 

Define the following

The Height of the Tree:

The definition of height of a tree is:

 The height of a binary tree is the maximum level of its leaves (also called the depth).

The balance of a node:

The balance of a node is defined as:

The balance of a node in a binary tree is defined as the height of its left subtree

minus height of its right subtree.

Question No:       ( Marks: 5)

 

Define