Papers, Notes, Books & Help For Students

MIDTERM EXAMINATION

Spring 2011

Question No: 1 ( M a r k s: 1 )

A subscript of an array may be an integer or an integer expression.

► True Click here for detail

► False

Question No: 2 ( M a r k s: 1 )

Doubly Linked List always has one NULL pointer.

► True

► False (Page 43)

Question No: 3 ( M a r k s: 1 )

In which of the traversal method, the recursive calls can be used to traverse a binary tree ?

► In preorder traversal only (Page 143)

► In inorder traversal only

► In postorder traversal only

► All of the given options

Question No: 4 ( M a r k s: 1 )

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 (Page 213)

► None of the given options

Question No: 5 ( M a r k s: 1 )

Suppose currentNode refers to a node in a linked list (using the Node class with member variables called data and nextNode). What boolean expression will be true when cursor refers to the tail node of the list?

► (currentNode == null)

► (currentNode->nextNode == null)

► (nextNode.data == null)

► (currentNode.data == 0.0)

Question No: 6 ( M a r k s: 1 ) – Please choose one

Suppose that the class declaration of SomeClass includes the following function prototype. bool LessThan( SomeClass anotherObject );

Which of the following tests in the client code correctly compares two class objects alpha and beta?

► if (alpha < beta)

► if (alpha.LessThan(beta)) Click here for detail

► if (LessThan(alpha, beta))

► if (LessThan(alpha).beta)

Question No: 7 ( M a r k s: 1 )

In C what is the operation that you can not do with primitive types? ► Assign a value to primitive type using a literal

► Declare primitive types to be constant using the Const keyword

► Create a new instance of primitive type with New keyword Click here for Detail

► None of these

Question No: 8 ( M a r k s: 1 )

The operation for adding an entry to a stack is traditionally called : ► add

► append

► insert

► push (Page 53)

Question No: 9 ( M a r k s: 1 )

The operation for removing an entry from a stack is traditionally called: ► delete

► peek

► pop (Page 53)

► remove

Question No: 10 ( M a r k s: 1 )

Consider the following sequence of push operations in a stack:

stack.push(’7’);

stack.push(’8’);

stack.push(’9’);

stack.push(’10’);

stack.push(’11’);

stack.push(’12’);

► 7 8 9 10 11 12

► 9 8 11 10 7 12

► 9 10 8 11 12 7

► 9 10 8 12 7 11

Question No: 11 ( M a r k s: 1 )

________ is the maximum number of nodes that you can have on a stack-linked list ? ► Zero

► 2n (where n is the number of nodes in linked list)

► Any Number Click here for detail

► None of these

Question No: 12 ( M a r k s: 1 )

Which of the following can be used to reverse a string value,

► Stack Click here for detail

► Queue

► Both of these

► None of these

Question No: 14 ( M a r k s: 1 )

AVL Tree is,

► Non Linear data structure Click here for detail

► Linear data structure

► Hybrid data structure (Mixture of Linear and Non Linear) ► None of the given options.

Question No: 15 ( M a r k s: 1 )

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 Click here for detail

Question No: 16 ( M a r k s: 1 )

An array is a group of consecutive related memory locations.

► True Click here for detail

► False

s height.

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

Is a data structure that can grow easily dynamically at run time without having to copy existing elements? ► Array

► List

► Both of these

► None of these

**CS301 Data Structures Solved MCQs**

For a perfect binary tree of height 4. What will be the sum of heights of nodes?

31

3027

26

For a perfect binary tree of height h, having N nodes, the sum of heights of nodes is _____________.

N – (h – 1)

N – (h + 1)

N – 1

N – 1 + h

If we want to find median of 50 elements, then after applying buildHeap method, how many times deleteMin method will be called ?

5

25

35

50

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)

www.vuzs.net

The main reason of using heap in priority queue is

improve performance

code is readable

less code

heap can’t be used in priority queues

The total number of nodes on 10th level of a perfect binary tree are :

256

512

1024

Can’t be determined

Which property of equivalence relation is satisfied if we say: Ahmad R(is related to) Ahmad

Reflexivity

Symmetry

Transitivity

All of the above

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

increaseKey(p,delta)

decreaseKey(p,delta)

preculateDown(p,delta)

remove(p,delta)

We can build a heap in _____ time.

Linear

Exponential

Polynomial

None of the given options

we can build a heap in linear time using n calls of percolate_down()

If a tree has 50 nodes, then the total edges/links in the tree will be :

55

51

50

49 N-1= 49

**40,30,20,10,15,16,17,8,4,35****
**40,30,20,10,35,16,17,8,4,15

40,35,20,10,30,16,17,8,4,15

40,35,20,10,15,16,17,18,4,30

**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) ___________Successor****.**

Preorder

**Inorder****
**Postorder

Leveloder

**Which of the following is a property of binary tree?****
**A Binary tree with N internal nodes has 2+N links, N-1 links to internal nodes and N+1 links to external nodes

A Binary tree with N internal nodes has 2*N links, N-1 links to internal nodes and N+1 links to external nodes.

A Binary tree with N internal nodes has 2-N links, N-1 links to internal nodes and N+1 links to external nodes.

**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)_____________ successor.****
**Preoder

Levelorder

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

54

55

56

**57**

**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 PREORDER successor.****
**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 POSTORDER predecessor.

**It is necessary fro Huffman encoding tree to be,**

AVL tree

**Binary tree****
**Complete binary Tree

None of these

**A binary tree with 45 internal nodes has _________ links to external nodes****.**

44

45

**46****
**90

**In which of the following tree, parent nodes has key greater than or equal to its both children?**

Max heap

Binary search tree

Threaded Binary tree

**Complete Binary tree**

**If one pointer of the nodes in a binary tree is NULL then it will be a/an**

Inner node

Leaf node

External node

Root node

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

N

**See the below code and fill the appropriate answer for? Void fastlnorder(TreeNod+p) {while((p+nextInorder(p)) !+ ? ) cout << p->getInfo();}**

**Dummy****
**rootNode

LTH

RTH

http://www.thecyberians.com/vu-forum

**In threaded binary tree, the NULL pointer are replaced by the****.
**Preorder successor or Predecessor

NULL pointer are not replaced

**In which of the following tree, parent nodes has a key greater than or equal to its both children?**

Max heap

Binary search tree

Threaded Binary three

Complete Binary tree

**In Complete binary tree the bottom level is filled from _______****.**

**Left to right****
**Right to left

Not filled at all

None of the given options

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

**Complete Binary tree****
**Threaded Binary Tree

Expression tree

Perfectly compete Binary tree

**If an expression tree is correct then its root should have,**

**An operator****
**(

)

an operand

**In threaded binary tree, the NULL pointers are replaced by the****.**

Preorder successor or predecessor

Inorder successor or predecessor

Postorder successor or predecessor

NULL pointer are not replaced

**A complete binary tree is a tree that is ________ filled, with the possible exception of the bottom level.**

Partially

**Completely****
**Incompletely

Partly

**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

**An expression tree will always be a,****
**Complete binary tree

**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 has N-1 external node

**In a threaded binary tree which nodes have NULL child pointers,**

**All leaf nodes**

Nodes other then leaf nodes

Root Node

None of the nodes

**In threaded binary tree, the NULL pointers are replaced by the**

preorder successor or predecessor

**inorder successor or predecessor**

postorder successor or predecessor

NULL pointers are not replaced

**A complete binary tree is a tree that is ****_______**** filled, with the possible exception of the bottom level****.**

partially

**completely**

incompletely

partly

**Which one of the following is TRUE about iteration?**

Iterative function calls consumes a lot of memory

Threaded Binary Trees use the concept of iteration

**Iteration extensively uses stack memory**

Recursion is more efficient than iteration

http://www.thecyberians.com/vu-forum

**We implement the heap by ****____________**** ****.**

Threaded Tree

AVL tree

**Complete binary tree**

Expression

**Which of the following statement concerning heaps is NOT true?**

**Traversing a heap in order provides access to the data in numeric or alphabetical order.****
**Removing the item at the top provides immediate access to the key value with highest (or lowest) priority.

Inserting an item is always done at the end of the array, but requires maintaining the heap property.

A heap may be stored in an array.

**Which of the following statement concerning heaps is NOT true?**

A heap can be stored in a binary search tree.

A heap can be stored in an array.

A heap can be used to implement a priority queue.

A heap can be used to sort data.

**A complete binary tree is a tree that is _________ filled, with the possible exception of the bottom level.**

partially

**completely****
**incompletely

partly

**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

Heap data structure

Huffman encoding

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.

**Threaded binary tree**

**When a complete binary tree, represented by an array then for any array element at position i, the parent is at position ______ .****
**2i-1

2i

2i+1

**When a complete binary tree represented by an array then if right child is at position 5 then left child will be at position _____****
**2

3

**A binary tree with N internal nodes has _____ links, _______ links to internal nodes and ________ links to external nodes.****
2N, N-1, N+1
**N-1, 2N, N+1

N+1, 2N, N-1

N+1, N-1, 2N

**If a binary tree has N + 1 external nodes then,****
It has N internal nodes**.

It has N-1 internal nodes.

It has N/2 internal nodes.

It has N+2 internal nodes.

**A binary tree with 45 internal nodes has _______links to external nodes.****
**44

45

46

90

**Consider a binary tree, represented by the following array: 10,7,9,5,2,1,6,3,4 This is a ________.****
**Min heap

Max heap (Not Sure)

Threaded binary tree

Binary Search tree

**In threaded binary tree the NULL pointers are replaced by the****
**preorder successor or predecessor

NULL pointers are not replaced

**Consider a binary tree, represented by the following array: A,B,C,D,E,F,G,H,I,J,K,L Is it a strictly binary tree?****
**Yes

**We implement the heap by ______________ .****
**Threaded Tree

AVL tree

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

► 54

► 55

► 56

**► 57**

** **

**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.

**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.

** **

**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 right pointer of dummy node points to the itself while the left pointer is always NULL.

**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

** 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.

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

** ► **23

** ► **2

** ► **21

** ► 22**

f 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

**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 POSTORDER successor.

**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****
► **Heap data structure

**Consider a min heap, represented by the following array:**

**10,30,20,70,40,50,80,60**

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

** ► 10,30,20,31,40,50,80,60,70 ****
► **10,30,20,70,40,50,80,60,31

**In complete binary tree the bottom level is filled from ________****.**

** ► Left to right****
► **Right to left

**In case of deleting a node from AVL tree, rotation could be prolong to the ****root**** node.****
► Yes
► **No

**When an array of object is created dynamically then there is no way to provide parameterized constructors for array of objects****.
**

**Which of the following method is helpful in creating the heap at once?**

Insert

add

update

**preculateDown**