CS301 Data Structure Quizzes File No 6

Question # 1 of 10 ( Start time: 07:36:03 PM ) Total Marks: 1
For a perfect binary tree of height h, having N nodes, the sum of heights of nodes is _____________.
Select correct option:
N – (h – 1) 
N – (h + 1)
N – 1
N – 1 + h


Question # 2 of 10 ( Start time: 07:36:32 PM ) Total Marks: 1
The expression if ( ! heap->isEmpty() ) checks
Select correct option:
Heap is empty
Heap is full
Heap is not empty 
Not a valid expression


Question # 3 of 10 ( Start time: 07:36:55 PM ) Total Marks: 1
Which one of the following is NOT the property of equivalence relation?
Select correct option:
Reflexive
Symmetric
Transitive
Associative 


Question # 4 of 10 ( Start time: 07:37:22 PM ) Total Marks: 1
If a tree has 20 edges/links, then the total number of nodes in the tree will be :
Select correct option:
19 
20
21
Can't be determined


Question # 5 of 10 ( Start time: 07:37:58 PM ) Total Marks: 1
We can build a heap in _____ time.
Select correct option:
Linear 
Exponential
Polynomial
None of the given options


Question # 5 of 10 ( Start time: 07:37:58 PM ) Total Marks: 1
We can build a heap in _____ time.
Select correct option:
Linear 
Exponential
Polynomial
None of the given options


Question # 6 of 10 ( Start time: 07:38:23 PM ) Total Marks: 1
given the values are the array representation of heap; 12 23 26 31 34 44 56 64 78 100 If we perform 4 deleteMin operations, the last element deleted is__________.
Select correct option:
31
34 
44
56


Question # 8 of 10 ( Start time: 07:39:48 PM ) Total Marks: 1
Suppose there are a set of fruits and a set of vegetables. Both sets are ______________ sets.
Select correct option:
Disjoint 
Subsets
Whole
Equal


Question # 10 of 10 ( Start time: 07:40:42 PM ) Total Marks: 1
The preculateDown procedure will move the smaller value____ and bigger value______.
Select correct option:
left,right
right,left
up,down 
down,up

FINALTERM  EXAMINATION

Fall 2009

CS301- Data Structures

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

__________ only removes items in reverse order as they were entered.

       ► Stack

       ► Queue

       ► Both of these

       ► None of these

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

Here is a small function definition:

void f(int i, int &k)

{

i = 1;

k = 2;

}

Suppose that a main program has two integer variables x and y, which are given the value 0. Then the main program calls f(x,y); What are the values of x and y after the function f finishes?

       ► Both x and y are still 0.

       ► x is now 1, but y is still 0.

       ► x is still 0, but y is now 2.

       ► x is now 1, and y is now 2.

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

Select the one FALSE statement about binary trees:

       ► Every binary tree has at least one node.

       ► Every non-empty tree has exactly one root node.

       ► Every node has at most two children.

       ► Every non-root node has exactly one parent.

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

Every AVL is _________________

       ► Binary Tree

       ► Complete Binary Tree

       ► None of these

       ► Binary Search Tree  

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

Searching an element in an AVL tree take maximum _______ time (where n is no. of nodes in AVL tree),

       ► Log₂(n+1)

       ► Log₂(n+1) -1

       ► 1.44 Log₂n

       ► 1.66 Log₂n

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

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.

       ► The reheapification is done.

       ► The next step will interchange the two children of the out-of-place node.

       ► The next step will swap the out-of-place node with its parent.

       ► The next step will swap the out-of-place node with its left child.

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

Suppose you implement a heap (with the largest element on top) in an array. Consider the different arrays below, determine the one that cannot possibly be a heap:

       ► 7 6 5 4 3 2 1

       ► 7 3 6 2 1 4 5

       ► 7 6 4 3 5 2 1

       ► 7 3 6 4 2 5 1

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

If there are 23 external nodes in a binary tree then what will be the no. of internal nodes in this binary tree?

       ► 23

       ► 24

       ► 21

       ► 22

Lesson # 27(the number of internal nodes is N, the number of external nodes will be N+1.)
Question No: 9      ( Marks: 1 ) – Please choose one

If there are N external nodes in a binary tree then what will be the no. of internal nodes in this binary tree?

       ► N -1

       ► N+1

      ► N+2

       ► N

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

Which one of the following is NOT the property of equivalence relation:

       ► Reflexive

       ► Symmetric

       ► Transitive

       ► Associative (lesson no 34)

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

The definition of Transitivity property is

       ► For all element x member of S, x R x

       ► For all elements x and y, x R y if and only if y R x

       ► For all elements x, y and z, if x R y and y R z then x R z   (lesson no 34)

       ► For all elements w, x, y and z, if x R y and w R z then x R z

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

Union is a _______ time operation.

       ► Constant ( lesson # 35 page 11)

       ► Polynomial

       ► Exponential

       ► None of the given option

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

Which of the following is NOT a correct statement about Table ADT.

► In a table, the type of information in columns may be different. yes

► A table consists of several columns, known as entities. (Lesson # 38 page 1 )

► The row of a table is called a record.

► A major use of table is in databases where we build and use tables for keeping information.

 Correct  A table consists of several columns, known as fields.

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

In the worst case of deletion in AVL tree requires  _________.

       ► Only one rotation 

       ► Rotation at each non-leaf node 

       ► Rotation at each leaf node

       ► Rotations equal to log2 N   (lesson # 23)

Question No: 15      ( Marks: 1 ) – Please choose on

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

► Sorted  (lesson # 39)

► Unsorted

► Heterogeneous

► Random

Question No: 16      ( Marks: 1 ) – Please choose on

Which of the following statement is correct?

► A Threaded Binary Tree is a binary tree in which every node that does not have a left child has a THREAD (in actual sense, a link) to its INORDER successor.

  ► A Threaded Binary Tree is a binary tree in which every node that does not have a right child has a THREAD (in actual sense, a link) to its PREOREDR successor.

► A Threaded Binary Tree is a binary tree in which every node that does not have a right child has a THREAD (in actual sense, a link) to its INORDER successor.

► A Threaded Binary Tree is a binary tree in which every node that does not have a right child has a THREAD (in actual sense, a link) to its POSTORDER successor.

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

By using __________we avoid the recursive method of traversing a Tree, which makes use of stacks and consumes a lot of memory and time.

       ► Binary tree only

       ► Threaded binary tree (lesson # 27 page 3)

       ► Heap data structure

       ► Huffman encoding

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

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

       ► Right thread of the right-most node points to the dummy node.

       ► Left thread of the left-most node points to the dummy node.

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

       ► Left thread of the right-most node points to the dummy node.

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

Consider a min heap, represented by the following array:

11,22,33,44,55

After inserting a node with value 66.Which of the following is the updated min heap?

       ► 11,22,33,44,55,66

       ► 11,22,33,44,66,55

       ► 11,22,33,66,44,55

       ► 11,22,66,33,44,55

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

Consider a min heap, represented by the following array:

3,4,6,7,5

After calling the function deleteMin().Which of the following is the updated min heap?

       ► 4,6,7,5

       ► 6,7,5,4

       ► 4,5,6,7

       ► 4,6,5,7

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

We can build a heap in  ________  time.

       ► Linear (lecture # 30 page 8)

       ► Exponential

       ► Polynomial

       ► None of the given options

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

Suppose we are sorting an array of eight integers using quick sort, 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?

       ► The pivot could be either the 7 or the 9.

       ► The pivot could be the 7, but it is not the 9.

       ► The pivot is not the 7, but it could be the 9

       ► Neither the 7 nor the 9 is the pivot.

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

Which formula is the best approximation for the depth of a heap with n nodes?

       ► log (base 2) of n

       ► The number of digits in n (base 10), e.g., 145 has three digits

       ► The square root of n

       ► n

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

Suppose you implement a Min heap (with the smallest element on top) in an array. Consider the different arrays below; determine the one that cannot possibly be a heap:

       ► 16, 18, 20, 22, 24, 28, 30  

       ► 16, 20, 18, 24, 22, 30, 28

       ► 16, 24, 18, 28, 30, 20, 22

       ► 16, 24, 20, 30, 28, 18, 22

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

While joining nodes in the building of Huffman encoding tree if there are more nodes with same frequency, we choose the nodes _______.

       ►  Randomly 

       ►  That occur first in the text message 

       ► That are lexically smaller among others.

       ►  That are lexically greater among others  

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

Consider the following paragraph with blanks.

A …….…….. is a linear list where …………… and ………… take place at the

same end . This end is called the …….……….

What would be the correct filling the above blank positions?

       ► (i) queue (ii) insertion (iii) removals (iv) top

       ► (i) stack (ii) insertion (iii) removals (iv) bottom

       ► (i) stack (ii) insertion (iii) removals (iv) top

       ► (i) tree (ii) insertion (iii) removals (iv) top

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

A binary tree with 33 internal nodes has _______ links to internal nodes.

       ► 31

       ► 32          (n-1 links to internal nodes)

       ► 33

       ► 66            (2n links)

Question No: 28      ( Marks: 1 ) – Please choose on

Which traversal gives a decreasing order of elements in a heap where the max element is stored at the top?

       ► post-order

       ► level-order

       ► inorder

       ► None of the given options

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

What requirement is placed on an array, so that binary search may be used to locate an entry

       ► The array elements must form a heap.

       ► The array must have at least 2 entries.

       ► The array must be sorted. (lecture # 38)

       ► The array’s size must be a power of two.

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

Which of the following is a non linear data structure?

       ► Linked List

       ► Stack

       ► Queue

       ► Tree   

CS301 Solved Mid Term Papers 

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

In the statement int x[6]; , we cannot assign any value to x because x is not an lvalue. 

       ► True

       ► False 

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

What will be postfix expression of the following infix expression?

Infix Expression : a+b*c-d 

       ► ab+c*d- 

       ► abc*+d-

       ► abc+*d- 

       ► abcd+*- 

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

In a program a reference variable, say x, can be declared as  

       ►  int &x ;  

       ►  int *x ; 

       ►  int x ;  

       ► None of the given options

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

A tree is an AVL tree if  

       ► Any one node fulfills the AVL condition  

       ► At least half of the nodes fulfill the AVL condition 

       ► All the nodes fulfill the AVL condition  

       ► None of the given options 

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

Consider the following pseudo code                                                                                               

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 )
{
pop a character off the stack
write the character to the screen
}
What is written to the screen for the input “apples”?

       ► selpa 

       ► selppa 

       ► apples 

       ► aaappppplleess 

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

In the following C++ code, how many function calls are made? 

            int x, y, z;

            x = 2;

            y = 3 + x;

            z = foobar(x,y); 

       ► 1 

       ► 4 

       ► 7 

       ► 8 

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

We can add elements in QUEUE From _________ 

       ► Front 

       ► Rear 

       ► From Both Rare and Front

       ► None of these 

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

Consider the following tree.

How many of the nodes have at least one sibling? 

       ► 8 

       ► 7

       ► 5 

       ► 6 

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

Consider the following tree.

How many descendants does the root have? 

       ► 5 

       ► 6 

       ► 7


       ► 8 

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

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

Which of the following statement regarding binary tree is NOT correct. 

       ► A binary tree can contain at least 2^L Nodes at level L. 

       ► A complete binary tree of depth d is a binary tree that contains 2^L Nodes at each level L between 0 and d, both inclusive. 

       ► The total number of nodes (Tn ) in a complete binary tree of depth d is 2 ^d+1 – 1 . 

       ► The height of the complete binary tree can be written as h = log 2 (Tn+1)-1 where Tn is Total number of Nodes.

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

The following are statements related to queues.

(i)   The last item to be added to a queue is the first item to be removed

(ii) A queue is a structure in which both ends are not used

(iii)  The last element hasn’t to wait until all elements preceding it on the queue are removed

(iv)  A queue is said to be a last-in-first-out list or LIFO data structure.

Which of the above is/are related to normal queues?

       ► (iii) and (ii) only 

       ► (i), (ii) and (iv) only 

       ► (ii) and (iv) only 

       ► None of the given options

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

The________method of list data structure removes the element residing at the current position.

       ► Add

       ► next 

       ► remove

       ► find 

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

it will be efficient to place stack elements at the start of the list because insertion and removal take _______time.  

       ► Variable 

       ► Constant

       ► Inconsistent 

       ► None of the above